如何用JavaScript实现一个简单的解释器？-js教程-PHP中文网

答案是使用JavaScript实现解释器需经历词法分析、语法分析和求值三个阶段，通过Lexer将代码分解为token，Parser生成AST表达结构，Interpreter遍历AST计算结果。该过程清晰分离各阶段职责，利用AST体现运算优先级与结合性，支持后续扩展变量、控制流等特性，是构建语言处理系统的核心路径。

如何用javascript实现一个简单的解释器？

用JavaScript实现一个简单的解释器，核心思路是把输入的代码字符串一步步地处理，先是分解成一个个有意义的“词”（词法分析），然后根据语言规则把这些词组织成一个结构化的“句子”（语法分析，生成抽象语法树），最后再遍历这个“句子”结构，执行或求值。这听起来有点像把一堆散乱的乐高积木（词法分析）按图纸拼成一个模型（语法分析），然后让模型动起来（求值）。

解决方案

要用JavaScript实现一个简单的解释器，我们通常会遵循经典的解释器架构，主要包括三个阶段：词法分析（Lexing/Tokenizing）、语法分析（Parsing）和求值（Evaluation）。

1. 词法分析器 (Lexer/Tokenizer)

这是解释器的第一步，它的任务是将输入的源代码字符串分解成一系列有意义的“词素”（tokens）。每个token代表源代码中的一个基本单元，比如数字、运算符、括号、标识符等。

// 简单Token类型定义
const TokenType = {
    NUMBER: 'NUMBER',
    PLUS: 'PLUS',
    MINUS: 'MINUS',
    MULTIPLY: 'MULTIPLY',
    DIVIDE: 'DIVIDE',
    LPAREN: 'LPAREN',
    RPAREN: 'RPAREN',
    EOF: 'EOF' // End Of File
};

class Token {
    constructor(type, value) {
        this.type = type;
        this.value = value;
    }
    toString() {
        return `Token(${this.type}, ${this.value})`;
    }
}

class Lexer {
    constructor(text) {
        this.text = text;
        this.pos = 0;
        this.currentChar = this.text[this.pos];
    }

    advance() {
        this.pos++;
        this.currentChar = this.text[this.pos];
    }

    skipWhitespace() {
        while (this.currentChar !== undefined && /\s/.test(this.currentChar)) {
            this.advance();
        }
    }

    number() {
        let result = '';
        while (this.currentChar !== undefined && /\d/.test(this.currentChar)) {
            result += this.currentChar;
            this.advance();
        }
        return new Token(TokenType.NUMBER, parseInt(result));
    }

    getNextToken() {
        while (this.currentChar !== undefined) {
            if (/\s/.test(this.currentChar)) {
                this.skipWhitespace();
                continue;
            }

            if (/\d/.test(this.currentChar)) {
                return this.number();
            }

            if (this.currentChar === '+') {
                this.advance();
                return new Token(TokenType.PLUS, '+');
            }
            if (this.currentChar === '-') {
                this.advance();
                return new Token(TokenType.MINUS, '-');
            }
            if (this.currentChar === '*') {
                this.advance();
                return new Token(TokenType.MULTIPLY, '*');
            }
            if (this.currentChar === '/') {
                this.advance();
                return new Token(TokenType.DIVIDE, '/');
            }
            if (this.currentChar === '(') {
                this.advance();
                return new Token(TokenType.LPAREN, '(');
            }
            if (this.currentChar === ')') {
                this.advance();
                return new Token(TokenType.RPAREN, ')');
            }

            throw new Error(`Lexer error: Unknown character ${this.currentChar}`);
        }
        return new Token(TokenType.EOF, null);
    }
}

登录后复制

2. 语法分析器 (Parser)

语法分析器接收词法分析器生成的token流，并根据语言的语法规则将其组织成一个抽象语法树（AST）。AST是源代码的树状表示，它去除了源代码的表面细节（如空格、括号），只保留了其结构和语义信息。

立即学习“Java免费学习笔记（深入）”；

// AST节点定义
class AST { }

class BinOp extends AST {
    constructor(left, op, right) {
        super();
        this.left = left;
        this.op = op; // Token object
        this.right = right;
    }
}

class Num extends AST {
    constructor(token) {
        super();
        this.token = token;
        this.value = token.value;
    }
}

class Parser {
    constructor(lexer) {
        this.lexer = lexer;
        this.currentToken = this.lexer.getNextToken();
    }

