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

解析算法

自頂向下算法

Packrat（PEG）

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

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

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

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

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

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

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

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

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

尾遞歸本身只是在函數結束時發生的遞歸。然而，尾部遞歸與語法規則的轉換一起使用。轉換語法規則和在過程結束時進行遞歸的組合允許處理左遞歸規則。

Pratt解析器

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

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

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

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

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

解析器組合器

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

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

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

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

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

請繼續關注第9部分！

推薦閱讀：

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

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

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

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