第1部分 代碼分析

第3章 語法分析的概要

本章先簡單地介紹一下負責代碼分析的語法分析器的相關內容，接著對描述cbc的解析器所使用的JavaCC這一工具的概要進行說明。

3.1 語法分析的方法

本節將對語法分析的一般方法進行說明。

代碼分析中的問題點

代碼的分析可不是用普通的方法就可以解決的。例如，考慮一下C語言中的算式。C語言中的8+2-3應該解釋為（8+2）-3，但8+2＊3的話就應該解釋為8+（2＊3）。分析算式時，一定要考慮運算符的優先級（operator precedence）。

C語言中能夠填寫數字的地方可以用變量或數組、結構體的元素來替代，甚至還可以是函數調用。對于這種多樣性，編譯器都必須能夠處理。

而且，無論是算式、變量還是函數調用，如果出現在注釋中，則不需要處理。同樣，出現在字符串中也不需要處理。編譯器必須考慮到這種因上下文而產生的差異。

如上所述，在分析編程語言的代碼時，需要考慮到各種因素，的確非常棘手。

代碼分析的一般規律

為了處理分析代碼時產生的各類問題，人們嘗試了各種手段，現在編程語言的代碼分析在多數范圍內都有一般規律可循。只要遵循一般規律，絕大多數的編程語言都能夠順利分析。

另外，如果將編程語言設計得能夠根據一般規律進行代碼分析，那么之后的處理就會容易得多。C?就是這樣設計的一種語言。它將C語言中不符合代碼分析一般規律的部分進行了改良，盡量簡化了代碼分析處理。

換言之，C?語言中所修改的規范也就是利用一般規律難以處理的規范。關于這部分規范的內容，以及原來的規范為什么使用一般規律難以處理，后文將進行適當的說明。

詞法分析、語法分析、語義分析

接著，我們就來具體了解一下代碼分析的一般規律。第1章中提到了代碼分析可分為語法分析和語義分析兩部分。一般來說，語法分析還可以繼續細分為以下2個階段。

1．詞法分析

2．語法分析

首先解釋一下詞法分析。

詞法分析（lexical analyze）就是將代碼分割為一個個的單詞，也可以稱為掃描（scan）。舉例來說，詞法分析就是將x = 1 + 2這樣的程序分割為“x”“=”“1”“+”“2”這樣5個單詞。并且在該過程中，會將空白符和注釋這種對程序沒有實際意義的部分剔除。正因為預先有了詞法分析，語法分析器才可以只處理有意義的單詞，進而實現簡化處理。

負責詞法分析的模塊稱為詞法分析器（lexical analyzer），又稱掃描器（scanner）。

理想的情況是將詞法分析、語法分析、語義分析這3個階段做成3個獨立的模塊，這樣的代碼是最優美的。但實際上，這3個階段并不能明確地分割開?，F有的編程語言中，能將詞法分析、語法分析、語義分析清晰地分割開的恐怕也不多。因此，比較實際的做法是以結構簡潔為目標，在意識到存在3個階段的基礎上，進行各類嘗試和修改。

本書中制作的C?編譯器的詞法分析為獨立的模塊，但語義分析的一部分將放在語法分析的模塊中來實現。

掃描器的動作

接著，讓我們更深入地了解一下這部分內容。先從掃描器（即詞法分析器）的結構開始，以下面的C?代碼為例。

import stdio;


int
main（int argc, char＊＊ argv）
{
    printf（"Hello, World! \n"）;  /＊ 打個招呼吧 ＊/
    return 0;
}

這就是所謂的Hello, World！程序。掃描器將此代碼分割為如下的單詞。

import
stdio
;
int
main
（
int
argc
,
char
＊
＊
argv
）
{
printf
（
"Hello, World! \n"
）
;
return
0
;
}

需要注意的是，這里已經剔除了空白符、換行以及注釋。一般情況下，空白符和注釋都是在詞法分析階段進行處理的。

單詞的種類和語義值

掃描器的工作不僅僅是將代碼分割成單詞，在分割的同時還會推算出單詞的種類，并為單詞添加語義值。

單詞的種類是指該單詞在語法上的分類，例如單詞“54”的種類是“整數”。

語義值（semantic value）表示單詞所具有的語義。例如，在C語言中，單詞“54”的語義為“數值54”。單詞“"string"”的語義為“字符串"string"”?！皃rintf”和“i”的語義有可能是函數名，也有可能是變量名。

