实用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/下载。