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

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

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

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

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

expression: addExpression

addExpression: mulExpression (op mulExpression)*

mulExpression: term (op term)*

term: "(" expression ")" | integerConstant

op: + - * /

PS: addExpression 對(duì)應(yīng) + - 表達(dá)式，mulExpression 對(duì)應(yīng) * / 表達(dá)式。

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

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

先來看看怎么分析一個(gè)四則運(yùn)算表達(dá)式 1 + 2 * 3。

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

如下圖所示：

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

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é)符為止。

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

以上是對(duì)這兩種算法的簡(jiǎn)介，具體實(shí)現(xiàn)請(qǐng)看下方的代碼實(shí)現(xiàn)。

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

后綴表達(dá)式

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

示例：

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

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

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

如果上面的理論知識(shí)看不太懂，沒關(guān)系，先看代碼，再和理論知識(shí)結(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 {
                // 沒有匹配上相應(yīng)的操作符 這里為沒有匹配上 + - 
                // 將 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 {
                // 沒有匹配上相應(yīng)的操作符 這里為沒有匹配上 * / 
                // 將 token 索引后退一位
                this.i--
                break
            }
        }
    },

    compileTerm() {
        this.getNextToken()
        if (this.token == "(") {
            this.compileExpression()
            this.getNextToken()
            if (this.token != ")") {
                throw "缺少右括號(hào)：)"
            }
        } else if (/^d+$/.test(this.token)) {
            this.writer.writePush(this.token)
        } else {
            throw "錯(cuò)誤的 token：第 " + (this.i + 1) + " 個(gè) 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
*/

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

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

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

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

完整源碼