所以，為了表示“整數54”，掃描器會為單詞“54”添加“這個單詞的語義是數值54”這樣的信息。該信息就是語義值。單詞“"Hello\n"”的種類是字符串，添加的語義值為“H”“e”“l”“l”“o”“換行符”這6個字符（圖3-1）。

圖3-1 單詞和語義值

另外，也有一些單詞本身不存在語義值。例如，對于保留字int來說，“保留字int”這樣的種類信息已經完全能夠表示語義，不需要額外的語義值。

token

在編程語言處理系統中，我們將“一個單詞（的字面）”和“它的種類”“語義值”統稱為token。通過使用token這個詞，詞法分析器的作用就可以說是解析代碼（字符行）并生成token序列。

以剛才列舉的Hello, World！程序為例，cbc的掃描器輸出的token序列如表3-1所示。

表3-1 Hello, World！的詞法分析結果

cbc中使用--dump-tokens選項就可以顯示任意代碼的掃描結果的token序列。請大家一定自己試著用cbc --dump-tokens處理各類代碼，看一下會生成怎樣的結果。

抽象語法樹和節點

編程語言的編譯器中解析器的主要作用是解析由掃描器生成的token序列，并生成代碼所對應的樹型結構，即語法樹。確切地說，也有方法可以不需要生成語法樹，但這樣的方法僅限于極小型的編譯器，因此本書予以省略。

語法樹和語法是完全對應的，所以例如C語言的終結符分號以及表達式兩端的括號等都包含在真實的語法樹中。但是，保存分號和括號基本沒有實際的意義，因此實際上大部分情況下會生成一開始就省略分號、括號等的抽象語法樹。也就是說，解析器會跳過語法樹，直接生成抽象語法樹。

無論語法樹還是抽象語法樹，都是樹形的數據結構，因此和普通的樹結構相同，由稱為節點（node）的數據結構組合而成。用Java來寫的話，一個節點可以用一個節點對象來表示。

3.2 解析器生成器

本節我們將了解自動生成解析器的工具。

什么是解析器生成器

手動編寫掃描器或解析器是一件非常無聊且繁瑣的事情，原因在于不得不反復編寫同樣的代碼。而且手動編寫掃描器或解析器的話，將很難理解要解析的究竟是一種怎樣的語法。

因此，為了使工作量和可讀性兩方面都有所改善，人們對自動生成掃描器和解析器的方法進行了研究。生成掃描器的程序稱為掃描器生成器（scanner generator），生成解析器的程序稱為解析器生成器（parser generator）。只需指定需要解析的語法，掃描器生成器和解析器生成器就能生成解析相應語法的代碼。

cbc使用名為JavaCC的工具來生成掃描器和解析器。JavaCC兼具掃描器生成器和解析器生成器的功能，因此能夠在一個文件中同時記述掃描器和解析器。

解析器生成器的種類

掃描器生成器都大體類似，解析器生成器則有若干個種類?，F在具有代表性的解析器生成器可分為LL解析器生成器和LALR解析器生成器兩類。

這樣劃分種類的依據是解析器生成器能夠處理的語法的廣度。解析器生成器并非能夠處理所有語法，有著其自身的局限性?？梢哉f這種局限性越小，能夠處理的語法就越廣。

一般的解析器生成器的種類如表3-2所示。大家可以結合該表來閱讀下面的內容。一般來說，能夠處理的語法范圍最廣的解析器生成器是LR解析器生成器。但是因為LR解析器生成器的速度非常緩慢，所以出現了通過稍微縮減可處理的語法范圍來提高效率的解析器生成器，那就是LALR解析器生成器。而LL解析器生成器比LALR解析器生成器的結構更簡單、更易于制作，但可處理的語法范圍也更小。

表3-2 解析器生成器的種類

LALR解析器生成器能夠處理的語法范圍比LL要廣泛很多，加上現有的編程語言幾乎都屬于LALR語法，因此解析器生成器長期以來都是以LALR解析器生成器為主。而最具代表性的LALR解析器生成器就要數UNIX上的yacc了。

但最近從解析器的易理解性和可操作性來看，LL解析器生成器的勢頭正在恢復。本書所用的JavaCC就是面向Java的LL解析器生成器。

解析器生成器的選擇

除JavaCC之外，還有很多其他的解析器生成器。表3-3中列舉了各語言具有代表性的解析器生成器。

