基于ANTLR实现的简单绘图语言解释器

Posted on | Post modified:
Words count in article: 2.8k

本文用于记录使用ANTLR实现一个简单绘图语言解释器的过程

一、实验环境

本节说明完成本次实验时所用的开发环境。

1.1软件环境

操作系统： MacOS High Sierra 版本10.13.6

工具：

  • ANTLR 版本4.7.2
  • VS Code 版本 1.33.1
  • java 版本 1.8.0_121

1.2 硬件环境

MacBook Pro(Retina, 13-inch, Early 2015)

处理器 2.7 GHz Intel Core i5

内存 8 GB 1867 MHz DDR3

启动磁盘 Macintosh HD

图形卡 Intel Iris Graphics 6100 1536MB

二、实验内容

基本功能：

  1. 实现课件“上机ANTLR与漏洞分析.ppt”中规定的功能。

  2. 用ANTLR构造所需的词法分析器、语法分析器。

  3. 基于ANTLR，构造分析树的遍历器。它是语义计算模块，即解释器的后端。遍历器可选用 Listener 模式，也可选用 Visitor 模式，也可同时实现两种模式。

  4. 手工编写其他所需程序，包括主程序、语义分析与计算辅助程序等。

扩展功能：

  1. 实现绘图操作，即：在屏幕上绘制图形，并显示出来。

  2. 扩展函数绘图语言的功能，包括但不限于增加绘图效果的语句，如设置绘图颜色、线条粗细（点的大小）等等。

  3. 能够检查输入（即函数绘图语言编写的源程序）中存在的语义错误/漏洞，如死循环、无效参数、除数为0、要绘制的点超出窗口边界等，并进行错误报告。

  4. 支持输入中有用户自定义变量（类型均为double），并在后续的表达式中引用这些变量。

​

三、方法/思路

3.1模块划分

ANTLR源文件：

DrawGraph.g4

根据ANTLR源文件自动生成的代码：

DrawGraph.interp、DrawGraph.tokens、DrawGraphBaseListener.java、 DrawGraphLexer.interp、DrawGraphLexer.java、DrawGraphLexer.tokens、DrawGraphListener.java、DrawGraphParser.java

JAVA编写：

前端源代码：FrontEnd.java

后端源代码：BackEnd.java

主程序源代码：DrawLangMain.java

绘图相关源代码：BaseUI.java、UiPixelAttrib.java

监听者模式的遍历器：DrawerListener.java

3.2重要数据结构及算法

  1. ANTLR源代码中出现的辅助定义:

    1
    2
    3
    4
    5
    fragment A: [aA];
    fragment B: [bB];
    fragment C: [cC];
    ...   
    fragment Z: [zZ];

    通过引入该辅助定义，可以方便地定义大小写不敏感的简单绘图语言解释器，而不必在文法规则中繁琐地到处规定[aA]此类的形式

  2. 数据结构UiPixelAttrib，负责管控绘制像素的信息，具体包含RGB数值、像素点的大小

  3. 继承了DrawGraphBaseListener.java类的用户自定义监听者类DrawerListener.java，其中通过对ANTLR自动生成的标签接口进行重载，定义了语义对应的语法动作，以实现语法制导翻译。

四、源代码

4.1文件1: DrawGraph.g4

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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
grammar DrawGraph;

options {
    language=Java;
}

PLUS: '+';
MINUS: '-';
DIV: '/';
MUL: '*';
POWER: '**';
SEMICO: ';';
L_BRACKET: '(';
R_BRACKET: ')';
COMMA: ',';

CONST_ID: Integer
    | Real
    | NamedConst
    ;
fragment Integer: Digits;
fragment Digits: [0-9]+;
fragment Real: Fraction Exponent?
    | Digits Exponent
    ;
fragment Fraction: Digits? '.' Digits
    | Digits '.'
    ;
fragment Exponent: E [+-]? Digits;
fragment NamedConst: P I
    | E
    ;
