解決LALR解析器中的移位/減少衝突

Question

我一直在使用PLY爲我的語言構建解析器，但是我遇到了移位/減少衝突，這給我造成了一些麻煩。我的語言具有語法ala C++模板的泛型類型。所以現在我有這樣的規則：

expression : expression LESS expression %prec COMPARISON 
    expression : template 
    template : NAME 
      | NAME LESS templates GREATER 
    templates : template 
       | templates COMMA template 

然而，我發現，這是無法解析：

a < 2 

（這是顯而易見的原因有問題）。以下是調試輸出：

PLY: PARSE DEBUG START 

State : 0 
Stack : . <Token: 'NAME' 'a'> 
Action : Shift and goto state 42 

State : 42 
Stack : NAME . <Token: 'LESS' '<'> 
Action : Shift and goto state 81 

State : 81 
Stack : NAME LESS . <Token: 'NUMBER' '2'> 
ERROR: Error : NAME LESS . <Token: 'NUMBER' '2'> 

如果我需要更多的解析器，我可以提供它。謝謝。

編輯：向我提出的一種解決方案是讓類型自己的令牌。這需要一點工作，因爲我的語言不使用像C/C++這樣的預處理器包含系統，但是我認爲它仍然是可能的，但是我更喜歡一個限於語法的解決方案。

Answer 1

Yacc解析器不是特別強大，嘗試上下文無關的解析可能會要求太多。我建議使用某種技巧來使yacc像分析上下文敏感語法一樣行事，或者，不要嘗試使用解析器來強制執行每條語法規則。

• 添加上下文
  當你解析類型識別，設置一個標誌或調用一個方法來此傳送給掃描儀，然後在這種情況下返回不同的終端符號<和>。
• 簡化語法
  或者，繼續，只對模板生成的一部分使用統一的表達式/模板語法，並在代碼中錯誤地輸出除模板語法之外的任何內容。解析器是系統中能力最低的部分，因此儘可能將工作推送到代碼中。 （對代碼沒有限制，對yacc有很多限制。）

我並不是說這些是你唯一的選擇。如果你花費了幾天時間，對國家表格感到困惑，並將語法調整到yacc滿意的地步，我想你會「成功」，但這不值得。那時你可能剛寫了一個遞歸下降解析器。 （RD是更多的代碼行，並且你不會看到在BNFish yacc中整齊排列的語法，但至少你可以解析任何東西，並且你永遠不會陷入「不工作」的謎題。）

Python與Ruby的Treetop有什麼相同之處嗎？這將解決問題。野牛的%glr-parser功能也可以「解決」這樣的問題，儘管採用BFI方式。