簡單語法的野牛移位/減少衝突

Question

我正在爲我設計的語言構建解析器，其中類型名稱以大寫字母開頭，變量名稱以小寫字母開頭，這樣詞法分析器可以告訴差異並提供不同的令牌。此外，字符串'this'被詞法分析器識別（它是一種OOP語言）並作爲單獨的標記傳遞。最後，數據成員只能在「這個」物體上訪問，所以我建立了語法像這樣：

%token TYPENAME 
%token VARNAME 
%token THIS 

%% 

start: 
    Expression 
    ; 

Expression: 
    THIS 
    | THIS '.' VARNAME 
    | Expression '.' TYPENAME 
    ; 
%% 

表達的第一條規則允許用戶通過「這個」圍繞作爲值（例如，從方法返回或傳遞給方法調用）。第二個是訪問「this」的數據。第三個規則是調用方法，但是我刪除了括號和參數，因爲它們與問題無關。最初的語法顯然比這個要大得多，但是這是產生相同錯誤的最小部分（1 Shift/Reduce衝突） - 我將它隔離到它自己的解析器文件中並驗證了這一點，所以錯誤與任何事情沒有任何關係其他符號。

據我所見，這裏給出的語法是明確的，所以不應該產生任何錯誤。如果刪除三條規則中的任何一條或將第二條規則更改爲

Expression '.' VARNAME 

沒有衝突。無論如何，我可能需要有人來闡明這種衝突發生的原因以及如何解決它。

Answer 1

問題是語法只能看一個。因此，當您看到THIS然後.時，您是在第2行（Expression: THIS '.' VARNAME）還是第3行（Expression: Expression '.' TYPENAME，通過根據行1進行縮小）。

語法可以減少THIS.到Expression.然後找一個TYPENAME或將其轉移到THIS.並尋找一個VARNAME，但它必須決定當它到達的.。

Answer 2

我儘量避免y.output，但有時它確實有幫助。我看着它製作並看到的文件。

state 1 

    2 Expression: THIS. [$end, '.'] 
    3   | THIS . '.' VARNAME 

    '.' shift, and go to state 4 

    '.'  [reduce using rule 2 (Expression)] 
    $default reduce using rule 2 (Expression) 

基本上它是說它看到'。'並可以減少或可以轉移。減少使我有時因爲他們很難罰款。這個轉變是規則3，很明顯（但輸出沒有提及規則＃）。減少它看到的'。'在這種情況下是線

| Expression '.' TYPENAME 

當去表達它着眼於下一個字母（的「」），去的。現在看到THIS |所以當它到達該語句的結束，預計''當它離開或出錯時。但它看到這''。'而它介於此​​與'。'之間。 （因此out文件中的點），並且它可以減少規則，所以存在路徑衝突。我相信你可以使用%glr-parser來允許它嘗試兩種方式，但是你有更多的衝突更有可能得到意想不到的輸出或者模糊性錯誤。過去我有模棱兩可的錯誤。他們討厭處理，特別是如果你不記得什麼規則造成或影響他們。建議避免衝突。

在試圖使用野牛之前，我強烈建議使用this book。

我想不出一個「偉大」的解決方案，但是這沒有給出衝突

start: 
    ExpressionLoop 
    ; 

ExpressionLoop: 
     Expression 
    | ExpressionLoop ';' Expression 
    ; 
Expression: 
     rval 
    | rval '.' TYPENAME 
    | THIS //trick is moving this AWAY so it doesnt reduce 
rval: 

    THIS '.' VARNAME 

---

替代你可以把它後來減少到規則添加更何況它不盡快或通過添加降低之後或之前令牌才能把它清楚哪個路徑或失敗（請記住，它必須知道之前減少任何路徑）

start: 
    ExpressionLoop 
    ; 

ExpressionLoop: 
     Expression 
    | ExpressionLoop ';' Expression 
    ; 
Expression: 
     rval 
    | rval '.' TYPENAME 
rval: 
     THIS '@' 
    | THIS '.' VARNAME 
%% 

CNC中注意到，如果我想要做func param和type varname我不能因爲根據詞法分析器func的類型是Var（這是A-Za-z09_）以及類型。 param和varname都是var的，所以這會導致我減少/減少衝突。你不能把它寫成它們的樣子，只能看它們的樣子。所以在寫作時請記住這一點。您必須編寫一個令牌來區分這兩者，或者將其作爲二者之一編寫，但在代碼中編寫額外的邏輯（位於規則右側的部分），以檢查它是否爲funcname或一個類型並處理這兩種情況。