第5章 基于JavaCC的解析器的描述

本章將介紹基于JavaCC的解析器的描述方法。

5.1 基于EBNF語法的描述

本節我們將一邊制作C?語言的解析器，一邊對使用JavaCC制作解析器的方法進行介紹。

本章的目的

首先，讓我們來回顧一下解析器的作用。

編譯器中解析器的作用是利用掃描器生成的token序列來生成語法樹。例如，生成如圖5-1所示的語法樹。

圖5-1 語法樹的例子

如圖5-1所示，字符串和"（"、"）"等對應代碼中的1個單詞。換言之，就是能夠作為掃描器中的1個token被識別。

另一方面，“語句”和“函數調用”則對應多個單詞，即對應多個token。但這樣的語法掃描器是無法識別的。

將上述這樣由多個token構成的語法單位識別出來，正是解析器最重要的工作。在token序列中，只要知道了“這個單詞列是語句”“這是函數調用”等，接下來就只需根據token信息來構建語法樹即可，并不是什么太難的工作。

基于JavaCC的語法描述

下面就來講一下使用JavaCC從token序列中識別出“語句”“表達式”“函數調用”等語法單位的方法。

只要為JavaCC描述“語句”“表達式”“函數調用”這樣的語法單位各自是由怎樣的token序列構成的，就能夠對該語法進行分析（parse）。

例如，讓我們以最簡單的賦值表達式為例來思考一下。最簡單的賦值表達式可以描述為“符號”“"="”“表達式”的排列。換言之，如果存在“符號”“"="”“表達式”這樣的排列，那就是賦值表達式。這個規則在JavaCC中表示成下面這樣。

assign（　）:
{}
{
    <IDENTIFIER> "=" expr（?。?
}

assign（?。x值表達式，<IDENTIFIER>對應token標識符，"="對應"="token, expr（　）對應表達式。assign（?。┖蚭xpr（　）是筆者隨便取的名字，并不是說賦值表達式就必須是assgin（　），表達式必須是expr（?。?。

像<IDENTIFIER>這樣已經在掃描器中定義過的token，在描述解析器時可以直接使用。其他的如"="這樣的固定字符串因為同樣可以表示token，所以也能在規則中使用。

另外，表達式expr（　）自身也是由多個token構成的。這樣的情況下需要進一步對expr（　）的規則進行描述。夾雜著中文來寫的話大致如下所示。

