优化Bison语法

Question

我有一种类似C#的语言的语法，我想为它做一个解析器，但当我放入语法时，它会告诉我关于Shift/Reduce冲突。我试着修正了一些，但我似乎找不到其他方法来改进这个语法。任何帮助都将不胜感激:D以下是语法：

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

我学校服务器上的旧Bison版本显示有241个shift/reduce冲突。一个是悬而未决的if/else语句。输入"OptElse“并不能解决这个问题。您只需写出IfStmt和IfElseStmt，然后在bison中使用%nonassoc和%prec选项来修复它。

你的表情是几乎所有其他240个冲突的问题。你需要做的要么是强制优先规则(混乱和可怕的想法)，要么是把你的算术表达式分解成像这样的东西：

AddSubtractExpr: AddSubtractExpr PLUS MultDivExpr | ....
               ;


MultDivExpr: MultiDivExpr TIMES Factor | ....
           ;


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

由于Bison生成了一个自下而上的解析器，类似这样的代码将为您提供正确的操作顺序。如果你有第一版的龙书，你应该看看附录A中的语法。我相信第二版也有类似的简单表达规则。

Answer 2

冲突(shift/reduce或reduce/reduce)意味着您的语法不是LALR(1)，因此如果没有帮助，bison无法直接处理。有许多显而易见的问题：

• 表达式多义性--语法中没有优先级，所以像a + b * c这样的东西是多义性的。您可以通过添加优先级规则或通过将歧义规则拆分为单独的AdditiveExpr、MultiplicativeExpr、ConditionalExpr等来解决此问题，否则歧义-- if (a) if (b) x; else y; -- else可以与任一if匹配。如果默认移位是正确的，则可以忽略此操作(通常适用于此特定情况，但忽略错误始终是危险的)，或者拆分Stmt规则

有很多关于语法和解析的书籍可以帮助你做到这一点。