在閱讀之前，一定要查看第1-6部分！

讓我們繼續我們的解析算法的概述。

解析算法

概述

解析算法表

我們在下面提供一個表格，提供理解和實現特定分析器算法所需的主要信息摘要。您可以通過閱讀我們提供用于Java、C＃、Python和JavaScript的解析工具和庫的文章來找到更多的實現（需要這些方面文章資源的同學可以聯系Elyn獲取哦）。

該表格列出：

• 一個形式化的描述，來解釋算法背后的理論
• 更實際的解釋
• 一個或兩個實現，通常一個更容易，另一個是專業解析器。有時候，沒有簡單的版本或專業版本。

要理解解析算法的工作原理，還可以查看語法分析工具包。這是一個解析器生成器教程，它描述了生成的解析器完成其目標的步驟。它實現了一個LL和一個LR算法。

第二個表格顯示了不同解析算法的主要特征以及它們通常使用的內容的總結。

自頂向下算法

自上而下的策略是兩種策略中最普遍的策略，并且有幾種成功的算法在應用它。

LL解析器

LL（從左到右讀取輸入，最左邊的派生）解析器是基于表格的解析器，沒有回溯，但具有前瞻性。基于表格意味著他們依靠分析表來決定應用哪個規則。解析表分別用作行和列的非終結符和終端。

要找到適用的正確規則：

1. 首先，解析器查看當前token和適量的先行tokens。
2. 然后，它試圖應用不同的規則，直到找到正確的匹配。

LL解析器的概念并不是指特定的算法，而更多的是指一類解析器。它們是根據語法來定義的。也就是說，LL解析器是一個可以解析LL語法的解析器。反過來，LL語法是根據解析它們所需的先行標記的數量來定義的。這個數字在LL旁邊的括號中表示，所以形式為LL（k）。

LL（k）解析器使用k個令牌的lookahead，因此它最多可以解析需要解析k個令牌的lookahead的語法。實際上，LL（k）語法的概念比相應的語法分析器更廣泛地使用——這意味著當比較不同的算法時，LL（k）語法被用作meter。例如，你會看到PEG解析器可以處理LL（*）語法。

LL語法的價值

LL語法的這種使用是由于LL語法分析器被廣泛使用并且有點限制的緣故。實際上，LL語法不支持左遞歸規則。你可以用等價的非遞歸形式來轉換任何左遞歸語法，但是這個限制的重要性有兩個：生產力和能力。

生產力的損失取決于你必須以特殊的方式寫出語法的需求，這需要花費時間。能力是有限的，因為當用左遞歸規則編寫時，可能需要一個前瞻標記的語法在以非遞歸方式寫入時可能需要兩個或三個向前的標記。所以，這個限制不僅僅是煩人的，它限制了算法的能力，即它可以用于的語法。

生產力的損失可以通過一種算法來減輕，該算法自動轉換非遞歸語法中的左遞歸語法。ANTLR是一個可以做到這一點的工具，但是當然，如果你正在構建你自己的解析器，你必須自己去做。

有兩種特殊的LL（k）語法：LL（1）和LL（*）。過去，第一種是唯一被認為是實用的，因為為他們構建高效的解析器是很容易的。直到許多計算機語言被有目的地設計為由LL（1）語法描述的時候。LL（*），也稱為LL-regular，解析器可以使用無限量的超前tokens來處理語言。

在StackOverflow上，您可以閱讀之間的簡單比較，或之間的比較。

Earley解析器

Earley解析器是一個以其發明者Jay Earley命名的圖表解析器。該算法通常與CYK（另一個圖表解析器）進行比較，該算法更簡單，但通常在性能和內存方面更差。Earley算法的突出特點是，除了存儲部分結果之外，還實現了一個預測步驟，以決定哪個規則將要嘗試匹配下一個。

Earley解析器從根本上按照分段劃分規則來工作，如下例所示。

// an example grammar
HELLO    : "hello"
NAME     : [a-zA-Z]+
greeting : HELLO NAME
// Earley parser would break up greeting like this
// . HELLO NAME
// HELLO . NAME
// HELLO NAME .

然后，在可以連接點（.）的這個段上工作，試圖達到完成狀態; 也就是說。末尾的內容在最后有一個點。

Earley解析器的吸引力在于能夠解析所有上下文無關的語言，而其他著名的算法（即LL、LR）只能解析其中的一個子集。例如，左遞歸語法沒有問題。更一般地說，Earley解析器也可以處理非確定性和模糊的語法。

在最糟糕的情況下，它可能會導致性能下降（O（n3））。但是，對于正常語法，它具有線性時間表現。問題在于用更傳統的算法解析的語言集合是我們通常感興趣的。

它也有一個缺點的副作用：通過強迫開發人員以某種方式編寫語法，解析可以更有效率，也就是說，構建一個LL（1）語法對于開發人員來說可能比較困難，但是解析器可以非常有效地應用它。Earley，你做的工作少，所以解析器做的更多。

簡而言之，Earley允許您使用更容易編寫的語法，但在性能方面可能不是最理想的。

Earley使用案例

所以，Earley解析器很容易使用，但在平均情況下，性能方面的優勢可能是不存在的。這使得該算法對于教育環境或生產力比速度更重要的地方是很好的。

例如，第一種情況很有用，因為大多數情況下，用戶編寫的語法工作得很好。問題是解析器會拋出模糊和看似隨機的錯誤。當然，這些錯誤實際上并不是隨機的，但是這是由于用戶不知道或不明白的算法的局限性。所以，你迫使用戶理解你的解析器的內部工作來使用它，這是不必要的。

生產力比速度更重要的一個例子可能是解析器生成器，用于為需要支持多種語言的編輯器實現語法高亮。在類似的情況下，能夠快速支持新語言可能比盡快完成任務更為可取。

請繼續關注第8部分！

推薦閱讀：

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

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

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

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