請(qǐng)務(wù)必首先查看第1部分、第2部分、第3部分和第4部分！

格式

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

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

Backus-Naur Form及其變體

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

為了說(shuō)明為什么這些變體是必要的，我們來(lái)展示一個(gè)BNF的例子：一個(gè)字符的描述。

< 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 >

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

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

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

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

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

Extended Backus-Naur Form

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

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

我們來(lái)看看如何在EBNF中編寫(xiě)前面的例子。

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 } ;

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

ABNF

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

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

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

PEG

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

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

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

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

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

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

PEG與CFG

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

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

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

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

dog ← 'dog' / 'doge'

PEG是否可以描述所有可以用CFG定義的語(yǔ)法，這是一個(gè)開(kāi)放的研究領(lǐng)域，但是對(duì)于所有的實(shí)際目的，它們都可以。

請(qǐng)繼續(xù)關(guān)注第6部分！

推薦閱讀：

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

開(kāi)發(fā)一個(gè)聊天機(jī)器人（Chatbot）應(yīng)用程序需要花費(fèi)多少錢(qián)？

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

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