Parsing shift-reduce conflict

Question

J'utilise l'outil JavaCUP pour produire un analyseur pour ma langue. J'essaie d'écrire une grammaire qui correspond à des instructions if_else imbriquées et multiples.

fichier d'entrée

// matches 
if() 
    if() 

    else 

    if() 

    else 
else 

// no match -> modifying grammar leads to shift/reduce conflict 
if() 

else 

Grammaire

expr ::= if_then_else_statement; 

if_then_else_statement ::= IF LPAREN RPAREN if_then_else_statement ELSE if_then_else_statement 
         | ; 

Cette grammaire correspond à des déclarations if_else imbriquées. Cependant, il ne reconnaît que la première instruction if_else imbriquée de mon fichier d'entrée.

J'ai modifié ma grammaire afin de faire correspondre plusieurs déclarations comme ceci:

expr ::= expr if_then_else_statement; 
     | ; 

if_then_else_statement ::= IF LPAREN RPAREN if_then_else_statement ELSE if_then_else_statement 
         | ; 

Le résultat a été un changement/réduire les conflits causés par la règle vide (je suppose). Comment puis-je le modifier pour prendre en charge les instructions imbriquées et multiples if_else sans utiliser la priorité?

Answer 1

La solution habituelle serait quelque chose comme ceci:

expr_list ::= | expr_list expr ; 
expr ::= if_then_else_statement ; 
if_then_else_statement ::= IF LPAREN RPAREN expr ELSE expr ; 

Cela ne permet pas vide else clauses (ou then clauses vides), car une clause else vide est ambigu: il n'y a aucun moyen de savoir si le s2 dans if() s1 else s2 est la clause else ou une instruction qui suit une instruction if complète avec une clause else vide.

Pour résoudre cette ambiguïté, vous avez besoin terminateurs de déclaration (par exemple.) Ou points-virgules if terminateurs déclaration (fi et end sont des choix communs) ou autre chose.