由于GFW，我無法聯系到作者，所以沒有授權，瞎翻譯的。原文在這里[http://blog.reverberate.org/2013/07/ll-and-lr-parsing-demystified.html]。

這是第2部分和完結。

3. 解析樹的形狀

到目前為止，我們使用的算術表達式的那棵樹，仍然不是解析樹，因為它并未與語法關聯。要考查一棵真正的解析樹，我們需要語法。不幸的是，為中綴算術表達式寫語法不像你期待的那么簡單和優雅。對優先級和結合性 (楊注：操作符左結合還是右結合)編碼，保證語法沒有二義性 (并受LL和LR支持) ，是非常丑陋和不符合直覺的。這也是為什么LL和LR解析器也允許你做指定操作符優先級這樣的擴展；比如，參見Bison優先級的相關特性[http://www.gnu.org/software/bison/manual/html_node/Precedence.html#Precedence]。而這篇文章的目的是打算討論純的LL和LR。

因此，我們得把那個算術表達式的例子調整為比較容易寫的語法的形式。我們將使用JSON (楊注：JSON是javascript的對象表示方法) ，既然它非常簡單，而又足夠復雜和有趣。

1 object → '{' pairs '}'
2 ?
3 pairs → pair pairs_tail | ε
4 pair → STRING ':' value
5 pairs_tail → ',' pairs | ε
6 ?
7 value → STRING | NUMBER | 'true' | 'false' | 'null' | object | array
8 array → '[' elements ']'
9 ?
10 elements → value elements_tail | ε
11 elements_tail → ',' elements | ε


上面，我用了單引號括起的字符串表示 原文文字標記 (literal tokens)，用大寫字母，比如STRING，表示那些拼寫不確定的tokens (比如，"abc"和""都是有效的STRING tokens)。所有的名字小寫字母的，都是語法規則 (也稱 非葉節點)。

你可能奇怪，為什么我要用 pairs_tail 和 elements_tail，而不用重復構造 (repetition construct) ，像很多解析器比如ANTLR支持的那樣。這樣，我們就可以這樣寫：

elements → value (',' value)*

使用*的這種語法，用起來更方便，語法也更簡單，但是同時，它導致解析樹概念上更復雜了一點，因為某個給定的語法規則的子樹個數不再是確定不變的。并且，LR解析器不支持重復操作符(比如，Bison就不支持)，這樣，我上面寫的語法就既可以用于LL也可以用于LR解析器。因此，我們現在要使用這個有點復雜的語法。

現在，我們有語法了，那么我們來看一個token的流的例子，再來看輸出的解析樹。

{"message":"Hello, World!"}

上述這段文字的token流是：

{ STRING : STRING }

而它的解析樹，按我們的語法，就是：



注意，所有的葉結點 (綠色的)都是tokens，它們的順序與我們的解析器的輸入順序是完全一致的。 (我做了一點小弊，把ε作為葉結點了，不過正如我們所看到的，這看起來更干凈更規則一些)

我前面曾經斷言過，LL解析器輸出的是先序遍歷，而LR解析器輸出的是后序遍歷。從這一點出發，我們可以知道LL和LR解析器對上述輸入分別會給出什么輸出：



既然葉節點總是輸入的tokens本身，且完全按輸入的順序，所以所有的解析器真正所做的，就是把中間節點 (楊注：語法規則)插入到合適的位置。看這一點的另一個角度就是，一棵解析樹，就是一堆結構體，這堆結構體定義在輸入的tokens的序列之上。我們稍微重新安排一下之前的這個圖示，這一點看起來就更清楚了。
?



我們正集中討論一個非常簡單的模型，用這個模型描述LL和LR解析器如何工作。LL和LR解析器二者都讀入一個輸入tokens的流，再把相同的流作為輸出，并且把規則 (楊注：中間節點)插入到適當的位置，以形成解析樹的先序 (LL)或后序 (LR)遍歷。




這樣，按波蘭和逆波蘭表示法考慮，這種對解析器輸出的認識又帶給我們一個好處。它使得我們可以對解析器的輸入和輸出都按簡單的、平坦的流建模。這比把解析器的中間輸出狀態視為部分地構造樹要容易多了，那種思路對于理解輸出和對輸出的檢驗都沒什么幫助。

4. 超前 (Lookahead)

LL和LR解析器都是"在線的"，意味著它們都能在輸入正在進行時開始產生輸出. ?但是在許多情況下，在流的位置之前的tokens沒有包含足夠的信息，因此解析無法知道是否需要插入規則 (或者，如果需要插入規則，應該插入哪一條).因此，解析器得超前 (lookahead)到流的后面，看看下面的一些tokens是什么，以便做出決定。當你看到像LL(1)或者LR (0)這樣的命令的時候，括號里的數字就是要超前的tokens的數量。

值得注意的是，超前是相對于規則將要插入的位置而言的，這個位置 (正如你記得的)對于LL解析器而言是在規則的tokens之前，而在LR解析器的規則tokens之后。這意味著，LL超前從規則的tokens的開頭開始計數，LR從末尾開始計數。這帶給LR解析器一個巨大的益處，因為在它們做出決定之前，他們能夠看到規則的所有tokens (可能再超前一些)，而LL解析器只能看到規則最初的幾個tokens。



這就是為什么會有LR(0)解析器這種東西，而LL(0)解析器是不可能存在的；那樣就根本不會有信息用來幫助決定接下來的tokens應該使用哪條規則。


5. 結果

根據上述對于LL和LR解析的比較的理解，我們能夠得到幾條重要的結論，有助于理解為什么有些當然的事是那樣的。

(1) LR解析器能夠處理更多的語法

這一點可由上一節超前 (lookahead)推得。既然LR超前開始于規則的末尾，在做決定的時候，LR(1)就確定地比LL(1)擁有更多的信息。進而，LR(1) 解析器確定地能比LL(1)解析器多解析一些語法 (楊注：原文接下來在括號里是modulo LL-only grammar extensions; see below。我不知道什么意思)。LR解析器可以處理左遞歸，LL解析器不能。

優勢：LR

(2) (楊注：EBNF這一類的)

另一方面，既然LL解析器在開始解析規則的tokens之前就選定了使用哪條規則，并且無論LL解析器什么時候解析一個token的時候，它一定知道其token的上下文。這是一個更困難的任務 (既然它們擁有的能夠繼續的信息更少)，這導致了一些重要的優勢。

LL解析器在語法中能支持 像正則表達式 一樣的操作符。

知道解析的上下文，這使得利用正則表達式形式的多種多樣的操作符成為可能，比如重復 (楊注：*)，比如alternation (楊注：|)，而且可以用在任何地方，而不僅僅是頂層處。基本上，每條規則都能構成一個DFA狀態機。對于自頂向下的解析，這是可能的，因為解析器知道它位于哪條規則之中，在解析進行的過程中可以按規則的狀態機進行。我認為這對于自底向上的解析，這是不可能的 (甚至如果你以某種方法令解析表做正確的事，歸約那一步也需要歸約有固定不變的參數個數。楊注：不懂)。這對于LL真是個好優點，因為有這些豐富的語法擴展(楊注：指類似正則表達式的)，語法容易讀多了。事實上，這有利于使LL那種嚴格語法的局面有所緩和，因為許多你需要左遞歸的地方都可以使用重復 (*)操作符替代。

1 // LR語法: 不允許任何特殊的，alternation 只允許
2 // 在頂層出現
3 //
4 // 允許這一條是因為它等價于
5 // pairs → pair pairs_tail
6 // pairs → ε
7 pairs → pair pairs_tail | ε
8 ?
9 // 擴展的LL語法； 之所以可能，是因為你可以對把每條規則
10 // 構造成一個DFA
11 pairs → (pair (',' pair)*)?

后一條規則可以構造出像這樣的DFA (綠色的狀態表示接受狀態) ：



知道上下文，也使得在規則中間的動作成為可能 (定制代碼，這些代碼運行在規則里的任意兩個元素之間。楊注：如antlr的 semantic action)。Bison支持這一點，是通過在內部重寫了語法，這使得所有的可視化 (楊注：可能指語法定義的時候？)都更加復雜了。

優勢：LL

(3) LL解析器支持上下文相關的掃描/詞法分析

知道上下文，另一個好處是也使得上下文相關的掃描/詞法分析成為可能。比如，許多程序設計語言不允許把關鍵詞用于變量名，因為獨立的詞法分析器 (及自底向上的解析器)不知道出現在這個位置上的token是變量名還是關鍵字。但是自頂向下的解析器調用詞法解析器的時候，可以輕易地把當前的上下文傳遞給它。

優勢：LL

(4) LL解析器支持繼承屬性

知道上下文，也能夠支持基于LL的應用程序在構造樹的時候把屬性/元數據傳遞給樹 (這有時被稱為繼承屬性。楊注原文：inherited attribute)。 (無論LL還是LR解析器都支持綜合屬性 (楊注：原文synthesized attributes)，是由樹向上傳遞的)。

優勢：LL

6. 結論

我描述了一種另類的LL和LR解析器的模型，這種模型與大多數文獻中提到的等價，但是更符合直覺 (至少對我而言是這樣)。我們可以把解析器視為黑盒子，這個黑盒子輸入輸出與先序和后序表示法對應的token和規則的流。至目前為止，我們還沒有探索這些解析器的內部工作原理；我們只是把它們視作黑盒，我們不清楚它們內部的工作。我們也沒有探究它們能處理和不能處理何種語法的問題。我們也沒有探索LL和LR的變形 (Strong-LL, SLR, LALR等等)。我希望在接下來的文章中會更完整地討論它們，再包含上示例代碼。

轉載于:https://www.cnblogs.com/dyllove98/p/3209190.html

總結

以上是生活随笔為你收集整理的解密：LL与LR解析 2（译，完结）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。