Итак, я делаю парсер, где я предпочитаю гибкость, а не скорость, и я хочу, чтобы было легко писать грамматики, например нет хитрых правил обхода (фальшивые правила для разрешения конфликтов и т. д., как вы должны делать в yacc / bison и т. д.)
Существует Lexer с ручным кодированием с фиксированным набором токенов (например, PLUS, DECIMAL, STRING_LIT, NAME и т. Д.). Сейчас существует три типа правил:
- TokenRule: соответствует определенному токену
- SequenceRule: соответствует упорядоченному списку правил
- GroupRule: соответствует любому правилу из списка
Например, допустим, у нас есть TokenRule 'varAccess', который соответствует токену NAME (примерно / [A-Za-z] [A-Za-z0-9 _] * /), и SequenceRule 'assignment', который соответствует [выражение, TokenRule (PLUS), выражение].
Выражение - это GroupRule, совпадающее либо с «назначением», либо с «varAccess» (фактический набор правил, с которым я тестирую, немного более полон, но для примера это подходит)
Но теперь допустим, я хочу разобрать
var1 = var2
И скажем, парсер начинается с правила Expression (порядок, в котором они определены, не должен иметь значения - приоритеты будут решены позже). И скажем, выражение GroupRule сначала попробует «назначение». Затем, поскольку «выражение» - это первое правило, которое должно быть найдено в «присваивании», оно будет пытаться снова проанализировать выражение и т. Д., Пока стек не будет заполнен, и компьютер - как и ожидалось - просто сдается в искрящем segfault.
Так что я сделал - SequenceRules добавляют себя в качестве «листьев» к своему первому правилу и становятся нерутовыми правилами. Корневые правила - это правила, которые парсер сначала попробует. Когда один из них применяется и совпадает, он пытается применить каждый из своих листьев один за другим, пока один не совпадет. Затем он пробует листы совпадающего листа и так далее, пока ничто больше не совпадает.
Так что он может анализировать выражения вроде
var1 = var2 = var3 = var4
В самый раз =) Теперь интересные вещи. Этот код:
var1 = (var2 + var3)
Не будет разбирать. Что происходит, так это то, что var1 анализируется (varAccess), назначается подприложение, он ищет выражение, пробует «скобки», начинает, ищет выражение после «(», находит var2, а затем нажимает на «+» «потому что ожидал»).
Почему он не совпадает с 'var2 + var3'? (и да, есть «добавить» SequenceRule, прежде чем вы спросите). Поскольку 'add' не является корневым правилом (чтобы избежать бесконечной рекурсии с помощью parse-expresssion-begin-with-expression-etc.) И что листы не проверяются в SequenceRules, в противном случае он будет анализировать такие вещи, как
reader readLine() println()
в
reader (readLine() println())
(например, '1 = 3' - ожидаемое выражение от add, лист varAccess a)
тогда как мы хотели бы, чтобы оно было левоассоциативным, например парсинг как
(reader readLine()) println()
Так или иначе, теперь у нас есть такая проблема, что мы должны иметь возможность анализировать выражения, такие как '1 + 2' в SequenceRules. Что делать? Добавьте особый случай, когда SequenceRules начинаются с TokenRule, а содержащиеся в нем GroupRules проверяются на наличие листьев? Будет ли это иметь смысл вне этого конкретного примера? Или нужно уметь указывать в каждом элементе SequenceRule, должен ли он быть проверен на наличие листьев или нет? Скажите мне, что вы думаете (кроме как отбросить всю систему - это, вероятно, произойдет через несколько месяцев)
П.С .: Пожалуйста, довольно, пожалуйста, не отвечайте на что-то вроде «иди и прочитай эту книгу на 400 страницах, или ты даже не заслуживаешь нашего времени». Если вы чувствуете необходимость - просто воздержитесь и идите на Reddit. Хорошо? Заранее спасибо.