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

解析算法

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

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

概述

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

兩種策略

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

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

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

示例解析樹（）

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

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

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

傳統(tǒng)上，自頂向下的解析器更容易構建，但自下而上的解析器更強大。現(xiàn)在，情況更加平衡，主要是因為自上而下的解析策略的進步。

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

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

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

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

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

派生與兩種策略相關聯(lián)，因為對于自下而上的解析，您可以應用最右邊的派生，而對于自頂向下的解析，您可以選擇最左派生。請注意，這對最終的解析樹沒有影響；它只是影響中間元素和使用的算法。

共同的元素

用自上而下和自下而上的策略構建的解析器有一些我們應該談論的內容。

前瞻性和回溯性

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

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

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

它們與LL、LR和LALR分析算法特別相關，因為只需要一個預讀標記的語言的解析器更容易構建并且更快地運行。在算法名稱之后的括號（即LL（1），LR（k））之間指示由這些算法使用的前瞻tokens。符號（*）表示該算法可以檢查無限的超前tokens，盡管這可能會影響算法的性能。

圖表解析器

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

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

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

自動機

在討論解析算法之前，我們想談談在解析算法中使用自動機。是一個抽象機器族群，其中有著名的圖靈機（Turing machine）。

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

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

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

用確定性有限自動機（Deterministic Finite Automaton）進行詞法分析

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

他們用于幾個原因：

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

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

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

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

推薦閱讀：

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

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

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

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