解析，以便能夠解析ML/F＃風格的函數調用使用YACC

Question

我試圖解析表達式序列無定界符表達式序列：

myfunc expr1 expr2 expr3 

然而，表達式的順序給我列出了轉移/減少衝突的列表。

我的猜測是衝突是由我的語法的遞歸性質引起的，但我不知道如何解決這些衝突。

我（簡化）的優先級規則和語法如下：

/* Lowest precedence */ 
%left PLUS 
%left TIMES 
%left LPAR 
/* Highest precedence */ 

Expr: 
    | CSTINT        { CstI $1     } 
    | LPAR Expr RPAR      { $2      } 
    | Expr TIMES Expr      { Prim("*", $1, $3)   } 
    | Expr PLUS Expr      { Prim("+", $1, $3)   } 
    | NAME ExprList       { Call(Var $1, $2)   } 

ExprList: 
    |          { []      } 
    | Expr ExprList      { $1::$2     } 

當我通過這fsyacc我得到轉變的列表/減少，減少/減少衝突。一個例子移進/歸約衝突

state 11: shift/reduce error on PLUS 

從fsyacc的輸出狀態11：

state 11: 
    items: 
    Expr -> Expr . 'TIMES' Expr 
    Expr -> Expr . 'PLUS' Expr 
    ExprList -> Expr . ExprList 

    actions: 
    action 'EOF' (noprec): reduce ExprList --> 
    action 'LPAR' (explicit left 10000): shift 6 
    action 'RPAR' (noprec): reduce ExprList --> 
    action 'COMMA' (noprec): reduce ExprList --> 
    action 'PLUS' (explicit left 9998): shift 13 
    action 'TIMES' (explicit left 9999): shift 12 
    action 'NAME' (noprec): shift 14 
    action 'CSTINT' (noprec): shift 5 
    action 'error' (noprec): reduce ExprList --> 
    action '#' (noprec): reduce ExprList --> 
    action '$$' (noprec): reduce ExprList --> 

    immediate action: <none> 
gotos: 
    goto Expr: 11 
    goto ExprList: 16 

它已經有一段時間我參加了編譯原理的課程，所以雖然我種知道什麼轉換/減少和減少/減少衝突，我不習慣考慮它們。特別是，我不明白如何減少​​可能導致有效的解析。總而言之，對以下一個或多個問題的深入瞭解將被高度讚賞：

1. 爲什麼我的語法看起來模糊不清？
2. 我可以使用優先級和/或關聯性規則修復它嗎？如果沒有，我可以使用優先級和/或關聯性規則修復它嗎？如果不是，我需要重寫語法嗎？如果是這樣，粗略地說，我該怎麼做？
3. yacc是一個適合這樣的結構的工具嗎？

Answer 1

1.爲什麼我的語法看起來模糊不清？

您的語法是含糊不清。這不是幻覺。

假設f是一個函數。

f x + 7 

那是f(x) + 7或f(x+7)？你的語法產生了兩個。

IIRC，功能應用程序綁定非常緊密，並關聯到左側。所以上面的表達式應該解析爲f(x) + 7。

2.我可以修復它使用的優先級和/或關聯規則，如果沒有，

您可以用歧義優先級和關聯規則的功能應用;你只需要用%prec來聲明它的優先級。然而，它看起來有點難看...

3.我是否需要重寫語法，如果是，粗略地說，我該怎麼做？

......我不認爲將功能應用程序表示爲Name ExprList是正確的。如果你一次一個地討論一個參數，至少在建立AST的時候會更清晰一些，如果你在語法中做這件事，而不是優先規則，它看起來更漂亮，而這些規則並不是爲隱形操作員設計的。見下文。

4. yacc是一個合適的工具嗎？

當然，爲什麼不呢？

這裏有兩個工作（據我所知）yacc語法。第一個使用優先聲明來處理所有事情;第二分離出來的功能應用，我認爲這是清潔：

// grammar1.y: 

%left '+' 
%left '*' 
%left ATOM ';' '(' ')' 

%% 

program: /* empty */   { $$ = ""; } 
     | program statement ';' { std::cout << $2 << std::endl; } 
     | program ';' 
     ; 

statement: expr 
     ; 

expr: ATOM 
    | '(' expr ')'    { $$ = $2; } 
    | expr expr %prec ATOM  { $$ = '(' + $1 + ' ' + $2 + ')'; } 
    | expr '+' expr   { $$ = "(+ " + $1 + ' ' + $3 + ')'; } 
    | expr '*' expr   { $$ = "(* " + $1 + ' ' + $3 + ')'; } 
    ; 

---

// grammar2.y 

%token ATOM 

%left '+' 
%left '*' 

%% 

program: /* empty */   { $$ = ""; } 
     | program statement ';' { std::cout << $2 << std::endl; } 
     | program ';' 
     ; 

statement: expr 
     ; 

term : ATOM 
    | '(' expr ')'    { $$ = $2; } 
    ; 

apply: term 
    | apply term    { $$ = '(' + $1 + ' ' + $2 + ')'; } 
    ; 

expr : apply 
    | expr '+' expr   { $$ = "(+ " + $1 + ' ' + $3 + ')'; } 
    | expr '*' expr   { $$ = "(* " + $1 + ' ' + $3 + ')'; } 
    ;