前言

    本系列的文章的宗旨是讓大家能夠寫出自己的編譯器,解釋器或者腳本引擎,所以每到理論介紹到一個程度后,我都會來討論實踐問題.理論方面,編譯原理的教材已經是夠多了,而實踐的問題卻很少討論.

    前幾節文章只討論到了詞法分析和LL 文法分析,關鍵的LR文法分析這里卻還沒有講,我們先不要管復雜的LR文法和算法,讓我們使用LL算法來實際做一些東西后再說.本文將介紹一個在JAVA 上廣泛使用的LL算法分析工具Javacc.(這是我唯一能找到的使用LL算法的語法分析器構造工具).這一節的文章并非只針對JAVA開發者,如果你是 C/C++開發者,那么也請你來看看這個JAVA下的優秀工具,或許你將來也用得著它.

    Lex和yacc這兩個工具是經典的詞法分析和語法分析工具,但是它們都是基于C語言下面的工具,而使用JAVA的朋友們就用不上了.但是JAVA下已經有了lex和yacc的替代品javacc(Java Compiler Compiler ).同時javacc也是使用LL算法的工具,我們也可以實踐一下前面學的LL算法.

首先聲明我不是一個JAVA專家,我也是剛剛才接觸JAVA.Java里面或許有很多類似javacc一樣的工具,但是據我所知,javacc還是最廣泛,最標準的JAVA下的詞法語法分析器.

Javacc的獲取

    同lex 和yacc一樣,javacc也是一個免費可以獲取的通用工具,它可以在很多JAVA相關的工具下載網站下載,當然,javacc所占的磁盤空間比起 lex和yacc更大一些,里面有標準的文檔和examples.相對lex和yacc來說,javacc做得更人性化,更容易一些.如果你實在找不到 javacc,還是可以聯系我,我這里有.現在最新的就是javacc 3.2版本.

Javacc的原理

Javacc 可以同時完成對text的詞法分析和語法分析的工作,使用起來相當方便.同樣,它和lex和yacc一樣,先輸入一個按照它規定的格式的文件,然后 javacc根據你輸入的文件來生成相應的詞法分析于語法分析程序.同時,新版本的Javacc除了常規的詞法分析和語法分析以外,還提供JJTree等 工具來幫助我們建立語法樹.總之,Javacc在很多地方做得都比lex和yacc要人性化,這個在后面的輸入文件格式中也能體現出來.

Javacc的輸入文件

Javacc的輸入文件格式做得比較簡單.每個非終結符產生式對應一個Class中的函數,函數中可以嵌入相應的識別出該終結符文法時候的處理代碼(也叫動作).這個與YACC中是一致的.

Javacc 的輸入文件中,有一系列的系統參數,比如其中lookahead可以設置成大于1的整數,那么就是說,它可以為我們生成LL(k)算法 (k>=1),而不是簡單的遞歸下降那樣的LL(1)算法了.要知道,LL(2)文法比起前面討論的LL(1)文法判斷每個非終結符時候需要看前面 兩個記號而不是一個,那么對于文法形式的限制就更少.不過LL(2)的算法當然也比LL(1)算法慢了不少.作為一般的計算機程序設計語言,LL(1)算 法已經是足夠了.就算不是LL(1)算法,我們也可以通過前面講的左提公因式把它變成一個LL(1)文法來處理.不過既然javacc都把 lookahead選擇做出來了,那么在某些特定的情況下,我們可以直接調整一個lookahead的參數就可以,而不必糾正我們的文法.

下面我們來看看Javacc中自帶的example中的例子.

例5.1

這個例子可以在javacc-3.2/doc/examples/SimpleExamples/Simple1.jj看到

PARSER_BEGIN(Simple1)

public class Simple1 {

public static void main(String args[]) throws ParseException {

    Simple1 parser = new Simple1(System.in);

    parser.Input();

  }

}

PARSER_END(Simple1)

void Input() :

{}

{

  MatchedBraces() ("\n"|"\r")* <EOF>

}

void MatchedBraces() :

{}

{

"{" [ MatchedBraces() ] "}"

}

設置好javacc的bin目錄后,在命令提示符下輸入

javacc Simple1.jj

然后javacc就會為你生成下面幾個java源代碼文件

Simple1.java

Simple1TokenManager.java

Simple1Constants.java

SimpleCharStream.java

Token.java

TokenMgrError.java