ORIGIN: O R I G I N;
SCALE: S C A L E;
ROT: R O T;
IS: I S;
TO: T O;
STEP: S T E P;
DRAW: D R A W;
FOR: F O R;
FROM: F R O M;
RED: R E D;
BLUE: B L U E;
GREEN: G R E E N;
COLOR: C O L O R;
T1: T;
WS : [ \t\f\r\n]+ -> skip;
COMMENT: (
    '//' ~[\r\n]*
    | '--' ~[\r\n]*
    | '/*' .*? '*/'
) -> skip;
ID : [a-zA-Z_][a-zA-Z_0-9]*;
ErrText: .;
fragment A: [aA];
fragment B: [bB];
fragment C: [cC];
fragment D: [dD];
fragment E: [eE];
fragment F: [fF];
fragment G: [gG];
fragment H: [hH];
fragment I: [iI];
fragment J: [jJ];
fragment K: [kK];
fragment L: [lL];
fragment M: [mM];
fragment N: [nN];
fragment O: [oO];
fragment P: [pP];
fragment Q: [qQ];
fragment R: [rR];
fragment S: [sS];
fragment T: [tT];
fragment U: [uU];
fragment V: [vV];
fragment W: [wW];
fragment X: [xX];
fragment Y: [yY];
fragment Z: [zZ];
program: (statement SEMICO)* EOF
    ;
statement: originStatement
    | scaleStatement
    | rotStatement
    | forStatement
    | colorStatement
    | variableStatement
    ;
variableStatement: ID '=' expr #Assign
    ; 
originStatement: ORIGIN IS L_BRACKET expr COMMA expr R_BRACKET;
scaleStatement: SCALE IS L_BRACKET expr COMMA expr R_BRACKET;
rotStatement: ROT IS expr;
forStatement: FOR T1 FROM expr TO expr STEP expr DRAW L_BRACKET expr COMMA expr R_BRACKET;
colorStatement: COLOR IS BLUE
    | COLOR IS GREEN
    | COLOR IS RED
    | COLOR IS L_BRACKET expr COMMA expr COMMA expr R_BRACKET
    ;
expr: <assoc=right> expr POWER expr #PowerExpr
    | (PLUS|MINUS) expr #UnaryExpr
    | expr (MUL|DIV) expr #MulDivExpr
    | expr (PLUS|MINUS) expr #PlusMinusExpr
    | CONST_ID #Const
    | T1 #VarT
    | ID L_BRACKET expr R_BRACKET #FuncExpr
    | L_BRACKET expr R_BRACKET #NestedExpr
    | ID #VarExpr
    ;

4.2 文件2: BackEnd.java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import org.antlr.v4.runtime.tree.*;
import org.antlr.v4.runtime.*;
public class BackEnd {
    protected ParseTree tree = null;
    protected BaseUI theUI = null;
    public BackEnd(ParseTree t, BaseUI ui) {
        tree = t; 
        theUI = ui;
    }
    public void run() {
        ParseTreeWalker walker = new ParseTreeWalker();
        DrawerListener eval = new DrawerListener();
        eval.setUI(theUI);
        walker.walk(eval, tree);
    }
}

4.3 文件3：FrontEnd.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
import java.io.FileInputStream;
import java.io.InputStream;
import org.antlr.v4.runtime.*;
import org.antlr.v4.runtime.tree.ParseTree;
public class FrontEnd {
    protected ParseTree tree = null;
    protected String theFilePath;

    public FrontEnd(String filePath) {
        theFilePath = filePath;
    }
    public ParseTree getTree() {
        return tree;
    }

    public int doParse() throws Exception {
        java.io.InputStream is = System.in;
        if (theFilePath != null) is = new FileInputStream(theFilePath);
        ANTLRInputStream input = new ANTLRInputStream(is);
        DrawGraphLexer lexer = new DrawGraphLexer(input);
        CommonTokenStream tokens = new CommonTokenStream(lexer);
        DrawGraphParser parser = new DrawGraphParser(tokens);

        tree = parser.program();
        int nErr = parser.getNumberOfSyntaxErrors();
        return nErr;
    }
}

