前言
本系列的文章的宗旨是让大家能够写出自己的编译器解释器或者脚本引擎所以每到理论介绍到一个程度后我都会来讨论实践问题理论方面编译原理的教材已经是够多了而实践的问题却很少讨论
前几节文章只讨论到了词法分析和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专家我也是刚刚才接触JAVAJava里面或许有很多类似javacc一样的工具但是据我所知javacc还是最广泛最标准的JAVA下的词法语法分析器
Javacc 的获取同lex和yacc一样javacc也是一个免费可以获取的通用工具它可以在很多JAVA相关的工具下载网站下载当然javacc所占的磁盘空间比起lex和yacc更大一些里面有标准的文档和examples相对lex和yacc来说javacc做得更人性化更容易一些如果你实在找不到javacc还是可以联系我我这里有现在最新的就是javacc 版本
Javacc 的原理
Javacc 可以同时完成对text的词法分析和语法分析的工作使用起来相当方便同样它和lex和yacc一样先输入一个按照它规定的格式的文件然后javacc根据你输入的文件来生成相应的词法分析于语法分析程序同时新版本的Javacc除了常规的词法分析和语法分析以外还提供JJTree等工具来帮助我们建立语法树总之Javacc在很多地方做得都比lex和yacc要人性化这个在后面的输入文件格式中也能体现出来
Javacc 的输入文件
Javacc 的输入文件格式做得比较简单每个非终结符产生式对应一个Class中的函数函数中可以嵌入相应的识别出该终结符文法时候的处理代码（也叫动作）这个与YACC中是一致的
Javacc 的输入文件中有一系列的系统参数比如其中lookahead可以设置成大于的整数那么就是说它可以为我们生成LL（k）算法（k>=）而不是简单的递归下降那样的LL（）算法了要知道LL（）文法比起前面讨论的LL（）文法判断每个非终结符时候需要看前面两个记号而不是一个那么对于文法形式的限制就更少不过LL（）的算法当然也比LL（）算法慢了不少作为一般的计算机程序设计语言LL（）算法已经是足够了就算不是LL（）算法我们也可以通过前面讲的左提公因式把它变成一个LL（）文法来处理不过既然javacc都把lookahead选择做出来了那么在某些特定的情况下我们可以直接调整一个lookahead的参数就可以而不必纠正我们的文法
下面我们来看看Javacc中自带的example中的例子
例
这个例子可以在javacc/doc/examples/SimpleExamples/Simplejj看到
PARSER_BEGIN(Simple)
publicclassSimple{
publicstaticvoidmain(Stringargs[])throwsParseException{
Simpleparser=newSimple(Systemin);
parserInput();
}
}
PARSER_END(Simple)
voidInput():
{}
{
MatchedBraces()(\n|\r)*<EOF>
}
voidMatchedBraces():
{}
{
{[MatchedBraces()]}
}
设置好javacc的bin目录后在命令提示符下输入
javacc Simplejj
然后 javacc 就会为你生成下面几个 java 源代码文件
Simplejava
SimpleTokenManagerjava
SimpleConstantsjava
SimpleCharStreamjava
Tokenjava
TokenMgrErrorjava
其中Simple就是你的语法分析器的对象它的构造函数参数就是要分析的输入流这里的是Systemin
class Simple 就定义在标记 PARSER_BEGIN（Simple）
PARSER_END（Simple） 之间
但是必须清楚的是PARSER_BEGIN和PARSER_END中的名字必须是词法分析器的名字（这里是Simple）
PARSER_END 下面的定义就是文法非终结符号的定义了
Simple 的文法基本就是
Input > MatchedBraces （\n|\r）* <EOF>
MatchedBraces > { MatchedBraces }
从它的定义我们可以看到 每个非终结符号对于一个过程
比如 Input 的过程
voidInput():
{}
{
MatchedBraces()(\n|\r)*<EOF>
}
在定义 void Input 后面记住需要加上一个冒号 然后接下来是两个块 {} 的定义
第一个 {} 中的代码是定义数据 初试化数据的代码 第二个 {} 中的部分就是真正定义 Input 的产生式了
每个产生式之间用 | 符号连接
注意 这里的产生式并非需要严格 BNF 范式文法 它的文法既可以是 BNF 同时还可以是混合了正则表达式中的定义方法 比如上面的
Input > MatchedBraces （\n|\r）* <EOF>
中 （\n|\r）* 就是个正则表达式 表示的是 \n 或者 \r 的 个到无限个的重复的记号
而 <EOF> 是 javacc 系统定义的记号 （TOKEN） 表示文件结束符号
除了 <EOF> 无论是系统定义的 TOKEN 还是自定义的 TOKEN 里面的 TOKEN 都是以 <tokens name> 的方式表示
每个非终结符号 （Input 和 MatchedBraces） 都会在 javacc 生成的 Simplejava 中形成 Class Simple 的成员函数 当你在外部调用 Simple 的 Input 那么语法分析器就会开始进行语法分析了
例
在 javacc 提供的 example 里面没有 javacc 提供的 example 里面提供的例子中 SimpleExamples 过于简单 而其它例子又过于庞大 下面我以我们最常见的数学四则混合运算的文法来构造一个 javacc 的文法识别器 这个例子是我自己写的 十分简单 其中还包括了文法识别同时嵌入的构建语法树 ParseTree 的代码 不过由于篇幅的原因 我并没有给出全部的代码 这里只给了 javacc 输入部分相关的代码 而 Parsetree 就是一个普通的 叉树 个 child 个 next（ 平行结点 ） 相信大家在学习数据结构的时候应该都是学过的 所以这里就省略过去了
在大家看这些输入代码之前 我先给出它所使用的文法定义 好让大家有个清楚的框架
Expression>Term{AddopTerm}
Addop>+|
Term>Factor{MulopFactor}
Mulop>*|/
Factor>ID|NUM|(Expression)
这里的文法可能和BNF范式有点不同{}的意思就是次到无限次重复它跟我们在学习正则表达式的时候的*符号相同所以在Javacc中的文法表示的时候{…}部分的就是用（…）*来表示
为了让词法分析做得更简单 我们通常都不会在文法分析的时候 使用 （） 等字符号串来表示终结符号 而需要转而使用 LPAREN RPAREN 这样的整型符号来表示
PARSER_BEGIN(Grammar)
publicclassGrammarimplementsNodeType{
publicParseTreeNodeGetParseTree(InputStreamin)throwsParseException
{
Grammarparser=newGrammar(in);
returnparserExpression();
}
}
PARSER_END(Grammar)
SKIP:
{
|\t|\n|\r
}
TOKEN:
{
<ID:[azAZ_]([azAZ_])*>
|<NUM:([])+>
|<PLUS:+>
|<MINUS:>
|<TIMERS:*>
|<OVER:/>
|<LPAREN:(>
|<RPAREN:)>
}
ParseTreeNodeExpression():
{
ParseTreeNodeParseTree=null;
ParseTreeNodenode;
}
{
(node=Simple_Expression()
{
if(ParseTree==null)
ParseTree=node;
else
{
ParseTreeNodet;
t=ParseTree;
while(tnext!=null)
t=tnext;
tnext=node;
}
}
)*
{returnParseTree;}
<EOF>
}
ParseTreeNodeSimple_Expression():
{
ParseTreeNodenode;
ParseTreeNodet;
intop;
}
{
node=Term(){}
(
op=addop()t=Term()
{
ParseTreeNodenewNode=newParseTreeNode();
newNodenodetype=op;
newNodechild[]=node;
newNodechild[]=t;
switch(op)
{
casePlusOP:
newNodename=Operator:+;
break;
caseMinusOP:
newNodename=Operator:;
break;
}
node=newNode;
}
)*
{returnnode;}
}
intaddop():{}
{
<PLUS>{returnPlusOP;}
|<MINUS>{returnMinusOP;}
}
ParseTreeNodeTerm():
{
ParseTreeNodenode;
ParseTreeNodet;
intop;
}
{
node=Factor(){}
(
op=mulop()t=Factor()
{
ParseTreeNodenewNode=newParseTreeNode();
newNodenodetype=op;
newNodechild[]=node;
newNodechild[]=t;
switch(op)
{
caseTimersOP:
newNodename=Operator:*;
break;
caseOverOP:
newNodename=Operator:/;
break;
}
node=newNode;
}
)*
{
returnnode;
}
}
intmulop():{}
{
<TIMERS>{returnTimersOP;}
|<OVER>{returnOverOP;}
}
ParseTreeNodeFactor():
{
ParseTreeNodenode;
Tokent;
}
{
t=<ID>
{
node=newParseTreeNode();
nodenodetype=IDstmt;
nodename=timage;
returnnode;
}
|
t=<NUM>
{
node=newParseTreeNode();
nodenodetype=NUMstmt;
nodename=timage;
nodevalue=IntegerparseInt(timage);
returnnode;
}
|
<LPAREN>node=Simple_Expression()<RPAREN>
{
returnnode;
}
}
其中 SKIP 中的定义就是在进行词法分析的同时 忽略掉的记号 TOKEN 中的 就是需要在做词法分析的时候 识别的词法记号 当然 这一切都是以正则表达式来表示的
这个例子就有多个非终结符号 可以看出 我们需要为每个非终结符号写出一个过程 不同的非终结符号的识别过程中可以互相调用
以 Simple_Expression（） 过程为例 它的产生式是 Expression > Term { addop Term } 而在 javacc 的输入文件格式是它的识别是这样写的 node=Term（）{} （ op=addop（） t=Term（）{ … }）* 前面说过这里的 * 符号和正则表达式是一样的就是 次到无限次的重复 那么 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 的下载地址是同时它已经包含了很多语言的grammar模版了譬如htmlxmlpythonvb………等等可以到下载