其中Simple1就是你的語法分析器的對象,它的構造函數參數就是要分析的輸入流,這里的是System.in.

class Simple1就定義在標記PARSER_BEGIN(Simple1)

PARSER_END(Simple1)之間.

但是必須清楚的是,PARSER_BEGIN和PARSER_END中的名字必須是詞法分析器的名字(這里是Simple1).

PARSER_END下面的定義就是文法非終結符號的定義了.

Simple1的文法基本就是:

Input -> MatchedBraces ("\n"|"\r")* <EOF>

MatchedBraces -> “{“ MatchedBraces “}”

從它的定義我們可以看到,每個非終結符號對于一個過程.

比如Input的過程

void Input() :

{}

{

  MatchedBraces() ("\n"|"\r")* <EOF>

}

在定義void Input后面記住需要加上一個冒號”:”,然后接下來是兩個塊{}的定義.

第一個{}中的代碼是定義數據,初試化數據的代碼.第二個{}中的部分就是真正定義Input的產生式了.

每個產生式之間用”|”符號連接.

注意: 這里的產生式并非需要嚴格BNF范式文法,它的文法既可以是BNF,同時還可以是混合了正則表達式中的定義方法.比如上面的

Input -> MatchedBraces ("\n"|"\r")* <EOF>

中(“\n”|”\r”)* 就是個正則表達式,表示的是\n或者\r的0個到無限個的重復的記號.

而<EOF>是javacc系統定義的記號(TOKEN),表示文件結束符號.

除了<EOF>,無論是系統定義的TOKEN,還是自定義的TOKEN, 里面的TOKEN都是以<token’s name>的方式表示.

每個非終結符號(Input和MatchedBraces)都會在javacc生成的Simple1.java中形成Class Simple1的成員函數.當你在外部調用Simple1的Input,那么語法分析器就會開始進行語法分析了.

例5.2

在javacc提供的example里面沒有.javacc提供的example里面提供的例子中SimpleExamples過于簡單,而其它例子又過于龐大.下面我以我們最常見的數學四則混合運算的文法來構造一個javacc的文法識別器.這個例子是我自己寫的,十分簡單,.其中還包括了文法識別同時嵌入的構建語法樹Parse-Tree的代碼.不過由于篇幅的原因,我并沒有給出全部的代碼,這里只給了javacc輸入部分相關的代碼.而Parse-tree就是一個普通的4叉樹,3個child,1個next(平行結點),相信大家在學習數據結構的時候應該都是學過的.所以這里就省略過去了.

在大家看這些輸入代碼之前,我先給出它所使用的文法定義,好讓大家有個清楚的框架.

Expression -> Term { Addop Term }
Addop -> "+" | "-"
Term -> Factor { Mulop Factor }
Mulop -> "*" | "/"
Factor -> ID | NUM | "(" Expression ")"

這里的文法可能和BNF范式有點不同.{}的意思就是0次到無限次重復,它跟我們在學習正則表達式的時候的”*”符號相同,所以，在Javacc中的文法表示的時候，{…}部分的就是用(…)*來表示.

為了讓詞法分析做得更簡單,我們通常都不會在文法分析的時候,使用”(”,”)“等字符號串來表示終結符號,而需要轉而使用LPAREN, RPAREN這樣的整型符號來表示.

PARSER_BEGIN(Grammar)

public class Grammar implements NodeType {

  public ParseTreeNode GetParseTree(InputStream in) throws ParseException

  {

       Grammar parser =new Grammar(in);

       return parser.Expression();

  }

}

PARSER_END(Grammar)

SKIP :

{

  " " | "\t" | "\n" | "\r"

}

TOKEN :

{

  < ID: ["a"-"z","A"-"Z","_"] ( ["a"-"z","A"-"Z","_","0"-"9"] )* >

|  < NUM: ( ["0"-"9"] )+ >

|  < PLUS:   "+" >

|  < MINUS:  "-" >

|  < TIMERS: "*" >

|  < OVER:   "/" >

|  < LPAREN: "(" >

|  < RPAREN: ")" >

}

ParseTreeNode Expression() :

{

         ParseTreeNode ParseTree = null;

         ParseTreeNode node;

}

{                

 ( node=Simple_Expression()

 {

    if(ParseTree == null)

             ParseTree =node;

    else

    {

                 ParseTreeNode t;

           t= ParseTree;

                 while(t.next != null)

                  t=t.next;

               t.next = node;

    }

 }

)*

  { return ParseTree;}

  <EOF>

}

