16. Error Handling
名詞定義
錯(cuò)誤檢測(cè)（Detection）：判斷輸入字符串是否包含語(yǔ)法錯(cuò)誤。
錯(cuò)誤恢復(fù)（Recovery）：找出輸入字符串中的所有語(yǔ)法錯(cuò)誤。
錯(cuò)誤修正（Correction）：修復(fù)輸入字符串，以得到一顆完整的語(yǔ)法樹(shù)。這樣相關(guān)的語(yǔ)義動(dòng)作（semantic action）才可以被觸發(fā)。
正確前綴性質(zhì)（correct-pre?x property）：出錯(cuò)位置為止的已識(shí)別的字符串，是該語(yǔ)言的合法字符串。
最少錯(cuò)誤修正方法（least-error correction method）：全局錯(cuò)誤處理（Global Error Handling）的一種方法，對(duì)輸入字符串的修正次數(shù)做出限制，找出滿足限制條的對(duì)輸入字符串做最少修正的解析方法。
局部錯(cuò)誤處理（Regional error handling）：在出錯(cuò)位置附近收集上下文信息，向解析棧頂壓入一些狀態(tài)，或者向輸入字符串前加入一些字符，使得解析器可以繼續(xù)解析。
續(xù)延（continuation）：對(duì)于具備正確前綴性質(zhì)（correct-pre?x property）的解析器，已識(shí)別字符串u的continuation，是另一個(gè)字符串w，使得uw是符合原文法的字符串。
續(xù)延文法（continuation grammar）：對(duì)原文法進(jìn)行刪減，只留下所需推導(dǎo)步數(shù)最少的產(chǎn)生式規(guī)則（最小化每一個(gè)字符的推導(dǎo)次數(shù)），用于構(gòu)造可接受集。
FMQ修正方法（FMQ error correction method，F(xiàn)ischer, Milton and Quiring）：不刪除不修改原輸入字符串，只通過(guò)添加字符的方式，繼續(xù)解析。但并不是所有的錯(cuò)誤都可以恢復(fù)。
插入可修正文法（insert-correctable grammars）：當(dāng)前輸入字符，總是在包含了任何非終結(jié)符的FIRST集中。即，插入合適的字符后，總能讓解析進(jìn)行下去。
非修正式錯(cuò)誤恢復(fù)（Non-Correcting Error Recovery）：不對(duì)輸入字符進(jìn)行任何修改，把出錯(cuò)位置后的字符串，當(dāng)做符合文法的字符串后綴來(lái)處理。缺點(diǎn)是無(wú)法形成一棵完整的解析樹(shù)。
內(nèi)容總結(jié)
錯(cuò)誤處理總共涉及三個(gè)層面：錯(cuò)誤檢測(cè)（Detection），錯(cuò)誤恢復(fù)（Recovery），錯(cuò)誤修正（Correction）。
不定向解析技術(shù)（Non-Directional Parsing）：處理錯(cuò)誤的能力較差，使用動(dòng)態(tài)規(guī)劃（dynamic programming）會(huì)有一些幫助。
有限狀態(tài)自動(dòng)機(jī)（Finite-State Automata）：具備正確前綴性質(zhì)（correct-pre?x property），還具有立即發(fā)現(xiàn)錯(cuò)誤的性質(zhì)（immediate error detection property）。
通用自頂向下解析（General Directional Top-Down Parsers）：廣度有限方法具備正確前綴性質(zhì)（correct-pre?x property），深度有限搜索不具備，因?yàn)楸仨毣厮菟锌赡懿拍芙Y(jié)束。
通用自底向上解析（General Directional Bottom-Up Parsers）：具備正確前綴性質(zhì)（correct-pre?x property）。
確定性自頂向下解析（Deterministic Top-Down Parsers）：具備正確前綴性質(zhì)（correct-pre?x property），但是由于空串規(guī)則（ε-rules）不能立即發(fā)現(xiàn)錯(cuò)誤。
確定性自底向上解析（Deterministic Bottom-Up Parsers）：LR(1)具備立即發(fā)現(xiàn)錯(cuò)誤的性質(zhì)（immediate error detection property），LALR(1)和SLR(1)不具備，它們只具備正確前綴性質(zhì)（correct-pre?x property）。GLR解析具備哪些性質(zhì)，依賴于底層使用的解析機(jī)制。
錯(cuò)誤恢復(fù)（Recovery）通常包含4種方法：
（1）區(qū)域錯(cuò)誤處理（regional error handling methods），使用一部分（區(qū)域）上下文來(lái)繼續(xù)解析
（2）局部錯(cuò)誤處理（local error handling methods），使用解析狀態(tài)和當(dāng)前輸入字符來(lái)繼續(xù)解析
（3）后綴方法（suf?x methods），不使用上下文，僅僅把出錯(cuò)后的輸入字符串看做原文法的后綴字符串，繼續(xù)解析。
（4）ad hoc methods，不成系統(tǒng)的一些方法，一般由解析器的作者來(lái)如何繼續(xù)解析。
前后移動(dòng)錯(cuò)誤恢復(fù)（backward/forward move error recovery method），是一種局部錯(cuò)誤處理方法（local error handling methods）
（1）壓縮階段（condensation phase），也稱為向后移動(dòng)（backward move）：棧頂加入什么狀態(tài)，當(dāng)前字符就能繼續(xù)歸約。
（2）修正階段（correction phase），也稱為向前移動(dòng)（forward move）：消耗掉輸入字符串的一些字符， 直到遇到下一個(gè)錯(cuò)誤。
可接受集恢復(fù)方法（acceptable-set error recovery），是一種局部錯(cuò)誤處理方法（local error handling methods），有兩種模式，
（1）懲罰模式（Panic Mode）：出現(xiàn)錯(cuò)誤的時(shí)候，開(kāi)始忽略下一個(gè)字符，直到出現(xiàn)接受集（acceptable-set）中的字符。
（2）FOLLOW集錯(cuò)誤恢復(fù)（FOLLOW-set error recovery）：出現(xiàn)錯(cuò)誤時(shí)，開(kāi)始忽略字符，直到下一個(gè)字符在當(dāng)前待歸約的非終結(jié)符的FOLLOW集中。
局部最小成本錯(cuò)誤恢復(fù)方法（locally least-cost error recovery）：根據(jù)計(jì)算插入，刪除，替換的成本，來(lái)修正錯(cuò)誤。
ad hoc methods：之所以稱為ad hoc，是因?yàn)樵撔拚椒o(wú)法自動(dòng)從文法得出。主要包括三種方法：
（1）錯(cuò)誤產(chǎn)生式（error productions）：通過(guò)對(duì)文法做出調(diào)整，增加可容忍錯(cuò)誤的產(chǎn)生式規(guī)則。
（2）空表插槽（empty table slots）：在表驅(qū)動(dòng)解析方法中，查表時(shí)如果沒(méi)有相關(guān)動(dòng)作，就調(diào)用特定的處理過(guò)程。
（3）錯(cuò)誤單詞（error tokens）：擴(kuò)展文法，增加表示錯(cuò)誤的單詞。
17. Practical Parser Writing and Usage
內(nèi)容總結(jié)
實(shí)際中使用的解析器，大多數(shù)是用來(lái)解析上下文無(wú)關(guān)文法，或者正則文法的。
所有已知的，上下文相關(guān)文法或短語(yǔ)結(jié)構(gòu)文法的解析器，時(shí)間復(fù)雜度都是指數(shù)級(jí)的。
在實(shí)踐中，唯一的可以達(dá)到線性時(shí)間復(fù)雜度的解析方法，就是使用確定性解析器（deterministic）。
在選擇解析器的時(shí)候，有以下幾個(gè)困難：
（1）自動(dòng)生成的確定性解析器，只能解析上下文無(wú)關(guān)文法的一個(gè)子集。
（2）雖然LR(1)和LALR(1)可以解析很多上下文無(wú)關(guān)文法，但是某些實(shí)際用到的文法仍然無(wú)法解析。
（3）雖然可以對(duì)文法進(jìn)行調(diào)整，使之可以在線性時(shí)間內(nèi)被解析出來(lái)，但是文法的轉(zhuǎn)換過(guò)程通常是無(wú)法自動(dòng)化的，并且轉(zhuǎn)換后的文法生成的解析樹(shù)與原文法會(huì)有不同。
（4）對(duì)于確定性解析器來(lái)說(shuō)，無(wú)法解析含有歧義的文法。
如果人們可以自行設(shè)計(jì)文法的話，那么問(wèn)題就簡(jiǎn)單多了，直接設(shè)計(jì)一個(gè)LL(1)文法，然后進(jìn)行遞歸下降解析。
這種解析器擁有線性時(shí)間復(fù)雜度，很好的錯(cuò)誤恢復(fù)機(jī)制，并且還允許嵌入語(yǔ)義動(dòng)作函數(shù)（semantic routines）。
因此，只有在解析別人設(shè)計(jì)的文法時(shí)，才有問(wèn)題。
通用解析器：
（1）Unger parser：具有指數(shù)時(shí)間復(fù)雜度，通過(guò)引入字符串表（substring table）可以降為多項(xiàng)式復(fù)雜度。多項(xiàng)式次數(shù)與產(chǎn)生式右側(cè)的最多非終結(jié)符個(gè)數(shù)有關(guān)。
（2）Earley parser：對(duì)于含有歧義的文法，具有立方時(shí)間復(fù)雜度，對(duì)于不含歧義的文法具有平方時(shí)間復(fù)雜度，它的確定性版本，具有線性時(shí)間復(fù)雜度。它不需要對(duì)原文法進(jìn)行修改，優(yōu)于GLR解析器。
（3）GLR parser：對(duì)于大部分有歧義的文法，GLR解析器可以用接近線性時(shí)間復(fù)雜度的方式解析，但是需要對(duì)文法進(jìn)行預(yù)處理。GLR解析器僅適合那種沒(méi)有確定性解析方案，且原文法較穩(wěn)定的場(chǎng)景。
即使通用解析算法的時(shí)間復(fù)雜度是線性的，比起確定性解析器的線性時(shí)間，也有一個(gè)不小的比例因子。
并且，確定性解析方法直到解析完成，解析樹(shù)都無(wú)法確定下來(lái)，因此語(yǔ)義動(dòng)作不得不等到解析完成后再觸發(fā)。
線性時(shí)間解析器（確定性解析器）：
（1）含歧義的文法無(wú)法在線性時(shí)間內(nèi)解析，但有一個(gè)例外，就是操作符優(yōu)先級(jí)文法（operator-precedence grammars）。只是它無(wú)法生成完成的解析樹(shù)，只能生成一個(gè)骨架（parse skeleton）。因此，它是實(shí)際使用中的最簡(jiǎn)單的解析方法。
（2）確定性解析器通常需要對(duì)文法進(jìn)行轉(zhuǎn)換，因此，原文法必須的穩(wěn)定不易變的，并且用戶可接受調(diào)整過(guò)后的解析樹(shù)。通常，文法轉(zhuǎn)換過(guò)程，通常無(wú)法自動(dòng)完成。
（3）常用的確定性解析器包括 strong-LL(1)解析器，和LALR(1)解析器，可以很方便的找到相關(guān)的解析器生成器（parser generator）。LL(1)通常會(huì)比LALR(1)對(duì)文法要求更高，因此需要對(duì)原文法進(jìn)行更多修改。LL(1)可以在產(chǎn)生式中遇到選擇（alternative）時(shí)，先執(zhí)行語(yǔ)義動(dòng)作，LALR(1)只有選擇執(zhí)行完后才能執(zhí)行語(yǔ)義動(dòng)作。LL(1)通常更簡(jiǎn)單，更易修改。如果LL(1)解析器采用遞歸下降方法實(shí)現(xiàn)，語(yǔ)義動(dòng)作可以像編程語(yǔ)言那樣，用命名的變量或?qū)傩员硎?，而LALR(1)這種表驅(qū)動(dòng)方法解析技術(shù)則很難做到這一點(diǎn)。在時(shí)間和空間復(fù)雜度方面，兩者差不多。
文法可以被解析器以兩種不同的方式執(zhí)行：解釋的方式，編譯的方式。
（1）解釋的方式：解析器源碼被編譯為一個(gè)文法解釋器（interpreter），用戶輸入文法和待解析的字符串，最終得到一棵解析樹(shù)，伴隨一些相關(guān)的語(yǔ)義動(dòng)作。
（2）編譯的方式：解析器生成器源碼被編譯為一個(gè)解析器生成器（parser generator），用戶輸入文法后，得到一個(gè)解析器或者一個(gè)解析表。生成的解析器接受輸入字符串，將得到一棵解析樹(shù)，伴隨一些相關(guān)的語(yǔ)義動(dòng)作，這種方式又被稱為編譯解析器（compiled parsers）。如果生成的是解析表，則還需要解析器作者提供一個(gè)驅(qū)動(dòng)器（driver），用來(lái)實(shí)現(xiàn)最終的解析，這種方式又被稱為表驅(qū)動(dòng)解析器（table-driven parsers）。
LL(1)解析器，通常有兩種方式實(shí)現(xiàn)：
（1）編譯解析器（compiled parser），采用遞歸下降解析，為每一個(gè)非終結(jié)符生成一個(gè)函數(shù)。
（2）表驅(qū)動(dòng)解析器（table-driven parsers），借助一個(gè)解析表和一個(gè)下推自動(dòng)機(jī)來(lái)實(shí)現(xiàn)。
第一種方式更常見(jiàn)。
幾乎所有的LR解析器是表驅(qū)動(dòng)的，借助一個(gè)解析表和下推自動(dòng)機(jī)實(shí)現(xiàn)。
編譯解析器（compiled parser）比表驅(qū)動(dòng)解析器（table-driven parsers）更快，并且語(yǔ)義動(dòng)作可以更方便的嵌入。
編程泛型，指的是考慮或解決問(wèn)題的一種思維定勢(shì)。
主要包括4種編程泛型：命令式，面向?qū)ο?，函?shù)式，邏輯式。
其他還有并行編程，和分布式計(jì)算。
盡管在原則上，任何編程泛型都有能力實(shí)現(xiàn)所有可編程的東西，但是某些場(chǎng)景下使用特定的編程泛型會(huì)更便利一些。
文法解釋器（interpreter）只不過(guò)是一段編譯過(guò)后的程序，因此用什么泛型實(shí)現(xiàn)都沒(méi)什么區(qū)別。
表驅(qū)動(dòng)解析器（table-driven parsers）需要不斷以循環(huán)的方式訪問(wèn)解析表，命令式是最合適的。
函數(shù)式編程雖然不太適合確定性的表驅(qū)動(dòng)的解析器，但是卻適合含回溯的遞歸下降解析器，一個(gè)例子是組合子解析（combinator parsing）。
組合子解析可以將每個(gè)非終結(jié)符的解析過(guò)程串聯(lián)起來(lái)，采用與文法相類似的寫(xiě)法描述解析過(guò)程。
邏輯式編程的優(yōu)勢(shì)是，內(nèi)置了深度優(yōu)先搜索算法。
其他可能用到解析技術(shù)的地方，有一下幾個(gè)：
（1）數(shù)據(jù)壓縮
（2）機(jī)器指令生成
（3）用與在邏輯式編程語(yǔ)言中實(shí)現(xiàn)推理過(guò)程（inference process）
