將優先錶轉換爲適合遞歸下降的語法？

Question

如果我們只包含原子元素和一元和二元運算的語言：

atomic elements: a b c 
unary operators: ! ~ + - 
binary operators: + -/* 

然後，我們可以定義一個語法：

ATOM := a | b | c 
UNOP := ! | ~ | + | - 
BINOP := + | - |/| * 
EXPR := ATOM | UNOP EXPR | EXPR BINOP EXPR 

但是這個語法會導致不明確的解析樹（和遞歸下降解析器中的一個無限循環，由於左遞歸）。

所以我們增加一個precendence表：

Precendence 1: unary+ unary- ~ ! (Right to Left) 
Precendence 2: */(Left to Right) 
Precendence 3: binary+ binary- (Left to Right) 

我的問題是，我們什麼算法或程序可以採取的優先順序表，併產生一個適當的文法遞歸下降解析器（不剩遞歸）。

優先表是運算符組和相關方向的有序列表（L-> R或R < -L）。答案將會把這個作爲輸入併產生語法作爲輸出。

Answer 1

將運算符優先級語法轉換爲LR(1)語法[1]很容易，但得到的語法將使用左遞歸來解析左關聯運算符。消除左遞歸很容易 - 例如，使所有操作符都是正確的關聯 - 但是當生成的語法識別相同的語言時，解析樹是不同的。

事實證明，稍微修改遞歸下降解析器以處理優先關係並不難。該技術由Vaughan Pratt發明，基本上使用調用堆棧來替代傳統shunting-yard algorithm中的顯式堆棧。

Pratt解析似乎正在經歷某種復興，你可以找到很多關於它的博客文章;一個合理的好的是Eli Bendersky。 Pratt在20世紀70年代初期設計了該程序，與此同時，Frank deRemer證明LR(1)解析是實用的。普拉特對正式解析的實用性和不靈活性持懷疑態度。我認爲自那以後，這場辯論一直在醞釀。普拉特語法分析器確實簡單而靈活，但另一方面可能很難證明它們是正確的（或者它們解析了特定的形式化語法）。另一方面，儘管bison最近獲得了對GLR解析的支持，使得它可能使用起來更加困難，並且儘管生成的解析器實際上解析了他們聲稱解析的語法，但仍有許多人會同意普拉特的聲明（從1973年起），正式的解析方法「不易使用，使用起來不太舒服」。

---

[1]在實踐中，所有YACC衍生物和許多其他LR解析器生成器將接受消歧優先關係;由此產生的語法表更小，涉及的單位減少量更少，因此如果您要使用解析器生成器，則沒有特別好的理由不使用此技術。

Answer 2

描述任意優先級的通用語法可以使用基於表的LALR解析器來解析，並且可以使用yacc生成。但是，這並不意味着當你想使用遞歸下降解析器時，全部都會丟失。

遞歸下降解析器只能驗證語法是否正確。構建語法樹是另一回事，應該在樹型構建級別上處理優先級。

因此，請考慮以下可解析中綴表達式的無左遞歸語法。沒什麼特別的優先無跡象：

Expr := Term (InfixOp Term)* 
InfixOp := '+' | '-' | '*' | '/' 
Term := '(' Expr ')' 
Term := identifier 

（右側使用的符號是正則表達式等，它們在使用大駝峯書面替換規則，令牌引用或使用小駱駝的情況下寫的）。

在構建語法樹時，您有一個當前節點，您將其添加到新節點中。

大多數情況下，當您解析規則時，您會在當前節點上創建一個新的子節點，並使該子節點成爲當前節點。完成解析後，您可以繼續學習父節點。

現在這是解析InfixOp規則時應該做的不同。您應該爲相關節點分配優先權。 Expr節點的優先級最低，而其他運營商的節點優先級最高。

處理綴優先

當解析InfixOp規則執行以下操作：

1. 雖然比輸入節點的優先級當前節點的優先做強，持續上漲一個級別（使父節點當前）。

2. 然後插入傳入節點作爲當前節點的最後一個子節點的父節點，並使其成爲當前節點。

由於Expr節點聲明具有最弱的優先級，它最終會停止攀登。

讓我們看一個例子：A+B*C

有當前節點總是打上!消耗電流令牌之後。

Parsed: none 

Expr! 

Parsed: A 

Expr! 
| 
A 

Parsed: A+ 

Expr 
| 
+! 
| 
A 

Parsed: A+B 

    Expr 
    | 
    +! 
/\ 
A B 

Parsed: A+B* 

    Expr 
    | 
    + 
/\ 
A *! 
/
    B 

Parsed: A+B*C 

    Expr 
    | 
    + 
/\ 
A *! 
/\ 
    B C 

如果你穿越這在後序的方式，你會得到逆波蘭式的，可用於評估它的表達。

或相反的例子：A*B+C

Parsed: none 

Expr! 

Parsed: A 

Expr! 
| 
A 

Parsed: A* 

Expr 
| 
*! 
| 
A 

Parsed: A*B 

    Expr 
    | 
    *! 
/\ 
A B 

Parsed: A*B+ 

    Expr 
    | 
    +! 
    | 
    * 
/\ 
A B 

Parsed: A*B+C 

    Expr 
    | 
    +! 
/\ 
    * C 
/\ 
A B 

處理關聯

有一些是左關聯的，而其他人是右關聯的運營商。例如在C語言系列中，+是左關聯的，而=是右關聯的。

其實整個結合性事情歸結爲在相同的優先級上對操作符的處理。對於左側關聯運算符，當您遇到相同優先級的運算符時，攀登會繼續向上。對於正確的關聯運算符，當遇到相同的運算符時停止。

（它需要太多的空間來展示所有的技術，我建議您嘗試出來的一張紙。）

處理前綴和後綴運算符

在這種情況下，你需要修改語法一位：

Expr := PrefixOp* Term PostfixOp* (InfixOp PrefixOp* Term PostfixOp*)* 
InfixOp := '+' | '-' | '*' | '/' 
Term := '(' Expr ')' 
Term := identifier 

當你遇到一個前綴操作，只需將其添加爲新的子當前節點，使新的子電流，無論優先，這將是正確的，即使它是一個強大的運營商或弱者優先c中綴操作員的限制規則確保了正確性。

對於後綴運算符，您可以使用與我在中綴運算符中描述的相同的優先級爬行，唯一的區別是我們沒有後綴運算符的右側，所以它只有1個子項。

處理三元運營商

C語言家族擁有?:三元運算符。關於語法樹構建，您可以將?和:作爲單獨的中綴運算符來處理。但有一個竅門。您爲?創建的節點應該是一個不完整的三元節點，這意味着你做平常優先登山和地方，但是，這個不完整的節點將具有優先級最低，這樣可以防止像逗號操作爬過它甚至較弱的運營商。當你到達:時，你必須爬到第一個不完整的三元節點（如果你沒有找到一個，然後報告語法錯誤），然後把它改成一個完整的節點，它將具有正常的優先級，並使其成爲當前節點。如果在當前分支上存在不完整的三元節點時意外地到達表達式的結尾，則會再次報告語法錯誤。

所以a , b ? c : d被解釋爲a , (b ? c : d)。

但是a ? c , d : e將被解釋爲a ? (c , d) : e，因爲我們阻止了逗號的上升。

處理數組下標和函數調用

儘管後綴外觀它們綴運營右側語法執行括號內的術語，這是數組索引真實，函數調用也是如此。