利用ANTLR生成C++描述的分析程序

摘要

ANTLR（ANother Tool for Language Recognition）是一種基于LL（k）文法的語法分析程序（以下簡稱分析器）生成工具。其生成的分析器默認使用Java描述，而不是更高效的C++。本文介紹了在Windows平臺下，借助VC6.0進行組織工程，使用ANTLR生成C++描述的分析器的方法，并給出了一個實例。最后，本文對ANTLR本身做出了一點小小的改進。

關鍵字

ANTLR，語法分析器，語法分析器生成工具

ANTLR簡介

分析器的自動生成一直是編譯理論研究的一個方向。早期的程序員手工編寫分析器，不但費時費力，而且編寫的分析器不穩定、不易修改和移植。在自動化大潮沖擊之下，越來越多的程序員拋棄了這種手工做法。

由舊金山大學的Terence Parr 領導開發的ANTLR（以前叫做PCCTS，Purdue Compiler Construction Tool Set，普渡大學編譯器構建工具集）是一種分析器自動生成工具，它可以接受語言的文法描述，并能產生識別這些語言的程序。而且我們可以在文法描述中插入特定的語義動作，告訴ANTLR怎樣去創建抽象語法樹(AST)和怎樣產生輸出。

現在ANTLR越來越流行（有評論說ANTLR的出現是一個里程碑），不僅因為它功能更強、容易擴展、開源，而且ANTLR生成的代碼和使用遞歸下降方法（手工生成分析器的主要方法）生成的代碼很相似，易于閱讀理解。與之相比，另外一種著名的分析器生成工具YACC（Yet Another Compiler-Compiler，基于LR分析方法）生成的程序就比較晦澀。

目前國內介紹ANTLR的文章不多，僅有的文章也是介紹使用ANTLR生成使用java描述的分析器。其實ANTLR也可以生成C++描述的源程序（從2.7.3版本開始，ANTLR開始支持C#，將來還會支持Python），不過需要一些準備工作。本文將詳細地介紹其中的具體步驟。

最新版本的ANTLR可以去ANTLR的官方網站（http://www.ANTLR.org）下載。截止到2004年6月，ANTLR的最新版本是2.7.4。下載的文件是一個不到1.3M的tar.gz形式的壓縮包，將其解壓到某個目錄（下文用<ANTLRpath>表示）。

ANTLR是使用Java開發的，需要JDK的支持。本文假設您的機器已經安裝JDK，并正確設置了classpath。

文法文件

文法就是語言識別的規則。它是ANTLR生成程序的依據。文法文件是ANTLR的核心，是程序員和ANTLR進行交流的接口。

文法文件的編寫基本是面向被解決的問題的。程序員只需要集中精力思考解決問題的邏輯，而不是羈絆于某種程序設計語言的實現細節，因此降低了出現錯誤的可能性。

文法文件的語法簡介

本文只是簡單地介紹一個文法文件的語法，具體內容可以參閱ANTLR的相關文檔。

文法文件一般包括header塊、options塊、文法分析器類（parser）及規則定義、詞法分掃描器類（lexer）及token定義。其中最為重要的是規則和token的定義。

規則的定義形式和編譯理論中的擴展巴科斯范式（EBNF）極為相似，包括規則名、規則體、一個用作結束標志的分號和異常處理部分（可省略）。例如如下的規則就描述了C語言中的賦值語句的語法：

assignment_stat:

     id '=' expr ';'

     ;

其意義是：一條賦值語句是由一個id、一個等號、一個表達式和一個分號順序組成的。

Token的定義方法與規則類似。例如如下的token定義就表示一個十進制的整數：

NUM:

     ('1'..'9')('0'..'9')*

     ;

其意義是：數字（NUM）的第一字符是‘1’到‘9’中的一個字符，后面是0個或多個‘0’到‘9’之間的字符。

需要注意的一點是：規則的名字必須是小寫字母開始，而token的名字則必須是大寫字母開始。

設定ANTLR生成的語言

ANTLR有很多選項，可以通過在文法文件中的options塊中進行設置，其中包括ANTLR最終生成的語言。如果要生成C++描述的分析器程序，就要如下設定：

options

{

language="Cpp";

// Other options

}

language選項的默認值是“Java”。如果您希望生成的程序是C#的，將language設為“Csharp”就可以了。

C++程序的例子

下面就給出一個ANTLR生成的C++描述的分析器的實例。該分析器的功能是分析用戶輸入的一個算術表達式，給出該表達式的最終結果。在該表達式中允許出現的運算符除了加減乘除之外，還包括求冪運算符“^”，以及sin、cos和tan三個三角函數。

在開始之前，我們首先要生成編譯鏈接ANTLR生成的程序時需要的庫文件。

構建靜態鏈接庫

構建（build）由ANTLR生成的C++程序需要一個運行庫的支持。該運行庫的源代碼也是完全開放的，位于<ANTLRpath>\antlr-2.7.4\lib\cpp目錄下。我們可以選擇這些代碼其編譯為靜態鏈接庫或者動態鏈接庫。對于2.7.4版本的ANTLR，編譯動態鏈接庫需要VC7.0以上的編譯環境。這里我們將其編譯為靜態庫。

