语法分析，是我们对源程序进行详细解析的生成语法树AST的过程

目标
解析如下语句，形成AST
3 * 4 + 2
3 * 4
2 + 3 * 4

语法分析

在上一步词法分析中， 我们将源代码中的token做了解析， 获得了程序语言对应的tokens。 本步骤中我们将按语句构成，将语句形成语法树的结构。
AST的叶子节点是一个个token， 我们解析的目的就是将源程序解析成树级结构。

分析过程

解析关键词

1. 上下文无关文法(Context-Free Grammars)
   一个上下文无关文法由许多产生式(productions)组 成。
   每个产生式都拥有一个抽象符号作为 其左式(left-hand side)，被称为非终结 符(nonterminal)，以及一个由零个或多个非终结符和终结 符(terminal)组 成的右式(right-hand side)。对于每个文法而言，终结符是从一个特定的字母表中 抽取的。

2. 非终结符
   非token，及该符号最终可以被一个或多个token组合替换

文法描述

基于我们要实现的解析目标， 加法和乘法表达式， 这边我们先将ECMASCRIPT对应的文法表达式取出来看看是如何表示的

简化如下：

PrimaryExpression :
       Identifier
       Literal 

MultiplicativeExpression :
	PrimaryExpression
	MultiplicativeExpression * PrimaryExpression
	MultiplicativeExpression / PrimaryExpression

AdditiveExpression :
	MultiplicativeExpression
	AdditiveExpression + MultiplicativeExpression
	AdditiveExpression - MultiplicativeExpression

上述为文法记法
：之前位一个非终结符
：之后每行一个右式，用于替换左侧的非终结符

按我们理解的AST生成， 其实目标就是将一个个非终结符最终替换成终结符（tokens）

要实现我们本节的目标，就是要将代码按照我们的文法，使用对应的算法解析即可

解析算法

递归下降算法

从上述的文法中， 我们可以看出， 文法描述本身就可能是一个递归调用自身的过程， 同时文法的右式是一个下降调用的过程，add-> multi -> primary -> token

如何实现

1. ASTNode定义

由于我们的目标是生成抽象语法树， 所以首先需要定义Node

/**
 * Ast 节点对象
 * @param type
 * @param value
 * @constructor
 */
function AstNode (type, value) {
    this.type = type;
    this.value = value || '';
    this.children = []
    this.parent = null
}
// 定义节点父子关系
AstNode.prototype.addChild = function(child) {
    this.children.push(child)
    child.parent = this;
}

2. 实现primaryExpression

按primary文法描述， primaryExpression暂时包括Identifier 和 Literal两种

tokenPeek方法是一个预读方法， 用于取出当前token预判断，用于有效减少回流次数

 primary() {
        let tokens = this.tokens;
        let node = null;

        // 预读判断， 读取当前的token进行判断
        let nextToken = this.lexerLevel.tokenPeek()
        if(nextToken) {
            // 判断是否符合文法规则
            if(nextToken.type === this.lexerLevel.DfaState.Identifier) {
                nextToken = this.lexerLevel.tokenRead();
                node = new AstNode(this.lexerLevel.DfaState.Identifier, nextToken.value);
            } else if(nextToken.type === this.lexerLevel.DfaState.Num) {
                nextToken = this.lexerLevel.tokenRead();
                node = new AstNode(this.lexerLevel.DfaState.Num, nextToken.value);
            }
            // 其他默认先不处理
        }

        return node

    }

从上述实现可以看出， primary的实现完全是按照文法同构的， 非常容易理解

3. 实现Multiplicative 乘除法表达式

multiplicative() {
        let tokens = this.tokens;
        // 先判断是否符合基本表达式, 如果符合基本表达式, 暂时就已经找到了一个叶子节点(TOKEN)
        let child = this.primary();
        let node = child;

        let nextToken = this.lexerLevel.tokenPeek()
        if(child && nextToken) {
            if(nextToken.type === this.lexerLevel.DfaState.Star || nextToken.type === this.lexerLevel.DfaState.Slash) {
                nextToken = this.lexerLevel.tokenRead();
                // 表示右侧必有一个字面量或者 表达式对应  MultiplicativeExpression *(/) PrimaryExpression
                let childRight = this.multiplicative();
                if(childRight) {
                    // 构建一个乘法表达式 AstNode
                    node = new AstNode("Multiplicative", nextToken.value);
                    node.addChild(child)
                    node.addChild(childRight)
                } else {
                    throw Error("error Multiplicative Expression")
                }
            }
        }

        return node;

    }

从编码上看， 我们是先下降调用了primary, 实际文法中其实是MultiplicativeExpression * PrimaryExpression，如果先判断multi表达式， 会出现循环递归栈溢出的情况， 所以对文法做了调整 变成 PrimaryExpression * MultiplicativeExpression

4. 实现加法表达式

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

        let nextToken = this.lexerLevel.tokenPeek()
        if(child && nextToken) {
            if(nextToken.type === this.lexerLevel.DfaState.Plus || nextToken.type === this.lexerLevel.DfaState.Minus) {
                nextToken = this.lexerLevel.tokenRead();
                // 判断右侧是否是一个加法表达式
                let childRight = this.additive();
                if(childRight) {
                    // 构建一个加法表达式 AstNode
                    node = new AstNode("Additive", nextToken.value);
                    node.addChild(child)
                    node.addChild(childRight)
                } else {
                    throw Error("error Additive Expression")
                }
            }
        }
        return node
    }

5. 最后调用测试

demo：

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

   console.log(syntaxLevel.astParse())

结果：

AstNode {
  type: 'Additive',
  value: '+',
  children:
   [ AstNode { type: 'Num', value: '2', children: [], parent: [Circular] },
     AstNode {
       type: 'Multiplicative',
       value: '*',
       children:
        [ AstNode { type: 'Num', value: '3', children: [], parent: [Circular] },
          AstNode { type: 'Num', value: '4', children: [], parent: [Circular] } ],
       parent: [Circular] } ],
  parent: null }

总结

本节主要是借用js的加法乘法文法规则，练习了如何解析源代码形成AST的过程，
但是还遗留了一些问题， 如我们虽然解决了左递归，但是却破坏了运算符的结合性， 如 2+3+4?
下节我们将解决结合性的问题，及如何利用现有的语法树，做简单的语法节点计算。