使用JavaCC做語法分析

火星人 @ 2014-03-10 , reply:0


前言

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

前幾節文章只討論到了詞法分析和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 提供的官方文檔資料 .

JavaCC 的下載地址是:https://javacc.dev.java.net/同時它已經包含了很多語言的grammar模版了,譬如html,xml,python,vb………等等,可以到http://www.cobase.cs.ucla.edu/pub/javacc/下載.6




[火星人 via ] 使用JavaCC做語法分析已經有132次圍觀

http://www.coctec.com/docs/java/show-post-61746.html