首页 > 文章 > 前端

递归下降算法解析JavaScript实现

时间：2025-12-22 19:51:51 162浏览收藏

亲爱的编程学习爱好者，如果你点开了这篇文章，说明你对《JavaScript解析器：递归下降算法实现》很感兴趣。本篇文章就来给大家详细解析一下，主要介绍一下，希望所有认真读完的童鞋们，都有实质性的提高。

递归下降解析通过递归函数实现语法分析，将语法规则转为函数，配合词法分析器生成AST，适用于JavaScript表达式解析，需避免左递归并支持错误处理与位置追踪。

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;
}

解析器实现：递归函数结构

基于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模式恢复。

本篇关于《递归下降算法解析JavaScript实现》的介绍就到此结束啦，但是学无止境，想要了解学习更多关于文章的相关知识，请关注golang学习网公众号！

递归下降算法