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

讓我們繼續(xù)我們的解析算法的概述。

解析算法

概述

解析算法表

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

該表格列出：

• 一個形式化的描述，來解釋算法背后的理論
• 更實際的解釋
• 一個或兩個實現(xiàn)，通常一個更容易，另一個是專業(yè)解析器。有時候，沒有簡單的版本或?qū)I(yè)版本。

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

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

自頂向下算法

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

LL解析器

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

要找到適用的正確規(guī)則：

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

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

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

LL語法的價值

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

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

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

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

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

Earley解析器

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

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

// 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 .

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

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

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

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

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

Earley使用案例

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

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

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

請繼續(xù)關(guān)注第8部分！

推薦閱讀：

展望2018年：基于AI人工智能的移動應(yīng)用程序開發(fā)將如何發(fā)展

開發(fā)一個聊天機器人（Chatbot）應(yīng)用程序需要花費多少錢？

PS: 更多、相關(guān)視頻、培訓(xùn)、公開課，請關(guān)注！

關(guān)于人工智能技術(shù)的最新資訊和相關(guān)開發(fā)工具推薦，請<>！