Ming
0%

函数绘图语言之解释器

Posted on Edited on In

函数绘图语言

Snipaste_2020-12-03_15-21-41.png

Github：carpediemtal/Drawlang-Interpreter (github.com)

概述

5 种语句

  • 循环绘图（FOR-DRAW）

  • 比例设置（SCALE）

  • 角度旋转（ROT）

  • 坐标平移（ORIGIN）

  • 注释 （– 或 //）

坐标系

  • 左上角为原点

  • x方向从左向右增长

  • y方向从上到下增长

栗子

1
2
3
4
5
6
7
8
9
10
11
--------------- 函数f(t)=t的图形
origin is (100, 300);	-- 设置原点的偏移量
rot is 0;			-- 设置旋转角度(不旋转)
scale is (1, 1);		-- 设置横坐标和纵坐标的比例
for T from 0 to 200 step 1 draw (t, 0);
				-- 横坐标的轨迹（纵坐标为0）
for T from 0 to 150 step 1 draw (0, -t);
				-- 纵坐标的轨迹（横坐标为0）
for T from 0 to 120 step 1 draw (t, -t);
				-- 函数f(t)=t的轨迹 

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
origin is (100, 300);
rot is 0;
scale is (1, 2);
for T from 0 to 100 step 1 draw (100 * cos(T), 100*sin(T));
scale is (2, 1);
for T from 0 to 2*PI step PI/50 draw (20 * cos(T), -20 * sin(T));
for T from 0 to 300 step 1 draw (T, -T);
for T from 0 to 500 step 5 draw (-T, -2 * T);

// 三个椭圆
origin is (380,340);
scale is (100,100/3);
rot is pi/2;
for T from -pi to pi step pi/50 draw (cos(t),sin(t));
rot is pi/2 + 2*pi/3;
for T from -pi to pi step pi/50 draw (cos(t),sin(t));
rot is pi/2 - 2*pi/3;
for T from -pi to pi step pi/50 draw (cos(t),sin(t));


// 新的图形:万花筒
origin is (250,250);
scale is (100,100);
rot is 0;
for t from 0 to 2*pi step pi/50 draw (cos(t), sin(t));
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)));

为函数绘图语言构造‘解释器’

Snipaste_2020-12-03_15-23-23.png

词法分析器

记号的种类

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
public enum TokenType {
    /**
     * 保留关键字
     */
    ORIGIN, SCALE, ROT, IS, TO, STEP, DRAW, FOR, FROM,

    /**
     * 参数和标点符号
     */
    T, SEMICOLON, L_BRACKET, R_BRACKET, COMMA,

    /**
     * 运算符号
     */
    PLUS, MINUS, MUL, DIV, POWER,

    /**
     * 函数
     */
    FUNC,

    /**
     * 常数
     */
    CONST_VAL,

    /**
     * 文件末尾和错误
     */
    END, ERROR;
}

  1. 常数

    数值字面量和标识符形式的常量名均称为常数。

    • 字面量的形式为普通的数值，如果没有小数部分，可以省略小数点。例如2、2.、2.0都是合法的常数。

    • 标识符PI、E也是常数，它们分别代表圆周率和自然对数的底。常数不能有符号位，如-1和+2不是常数而是（一元运算的）表达式。

  2. 参数

    本绘图语言中唯一的、已经被定义好的变量名T被称为参数，它也是一个表达式。由于绘图语言中只有这唯一的变量，因此绘图语言中无需变量或参数的声明和定义语句。

  3. 函数

    为简单起见，当前函数调用仅支持Sin、Cos、Tan、Sqrt、Exp 和 Ln。

  4. 保留字

    语句中具有固定含义的标识符，包括：

    • ORIGIN, SCALE, ROT, IS,

    • FOR, FROM, TO, STEP, DRAW

  5. 运算符

    • + - * / **

    • 结合性： ** 右结合， 其他 左结合

    • 优先级：** ＞ 一元+- ＞ */ ＞ 二元+-

  6. 分隔符

    ； （ ） ，

