在閱讀之前，請務(wù)必首先查看第1部分、第2部分、第3部分、第4部分和第5部分！

解析算法

從理論上講，解析是一個已解決的問題，但是這種問題還是會一再地被解決。也就是說，有很多不同的算法，每個算法都有強(qiáng)大的優(yōu)點(diǎn)和缺點(diǎn)，而且學(xué)者們還在不斷進(jìn)步。

在本節(jié)中，我們不會教導(dǎo)如何實(shí)現(xiàn)每一個解析算法，但是我們將解釋它們的特征。目標(biāo)是您可以選擇更多的知道哪些分析工具使用或哪些算法更好地學(xué)習(xí)和實(shí)現(xiàn)您的自定義分析器。

概述

我們先從全局概述所有解析器的功能和策略。

兩種策略

有兩種解析策略：自頂向下解析（top-down parsing）和自底向上解析（bottom-up parsing）。這兩個術(shù)語都是根據(jù)解析器生成的分析樹來定義的。簡單的解釋：

• 自頂向下的解析器首先嘗試識別解析樹的根，然后向下移動子樹直到找到樹的葉子。
• 自下而上的解析器是從樹的最低部分（樹葉）開始，然后上升直到確定樹的根部。

讓我們看一個例子，從一個分析樹開始。

示例解析樹（）

同樣的樹會由一個自頂向下和一個自底向上的解析器以不同的順序生成。在下面的圖片中，數(shù)字表示創(chuàng)建節(jié)點(diǎn)的順序。

自上而下的樹的生成順序（）

自下而上的生成樹的順序（）

傳統(tǒng)上，自頂向下的解析器更容易構(gòu)建，但自下而上的解析器更強(qiáng)大。現(xiàn)在，情況更加平衡，主要是因?yàn)樽陨隙碌慕馕霾呗缘倪M(jìn)步。

推導(dǎo)的概念與策略密切相關(guān)。派生指出了規(guī)則中的非終結(jié)符元素出現(xiàn)在右側(cè)的順序，用于獲取左側(cè)的非終結(jié)符號。使用BNF術(shù)語，它指示如何使用__expression__中出現(xiàn)的元素來獲得< symbol >。這兩種可能性是最左邊的推導(dǎo)和最右邊的推導(dǎo)。第一個表示規(guī)則從左到右應(yīng)用，而第二個表示相反。

一個簡單的例子：想象一下，你正在試圖解析符號結(jié)果，在語法中定義了這樣的結(jié)果。

expr_one = .. // stuff
expr_two = .. // stuff
result   = expr_one 'operator' expr_two

您可以先將符號規(guī)則應(yīng)用于符號expr_one，然后執(zhí)行expr_two，反之亦然。在最左邊的派生的情況下，你選擇第一個選項(xiàng)，而為了最右邊的派生，你選擇第二個。

理解推導(dǎo)是深度優(yōu)先還是遞歸應(yīng)用是很重要的。也就是說，它被應(yīng)用到開始表達(dá)式，然后再被應(yīng)用到所獲得的中間結(jié)果。因此，在這個例子中，如果在應(yīng)用expr_one對應(yīng)的規(guī)則之后，有一個新的非終結(jié)符；那個先變了 非終結(jié)符expr_two僅在它成為第一個非終結(jié)符并且不遵循原始規(guī)則中的順序時才應(yīng)用。

派生與兩種策略相關(guān)聯(lián)，因?yàn)閷τ谧韵露系慕馕觯梢詰?yīng)用最右邊的派生，而對于自頂向下的解析，您可以選擇最左派生。請注意，這對最終的解析樹沒有影響；它只是影響中間元素和使用的算法。

共同的元素

用自上而下和自下而上的策略構(gòu)建的解析器有一些我們應(yīng)該談?wù)摰膬?nèi)容。

前瞻性和回溯性

術(shù)語“前瞻”和“回溯”在解析方面的含義與其在大型計(jì)算機(jī)科學(xué)領(lǐng)域中的含義不同。Lookahead表示在當(dāng)前的元素之后的元素的數(shù)量，這些元素被考慮來決定采取哪個當(dāng)前的行動。

一個簡單的例子：解析器可能會檢查下一個標(biāo)記以決定現(xiàn)在應(yīng)用哪個規(guī)則。當(dāng)適當(dāng)?shù)囊?guī)則匹配時，當(dāng)前token被消耗，但下一個仍然在隊(duì)列中。