    error(message = 'Invalid syntax') {
        throw new Error(`Parser error: ${message} at ${this.currentToken.toString()}`);
    }

    eat(tokenType) {
        if (this.currentToken.type === tokenType) {
            this.currentToken = this.lexer.getNextToken();
        } else {
            this.error(`Expected token type ${tokenType}`);
        }
    }

    // factor: NUMBER | LPAREN expr RPAREN
    factor() {
        const token = this.currentToken;
        if (token.type === TokenType.NUMBER) {
            this.eat(TokenType.NUMBER);
            return new Num(token);
        } else if (token.type === TokenType.LPAREN) {
            this.eat(TokenType.LPAREN);
            const node = this.expr();
            this.eat(TokenType.RPAREN);
            return node;
        }
        this.error('Unexpected token in factor');
    }

    // term: factor ((MUL | DIV) factor)*
    term() {
        let node = this.factor();

        while ([TokenType.MULTIPLY, TokenType.DIVIDE].includes(this.currentToken.type)) {
            const token = this.currentToken;
            if (token.type === TokenType.MULTIPLY) {
                this.eat(TokenType.MULTIPLY);
            } else if (token.type === TokenType.DIVIDE) {
                this.eat(TokenType.DIVIDE);
            }
            node = new BinOp(node, token, this.factor());
        }
        return node;
    }

    // expr: term ((PLUS | MINUS) term)*
    expr() {
        let node = this.term();

        while ([TokenType.PLUS, TokenType.MINUS].includes(this.currentToken.type)) {
            const token = this.currentToken;
            if (token.type === TokenType.PLUS) {
                this.eat(TokenType.PLUS);
            } else if (token.type === TokenType.MINUS) {
                this.eat(TokenType.MINUS);
            }
            node = new BinOp(node, token, this.term());
        }
        return node;
    }

    parse() {
        const node = this.expr();
        if (this.currentToken.type !== TokenType.EOF) {
            this.error('Unexpected token at end of expression');
        }
        return node;
    }
}

登录后复制

3. 求值器 (Interpreter/Evaluator)

求值器遍历AST，并执行或计算每个节点表示的操作。对于我们这个简单的算术解释器，它会递归地计算表达式的值。

class Interpreter {
    constructor(parser) {
        this.parser = parser;
    }

    visit(node) {
        if (node instanceof BinOp) {
            return this.visitBinOp(node);
        }
        if (node instanceof Num) {
            return this.visitNum(node);
        }
        throw new Error(`No visit method for ${node.constructor.name}`);
    }

    visitBinOp(node) {
        if (node.op.type === TokenType.PLUS) {
            return this.visit(node.left) + this.visit(node.right);
        }
        if (node.op.type === TokenType.MINUS) {
            return this.visit(node.left) - this.visit(node.right);
        }
        if (node.op.type === TokenType.MULTIPLY) {
            return this.visit(node.left) * this.visit(node.right);
        }
        if (node.op.type === TokenType.DIVIDE) {
            const rightValue = this.visit(node.right);
            if (rightValue === 0) {
                throw new Error("Division by zero!");
            }
            return this.visit(node.left) / rightValue;
        }
        throw new Error(`Unknown operator: ${node.op.type}`);
    }

    visitNum(node) {
        return node.value;
    }

    interpret() {
        const tree = this.parser.parse();
        return this.visit(tree);
    }
}

// 实际运行
function runInterpreter(text) {
    try {
        const lexer = new Lexer(text);
        const parser = new Parser(lexer);
        const interpreter = new Interpreter(parser);
        const result = interpreter.interpret();
        console.log(`Input: "${text}" => Result: ${result}`);
        return result;
    } catch (e) {
        console.error(`Error interpreting "${text}": ${e.message}`);
        return null;
    }
}

// 示例
runInterpreter("3 + 5 * (10 - 2) / 2"); // 应该输出 23
runInterpreter("10 / (2 + 3)"); // 应该输出 2
runInterpreter("7 - 3 * 2 + 1"); // 应该输出 2
runInterpreter("1 + 2 * (3 - 1)"); // 应该输出 5
runInterpreter("10 / 0"); // 应该报错
runInterpreter("10 % 3"); // 应该报错

登录后复制

这个简单的解释器实现了基本的四则运算和括号优先级。它展示了从源代码到结果的完整路径，虽然功能有限，但足以说明解释器的工作原理。

为什么我们需要抽象语法树（AST）？它在解释器中有什么作用？

