在繼續(xù)之前，請(qǐng)務(wù)必首先查看第1部分、第2部分和第3部分！

語(yǔ)法

語(yǔ)法是用來描述語(yǔ)言的一套規(guī)則，因此研究規(guī)則的格式是很自然的。然而，典型語(yǔ)法中還有幾個(gè)元素可以引起進(jìn)一步的關(guān)注。其中一些原因是因?yàn)檎Z(yǔ)法也可以用來定義其他職責(zé)或者執(zhí)行一些代碼。

典型的語(yǔ)法問題

首先，我們將討論在解析中可能遇到的一些特殊規(guī)則或問題。

缺少的Tokens

如果你閱讀語(yǔ)法，你可能會(huì)遇到許多其中只定義了幾個(gè)tokens的東西，而不是全部。就像這個(gè)語(yǔ)法一樣：

NAME     : [a-zA-Z]+
greeting : "Hello" NAME

token “你好”沒有定義，但既然你知道一個(gè)解析器處理tokens，你可能會(huì)問自己這怎么可能。答案是有些工具會(huì)為您生成字符串文字的對(duì)應(yīng)token，以節(jié)省您一些時(shí)間。

請(qǐng)注意，這可能只在某些條件下才有可能。例如，使用ANTLR，如果您定義了單獨(dú)的詞法分析器和分析器語(yǔ)法，則必須自己定義所有的tokens。

左遞歸規(guī)則

在解析器的上下文中，一個(gè)重要的特性是支持左遞歸規(guī)則。這意味著一條規(guī)則從對(duì)自身的引用開始。有時(shí)候，這個(gè)參考也可能是間接的；也就是說，它可能出現(xiàn)在第一個(gè)引用的另一個(gè)規(guī)則中。

考慮例如算術(shù)運(yùn)算。一個(gè)加法可以被描述為由加號(hào)（+）分隔的兩個(gè)表達(dá)式，但是加法的操作數(shù)可以是其他的加法。

addition       : expression '+' expression
multiplication : expression '*' expression
// an expression could be an addition or a multiplication or a number
expression     : multiplication | addition | [0-9]+

在這個(gè)例子中，表達(dá)式通過規(guī)則的加法和乘法包含對(duì)自身的間接引用。

此描述也匹配多個(gè)添加如5 + 4 + 3。這是因?yàn)樗梢越忉尀楸磉_(dá)式（5）（'+'）表達(dá)式（4 + 3）（規(guī)則加法：第一個(gè)表達(dá)式對(duì)應(yīng)于選項(xiàng)[0 -9] +，第二個(gè)是另外一個(gè)）。然后4 + 3本身可以分為兩個(gè)部分：表達(dá)式（4）（'+'）表達(dá)式（3）（規(guī)則加法：第一個(gè)和第二個(gè)表達(dá)式都對(duì)應(yīng)于選項(xiàng)[0-9] +）。

該問題是左遞歸規(guī)則可能不能用于一些解析器生成器。另一種選擇是長(zhǎng)鏈表達(dá)，也關(guān)心運(yùn)營(yíng)商的優(yōu)先級(jí)。不支持這些規(guī)則的解析器的典型語(yǔ)法看起來與此類似：

expression     : addition
addition       : multiplication ('+' multiplication)*
multiplication : atom ('*' atom)*
atom           : [0-9]+

正如你所看到的，表達(dá)式是按照優(yōu)先順序的相反順序來定義的。因此，解析器會(huì)將低優(yōu)先級(jí)的表達(dá)式放在最低級(jí)別的表達(dá)式中；因此，他們將首先執(zhí)行。

一些解析器生成器支持直接的左遞歸規(guī)則，但不支持間接的。請(qǐng)注意，通常，問題是不支持左遞歸規(guī)則的解析算法。因此，解析器生成器可以將以正確的方式寫成左遞歸的規(guī)則轉(zhuǎn)換成使其與其算法一起工作。在這個(gè)意義上，左遞歸支持可能是（非常有用的）語(yǔ)法糖。

左遞歸規(guī)則是如何轉(zhuǎn)換的

規(guī)則轉(zhuǎn)換的具體方式因語(yǔ)法分析器的不同而不同， 然而，邏輯保持不變。表達(dá)式分為兩組：一組有運(yùn)算符和兩個(gè)操作數(shù)和原子。在我們的例子中，唯一的原子表達(dá)式是一個(gè)數(shù)字（[0-9] +），但也可以是括號(hào)（（5 + 4））之間的表達(dá)式。這是因?yàn)樵跀?shù)學(xué)中，括號(hào)被用來增加表達(dá)的優(yōu)先級(jí)。

一旦擁有了這兩個(gè)組，就可以維護(hù)第二組成員的順序，并顛倒第一組成員的順序。原因是人類以先到先得的原則推理：按優(yōu)先順序編寫表達(dá)式比較容易。

然而，解析的最終形式是一棵樹，它運(yùn)行在一個(gè)不同的原理上：你開始在樹葉上工作，并在這個(gè)過程結(jié)束時(shí)，根節(jié)點(diǎn)包含最終結(jié)果——這意味著在解析樹的原子表達(dá)式在底部，而帶有運(yùn)算符的那些則以相反的順序出現(xiàn)。

謂語(yǔ)

謂語(yǔ)（有時(shí)稱為句法或語(yǔ)義謂詞）是特殊的規(guī)則，只有在滿足某個(gè)條件的情況下才能匹配。該條件是用編寫語(yǔ)法的工具所支持的編程語(yǔ)言中的代碼定義的。

它們的優(yōu)點(diǎn)是它們?cè)试S某種形式的上下文相關(guān)的解析，這有時(shí)是不可避免的匹配某些元素。例如，它們可以用來確定定義一個(gè)軟關(guān)鍵字的字符序列是否被用在關(guān)鍵字的位置（即前一個(gè)關(guān)鍵字后面可以跟著一個(gè)關(guān)鍵字），還是一個(gè)簡(jiǎn)單的標(biāo)識(shí)符。

缺點(diǎn)是它們減慢了解析速度，并且使語(yǔ)法依賴于所述編程語(yǔ)言。那是因?yàn)闂l件是用編程語(yǔ)言表達(dá)的，必須檢查。

嵌入式操作

嵌入式操作辨認(rèn)每次匹配規(guī)則時(shí)執(zhí)行的代碼。由于規(guī)則被代碼所包圍，它們有明顯的缺點(diǎn)，使得語(yǔ)法難以閱讀。此外，就像謂語(yǔ)一樣，它們打破了描述語(yǔ)言的語(yǔ)法和操縱解析結(jié)果的代碼之間的分離。

不太復(fù)雜的解析生成器經(jīng)常使用操作作為在節(jié)點(diǎn)匹配時(shí)輕松執(zhí)行某些代碼的唯一方法。使用這些解析器世代，唯一的選擇是遍歷樹并自己執(zhí)行正確的代碼。更高級(jí)的工具反而允許使用訪問者模式（）在需要的時(shí)候執(zhí)行任意代碼，并且管理樹的遍歷。

它們也可以用來添加特定的tokens或更改生成的樹。雖然不美觀，但這可能是處理像C這樣的復(fù)雜語(yǔ)言或像Python中的空白這樣的特定問題的唯一實(shí)用方法。

請(qǐng)繼續(xù)關(guān)注第5部分，我們將主要討論語(yǔ)法格式。

推薦閱讀：

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

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

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

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