write a antlr4 visitor with golang

ANTLR（全名：ANother Tool for Language Recognition）是基于LL(*)算法实现的语法解析器生成器（parser generator）,用Java语言编写,使用自上而下（top-down）的递归下降LL剖析器方法。由旧金山大学的Terence Parr博士等人于1989年开始发展。目前网上的antlr示例大多为java,python,c++等,其github上虽有关于go的一个文档:go-target.md,但是是基于listener模式实现的,而本文是基于visitor实现的一个简单计算器

install antlr

安装java

antlr是基于Java开发的的,其运行依赖java环境。当前(2021年05月11日18:39:11) mac可使用homebrew命令brew install openjdk但是M1的openjdk兼容性有问题,使用antlr生成AST树的图片时总会异常退出,最终选择使用Azul Zulu的dmg二进制安装可正常运行

安装antlr

antlr官网首页已经给出了安装教程:

1
2
3
4
5
6
OS X
$ cd /usr/local/lib
$ sudo curl -O https://www.antlr.org/download/antlr-4.9.2-complete.jar
$ export CLASSPATH=".:/usr/local/lib/antlr-4.9.2-complete.jar:$CLASSPATH"
$ alias antlr4='java -jar /usr/local/lib/antlr-4.9.2-complete.jar'
$ alias grun='java org.antlr.v4.gui.TestRig'

运行示例测试

编写Expr.g4

1
2
3
4
5
6
7
8
9
grammar Expr;		
prog:	(expr NEWLINE)* ;
expr:	expr ('*'|'/') expr
    |	expr ('+'|'-') expr
    |	INT
    |	'(' expr ')'
    ;
NEWLINE : [\r\n]+ ;
INT     : [0-9]+ ;

运行antlr工具
1 2 3 4
$ antlr4 Expr.g4 $ javac Expr*.java $ grun Expr prog -gui 100+2*34
ctrl + d看到AST图片 ,说明我们antlr安装成功且可以正常运行。

golang visitor实现

antlr grammar文件编写

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
grammar Calculantlr;

// non-terminals expressed as context-free grammar (BNF)
expr:	left=expr op=('*'|'/') right=expr  # OpExpr
    |	left=expr op=('+'|'-') right=expr  # OpExpr
    |	atom=INT                           # AtomExpr
    |	'(' expr ')'                       # ParenExpr
    ;

// tokens expressed as regular expressions
INT : [0-9]+ ;
WS  :   [ \t]+ -> skip ;

使用antlr生成相关的go文件

antlr4 -Dlanguage=Go -o parser -package parser -visitor -no-listener Expression.g4 上面的命令参数作用一目了然不在赘述,需要注意的是antlr默认会生成listenner模式的相关文件,所以我们使用了-no-listener参数阻止

编写go的`main`程序

 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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
package main

import (
	"antlrtest/parser"
	"fmt"
	"strconv"

	"github.com/antlr/antlr4/runtime/Go/antlr"
)

type Visitor struct {
	parser.CalculantlrVisitor
}

func (v *Visitor) Visit(tree antlr.ParseTree) float64 {
	switch val := tree.(type) {
	case *parser.AtomExprContext:
		return v.VisitAtomExpr(val)
	case *parser.ParenExprContext:
		return v.VisitParenExpr(val)
	case *parser.OpExprContext:
		return v.VisitOpExpr(val)
	default:
		panic("Unknown context")
	}
}

func (v *Visitor) VisitAtomExpr(ctx *parser.AtomExprContext) float64 {
	fmt.Println("atom", ctx.GetText())
	i1, _ := strconv.ParseFloat(ctx.GetText(), 64)

	return i1
}

func (v *Visitor) VisitParenExpr(ctx *parser.ParenExprContext) float64 {
	fmt.Println("parent", ctx.GetText())
	tar := v.Visit(ctx.Expr())
	return tar
}

func (v *Visitor) VisitOpExpr(ctx *parser.OpExprContext) float64 {
	// fmt.Println("op")
	l := v.Visit(ctx.GetLeft())
	r := v.Visit(ctx.GetRight())
	op := ctx.GetOp().GetText()
	// if op == "+" {
	// 	return l + r
	// }
	fmt.Println("op", op)
	switch op {
	case "+":
		return l + r
	case "-":
		return l - r
	case "*":
		return l * r
	case "/":
		return l / r
	}
	return 0
}

// func (this *TreeShapeListener) EnterEveryRule(ctx antlr.ParserRuleContext) {
// 	fmt.Println(ctx.GetText())
// }

func main() {
	expression := "100 + 3 * 4 + 5"
	// input, _ := antlr.NewFileStream(os.Args[1])
	input := antlr.NewInputStream(expression)

	lexer := parser.NewCalculantlrLexer(input)

	stream := antlr.NewCommonTokenStream(lexer, 0)
	p := parser.NewCalculantlrParser(stream)

	// p.AddErrorListener(antlr.NewDiagnosticErrorListener(true))
	p.BuildParseTrees = true
	tree := p.Expr()
	var visitor = Visitor{}
	var result = visitor.Visit(tree)
	fmt.Println(expression, "=", result)
}

其它关于go的mod的一些基础操作这里不提,运行go run test.go可以看到以下输出

1
2
3
4
5
6
7
8
atom 100
atom 3
atom 4
op *
op +
atom 5
op +
100 + 3 * 4 + 5 = 117