建立hash表将字符串和Token相对应

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
private void initTable() {
    tokenTable.put("PI", new Token(TokenType.CONST_VAL, "PI", 3.1415926));
    tokenTable.put("E", new Token(TokenType.CONST_VAL, "E", 2.71828));
    tokenTable.put("T", new Token(TokenType.T, "T", 0));
    tokenTable.put("SIN", new Token(TokenType.FUNC, "SIN", 0));
    tokenTable.put("COS", new Token(TokenType.FUNC, "COS", 0));
    tokenTable.put("TAN", new Token(TokenType.FUNC, "TAN", 0));
    tokenTable.put("LN", new Token(TokenType.FUNC, "LN", 0));
    tokenTable.put("EXP", new Token(TokenType.FUNC, "EXP", 0));
    tokenTable.put("SQRT", new Token(TokenType.FUNC, "SQRT", 0));
    tokenTable.put("ORIGIN", new Token(TokenType.ORIGIN, "ORIGIN", 0));
    tokenTable.put("SCALE", new Token(TokenType.SCALE, "SCALE", 0));
    tokenTable.put("ROT", new Token(TokenType.ROT, "ROT", 0));
    tokenTable.put("IS", new Token(TokenType.IS, "IS", 0));
    tokenTable.put("FOR", new Token(TokenType.FOR, "FOR", 0));
    tokenTable.put("FROM", new Token(TokenType.FROM, "FROM", 0));
    tokenTable.put("TO", new Token(TokenType.TO, "TO", 0));
    tokenTable.put("STEP", new Token(TokenType.STEP, "STEP", 0));
    tokenTable.put("DRAW", new Token(TokenType.DRAW, "DRAW", 0));
}

识别出的函数会在后面的语法分析器进一步细分：

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
/**
 * 计算带有函数的表达式的值
 *
 * @param funcName 函数名
 * @param val      函数
 * @return 函数值
 */
private double function(String funcName, double val) {
    switch (funcName) {
        case "COS" -> {
            return Math.cos(val);
        }
        case "SIN" -> {
            return Math.sin(val);
        }
        case "TAN" -> {
            return Math.tan(val);
        }
        case "SQRT" -> {
            return Math.sqrt(val);
        }
        case "EXP" -> {
            return Math.exp(val);
        }
        case "LN" -> {
            return Math.log(val);
        }
        default -> throw new RuntimeException("Syntax Error");
    }
}

DFA

image-20201203153447268.png

核心代码

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
/**
        * 每次调用获得一个Token
 *
         * @return 返回下一个Token
 */
public Token getToken() {
    // 跳过最初的空白字符
    jumpSpace();

    // 读到了源代码末尾
    if (index >= src.length()) {
        return new Token(TokenType.END, "END", 0);
    }

    // 存储Token字符
    StringBuilder tokenString = new StringBuilder();

    // 第一个非空字符
    char ch = getChar();
    tokenString.append(ch);
    // 识别保留字、常量名和参数名:纯字母
    if (Character.isAlphabetic(ch)) {
        while (true) {
            ch = getChar();
            if (Character.isAlphabetic(ch)) {
                tokenString.append(ch);
            } else {
                break;
            }
        }
        index--;
        return lookUpTable(tokenString.toString());
    } else if (Character.isDigit(ch)) { // 识别数字常量
        while (true) {
            ch = getChar();
            if (Character.isDigit(ch)) {
                tokenString.append(ch);
            } else {
                break;
            }
        }
        if (ch == '.') {
            tokenString.append(ch);
            while (true) {
                ch = getChar();
                if (Character.isDigit(ch)) {
                    tokenString.append(ch);
                } else {
                    break;
                }
            }
        }
        index--;
        return new Token(TokenType.CONST_VAL, tokenString.toString(), Double.parseDouble(tokenString.toString()));
    } else {
        // 识别运算符或者分隔符，跳过注释
        switch (ch) {
            case ';' -> {
                return new Token(TokenType.SEMICOLON, ";", 0);
            }
            case '(' -> {
                return new Token(TokenType.L_BRACKET, "(", 0);
            }
            case ')' -> {
                return new Token(TokenType.R_BRACKET, ")", 0);
            }
            case ',' -> {
                return new Token(TokenType.COMMA, ",", 0);
            }
            case '+' -> {
                return new Token(TokenType.PLUS, "+", 0);
            }
            // comment or minus
            case '-' -> {
                ch = getChar();
                // 跳过注释
                if (ch == '-') {
                    while (ch != '\n' && ch != '!') {
                        ch = getChar();
                    }
                    index--;
                    return getToken();
                } else {
                    index--;
                    return new Token(TokenType.MINUS, "-", 0);
                }
            }
            case '*' -> {
                ch = getChar();
                if (ch == '*') {
                    return new Token(TokenType.POWER, "**", 0);
                } else {
                    index--;
                    return new Token(TokenType.MUL, "*", 0);
                }
            }
            // comment or div
            case '/' -> {
                ch = getChar();
                if (ch == '/') {
                    while (ch != '\n' && ch != '!') {
                        ch = getChar();
                    }
                    index--;
                    return getToken();
                } else {
                    index--;
                    return new Token(TokenType.DIV, "/", 0);
                }
            }
            // 不能识别的字符返回ERROR类型的Token
            default -> {
                return new Token(TokenType.ERROR, "ERROR", 0);
            }
        }
    }
}