首先使用VC6.0新建一個名為ANTLRLib的Win32的靜態鏈接庫的工程，不要選擇“Pre-compiled Header”和“MFC support”選項。

點擊菜單“Project”à“Add to Project”à“Files…”，將Antlr-2.7.4\lib\cpp\src下面的除了dll.cpp之外的所有文件加入到工程中（注意一定不要加入dll.cpp，否則無法通過編譯）。

為了讓VC6.0找到所需要的頭文件，需要將<ANTLRpath>\antlr-2.7.4\lib\cpp加入到頭文件搜索路徑中。具體方法是點擊“Project”à“Settings…”，在彈出的對話框中選擇“Debug”標簽頁，在下拉列表中選擇“Preprocessor”，在“Additional include path”中，如圖填入：

         <ANTLRpath>\antlr-2.7.4\lib\cpp

此時build整個工程，就可以生成ANTLR的運行庫文件ANTLRLib.lib（有些文檔說需要在工程設置中開啟RTTI選項，但是似乎不這樣做也沒有太大的影響）。

編寫文法文件

根據需求，不難寫出如下的文法文件：

header{

#include <stdlib.h>

#include <stdio.h>

#include <math.h>

}

 

options

{

    language="Cpp";

}

 

class ExprParser extends Parser;

{

}

 

// rules

expr returns [double value=0]

{double x;}

    :

    value=term

    (

    PLUS x=term {value+=x;}

    |

    MINUS x=term{value-=x;}

    )*

    ;

exception

    catch [ANTLR_USE_NAMESPACE(antlr)ANTLRException& ex] {

        // catch all exceptions and report it

        reportError(ex.toString());

    }

 

term returns [double value=0]

{double x;}

    :

    value=factor

    (

    STAR x=factor {value*=x;}

    |

    SLASH x=factor { value /= x;}

    )*

    ;

 

factor returns [double value =0 ]

{double x;}

    :

    value = atom

    (

    TOK_POW x = atom { value = pow(value,x); }

    )*

    ;

 

atom returns [double value=0]

{double x;}

    :

    i:NUM

    {

        value=atof((i->getText()).c_str());

    }

    |

    TOK_SIN x = atom { value = sin (x);}

    |

    TOK_COS x = atom { value = cos (x);}

    |

    TOK_TAN x = atom { value = tan (x);}

    |

    LPAREN value=expr RPAREN

    ;

exception

    catch [ANTLR_USE_NAMESPACE(antlr)ANTLRException& ex] {

        reportError(ex.toString());

    }

 

class ExprLexer extends Lexer;

options{

    k=1;

    caseSensitive = false;

}

 

// tokens

LPAREN  :'(';

RPAREN  :')';

PLUS    :'+';

MINUS   :'-';

STAR    :'*';

SLASH   :'/';

NUM     :('0'..'9')('0'..'9')*('.'('0'..'9')*)?;

RETURN  :'\n';

 

// math token

TOK_SIN :"sin";

TOK_COS :"cos";

TOK_TAN :"tan";

TOK_POW :'^';

 

// white space

WS  :

    (

    ' '

    |

    '\t'

    )

    {$setType(ANTLR_USE_NAMESPACE(antlr)Token::SKIP);}

    ;

 

將該文件保存為test.g（‘g’是默認的文法文件的擴展名）。

在該文法文件中，定義了一個分析器類ExprParser和一個詞法掃描器類ExprLexer。ANTLR會為兩個類分別生成頭文件和實現文件。

使用VC6.0組織工程

現在需要由文法文件生成分析器的源代碼，然后再添加其他的一些代碼，最后編譯這些代碼，過程略顯繁瑣。因此這里借助VC6.0作為開發環境來組織工程，簡化步驟。

新建工程

使用VC6.0新建一個名為AntlrCpp的Win32控制臺的項目。選擇新建一個空的工程。點擊“Project”à“Add To Project”à“Files”，將文法文件test.g添加到工程中。

在VC的FileView中右鍵點擊該文法文件，在彈出菜單中選擇“Settings…”，彈出如圖所示的對話框，選擇“Custom Build”標簽頁，如圖所示：

在“Commands”里面填入調用ANTLR編譯文法文件的命令：

         java -cp  <ANTLRpath>\antlr-2.7.4\antlr.jar antlr.Tool -o "$(WkspDir)" $(InputName).g

在“Outputs”里面填入ANTLR編譯文法文件后要生成的所有文件的名字，如下：

         ExprLexer.cpp     

         ExprLexer.hpp

         ExprParser.cpp

         ExprParser.hpp

         ExprParserTokenTypes.hpp

         ExprParserTokenTypes.txt

生成分析器源代碼

設置完成之后，就可以編譯該文法文件了：選中該文法文件，按Ctrl+F7（或者點擊工具欄中的編譯按鈕），執行編譯操作。在VC的Output窗口里面會顯示出如下的內容：

         --------------------Configuration: AntlrCpp - Win32 Debug--------------------

         Performing Custom Build Step on .\testjava.g

         ANTLR Parser Generator   Version 2.7.4   1989-2004 jGuru.com

        

         ExprLexer.cpp - 0 error(s), 0 warning(s)

此時，分析器的源代碼已經生成。再次點擊菜單“Project”à“Add To Project