Résoudre des conflits d'analyse dans une minuscule grammaire Lemon

Question

J'essaie d'apprendre les bases de la Lemon parser generator, mais j'ai bloqué rapidement.

Voici une petite grammaire:

%right PLUS_PLUS. 
%left DOT. 

program ::= expr. 

member_expr ::= expr DOT IDENTIFIER. 

lhs_expr ::= member_expr. 

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

Il provoque 1 conflit analyse syntaxique:

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 

considérant que, si je réécris la dernière règle comme suit:

expr ::= PLUS_PLUS expr DOT IDENTIFIER. 

Ensuite, il provoque pas de conflits. Mais je ne pense pas que ce soit la bonne voie à suivre.

Je serais reconnaissant si quelqu'un pouvait expliquer ce qui est la bonne façon, et pourquoi.

Answer 1

Alors vous avez écrit une grammaire ambiguë, qui dit accepter:

++ x . y 

avec deux interprétations:

[++ x ] . y 

et

++ [x . y] 

où le [] sont juste ma façon montrer aux groupements. Lemon est un analyseur L (AL) R, et de tels analyseurs ne gèrent tout simplement pas les ambiguïtés (interprétations multiples). Le conflit réduire-réduire rapporté est ce qui se passe lorsque l'analyseur frappe ce point du milieu; Est-ce que le groupe "++ x" est "[++ x]"? ou comme "++ [x.]"? Les deux choix sont valides, et il ne peut pas choisir en toute sécurité.

Si vous restez avec Lemon (ou un autre générateur d'analyseur LALR), vous devez vous débarrasser du problème en changeant la grammaire. [Vous pouvez utiliser un générateur d'analyseur GLR; il accepterait et vous donnerait les deux analyses. Mais tout ce que vous avez fait est de pousser le problème de la résolution de l'ambiguïté vers l'expression post-analyse. Comme vous ne voulez pas d'ambiguïté, vous pourriez aussi bien l'éviter pendant l'analyse si vous le pouvez. Dans ce cas je pense que vous pouvez.]

Je pense que vous essayez de construire un langage de type C. Donc, vous voulez quelque chose comme ceci:

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 ;