Comment résoudre shift réduire les conflits dans ma grammaire?

J'écris un compilateur de Pascal (réduit) en ARM asm. Je suis à la deuxième étape du processus - après avoir écrit l'analyseur lexical maintenant je travaille sur l'analyse syntaxique avec java cup.Comment résoudre shift réduire les conflits dans ma grammaire?

J'ai écrit ma grammaire, mais j'ai eu 5 conflits S/R, qui sont tous très similaires. Exemple:

Warning : *** Shift/Reduce conflict found in state #150 
between assign_stmt ::= val_expr ASSIGN val_expr (*) 
    and  val_expr ::= val_expr (*) LBRACKET val_expr RBRACKET 
    under symbol LBRACKET 
    Resolved in favor of shifting

Ma grammaire pour cette section:

assign_stmt ::= 
val_expr ASSIGN val_expr; 

val_expr ::= 
    NIL | BOOL_CONST | INT_CONST | CHAR_CONST | PTR val_expr %prec MEM | ADD val_expr %prec UADD | 
    SUB val_expr %prec USUB | NOT val_expr | val_expr PTR %prec VAL | val_expr MUL val_expr | 
    val_expr DIV val_expr | val_expr ADD val_expr | val_expr SUB val_expr | val_expr EQU val_expr | 
    val_expr NEQ val_expr | val_expr LTH val_expr | val_expr GTH val_expr | val_expr LEQ val_expr | 
    val_expr GEQ val_expr | val_expr AND val_expr | val_expr OR val_expr | IDENTIFIER | 
    val_expr LBRACKET val_expr RBRACKET | val_expr DOT IDENTIFIER | IDENTIFIER LPARENTHESIS params_list RPARENTHESIS | 
    LBRACKET type_desc RBRACKET | LPARENTHESIS val_expr RPARENTHESIS 
    ;

Comment pourrais-je éliminer ce conflit?

Merci.

Source

2010-10-16 Uros K

Vous devriez probablement étiqueter cette question avec le générateur d'analyseur que vous utilisez - ou au moins le mentionner quelque part dans la question. – sepp2k

J'ai mentionné java cup, mais je ne peux pas ajouter le tag, car vous avez besoin de 1,5k réputation pour ajouter de nouveaux tags. –

Votre grammaire est ambiguë, et récursive à droite et à gauche. De mes connaissances (limitées) sur les parseurs, je sais que c'est impossible à analyser par la plupart des générateurs d'analyseurs.

Il est ambigu, car val_expr ADD val_expr SUB val_expr peut être analysé comme:

 ADD 
    / \ 
val_expr SUB 
     / \ 
    val_expr val_expr

 SUB 
    / \ 
    ADD val_expr 
    / \ 
val_expr val_expr

Je ne l'ai jamais utilisé Java CUP, mais voici comment je l'ai fait une chose similaire en utilisant un autre générateur d'analyseur:

val_expr ::= 
    expr1 (SUB | ADD | <add all your operators here>) val_expr 
    | expr1 ; 

expr1 ::= 
    NIL | BOOL_CONST | INT_CONST | CHAR_CONST | <etc> ;

Ceci rend la grammaire non ambiguë et seulement récursive à droite, ce qui peut être manipulé par tous les générateurs de parser que je connais.

Un aspect négatif de cette grammaire est que vous n'avez aucune priorité, mais Java CUP a probablement un autre moyen de spécifier la priorité.

Modifier: Correction de la première règle de grammaire.

Source

2010-10-16 15:10:16 imgx64

En fait, j'avais d'autres problèmes avec ma grammaire et comme je les ai résolus, tous les conflits "auto-magiquement" ont disparu. Cependant, j'ai aussi changé (et rendu plus joli) ma grammaire en fonction de votre message. Merci, j'ai appris quelque chose de nouveau! –

Comment résoudre shift réduire les conflits dans ma grammaire?

Répondre

Questions connexes