从开始学计算理论,就对形式语言,编译原理很感兴趣,所以大学对这门课学的也算是最好了。自己也实现过一些简单的词法分析器之类的东西,不过也都是学习目的的,质量一般
后来一直在Linux学习,对lex/yacc研究过一点时间,设计过一个小的脚本引擎,可以做一些比较复杂的数学运算,这个可以参考我的这篇博客<hoc>。工作以后,平台
变成了java,跟C渐渐的离得远了,也喜欢上java这个提供语言级别的面向对象的语言以前的一些东西用顺手了,一时习惯还改不过来,于是就开始找lex/yacc的替代品。
研究过一段时间的antlr,觉得还行,特别是那个GUI做的非常好,但是跟lex/yacc在用法上还是有些差别的,最近才遇到了javacc,觉得跟lex/yacc的写法相当像,就试着
写了一个简单的桌面计算器(desktop-calculator),大家可以参考一下。 (从下载到javacc.zip到写出这个计算器,大约花了我一个下午的时间,所以你可以很快
的学会javacc,并在实际中应用。)用这类工具的好处是,只要你理解形式语言,那么就可以很方便的做出一个分析起来,而不用关心其实现细节(如词法分析等部分是十分
枯燥且无意义的)
一来这是一个比较经典的例子,通过它的学习,可以迅速掌握一个编译器生成器,或者叫语言解析器生成器。二来最近项目中用到了一些类似的东西,正好趁此机会记下来
以便将来参考。
四则运算的计算器的规则非常清晰,可以看一下这个巴克斯范式(BNF)
expr ::= term ((+|-) term)*
term ::= factor ((*|/) factor)*
factor ::= number | expr
number ::= [0-9]+...
形式语言的好处就在于其清晰,准确和强大。如果你对正则表达式比较收悉,那么可以很容易掌握形式语言。(正则表达式其实就是一个精简而强大的形式语言实例)
首先,我们需要定义在文法描述中需要用到的所有记号(token),这是分析器能认识到的最小单元
TOKEN:{
<ADD : "+">
| <SUB : "-">
| <MUL : "*">
| <DIV : "/">
| <LPAREN : "(">
| <RPAREN : ")">
| <NUMBER :
["0"-"9"] (["0"-"9"])*
| (["0"-"9"])+ "." (["0"-"9"])* (<EXPONENT>)?
| "." (["0"-"9"])+ (<EXPONENT>)?
| (["0"-"9"])+ <EXPONENT> >
| <#EXPONENT: ["e","E"] (["+","-"])? (["0"-"9"])+ >
}
javacc的记号描述很简单,就是普通的正则表达式,当然用引号引起来的简单单词也算是正则表达式,如记号ADD,就是"+",这样,当解析器遇到"+"时就返回一个ADD记号,方便在内部使用。
这里详细说一下NUMBER记号,数字怎么表示呢?
我们用自然语言可以描述成:以0到9中的任一个数字开头,后边可以有任意多位(包括0位)数字(此为整数),或者以至少一位数字,后边跟一个小数点,然后又有任意多位的数字,如果使用科学 计数法,则这个数字串后边还可以跟一个E,E后边又可以有正号(+)或者负号(-),也可以没有,然后,后边又是至少一位数字,或者……
可以看到,自然语言的描述冗长且不容易理解,我们看看形式语言的描述:首先定义一些符号的意义,如
"|" |
表示或者 |
0-9 |
表示0到9的一个数字 |
[] |
表示一个区间 |
"?" |
表示其前的区间中的元素重复一次或零次 |
"+" |
表示其前的区间中的元素重复至少一次 |
"*" |
表示其前的区间中的元素重复零次或多次 |
() |
表示一个分组,是一个整 |
好了,有了这些定义,我们再看看如何用形式语言描述一个浮点数或者整数:
number ::= [0-9]([0-9])* | [0-9]+ '.' ([0-9])+ exponent?
| '.' ([0-9])+ exponent?
| ([0-9])+ exponent?
exponent ::= [e,E]([+,-])?([0-9])+
可以看到,形式语言在描述这种抽象概念上比自然语言要好得多。一旦掌握了形式语言就可以很容易的理解各种复杂的规则。
词法分析器的一个功能就是剔除源码中的空白字符,比如,空格,制表符,回车换行等
SKIP:{
" " | "\t" | "\r" | "\n"
}
有了BNF,我们看看在javacc中,如何表现这些规则:
void expr():{}
{
term()((<ADD>|<SUB>)term())*
}
void term():{}
{
factor()((<MUL>|<DIV>)factor())*
}
void factor():{}
{
<NUMBER>|
<LPAREN>expr()<RPAREN>
}
javacc基本忠实的体现了BNF的规则定义,当然,现在这个解析器的文法部分(词法分析和语法分析) 已经算是结束了,但是它还不能完成任何计算,因为它没有语义的定义部分,即当发现了 此语法现象后该做什么是没有定义的。
相信大家都已经注意到,每个非终结符后边都有两个大括号{},第一个目前为空。在javacc中,每个非终结符都最终会被翻译成一个方法,(至于怎么翻译的,你可以自己看看它生成的代 码,当年我曾痛苦在yacc生成的一堆yy_*中徜徉过一段时间,现在是实在看不下去了,javacc生成的代码中到处都是jj_*,唉,一个yy,一个jj,生成的代码是看不成了), 第一个空的大括号中即为将来你自己填写的一些关于这个方法的一些临时变量,包括返回值等信息。
好了,我们看看加入了语义解释后的代码:
double expr():
{
double temp = 0;
double first, second;
}
{
//你可以在非终结符前插入变量,等号等,在其后可以插入普通的java代码
//插入代码后看起来可能不够清晰,可以参看上边的形式定义
first=term(){temp = first;}
(<ADD>second=term(){temp = first + second;}|
<SUB>second=term(){temp = first - second;})*
{return temp;}//最后,应当返回某值
}
double term():
{
double temp = 0;
double first, second;
}
{
first=factor(){temp = first;}
(<MUL>second=factor(){temp = first * second;}|
<DIV>second=factor(){temp = first / second;})*
{return temp;}
}
double factor():
{
double temp = 0;
Token token;
}
{
token=<NUMBER>{
return Double.parseDouble(token.image);
} | <LPAREN> temp=expr() <RPAREN>{
return temp;
}
}
好了,主体部分已经建立好了,我们再来看看声明信息等(形式语言的学习是重点,其余的 都比较简单易学,而且不同的cc都提供大同小异的功能)
PARSER_BEGIN(CalcParser)
import java.io.StringReader;
import java.io.Reader;
public class CalcParser{
public CalcParser(String expr){
this((Reader)(new StringReader(expr)));
}
public static void main(String[] args){
try{
CalcParser parser = new CalcParser(args[0]);
System.out.println(parser.expr());
}catch(Exception e){
System.out.println("error : "+e.getMessage());
}
}
}
PARSER_END(CalcParser)
每个分析器需要一个名字,这个名字定义在PARSER_BEGIN(xxx)中,而且应保证与下面的类声明保持一致:
public class xxx{}
现在,我们可以用javacc提供的命令行程序来生成我们的计算器,需要注意的是,javacc生成的是java源码,且不再依赖于javacc,你可以将你的分析器源码放在任何地方使用。
$ javacc CalcParser.jj(你看看这文件名后缀)
可以看到有类似的输出;
写道
Java Compiler Compiler Version 4.2 (Parser Generator)
(type "javacc" with no arguments for help)
Reading from file CalcParser.jj . . .
File "TokenMgrError.java" does not exist. Will create one.
File "ParseException.java" does not exist. Will create one.
File "Token.java" does not exist. Will create one.
File "SimpleCharStream.java" does not exist. Will create one.
Parser generated successfully.
你现在可以试着输入一些表达式让计算器进行计算了。(事例结果见后)
如果想要加入一些别的功能,比如,计算表达式的正弦,余弦函数?很简单,我们可以使用 java.lang.Math中提供的一些数学函数。
对规则稍事修改,即可完成我们的需求。当然,这个计算器的还是比较简单的,比如,不能回溯(这个以后再说),不支持负数,不支持幂计算。但是,如果通过此文,你对形式语言有了比较 好的理解的话,这些问题都是很容易解决的。
下面这些代码是我再上边的这个四则运算计算器的基础上加入了少量规则而成的一个微型函数计算器,其表达式格式类似于JSP中的EL表达式,你可以对其进行扩展,从而使之更加有趣。
PARSER_BEGIN(CalcParser)
import java.io.StringReader;
import java.io.Reader;
public class CalcParser{
public CalcParser(String expr){
this((Reader)(new StringReader(expr)));
}
public static void main(String[] args){
try{
CalcParser parser = new CalcParser(args[0]);
System.out.println(parser.elexpr());
}catch(Exception e){
System.out.println("error : "+e.getMessage());
}
}
}
PARSER_END(CalcParser)
//声明到此结束
SKIP:{
" " | "\t" | "\r" | "\n"
}
TOKEN:{
<ADD : "+">
| <SUB : "-">
| <MUL : "*">
| <DIV : "/">
| <MOD : "%">
| <LPAREN : "(">
| <RPAREN : ")">
| <NUMBER :
["0"-"9"] (["0"-"9"])*
| (["0"-"9"])+ "." (["0"-"9"])* (<EXPONENT>)?
| "." (["0"-"9"])+ (<EXPONENT>)?
| (["0"-"9"])+ <EXPONENT> >
| <#EXPONENT: ["e","E"] (["+","-"])? (["0"-"9"])+ >
| <EXPRPREFIX: "${">
| <EXPRSUFFIX: "}">
| <SIN: "sin">
| <COS: "cos">
}
//记号部分声明到此结束,下面是语法声明,包括语义解释
double elexpr():
{ double temp = 0; }
{
<EXPRPREFIX>temp=expr()<EXPRSUFFIX>
{return temp;}
}
double expr():
{
double temp = 0;
double first, second;
}
{
first=term(){temp = first;}
(<ADD>second=term(){temp = first + second;}|
<SUB>second=term(){temp = first - second;})*
{return temp;}
}
double term():
{
double temp = 0;
double first, second;
}
{
first=factor(){temp = first;}
(<MUL>second=factor(){temp = first * second;}|
<DIV>second=factor(){temp = first / second;})*
{return temp;}
}
double factor():
{
double temp = 0;
Token token;
}
{
token=<NUMBER>{
return Double.parseDouble(token.image);
} | <LPAREN> temp=expr() <RPAREN>{
return temp;
} |
<SIN><LPAREN>temp=expr()<RPAREN>{
return java.lang.Math.sin(temp);
} |
<COS><LPAREN>temp=expr()<RPAREN>{
return java.lang.Math.sin(temp);
}
//如果有兴趣,可以加入更多的java.lang.Math中的数学函数,
//当然,你也可以加入自己实现的一些方法,如返回前一个运算结果
//记录历史信息等等。
}
演示计算过程,如:
[juntao@juntao CalcParser]$ java CalcParser '${sin(1/2)*cos(1/4) + 12.3}'
12.418611776418413
[juntao@juntao CalcParser]$ java CalcParser '${(12+45)*(3-23)}'
-1140.0
[juntao@juntao CalcParser]$ java CalcParser '${3e-5}'
3.0E-5
[juntao@juntao CalcParser]$ java CalcParser '${sin(3/4)/2}'
0.34081938001166706
关于JJTree后边再说吧,最重要的还是上边提到的形式语言,它是一切的基础。
分享到:
相关推荐
本程序实现一个四则混合运算,用户只需要输入四则混合运算表达式,程序自动计算, 可以一次计算一个表达式,也可以批量计算多行表达式,而且适合商业计算精度要求。 由于该程序依赖一个清屏功能cls.dll,使用32位win7...
对于初学者来说,理解并调试JavaCC生成的代码可能有一定难度,因为它们通常是自动产生的,并且内部实现较为复杂。但是,通过学习JavaCC,你可以深入理解编译原理和解析技术,这对于提升编程能力,特别是处理语言解析...
在本项目中,"JavaCC实现MiniC语言的编译"是一个实践性的任务,目的是利用JavaCC来构建一个小型的C语言编译器——MiniC。这个编译器能够解析、理解和转换C语言的基本元素,如变量声明、表达式、控制结构等。 1. **...
总的来说,"CMM语言解释器JAVA实现(javacc5.0)"项目是一个典型的编译原理实践,它涉及到语言设计、解析技术以及程序执行等多个方面的知识。通过这个项目,开发者可以深入理解编程语言的底层工作原理,同时也能提升...
这个增强版的实现是基于JAVA语言,并利用了javacc5.0工具来完成语法解析和词法分析的部分。下面将详细讨论相关知识点。 1. **CMM语言**:CMM可能代表一种特定的编程模型或领域专用语言(DSL),用于解决特定问题。...
在Android和Java中实现计算器是一项常见的编程任务,它涉及到用户界面设计、事件处理以及数学运算逻辑。本项目提供了这样一个计算器的实现,具有处理合法输入、支持负数计算、多表达式处理以及友好的用户交互特性。 ...
在这个特定的场景中,我们关注的是如何使用JavaCC来实现CMM(可能是“计算机动画建模语言”或“计算机辅助制造”等特定领域的语法)的语法分析。下面我们将深入探讨JavaCC的工作原理、CMM语法分析的关键步骤以及如何...
这个项目“基于JavaCC的C语言编译器前端实现”显然旨在教授如何使用JavaCC来创建一个C语言的编译器前端。 在编译器设计中,前端主要负责词法分析、语法分析和语义分析。词法分析是将源代码转换为一系列的单词项...
JavaCC可以帮助开发者识别并提取这些关键词,从而实现对输入语句的深入理解和处理。例如,如果你正在创建一个简单的编程语言解析器,JavaCC可以帮助你识别像"if"、"for"、"while"这样的控制结构关键词。 面对对象...
在实际应用中,JavaCC被广泛用于实现Java、SQL等语言的解析器,以及XML、JSON等数据格式的解析工具。由于其强大的能力和广泛的社区支持,JavaCC成为了Java开发人员构建自定义解析解决方案的首选工具之一。 总结起来...
这个实习项目旨在让你深入理解编译原理,并通过实际操作来构建一个小型编译器。在JavaCC的帮助下,你可以定义语言的文法,然后它会自动生成处理这些文法的Java类。 首先,我们需要了解编译原理的基础知识。编译器是...
为了更好地理解如何使用JavaCC构建编译器,我们可以设计一个简单的命令行计算器作为示例。 - **定义词法规则**:首先要定义计算器能够识别的词汇单位,如数字、加号、减号等。 - **定义文法规则**:接下来需要定义...
- JavaCC允许用户在生成的解析器代码中添加额外的逻辑,以便实现更复杂的功能,如语义检查、代码生成等。 - 用户可以通过在语法文件中嵌入Java代码片段来实现这一点。 4. **测试与调试**: - 在解析器代码生成后...
JavaCC(Java Compiler Compiler)是Java语言的一个开源工具,用于生成词法分析器(lexical analyzers)和语法分析器(parsers)。它基于LL(k)语法解析策略,允许开发者使用简洁的BNF(巴科斯范式)语法来定义语言或...
这通常通过添加“动作”(Action)到文法中实现。 7. **错误处理**:在解析过程中,我们可能会遇到无法解析的输入或者语法错误。JavaCC提供了处理这些错误的方法,如错误恢复策略,以确保解析过程的健壮性。 8. **...
本例中的简单计算器程序展示了如何利用JavaCC来定义语法规则并实现基本的数学运算。无论是对于想要深入了解编译器工作原理的学习者,还是希望创建自己专属语言的开发者来说,JavaCC都是一个不可或缺的工具。
5. **集成到项目**:将生成的解析器类集成到实际的Java项目中,实现对特定语言或数据格式的解析功能。 总之,JavaCC Eclipse插件是开发者构建复杂解析器和词法分析器的强大工具,它简化了在Eclipse中使用JavaCC的...
JavaCC会读取这些文法文件,并生成相应的Java类,这些类可以解析符合文法的输入字符串,从而实现对特定语言的解析。 使用JavaCC的优势在于其灵活性和可扩展性。它支持左递归消除、优先级和结合性、错误恢复策略等...
JavaCC和JJTree是用于构建解析器和抽象语法树(AST)的工具,常用于编译器设计和解析复杂语法的场景。它们是Java语言的版本,类似于其他编程语言中的YACC和LEX。 1. **JavaCC**: - JavaCC(Java Compiler ...