Tiny Compiler

一个极小极小编译器，用于理解与展示编译器的核心原理。将 Lisp 风格语法编译为 JavaScript 语法。

仓库地址: https://github.com/WuChenDi/Front-End/tree/master/24-ast

示例

javascript

// 输入
(add 2 (subtract 4 2))

// 输出
add(2, subtract(4, 2));

快速开始

javascript

import { compiler } from './index.js'

const code = compiler('(multiply 2 (add 3 4))')
console.log(code) // multiply(2, add(3, 4));

单独使用各模块

javascript

import { tokenizer, parser, transformer, codeGenerator } from './index.js'

const tokens = tokenizer('(add 2 3)')
const ast = parser(tokens)
const newAst = transformer(ast)
const output = codeGenerator(newAst)

编译流程

源代码 → 词法分析 → 语法分析 → AST 转换 → 代码生成 → 目标代码
        Tokenizer  Parser   Transformer  CodeGen

完整的数据流：

Input: "(add 2 (subtract 4 2))"
    ↓
Tokenizer (词法分析)
    ↓
Token Array: [
  { type: 'paren', value: '(' },
  { type: 'name', value: 'add' },
  { type: 'number', value: '2' },
  ...
]
    ↓
Parser (语法分析)
    ↓
Original AST: {
  type: 'Program',
  body: [{ type: 'CallExpression', ... }]
}
    ↓
Transformer (AST 转换)
    ↓
New AST: {
  type: 'Program',
  body: [{ type: 'ExpressionStatement', ... }]
}
    ↓
Code Generator (代码生成)
    ↓
Output: "add(2, subtract(4, 2));"

核心模块详解

1. Tokenizer - 词法分析器

功能： 将字符串分解为 token 流

核心算法： 字符遍历 + 模式匹配

javascript

function tokenizer(input) {
  let current = 0        // 字符指针
  const tokens = []      // 结果数组
  
  while (current < input.length) {
    let char = input[current]
    
    // 识别括号
    if (char === '(') {
      tokens.push({ type: 'paren', value: '(' })
      current++
      continue
    }
    
    // 识别数字（连续读取）
    if (/[0-9]/.test(char)) {
      let value = ''
      while (/[0-9]/.test(char)) {
        value += char
        char = input[++current]
      }
      tokens.push({ type: 'number', value })
      continue
    }
    
    // 识别标识符
    if (/[a-z]/i.test(char)) {
      let value = ''
      while (/[a-z]/i.test(char)) {
        value += char
        char = input[++current]
      }
      tokens.push({ type: 'name', value })
      continue
    }
    
    // 识别字符串
    if (char === '"') {
      let value = ''
      char = input[++current]  // 跳过开始引号
      while (char !== '"') {
        value += char
        char = input[++current]
      }
      char = input[++current]  // 跳过结束引号
      tokens.push({ type: 'string', value })
      continue
    }
    
    // 跳过空白字符
    if (/\s/.test(char)) {
      current++
      continue
    }
    
    throw new TypeError('Unknown character: ' + char)
  }
  
  return tokens
}

识别的 Token 类型：

Token 类型	示例	正则/规则
`paren`	`(`, `)`	字符匹配
`number`	`2`, `42`	`/[0-9]/`
`string`	`"hello"`	引号包裹
`name`	`add`, `subtract`	`/[a-z]/i`
`whitespace`	空格、换行	`/\s/` (跳过)

示例：

javascript

'(add 2 3)' → [
  { type: 'paren', value: '(' },
  { type: 'name', value: 'add' },
  { type: 'number', value: '2' },
  { type: 'number', value: '3' },
  { type: 'paren', value: ')' }
]

2. Parser - 语法分析器

功能： 将 token 数组转换为抽象语法树（AST）

核心算法： 递归下降解析

javascript

