词法分析将源码拆分为tokens，语法分析构建AST，最终生成类似add(1,multiply(2,3))的表达式树。
实现一个简单的编译器，核心第一步是从源码构建出抽象语法树（AST）。这个过程主要包括词法分析（Lexical Analysis）和语法分析（Parsing）。下面用 JavaScript 实现一个极简的编译器，支持类似 add(1, multiply(2, 3)) 这样的表达式，并生成对应的 AST。
词法分析：将源码拆分为 Token
词法分析器（Tokenizer）读取源代码字符串，将其分解为有意义的标记（tokens），比如标识符、括号、数字等。
function tokenizer(input) {
let current = 0;
const tokens = [];
while (current < input.length) {
let char = input[current];
// 处理括号
if (char === '(' || char === ')') {
tokens.push({
type: 'paren',
value: char
});
current++;
continue;
}
// 跳过空白字符
if (/\s/.test(char)) {
current++;
continue;
}
// 处理数字（支持多位）
if (/[0-9]/.test(char)) {
let value = '';
while (/[0-9]/.test(input[current])) {
value += input[current++];
}
tokens.push({ type: 'number', value });
continue;
}
// 处理字母（用于函数名如 add, multiply）
if (/[a-z]/i.test(char)) {
let value = '';
while (/[a-z]/i.test(input[current])) {
value += input[current++];
}
tokens.push({ type: 'name', value });
continue;
}
throw new TypeError('未知字符: ' + char);
}
return tokens;
}
语法分析：从 Token 构建 AST
语法分析器（Parser）遍历 tokens，根据语法规则构造出 AST。我们假设语法是类似 Lisp 的结构：函数调用写成 (func arg1 arg2)。
function parser(tokens) {
let current = 0;
function walk() {
let token = tokens[current];
// 如果是数字，生成 NumberLiteral 节点
if (token.type === 'number') {
current++;
return {
type: 'NumberLiteral',
value: token.value
};
}
// 如果是左括号，说明是函数调用
if (token.type === 'paren' && token.value === '(') {
token = tokens[++current]; // 跳过 '('
// 下一个 token 是函数名
let node = {
type: 'CallExpression',
name: token.value,
params: []
};
token = tokens[++current]; // 跳过函数名
// 收集参数，直到遇到右括号
while (token.type !== 'paren' || token.value !== ')') {
node.params.push(walk()); // 递归解析子节点
token = tokens[current];
}
current++; // 跳过 ')'
return node;
}
throw new TypeError('Unexpected token: ' + token.type);
}
let ast = {
type: 'Program',
body: []
};
while (current < tokens.length) {
ast.body.push(walk());
}
return ast;
}
完整示例：从源码到 AST
把上面两个部分组合起来，就可以把一段简单代码转换成 AST。
立即学习“Java免费学习笔记（深入）”；
// 示例输入 const input = 'add(1, multiply(2, 3))'; // 执行编译步骤 const tokens = tokenizer(input); const ast = parser(tokens); console.log(JSON.stringify(ast, null, 2));
输出结果如下：
{
"type": "Program",
"body": [
{
"type": "CallExpression",
"name": "add",
"params": [
{
"type": "NumberLiteral",
"value": "1"
},
{
"type": "CallExpression",
"name": "multiply",
"params": [
{
"type": "NumberLiteral",
"value": "2"
},
{
"type": "NumberLiteral",
"value": "3"
}
]
}
]
}
]
}
总结与扩展思路
这个简易编译器完成了从源码到 AST 的基本流程：
- Tokenizer 把字符串变成 token 流
- Parser 利用递归下降方法构建树形结构
- 输出符合约定格式的 AST，便于后续遍历、转换或生成代码
你可以在此基础上扩展：
- 支持更多语法，如变量、操作符（+、-）、if 表达式
- 加入错误处理和位置信息（行、列）
- 添加遍历器（traverser）和转换器（transformer）来实现完整编译流程