4.4 文件4：UiPixelAttrib.java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class UiPixelAttrib {
    public double Size = 3;
    public double Green = 0, Red = 0, Blue = 0;
    public UiPixelAttrib(){}
    public UiPixelAttrib(double red, double green, double blue) {
        Green = green;
        Red = red;
        Blue = blue;
    }
    public void setSize(double size) {
        Size = size;
    }
    
    public double green() {return Green;}
    public double red() {return Red;}
    public double blue() {return Blue;}
    public double size() {return Size;}

}

4.5 文件5：DrawLangMain.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
public class DrawLangMain {
    public static void main(String[] args) {
        if (args.length < 1) {
            System.err.println("未指定输入源文件\n");
            System.exit(1);
        }
        try {
            BaseUI theUI = new BaseUI();
            DrawLangMain.doFile(args[0], theUI);
        } catch (Exception e) {
            System.err.println("Exception in main: " + e);
            e.printStackTrace();
            System.exit(1);
        }
    }
    public static void doFile(String file, BaseUI theUI) throws Exception {
        FrontEnd fe = new FrontEnd(file);
        int nErr = fe.doParse();
        if (nErr > 0) {
            theUI.showMessage("语法分析出现错误");
            System.gc();
            return ;
        }
        theUI.setVisible(true);

        BackEnd be = new BackEnd(fe.getTree(), theUI);
        be.run();
    }
}

4.6 文件6：DrawerListener.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
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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
import org.antlr.v4.runtime.*;
import org.antlr.v4.runtime.tree.*;

import java.util.*;

@SuppressWarnings({"deprecation"})
class DrawerListener extends DrawGraphBaseListener {

    BaseUI    theUI       =null;
    
    public DrawerListener()
    {
    }
    
    public void setUI(BaseUI ui)
    {
        theUI = ui;        
    }

    ParseTreeProperty<Double> values = new ParseTreeProperty<Double>();
    Map<String, Double> memory = new HashMap<String, Double>();

    void setValue(ParseTree node, double value) {
        values.put(node, value);
    }
    double getValue(ParseTree node) {
        return values.get(node);
    }
    private double valueOfT =0; // 循环变量 T 的值
    private double originX =0; // 坐标平移参数
    private double originY =0; 
    private double scaleX  =1;  // 横向缩放因子
    private double scaleY  =1;  // 纵向缩放因子
    private double rotate  =0;  // 旋转角度
    private UiPixelAttrib  pixelAttrib = new UiPixelAttrib();
    @Override
    public void exitOriginStatement(DrawGraphParser.OriginStatementContext ctx) {
        originX = getValue(ctx.expr(0));
        originY = getValue(ctx.expr(1));
    }

    @Override
    public void exitScaleStatement(DrawGraphParser.ScaleStatementContext ctx) {
        scaleX = getValue(ctx.expr(0));
        scaleY = getValue(ctx.expr(1));
    }

    @Override 
    public void exitRotStatement(DrawGraphParser.RotStatementContext ctx) {
        rotate = getValue(ctx.expr());
    }

    @Override public void exitForStatement(DrawGraphParser.ForStatementContext ctx) {
        if(pixelAttrib == null) pixelAttrib = new UiPixelAttrib();
	    double Tbegin = getValue( ctx.expr(0));
	    double Tend   = getValue( ctx.expr(1));
	    double Tstep  = getValue( ctx.expr(2));

        ParseTreeWalker walker = new ParseTreeWalker(); //用于多次遍历子树
	    for(valueOfT = Tbegin; valueOfT <Tend; valueOfT += Tstep)
	    {	        
            walker.walk(this , ctx.expr(3));      // 遍历子树，获得当前的逻辑坐标
			double x = getValue( ctx.expr(3) );
            walker.walk(this , ctx.expr(4));
			double y = getValue( ctx.expr(4) );

			x *= scaleX; y *= scaleY;           // 先比例变换
			double tmp;
			tmp = x*Math.cos(rotate) + y*Math.sin(rotate); // 再旋转变换
			y = y*Math.cos(rotate)-x*Math.sin(rotate);
			x = tmp;
			x+=originX; y+=originY;             // 最后平移变换
			theUI.drawPixel(x, y, pixelAttrib);
			
        //  theUI.showMessage("*** PIXEL at (" + x + ", " + y + ")");
	    }
    }

