實用javacc
?
前言
本系列的文章的宗旨是讓大家能夠寫出自己的編譯器,解釋器或者腳本引擎,所以每到理論介紹到一個程度后,我都會來討論實踐問題.理論方面,編譯原理的教材已經是夠多了,而實踐的問題卻很少討論.
?
前幾節文章只討論到了詞法分析和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
做實際問題的時候遇到什么問題
,
不妨上去找找專家
.
轉載人【chenpengyi】注：
JavaCC 的下載地址是：https://javacc.dev.java.net/
同時它已經包含了很多語言的grammar模版了，譬如html,xml,python,vb…..等等，可以到http://www.cobase.cs.ucla.edu/pub/javacc/下載。