ANTLR 语言识别工具

发表于 更新于 分类于 ， 阅读次数： Waline： 本文字数： 1.7k 阅读时长 ≈ 6 分钟

实验目的

  1. 了解 ANTLR 语言识别工具，安装 ANTLR 环境，熟悉 ANTLR 的使用。
  2. 掌握使用 ANTLR 构建的语法分析器和树解析器分析语言，通过 ANTLR 实现语法分析过程。

实验条件

  1. Windows 10 专业版
  2. JDK 1.8 版本（64 位，版本号为 1.8.0_202）
  3. ANTLR 环境 ——ANTLR 4

实验内容

安装 ANTLR

个人所用的集成开发环境中提供 ANTLR 插件的安装，故可直接进入插件下载功能中下载该插件。运行时环境配置过程和安装过程不再赘述。

安装以后，下方工具栏会多出两个窗口：ANTLR Preview 和 Tool Output。

Preview 中可以显示 Parse tree，从而省去了在控制台中输入 -gui 命令的麻烦。

使用 ANTLR 实现实数的四则运算

要求

创建 ANTLR 语法文件 expr.g4，解析如赋值语句 a = 5.5 和表达式 a+4*3÷2-1 这样的语句。

  • 要验证所编写的文法是否正确，可使用 TestRig 测试语法，在 CMD 中输入 -gui 可直观展示其语法分析树。
  • 创建 expr 文件（如 test.expr，输入一个表达式）检验程序是否能够正确运行和计算四则算式。

  1. 文法设计

    1
    2
     
    E -> E OP E|VAR = E|E'; E'-> D; OP: [+|-|*|/]; D:[0-9]+; VAR:[a-zA-Z]+;

    由此编写的 expr.g4 文件如下：（还考虑了一些换行及空格因素）

    expr.g4
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
     
    grammar expr; 
    exprs : setExpr | calcExpr ; 
    setExpr : id=ID '=' num=NUMBER ; 
    calcExpr: calcExpr op=(MUL | DIV) calcExpr | calcExpr op=(ADD | SUB) calcExpr | factor ; 
    factor: (sign=(ADD | SUB))? num=NUMBER // 计算因子可以是一个正数或负数 
                               | id=ID // 计算因子可以是一个变量 ; 
    WS : [ \t\n\r]+ -> skip ; 
    ID : [a-zA-Z]+ ; 
    NUMBER : [0-9]+('.'([0-9]+)?)? ; 
    ADD : '+' ; 
    SUB : '-' ; 
    MUL : '*' ; 
    DIV : '/' ;

  2. 运行结果

控制台工具显示如下

Main 函数如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
public static void main(String[] args){ 
	String input_string = "a=5.5";
	InputStream is = System.in; 
	try{ 
		ANTLRInputStream input = new ANTLRInputStream(input_string); 
		exprLexer lexer = new exprLexer(input); 
		CommonTokenStream tokens = new CommonTokenStream(lexer); 
		exprParser parser = new exprParser(tokens);
		ParseTree tree = parser.exprs(); 
		Visitor visitor = new Visitor(); 
		System.out.println(visitor.visit(tree)); 
	} catch(IOException ioe){ 
		ioe.printStackTrace(); 
	} 
}

运行结果如下

本次测试的式子为 a+4*3/2-1

控制台工具显示如下

Main 函数如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
public static void main(String[] args){ 
	String input_string = "a+4*3/2-1";
	InputStream is = System.in; 
	try{ 
		ANTLRInputStream input = new ANTLRInputStream(input_string); 
		exprLexer lexer = new exprLexer(input); 
		CommonTokenStream tokens = new CommonTokenStream(lexer); 
		exprParser parser = new exprParser(tokens);
		ParseTree tree = parser.exprs(); 
		Visitor visitor = new Visitor(); 
		System.out.println(visitor.visit(tree)); 
	} catch(IOException ioe){ 
		ioe.printStackTrace(); 
	} 
}
从输出来看，对语法树的遍历过程几乎遍及了句子的每一个结点。由于最后得到的句型是一个类似于 a + <数字> 的格式，所以它输出 NaN，与预期一致。

a 是与前一个赋值语句分开输入的，所以它并没有被定义值

本次测试的式子为 1+4.5*2-3/3

Main 函数代码类似，控制台工具显示如下

代码输出结果如下