语法分析器

流程

Snipaste_2020-12-03_15-39-00.png

语法分析器Parser内部持有一个词法分析器Lexer实例，通过该实例的getToken获得Token，再进一步分析。

1
2
3
4
public void parse() {
    fetchToken();
    program();
}

文法

经过各种处理之后的最终文法规则

Snipaste_2020-12-03_15-41-41.png

表达式的语法树

函数绘图语言比较简单，只有表达式需要建立语法树进一步求值。

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
package eternal.fire.syntax;

import eternal.fire.token.TokenType;

/**
 * 当节点有两个孩子的时候，使用left和right
 * 当节点只有一个孩子的时候，使用child
 */
public class ExprNode {
    private TokenType tokenType;

    private ExprNode left;

    private ExprNode right;

    private ExprNode child;

    // 针对CONST_VAL
    private double val;

    // 针对FUNC
    private String funcName;

    // 针对FUNC类型的节点
    public ExprNode(TokenType tokenType, String funcName) {
        this.tokenType = tokenType;
        this.funcName = funcName;
    }

    // CONST_VAL类型的节点
    public ExprNode(TokenType tokenType, double val) {
        this.tokenType = tokenType;
        this.val = val;
    }

    // 针对二元运算类型的节点（已经构造好了左子树和右子树）
    public ExprNode(TokenType tokenType, ExprNode left, ExprNode right) {
        this.tokenType = tokenType;
        this.left = left;
        this.right = right;
    }

    public ExprNode() {

    }
    
    // ......只截取了一部分
}

构造语法树的片段节选

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
 * 匹配一个表达式expression，为表达式expression构造语法树ExprNode
 *
 * @return 构造出的语法树
 */
private ExprNode expression() {
    var left = term();
    while (token.getTokenType() == TokenType.PLUS || token.getTokenType() == TokenType.MINUS) {
        var tmp = token.getTokenType();
        matchToken(token.getTokenType());
        var right = term();
        // 不断更新左节点
        left = new ExprNode(tmp, left, right);
    }
    return left;
}

To be continued…

绘图：JavaFX

核心思路

利用JavaFx的canvas可以轻松在窗口面板上绘制一个点。

1
2
3
4
Canvas canvas = new Canvas(500, 500);
var context = canvas.getGraphicsContext2D();
context.setFill(Color.GREEN);
context.fillOval(x, y, dotSize, dotSize);

当语法分析器获得绘图语句的结果后，使用循环语句在面板上画上若干个点，于是一切都结束了。

前端界面设计

画板大小：500px*500px

使用JFoenix和css样式对部分组件稍加美化

Snipaste_2020-12-03_15-21-41.png

布局

Snipaste_2020-12-03_15-56-34.png

窗口图标

draw.png

1
primaryStage.getIcons().add(new Image(Draw.class.getResourceAsStream("/draw.png")));

补充的功能

Snipaste_2020-12-03_16-00-36.png

改变画笔颜色

添加一个拾色器组件，当拾色器组件的值发生变化，就以新的值为画笔颜色，清空画板，重新渲染。

