本節書摘來自華章出版社《antlr 4權威指南 》一書中的第2章,第2.3節,[美] 特恩斯·帕爾(terence parr) 著張 博 譯,更多章節内容可以通路雲栖社群“華章計算機”公衆号檢視。
歧義性語句是指存在不止一種語義的語句。換句話說,歧義性語句中的單詞序列能夠比對多種文法結構。本節的标題“你再也不能往核反應堆多加水了”就是我在幾年前的《周六夜現場》中看到的一個有歧義的句子。這句話讓人不确定,是已經無法往核反應堆多加水了,還是不應該往核反應堆多加水。

出現在自然語言中的歧義句會顯得非常滑稽,但是出現在基于計算機的語言類應用程式中的歧義就會帶來很多問題。為了解釋或者翻譯一個詞組,程式必須能夠唯一地辨識出它的準确含義。這意味着,我們必須提供沒有歧義的文法,使得antlr生成的文法分析器能夠以單一方式比對每個輸入詞組。
迄今為止,我們還沒有深入了解antlr文法的細節,不過,接下來我們将通過一些有歧義的文法來闡明歧義性的含義。你可以在以後建構文法并遇到歧義問題的時候再來回顧本節。
比如一些文法的歧義是非常明顯的:
大多數情況下,歧義的表現更為微妙。在下面的文法中,stat規則包含兩個備選分支,二者都可以比對一個函數調用語句。
下面的圖顯示了stat規則對輸入文本“f();”的兩種不同的解釋:
左邊的文法分析樹展示的是f()比對expr規則的情況,右邊的文法分析樹展示的是f()比對stat規則的第二個備選分支的情況。由于大多數語言的設計者都傾向于将文法設計成無歧義的,一個歧義性文法通常被認為是程式設計上的bug。我們需要重新組織文法,使得對于每個輸入的詞組,文法分析器都能夠選擇唯一比對的備選分支。如果文法分析器檢測到該詞組存在歧義,它就必須在多個備選分支中做出選擇。antlr解決歧義問題的方法是:選擇所有比對的備選分支中的第一條。在上面的例子中,antlr将會選擇左邊的文法分析樹作為對輸入文本“f();”的語義解釋。
歧義問題在詞法分析器和文法分析器中都會發生,antlr的解決方案使得對規則的解析能夠正常進行。在詞法分析器中,antlr解決歧義問題的方法是:比對在文法定義中最靠前的那條詞法規則。我們通過程式設計語言中常見的一種歧義——關鍵字和辨別符規則的沖突——來說明這套機制是如何工作的。關鍵字begin同時也是一個辨別符,至少從詞法意義上來說是這樣的。是以詞法分析器可以使用以下任一詞法規則來比對字元序列“b-e-g-i-n”:
有關詞法分析中歧義性的更多資訊,請參閱5.5節中“比對辨別符”部分。要注意的是,詞法分析器會比對可能的最長字元串來生成一個詞法符号,這意味着,輸入文本beginner隻會比對上例中的id這條詞法規則。antlr詞法分析器不會把它比對為關鍵字begin後跟着辨別符ner。
有時候,一門語言的文法本身就存在歧義,無論如何修改文法也不能改變這一點。例如,常見的數學表達式1 + 2*3可以用兩種方式解釋,一種是自左向右地處理(smalltalk就是這麼做的),另外一種是像絕大多數程式設計語言一樣,按照優先級來處理。我們将在5.4節中學習如何隐式地指定表達式中的運算符優先級。
經典的c語言向我們展示了另外一種歧義,我們可以通過包含辨別符定義的上下文資訊來解決這樣的歧義問題。例如,對于代碼片段“i*j;”,從句法角度看,它像是一個表達式,但是實際上它的實際含義,或者說語義,依賴于i是一個類型還是一個變量。如果i是一個類型的名字,那麼這段代碼就不是一個表達式,而是一個指向類型i的指針變量j的聲明。我們将在第11章中解決這樣的歧義問題。
文法分析器本身僅僅驗證輸入語句的合法性并建立一棵文法分析樹。這是一項非常重要的工作,接下來,我們将了解一個語言類應用程式如何使用文法分析樹來對輸入文本進行語義分析和翻譯。