Optimisation de la grammaire Bison

Question

J'ai cette grammaire d'un langage C#, et je veux faire un analyseur pour elle, mais quand je mets la grammaire, elle me parle de Shift/Réduire les conflits. J'ai essayé de résoudre certains problèmes, mais je n'arrive pas à trouver un autre moyen d'améliorer cette grammaire. Toute aide serait grandement appréciée: D Voici la grammaire:

Program: Decl 
     | Program Decl 
     ; 

Decl: VariableDecl 
    | FunctionDecl 
    | ClassDecl 
    | InterfaceDecl 
    ; 

VariableDecl: Variable SEMICOLON 
      ; 

Variable: Type IDENTIFIER 
     ; 

Type: TOKINT 
    | TOKDOUBLE 
    | TOKBOOL 
      | TOKSTRING 
    | IDENTIFIER 
    | Type BRACKETS 
    ; 

FunctionDecl: Type IDENTIFIER OPARENS Formals CPARENS StmtBlock 
      | TOKVOID IDENTIFIER OPARENS Formals CPARENS StmtBlock 
      ; 

Formals: VariablePlus 
     | /* epsilon */ 
     ; 

VariablePlus: Variable 
      | VariablePlus COMMA Variable 
      ; 

ClassDecl: TOKCLASS IDENTIFIER OptExtends OptImplements OBRACE ListaField CBRACE 
     ; 

OptExtends: TOKEXTENDS IDENTIFIER 
      | /* epsilon */ 
      ; 

OptImplements: TOKIMPLEMENTS ListaIdent 
      | /* epsilon */ 
      ; 

ListaIdent: ListaIdent COMMA IDENTIFIER 
      | IDENTIFIER 
      ; 

ListaField: ListaField Field 
      | /* epsilon */ 
      ; 

Field: VariableDecl 
    | FunctionDecl 
    ; 

InterfaceDecl: TOKINTERFACE IDENTIFIER OBRACE ListaProto CBRACE 
      ; 

ListaProto: ListaProto Prototype 
      | /* epsilon */ 
      ; 

Prototype: Type IDENTIFIER OPARENS Formals CPARENS SEMICOLON 
     | TOKVOID IDENTIFIER OPARENS Formals CPARENS SEMICOLON 
     ; 

StmtBlock: OBRACE ListaOptG CBRACE 
     ; 

ListaOptG: /* epsilon */ 
     | VariableDecl ListaOptG 
     | Stmt ListaOptG 
     ; 

Stmt: OptExpr SEMICOLON 
    | IfStmt 
    | WhileStmt 
    | ForStmt 
    | BreakStmt 
    | ReturnStmt 
    | PrintStmt 
    | StmtBlock 
    ; 

OptExpr: Expr 
     | /* epsilon */ 
     ; 

IfStmt: TOKIF OPARENS Expr CPARENS Stmt OptElse 
     ; 

OptElse: TOKELSE Stmt 
     | /* epsilon */ 
     ; 

WhileStmt: TOKWHILE OPARENS Expr CPARENS Stmt 
     ; 

ForStmt: TOKFOR OPARENS OptExpr SEMICOLON Expr SEMICOLON OptExpr CPARENS Stmt 
     ; 

ReturnStmt: TOKRETURN OptExpr SEMICOLON 
      ; 

BreakStmt: TOKBREAK SEMICOLON 
     ; 

PrintStmt: TOKPRINT OPARENS ListaExprPlus CPARENS SEMICOLON 
     ; 

ListaExprPlus: Expr 
      | ListaExprPlus COMMA Expr 
      ; 

Expr: LValue LOCATION Expr 
    | Constant 
    | LValue 
    | TOKTHIS 
    | Call 
    | OPARENS Expr CPARENS 
    | Expr PLUS Expr 
    | Expr MINUS Expr 
    | Expr TIMES Expr 
    | Expr DIVIDED Expr 
    | Expr MODULO Expr 
    | MINUS Expr 
    | Expr LESSTHAN Expr 
    | Expr LESSEQUALTHAN Expr 
    | Expr GREATERTHAN Expr 
    | Expr GREATEREQUALTHAN Expr 
    | Expr EQUALS Expr 
    | Expr NOTEQUALS Expr 
    | Expr AND Expr 
    | Expr OR Expr 
    | NOT Expr 
    | TOKNEW OPARENS IDENTIFIER CPARENS 
    | TOKNEWARRAY OPARENS Expr COMMA Type CPARENS 
    | TOKREADINTEGER OPARENS CPARENS 
    | TOKREADLINE OPARENS CPARENS 
    | TOKMALLOC OPARENS Expr CPARENS 
    ; 

LValue: IDENTIFIER 
     | Expr PERIOD IDENTIFIER 
     | Expr OBRACKET Expr CBRACKET 
     ; 

Call: IDENTIFIER OPARENS Actuals CPARENS 
    | Expr PERIOD IDENTIFIER OPARENS Actuals CPARENS 
    | Expr PERIOD LibCall OPARENS Actuals CPARENS 
    ; 

LibCall: TOKGETBYTE OPARENS Expr CPARENS 
     | TOKSETBYTE OPARENS Expr COMMA Expr CPARENS 
     ; 

Actuals: ListaExprPlus 
     | /* epsilon */ 
     ; 

Constant: INTCONSTANT 
     | DOUBLECONSTANT 
     | BOOLCONSTANT 
     | STRINGCONSTANT 
     | TOKNULL 
     ; 

Answer 1

L'ancienne version de Bison sur le serveur de mon école indique que vous avez 241 conflits de décalage/réduction. L'une est l'instruction if/else qui pend. Mettre "OptElse" ne le résout PAS. Vous devez simplement écrire IfStmt et IfElseStmt, puis utiliser les options% nonassoc et% prec dans bison pour le réparer.

Vos expressions représentent le problème de presque tous les autres conflits. Ce que vous devez faire est soit des règles de priorité de la force (en désordre et une très mauvaise idée) ou briser vos expressions arithmétiques dans des choses comme:

AddSubtractExpr: AddSubtractExpr PLUS MultDivExpr | .... 
       ; 


MultDivExpr: MultiDivExpr TIMES Factor | .... 
      ; 


Factor: Variable | LPAREN Expr RPAREN | call | ... 
     ; 

Depuis Bison produit un bas vers le haut parser, quelque chose comme cela vous donnera ordre de opérations. Si vous avez une copie de la première édition du livre du dragon, vous devriez regarder la grammaire dans l'annexe A. Je crois que la deuxième édition a également des règles similaires pour les expressions simples.

Answer 2

conflits (changement/réduire ou réduire/réduire) signifie que votre grammaire n'est pas LALR (1) ne peut donc pas être manipulés par le bison directement, sans l'aide . Il y a un certain nombre de problèmes immédiatement évidents:

• ambiguïté d'expression - il n'y a pas de précédent dans la grammaire, donc les choses comme a + b * c sont ambigus. Vous pouvez résoudre ce problème en ajoutant des règles de priorité ou en divisant la règle Expr en règles AdditiveExpr, MultiplicativeExpr, ConditionalExpr etc.

• dangling else ambiguité - if (a) if (b) x; else y; - l'autre pourrait correspondre à if. Vous pouvez ignorer ceci si le décalage par défaut est correct (il est généralement pour ce cas précis, mais sans tenir compte des erreurs est toujours dangereuse) ou diviser la Stmt règle

Il y a beaucoup de livres sur grammaires et l'analyse qui aidera avec ça.