JavaScript解析器_递归下降算法实现-js教程-PHP中文网

JavaScript解析器_递归下降算法实现

幻影之瞳

发布： 2025-11-30 16:05:02

原创

825人浏览过

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

javascript解析器_递归下降算法实现

递归下降解析是一种直观且易于实现的自顶向下语法分析方法，常用于构建JavaScript等编程语言的解析器。它通过一组相互递归的函数来对应语法规则，每个函数负责解析语法中的一个非终结符。下面介绍如何使用递归下降算法实现一个简单的JavaScript表达式解析器。

基本原理与设计思路

递归下降解析器的核心是将语法规则转换为函数。每条规则对应一个函数，函数体内按照产生式的结构进行词法匹配和子规则调用。对于JavaScript中常见的表达式（如算术运算、变量访问），我们可以定义如下简化的语法规则：

Expression → Term (('+' | '-') Term)*
Term → Factor (('*' | '/') Factor)*
Factor → Number | Identifier | '(' Expression ')'

这个结构避免了左递归（否则会导致无限递归），适合递归下降实现。

词法分析：构建Tokenizer

在解析之前，需要将源代码分解为token流。这是递归下降解析的基础。

立即学习“Java免费学习笔记（深入）”；

function tokenize(source) {
  const tokens = [];
  let i = 0;
<p>while (i < source.length) {
const char = source[i];</p><pre class='brush:php;toolbar:false;'>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节点。

Qwen

阿里巴巴推出的一系列AI大语言模型和多模态模型

691

查看详情

function parseExpression(tokens, index = 0) {
  let node, nextIndex;
<p>[node, nextIndex] = parseTerm(tokens, index);</p><p>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
};
}</p><p>return [node, nextIndex];
}</p><p>function parseTerm(tokens, index) {
let node, nextIndex;</p><p>[node, nextIndex] = parseFactor(tokens, index);</p><p>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
};
}</p><p>return [node, nextIndex];
}</p><p>function parseFactor(tokens, index) {
const token = tokens[index];</p><p>if (token.type === 'Number') {
return [
{ type: 'Literal', value: token.value },
index + 1
];
}</p><p>if (token.type === 'Identifier') {
return [
{ type: 'Identifier', name: token.value },
index + 1
];
}</p><p>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];
}</p><p>throw new SyntaxError(<code>Unexpected token: ${token.value}</code>);
}</p>

登录后复制

使用示例与输出结构

测试一个简单表达式：a + 2 * b

const code = "a + 2 * b";
const tokens = tokenize(code);
const [ast] = parseExpression(tokens);
<p>console.log(JSON.stringify(ast, null, 2));</p>

登录后复制

输出的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解析器_递归下降算法实现的详细内容，更多请关注php中文网其它相关文章！