JS实现递归下降解析器教程

本文深入解析了使用JS实现递归下降解析器的原理与实践。递归下降解析器是一种强大的语法分析工具，它通过将文法规则转化为函数间的相互调用来实现。文章首先介绍了递归下降解析器的基本概念，即如何将非终结符对应到函数，终结符对应到token匹配。然后，以一个简单的算术表达式为例，详细阐述了如何构建Parser类，实现expression、term、factor等函数，并生成抽象语法树（AST）。同时，文章还讨论了如何消除左递归，进行词法分析（Tokenization），处理运算符的优先级和结合性，以及实现错误恢复等关键问题。通过阅读本文，开发者能够全面理解并掌握JS递归下降解析器的核心技术，并将其应用于实际项目中。

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

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

实现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)*

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

如何进行词法分析（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实现递归下降解析器教程》的内容介绍就到此结束，如果有什么疑问或者建议，可以在golang学习网公众号下多多回复交流；文中若有不正之处，也希望回复留言以告知！