你可能会问，为什么词法分析完直接求值不行，非要多此一举弄个AST？我的经验是，AST是解释器，乃至编译器，处理源代码的核心抽象。它就像一张详细的建筑蓝图，而不是一堆散落的砖头（token）。

首先，AST解决了语法结构和语义表达的问题。词法分析器输出的tokens只是扁平的序列，它们只知道自己是什么类型，但不知道它们之间的关系。比如

1 + 2 * 3

登录后复制

，词法分析器会得到

[NUMBER(1), PLUS, NUMBER(2), MULTIPLY, NUMBER(3)]

登录后复制

。从这个序列里，你很难直接看出来

登录后复制

的优先级比

登录后复制

高。但如果构建成AST，它会是一个

BinOp(left: Num(1), op: PLUS, right: BinOp(left: Num(2), op: MULTIPLY, right: Num(3)))

登录后复制

这样的树形结构，优先级关系一目了然。AST天然地表达了代码的层级结构和操作顺序。

其次，AST是解耦各个阶段的关键。有了AST，语法分析器和求值器就不用直接打交道了。语法分析器只负责把token流转换成AST，而求值器只负责遍历AST并计算结果。这种分离让每个模块的职责更单一，更易于开发和维护。想象一下，如果后续要添加新的语言特性，比如变量、函数，我们只需要扩展AST节点类型和求值器的

visit

登录后复制

方法，而词法分析器和基本的语法规则可能不需要大改。

再者，AST提供了丰富的语义信息。它不仅仅是结构，还能承载更多的信息。比如，你可以在AST节点上附带类型信息、作用域信息，甚至代码在源文件中的位置信息。这些对于错误报告、静态分析、代码优化等都非常有用。对于一个更复杂的语言，AST是进行类型检查、变量解析、控制流分析等高级操作的基础。没有AST，你很难想象如何有效地进行这些复杂的语义分析。它就是我们理解和操作代码的“语言”。

如何处理运算符优先级和结合性？

处理运算符优先级和结合性是构建语法分析器时的一个经典挑战，也是我个人觉得最能体现解析器设计精妙之处的地方。在我们的简单解释器中，我采用了“操作符优先级爬升”（Operator-Precedence Parsing）的一种简化形式，通过递归下降解析器（Recursive Descent Parser）的结构来隐式地处理。

Giiso写作机器人

Giiso写作机器人，让写作更简单

查看详情

具体来说，我们定义了不同的解析函数来对应不同的优先级层级：

```
factor()
```
登录后复制
: 优先级最高，处理数字和括号表达式。括号会强制其内部表达式先被计算，这自然就提升了括号内内容的优先级。
- ```
NUMBER
```
  登录后复制
  (例如
```
5
```
  登录后复制
  )
- ```
LPAREN expr RPAREN
```
  登录后复制
  (例如
```
(3 + 2)
```
  登录后复制
  )
```
term()
```
登录后复制
: 处理乘法和除法，它们的优先级高于加减法。
```
term
```
登录后复制
函数会首先调用
```
factor
```
登录后复制
来获取操作数，然后在一个
```
while
```
登录后复制
循环中，只要遇到乘除运算符，就继续获取下一个
```
factor
```
登录后复制
并构建
```
BinOp
```
登录后复制
节点。这个循环确保了乘除法会“吃掉”尽可能多的
```
factor
```
登录后复制
。
```
// 伪代码
node = factor();
while (currentToken is MULTIPLY or DIVIDE) {
    op = currentToken;
    eat(op.type);
    node = new BinOp(node, op, factor()); // 这里的factor()会是下一个操作数
}
return node;
```
登录后复制
这里体现了左结合性：
```
a * b * c
```
登录后复制
会被解析成
```
(a * b) * c
```
登录后复制
。当解析到第二个
```
*
```
登录后复制
时，
```
node
```
登录后复制
已经是
```
a * b
```
登录后复制
的结果，然后它会和
```
c
```
登录后复制
结合。
```
expr()
```
登录后复制
: 优先级最低，处理加法和减法。它的结构与
```
term()
```
登录后复制
类似，但它调用的是
```
term()
```
登录后复制
来获取操作数。这意味着在
```
expr
```
登录后复制
遇到加减法之前，
```
term
```
登录后复制
已经把所有乘除法处理完了。
```
// 伪代码
node = term();
while (currentToken is PLUS or MINUS) {
    op = currentToken;
    eat(op.type);
    node = new BinOp(node, op, term()); // 这里的term()会是下一个操作数
}
return node;
```
登录后复制
同样，这也处理了加减法的左结合性。