    @Override
    public void exitPowerExpr(DrawGraphParser.PowerExprContext ctx) {
        double L = getValue(ctx.expr(0));
        double R = getValue(ctx.expr(1));
        double value = Math.pow(L, R);
        setValue(ctx, value);
    }

    @Override
    public void exitMulDivExpr(DrawGraphParser.MulDivExprContext ctx) {
        double left = getValue(ctx.expr(0));
        double right = getValue(ctx.expr(1));
        double value = 0;
        if (ctx.MUL() != null) value = left * right;
        else value = left / right;
        setValue(ctx, value);
    }

    @Override
    public void exitVarT(DrawGraphParser.VarTContext ctx) {
        setValue(ctx, valueOfT);
    }
    
    @Override 
    public void exitConst(DrawGraphParser.ConstContext ctx) {
	    Token tk = ctx.CONST_ID().getSymbol();    // 获得记号对象
	    String vName = tk.getText().toLowerCase();// 获得记号对象的文本并转换为小写字母
	    double value = 0;
	    
	    if(vName.equals("pi")) value = Math.PI; //3.1415926
	    else if(vName.equals("e")) value = Math.E; //2.7182818284
	    else {
	        try {
	           value = Double.valueOf(vName);
	        } catch(Exception e) {
	            theUI.showMessage("error " + tk.getLine() + ":" 
	               + tk.getCharPositionInLine()
	               + "  不支持的常量名 '" + vName  +"'" );
	            value = 0;
	        }
	    }

	    setValue(ctx, value);
    }

    @Override 
    public void exitPlusMinusExpr(DrawGraphParser.PlusMinusExprContext ctx) {
        double left = getValue(ctx.expr(0));
        double right = getValue(ctx.expr(1));
        double value = 0;
        if (ctx.PLUS() != null) value = left + right;
        else value = left - right;
        setValue(ctx, value);
    }

    @Override
    public void exitNestedExpr(DrawGraphParser.NestedExprContext ctx) {
        setValue(ctx, getValue(ctx.expr()));
    }

    @Override
    public void exitUnaryExpr(DrawGraphParser.UnaryExprContext ctx) {
        double value = getValue(ctx.expr());
        if (ctx.PLUS() == null) value = -value;
        setValue(ctx, value);
    }

    @Override
    public void exitFuncExpr(DrawGraphParser.FuncExprContext ctx) {
        Token id = ctx.ID().getSymbol();
	    String funcName = id.getText().toLowerCase();
	    double value = 0;
	    double param = getValue(ctx.expr());  // 函数调用的参数值
	    if(funcName.equals("sin")) value = Math.sin(param);
	    else if(funcName.equals("cos")) value = Math.cos(param);
	    else if(funcName.equals("tan")) value = Math.tan(param);
	    else {
	        theUI.showMessage("error " + id.getLine() + ":" 
	               + id.getCharPositionInLine()
	               + "  不支持的函数名 '" + funcName  +"'" );
	    }
	    setValue(ctx, value);
    }

    @Override
    public void exitColorStatement(DrawGraphParser.ColorStatementContext ctx) {
        TerminalNode node = ctx.RED();
	    if(node != null) {
	        pixelAttrib = new UiPixelAttrib(255, 0, 0);
	        return;
	    }
	    
	    node = ctx.GREEN();
	    if(node != null) {
	        pixelAttrib = new UiPixelAttrib(0, 255, 0);
	        return;
	    }
	    node = ctx.BLUE();
	    if(node != null) {
	        pixelAttrib = new UiPixelAttrib(0, 0, 255);
	        return;
	    }
	    
	    double r = getValue( ctx.expr(0) );
	    double g = getValue( ctx.expr(1) );
	    double b = getValue( ctx.expr(2) );
    	    
  	    pixelAttrib = new UiPixelAttrib(r, g, b);
    }

