一定要先看看第7部分！如果您第一次遇到這個系列，您可以在本文頂部找到其余的帖子。

解析算法

自頂向下算法

Packrat（PEG）

Packrat經(jīng)常與正式語法PEG相關(guān)，因為它們是由同一個人Bryan Ford發(fā)明的。Packrat在他的論文中首先被描述了：標題說幾乎所有我們關(guān)心的事情：它有一個線性的執(zhí)行時間，不使用回溯。

其效率的另一個原因是記憶：在解析過程中存儲部分結(jié)果。缺點是，直到最近才使用該技術(shù)的原因是存儲所有中間結(jié)果所需的內(nèi)存數(shù)量。如果所需的內(nèi)存超過了可用的內(nèi)存，算法將失去執(zhí)行的線性時間。

Packrat也不支持左遞歸規(guī)則，因為PEG需要總是選擇第一個選項。實際上，一些變體可以支持直接的左遞歸規(guī)則，但是以犧牲線性復(fù)雜性為代價。

如果需要的話，Packrat解析器可以執(zhí)行無限量的lookahead。這會影響執(zhí)行時間，在最壞的情況下可能是指數(shù)級的。

遞歸下降解析器（Recursive Descent Parser）

遞歸下降解析器是一個解析器，它與一組（相互）遞歸過程一起工作，對于語法的每個規(guī)則通常是一個過程。因此，解析器的結(jié)構(gòu)反映了語法的結(jié)構(gòu)。

termpredictive解析器以幾種不同的方式使用：有些人把它作為自頂向下解析器的同義詞，有些人認為它是從不回溯的遞歸下降解析器。

第二個含義的反義詞是一個遞歸下降解析器，它會回溯。也就是說，通過依次嘗試每一個規(guī)則，然后每次失敗就返回，找到與輸入相匹配的規(guī)則。

通常，遞歸下降解析器在解析左遞歸規(guī)則時會遇到問題，因為算法會一次又一次地調(diào)用同一個函數(shù)。這個問題的一個可能的解決方案是使用尾遞歸。使用此方法的解析器稱為尾遞歸解析器。

尾遞歸本身只是在函數(shù)結(jié)束時發(fā)生的遞歸。然而，尾部遞歸與語法規(guī)則的轉(zhuǎn)換一起使用。轉(zhuǎn)換語法規(guī)則和在過程結(jié)束時進行遞歸的組合允許處理左遞歸規(guī)則。

Pratt解析器

Pratt解析器是一個廣泛未使用的，但非常值得贊賞的（由少數(shù)人知道的），由Vaughan Pratt在一篇名為“”的論文中定義的解析算法。本文首先從BNF語法的論戰(zhàn)開始，筆者認為錯誤的是解析研究的唯一問題。這是缺乏成功的原因之一。實際上，該算法不依賴于語法，而是直接對tokens進行操作，這使解析專家變得不同尋常。

第二個原因是，如果你有一個有意義的前綴來幫助區(qū)分不同的規(guī)則，那么傳統(tǒng)的自頂向下的解析器就能很好地工作。例如，如果您得到token FOR，您正在查看for語句。由于這基本上適用于所有的編程語言及其語句，所以很容易理解為什么Pratt解析器沒有改變解析世界。

Pratt算法的亮點在于表達式。事實上，優(yōu)先的概念使得不可能僅僅通過查看tokens的順序來理解輸入的結(jié)構(gòu)。

基本上，該算法要求您為每個運算符token分配一個優(yōu)先值，并根據(jù)token的左側(cè)和右側(cè)確定要執(zhí)行的操作。然后，它使用這些值和函數(shù)在遍歷輸入的同時將操作綁定在一起。

雖然Pratt算法沒有公開地成功，但它用于解析表達式。JSLint也為Douglas Crockford（JSON成名）所采用。

解析器組合器

解析器組合器是一個高階函數(shù)，接受解析器函數(shù)作為輸入，并返回一個新的解析器函數(shù)作為輸出。解析器函數(shù)通常意味著接受一個字符串并輸出解析樹的函數(shù)。

解析器組合器是模塊化的并且易于構(gòu)建，但是它們也比較慢（在最壞的情況下它們具有O（n4）復(fù)雜性）并且不太高端。它們通常被用于更簡單的解析任務(wù)或原型設(shè)計。從某種意義上說，解析器組合器的用戶部分手動構(gòu)建解析器，但依賴于創(chuàng)建解析器組合器的人所做的艱苦工作。

通常，它們不支持左遞歸規(guī)則，但是有更高級的實現(xiàn)可以做到這一點。例如，參見，其也設(shè)法描述具有執(zhí)行多項式時間的算法。

許多當代實現(xiàn)被稱為monadic解析器組合器，因為它們依賴于稱為的函數(shù)式編程的結(jié)構(gòu)。Monad是一個相當復(fù)雜的概念，我們不能在這里解釋。但是，monad基本上可以將依賴于數(shù)據(jù)類型的功能和操作組合起來。關(guān)鍵的特點是數(shù)據(jù)類型指定如何組合不同的值。

最基本的例子是Maybe monad。這是一個正常類型的包裝器，比如整數(shù)，在值有效的時候（567）返回值本身，當它不是時（即未定義或被零除），則返回一個特殊的值Nothing。因此，你可以避免使用空值，并毫不客氣地崩潰程序。相反，Nothing值是正常管理的，就像管理任何其他值一樣。

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

推薦閱讀：

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

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

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

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