JS如何实现递归下降？解析器的实现-js教程-PHP中文网

JS如何实现递归下降？解析器的实现

月夜之吻

发布： 2025-08-22 08:48:02

原创

885人浏览过

递归下降解析器通过函数调用模拟文法规则推导，将非终结符转为函数，终结符匹配token，利用调用顺序体现优先级，循环实现左结合，消除左递归避免栈溢出，配合词法分析生成token流，并构建AST，错误恢复可采用跳过token至同步点。

js如何实现递归下降？解析器的实现

递归下降解析器，说白了，就是利用函数之间的相互调用来模拟文法规则的推导过程。每个非终结符对应一个函数，函数内部根据产生式规则选择性地调用其他函数（对应其他非终结符）或者直接匹配终结符。

实现JS递归下降解析器，核心在于将文法规则转化为可执行的代码逻辑。

解决方案

首先，你需要定义好你的文法。举个例子，我们来解析一个简单的算术表达式，包含加法和乘法：

expression : term ((PLUS | MINUS) term)*
term       : factor ((MUL | DIV) factor)*
factor     : NUMBER | LPAREN expression RPAREN

登录后复制

这里

PLUS

登录后复制

MINUS

登录后复制

MUL

登录后复制

DIV

登录后复制

NUMBER

登录后复制

LPAREN

登录后复制

RPAREN

登录后复制

都是终结符，

expression

登录后复制

term

登录后复制

factor

登录后复制

是非终结符。

接下来，为每个非终结符创建一个函数：

class Parser {
  constructor(tokens) {
    this.tokens = tokens;
    this.current = 0;
  }

  parse() {
    return this.expression();
  }

  expression() {
    let left = this.term();

    while (this.match("PLUS", "MINUS")) {
      let operator = this.previous();
      let right = this.term();
      left = { type: "Binary", operator, left, right }; // 构建抽象语法树 (AST)
    }

    return left;
  }

  term() {
    let left = this.factor();

    while (this.match("MUL", "DIV")) {
      let operator = this.previous();
      let right = this.factor();
      left = { type: "Binary", operator, left, right };
    }

    return left;
  }

  factor() {
    if (this.match("NUMBER")) {
      return { type: "Literal", value: this.previous().value };
    }

    if (this.match("LPAREN")) {
      let expr = this.expression();
      this.consume("RPAREN", "Expect ')' after expression.");
      return expr;
    }

    throw new Error("Expect expression.");
  }

  match(...types) {
    for (let type of types) {
      if (this.check(type)) {
        this.advance();
        return true;
      }
    }

    return false;
  }

  consume(type, message) {
    if (this.check(type)) {
      return this.advance();
    }

    throw new Error(message);
  }

  check(type) {
    if (this.isAtEnd()) return false;
    return this.peek().type === type;
  }

  advance() {
    if (!this.isAtEnd()) this.current++;
    return this.previous();
  }

  isAtEnd() {
    return this.peek().type === "EOF";
  }

  peek() {
    return this.tokens[this.current];
  }

  previous() {
    return this.tokens[this.current - 1];
  }
}

登录后复制

代码中，

expression

登录后复制

函数对应

expression

登录后复制

非终结符，内部调用

term

登录后复制

函数，并循环匹配

PLUS

登录后复制

或

MINUS

登录后复制

。

term

登录后复制

函数类似，对应

term

登录后复制

非终结符。

factor

登录后复制

函数处理数字和括号表达式。

关键点：

递归调用:
```
factor
```
登录后复制
函数中，如果遇到
```
LPAREN
```
登录后复制
，会递归调用
```
expression
```
登录后复制
函数，处理括号内的表达式。
错误处理:
```
consume
```
登录后复制
函数用于确保解析器按照预期找到特定的终结符，否则抛出错误。
抽象语法树 (AST): 代码构建了一个简单的 AST，用于后续的求值或者代码生成。 AST 的结构反映了表达式的语法结构。

如何处理左递归文法？

左递归文法是指文法规则中，某个非终结符直接或间接地推导出以自身开头的产生式。例如：

expression : expression PLUS term | term

登录后复制