表3-3 各類解析器生成器

在“可處理語法的范圍”一列中，有的像LALR（1）這樣，標注了（1）這樣的數字。這表示能夠超前掃描的token數，其中（k）或（*）表示能夠超前掃描任意個數?；旧峡梢哉J為這個數字越大解析器生成器的功能就越強。也就是說，同樣為LL解析器生成器，比起LL（1）, LL（k）或者LL（*）要更強大。有關token的超前掃描的內容將在第5章進行講解。

另外，cbc選擇JavaCC作為解析器生成器的原因有如下4個。

●具備了所必需的最低限度的功能

●運行生成的解析器時不需要專門的庫

●軟件的實現比較成熟

●生成的代碼還算是可讀的

但是大家在制作解析器時不必局限于JavaCC。只要學會使用一個解析器生成器，學習其他的解析器生成器也就變得容易了。通過本書理解了JavaCC的優缺點后，也請大家試著研究一下其他生成器。

3.3 JavaCC的概要

本書中的C?編譯器使用名為JavaCC的工具來生成解析器。本節就對JavaCC進行簡單的說明。

什么是JavaCC

JavaCC是Java的解析器生成器兼掃描器生成器。為JavaCC描述好語法的規則，JavaCC就能夠生成可以解析該語法的掃描器和解析器（的代碼）了。

JavaCC是LL解析器生成器，因此比起LR解析器生成器和LALR解析器生成器，它有著可處理語法的范圍相對狹窄的缺點。但另一方面，JavaCC生成的解析器有易于理解、易于使用的優勢。另外，因為支持了“無限長的token超前掃描”，所以可處理語法范圍狹窄的問題也得到了很好的改善，這一點將在第5章中介紹。

語法描述文件

語法規則通常會用一個擴展名為“.jj”的文件來描述，該文件稱為語法描述文件。cbc中在名為Parser.jj的文件中描述語法。

一般情況下，語法描述文件的內容多采用如下形式。

options {
    JavaCC的選項
}


PARSER_BEGIN（解析器類名）
package包名；
import庫名；


public class解析器類名 {
    任意的Java代碼
}
PARSER_END（解析器類名）


掃描器的描述


解析器的描述

語法描述文件的開頭是描述JavaCC選項的options塊，這部分可以省略。

JavaCC和Java一樣將解析器的內容定義在單個類中，因此會在PARSER_BEGIN和PARSER_END之間描述這個類的相關內容。這部分可以描述package聲明、import聲明以及任意的方法。

在此之后是掃描器的描述和解析器的描述。這部分的內容將在以后的章節中詳細說明，這里暫且省略。

語法描述文件的例子

如果完全沒有例子將很難理解語法描述文件，因此這里舉一個非常簡單的例子。如代碼清單3.1所示，這是一個只能解析正整數加法運算并進行計算的解析器的語法描述文件。請大家粗略地看一下，只要對內容有大致的了解就行了。

代碼清單3.1 Adder.jj

options {
    STATIC = false;
}


PARSER_BEGIN（Adder）
import java.io.＊;


class Adder {
    static public void main（String[] args）{
        for（String arg : args）{
            try {
                System.out.println（evaluate（arg））;
            }
            catch（ParseException ex）{
                System.err.println（ex.getMessage（?。?
            }
        }
    }


    static public long evaluate（String src）throws ParseException {
        Reader reader = new StringReader（src）;
        return new Adder（reader）.expr（　）;
    }
}
PARSER_END（Adder）


SKIP: { <[" ", "\t", "\r", "\n"]> }


TOKEN: {
    <INTEGER:（["0"-"9"]）+>
}


long expr（?。?
{
    Token x, y;
}
{
    x=<INTEGER> "+" y=<INTEGER> <EOF>
        {
            return Long.parseLong（x.image）+ Long.parseLong（y.image）;
        }
}

接著，從PARSER_BEGIN（Adder）到PARSER_END（Adder）是解析器類的定義。解析器類中需要定義的成員和方法也寫在這里。為了實現即使只有Adder類也能夠運行，這里定義了main函數。main函數的內容將稍后講解。

之后的SKIP和TOKEN部分定義了掃描器。SKIP表示要跳過空格、制表符（tab）和換行符。TOKEN表示掃描整數字符并生成token。

