ARTS （第67周）

业精于勤疏于嬉，行成于思毁于随

Algorithm 算法

最简单的编译器2（加减乘除、优先级）

AST和TOKEN

package compiler.demo1.ast;

import compiler.demo1.token.TokenType;
import lombok.AllArgsConstructor;
import lombok.Getter;
@AllArgsConstructor
@Getter
public enum NodeType {
    Plus("加法","+",10),
    Sub("减法","-",10),
    Mul("乘法","*",20),
    Div("除法","/",20),
    Paren("()","括号",90),
    Literal("字面量",null,99);
    String code;
    String text;
    int level;//优先级
    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;
    }
}

package compiler.demo1.ast;

import compiler.demo1.util.CommonUtil;
import lombok.Data;

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

@Data()
public class SimpleASTNode {
    //SimpleASTNode parent = null;

    List<SimpleASTNode> children = new ArrayList<SimpleASTNode>();
    NodeType nodeType = null;
    String text = null;

    /**
     * compiler1 使用的
     * @return
     */
    public int calValue1(){
        if(nodeType== NodeType.Mul){
            if(children.size()<2){
                throw  new RuntimeException("乘法节点解析错误");
            }
            int res = children.get(0).calValue1();
            for (int i = 1; i < children.size(); i++) {
                res*=children.get(i).calValue1();
            }
            return res;
        }

        if(nodeType== NodeType.Plus){
            if(children.size()<2){
                throw  new RuntimeException("加法节点解析错误");
            }
            int res = children.get(0).calValue1();
            for (int i = 1; i < children.size(); i++) {
                res+=children.get(i).calValue1();
            }
            return res;
        }
        if(nodeType== NodeType.Div){
            if(children.size()<2){
                throw  new RuntimeException("除法节点解析错误");
            }
            int res = children.get(0).calValue1();
             res /= children.get(1).calValue1();
            return res;
        }
        if(nodeType== NodeType.Sub){
            if(children.size()<2){
                throw  new RuntimeException("减法节点解析错误");
            }
            int res = children.get(0).calValue1();
            res -= children.get(1).calValue1();
            return res;
        }
        if(CommonUtil.isNumeric(text))
            return Integer.parseInt(text);
        throw  new RuntimeException("无法将token解析成数字");
    }


}

package compiler.demo1.token;

import lombok.Data;

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

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

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


}

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.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) {
            String[] tokens = line.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);
            }
            result.add(tokenOneLine);
        }
        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
    }
}

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;
    }
}

package compiler.demo1.token;

import lombok.AllArgsConstructor;
import lombok.Getter;

@Getter
@AllArgsConstructor
public enum TokenType {

    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;
    }
}

解析、编译器

package compiler.demo1.compile2;

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 TestCompiler2 {
    


    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);
        SimpleASTNode node = additive(reader);
        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.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("括号解析错误");
            }
        }
        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.getText()+"("+ast.getNodeType()+")");
        indent +="   ";
        for (SimpleASTNode child : ast.getChildren()) {
            dumpHelp(child,indent);
        }
    }

}

package compiler.demo1.compile2;

import compiler.demo1.ast.NodeType;
import compiler.demo1.ast.SimpleASTNode;
import compiler.demo1.util.CommonUtil;

import java.util.List;

public class TestCalculator2 {

    public void calByRecursion(SimpleASTNode root){
        System.out.println("res->:"+root.calValue1());
    }
}

测试

package compiler.demo1.compile2;


import compiler.demo1.ast.SimpleASTNode;
import compiler.demo1.compile1.TestCalculator1;
import compiler.demo1.compile1.TestCompiler1;

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

public class Test2 {
    public static void main(String[] args) {
        TestCompiler2 compiler = new TestCompiler2();
        TestCalculator2 calculator = new TestCalculator2();
        String code = "3 * ( 5 + 2 ) + 10 / ( 5 - 3 )";
        //String code = "2 + 1 + 21 + 21 + 2";
        //String code = "2 * 1 * 21 * 21 * 2";
        System.out.println("code_>"+code);
        SimpleASTNode simpleASTNode = compiler.compilerOneLine(code);
        TestCompiler2.dump(simpleASTNode);
        calculator.calByRecursion(simpleASTNode);
    }
}

Review 英文文章

https://spring.io/guides/tutorials/spring-boot-oauth2/ spring整合oatuth2

Tip 技巧

JMM内存模型三大特性

1、原子性
AtomicInteger使用 synchronized 互斥锁来保证操作的原子性
2、可见性：
volatile，会强制将该变量自己和当时其他变量的状态都刷出缓存。
synchronized，对一个变量执行 unlock 操作之前，必须把变量值同步回主内存。
final，被 final 关键字修饰的字段在构造器中一旦初始化完成，并且没有发生 this 逃逸（其它线程通过 this 引用访问到初始化了一半的对象），那么其它线程就能看见 final 字段的值。
3、有序性
源代码 -> 编译器优化的重排 -> 指令并行的重排 -> 内存系统的重排 ->最终执行的命令
重排序过程不会影响到单线程程序的执行，却会影响到多线程并发执行的正确性

内存屏障

1、LoadLoad Barriers 参考指令：Load1;LoadLoad;Load2
该屏障确保Load1数据的装载先于Load2及其后所有装载指令的的操作
2、StoreStore Barriers 参考指令：Store1;StoreStore;Store2
该屏障确保Store1立刻刷新数据到内存(使其对其他处理器可见)的操作先于Store2及其后所有存储指令的操作
3、LoadStore Barriers 参考指令：Load1;LoadStore;Store2
确保Load1的数据装载先于Store2及其后所有的存储指令刷新数据到内存的操作
4、StoreLoad Barriers 参考指令：Store1;StoreLoad;Load2
该屏障确保Store1立刻刷新数据到内存的操作先于Load2及其后所有装载装载指令的操作。它会使该屏障之前的所有内存访问指令(存储指令和访问指令)完成之后,才执行该屏障之后的内存访问指令
另外，StoreLoad Barriers同时具备其他三个屏障的效果，因此也称之为全能屏障（mfence），是目前大多数处理器所支持的；但是相对其他屏障，该屏障的开销相对昂贵。

Share 分享

https://www.cs.usfca.edu/~galles/visualization/Algorithms.html 数据结构可视化

https://blog.csdn.net/a602519773/article/details/86086655 maven打包项目 包含与不包含依赖打包方式

https://zhidao.baidu.com/question/454840655563209205.html /usr、/home、/bin、/dev、/var、/etc中主要存放什么文件