解決在yacc/ocamlyacc中減少/減少衝突

我想解析一個在ocamlyacc中的語法（幾乎與常規的yacc相同），它支持沒有運算符的函數應用程序（如Ocaml或Haskell）以及正常的分類二元和一元運算符。我得到了與' - '運算符的減少/減少衝突，可用於減法和否定。下面是語法的樣品我使用：解決在yacc/ocamlyacc中減少/減少衝突

%token <int> INT 
%token <string> ID 
%token MINUS 

%start expr 
%type <expr> expr 

%nonassoc INT ID 
%left MINUS 
%left APPLY 

%% 

expr: INT 
    { ExprInt $1 } 
| ID 
    { ExprId $1 } 
| expr MINUS expr 
    { ExprSub($1, $3) } 
| MINUS expr 
    { ExprNeg $2 } 
| expr expr %prec APPLY 
    { ExprApply($1, $2) };

的問題是，當你得到這樣的表達式「A - B」的分析器不知道這是否應該降低爲「（ - b）「（否定b，後面是申請）或」a - b「（減法）。減法減少是正確的。我如何解決衝突，支持該規則？

來源

2008-08-23 Jay Conrod

不幸的是，我能想出的唯一答案意味着增加語法的複雜性。

分裂expr成simple_expr和expr_with_prefix
只允許在simple_expr或(expr_with_prefix)適用

的第一步將您減少/減少衝突到移位/減少衝突，但括號解決。

你會遇到與'a b c'相同的問題：是a(b(c))還是(a(b))(c)？您還需要在文法中斷開applied_expression並需要(applied_expression)。

我想這會做到這一點，但我不知道：

expr := INT 
     | parenthesized_expr 
     | expr MINUS expr 

parenthesized_expr := (expr) 
        | (applied_expr) 
        | (expr_with_prefix) 

applied_expr := expr expr 

expr_with_prefix := MINUS expr

來源

2008-08-23 20:49:00

`％left APPLY` /`％prec APPLY`解決了`a b c` - 它的左聯合（所以它的（a b）c）和較低優先級的含糊性。問題在於，優先規則不適用於表現爲減少/減少衝突的歧義。 – 2011-10-06 17:59:03

好吧，這簡單的答案是，只是忽略它，讓默認的減少/降低分辨率處理它 - 減少規則這在語法中首先出現。在這種情況下，這意味着減少expr MINUS expr而不是MINUS expr，這正是你想要的。在看到a-b之後，您想要將其解析爲二進制減號，而不是一元減號，然後應用。

來源

2011-10-06 18:06:54

解決在yacc/ocamlyacc中減少/減少衝突

回答

相關問題