摘要：語法分析對輸入的文本按照語法規(guī)則進行分析并確定其語法結(jié)構(gòu)的一種過程，稱為語法分析。遞歸下降分析法遞歸下降分析法，也稱為自頂向下分析法。表達式代碼生成我們通常用的四則運算表達式是中綴表達式，但是對于計算機來說中綴表達式不便于計算。

x* 表示 x 出現(xiàn)零次或多次

x | y 表示 x 或 y 將出現(xiàn)

( ) 圓括號，用于語言構(gòu)詞的分組

以下規(guī)則從左往右看，表示左邊的表達式還能繼續(xù)往下細分成右邊的表達式，一直細分到不可再分為止。

expression: addExpression

addExpression: mulExpression (op mulExpression)*

mulExpression: term (op term)*

term: "(" expression ")" | integerConstant

op: + - * /

PS: addExpression 對應 + - 表達式，mulExpression 對應 * / 表達式。

對輸入的文本按照語法規(guī)則進行分析并確定其語法結(jié)構(gòu)的一種過程，稱為語法分析。

一般語法分析的輸出為抽象語法樹（AST）或語法分析樹（parse tree）。但由于四則運算比較簡單，所以這里采取的方案是即時地進行代碼生成和錯誤報告，這樣就不需要在內(nèi)存中保存整個程序結(jié)構(gòu)。

先來看看怎么分析一個四則運算表達式 1 + 2 * 3。

首先匹配的是 expression，由于目前 expression 往下分只有一種可能，即 addExpression，所以分解為 addExpression。
依次類推，接下來的順序為 mulExpression、term、1（integerConstant）、+（op）、mulExpression、term、2（integerConstant）、*（op）、mulExpression、term、3（integerConstant）。

如下圖所示：

這里可能會有人有疑問，為什么一個表達式搞得這么復雜，expression 下面有 addExpression，addExpression 下面還有 mulExpression。
其實這里是為了考慮運算符優(yōu)先級而設的，mulExpr 比 addExpr 表達式運算級要高。

1 + 2 * 3
compileExpression
???|?compileAddExpr
???|??|?compileMultExpr
???|??|??|?compileTerm
???|??|??|??|_?matches integerConstant        push 1
  ?|??|??|_
? ?|??|?matches "+"
???|??|?compileMultExpr
???|??|??|?compileTerm
???|??|??|??|_?matches integerConstant        push 2
???|??|??|?matches "*"
???|??|??|?compileTerm
 ??|??|??|??|_?matches integerConstant        push 3
???|??|??|_?compileOp("*")                      *
???|??|_?compileOp("+")                         +
?  |_

有很多算法可用來構(gòu)建語法分析樹，這里只講兩種算法。

遞歸下降分析法，也稱為自頂向下分析法。按照語法規(guī)則一步步遞歸地分析 token 流，如果遇到非終結(jié)符，則繼續(xù)往下分析，直到終結(jié)符為止。

遞歸下降分析法是簡單高效的算法，LL(0)在此基礎上多了一個步驟，當?shù)谝粋€ token 不足以確定元素類型時，對下一個字元采取“提前查看”，有可能會解決這種不確定性。

以上是對這兩種算法的簡介，具體實現(xiàn)請看下方的代碼實現(xiàn)。

我們通常用的四則運算表達式是中綴表達式，但是對于計算機來說中綴表達式不便于計算。所以在代碼生成階段，要將中綴表達式轉(zhuǎn)換為后綴表達式。

后綴表達式

后綴表達式，又稱逆波蘭式，指的是不包含括號，運算符放在兩個運算對象的后面，所有的計算按運算符出現(xiàn)的順序，嚴格從左向右進行（不再考慮運算符的優(yōu)先規(guī)則）。

示例：

中綴表達式： 5 + 5 轉(zhuǎn)換為后綴表達式：5 5 +，然后再根據(jù)后綴表達式生成代碼。

// 5 + 5 轉(zhuǎn)換為 5 5 + 再生成代碼
push 5
push 5
add

編譯原理的理論知識像天書，經(jīng)常讓人看得云里霧里，但真正動手做起來，你會發(fā)現(xiàn)，其實還挺簡單的。

如果上面的理論知識看不太懂，沒關系，先看代碼，再和理論知識結(jié)合起來看。

注意：這里需要引入上一篇文章詞法分析的代碼。

// 匯編代碼生成器
function AssemblyWriter() {
    this.output = ""
}

AssemblyWriter.prototype = {
    writePush(digit) {
        this.output += `push ${digit}
`
    },

    writeOP(op) {
        this.output += op + "
"
    },

    //輸出匯編代碼
    outputStr() {
        return this.output
    }
}

// 語法分析器
function Parser(tokens, writer) {
    this.writer = writer
    this.tokens = tokens
    // tokens 數(shù)組索引
    this.i = -1
    this.opMap1 = {
        "+": "add",
        "-": "sub",
    }

    this.opMap2 = {
        "/": "div",
        "*": "mul"
    }

    this.init()
}

Parser.prototype = {
    init() {
        this.compileExpression()
    },

    compileExpression() {
        this.compileAddExpr()
    },

    compileAddExpr() {
        this.compileMultExpr()
        while (true) {
            this.getNextToken()
            if (this.opMap1[this.token]) {
                let op = this.opMap1[this.token]
                this.compileMultExpr()
                this.writer.writeOP(op)
            } else {
                // 沒有匹配上相應的操作符 這里為沒有匹配上 + - 
                // 將 token 索引后退一位
                this.i--
                break
            }
        }
    },

    compileMultExpr() {
        this.compileTerm()
        while (true) {
            this.getNextToken()
            if (this.opMap2[this.token]) {
                let op = this.opMap2[this.token]
                this.compileTerm()
                this.writer.writeOP(op)
            } else {
                // 沒有匹配上相應的操作符 這里為沒有匹配上 * / 
                // 將 token 索引后退一位
                this.i--
                break
            }
        }
    },

    compileTerm() {
        this.getNextToken()
        if (this.token == "(") {
            this.compileExpression()
            this.getNextToken()
            if (this.token != ")") {
                throw "缺少右括號：)"
            }
        } else if (/^d+$/.test(this.token)) {
            this.writer.writePush(this.token)
        } else {
            throw "錯誤的 token：第 " + (this.i + 1) + " 個 token (" + this.token + ")"
        }
    },

    getNextToken() {
        this.token = this.tokens[++this.i]
    },

    getInstructions() {
        return this.writer.outputStr()
    }
}

const tokens = lexicalAnalysis("100+10*10")
const writer = new AssemblyWriter()
const parser = new Parser(tokens, writer)
const instructions = parser.getInstructions()
console.log(instructions) // 輸出生成的匯編代碼
/*
push 100
push 10
push 10
mul
add
*/

編譯原理實戰(zhàn)入門：用 JavaScript 寫一個簡單的四則運算編譯器（一）詞法分析

編譯原理實戰(zhàn)入門：用 JavaScript 寫一個簡單的四則運算編譯器（二）語法分析

編譯原理實戰(zhàn)入門：用 JavaScript 寫一個簡單的四則運算編譯器（三）模擬執(zhí)行

編譯原理實戰(zhàn)入門：用 JavaScript 寫一個簡單的四則運算編譯器（四）結(jié)語

完整源碼