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