Оптимизация грамматики бизонов

Question

У меня есть эта грамматика языка, похожего на C #, и я хочу создать для него синтаксический анализатор, но когда я добавляю грамматику, она говорит мне о конфликтах сдвига / уменьшения. Я пытался исправить некоторые, но я не могу найти другой способ улучшить эту грамматику. Любая помощь будет принята с благодарностью: 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 сдвиг / уменьшение конфликтов. Одним из них является висячий оператор if / else. Установка "OptElse" НЕ решает эту проблему. Вам просто нужно записать IfStmt и IfElseStmt, а затем использовать опции% nonassoc и% prec в зубре, чтобы исправить это.

Ваши выражения - это проблема почти всех остальных 240 конфликтов. Вам нужно либо форсировать правила приоритетов (грязная и ужасная идея), либо разбить ваши арифметические выражения на такие вещи, как:

AddSubtractExpr: AddSubtractExpr PLUS MultDivExpr | ....
               ;


MultDivExpr: MultiDivExpr TIMES Factor | ....
           ;


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

Поскольку Bison создает анализатор снизу вверх, что-то вроде этого даст вам правильный порядок операций. Если у вас есть копия первого издания Книги Дракона, вы должны взглянуть на грамматику в Приложении А. Я считаю, что во 2-м издании также есть похожие правила для простых выражений.

Answer 2

конфликтов (сдвиг / уменьшение или уменьшение / уменьшение) означают, что ваша грамматика не является LALR (1), поэтому не может быть обработана бизоном напрямую без посторонней помощи.Существует ряд сразу очевидных проблем:

• неоднозначность выражений - в грамматике нет приоритета, поэтому такие вещи, как a + b * c, неоднозначны.Это можно исправить, добавив правила приоритета или разделив правило Expr на отдельные правила AdditiveExpr, MultiplicativeExpr, ConditionalExpr и т. Д.

• висящая неопределенность - if (a) if (b) x; else y; -иначе может быть сопоставлено с любым, если.Вы можете либо проигнорировать это, если сдвиг по умолчанию правильный (это обычно для этого конкретного случая, но игнорирование ошибок всегда опасно), либо разделить Stmt правило

Есть много книгна грамматике и разборе, которые помогут с этим.