语法分析
JavaCC 生成的是自上而下,不支持左递归,递归下降的解析器。这种解析器的优点是语法编写简单易懂,方便调试。在语法解析树上可以上下的传递属性,分支间可以也可调用。如图:
左递归是语法解析的递归的一种,详细的可以参考:左递归文法_Chaoer-CSDN博客_左递归文法
可以把左递归等价的改下为右递归处理。
语法解析重要就要理解清楚这个规则的语义,清楚了语义写规则就是信手捏来,那么动作执行就水到渠成。
四则运算的解析之路
//eg1:输入
8+6*5-4
34//输出
//eg2
8+6*5-(59-3)/7
30
//eg3
-10 //输入
-10 //输出
//eg4
-10*7 //输入
-70 //输出
四则运算大家都比较熟悉,小学二年级就可以运算。在语法解析的处理的时候,重点解决运算的优先级问题:1、乘除优先 2、括号优先。
解析树
在开始编写语法分析前,可以先画一下语法分析树整理下思路。
先从简单的开始,7+8这个运算公式,可以这样简单解析为一颗树。但是我们是学习Java的, 面向对象的思想应该是必备的。我们可以将其抽象一下,把“+”、“-”、“*”、“\”抽象一个oper符号,符号左侧的抽象成一个left对象,右侧就抽象为right对象,那么四则运行算的基础表达应该是 left oper right。现在还处理不了 7+8-5....*6 运算公式,那就利用正则表达式完善一下,left (oper rignt)*表示可以处理很长的四则运算。现在把抽象过得解析树也画出来如图:
加减与乘除的优先级问题没解决。我们就在分析一个7+2*8 公式的解析,把它画出来
这个过程其实就是先把2*4当成一个子树,那么优先级就是先去解析子树的,把子树的数据算好后返回给父级上再去运算。那么我们就稍微动点脑筋把抽象的语法树也改进一下。如图:
既然加减与乘除的优先级确定可以通过构建子树的方式去解决,那么“(四则运算)”的优先级也可以通过构建子树的方式去解决。那么我们就再分析一个7+2*(1+3) 公式的解析。如图:
关键点来了,“(四则运算)”里面的四则运算是不是跟根节点的解析过程是一致的。好了有了这个思路我们就可以对抽象语法树进行升级改造了。如图:
一级树处理加,减运算,运算的对象是二级树
二级树处理乘,除运算,运算的对象是三级树
三级树处理数字解析,以及括号里的四则运算。括号里的四则运算的解析可以调用根的解析。
到此四则运算的语法树的分析思路基本是大功告成了,可以根据思路去编写语法文件了。其实语法分析不是一次就能完成的,需要不断的改进思路,多尝试几次,才能最终定型。画语法树是帮助我们理清思路的重要方法。
Calculator.jj
//可选配置参数
options{
STATIC = false; //关闭生成java方法是静态的,默认是true
DEBUG_PARSER = true;//开启调试解析打印,默认是false
JDK_VERSION = "1.8";//生产java时使用jdk版本,默认1.5
}
//固定格式
PARSER_BEGIN(Calculator)
//像java一样的包名定义,生成的java文件会带上此包名
package com.javacc.calculator;
//导入需要引用java
import cn.hutool.core.date.DateUtil;
import java.io.StringReader;
public class Calculator {
//可以再里面定义初始化信息,字符串接收方式,异常处理..
public Calculator(String expr){
this(new StringReader(expr));
}
}
//固定格式
PARSER_END(Calculator)
//词法定义
//SKIP是一种词法 要跳过忽略的字符串
SKIP : { " " | "\t" | "\n" }
TOKEN : {
<NUMBER : <DIGITS>
| <DIGITS> "." <DIGITS>
>
|
//#开头则表示内部Token,只可以在词法中使用,不能在语法中引用
<#DIGITS :(["0"-"9"])+>
}
TOKEN : {
< LPAREN: "(" >
| < RPAREN: ")" >
| < ADD : "+" >
| < SUBTRACT : "-" >
| < MULTIPLY : "*" >
| < DIVIDE : "/" >
}
//为了调试方便将换行定义为一个特殊的token
TOKEN : { < EOL : "\n" | "\r" | "\r\n" > }
//定义语法
double calc():
{
double left;
double right;
}
{
left = mutlOrDiv()
(<ADD> right = mutlOrDiv() {left += right;}
| <SUBTRACT> right = mutlOrDiv() {left = left - right;}
)*
{
return left;
}
}
double mutlOrDiv():
{
double left;
double right;
}
{
left = parseBase()
(<MULTIPLY> right = parseBase() {left *= right ;}
| <DIVIDE> right = parseBase() {left = left/right;}
)*
{
return left;
}
}
double parseBase() :
{
Token t = null;
double num;
}
{
t = <NUMBER> {return Double.parseDouble(t.image);}
| <LPAREN> num = calc() <RPAREN> {return num;}
//处理负数
| <SUBTRACT> t = <NUMBER> {return 0-Double.parseDouble(t.image); }
}
实现的思路几乎跟上面的语法分析的是一致,就是对parseBase处理中增加了对负数的处理。
测试类CalculatorTest
public class CalculatorTest {
public void testCalc() throws Exception {
boolean isBeak = false;
BufferedReader reader;
String expr ="";
com.javacc.calculator.Calculator calculator ;
while (!isBeak){
System.out.println("please input four arithmetic expressions , input quit exit");
reader = new BufferedReader(new InputStreamReader(System.in));
expr = reader.readLine();
if(!"quit".equals(expr)){
calculator = new Calculator(expr);
double res = calculator.calc();
System.out.println(res);
}else {
isBeak =true;
}
}
}
public static void main(String[] args) {
CalculatorTest calculatorTest = new CalculatorTest();
try {
calculatorTest.testCalc();
} catch (Exception e) {
e.printStackTrace();
}
}
}
测试1效果:
测试2效果:
上一篇:JAVACC使用总结(二):词法TOKEN_IT不码农的博客-CSDN博客