從long expr..．開始到最后的部分定義了狹義的解析器。這部分解析token序列并執行某些操作。cbc生成抽象語法樹，但Adder類并不生成抽象語法樹，而是直接計算表達式的結果。

運行JavaCC

要用JavaCC來處理Adder.jj，需使用如下javacc命令。

$ javacc Adder.jj
Java Compiler Compiler Version 4.0（Parser Generator）
（type "javacc" with no arguments for help）
Reading from file Adder.jj . . .
File "TokenMgrError.java" does not exist.  Will create one.
File "ParseException.java" does not exist.  Will create one.
File "Token.java" does not exist.  Will create one.
File "SimpleCharStream.java" does not exist.  Will create one.
Parser generated successfully.
$ ls Adder.＊
Adder.Java  Adder.jj

除了輸出上述消息之外，還會生成Adder.java和其他的輔助類。

要編譯生成的Adder.java，只需要javac命令即可。輸入如下命令試著進行編譯。

$ javac Adder.java
$ ls Adder.＊
Adder.class Adder.java Adder.jj

這樣就生成了Adder.class文件。

讓我們馬上試著執行一下。Adder類是從命令行參數獲取計算式并進行計算的，因此可以如下這樣從命令行輸入計算式并執行。

$ java Adder '1+5'
6
$ java Adder '1  + 5'
6
$ java Adder '300 + 1234'
1534

可見已經能很好地進行加法運算了。

啟動JavaCC所生成的解析器

在本節結束前，我們來了解一下main函數的代碼。首先，代碼清單3.2中再一次給出了main函數的代碼。

代碼清單3.2 Adder#main函數（Adder.java）

static public void main（String[] args）{
    for（String arg : args）{
        try {
            System.out.println（evaluate（arg））;
        }
        catch（ParseException ex）{
            System.err.println（ex.getMessage（?。?
        }
    }
}

該函數將所有命令行參數的字符串作為計算對象的算式，依次用evaluate方法進行計算。例如從命令行輸入參數"1 + 3", evaluate方法就會返回4，之后只需用System.out. println方法輸出結果即可。

下面所示的是evaluate方法的代碼。

代碼清單3.3 Adder#evaluate方法（Adder.java）

static public long evaluate（String src）throws ParseException {
    Reader reader = new StringReader（src）;
    return new Adder（reader）.expr（?。?
}

該方法中生成了Adder類（解析器類）的對象實例，并讓Adder對象來計算（解析）參數字符串src。

要運行JavaCC生成的解析器類，需要下面2個步驟。

1．生成解析器類的對象實例

2．用生成的對象調用和需要解析的語句同名的方法

首先說一下第1點。JavaCC 4.0生成的解析器中默認定義有如下4種類型的構造函數。

1． Parser（nputStream s）

2． Parser（InputStream s, String encoding）

3． Parser（Reader r）

4. Parser（××××TokenManager tm）

第1種形式的構造函數是通過傳入InputStream對象來構造解析器的。這個構造函數無法設定輸入字符串的編碼，因此無法處理中文字符等。

而第2種形式的構造函數除了InputStream對象之外，還可以設置輸入字符串的編碼來生成解析器。如果要使解析器能夠解析中文字符串或注釋的話，就必須使用第2種或第3種構造函數。但如下所示，如果要處理中文字符串，僅靠改變構造函數是不夠的。

第3種形式的構造函數用于解析Reader對象所讀入的內容。Adder類中就使用了該形式。

第4種形式是將掃描器作為參數傳入。如果是要解析字符串或文件輸入的內容，沒有必要使用該形式的構造函數。

解析器生成后，用這個實例調用和需要解析的語法（正確地說是標識符）同名的方法。這里調用Adder類實例的expr方法，就會開始解析，解析正常結束后會返回語義值。

中文的處理

下面講解一下用JavaCC處理帶有中文字符的字符串的方法。

代碼清單3.4 options塊（parser/Parser.jj）

options {
    STATIC = false;
    JDK_VERSION = "1.5";
}

這樣就會先將輸入的字符串轉換成UNICODE后再進行處理。UNICODE_INPUT選項為false的情況下只能處理ASCII范圍內的字符。

另外，使用剛才列舉的構造函數的第2種或第3種形式，為輸入的字符串設置適當的編碼。使用第3種形式的情況下，在Reader類的構造函數中指定編碼。

編碼所對應的名稱請見表3-4。這樣即使包含中文字符的代碼也能夠正常處理了。

表3-4 編碼的名稱