expr（?。?
{}
{
          expr（?。?+" expr（　）
      或   expr（　）"-" expr（　）
      或   expr（?。?＊" expr（?。?
          …
          …

像這樣寫好所有語法單位的規則之后，基于JavaCC的解析器的描述也就完成了。大家應該有一個大致的印象了吧。

終端符和非終端符

這里請記住1個術語。JavaCC中將剛才的“語句”“函數調用”“表達式”等非token的語法單位稱為非終端符（nonterminal symbol），并將非終端符像Java的函數調用一樣在后面加上括號寫成stmt（?。┗騟xpr（?。?。

既然有“非”終端符，自然也有終端符。終端符（terminal symbol）可以歸納為token。使用在掃描器中定義的名稱，可以寫成<IDENTIFIER>或<LONG>。并且JavaCC中除了掃描器中定義的token以外，"="、"+"、"=="這樣的字符串字面量也可以作為終端符來使用（表5-1）。

表5-1 終端符和非終端符

在講解token時我們提到了“token是單詞的字面表現和含義的組合”，這里的終端符和非終端符中的“符”可以說蘊含了相同的意思。

也就是說，這里的“符”也兼具字面表現和含義兩重功能。舉例來說，賦值表達式這樣的非終端符就既有i=1這樣的字面表現，又有“將整數1賦值給變量i”這樣的含義。字面表現和含義兩者的組合才能稱為“符”。

順便提一下，至于為什么稱為終端和非終端，是因為在畫語法樹的圖時，終端符位于樹的枝干的末端（終端）。非終端符由于是由其他符號的列組成的，因此一定位于分叉處，而非樹的末端。

JavaCC的EBNF表示法

下面具體地說一下JavaCC中語法規則的描述方法。

JavaCC使用名為EBNF（Extended Backus-Naur Form）的表示法來描述語法規則。EBNF和描述掃描器時使用的正則表達式有些相似，但比正則表達式所能描述的語法范圍更廣。

首先，表5-2中羅列了JavaCC的解析器生成器所使用的EBNF表示法。

表5-2 JavaCC的EBNF表示法

我們已經講過了終端符和非終端符，下面我們從第3項的“連接”開始來看一下。

連接

連接是指特定符號相連續的模式，比如首先是符號A，接著是符號B，再接著是符號C……

例如C語言（C?）的continue語句是保留字continue和分號的排列。反過來說，如果保留字continue之后接著分號，就說明這是continue的語句。JavaCC中將該規則寫成如下形式。

<CONTINUE> "; "

<CONTINUE>是表示保留字continue的終端符，"; "是表示字符自身的終端符。像這樣，JavaCC中通過簡單地并列符號來表示連接。

表示連接的符號可以是終端符也可以是非終端符，當然兩者混用也是可以的。

重復0次或多次

接著我們來看一下如何描述將符號重復0次或多次。重復是指相同的符號X并排出現多次的模式。

例如，C語言（C?）的代碼塊中可以記載0個或多個語句的排列，我們來試著描述一下。下面的寫法就能表示0個或多個語句（stmt:statement）排列。

（stmt（?。?

和正則表達式相同，＊是表示重復0次或多次的特殊字符。并且此處stmt（?。﹥蓚鹊睦ㄌ柌荒苁÷?。

再來看一個例子。函數的參數是由逗號分隔的表達式（expr:expression）排列而成的。換種說法就是expr之后排列著0個或多個逗號和expr的組合。這樣的規則在JavaCC中寫成如下形式。

expr（?。?, " expr（?。?

上述表述中，＊的作用域是與其緊挨著的左側括號中的內容，也就是說，作用對象是逗號和expr這兩者。因此上述規則能夠表現下面這樣的符號列。

expr（?。?
expr（　）", " expr（?。?
expr（?。?, " expr（?。?, " expr（?。?
expr（?。?, " expr（?。?, " expr（?。?, " expr（?。?
              …
              …

在編程語言的語法中，“期間○○重復多次”是非常常見的，因此請將剛才的寫法作為常用的語法描述記憶下來。

重復1次或多次

剛才我們看了重復0次或多次，JavaCC同樣可以表示重復1次或多次。和正則表達式一樣，重復1次或多次也使用+寫成如下形式。

（stmt（　））+

上述代碼描述了非終端符stmt（?。┲貜?次或多次。如果stmt（?。┦钦Z句的話，（stmt（　））+就是1個或多個語句的排列。

選擇

接著是符號的選擇（alternative）。選擇是指在多個選項中選擇1個的規則，比如選擇符號A或者符號B。

例如C?的類型有void、char、unsigned char等，可以寫成如下形式。

<VOID> | <CHAR> | <UNSIGNED> <CHAR> | ……

即<VOID>或<CHAR>或<UNSIGNED><CHAR>或……的意思。

可以省略

某些模式可能出現0次或1次，即可以省略。表示這樣的模式時使用[]。

以變量的定義為例。定義變量時可以設置初始值，但如果不設置的話也沒有問題。也就是說，初始值的記載是可以省略的。這樣的情況下，在JavaCC中可以寫成如下形式。

storage（　）typeref（?。﹏ame（?。"=" expr（?。 "; "

5.2 語法的二義性和token的超前掃描

本節將介紹使用JavaCC進行語法分析時所遇到的各類問題，以及其解決方法之一——token的超前掃描。

語法的二義性

事實上，JavaCC并非能夠分析所有用上一節敘述的方法（EBNF）所描述的語法。原因在于用EBNF描述的語法本質上存在具有二義性的情況。

舉一個有名的例子，讓我們試著考慮下C語言中if語句的語法。C語言中的if語句用JavaCC的EBNF可以如下這樣描述。

"if" "（" expr（?。?）" stmt（?。"else" stmt（?。

另一方面，作為符合上述規則的具體代碼，我們來看一下下面的例子。

if（cond1）
    if（cond2）
        f（?。?
    else
        g（?。?

讓我們根據剛才的規則試著分析下這段代碼。

乍看之下會覺得第2個if和else是成對的，這一整體位于最初的if條件之下。加上括號后的代碼如下所示。

if（cond1）{
    if（cond2）{
        f（　）;
    } else {
        g（?。?
    }
}

但實際上，如果不依賴直覺，僅依據剛才的規則仔細思考一下，下面這樣的解釋也是可能的。

if（cond1）{
    if（cond2）{
        f（?。?
        }
} else {
    g（?。?
}

也就是說，對于1份具體的代碼，可以如圖5-2這樣生成2棵語法樹。像這樣對于單個輸入可能有多種解釋時，這樣的語法就可以說存在二義性。

圖5-2 對應兩種解釋的語法樹

順便說一下，C語言中的if語句的規則存在二義性的問題是比較有名的，俗稱空懸else（dangling else）。

JavaCC的局限性

剛才的空懸else問題，其語法在本質上就存在二義性。除此之外，也存在因為JavaCC本身的局限性而無法正確解析程序的情況。例如像下面這樣描述語法時就會發生這種問題。

type（　）: {}
{
      <SIGNED> <CHAR>       // 選項1
    | <SIGNED> <SHORT>      // 選項2
    | <SIGNED> <INT>        // 選項3
    | <SIGNED> <LONG>       // 選項4
      ……

事實上，JavaCC在遇到用“|”分隔的選項時，在僅讀取了1個token的時刻就會對選項進行判斷，確切的動作如下所示。

1．讀取1個token

2．按照書寫順序依次查找由上述token開頭的選項

3．找到的話就選用該選項

也就是說，根據上述規則，JavaCC在讀取了<SIGNED>token時就已經選擇了<SIGNED><CHAR>，即選項1。因此即便寫了選項2和選項3，也是完全沒有意義的。這個問題稱為JavaCC的選擇沖突（choice conflict）。

提取左側共通部分

值得慶幸的是，當你寫了會發生選擇沖突的規則的情況下，若用JavaCC處理該語法描述文件，就會給出如下警告消息。因此如果是無法分析的語法，馬上就能知道。

$ javacc Parser.jj
Java Compiler Compiler Version 4.0（Parser Generator）
（type "javacc" with no arguments for help）
Reading from file Parser.jj . . .
Warning: Choice conflict involving two expansions at
          line 642, column 8 and line 643, column 7 respectively.
          A common prefix is: "unsigned"
          Consider using a lookahead of 2 for earlier expansion.
Parser generated with 0 errors and 1 warnings.

像這樣，消息中如果出現了Choice conflict字眼，就說明發生了選擇沖突。

解決上述問題的方法有兩個，其中之一就是將選項左側共通的部分提取出來。以剛才的規則為例，修改為如下這樣即可。

type（　）: {}
{
      <SIGNED>（<CHAR> | <SHORT> | <INT> | <LONG>）
      ……

這樣就不會發生選擇沖突了。

當遇到JavaCC的上述局限性時，應首先考慮是否可以用提取共通部分的方法來處理。但還是存在使用此方法仍然無法描述的規則，以及提取共通部分的處理非常復雜的情況，這樣的情況下就可以通過接下來要講的“token的超前掃描”來解決。

token的超前掃描

之前提到了JavaCC在遇到選項時僅根據讀取的1個token來判斷選擇哪個選項。事實上這只是因為JavaCC默認僅根據讀取的1個token進行判斷。只要明確指定，JavaCC可以在讀取更多的token后再決定選擇哪個選項。這個功能就稱為token的超前掃描（lookahead）。

剛才列舉的語法規則也能夠用token的超前掃描進行分析，為此要將規則寫成如下形式。

type（?。? {}
{
      LOOKAHEAD（2）<SIGNED> <CHAR>       // 選項1
    | LOOKAHEAD（2）<SIGNED> <SHORT>      // 選項2
    | LOOKAHEAD（2）<SIGNED> <INT>        // 選項3
    | <SIGNED> <LONG>                     // 選項4
      以下省略

添加的LOOKAHEAD（2）是關鍵。LOOKAHEAD（2）表示的意思為“讀取2個token后，如果讀取的token和該選項相符合，則選擇該選項”。也就是說，讀取2個token，如果它們是<SIGNED>和<CHAR>的話，就選用選項1。同樣，第2個選項的意思是讀取2個token，如果它們是<SIGNED>和<SHORT>的話，就選用選項2。

需要超前掃描的token個數（上述例子中為2）是通過“共通部分的token數+1”這樣的算式計算得到的。例如，上述規則中選項之間的共通部分為<SIGNED>，只有1個，因此需要超前掃描的token個數為在此基礎上再加1，即2。

為什么這樣能夠解決問題呢？因為只要讀取了比共通部分的token數多1個的token，就一定能讀到非共通部分的token，也就是說，能夠讀到各選項各自特有的部分。經過了這樣的確認后再進行選擇就不會有問題了。

最后的選項（選項4）不需要使用LOOKAHEAD。這是因為LOOKAHEAD是在還剩下多個選項時，為了延遲決定選擇哪個選項而使用的功能。

正如之前所講的那樣，JavaCC會優先選用先描述的選項，因此，當到達最后的選項即意味著其他的選項都已經被丟棄，只剩下這最后1個選項了。在只剩下1個選項時，即便推遲選擇也是沒有意義的。如果和任何一個選項都不匹配的話，那只能是代碼存在語法錯誤了。

最后，無法獲知“共通部分的token數”的情況也是存在的。這樣的例子以及解決方案將在稍后介紹“更靈活的超前掃描”這一部分時進行討論。

可以省略的規則和沖突

除“選擇”以外，選擇沖突在“可以省略”或“重復0次或多次”中也可能發生。

可以省略的規則中，會發生“是省略還是不省略”的沖突，而非“選擇選項1還是選項2”的沖突。之前提到的空懸else就是一個具體的例子。空懸else的問題在于內側的if語句的else部分是否省略（圖5-3）。如果內測的if語句的else部分沒有省略，則else部分屬于內側的if語句，如果省略的話則屬于外側的if語句。

圖5-3 空懸else問題和沖突

空懸else最直觀的判斷方法是“else屬于最內側的if”，因此試著使用LOOKAHEAD來進行判斷。首先，未使用LOOKAHEAD進行判斷的規則描述如下所示。

if_stmt（　）: {}
{
    <IF> "（" expr（?。?）" stmt（?。<ELSE> stmt（　）]
}

使用LOOKAHEAD來避免沖突發生的規則如下所示。

if_stmt（?。? {}
{
    <IF> "（" expr（　）"）" stmt（?。LOOKAEHAD（1）<ELSE> stmt（　）]
}

如你所見，判斷方法本身非常簡單。通過添加LOOKAHEAD（1），就可以指定“讀取1個token后，如果該token符合規則（即如果是<ELSE>）則不省略<ELSE> stmt（?。薄＿@樣就能明確else始終屬于最內側的if語句，空懸else的問題就可以解決了。

重復和沖突

重復的情況下會發生“是作為重復的一部分讀入還是跳出重復”這樣的選擇沖突。

來看一個具體的例子，如下所示為C?中表示函數形參的聲明規則。

param_decls（　）: {}
{
    type（?。?, " type（?。?[", " "..."]
}

這個規則中，表示可變長參數的", " "..."不會被解析。原因大家應該知道的吧。

根據上述規則，在讀取type（?。┖笥肿x到", "時，本來可能是", " type（?。┮部赡苁?, " "..."的，但JavaCC默認向前只讀取1個token，因此在讀到", "時就必須判斷是繼續重復還是跳出重復。并且恰巧", "和（", " type（?。┑拈_頭一致，所以JavaCC會一直判斷為重復（", " type（?。?，而規則", " "..."則完全不會被用到。實際上如果程序中出現", ""..."，會因為不符合規則", " type（　）而判定為語法錯誤。

要解決上述問題，可以如下添加LOOKAHEAD。

param_decls（　）: {}
{
    type（?。↙OOKAHEAD（2）", " type（?。?[", " "..."]
}

這樣JavaCC在每次判斷該重復時就會在讀取2個token后再判斷是否繼續重復，因此在輸入了", " "..."后就會因為檢測到和", " type（?。┎黄ヅ涠觯?, " type（　））＊的重復。

更靈活的超前掃描

關于token的超前掃描，JavaCC中還提供了更為靈活的方法。之前提到的LOOKAHEAD可以指定“恰好讀取了幾個token”，除此之外還可以指定“讀取符合這個規則的所有token”。

讓我們來看一下需要用到上述功能的例子。請看下面的規則。

definition（?。? {}
{
      storage（　）type（?。?lt;IDENTIFIER> "; "
    | storage（?。﹖ype（?。?lt;IDENTIFIER> arg_decls（　）block（?。?
    以下省略

上述是C?的參數定義和函數定義的規則。左側的部分完全一樣，也就是說，這樣的規則也會發生選擇沖突。雖說可以通過提取左側共通部分來解決問題，但這次讓我們考慮嘗試用超前掃描的方法。

用超前掃描來分析上述規則，讀取“恰好n個”token是行不通的。原因在于共通部分storage（　）type（　）<IDENTIFIER>中存在非終端符號storage（　）和type（　）。因為不知道storage（?。┖蛅ype（?。嶋H對應幾個token，所以無法用讀取“恰好n個”token來處理。

這里就需要使用剛才提到的“讀取符合這個規則的所有token”這樣的設置。上述規則中選項間的共通部分是storage（　）type（?。?lt;IDENTIFIER>，因此只要讀取了共通部分加上1個token，即storage（?。﹖ype（?。?lt;IDENTIFIER> "; "，就能夠區別2個選項了。將規則進行如下改寫。

definition（?。? {}
{
      LOOKAHEAD（storage（　）type（　）<IDENTIFIER> "; "）
      storage（?。﹖ype（?。?lt;IDENTIFIER> "; "
    | storage（　）type（　）<IDENTIFIER> arg_decls（　）block（　）
    以下省略

如上所示，只需在LOOKAHEAD的括號中寫上需要超前掃描的規則即可。這樣利用超前掃描就能夠順利地區分2個選項了。

超前掃描的相關注意事項

這里講一個和token的超前掃描相關的注意事項。

即便寫了LOOKAHEAD也并非一定能按照預期對程序進行分析。添加LOOKAHEAD后Choice conflict的警告消息的確消失了，但實際上JavaCC不會對LOOKAHEAD描述的內容進行任何檢查。在發生選擇沖突的地方加上LOOKAHEAD后不再顯示警告，僅此而已。LOOKAHEAD處理的描述是否正確，我們必須自己思考。