编译原理实战入门：用 JavaScript 写一个简单的四则运算编译器（修订版）（一）

// CPU 无法识别
10 + 5
// 翻译成汇编语言
push 10
push 5
add
// 最后翻译为机器指令，汇编代码和机器指令一一对应
// 机器指令由 1 和 0 组成，以下指令非真实指令，只做演示用
0011101001010101
1101010011100101
0010100111100001

// 程序代码
10 + 5 + 6
// 词法分析后得到的 token
10
+
5
+
6

function lexicalAnalysis(expression) {
    const symbol = ['(', ')', '+', '-', '*', '/']
    const re = /\d/
    const tokens = []
    const chars = expression.trim().split('')
    let token = ''
    chars.forEach(c => {
        if (re.test(c)) {
            token += c
        } else if (c == ' ' && token) {
            tokens.push(token)
            token = ''
        } else if (symbol.includes(c)) {
            if (token) {
                tokens.push(token)
                token = ''
            } 
            tokens.push(c)
        }
    })
    if (token) {
        tokens.push(token)
    }
    return tokens
}
console.log(lexicalAnalysis('100    +   23   +    34 * 10 / 2')) 
// ["100", "+", "23", "+", "34", "*", "10", "/", "2"]

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
*/