JAVACC使用总结(三):通过四则运算解析,初探语法分析

语法分析

JavaCC 生成的是自上而下,不支持左递归,递归下降的解析器。这种解析器的优点是语法编写简单易懂,方便调试。在语法解析树上可以上下的传递属性,分支间可以也可调用。如图:

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、括号优先。

解析树

在开始编写语法分析前,可以先画一下语法分析树整理下思路。

JAVACC使用总结(三):通过四则运算解析,初探语法分析

先从简单的开始,7+8这个运算公式,可以这样简单解析为一颗树。但是我们是学习Java的, 面向对象的思想应该是必备的。我们可以将其抽象一下,把“+”、“-”、“*”、“\”抽象一个oper符号,符号左侧的抽象成一个left对象,右侧就抽象为right对象,那么四则运行算的基础表达应该是 left oper right。现在还处理不了 7+8-5....*6 运算公式,那就利用正则表达式完善一下,left (oper rignt)*表示可以处理很长的四则运算。现在把抽象过得解析树也画出来如图:

JAVACC使用总结(三):通过四则运算解析,初探语法分析

加减与乘除的优先级问题没解决。我们就在分析一个7+2*8 公式的解析,把它画出来

JAVACC使用总结(三):通过四则运算解析,初探语法分析

这个过程其实就是先把2*4当成一个子树,那么优先级就是先去解析子树的,把子树的数据算好后返回给父级上再去运算。那么我们就稍微动点脑筋把抽象的语法树也改进一下。如图:

JAVACC使用总结(三):通过四则运算解析,初探语法分析

既然加减与乘除的优先级确定可以通过构建子树的方式去解决,那么“(四则运算)”的优先级也可以通过构建子树的方式去解决。那么我们就再分析一个7+2*(1+3) 公式的解析。如图:

JAVACC使用总结(三):通过四则运算解析,初探语法分析

 关键点来了,“(四则运算)”里面的四则运算是不是跟根节点的解析过程是一致的。好了有了这个思路我们就可以对抽象语法树进行升级改造了。如图:

JAVACC使用总结(三):通过四则运算解析,初探语法分析

 一级树处理加,减运算,运算的对象是二级树

二级树处理乘,除运算,运算的对象是三级树

三级树处理数字解析,以及括号里的四则运算。括号里的四则运算的解析可以调用根的解析。

到此四则运算的语法树的分析思路基本是大功告成了,可以根据思路去编写语法文件了。其实语法分析不是一次就能完成的,需要不断的改进思路,多尝试几次,才能最终定型。画语法树是帮助我们理清思路的重要方法。

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效果:

JAVACC使用总结(三):通过四则运算解析,初探语法分析

JAVACC使用总结(三):通过四则运算解析,初探语法分析 

 测试2效果:

JAVACC使用总结(三):通过四则运算解析,初探语法分析

 

上一篇:JAVACC使用总结(二):词法TOKEN_IT不码农的博客-CSDN博客

上一篇:郑州轻工业大学OJ1135: 算菜价


下一篇:【51nod】1634 刚体图