亚洲日韩精品国产,69福利网,成人午夜福利

NLP|自然語(yǔ)言處理-語(yǔ)法解析指南：算法和技術(shù)（第6部分）

原創(chuàng)|使用教程|編輯：鄭恭琳|2018-01-04 13:18:51.000|閱讀 785 次

概述：這篇文章的目標(biāo)是教你何時(shí)使用哪種解析算法，以及哪些解析算法可能需要刷新。

相關(guān)鏈接：

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

解析算法

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

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

概述

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

兩種策略

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

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

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

示例解析樹（）

同樣的樹會(huì)由一個(gè)自頂向下和一個(gè)自底向上的解析器以不同的順序生成。在下面的圖片中，數(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é)符號(hào)。使用BNF術(shù)語(yǔ)，它指示如何使用__expression__中出現(xiàn)的元素來獲得< symbol >。這兩種可能性是最左邊的推導(dǎo)和最右邊的推導(dǎo)。第一個(gè)表示規(guī)則從左到右應(yīng)用，而第二個(gè)表示相反。

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

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

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

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

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

共同的元素

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

前瞻性和回溯性

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

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

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

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

圖表解析器

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

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

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

自動(dòng)機(jī)

在討論解析算法之前，我們想談?wù)勗诮馕鏊惴ㄖ惺褂米詣?dòng)機(jī)。是一個(gè)抽象機(jī)器族群，其中有著名的圖靈機(jī)（Turing machine）。

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

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

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

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

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

他們用于幾個(gè)原因：