hugh 的个人博客

上一节中， 我们使用递归下降算法实现了基础的语法分析，但是遗留了结合性的问题， 本节将解决该问题，同时利用生成的AST，做简单的数学运算。

目标：
解决上一节中结合性的问题
支持()优先级
实现数学表达式计算，并输出计算结果

结合性bug

上节中，
我们通过文法描述，基于运算符优先级定义了加法和乘法运算，并正确实现了优先级的问题
同时通过修改文法表达式的运算顺序，解决了左递归的问题
本节首先要看的是，为什么会引起结合性的问题
按照上节描述
1+2+3 形成的语法树如下

可以看出 本应该是 (1+2)+3 结果AST变成了 1+(2+3)
实际上，我们在写加法表达式的时候， 文法描述为

AdditiveExpression : 
	MultiplicativeExpression 
	AdditiveExpression + MultiplicativeExpression 
        AdditiveExpression - MultiplicativeExpression

AdditiveExpression是在左边的， 因为加法表达式是左结合的
但是上一节中，我们取巧改变了顺序解决左递归的问题，
本节将通过循环改写递归的方式解决左递归的问题

具体代码如下

 additive() {
        let tokens = this.tokens;
        let child = this.multiplicative();
        let node = child;

        if(child ) {
            while(true) { // 循环判断下一个表达式是否满足
                let nextToken = this.lexerLevel.tokenPeek()
                if(nextToken && (nextToken.type === this.lexerLevel.DfaState.Plus || nextToken.type === this.lexerLevel.DfaState.Minus)) {
                    nextToken = this.lexerLevel.tokenRead();
                    // 左侧已经满足是一个加法表达式, 判断右侧是否是一个乘法表达式
                    let childRight = this.multiplicative();
                    if(childRight) {
                        // 构建一个加法表达式 AstNode
                        node = new BinaryAstNode("Additive", nextToken.value, nextToken.type);
                        node.addRightChild(child)
                        node.addLeftChild(childRight)
                        // 上一个语句判断已经完成, 将当前add语句设为child
                        child = node;
                    } else {
                        throw Error("error Additive Expression")
                    }
                } else {
                    break;
                }
            }

        }
        return node
    }

如何实现()优先级

上节中，我们抽离出了primary表达式，用于处理优先级最高的表达式
()运算符同样需要放在该方法里处理
词法分析的部分就不多描述， 同样适用DFA解析即可

/**
     * primary Expressions
     * 针对最基本的预计, 我们设定文法规则如下, 只处理标识符 和 Number类型的字面量
     * v0.0.2 支持表达式 - (expression)
     * PrimaryExpression :
     *      Identifier
     *      Literal
     *      (expression)
     */
    primary() {
        let tokens = this.tokens;
        let node = null;

        // 预读判断
        let nextToken = this.lexerLevel.tokenPeek()
        if(nextToken) {
            // 判断是否符合文法规则
            if(nextToken.type === this.lexerLevel.DfaState.Identifier) {
                nextToken = this.lexerLevel.tokenRead();
                node = new PrimaryAstNode(this.lexerLevel.DfaState.Identifier, nextToken.value);
            } else if(nextToken.type === this.lexerLevel.DfaState.Num) {
                nextToken = this.lexerLevel.tokenRead();
                node = new PrimaryAstNode(this.lexerLevel.DfaState.Num, nextToken.value);
            } else if(nextToken.type === this.lexerLevel.DfaState.LeftParen) {
                // v0.0.2 新增支持( )简单处理
                nextToken = this.lexerLevel.tokenRead();
                // 检测下一个表达式， 目前实现的加法表达式最优
                node = this.additive();
                if(node) {
                    nextToken = this.lexerLevel.tokenPeek();
                    if(nextToken.type === this.lexerLevel.DfaState.RightParen) {
                        this.lexerLevel.tokenRead()
                    } else {
                        throw Error("right paren is lost")
                    }
                }
            }
            // 剩余类型待处理
        }

        return node

    }

