ARTS-第68周

发表于

ARTS （第68周）

不积跬步，无以至千里，不积小流，无以成江海

Algorithm 算法

最简单的编译器3(加减乘除、优先级、变量、控制台)

加减乘除、括号、变量声明和控制台功能的脚本

AST和TOKEN

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
package compiler.demo1.ast;

import compiler.demo1.token.TokenType;
import lombok.AllArgsConstructor;
import lombok.Getter;
@AllArgsConstructor
@Getter
public enum NodeType {
    VariableAssign("变量",null),
    VariableName("变量名",null),
    Declare("声明变量","var"),
    Plus("加法","+"),
    Sub("减法","-"),
    Mul("乘法","*"),
    Div("除法","/"),
    Literal("字面量",null);
    String desc;
    String text;
    public static NodeType getTypeByCode(String code) {
        if(code == null)
            return null;
        NodeType[] enums = values();
        for (NodeType e : enums) {
            if (code.equals(e.getText())) {
                return e;
            }
        }
        return null;
    }
}
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
package compiler.demo1.ast;

import compiler.demo1.token.TokenType;
import lombok.AllArgsConstructor;
import lombok.Getter;
@AllArgsConstructor
@Getter
public enum NodeType {
    VariableAssign("变量",null),
    VariableName("变量名",null),
    Declare("声明变量","var"),
    Plus("加法","+"),
    Sub("减法","-"),
    Mul("乘法","*"),
    Div("除法","/"),
    Literal("字面量",null);
    String desc;
    String text;
    public static NodeType getTypeByCode(String code) {
        if(code == null)
            return null;
        NodeType[] enums = values();
        for (NodeType e : enums) {
            if (code.equals(e.getText())) {
                return e;
            }
        }
        return null;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
package compiler.demo1.token;

import lombok.Data;

/**
 * 一个简单的Token。
 * 具有文本值、类型、在字符串中的位置等属性。
 */
@Data
public class Token {

    //token的类型
    private TokenType tokenType = null;

    //token的文本值
    private String text = null;


}
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
package compiler.demo1.token;

import compiler.demo1.token.Token;
import compiler.demo1.token.TokenType;
import compiler.demo1.util.CommonUtil;

import java.util.ArrayList;
import java.util.List;

import static com.sun.org.apache.xalan.internal.lib.ExsltStrings.split;

public class TokenAnalyser {

    public static List<Token> analyserTokenOneLine(String code) {
        String[] tokens = code.trim().split("\\s+");
        List<Token> tokenOneLine = new ArrayList<>();
        for (String tokenStr : tokens) {
            Token token = new Token();
            token.setText(tokenStr);
            token.setTokenType(getTokenType(tokenStr));
            tokenOneLine.add(token);
        }
        return tokenOneLine;
    }

    public static List<List<Token>> analyserToken(String code) {
        ArrayList<List<Token>> result = new ArrayList<>();
        String[] lines = code.split(getLineSeparator());
        for (String line : lines) {
           result.add(analyserTokenOneLine(line));
        }
        return result;
    }

    private static TokenType getTokenType(String s) {
        TokenType r=  TokenType.getTypeByCode(s);
        if( r == null ){
            if(CommonUtil.isNumeric(s))
                r = TokenType.Literal;
            else{
                r=TokenType.Variable;
            }
        }

        return r;
    }

    private static String getLineSeparator() {
        return "\\r\\n";//windows
    }
}
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
package compiler.demo1.token;

import java.util.List;

/**
 * Token流。
 * 可以read或peekToken。
 * 可以通过unread、setPosition()回溯。
 */
public class TokenReader {

    List<Token> tokens = null;

    //当前指针位置。
    int pos = 0;

    public TokenReader(List<Token> tokens) {
        this.tokens = tokens;
    }

    /**
     * 读取一个Token，并移动指针。
     * @return 如果已经读完，则返回null。
     */
    public Token read() {
        if (pos < tokens.size()) {
            return tokens.get(pos++);
        }
        return null;
    }

    /**
     * 预读一个Token。
     * @return 如果已经读完，则返回null。
     */
    public Token peek() {
        if (pos < tokens.size()) {
            return tokens.get(pos);
        }
        return null;
    }

    /**
     * 回溯一个Token。
     */
    public void unread() {
        if (pos > 0) {
            pos--;
        }
    }

    /**
     * 获取当前指针位置。
     * @return
     */
    public int getPosition() {
        return pos;
    }

    /**
     * 设置指针位置。用于回溯。
     * @param position
     */
    public boolean setPosition(int position) {
        if (position >=0 && position < tokens.size()){
            pos = position;
            return true;
        }
        return false;
    }
}
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
package compiler.demo1.token;

import lombok.AllArgsConstructor;
import lombok.Getter;

@Getter
@AllArgsConstructor
public enum TokenType {
    Declare("var","声明变量名"),
    Equal("=","赋值"),
    End(";","结束"),
    Variable(null,"变量名"),
    Int("int","变量声明"),
    Plus("+","加法"),
    Sub("-","减法"),
    Mul("*","乘法"),
    Div("/","除法"),
    LParen("(","左括号"),
    RParen(")","右括号"),
    Literal(null,"字面量");

    public String code;
    public String text;

    public static TokenType getTypeByCode(String code) {
        if(code == null)
            return null;
        TokenType[] enums = values();
        for (TokenType e : enums) {
            if (code.equals(e.getCode())) {
                return e;
            }
        }
        return null;
    }
}

解析器、编译器

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
package compiler.demo1.compile3;

import compiler.demo1.ast.NodeType;
import compiler.demo1.ast.SimpleASTNode;
import compiler.demo1.token.Token;
import compiler.demo1.token.TokenAnalyser;
import compiler.demo1.token.TokenReader;
import compiler.demo1.token.TokenType;

import java.util.List;

public class TestCompiler3 {
    


    public SimpleASTNode compilerOneLine(String code) {
        List<Token> tokens = TokenAnalyser.analyserTokenOneLine(code);
        return compileLine(tokens);
    }


    private SimpleASTNode compileLine(List<Token> tokens) {
        TokenReader reader = new TokenReader(tokens);
        TokenType tokenType = reader.peek().getTokenType();
        if(tokenType==TokenType.Declare){
            return declaration(reader);
        }
        if(tokenType==TokenType.Variable){
            return assignment(reader);
        }
        if(tokenType==TokenType.Literal){
            return additive(reader);
        }
        throw new RuntimeException("非法的代码开头");
    }
    private SimpleASTNode assignment(TokenReader reader) {
        SimpleASTNode node = null;
        Token peek = reader.peek();
        if(peek != null && peek.getTokenType() == TokenType.Variable){
            reader.read();
            Token next = reader.peek();
            if(next != null && next.getTokenType()== TokenType.Equal){
                reader.read();//消耗掉等号
                node = new SimpleASTNode();
                node.setNodeType(NodeType.VariableAssign);
                SimpleASTNode c1 = new SimpleASTNode();
                c1.setNodeType(NodeType.VariableName);
                c1.setText( peek.getText()); //变量名
                SimpleASTNode c2 = additive(reader);  //后续节点
                node.getChildren().add(c1);
                node.getChildren().add(c2);
            }else{
                reader.unread();
                return additive(reader);
            }

        }
        return node;

    }
    private SimpleASTNode declaration(TokenReader reader) {
        SimpleASTNode node = null;
        Token peek = reader.peek();
        if(peek != null && peek.getTokenType() == TokenType.Declare){
            reader.read();
            Token var = reader.read();
            if(var.getTokenType()==TokenType.Variable){
                node = new SimpleASTNode();
                node.setNodeType(NodeType.Declare);
                //变量节点
                SimpleASTNode c1 = new  SimpleASTNode ();
                c1.setNodeType(NodeType.VariableName);
                c1.setText(var.getText());
                node.getChildren().add(c1);
                //值节点
                Token next= reader.peek();
                if(next != null){
                    if(next.getTokenType()== TokenType.Equal){
                        reader.read();
                        SimpleASTNode c2 = additive(reader);
                        if( c2 != null){
                            node.getChildren().add(c2);
                        }else{
                            throw new RuntimeException("变量声明错误，等号后必须有内容");
                        }
                    }else{
                        throw new RuntimeException("变量声明错误，变量名后只能跟随等号或者不跟随");
                    }
                }


            }else{
                throw new RuntimeException("变量声明错误，丢失变量名");
            }

        }
        return  node;
    }
    private SimpleASTNode additive(TokenReader reader) {
        SimpleASTNode node = null;
        node = multiplicative(reader);
        if(node != null){
            Token peek = reader.peek();
            if(peek!=null && (peek.getTokenType()== TokenType.Plus ||peek.getTokenType()== TokenType.Sub)){
                reader.read();
                //Token token2 = reader.read();
                SimpleASTNode node2 = additive(reader);
                if(node2 != null ){
                    SimpleASTNode node1 = node;
                    node = new SimpleASTNode();
                    node.setText(peek.getTokenType().getText());
                    node.setNodeType(NodeType.getTypeByCode(peek.getTokenType().getCode()));
                    node.getChildren().add(node1);
                    node.getChildren().add(node2);
                }else{
                    throw  new RuntimeException("加法解析错误");
                }
            }
        }

        return node;
    }
    private SimpleASTNode multiplicative(TokenReader reader) {
        SimpleASTNode node = null;
        node = primary(reader);
        if(node != null){
            Token peek = reader.peek();
            if(peek!=null &&( peek.getTokenType() == TokenType.Mul || peek.getTokenType() == TokenType.Div)){
                reader.read();
                SimpleASTNode node2 = multiplicative(reader);
                if(node2 != null ){
                    SimpleASTNode node1 = node;
                    node = new SimpleASTNode();
                    node.setText(peek.getTokenType().getText());
                    node.setNodeType(NodeType.getTypeByCode(peek.getTokenType().getCode()));
                    node.getChildren().add(node1);
                    node.getChildren().add(node2);
                }else{
                    throw  new RuntimeException("乘法解析错误");
                }

            }

        }

        return node;
    }
    private SimpleASTNode primary(TokenReader reader) {
        SimpleASTNode node = null;
        Token peek = reader.peek();
        if(peek !=null && peek.getTokenType()== TokenType.Variable){
            node= new SimpleASTNode();
            node.setNodeType(NodeType.VariableName);
            node.setText(reader.read().getText());
        } else if(peek !=null && peek.getTokenType()== TokenType.Literal){
            node= new SimpleASTNode();
            node.setNodeType(NodeType.Literal);
            node.setText(reader.read().getText());
        }else if(peek !=null && peek.getTokenType()== TokenType.LParen){
            reader.read();
            node = additive(reader);
            Token r = reader.read();
            if(r==null || r.getTokenType() != TokenType.RParen){
                throw new RuntimeException("括号解析错误");
            }
        }else{
            throw new RuntimeException("语法解析错误:" + peek.getText());
        }
        return node;
    }



    public static void  dump(SimpleASTNode ast ){
        dumpHelp(ast,"");
    }
    private static void  dumpHelp(SimpleASTNode ast ,String indent){
        System.out.print(indent);
        System.out.println(ast.getNodeType ()+"("+ast.getText()+")");
        indent +="   ";
        for (SimpleASTNode child : ast.getChildren()) {
            dumpHelp(child,indent);
        }
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
package compiler.demo1.compile3;

import compiler.demo1.ast.SimpleASTNode;

import java.util.HashMap;
import java.util.Map;
import java.util.Set;

public class TestCalculator3 {
    private Map<String,Object> variables = new HashMap<>();

    public void calByRecursion(SimpleASTNode root){
        System.out.println("->:"+root.calValueWithVariable(variables));
    }
    public Object getVariable(String key){
        return variables.get(key);
    }
    public void showAllVariables(){
        Set<Map.Entry<String, Object>> entries = variables.entrySet();
        entries.forEach(o->{
            System.out.println(o.getKey()+":"+o.getValue());
        });
    }
}

测试

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
package compiler.demo1.compile3;

import compiler.demo1.ast.SimpleASTNode;

import java.util.Scanner;

public class Test3 {
    public static void main(String[] args) {
        console();
    }
    public static void test(){
        TestCompiler3 compiler = new TestCompiler3();
        TestCalculator3 calculator = new TestCalculator3();
        Scanner scan = new Scanner(System.in);
        //String code = "3 * ( 5 + 2 ) + 10 / ( 5 - 3 )";
        //String code = "2 + 1 + 21 + 21 + 2";
        //String code = "2 * 1 * 21 * 21 * 2";
        String code = "var a";
        //System.out.println("code_>"+code);
        SimpleASTNode simpleASTNode = compiler.compilerOneLine(code);
        TestCompiler3.dump(simpleASTNode);
        calculator.calByRecursion(simpleASTNode);
        calculator.showAllVariables();
    }
    public static void console(){
        System.out.println("*** simple script start  ***");
        TestCompiler3 compiler = new TestCompiler3();
        TestCalculator3 calculator = new TestCalculator3();
        Scanner scan = new Scanner(System.in);
        scan.useDelimiter("\n");
        //String code = "3 * ( 5 + 2 ) + 10 / ( 5 - 3 )";
        //String code = "2 + 1 + 21 + 21 + 2";
        //String code = "2 * 1 * 21 * 21 * 2";
        //String code = "var aaa = 1";
        //System.out.println("code_>"+code);

        calculator.showAllVariables();
        // 从键盘接收数据
        // next方式接收字符串
        // 判断是否还有输入
        while (true) {
           try {
               System.out.print("<-");
               String code = scan.next();
               if("exit()".equals(code)){
                   break;
               }
               if("showAll()".equals(code)){
                   calculator.showAllVariables();
                   continue;
               }
               SimpleASTNode simpleASTNode = compiler.compilerOneLine(code);
               //TestCompiler3.dump(simpleASTNode);
               calculator.calByRecursion(simpleASTNode);
               //calculator.showAllVariables();
           }catch (Exception ex){
               System.out.println("异常:"+ex.getMessage());
           }
        }
        System.out.println("*** simple script stop  ***");
    }
}

Review 英文文章

https://spring.io/projects/spring-cloud-alibaba

spring cloud alibaba

Tip 技巧

Window配置antlr

1.找个目录放JAR包

我这里的全路径 

1
C:\DEV_TOOL\antlr\antlr-4.7.2-complete.jar

2.配置环境变量

CLASSPATH增加

1
C:\DEV_TOOL\antlr\antlr-4.7.2-complete.jar

PATH增加

1
C:\DEV_TOOL\antlr

3.编写bat文件

antlr4.bat

1
java org.antlr.v4.Tool %*

grun.bat

1
2
3
4
5
@ECHO OFF
SET TEST_CURRENT_DIR=%CLASSPATH:.;=%
if "%TEST_CURRENT_DIR%" == "%CLASSPATH%" ( SET CLASSPATH=.;%CLASSPATH% )
@ECHO ON
java org.antlr.v4.gui.TestRig %*

Java元注解

元注解是指注解的注解，Java中有：
① @Retention: 定义注解的保留策略
② @Target：定义注解的作用目标
③ @Document：说明该注解将被包含在javadoc中
④ @Inherited：说明子类可以继承父类中的该注解

Share 分享

https://resources.jointjs.com/demos/javascript-ast JS抽象语法树可视化

https://www.jianshu.com/p/b6b5d39bf1aa seata分布式事务调研