LL和LR解析有什麼區別？

Question

任何人都可以給我一個LL解析與LR解析的簡單例子嗎？

Answer 1

在較高的層次上，LL解析和LR解析的區別在於LL解析器從開始符號開始，嘗試應用作品到達目標字符串，而LR解析器從目標字符串開始嘗試到達回到開始符號。

LL解析是從左到右，最左端的派生。也就是說，我們從左到右考慮輸入符號並嘗試構造最左邊的派生。這是通過從開始符號開始並反覆擴展最左端的非終結符，直到到達目標字符串。 LR解析是從左到右，最右邊的派生，這意味着我們從左到右掃描並嘗試構造最右邊的派生。解析器不斷挑選輸入的子字符串，並試圖將其反轉回非終結符。

在一個LL解析，解析器連續兩個動作之間進行選擇：

1. 預測：基於最左邊的非終結符和若干前瞻令牌，選擇哪個產品應該被應用到更接近輸入字符串。
2. 符合：匹配最左邊的猜測終端符號和輸入的最左端未消耗符號。

作爲一個例子，考慮到本語法：

• 小號→Ë
• Ë→ T +È
• Ë→Ť
• Ť→ int

然後鑑於串int + int + int，一個LL（2）分析器（它使用先行的兩個標記）將如下分析該字符串：

Production  Input    Action 
--------------------------------------------------------- 
S    int + int + int Predict S -> E 
E    int + int + int Predict E -> T + E 
T + E   int + int + int Predict T -> int 
int + E   int + int + int Match int 
+ E    + int + int  Match + 
E    int + int   Predict E -> T + E 
T + E   int + int   Predict T -> int 
int + E   int + int   Match int 
+ E    + int    Match + 
E    int    Predict E -> T 
T    int    Predict T -> int 
int    int    Match int 
            Accept 

請注意，在每一個步驟中，我們看一下在我們的生產中最左邊的符號。如果它是一個終端，我們匹配它，如果它是一個非終結符，我們通過選擇一個規則來預測它將會是什麼。

在一個LR語法分析器，有兩個動作：

1. 移：輸入的下一個標記添加到考慮一個緩衝。
2. 減少：通過反轉生產，將此緩衝區中的終端和非終止符的集合還原到某個非終結符。你提到

   Workspace  Input    Action 
   --------------------------------------------------------- 
          int + int + int Shift 
   int    + int + int  Reduce T -> int 
   T    + int + int  Shift 
   T +    int + int   Shift 
   T + int   + int    Reduce T -> int 
   T + T   + int    Shift 
   T + T +   int    Shift 
   T + T + int       Reduce T -> int 
   T + T + T       Reduce E -> T 
   T + T + E       Reduce E -> T + E 
   T + E        Reduce E -> T + E 
   E         Reduce S -> E 
   S         Accept 
   

   兩個解析算法（LL和LR）是：

作爲一個例子，一個LR（1）解析器（與先行的一個令牌）可以如下分析該相同的字符串已知具有不同的特徵。LL解析器傾向於更容易手動編寫，但它們不如LR解析器強大，並且接受比LR解析器更小的一組語法。 LR語法分析器有很多種（LR（0），SLR（1），LALR（1），LR（1），IELR（1），GLR（0）等），並且功能更加強大。他們也往往有更復雜的幾乎總是由工具，如yacc或bison。 LL語法分析器也有很多種（包括LL（*），它被ANTLR工具使用），儘管在實踐中LL（1）是使用最廣泛的。

作爲一個無恥的插件，如果您想了解關於LL和LR解析的更多信息，我剛剛完成了一門編譯器課程的教學，並在課程網站上有some handouts and lecture slides on parsing。如果你認爲它會有用，我會很樂意詳細說明它們中的任何一個。

Answer 2

Josh Haberman在他的文章LL and LR Parsing Demystified聲稱LL解析直接對應於Polish Notation，而LR對應於Reverse Polish Notation。 PN和RPN之間的差是遍歷方程的二進制樹的順序：

+ 1 * 2 3 // Polish (prefix) expression; pre-order traversal. 
1 2 3 * + // Reverse Polish (postfix) expression; post-order traversal. 

根據哈伯曼，這說明LL和LR語法分析器之間的主要區別在於：

LL和LR解析器如何操作的主要區別是LL解析器輸出解析樹的預遍歷，LR解析器輸出後序遍歷。

對於深入的解釋，例子和結論檢查哈伯曼的article。