编译原理实战入门：用 JavaScript 写一个简单的四则运算编译器（二）语法分析

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('+')                         +
   |_

// 5 + 5 转换为 5 5 + 再生成代码
push 5
push 5
add

// 汇编代码生成器
function AssemblyWriter() {
    this.output = ''
}
AssemblyWriter.prototype = {
    writePush(digit) {
        this.output += `push ${digit}\r\n`
    },
    writeOP(op) {
        this.output += op + '\r\n'
    },
    //输出汇编代码
    outputStr() {
        return this.output
    }
}
// 语法分析器
function Parser(tokens, writer) {
    this.writer = writer
    this.tokens = tokens
    // tokens 数组索引
    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
*/