Несмотря на заголовок вашего поста, ваша грамматика не является двусмысленной. Это просто не LR (1) по той причине, которую вы упомянули: вход
A ( B ,
может быть началом Call_expr или Iter_expr. В первом случае значение B должно быть уменьшено до Expr, а затем до Args; во втором случае его нельзя уменьшать, поскольку он должен быть равен id, когда правая часть id '(' id ',' id ':' id '/' Expr ')' уменьшена. Решение нельзя принять, просто взглянув на один жетон предпросмотра (, ), поэтому возникает конфликт сдвиг-уменьшение.
Этот конфликт может быть разрешен не более чем двумя дополнительными жетонами предпросмотра, поскольку смещение является допустимым действием, только если за , следует точно id, а затем : . Так что это делает грамматику LALR (3). К сожалению, Ply не генерирует парсеры LALR (3) (как и yacc / bison), но есть некоторые альтернативы.
1. Используйте другой алгоритм разбора
Поскольку грамматика однозначна, она может быть проанализирована без проблем (и без каких-либо изменений) с помощью синтаксического анализатора GLR. Ply также не производит парсеры GLR, но Bison может. Это вряд ли будет вам полезно, но я подумал, что стоит упомянуть об этом, если вы не используете Python.
2. Используйте грамматику, которая допускает некоторые неверные входные данные, и отбросьте их с помощью семантического анализа
Это почти наверняка самое простое решение, и это то, что я обычно рекомендую. Если вы измените определение Iter_expr на:
Iter_expr : id '(' id '/' Expr ')'
| id '(' Args ':' id '/' Expr ')'
, тогда он все равно будет распознавать каждый действительный ввод (поскольку id и id , id являются действительными экземплярами Args). Это устраняет конфликт сдвиг-уменьшение; по сути, он позволяет анализатору избегать принятия решения, пока он не встретит ) (что будет означать Call_expr) или : (что означает Iter_expr) , (С первой альтернативой для Iter_expr проблем нет, поскольку решение о смещении / вместо уменьшения id не требует дополнительного просмотра.)
Конечно, вторая продукция для Iter_expr распознает множество вещей, которые не являются допустимыми итерационными выражениями: списки из более чем 2 элементов и списки, которые включают выражения, более сложные, чем просто один id. Однако эти входные данные вообще не являются действительными программами, поэтому их можно просто отклонить в действии для Iter_expr. Точный код для распознавания действительной итерации будет зависеть от того, как вы представляете свой AST, но это не сложно: просто убедитесь, что длина Args равна одному или двум, и что каждый элемент в списке является просто id.
3. Используйте лексический хак
Один из способов восполнить недостаток информации о предварительном просмотре - это собрать ее в лексере, собрав необходимые данные в буфере и выводя лексемы только тогда, когда известна их синтаксическая категория. В этом случае лексер может найти последовательность '(' id ',' id ':' и отметить первую id, чтобы ее можно было использовать только в Iter_expr. В этом случае единственное изменение в грамматике:
Iter_expr : id '(' id '/' Expr ')'
| id '(' id ':' id '/' Expr ')'
| id '(' iter_id ',' id ':' id '/' Expr ')'
Хотя в данном конкретном случае это будет хорошо работать, оно не очень легко обслуживаемо. В частности, он основан на возможности определить простой и однозначный шаблон, который может быть реализован в лексере. Поскольку этот шаблон является упрощением грамматики, вполне возможно, что какое-то будущее синтаксическое добавление создаст синтаксис, который также будет соответствовать тому же шаблону. (Это называется лексическим «взломом» по причине.)
4. Найдите LALR (1) грамматику
Как указано, эта грамматика LALR(3). Но не существует такой вещи, как LALR(3) язык . Точнее, если язык имеет грамматику LALR(k), то он также имеет грамматику LALR(1), и эта грамматика может быть создана механически из грамматики LALR(k). Более того, при анализе разборочной грамматики из одного символа можно восстановить дерево разбора для исходной грамматики.
Поскольку грамматики механического производства довольно большие, эта процедура не очень привлекательна, и я не знаю о реализации алгоритма. Вместо этого чаще всего пытаются переписать только часть грамматики, как вы пытались в первоначальном вопросе. Конечно, это можно сделать, но конечный результат не совсем интуитивен.
Однако это не так сложно. Вот, например, немного упрощенная версия вашей грамматики с удаленными избыточными производственными единицами и парой исправлений в приоритете операторов (возможно, некорректных, поскольку я не знаю, на какую семантику вы нацеливаетесь).
Продукция, названия которой заканчиваются на N, не производит ID. Для каждого из них есть соответствующая продукция без N, которая добавляет ID. После этого необходимо было переписать Args для использования продукции ExprN, а также разрешить различные списки аргументов, начинающиеся с одного или двух ID s. Производство Chain было сделано только для того, чтобы избежать повторения.
Start : Call
| Iter
Expr : ID
| ExprN
ExprN : UnaryN
| Expr '+' Unary
Unary : ID
| UnaryN
UnaryN : ChainN
| '^' Chain
Chain : ID
| ChainN
ChainN : PrimaryN
| Chain '>' CallIter
PrimaryN: LITERAL
| Call
| Iter
| '(' Expr ')'
Call : ID '(' ')'
| ID '(' ID ')'
| ID '(' ID ',' ID ')'
| ID '(' Args ')'
Iter : ID '(' ID '/' Expr ')'
| ID '(' ID ':' ID '/' Expr ')'
| ID '(' ID ',' ID ':' ID '/' Expr ')'
Args : ExprN ExprList
| ID ',' ExprN ExprList
| ID ',' ID ',' Expr ExprList
ExprList:
| ExprList ',' Expr
Я не проверял это так сильно, как хотел бы, но я думаю, что он дает правильный язык.