如果直接按照上面的方式写递归下降解析器，会导致无限递归，栈溢出。解决办法是消除左递归。上面的文法可以改写成：

expression : term (PLUS term)*

登录后复制

ViiTor实时翻译

AI实时多语言翻译专家！强大的语音识别、AR翻译功能。

116

查看详情

也就是上面的代码实现的方式。本质上，是将左递归转换为右递归或者循环。

如何进行词法分析（Tokenization）？

在解析之前，需要将源代码转换成 token 流。 Tokenization 就是这个过程。一个简单的 Tokenizer 如下：

class Tokenizer {
  constructor(source) {
    this.source = source;
    this.current = 0;
    this.tokens = [];
  }

  tokenize() {
    while (!this.isAtEnd()) {
      this.start = this.current;
      this.scanToken();
    }

    this.tokens.push({ type: "EOF", lexeme: "", value: null, line: this.line });
    return this.tokens;
  }

  scanToken() {
    let char = this.advance();
    switch (char) {
      case '(': this.addToken("LPAREN"); break;
      case ')': this.addToken("RPAREN"); break;
      case '+': this.addToken("PLUS"); break;
      case '-': this.addToken("MINUS"); break;
      case '*': this.addToken("MUL"); break;
      case '/': this.addToken("DIV"); break;
      case ' ':
      case '\r':
      case '\t':
        // Ignore whitespace.
        break;
      default:
        if (this.isDigit(char)) {
          this.number();
        } else {
          throw new Error("Unexpected character.");
        }
    }
  }

  number() {
    while (this.isDigit(this.peek())) this.advance();

    this.addToken("NUMBER", Number(this.source.substring(this.start, this.current)));
  }

  isDigit(char) {
    return char >= '0' && char <= '9';
  }

  addToken(type, literal = null) {
    const text = this.source.substring(this.start, this.current);
    this.tokens.push({ type, lexeme: text, value: literal, line: this.line });
  }

  advance() {
    this.current++;
    return this.source[this.current - 1];
  }

  peek() {
    if (this.isAtEnd()) return '\0';
    return this.source[this.current];
  }

  isAtEnd() {
    return this.current >= this.source.length;
  }
}

登录后复制

Tokenizer 的作用是将字符串分解成 token 数组，例如

"(1 + 2) * 3"

登录后复制

会被分解成

[LPAREN, NUMBER(1), PLUS, NUMBER(2), RPAREN, MUL, NUMBER(3)]

登录后复制

。

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

优先级和结合性是算术表达式解析中的重要概念。优先级决定了运算符的运算顺序（例如，乘除优先于加减），结合性决定了相同优先级运算符的运算顺序（例如，左结合的加法

1 + 2 + 3

登录后复制

等价于

(1 + 2) + 3

登录后复制

）。

在递归下降解析器中，优先级通过函数的调用顺序来体现。例如，

expression

登录后复制

函数调用

term

登录后复制

函数，而

term

登录后复制

函数调用

factor

登录后复制

函数，就意味着

factor

登录后复制

中的运算符（例如括号）优先级最高，其次是

term

登录后复制

中的运算符（例如乘除），最后是

expression

登录后复制

中的运算符（例如加减）。

结合性通过循环的方向来控制。例如，上面的

expression

登录后复制

和

term

登录后复制

函数中的

while

登录后复制

循环是从左到右的，因此加法和乘法都是左结合的。如果要实现右结合，需要调整循环的方向或者使用递归。

如何进行错误恢复？

解析过程中难免会遇到错误，例如语法错误。好的解析器应该能够尽可能地从错误中恢复，继续解析，而不是直接崩溃。

错误恢复的策略有很多种，例如：

Panic Mode: 遇到错误后，跳过一些 token，直到遇到一个同步 token（例如分号、括号），然后继续解析。
Rule Resynchronization: 在每个非终结符对应的函数中，定义一些同步 token。遇到错误后，跳过一些 token，直到遇到同步 token，然后重新开始解析该非终结符。

错误恢复是一个比较复杂的问题，需要根据具体的文法和应用场景来选择合适的策略。

以上就是JS如何实现递归下降？解析器的实现的详细内容，更多请关注php中文网其它相关文章！