function parser(tokens) {
  let current = 0
  
  function walk() {
    let token = tokens[current]
    
    // 处理数字
    if (token.type === 'number') {
      current++
      return {
        type: 'NumberLiteral',
        value: token.value,
      }
    }
    
    // 处理字符串
    if (token.type === 'string') {
      current++
      return {
        type: 'StringLiteral',
        value: token.value,
      }
    }
    
    // 处理函数调用表达式
    if (token.type === 'paren' && token.value === '(') {
      token = tokens[++current]  // 跳过 '('，获取函数名
      
      const 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(token.type)
  }
  
  const ast = {
    type: 'Program',
    body: [],
  }
  
  while (current < tokens.length) {
    ast.body.push(walk())
  }
  
  return ast
}

AST 节点类型：

javascript

// 程序根节点
{
  type: 'Program',
  body: [...]  // 顶层表达式数组
}

// 函数调用表达式
{
  type: 'CallExpression',
  name: 'add',
  params: [...]
}

// 数字字面量
{ type: 'NumberLiteral', value: '2' }

// 字符串字面量
{ type: 'StringLiteral', value: 'hello' }

示例：

javascript

Input: [
  { type: 'paren', value: '(' },
  { type: 'name', value: 'add' },
  { type: 'number', value: '2' },
  { type: 'number', value: '3' },
  { type: 'paren', value: ')' }
]

Output: {
  type: 'Program',
  body: [{
    type: 'CallExpression',
    name: 'add',
    params: [
      { type: 'NumberLiteral', value: '2' },
      { type: 'NumberLiteral', value: '3' }
    ]
  }]
}

3. Traverser - 遍历器

功能： 使用访问者模式遍历 AST

javascript

function traverser(ast, visitor) {
  function traverseNode(node, parent) {
    const methods = visitor[node.type]
    
    // 进入节点时调用
    if (methods && methods.enter) {
      methods.enter(node, parent)
    }
    
    // 递归遍历子节点
    switch (node.type) {
      case 'Program':
        traverseArray(node.body, node)
        break
      case 'CallExpression':
        traverseArray(node.params, node)
        break
      case 'NumberLiteral':
      case 'StringLiteral':
        // 字面量没有子节点
        break
    }
    
    // 离开节点时调用
    if (methods && methods.exit) {
      methods.exit(node, parent)
    }
  }
  
  traverseNode(ast, null)
}

访问者对象示例：

javascript

const visitor = {
  NumberLiteral: {
    enter(node, parent) {
      console.log('进入数字节点:', node.value)
    },
    exit(node, parent) {
      console.log('离开数字节点')
    }
  },
  CallExpression: {
    enter(node, parent) {
      console.log('进入函数调用:', node.name)
    }
  }
}

4. Transformer - AST 转换器

功能： 将 Lisp 风格 AST 转换为 C 风格 AST

核心技巧： 使用 _context 引用传递，实现父子节点的自动关联

AST 结构对比

旧 AST（Lisp 风格）：

javascript

{
  type: 'CallExpression',
  name: 'add',           // 函数名直接存储
  params: [...]          // 参数列表
}

新 AST（C 风格）：

javascript

{
  type: 'ExpressionStatement',
  expression: {
    type: 'CallExpression',
    callee: {
      type: 'Identifier',  // 函数名用标识符表示
      name: 'add'
    },
    arguments: [...]       // 参数列表改名
  }
}

`_context` 工作原理

这是转换器最精妙的设计：通过在旧 AST 节点上添加 _context 引用，指向新 AST 中的容器数组，子节点可以自动添加到正确位置。

javascript

function transformer(ast) {
  const newAst = {
    type: 'Program',
    body: [],
  }
  
  // 🔥 关键：建立引用关系
  ast._context = newAst.body
  
  traverser(ast, {
    NumberLiteral: {
      enter(node, parent) {
        // 子节点通过 parent._context 添加到父节点
        parent._context.push({
          type: 'NumberLiteral',
          value: node.value,
        })
      },
    },
    
    StringLiteral: {
      enter(node, parent) {
        parent._context.push({
          type: 'StringLiteral',
          value: node.value,
        })
      },
    },
    
    CallExpression: {
      enter(node, parent) {
        let expression = {
          type: 'CallExpression',
          callee: {
            type: 'Identifier',
            name: node.name,
          },
          arguments: [],
        }
        
        // 🔥 为当前节点设置 _context
        // 子节点（参数）会 push 到这个 arguments 数组
        node._context = expression.arguments
        
        // 顶层调用需要包装成 ExpressionStatement
        if (parent.type !== 'CallExpression') {
          expression = {
            type: 'ExpressionStatement',
            expression: expression,
          }
        }
        
        parent._context.push(expression)
      },
    },
  })
  
  return newAst
}

`_context` 传递示意图

旧 AST:                       新 AST:
Program                       Program
 ├─ _context ───────────────> body: []
 └─ CallExpression                ↑
     ├─ name: 'add'                │
     ├─ _context ─────────┐        │
     └─ params: [         │        │
          NumberLiteral   │        │
          (通过 parent._context.push() 添加)
        ]                 │        │
                          │        │
     (整个表达式 push ────────────┘)

为什么需要 _context？

javascript

// ❌ 没有 _context - 需要手动管理关系
function transform(oldNode, newParent) {
  const newNode = createNewNode(oldNode)
  newParent.children.push(newNode)  // 手动添加
  oldNode.children.forEach(child => {
    transform(child, newNode)        // 递归传递
  })
}

// ✅ 有 _context - 自动关联
traverser(ast, {
  SomeNode: {
    enter(node, parent) {
      const newNode = createNewNode(node)
      parent._context.push(newNode)     // 自动添加到正确位置
      node._context = newNode.children  // 设置子节点容器
    }
  }
})

5. Code Generator - 代码生成器

功能： 递归遍历 AST，生成目标代码字符串

javascript

function codeGenerator(node) {
  switch (node.type) {
    case 'Program':
      // 递归生成所有语句，用换行符连接
      return node.body.map(codeGenerator).join('\n')
    
    case 'ExpressionStatement':
      // 生成表达式并加分号
      return codeGenerator(node.expression) + ';'
    
    case 'CallExpression':
      // 生成：functionName(arg1, arg2, ...)
      return (
        codeGenerator(node.callee) +
        '(' +
        node.arguments.map(codeGenerator).join(', ') +
        ')'
      )
    
    case 'Identifier':
      return node.name
    
    case 'NumberLiteral':
      return node.value
    
    case 'StringLiteral':
      return '"' + node.value + '"'
    
    default:
      throw new TypeError(node.type)
  }
}

示例：

javascript

Input: {
  type: 'Program',
  body: [{
    type: 'ExpressionStatement',
    expression: {
      type: 'CallExpression',
      callee: { type: 'Identifier', name: 'add' },
      arguments: [
        { type: 'NumberLiteral', value: '2' },
        { type: 'NumberLiteral', value: '3' }
      ]
    }
  }]
}

Output: "add(2, 3);"

完整编译示例

让我们追踪一个完整的编译过程：

输入：

lisp

(add 2 (subtract 4 2))

步骤 1：Tokenizer

javascript

[
  { type: 'paren', value: '(' },
  { type: 'name', value: 'add' },
  { type: 'number', value: '2' },
  { type: 'paren', value: '(' },
  { type: 'name', value: 'subtract' },
  { type: 'number', value: '4' },
  { type: 'number', value: '2' },
  { type: 'paren', value: ')' },
  { type: 'paren', value: ')' }
]

步骤 2：Parser

javascript

{
  type: 'Program',
  body: [{
    type: 'CallExpression',
    name: 'add',
    params: [
      { type: 'NumberLiteral', value: '2' },
      {
        type: 'CallExpression',
        name: 'subtract',
        params: [
          { type: 'NumberLiteral', value: '4' },
          { type: 'NumberLiteral', value: '2' }
        ]
      }
    ]
  }]
}

步骤 3：Transformer

javascript

{
  type: 'Program',
  body: [{
    type: 'ExpressionStatement',
    expression: {
      type: 'CallExpression',
      callee: { type: 'Identifier', name: 'add' },
      arguments: [
        { type: 'NumberLiteral', value: '2' },
        {
          type: 'CallExpression',
          callee: { type: 'Identifier', name: 'subtract' },
          arguments: [
            { type: 'NumberLiteral', value: '4' },
            { type: 'NumberLiteral', value: '2' }
          ]
        }
      ]
    }
  }]
}

步骤 4：Code Generator

javascript

"add(2, subtract(4, 2));"

支持的语法

类型	语法	示例
数字	`42`	`(add 1 2)`
字符串	`"text"`	`(log "hello")`
函数调用	`(fn arg1 arg2)`	`(subtract 10 5)`
嵌套调用	`(fn1 (fn2 x))`	`(add 2 (multiply 3 4))`

运行测试

bash

npm run test

输出示例：

🚀 Starting Compiler Tests...

1. Testing Tokenizer...
   ✅ Tokenizer test passed!

2. Testing Parser...
   ✅ Parser test passed!

3. Testing Transformer...
   ✅ Transformer test passed!

4. Testing Code Generator...
   ✅ Code Generator test passed!

5. Testing full Compiler pipeline...
   ✅ Full compiler test passed!

🎉 All tests passed successfully!

技术亮点

访问者模式 (Visitor Pattern)

解耦遍历与转换逻辑，易于扩展新的节点操作

javascript

const visitor = {
  NodeType: {
    enter(node, parent) { },
    exit(node, parent) { }
  }
}

递归下降解析 (Recursive Descent)

代码结构清晰，直接对应文法规则

javascript

function walk() {
  if (isLiteral) return createLiteral()
  if (isExpression) {
    const node = createExpression()
    while (hasParams) {
      node.params.push(walk())  // 递归处理
    }
    return node
  }
}

上下文传递 (Context Reference)

通过 _context 引用实现父子节点自动关联，简化代码逻辑

javascript

ast._context = newAst.body
parent._context.push(newNode)
node._context = newNode.children

函数式编程

无副作用的纯函数设计，每个模块独立且可组合

javascript

const output = codeGenerator(
  transformer(
    parser(
      tokenizer(input)
    )
  )
)

扩展思路

1. 支持运算符

javascript

// (+ 2 3) → 2 + 3
// (* 2 (+ 3 4)) → 2 * (3 + 4)

2. 变量声明

javascript

// (let x 10) → let x = 10;
// (const name "Alice") → const name = "Alice";

3. 条件语句

javascript

// (if (> x 5) (console.log "big") (console.log "small"))
// →
// if (x > 5) {
//   console.log("big");
// } else {
//   console.log("small");
// }

4. 函数定义

javascript

// (defn add (a b) (+ a b))
// →
// function add(a, b) {
//   return a + b;
// }

5. 错误处理增强

javascript

// 提供行号、列号等详细错误信息
throw new CompilerError('Unexpected token', { line: 1, column: 5 })

6. 类型检查

javascript

// 添加简单的类型系统
(add 1 2)      // ✅ OK
(add 1 "foo")  // ❌ Error: Type mismatch

7. 代码优化

javascript

// 常量折叠
(add 2 3) → 5

// 死代码消除
if (false) { ... } → (删除)

学习资源

常见问题

Q: 为什么需要两个 AST？

A: 因为源语言（Lisp）和目标语言（C/JS）的语法结构不同。Lisp 的函数调用是 (name arg1 arg2)，而 C/JS 是 name(arg1, arg2)。两种 AST 分别对应这两种结构。

Q: `_context` 是必需的吗？

A: 不是必需的，但它大大简化了代码。没有它也可以实现转换，但需要手动管理父子节点关系，代码会更复杂。

Q: 这个编译器可以用于生产环境吗？

A: 不建议。这是一个教学项目，缺少很多生产环境必需的特性（错误恢复、性能优化、完整的语法支持等）。

Q: 如何添加新的语法特性？

A: 按照以下步骤：

在 Tokenizer 中添加新的 token 类型识别
在 Parser 中添加对应的 AST 节点构建逻辑
在 Transformer 中添加节点转换规则
在 Code Generator 中添加代码生成逻辑

Tiny Compiler ​

示例 ​

快速开始 ​

单独使用各模块 ​

编译流程 ​

核心模块详解 ​

1. Tokenizer - 词法分析器 ​

2. Parser - 语法分析器 ​

3. Traverser - 遍历器 ​

4. Transformer - AST 转换器 ​

AST 结构对比 ​

_context 工作原理 ​

_context 传递示意图 ​

5. Code Generator - 代码生成器 ​

完整编译示例 ​

支持的语法 ​

运行测试 ​

技术亮点 ​

访问者模式 (Visitor Pattern) ​

递归下降解析 (Recursive Descent) ​

上下文传递 (Context Reference) ​

函数式编程 ​

扩展思路 ​

1. 支持运算符 ​

2. 变量声明 ​

3. 条件语句 ​

4. 函数定义 ​

5. 错误处理增强 ​

6. 类型检查 ​

7. 代码优化 ​

学习资源 ​

常见问题 ​

Q: 为什么需要两个 AST？ ​

Q: _context 是必需的吗？ ​

Q: 这个编译器可以用于生产环境吗？ ​

Q: 如何添加新的语法特性？ ​

Tiny Compiler

示例

快速开始

单独使用各模块

编译流程

核心模块详解

1. Tokenizer - 词法分析器

2. Parser - 语法分析器

3. Traverser - 遍历器

4. Transformer - AST 转换器

AST 结构对比

`_context` 工作原理

`_context` 传递示意图

5. Code Generator - 代码生成器

完整编译示例

支持的语法

运行测试

技术亮点

访问者模式 (Visitor Pattern)

递归下降解析 (Recursive Descent)

上下文传递 (Context Reference)

函数式编程

扩展思路

1. 支持运算符

2. 变量声明

3. 条件语句

4. 函数定义

5. 错误处理增强

6. 类型检查

7. 代码优化

学习资源

常见问题

Q: 为什么需要两个 AST？

Q: `_context` 是必需的吗？

Q: 这个编译器可以用于生产环境吗？

Q: 如何添加新的语法特性？