    @Override
    public void exitAssign(DrawGraphParser.AssignContext ctx) {
        String id = ctx.ID().getText();  // id is left-hand side of '='
        double value = getValue(ctx.expr());  
        memory.put(id, value);           // store it in our memory
        setValue(ctx, value);
    }

    @Override 
    public void exitVarExpr(DrawGraphParser.VarExprContext ctx) {
        String id = ctx.ID().getText();
        if ( memory.containsKey(id) )
            setValue(ctx, memory.get(id));
        else {
            theUI.showMessage("不存在变量" + id);
        }
	}

    @Override
    public void visitErrorNode(ErrorNode node) {}
}

五、测试用例及运行结果

5.1 测试用例1

测试文件1的内容：

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
// this is comment
--pixsize is 5;
--zonesize is (800, 600);

ORIGIN IS (20,200);
rot IS 0;
SCALE IS(40,40);
FOR T FROM 0 TO 2*PI+PI/50 STEP PI/50 DRAW(T, sin(T));
COLOR IS GREEN;
ORIGIN IS (20,240);
FOR T FROM 0 TO 2*PI+PI/50 STEP PI/50 DRAW(T, sin(T));
COLOR IS BLUE;
ORIGIN IS (20,280);
FOR T FROM 0 TO 2*PI+PI/50 STEP PI/50 DRAW(T, sin(T));

ORIGIN IS (380,240);
SCALE IS(80,80/3);
COLOR is (255,0,255);
ROT IS PI/2+0*PI/3;
FOR T FROM -PI TO PI STEP PI/50 DRAW (cos(T), sin(T));
COLOR is (128,0,255);
ROT IS PI/2+2*PI/3;
FOR T FROM -PI TO PI STEP PI/50 DRAW (cos(T), sin(T));
COLOR is (0,128,255);
ROT IS PI/2-2*PI/3;
FOR T FROM -PI TO PI STEP PI/50 DRAW (cos(T), sin(T));


ORIGIN IS(580,240);
SCALE IS (80,80);
ROT IS 0;

color is red;
FOR T FROM 0 TO PI*20 STEP PI/50 
DRAW((1-1/(10/7))*cos(T)+1/(10/7)*cos(-T*((10/7)-1)), (1-1/(10/7))*sin(T)+1/(10/7)*sin(-T*(10/7-1)));

color is (128,0,0);
FOR T FROM 0 TO 2*PI STEP PI/50 DRAW(cos(T), sin(T));

运行结果：

5.2 测试用例2

测试文件2的内容：

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
color is red;
origin is (300,300);
scale is (200,200);
rot is 0;
for T from 0 to 2*pi step pi/700 draw (cos(t), sin(t));


color is (0,0,0);
origin is (300,200);
scale is (30,30);
rot is 0;
for t from 0 to 2*pi step pi/350 draw (cos(t), sin(t));

color is (255,0,0);
origin is (300,400);
scale is (30,30);
rot is 0;
for t from 0 to 2*pi step pi/350 draw (cos(t), sin(t));

color is (0,0,0);
origin is (300,200);
scale is (100,100);
rot is pi/2;
for t from -pi to 0 step pi/500 draw (cos(t), sin(t));


color is red;
origin is (300,400);
scale is (100,100);
rot is 0;
for t from -pi/2 to pi/2 step pi/500 draw (cos(t), sin(t));

运行结果：

六、心得体会

从上一学期中使用Python从头到尾设计词法分析器、语法分析器、语法制导翻译；到如今的使用ANTLR规定语法规则、词法规则自动生成前端程序，自己动手设计遍历器的语义动作，编译原理与程序分析的课程设计让我充分明白了自动化编程的工作流程与意义。

经过这次实验，我体会到了避免重复造轮子的编程思想，同时也感受到了使用自动化编程工具提高生产力的力量。

0%