1
2
3
4
5
6
7
8
9
// 拾色器
ColorPicker colorPicker = new ColorPicker(Color.GREEN);
colorPicker.setOnAction(event -> {
    logger.info("画笔颜色改变为{}", colorPicker.getValue());
    context.clearRect(0, 0, 500, 500);
    context.setFill(colorPicker.getValue());
    parser.getLexer().reload();
    parser.parse();
});
改变画笔宽度

和上面的思路类似。

1
2
3
4
5
6
7
8
9
10
// 滑动按钮
JFXSlider slider = new JFXSlider(0, 10, 0.5);
slider.setValue(5);
slider.valueProperty().addListener((observable, oldValue, newValue) -> {
    logger.info("画笔宽度改变为{}", newValue.doubleValue());
    context.clearRect(0, 0, 500, 500);
    parser.setDotSize(newValue.doubleValue());
    parser.getLexer().reload();
    parser.parse();
});

Help按钮

跳转到我的博客。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// Help
JFXButton helpBtn = new JFXButton("Help");
helpBtn.setMaxWidth(90);
helpBtn.getStyleClass().add("button-raised");
helpBtn.setStyle("-fx-background-color: #0F9D58");
/*var helpIcon = new ImageView(new Image(Draw.class.getResourceAsStream("/help.png")));
helpIcon.setFitWidth(25);
helpIcon.setFitHeight(25);
helpBtn.setGraphic(helpIcon);*/
helpBtn.setOnAction(event -> {
    try {
        Desktop.getDesktop().browse(new URI(BLOG_URL));
    } catch (IOException | URISyntaxException e) {
        e.printStackTrace();
    }
});

help的图标看上去好丑，我注释掉了。

Github按钮

跳转到我的github仓库。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// Github
JFXButton githubBtn = new JFXButton("Github");
githubBtn.setMaxWidth(90);
githubBtn.getStyleClass().add("button-raised");

// 为按钮添加图标
var githubIcon = new ImageView(new Image(Draw.class.getResourceAsStream("/github.png")));
githubIcon.setFitWidth(20);
githubIcon.setFitHeight(20);

githubBtn.setGraphic(githubIcon);
githubBtn.setOnAction(event -> {
    try {
        Desktop.getDesktop().browse(new URI(GITHUB_URL));
    } catch (IOException | URISyntaxException e) {
        e.printStackTrace();
    }
});

日志

使用SLF4J和Logback

依赖项：

1
2
3
4
5
6
7
8
dependencies {
// https://mvnrepository.com/artifact/org.slf4j/slf4j-api
    compile group: 'org.slf4j', name: 'slf4j-api', version: '1.7.30'
// https://mvnrepository.com/artifact/ch.qos.logback/logback-classic
    compile group: 'ch.qos.logback', name: 'logback-classic', version: '1.2.3'
// https://mvnrepository.com/artifact/ch.qos.logback/logback-core
    compile group: 'ch.qos.logback', name: 'logback-core', version: '1.2.3'
}

构建

使用Gradle管理依赖项

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
plugins {
    id 'application'
    id 'org.openjfx.javafxplugin' version '0.0.8'
}

group 'eternal.fire'
version '1.0-SNAPSHOT'

repositories {
    maven { url 'http://maven.aliyun.com/nexus/content/groups/public/' }
    maven { url 'http://maven.aliyun.com/nexus/content/repositories/jcenter' }
}

dependencies {
// https://mvnrepository.com/artifact/org.slf4j/slf4j-api
    compile group: 'org.slf4j', name: 'slf4j-api', version: '1.7.30'
// https://mvnrepository.com/artifact/ch.qos.logback/logback-classic
    compile group: 'ch.qos.logback', name: 'logback-classic', version: '1.2.3'
// https://mvnrepository.com/artifact/ch.qos.logback/logback-core
    compile group: 'ch.qos.logback', name: 'logback-core', version: '1.2.3'
    compile 'com.jfoenix:jfoenix:9.0.10'
}
javafx {
    version = "13"
    modules = ['javafx.controls', 'javafx.fxml']
}

application {
    mainClass = 'eternal.fire.Draw'
//    mainClass = 'eternal.fire.Parser'
}

tasks.withType(JavaCompile) {
    options.encoding = 'UTF-8'
}

运行

1
gradlew run