从lex&yacc说到编译器--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做实际问题的时候遇到什么问题,不妨上去找找专家.

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

国内最棒的Google Android技术社区（eoeandroid），欢迎访问！

《银河系列原创教程》发布

《Java Web开发速学宝典》出版，欢迎定购