递归下降解析通过递归函数实现语法分析，将语法规则转为函数，配合词法分析器生成AST，适用于JavaScript表达式解析，需避免左递归并支持错误处理与位置追踪。
递归下降解析是一种直观且易于实现的自顶向下语法分析方法，常用于构建JavaScript等编程语言的解析器。它通过一组相互递归的函数来对应语法规则，每个函数负责解析语法中的一个非终结符。下面介绍如何使用递归下降算法实现一个简单的JavaScript表达式解析器。
基本原理与设计思路
递归下降解析器的核心是将语法规则转换为函数。每条规则对应一个函数，函数体内按照产生式的结构进行词法匹配和子规则调用。对于JavaScript中常见的表达式（如算术运算、变量访问），我们可以定义如下简化的语法规则：
- Expression → Term (('+' | '-') Term)*
- Term → Factor (('*' | '/') Factor)*
- Factor → Number | Identifier | '(' Expression ')'
这个结构避免了左递归（否则会导致无限递归），适合递归下降实现。
词法分析：构建Tokenizer
在解析之前，需要将源代码分解为token流。这是递归下降解析的基础。
function tokenize(source) {
const tokens = [];
let i = 0;
while (i < source.length) {
const char = source[i];
if (/\s/.test(char)) {
i++;
continue;
}
if (/[0-9]/.test(char)) {
let num = '';
while (i < source.length && /[0-9]/.test(source[i])) {
num += source[i++];
}
tokens.push({ type: 'Number', value: Number(num) });
continue;
}
if (/[a-zA-Z_]/.test(char)) {
let ident = '';
while (i < source.length && /[a-zA-Z_0-9]/.test(source[i])) {
ident += source[i++];
}
tokens.push({ type: 'Identifier', value: ident });
continue;
}
if (char === '+' || char === '-' || char === '*' || char === '/' || char === '(' || char === ')') {
tokens.push({ type: 'Punctuator', value: char });
i++;
continue;
}
throw new Error(`Unknown character: ${char}`);}
tokens.push({ type: 'EOF' });
return tokens;
}
let num = '';
while (i < source.length && /[0-9]/.test(source[i])) {
num += source[i++];
}
tokens.push({ type: 'Number', value: Number(num) });
continue;
}
if (/[a-zA-Z_]/.test(char)) {
let ident = '';
while (i < source.length && /[a-zA-Z_0-9]/.test(source[i])) {
ident += source[i++];
}
tokens.push({ type: 'Identifier', value: ident });
continue;
}
if (char === '+' || char === '-' || char === '*' || char === '/' || char === '(' || char === ')') {
tokens.push({ type: 'Punctuator', value: char });
i++;
continue;
}
throw new Error(`Unknown character: ${char}`);解析器实现：递归函数结构
基于token流，我们实现对应的解析函数。每个函数消耗匹配的token，并返回AST节点。
function parseExpression(tokens, index = 0) {
let node, nextIndex;
[node, nextIndex] = parseTerm(tokens, index);
while (tokens[nextIndex]?.value === '+' || tokens[nextIndex]?.value === '-') {
const op = tokens[nextIndex].value;
let right;
[right, nextIndex] = parseTerm(tokens, nextIndex + 1);
node = {
type: 'BinaryExpression',
operator: op,
left: node,
right: right
};
}
return [node, nextIndex];
}
function parseTerm(tokens, index) {
let node, nextIndex;
[node, nextIndex] = parseFactor(tokens, index);
while (tokens[nextIndex]?.value === '*' || tokens[nextIndex]?.value === '/') {
const op = tokens[nextIndex].value;
let right;
[right, nextIndex] = parseFactor(tokens, nextIndex + 1);
node = {
type: 'BinaryExpression',
operator: op,
left: node,
right: right
};
}
return [node, nextIndex];
}
function parseFactor(tokens, index) {
const token = tokens[index];
if (token.type === 'Number') {
return [
{ type: 'Literal', value: token.value },
index + 1
];
}
if (token.type === 'Identifier') {
return [
{ type: 'Identifier', name: token.value },
index + 1
];
}
if (token.value === '(') {
let expr;
[expr, index] = parseExpression(tokens, index + 1);
if (tokens[index]?.value !== ')') {
throw new SyntaxError('Expected closing parenthesis');
}
return [expr, index + 1];
}
throw new SyntaxError(Unexpected token: ${token.value});
}
使用示例与输出结构
测试一个简单表达式：a + 2 * b
const code = "a + 2 * b"; const tokens = tokenize(code); const [ast] = parseExpression(tokens);console.log(JSON.stringify(ast, null, 2));
输出的AST大致如下：
{
"type": "BinaryExpression",
"operator": "+",
"left": { "type": "Identifier", "name": "a" },
"right": {
"type": "BinaryExpression",
"operator": "*",
"left": { "type": "Literal", "value": 2 },
"right": { "type": "Identifier", "name": "b" }
}
}
基本上就这些。递归下降虽然不能处理所有文法（比如左递归需改写），但对大多数常见语法足够有效，尤其适合手写解析器。配合良好的错误提示和扩展机制，可以逐步支持更完整的JavaScript语法。不复杂但容易忽略的是token位置追踪和错误恢复，实际项目中建议加入行列号记录和panic模式恢复。
