Решите двусмысленность в моей грамматике с парсером LALR

Question

Я использую whittle для разбора грамматики, но сталкиваюсь с классической проблемой неоднозначности LALR. Моя грамматика выглядит так (упрощенно):

<comment> ::= '{' <string> '}'           # string enclosed in braces
<tag> ::= '[' <name> <quoted-string> ']' # [tagname "tag value"]
<name> ::= /[A-Za-z_]+/                  # subset of all printable chars
<quoted-string> ::= '"' <string> '"'     # string enclosed in quotes
<string> ::= /[:print:]/                 # regex for all printable chars

Проблема, конечно же, заключается в <string>, Он содержит все печатные символы и поэтому очень жадный. Так как это LALR-парсер, он пытается разобрать <name> как <string> и все ломается. Грамматика усложняет ситуацию, потому что она использует разные разделители строк для разных вещей, поэтому я попытался сделать <string> правило в первую очередь.

Есть ли канонический способ нормализовать эту грамматику, чтобы сделать ее LALR-совместимой, если это вообще возможно?

Answer 1

Это не "классическая проблема двусмысленности LALR", что бы это ни было. Это просто ошибка в лексической спецификации языка.

Я быстро взглянул на readme Уиттла, но он не имел никакого сходства с грамматикой в ​​OP. Поэтому я предполагаю, что текст в ОП скорее концептуальный, чем буквальный, и тот факт, что он включает в себя явно неправильный

<string> ::= /[:print:]/                 # regex for all printable chars

это просто опечатка.

Лучше было бы /[:print:]*/предполагая, что Ruby позволяет вам [:print:] а не стандарт Posix [[:print:]],

Но это также не будет правильным, потому что lexing (обычно) соответствует самой длинной из возможных строк, и, следовательно, это сожрет заключительную кавычку и любой последующий текст.

Так что правильное решение для quoted-string это правильно написать:

<quoted-string> ::= /"[^"]*"/

или даже

<quoted-string> :: /"([^\\"]|\\.)*"/
# any number of characters other than quote or escape, or escaped pairs

У вас могут быть другие идеи о том, как избежать внутренних двойных кавычек; это всего лишь примеры. В обоих случаях вам нужно постобработать токен, чтобы (как минимум) убрать двойные кавычки и, возможно, интерпретировать escape-последовательности. Это просто так.

Ваши последовательности комментариев представляют более сложную проблему, если предположить, что вы предполагаете, что комментарий может содержать вложенные скобки (например, {This comment {with this} ends here}) потому что синтаксис вложенных скобок не является регулярным и поэтому не может быть сопоставлен с регулярным выражением. Конечно, очень немногие библиотеки "регулярных выражений" действительно являются регулярными в наши дни, и я не знаю, содержит ли Ruby какое-то расширение для подсчета фигурных скобок, как, например, синтаксис шаблона Lua. Синтаксис вложенных фигурных скобок, безусловно, не зависит от контекста, но для его синтаксического анализа вам необходим лексический анализ содержимого внешнего {...} по-другому, чем остальная часть программы.

Именно это последнее наблюдение, а не какая-либо слабость в алгоритме LALR, причиняет вам боль, и я бы сказал, что это слабость в разделе лексического анализа (в основном недокументированного на афике). Например, в сгенерированном во флексах лексере было бы нормально использовать начальные условия для разделения лексических сред (программа / строка в кавычках / фигурный комментарий), и тогда парсер не имел бы никакой двусмысленности.

Надеюсь, это поможет.