欧美视频免费网站,成人福利在线播放,91视频app福

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

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

概述：語法有兩種主要格式：BNF（及其變體）和PEG。本章節(jié)旨在讓大家了解這些不同的格式以及何時應(yīng)該使用它們。

相關(guān)鏈接：

格式

語法有兩種主要格式：BNF（及其變體）和PEG。許多工具都實(shí)現(xiàn)了這些理想格式的變體。一些工具完全使用自定義格式。頻繁的自定義格式由三部分語法組成：結(jié)合自定義代碼的選項(xiàng)，其次是詞法分析部分，最后是解析器部分。

鑒于類似BNF的格式通常是上下文無關(guān)語法的基礎(chǔ)，您還可以看到它以CFG格式標(biāo)識。

Backus-Naur Form及其變體

Backus-Naur Form（BNF）是最成功的格式，甚至是PEG的基礎(chǔ)。但是，這個過程很簡單，因此它的基本形式并不常用。我們通常使用更強(qiáng)大的變體。

為了說明為什么這些變體是必要的，我們來展示一個BNF的例子：一個字符的描述。

< letter >    ::= "a" | "b" | "c" | "d" | "e" | "f" | "g" | "h" | "i" | "j" | "k" | "l" | "m" | "n" | "o" | "p" | "q" | "r" | "s" | "t" | "u" | "v" | "w" | "x" | "y" | "z"
< digit >     ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"
< character > ::= < letter > | < digit >

符號< letter >可以在英文字母的任何字母中轉(zhuǎn)換，盡管在我們的例子中只有小寫字母是有效的。類似的過程發(fā)生在< digit >，它可以指示任何替代數(shù)字。第一個問題是你必須單獨(dú)列出所有的選擇；像使用正則表達(dá)式一樣，不能使用字符類。這很煩人，但通常是可以管理的，除非你必須列出所有的Unicode字符。

一個更難的問題是，沒有簡單的方法來表示可選的元素或重復(fù)。所以，如果你想這樣做，你必須依靠布爾邏輯（boolean logic）和替代(|)符號。

< text >      ::= < character > | < text > < character >

該規(guī)則規(guī)定< text >可以由一個字符或一個短的< text >和一個< character >組成。這將是dog的分析樹：

BNF還有許多其他限制：在語法中使用空字符串或格式使用的符號（即:: =）使得復(fù)雜，它有一個詳細(xì)的語法（即你必須在< and >之間包含終端）等等。

Extended Backus-Naur Form

為了解決這些限制，Niklaus Wirth創(chuàng)建了Extended Backus-Naur Form(EBNF)，其中包含了他自己的Wirth語法表示法的一些概念。

EBNF是最常用的當(dāng)代解析工具，盡管工具可能偏離標(biāo)準(zhǔn)符號。EBNF有一個更清潔的符號，并采用更多的運(yùn)算符來處理連接或可選的元素。

我們來看看如何在EBNF中編寫前面的例子。

letter    = "a" | "b" | "c" | "d" | "e" | "f" | "g" | "h" | "i" | "j" | "k" | "l" | "m" | "n" | "o" | "p" | "q" | "r" | "s" | "t" | "u" | "v" | "w" | "x" | "y" | "z" ;
digit     = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ;
character = letter | digit ;
text      = character , { character } ;

文字符號在連接運(yùn)算符（，）和可選符號（{..}）的幫助下更容易描述。得到的分析樹也會更簡單。標(biāo)準(zhǔn)的EBNF仍然存在一些問題，如不熟悉的語法。為了克服這個問題，大多數(shù)解析工具都采用了受正則表達(dá)式啟發(fā)的語法，并且還支持像字符類這樣的附加元素。

ABNF

Augmented BNF (ABNF)是BNF的另一種變體，主要用于描述雙向通信協(xié)議，并由IETF和幾個文檔（參見和更新）進(jìn)行形式化。

ABNF可以和EBNF一樣有效，但是有一些怪癖限制了它在互聯(lián)網(wǎng)協(xié)議之外的采用。例如，直到最近，標(biāo)準(zhǔn)規(guī)定字符串以不區(qū)分大小寫的方式進(jìn)行匹配，這在許多編程語言中匹配標(biāo)識符是個問題。

ABNF與EBNF有不同的語法；例如，替代運(yùn)算符是斜杠（/），有時它更好。例如，不需要連接運(yùn)算符。它還比標(biāo)準(zhǔn)的EBNF有更多的東西。例如，它允許您定義數(shù)字范圍，如％x30-39，相當(dāng)于[0-9]。這也被設(shè)計(jì)師自己用來包含標(biāo)準(zhǔn)的字符類，比如最終用戶可以使用的基本規(guī)則。這種規(guī)則的一個例子是ALPHA，相當(dāng)于[a-zA-Z]。

PEG

解析表達(dá)語法（PEG）是。從技術(shù)上講，它來源于一種稱為自頂向下解析語言（Top-Down Parsing Language，TDPL）的舊式正式語法。然而，描述它的一個簡單的方法是在現(xiàn)實(shí)世界中的EBNF。

實(shí)際上，它看起來和EBNF相似，但也直接支持廣泛使用的東西，比如字符范圍（字符類）——雖然它也有一些實(shí)際上并不那么實(shí)際的差異，比如使用更正式的箭頭符號（←）更常見的等號（=）。前面的例子可以用PEG來寫。

letter    ← [a-z]
digit     ← [0-9]
character ← letter / digit
text      ← character+

正如你所看到的，這是程序員寫的最明顯的方式：用字符類和正則表達(dá)式運(yùn)算符。唯一的異常是替代運(yùn)算符（/）和箭頭字符，事實(shí)上，PEG的許多實(shí)現(xiàn)使用“equals”字符。

實(shí)用的方法是PEG形式化的基礎(chǔ)：創(chuàng)建它是為了描述更自然的編程語言。這是因?yàn)樯舷挛臒o關(guān)文法起源于描述自然語言的工作。從理論上講，CFG是一個生成語法，而PEG是一個分析語法。

第一個應(yīng)該是用語法描述的語言只生成有效句子的一種配方。它不必與解析算法相關(guān)。相反，第二種類型直接定義了該語言的解析器的結(jié)構(gòu)和語義。

PEG與CFG

這種理論差異的實(shí)際意義是有限的：PEG與packrat算法更密切相關(guān)，但基本上這是它。例如，一般來說，PEG（packrat）不允許左遞歸。雖然可以修改算法本身來支持它，但是這消除了線性時間解析屬性。另外，PEG解析器通常是無掃描器的解析器。

PEG和CFG之間最重要的區(qū)別可能是PEG的選擇順序是有意義的，而CFG則不是。如果有許多可能的有效方法來解析輸入，則CFG將不明確，因此將返回錯誤。通常錯誤的意思是，一些采用CFG的解析器可以處理模糊的語法；例如，向開發(fā)者提供所有可能的有效結(jié)果，并讓他們把它整理出來。相反，由于第一個適用的選擇將被選擇，PEG完全消除了歧義。因此，PEG永遠(yuǎn)不會含糊不清。

這種方法的缺點(diǎn)是，在列出可能的備選方案時必須更加小心，否則可能會產(chǎn)生意想不到的后果。也就是說，有些選擇永遠(yuǎn)無法匹配。

在下面的例子中，doge永遠(yuǎn)不會被匹配。由于dog先來，它每次都會被挑選。