使用JavaScript实现一个简单的AST解析器_js编译原理-js教程-PHP中文网

使用JavaScript实现一个简单的AST解析器_js编译原理

betcha

发布： 2025-10-31 18:18:02

原创

275人浏览过

首先实现词法分析将代码转为Token，再通过递归下降解析器构建AST，正确处理运算优先级，最终生成反映表达式结构的抽象语法树。

使用javascript实现一个简单的ast解析器_js编译原理

要实现一个简单的AST（抽象语法树）解析器，我们需要从词法分析（Lexer）开始，接着进行语法分析（Parser），最终生成AST。这个过程是编译原理中的核心部分，适用于构建DSL、模板引擎或简化脚本语言。

词法分析：将代码拆分为 Token

词法分析的目标是把源代码字符串转换成一个个有意义的标记（Token）。比如对于表达式 2 + 3 * 4，我们希望得到类似：

[ { type: 'number', value: '2' }, { type: 'operator', value: '+' }, { type: 'number', value: '3' }, { type: 'operator', value: '*' }, { type: 'number', value: '4' } ]

下面是一个简单的 Lexer 实现：

function tokenize(input) {
  const tokens = [];
  let i = 0;
<p>while (i < input.length) {
let char = input[i];</p><pre class="brush:php;toolbar:false;"><pre class="brush:php;toolbar:false;">if (char === '+' || char === '-' || char === '*' || char === '/') {
  tokens.push({ type: 'operator', value: char });
  i++;
  continue;
}

if (/\d/.test(char)) {
  let num = '';
  while (i < input.length && /\d/.test(input[i])) {
    num += input[i++];
  }
  tokens.push({ type: 'number', value: parseInt(num, 10) });
  continue;
}

if (char === ' ') {
  i++;
  continue;
}

throw new Error(`未知字符: ${char}`);

登录后复制

}

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

return tokens; }

语法分析：根据 Token 构建 AST

语法分析的任务是根据 Token 流构建出一棵树结构，体现运算的优先级和嵌套关系。我们采用递归下降的方式处理表达式，并优先处理乘除（高优先级），再处理加减（低优先级）。

目标AST结构示例：

{ type: 'BinaryExpression', operator: '+', left: { type: 'NumberLiteral', value: 2 }, right: { type: 'BinaryExpression', operator: '*', left: { type: 'NumberLiteral', value: 3 }, right: { type: 'NumberLiteral', value: 4 } } }

下面是 Parser 的实现：

ViiTor实时翻译

AI实时多语言翻译专家！强大的语音识别、AR翻译功能。

116

查看详情

function parse(tokens) {
  let current = 0;
<p>function walk() {
let token = tokens[current];</p><pre class="brush:php;toolbar:false;"><pre class="brush:php;toolbar:false;">if (token.type === 'number') {
  current++;
  return {
    type: 'NumberLiteral',
    value: token.value
  };
}

if (
  token.type === 'operator' &&
  (token.value === '+' || token.value === '-')
) {
  current++; // 跳过操作符
  return {
    type: 'BinaryExpression',
    operator: token.value,
    left: walk(),         // 左边可能是更复杂的表达式
    right: parseMultiplication() // 右边优先处理乘除
  };
}

throw new Error(`无法解析的 token: ${token.value}`);

登录后复制

}

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

// 单独处理乘除法，保证优先级更高 function parseMultiplication() { let token = tokens[current];

if (token.type === 'number') {
  current++;
  return {
    type: 'NumberLiteral',
    value: token.value
  };
}

if (
  token.type === 'operator' &&
  (token.value === '*' || token.value === '/')
) {
  current++;
  return {
    type: 'BinaryExpression',
    operator: token.value,
    left: parseMultiplication(),
    right: parseMultiplication()
  };
}

throw new Error(`期望一个数字或乘除操作符`);

登录后复制

}

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

const ast = { type: 'Program', body: [] };

while (current < tokens.length) { ast.body.push(walk()); }

return ast; }

测试整个流程

现在我们可以组合 Lexer 和 Parser 来测试一个简单表达式：

<pre class="brush:php;toolbar:false;">const code = "2 + 3 * 4";
const tokens = tokenize(code);
const ast = parse(tokens);
console.log(JSON.stringify(ast, null, 2));

登录后复制

输出结果会正确反映优先级：

{ "type": "Program", "body": [ { "type": "BinaryExpression", "operator": "+", "left": { "type": "NumberLiteral", "value": 2 }, "right": { "type": "BinaryExpression", "operator": "*", "left": { "type": "NumberLiteral", "value": 3 }, "right": { "type": "NumberLiteral", "value": 4 } } } ] }