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，然后重新开始解析该非终结符。

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