得到了正确的输出结果，证明我们写的语法解析是正确的。

  1. 针对除 0 错误，程序可以顺利显示出 Infinity，没有中断程序
  2. 输入过长也不会中断程序
  3. 符号错误需要单独处理

这说明符号错误需要单独处理，java 中可以使用 try-catch 来完成这项工作。除此之外，也可从前端角度考虑，提前检验用户输入。

总结

这个解析过程是怎么实现的呢？

  • 在生成 ANTLR 识别文件时，实际上生成了很多个 java 和 token 源文件。

  • 有两个 tokens 文件和六个 java 文件，Listener 和 Visitor 是两个接口，Listener 中定义了一些退出或进入一个表达式中所进行的语法动作，Visitor 中定义了遍历语法树中项目的返回动作，一个语法项对应一个 visit 函数。具体由 xxBaseListener 或 xxBaseVisitor 来实现。默认状态下，所有的实现都是空的，我们可以扩展 xxBase[Listener|Visitor] 类，自己定义语法动作。本实验中，只需要实现 Visitor 的内容即可，不过由于上下文的关系，我们需要自建一个 Context 类，负责上下文内容的保存和识别。

  • 重写 visit 函数：

    1
    public <你需要的返回值> visit<A>(xxParser.<A>Context ctx)

  • .tokens 文件中将语法常量对应了一个整数数值，方便常量的建立。.interp 文件则记录了字面值。

  • Parser 中，对每一个语法变量，生成了很多上下文相关的方法（xxContext）。其中的某些常量在前面所述的.tokens 文件中可以找到。

  • Lexer 中，则存储了字面量及其相关方法，某些内容可在.interp 文件中找到。

  • 而所有开头的 xx 来自于语法文件第一行的 grammar xx，即为语法名。

  • Visitor 实现完成后，在主函数中建立 visitor 对象，调用 visit 语法树方法，将用户输入作为参数传入，其返回值即为语法分析结果。

visitor.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
public class Visitor extends exprBaseVisitor<Double>{
	@Override 
	public Double visitExprs(exprParser.ExprsContext ctx){ 
		//System.out.println("visit exprs"); 
		return visit(ctx.getChild(0)); 
	}
	@Override 
	public Double visitSetExpr(exprParser.SetExprContext ctx){
		Context.getInstance().setContext(ctx.id.getText(), ctx.num.getText());
		System.out.println("Assign operation in current line:" + ctx.id.getText() + " = " + ctx.num.getText());
		return null;
	}
	@Override 
	public Double visitCalcExpr(exprParser.CalcExprContext ctx){ 
		//System.out.println("visit calc expr "); 
		int cc = ctx.getChildCount(); 
		if (cc == 3) { 
			switch (ctx.op.getType()) { 
				case exprParser.ADD:
					return visit(ctx.calcExpr(0)) + visit(ctx.calcExpr(1));
				case exprParser.SUB:
					return visit(ctx.calcExpr(0)) - visit(ctx.calcExpr(1));
				case exprParser.MUL:
					return visit(ctx.calcExpr(0)) * visit(ctx.calcExpr(1));
				case exprParser.DIV:
					return visit(ctx.calcExpr(0)) / visit(ctx.calcExpr(1));
			}
		}
		else if(cc == 1)
		{
			return visit(ctx.getChild(0));
		}
		throw new RuntimeException();
	}
	@Override 
	public Double visitFactor(exprParser.FactorContext ctx){ 
		//System.out.println("visit factor"); 
		int cc = ctx.getChildCount(); 
		if (cc == 3) { 
			return visit(ctx.getChild(1)); 
		} else if (cc == 2) { 
			if (ctx.sign.getType() == exprParser.ADD)
				return Double.valueOf(ctx.getChild(1).getText());
			if(ctx.sign.getType() == exprParser.SUB) 
				return -1 * Double.valueOf(ctx.getChild(1).getText());
		}
		else if(cc == 1){
			if(ctx.num != null) return Double.valueOf(ctx.getChild(0).getText());
			if(ctx.id != null) return Context.getInstance().getValue(ctx.id.getText());
		}
		throw new RuntimeException();
	}
}
  • 目前实现的版本中，可以正确地进行运算，但还没有实现连续赋值功能，也没有考虑到多语句的分隔及分开解析，例如输入 "a=1 a+1" 后不能得到 2，可能需要修改 Context 类和 Visitor 类中的代码，使其可以记录上下文信息，将 a 的值存入暂存区。