shift/reduce conflicts yacc

Question

voir le code suivant pour yacc. si j'enlève le facteur de production: '!' expr, le conflit d'analyse disparaît. que se passe-t-il ici?

%{ 
#include <stdio.h> 
#include <ctype.h> 

%} 


%token TRUE 
%token FALSE 


%% 
line : line expr '\n' { printf("%d\n", $2); } 
    | line '\n' 
| 
; 
expr : expr "or" term { printf("expr : expr or term\n"); $$ = $1 | $3; } 
| term  { printf("expr : term\n");  } 
; 
term : term "and" factor { printf("term : term and factor\n"); $$ = $1 & $3; } 
| factor  { printf("term : factor\n"); } 
; 
factor : '(' expr ')' { printf("factor : (expr)\n"); $$ = $2; } 
| '!' expr { printf("factor : !expr\n"); $$ = !$2; } 
| TRUE  { printf("factor : TRUE\n"); } 
| FALSE  { printf("factor : FALSE\n"); } 
; 
%% 

#include "lex.yy.c" 

int main(int argc, char** argv) 
{ 
while (yyparse() == 0) { 
    } 

    return 0; 
} 

Answer 1

Il me semble que le conflit se pose probablement parce que lorsque l'analyseur voit un « ! », Il est en cours d'exécution un problème avec votre réécritures pour « expr ». Ignorant les autres productions pour « facteur », examiner spécifiquement ces deux productions: '!

expr : expr "or" term { printf("expr : expr or term\n"); $$ = $1 | $3; } 
     | term   { printf("expr : term\n"); } 
     ; 

factor : '!' expr  { printf("factor : !expr\n"); $$ = !$2; } 

Depuis expr est récursive, lorsque l'analyseur voit un, il sait que la négation applique à la expr suivante, mais si vous écrivez "! TRUE OR TRUE", cette négation s'applique-t-elle seulement à la première vraie, ou à la disjonction entière?

EDIT: En d'autres termes, il ne peut pas décider s'il doit déplacer le "ou" ou réduire "expr".

La définition de l'option de ligne de commande -v dans yacc produira un fichier .output contenant toutes sortes de goodies, y compris des informations de diagnostic pour les conflits de décalage/réduction. Il vous montrera tous les états de la DFA et où les conflits se produisent, et parfois vous montrer exactement pourquoi.

Mettre des négations dans leur propre production logiquement "entre" 'term' et 'factor' devrait faire l'affaire.

Answer 2

Si vous modifiez factor: ! expr à factor: ! factor, les conflits disparaîtront.

En analysant juste le premier conflit, le problème est qu'un term peut réduire à expr ou devenir un term plus complexe. Sans !, cette décision peut être prise avec un seul symbole de lookahead.

Notez que les conflits de décalage/réduction ne sont pas nécessairement des erreurs. Le conflit est résolu en faisant le changement, ce qui pourrait bien être ce que vous voulez. La plupart des vraies grammaires de production contiennent un certain nombre de conflits de décalage/réduction.