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

Question

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

Вот маленькая грамматика:

%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] 

где [] являются только мой путь для отображения групп.

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

Если вы придерживаетесь лимона (или другого генератора парсеров 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 ;