ParseTreeNode Simple_Expression() :

{

         ParseTreeNode node;

         ParseTreeNode t;

         int op;

}

{

  node=Term(){}

  (

  op=addop() t=Term()

{

                  ParseTreeNode newNode = new ParseTreeNode();

                  newNode.nodetype = op;

                  newNode.child[0] = node;

                  newNode.child[1] = t;

                  switch(op)

                   {

                            case PlusOP:

                            newNode.name = "Operator: +";

                            break;

                            case MinusOP:

                            newNode.name = "Operator: -";

                            break;

                   }

                   node = newNode;

         }

  )*

  { return node; }

}

int addop() : {}

{

         <PLUS> { return PlusOP; }

|   <MINUS> { return MinusOP; }

}

ParseTreeNode Term() :

{

         ParseTreeNode node;

         ParseTreeNode t;

         int op;

}

{

  node=Factor(){}

  (

  op=mulop() t=Factor()

{

                  ParseTreeNode newNode = new ParseTreeNode();

                  newNode.nodetype = op;

                  newNode.child[0] = node;

                  newNode.child[1] = t;

                  switch(op)

                   {

                            case TimersOP:

                            newNode.name = "Operator: *";

                            break;

                            case OverOP:

                            newNode.name = "Operator: /";

                            break;

                   }

                   node = newNode;

         }

  )*

  {

       return node;

  }

}

int mulop() :{}

{

         <TIMERS> { return TimersOP; }

         | <OVER> { return OverOP;   }

}

ParseTreeNode Factor() :

{

         ParseTreeNode node;

         Token t;

}

{

  t=<ID>

{

           node=new ParseTreeNode();

           node.nodetype= IDstmt;

           node.name = t.image;

           return node;

         }

  |

  t=<NUM>

  {

      node=new ParseTreeNode();

           node.nodetype= NUMstmt;

           node.name = t.image;

           node.value= Integer.parseInt(t.image);

           return node;

    }

  |

  <LPAREN> node=Simple_Expression() <RPAREN>

  {

         return node;

  }

}

其中SKIP 中的定義就是在進行詞法分析的同時,忽略掉的記號.TOKEN中的,就是需要在做詞法分析的時候,識別的詞法記號.當然,這一切都是以正則表達式來表示的.

這個例子就有多個非終結符號,可以看出,我們需要為每個非終結符號寫出一個過程.不同的非終結符號的識別過程中可以互相調用.

    以Simple_Expression()過程為例,它的產生式是Expression -> Term { addop Term },而在javacc的輸入文件格式是，它的識別是這樣寫的node=Term(){} ( op=addop() t=Term(){ … })* 前面說過，這里的”*”符號和正則表達式是一樣的，就是0次到無限次的重復.那么Simple_Expression等于文法Term Addop Term Addop Term Addop Term … 而Addop也就相當于PLUS和MINUS兩個運算符號.這里我們在寫Expression的文法的時候，同時還使用了賦值表達式，因為這個和Yacc不同的時候，Javacc把文法識別完全地做到了函數過程中，那么如果我們要識別Simple_Expression的文法，就相當于按順序識別Term和Addop兩個文法,而識別那個文法，就相當于調用那兩個非終結符的識別函數.正是這一點，我覺得Javacc的文法識別處理上就很接近程序的操作過程,我們不需要像YACC那樣使用嚴格的文法表示格式，復雜的系統參數了.

關于Yacc的使用，其實比Javacc要復雜，還需要考慮到和詞法分析器接口的問題，這個我會在以后細細講到.

    至于其它的文法操作解釋我就不再多說了,如果要說,就是再寫上十篇這樣的文章也寫不完.本文只能給讀者們一個方向,至于深入的研究,還是請大家看javacc提供的官方文檔資料.

最后

    由于國外使用JAVA做項目的程序員比國內多,那么討論JAVA技術的人員也比較多.可能來這里讀我的文章的人都是C/C++程序員,但是關注其它領域同方向的技術也是可以讓我們的知識領域更加寬廣.關于JavaCC的討論主要是在國際新聞組comp.compilers.tools.javacc如果大家在使用JavaCC做實際問題的時候遇到什么問題,不妨上去找找專家.

原文：http://dev.csdn.net/article/22/22189.shtm