回溯是一種算法的技術(shù)。它包括通過嘗試部分解決方案找到復(fù)雜問題的解決方案，然后不斷檢查最有前途的解決方案。如果當(dāng)前正在測試的那個失敗，則解析器回溯（即，它回到最后被成功解析的位置）并且嘗試另一個。

它們與LL、LR和LALR分析算法特別相關(guān)，因?yàn)橹恍枰粋€預(yù)讀標(biāo)記的語言的解析器更容易構(gòu)建并且更快地運(yùn)行。在算法名稱之后的括號（即LL（1），LR（k））之間指示由這些算法使用的前瞻tokens。符號（*）表示該算法可以檢查無限的超前tokens，盡管這可能會影響算法的性能。

圖表解析器

圖表解析器是可以自下而上（即CYK）或自上而下（即Earley）的一系列解析器。圖表解析器基本上試圖通過使用動態(tài)編程來避免回溯，這可能是昂貴的。或動態(tài)優(yōu)化是在較小的子問題中解決較大問題的一般方法。

圖表解析器使用的常見動態(tài)編程算法是（Viterbi algorithm）。該算法的目標(biāo)是在給定已知事件序列的情況下找到最有可能的隱藏狀態(tài)。基本上，考慮到我們所知道的tokens，我們試圖找出最可能的規(guī)則。

名稱圖表解析器來自這樣一個事實(shí)，即部分結(jié)果存儲在名為圖表的結(jié)構(gòu)中（通常，圖表是表格）。存儲部分結(jié)果的特定技術(shù)稱為memoization。其他算法也使用Memoization，與圖表解析器無關(guān)，如packrat。

自動機(jī)

在討論解析算法之前，我們想談?wù)勗诮馕鏊惴ㄖ?使用自動機(jī)。是一個抽象機(jī)器族群，其中有著名的圖靈機(jī)（Turing machine）。

當(dāng)談到解析器時，您可能會聽到（確定性）下推自動機(jī)（PDA）這個術(shù)語，當(dāng)您閱讀詞法分析器時，您會聽到術(shù)語（確定性）有限自動機(jī)（DFA）。PDA比DFA更強(qiáng)大，更復(fù)雜（雖然比圖靈機(jī)簡單）。

由于它們定義了抽象機(jī)器，通常它們與實(shí)際算法沒有直接關(guān)系。相反，他們正式描述算法必須能夠處理的復(fù)雜程度。如果有人說解決問題X需要一個DFA，他意味著你需要一個和DFA一樣強(qiáng)大的算法。

但是，由于DFA是狀態(tài)機(jī)，在詞法分析器的情況下，區(qū)分通常是沒有意義的。這是因?yàn)闋顟B(tài)機(jī)實(shí)現(xiàn)相對簡單（即有現(xiàn)成的庫），所以大多數(shù)情況下，DFA是通過狀態(tài)機(jī)實(shí)現(xiàn)的。這就是為什么我們要簡要地談?wù)揇FA以及為什么他們經(jīng)常用于詞法分析器。

用確定性有限自動機(jī)（Deterministic Finite Automaton）進(jìn)行詞法分析

DFA是一個（有限的）狀態(tài)機(jī)，這個概念我們假設(shè)你很熟悉。基本上，狀態(tài)機(jī)有許多可能的狀態(tài)和每個狀態(tài)的轉(zhuǎn)換函數(shù)。這些轉(zhuǎn)換功能控制機(jī)器如何從一個狀態(tài)移動到另一個狀態(tài)以響應(yīng)事件。當(dāng)用于練習(xí)時，機(jī)器每次輸入一個輸入字符，直到達(dá)到接受狀態(tài)（即它可以建立一個標(biāo)記）。

他們用于幾個原因：

• 事實(shí)證明，他們確實(shí)認(rèn)可了一套正規(guī)語言；也就是說，它們和普通語言一樣強(qiáng)大。
• 有一些數(shù)學(xué)方法來操作和檢查它們的屬性（即它們是否可以解析所有字符串或任何字符串）。
• 他們可以使用高效的在線算法（見下文）。

在線算法是一個不需要整個輸入工作的算法。在詞法分析器的情況下，這意味著只要算法看到其中的字符，就可以識別它。另一種選擇是它需要整個輸入來識別每個token。

除了這些屬性之外，將一組正則表達(dá)式轉(zhuǎn)換為DFA相當(dāng)容易，這使得可以以許多開發(fā)人員熟悉的簡單方式輸入規(guī)則。然后，您可以自動將其轉(zhuǎn)換為可以高效處理的狀態(tài)機(jī)。

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

推薦閱讀：

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

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

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

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