本节中对AstNode节点扩展出了多个类型， 主要是用于解决本文目标之一：计算表达式的值

如何实现表达式计算

目标

类似 1+2*3, 2*3, 2+1+2+3+4等表达式，计算结果值并输出

如何实现

基于语法解析的结果， 我们已经得到了一颗完整的抽象语法树AST，
我们目前的表达式都是二元表达式，即一个表达式包括了
左侧表达式值 运算符 右侧表达式值

要计算1+2+3, 即对ast中的运算符节点做计算， 使用深度优先遍历，一层层解出表达式1， 表达式2即可

本节利用ast本身的node对象， 将递归遍历的过程分解到对象调用上

1. 设计ASTNode

class AstNode{
    constructor(type, value) {
        this.type = type;  // 节点类型
        this.value = value || ''; // 节点自身包含的值
        this.children = [] ;// 具备的子节点
        this.parent = null;// 对应的父节点
    }

    addChild(child) {
        this.children.push(child)
        child.parent = this;
    }


    getValue() {
        return this.value // 用于获取对应的值， 如2，3
    }
}


module.exports = AstNode

2. 实现primaryAstNode，标识一个token节点

const AstNode = require("./AstNode")
class PrimaryAstNode extends AstNode{
    constructor(type, value) {
        super(type, value)
    }

    /**
     * 先对普通值转int处理
     * @returns {*}
     */
    getValue(){
        if(this.type === "Identifier") {
            return this.value;
        }
        return Number(this.value);
    }
}

module.exports = PrimaryAstNode

3. 实现二元表达式节点

const AstNode = require("./AstNode")

class BinaryAstNode  extends AstNode{
    constructor(type, value, opera) {
        super(type, value)
        this.opera = opera;
        this.left = null;
        this.right = null;
    }

    getValue(){
	// 该方法中，对子节点做了循环调用， 如果right还是一个二元表达式，类似递归的效果
        switch(this.opera) {
            case "Plus":
                return this.left.getValue() + this.right.getValue();
            case "Minus":
                return this.left.getValue() - this.right.getValue();
            case "Star":
                return this.left.getValue() * this.right.getValue();
            case "Slash":
                return this.left.getValue() / this.right.getValue();
            case "LeftShirt":
                return this.left.getValue() << this.right.getValue();
            case "RightShirt":
                return this.left.getValue() >>> this.right.getValue();
            case "RightShirt2":
                return this.left.getValue() >>> this.right.getValue();
            case "Mod":
                return this.left.getValue() % this.right.getValue();
        }
        return NaN
    }

    addLeftChild(child) {
        this.left = child;
        super.addChild(child)
    }

    addRightChild(child) {
        this.right = child;
        super.addChild(child)
    }
}

module.exports = BinaryAstNode

测试

let syntaxLevel = new SyntaxLevel1("(2+3)*4")

   let node = syntaxLevel.astParse()

    // console.log(node)
    console.log("(2+3)*4=",node.getValue())

    let syntaxLevel2 = new SyntaxLevel1("3*4+2")

    console.log("3*4+2=",syntaxLevel2.astParse().getValue())

    let syntaxLevel3 = new SyntaxLevel1("3*4")

    console.log("3*4=",syntaxLevel3.astParse().getValue())

    let syntaxLevel4 = new SyntaxLevel1("2+3+4")

    console.log("2+3+4=",syntaxLevel4.astParse().getValue())

    let syntaxLevel5 = new SyntaxLevel1("3*4 *4 +2 + 5 /6")

    console.log("3*4 *4 +2 + 5 /6=",syntaxLevel5.astParse().getValue())


    let syntaxLevel6 = new SyntaxLevel1("1>>1+2")

    console.log("1>>1+2=",syntaxLevel6.astParse().getValue())

结果：

(2+3)*4= 20
3*4+2= 14
3*4= 12
2+3+4= 9
3*4 *4 +2 + 5 /6= 50.833333333333336
1>>1+2= 6