递归下降解析器通过函数调用模拟文法规则推导，将非终结符转为函数，终结符匹配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，然后重新开始解析该非终结符。
错误恢复是一个比较复杂的问题，需要根据具体的文法和应用场景来选择合适的策略。