这种分层函数的设计巧妙地利用了函数调用的堆栈来模拟优先级。高优先级的操作符（如乘除）在低优先级操作符（如加减）的函数被调用之前，就已经被解析并构建到AST的更深层级中。而结合性则通过循环处理同一优先级操作符时，将新的操作数与当前已构建的AST节点结合来自然实现。这种方法对于简单的算术表达式非常有效，但对于更复杂的语法，可能需要更强大的解析技术，比如 Pratt Parser 或者使用解析器生成器。

构建一个简单的解释器时，有哪些常见的挑战和优化方向？

在我看来，构建解释器，即使是简单的，也充满了乐趣和挑战。以下是一些我遇到的常见挑战和一些可以考虑的优化方向：

常见挑战：

错误处理和报告：这是最让我头疼的地方。当用户输入不合法的代码时，解释器应该能给出清晰、有用的错误信息，指出错误发生的位置和原因。比如，是缺少括号？还是使用了未知符号？在我的例子中，错误信息只是简单的
```
Lexer error
```
登录后复制
或
```
Parser error
```
登录后复制
，这对于真实世界的应用来说是远远不够的。你需要记录token的位置（行号、列号），并在抛出错误时附带这些信息。
语法歧义：随着语言特性的增加，语法规则可能会变得复杂，容易产生歧义。比如，
```
a - b
```
登录后复制
是减法，但
```
a -b
```
登录后复制
可能是负数
```
b
```
登录后复制
的赋值。如何设计无歧义的语法规则，或者如何让解析器在有歧义时做出正确的选择，是很大的挑战。我们这个简单算术解释器在这方面还比较容易，因为语法非常有限。
运算符的复杂性：除了优先级和结合性，还有一元运算符（如
```
-5
```
登录后复制
）、三元运算符（如
```
a ? b : c
```
登录后复制
）等。一元运算符的处理需要特殊的语法规则，通常在
```
factor
```
登录后复制
阶段或更早的词法分析阶段就处理掉。
性能：对于简单的表达式，性能不是问题。但如果解释器需要处理大量代码，或者代码中包含循环、复杂的数据结构，那么求值阶段的效率就会变得很重要。递归下降解析器虽然直观，但对于非常大的输入，可能会有栈溢出的风险。
内存管理：AST可能会变得非常庞大，尤其是在处理大型源文件时。如何有效地构建和管理AST节点，避免内存泄漏，也是一个实际问题。

优化方向：

更健壮的错误恢复：当前的解释器在遇到第一个错误时就会停止。一个更友好的解释器应该尝试从错误中恢复，继续解析和报告后续的错误，这样用户可以一次性看到所有问题。这通常需要解析器具备跳过错误token的能力。
支持更多数据类型和操作：比如浮点数、字符串、布尔值。这需要在词法分析器中识别新的字面量，并在求值器中添加相应的操作逻辑。
添加变量和赋值：这是任何编程语言都必不可少的功能。你需要一个“符号表”（Symbol Table）或“环境”（Environment）来存储变量名及其对应的值。这会改变求值器的行为，因为它需要查找和更新变量。
控制流语句：
```
if/else
```
登录后复制
、
```
while
```
登录后复制
循环等。这需要引入新的AST节点类型来表示这些结构，并在求值器中实现相应的逻辑，比如条件跳转和循环执行。
函数定义与调用：这是语言的另一个核心特性。你需要处理函数参数、函数体、作用域链等。这会显著增加解释器的复杂性，特别是涉及闭包时。
优化AST遍历：对于复杂的AST，可以考虑使用迭代器模式而不是纯粹的递归，以避免JavaScript的递归深度限制。
即时编译 (JIT)：对于性能要求高的场景，可以考虑在解释执行的同时，将部分热点代码编译成机器码或字节码，从而提高执行效率。当然，这已经超出了“简单解释器”的范畴，进入了编译器的领域。

构建解释器是一个迭代的过程，从一个简单的计算器开始，逐步添加新的语言特性，你会发现很多设计模式和计算机科学原理都能在这里找到实际的应用。每解决一个问题，都像是在拼图上放对了一块，非常有成就感。

以上就是如何用JavaScript实现一个简单的解释器？的详细内容，更多请关注php中文网其它相关文章！