Решение разбор конфликтов в крошечной грамматике Лимона

Question

Я пытаюсь изучить основы генератора парсеров Lemon, но я застрял быстро.

Вот крошечная грамматика:

%right PLUS_PLUS.
%left DOT.

program ::= expr.

member_expr ::= expr DOT IDENTIFIER.

lhs_expr ::= member_expr.

expr ::= lhs_expr.
expr ::= PLUS_PLUS lhs_expr.

Это вызывает 1 конфликт синтаксического анализа:

State 3:
      (3) expr ::= lhs_expr *
      (4) expr ::= PLUS_PLUS lhs_expr *

                           DOT reduce       3      expr ::= lhs_expr
                           DOT reduce       4       ** Parsing conflict **
                     {default} reduce       4      expr ::= PLUS_PLUS lhs_expr

Принимая во внимание, что если я перепишу последнее правило следующим образом:

expr ::= PLUS_PLUS expr DOT IDENTIFIER.

Тогда это не вызывает конфликтов. Но я не думаю, что это правильный путь.

Буду признателен, если кто-нибудь сможет объяснить, что правильно и почему.

Answer 1

Итак, вы написали двусмысленную грамматику, в которой говорится принять:

 ++ x . y

с двумя интерпретациями:

 [++ x ] . y

а также

 ++ [x . y]

где [ ] это просто мой способ показать группировкам.

Lemon является парсером L(AL)R, и такие парсеры просто не обрабатывают неоднозначности (множественные интерпретации). Сообщается о конфликте уменьшения-уменьшения, который происходит, когда синтаксический анализатор достигает этой средней точки; делает ли он группу "++ x" как "[++ x]". или как "++ [ x .]"? Оба варианта действительны, и он не может быть безопасным.

Если вы придерживаетесь Lemon (или другого генератора синтаксического анализатора LALR), вы должны избавиться от проблемы, изменив грамматику. [Вы можете использовать генератор парсера GLR; он примет и даст вам оба разбора. Но все, что вы тогда сделали, это подтолкнули проблему устранения неоднозначности к фразе после разбора. Поскольку вы не хотите двусмысленности, вы можете избежать ее во время анализа, если можете. В этом случае я думаю, что вы можете.]

Я думаю, что вы пытаетесь создать C-подобный язык. Итак, вы хотите что-то вроде этого:

primitive_target ::= IDENTIFIER ;
primitive_target ::= IDENTIFIER '[' expr ']' ;
access_path ::= primitive_target ;
access_path ::= access_path '.' primitive_target ;

lhs ::= access_path ;
lhs ::= PLUS_PLUS access_path ;
lhs ::= access_path PLUS_PLUS ;

program ::= expr ;

expr ::= term ;
expr ::= expr '+' term ;
term :::= '(' expr ')' ;
term ::= lhs ;
term ::= lhs '=' expr ;
term ::= constant ;