我們已經到了最后！如果您是第一次遇到這個系列，請查看上面的其他帖子。

解析算法

我們最后的重點是自下而上的算法。

自下而上算法

自下而上策略的主要成功是許多不同LR解析器的家族。雖然LR解析器比傳統的LL（1）語法更強大，但它們相對不受歡迎的原因是，歷史上它們難以建立。因此，除了對CYK解析器的簡要描述之外，我們主要關注它們。

這意味著我們避免談論更通用的shift-reduce分析器類，它也包含LR分析器。

Shift-Reduce算法分兩步工作：

1. Shift：從輸入中讀取一個token，這將成為一個新的（暫時孤立的）節點。
2. Reduce：一旦適當的規則匹配，加入結果樹與先行的現有子樹。

基本上，Shift步驟讀取輸入直到完成，而Reduce步驟連接子樹，直到構建最終的分析樹。

CYK解析器

Cocke-Younger-Kasami（CYK）算法由三位作者獨立制定。它的顯著性是由于最糟糕的表現（O（n3））造成的，盡管它在大多數常見的情況下受到相對較差的表現的阻礙。

然而，該算法的真正缺點是它需要以表示。

這是因為該算法依賴于這種特殊形式的屬性，能夠將輸入分成兩半來嘗試匹配所有的可能性。從理論上講，任何上下文無關的語法都可以轉化為相應的CNF，但這種手段很少實用。想象一下，你不能使用左遞歸規則，然后被要求學習一種特殊的形式這一事實令人煩惱。

CYK算法主要用于特定問題；例如，會員問題：確定一個字符串是否與某個語法兼容。它也可以在自然語言處理中使用，以找到許多選項之間最可能的解析。

出于所有實際的目的，如果您需要解析所有上下文無關的語法，并且性能很差，那么您需要使用Earley解析器。

LR分析器

LR（從左到右讀取輸入；最右邊的派生）分析器是自下而上的分析器，可以以線性時間處理確定性的上下文無關語言，而且無需回溯。LR解析器的發明歸功于著名的Donald Knuth。

傳統上，他們已經被比較，并與LL解析器競爭。有一個類似的分析需要解析一個語言的前瞻tokens的數量。一個LR（k）解析器可以解析需要解析前向k個tokens的語法。然而，LR語法的限制性較小，因此比相應的LL語法更強大。例如，不需要排除左遞歸規則。

從技術上講，LR語法是LL語法的超集。這樣做的一個結果是你只需要LR（1）語法，所以通常，（k）被省略。

它們也是基于表格的，就像LL解析器一樣，但是它們需要兩個復雜的表格。非常簡單地說：

1. 一個表告訴解析器根據當前的token，它所處的狀態以及可能跟隨當前token（token集）做什么。
2. 另一個告訴解析器接下來的狀態。

LR語法分析器功能強大，性能很好，所以在哪里？他們需要的表格很難用手工編寫，對于普通的計算機語言來說可能會變得非常大，所以通常通過語法分析器來使用它們。如果您需要手動構建解析器，則可能更喜歡自頂向下的解析器。

簡單LR和前瞻LR

解析器生成器避免了創建這樣的表的問題，但是它們不能解決生成和瀏覽這樣的大表的成本問題。Knuth描述的規范LR（1）解析器有更簡單的選擇。這些替代品比原來的要少。它們是簡單的LR解析器（SLR）和前瞻LR解析器（LALR）。所以，按照能力的順序，我們有：

1. LR(1)
2. LALR(1)
3. SLR(1)
4. LR(0)

Frank DeRemer發明的兩個解析器的名字有些誤導：一個不是那么簡單，另一個不是唯一使用前瞻的解析器。我們可以說一個更簡單，另一個更依賴前瞻來做出決定。

基本上，他們使用的表格不同。大多數情況下，他們改變了“做什么”的部分和前瞻集，這又對語法分析提出了不同的限制。換句話說，他們使用不同的算法從語法中派生語法分析表。

SLR解析器在實際應用上有相當的限制，并不經常使用。LALR解析器反而適用于大多數實際的語法，并被廣泛使用。實際上，使用LALR解析器表的流行工具yacc和bisonwork。

與LR語法相反，LALR和SLR語法不是LL語法的超集。他們不容易比較；一些語法可以被一個類而不是另一個所覆蓋，反之亦然。

廣義LR解析器

通用的LR解析器（GLR）是LR解析器的更強大的變體。它們在1974年由Bernard Land描述，1984年由Tomita首次實現。GLR存在的原因是需要解析非確定性和模糊的語法。

在其表上找不到GLR解析器的威力，這相當于傳統LR解析器的表。相反，它可以移動到不同的狀態。在實踐中，如果存在歧義，則會派生一個新的解析器（或解析器）來處理特定的情況。這些解析器可能會在稍后階段失敗并被丟棄。

GLR解析器的最壞情況下的復雜度與Earley（O（n3））相同，盡管用確定性語法的最好情況可能會有更好的性能。一個GLR解析器也比Earley的解析器更難構建。

總結

通過這個大系列，我們希望解決大部分關于解析術語和算法的疑問，比如術語的含義以及為什么選擇某種算法。我們不僅解釋了它們，而且還解釋了解析編程語言的一些常見問題。

由于時間和精力的原因，我們無法提供所有解析算法的詳細解釋。所以，我們還提供了一些鏈接，讓您更深入地了解這些算法，背后的理論以及它們是如何工作的。

如果您只是對解析感興趣，您可能需要閱讀“解析技術”（）這本書。它明顯比我們的理解深入得多，并且它也涵蓋了一些較少使用的解析算法。

推薦閱讀：

展望2018年：基于AI人工智能的移動應用程序開發將如何發展

開發一個聊天機器人（Chatbot）應用程序需要花費多少錢？

PS: 更多、相關視頻、培訓、公開課，請關注！

關于人工智能技術的最新資訊和相關開發工具推薦，請<>！