優化野牛語法

我有這樣一種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 
     ;

來源

2010-10-11 Osukaa

你能提供錯誤信息嗎？ – 2010-10-11 17:00:49

除了轉換減少錯誤之外，您正在使用右遞歸規則，例如非常低效的Expr：Expr PLUS Expr。有關詳細信息，請參閱Bison手冊，http://dinosaur.compilertools.net/bison/bison_6.html#SEC42 – 2010-10-11 17:24:34

我學校服務器上的舊版Bison版本說你有241個轉換/減少衝突。一個是懸掛if/else語句。把「OptElse」不解決它。你應該只寫出IfStmt和一個IfElseStmt，然後在野牛中使用％nonassoc和％prec選項來修復它。

你的表情是幾乎所有其他240個衝突的問題。你需要做的是無論是力優先規則（凌亂和一個可怕的想法），或者打破你的算術表達式到東西，如：

AddSubtractExpr: AddSubtractExpr PLUS MultDivExpr | .... 
       ; 


MultDivExpr: MultiDivExpr TIMES Factor | .... 
      ; 


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

由於野牛產生自下而上的解析器，這樣的事情會給你正確的順序操作。如果你有龍書第一版的副本，你應該看附錄A中的語法。我相信第二版對簡單表達式也有類似的規則。

來源

2010-10-11 17:21:09 Kizaru

衝突（移動/降低或減少/降低）意味着你的語法不是LALR（1），因此不能被野牛的情況下直接幫助處理。有一些顯而易見的問題：

表達歧義 - 有一個在語法沒有優先級，所以像a + b * c是不明確的。您可以通過添加優先規則或將Expr規則拆分爲單獨的AdditiveExpr，MultiplicativeExpr，ConditionalExpr等規則來解決此問題。
dangling else ambiguity - if (a) if (b) x; else y; - else可以與if匹配。您可以忽略這一點，如果默認的轉變是正確的（通常是這種特殊情況下，卻忽略了錯誤永遠是危險的）或拆分Stmt規則

上有語法和分析，這將有助於許多書有了這個。

來源

2010-10-11 17:15:23

優化野牛語法

回答

相關問題