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

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

解析算法

概述

解析算法表

我們?cè)谙旅嫣峁┮粋€(gè)表格，提供理解和實(shí)現(xiàn)特定分析器算法所需的主要信息摘要。您可以通過(guò)閱讀我們提供用于Java、C＃、Python和JavaScript的解析工具和庫(kù)的文章來(lái)找到更多的實(shí)現(xiàn)（需要這些方面文章資源的同學(xué)可以聯(lián)系Elyn獲取哦）。

該表格列出：

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

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

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

自頂向下算法

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

LL解析器

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

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

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

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

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

LL語(yǔ)法的價(jià)值

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

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

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

有兩種特殊的LL（k）語(yǔ)法：LL（1）和LL（*）。過(guò)去，第一種是唯一被認(rèn)為是實(shí)用的，因?yàn)闉樗麄儤?gòu)建高效的解析器是很容易的。直到許多計(jì)算機(jī)語(yǔ)言被有目的地設(shè)計(jì)為由LL（1）語(yǔ)法描述的時(shí)候。LL（*），也稱為L(zhǎng)L-regular，解析器可以使用無(wú)限量的超前tokens來(lái)處理語(yǔ)言。

在StackOverflow上，您可以閱讀之間的簡(jiǎn)單比較，或之間的比較。

Earley解析器

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

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

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

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

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

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

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

簡(jiǎn)而言之，Earley允許您使用更容易編寫(xiě)的語(yǔ)法，但在性能方面可能不是最理想的。

Earley使用案例

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

例如，第一種情況很有用，因?yàn)榇蠖鄶?shù)情況下，用戶編寫(xiě)的語(yǔ)法工作得很好。問(wèn)題是解析器會(huì)拋出模糊和看似隨機(jī)的錯(cuò)誤。當(dāng)然，這些錯(cuò)誤實(shí)際上并不是隨機(jī)的，但是這是由于用戶不知道或不明白的算法的局限性。所以，你迫使用戶理解你的解析器的內(nèi)部工作來(lái)使用它，這是不必要的。

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

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

推薦閱讀：

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

開(kāi)發(fā)一個(gè)聊天機(jī)器人（Chatbot）應(yīng)用程序需要花費(fèi)多少錢(qián)？

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

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