Правила разбора - как заставить их хорошо играть вместе

Question

Итак, я делаю синтаксический анализатор, в котором я предпочитаю гибкость скорости, и я хочу, чтобы для него было легко писать грамматики, напримерникаких хитрых правил обхода (поддельные правила для разрешения конфликтов и т.д., Как вы должны делать в yacc / bison и т.д.)

Существует закодированный вручную лексер с фиксированным набором токенов (напримерПЛЮС, ДЕСЯТИЧНОЕ ЧИСЛО, STRING_LIT, NAME и так далее) прямо сейчас существует три типа правил:

• Токен - правило:соответствует определенному токену
• Последовательность действий:соответствует упорядоченному списку правил
• Групповое правило:соответствует любому правилу из списка

Например, предположим, что у нас есть TokenRule 'varAccess', которое соответствует ИМЕНИ токена (примерно /[A-Za-z][A-Za-z0-9_]*/), и SequenceRule 'assignment', которое соответствует [expression, TokenRule(PLUS), выражение].

Выражение - это групповое правило, соответствующее либо 'assignment', либо 'varAccess' (фактический набор правил, с которым я тестирую, немного более полный, но этого хватит для примера)

Но теперь, допустим, я хочу разобрать

var1 = var2

И допустим, анализатор начинается с выражения правила (порядок, в котором они определены, не должен иметь значения - приоритеты будут решены позже).И допустим, выражение GroupRule сначала попробует 'assignment'.Затем, поскольку 'expression' - это первое правило, которому нужно соответствовать в 'assignment', оно попытается снова проанализировать выражение, и так далее, пока стек не будет заполнен и компьютер, как и ожидалось, просто не сдастся в результате блестящего сбоя в сегменте.

Итак, что я сделал, так это то, что SequenceRules добавляют себя как "листья" к своему первому правилу и становятся некорневыми правилами.Корневые правила - это правила, которые анализатор будет опробовать в первую очередь.Когда один из них применяется и совпадает, он пытается повторно применить каждый из своих листов, один за другим, пока один не совпадет.Затем он пробует створки соответствующего листа и так далее, пока больше ничего не совпадет.

Чтобы он мог анализировать выражения типа

var1 = var2 = var3 = var4

В самый раз =) Теперь самое интересное.Этот код:

var1 = (var2 + var3)

Не будет разбираться.Что происходит, var1 анализируется (varAccess), присваивается дополнительный параметр, он ищет выражение, пробует 'parenthesis', запускается, ищет выражение после '(', находит var2, а затем прерывается на '+', потому что ожидалось ')'.

Почему это не соответствует 'var2 + var3' ?(и да, есть 'add' SequenceRule, прежде чем вы спросите).Потому что 'add' не является корневым правилом (чтобы избежать бесконечной рекурсии с помощью parse-expresssion-beginning-with-expression-etc.) И что leafs не тестируются в SequenceRules, иначе он анализировал бы такие вещи, как

reader readLine() println()

как

reader (readLine() println())

(например,'1 = 3' - это выражение, ожидаемое add, лист varAccess a)

в то время как мы хотели бы, чтобы он был левоассоциативным, напримерразбор как

(reader readLine()) println()

Итак, в любом случае, теперь у нас есть проблема, заключающаяся в том, что мы должны иметь возможность анализировать выражения, такие как '1 + 2', в SequenceRules .Что же делать?Добавить особый случай, когда SequenceRules начинаются с TokenRule, тогда содержащиеся в нем GroupRules проверяются на наличие листьев?Будет ли это вообще иметь смысл вне этого конкретного примера?Или нужно иметь возможность указать в каждом элементе SequenceRule, следует ли его тестировать на наличие листьев или нет?Скажите мне, что вы думаете (кроме того, что выбросите всю систему - это, вероятно, произойдет в любом случае через несколько месяцев)

P.S:Пожалуйста, очень пожалуйста, не отвечайте что-то вроде "иди прочти эту книгу на 400 страниц, иначе ты даже не заслуживаешь нашего времени", если ты чувствуешь необходимость - просто воздержись от этого и заходи на reddit.Ясно?Заранее благодарю.

Answer 1

LL (k) синтаксические анализаторы (рекурсивные сверху вниз, будь то автоматизированные или написанные вручную) требуют рефакторинга вашей грамматики, чтобы избежать левой рекурсии, и часто требуют специальных спецификаций lookahead (напримерANTLR), чтобы иметь возможность обрабатывать предварительный просмотр k-токена.Поскольку грамматики сложны, вы можете обнаружить k, экспериментируя, а это именно то, чего вы хотите избежать.

Грамматики YACC / LALR(1) решают проблему левой рекурсии, что является большим шагом вперед.Плохая новость заключается в том, что не существует реальных языков программирования (кроме оригинального PASCAL Вирта), которые являются LALR(1).Следовательно, вы можете взломать свою грамматику, чтобы изменить ее с LR (k) на LALR (1), снова заставляя вас страдать от экспериментов, которые выявляют странные случаи, и взламывая логику сокращения грамматики, чтобы попытаться обработать K-предвидения, когда генераторы синтаксического анализа (YACC, BISON, ...вы называете это) создайте парсеры с 1 обзором.

Анализаторы GLR (http://en.wikipedia.org/wiki/GLR_parser) позволяют вам избежать почти всей этой чепухи.Если вы можете написать контекстно-свободный анализатор, то в большинстве практических случаев анализатор GLR обработает его без дополнительных усилий.Это огромное облегчение, когда вы пытаетесь писать произвольные грамматики.И действительно хороший анализатор GLR непосредственно создаст дерево.

BISON был усовершенствован для выполнения синтаксического анализа GLR, вроде как.Вам все еще придется написать сложную логику для создания желаемого AST, и вам придется беспокоиться о том, как обрабатывать сбойные синтаксические анализаторы и очищать / удалять соответствующие им (сбойные) деревья.В Tookit Реинжиниринг программного обеспечения DMS предоставляет стандартные парсеры GLR для любой контекстно-свободной грамматики и автоматически создает ASTS без каких-либо дополнительных усилий с вашей стороны;неоднозначные деревья создаются автоматически и могут быть очищены с помощью семантического анализа после синтаксического анализа.Мы использовали это, чтобы определить более 30 языковых грамматик, включая C, включая C ++ (который, как считается, сложен для анализа [и его почти невозможно проанализировать с помощью YACC], но прост с реальным GLR);видишь Анализатор интерфейса C +++ и конструктор AST на основе DMS.

Итог:если вы хотите написать грамматические правила простым способом и получить анализатор для их обработки, используйте технологию синтаксического анализа GLR.Бизон почти работает.DMs действительно работает.

Answer 2

Мой любимый метод синтаксического анализа - создать анализатор рекурсивного спуска (RD) на основе спецификации грамматики PEG.Обычно они очень быстрые, простые и гибкие.Одним из приятных преимуществ является то, что вам не нужно беспокоиться об отдельных проходах токенизации, а беспокоиться о том, чтобы втиснуть грамматику в какую-либо форму LALR, не существует.Некоторые библиотеки PEG перечислены [здесь][1].

Извините, я знаю, что это относится к выбрасыванию системы, но вы едва справились со своей проблемой, и переход на анализатор PEG RD просто избавил бы вас от головной боли сейчас.