393 lines
10 KiB
Markdown
393 lines
10 KiB
Markdown
# Tiny C Compiler in C# - Technical Design
|
||
|
||
Feature Name: tiny-c-compiler-csharp
|
||
Updated: 2026-05-20
|
||
|
||
## Description
|
||
|
||
本项目实现一个使用 C# 编写的 C 语言编译器，参考 TCC 的设计理念。编译器将 C 源代码直接编译为 x86/x64 本地机器码，不经过 MSIL 中间层。项目目标是实现一个轻量级、编译速度快的 C 编译器，支持 C99 标准的核心子集。
|
||
|
||
## Architecture
|
||
|
||
```mermaid
|
||
graph TD
|
||
A["C Source Code\n.c files"] --> B["Preprocessor\n预处理"]
|
||
B --> C["Lexer\n词法分析"]
|
||
C --> D["Parser\n语法分析"]
|
||
D --> E["Semantic Analyzer\n语义分析"]
|
||
E --> F["IR Generator\n中间表示生成"]
|
||
F --> G["Code Generator\n代码生成 x86/x64"]
|
||
G --> H["Object File\nPE/ELF"]
|
||
H --> I["Executable\n可执行文件"]
|
||
|
||
J["Error Handler"] -.-> B
|
||
J -.-> C
|
||
J -.-> D
|
||
J -.-> E
|
||
J -.-> F
|
||
J -.-> G
|
||
|
||
K["Symbol Table"] -.-> E
|
||
K -.-> F
|
||
K -.-> G
|
||
|
||
L["Type System"] -.-> E
|
||
L -.-> F
|
||
```
|
||
|
||
### Architecture Overview
|
||
|
||
编译器采用传统的单遍或多遍编译架构，分为以下主要阶段：
|
||
|
||
1. **预处理阶段**：处理宏展开、条件编译、头文件包含
|
||
2. **前端阶段**：词法分析、语法分析、语义分析
|
||
3. **中间阶段**：IR 生成与优化
|
||
4. **后端阶段**：x86/x64 代码生成与可执行文件输出
|
||
|
||
## Components and Interfaces
|
||
|
||
### 1. Preprocessor (预处理器)
|
||
|
||
**职责**：
|
||
- 处理 `#include` 指令，展开头文件
|
||
- 处理 `#define` 宏定义和宏展开
|
||
- 处理条件编译 `#ifdef`、`#ifndef`、`#endif`、`#if`
|
||
- 处理 `#pragma` 指令
|
||
|
||
**接口**：
|
||
```csharp
|
||
public interface IPreprocessor
|
||
{
|
||
string Preprocess(string sourceCode, string sourceFile);
|
||
void AddIncludePath(string path);
|
||
void DefineMacro(string name, string? value);
|
||
}
|
||
```
|
||
|
||
### 2. Lexer (词法分析器)
|
||
|
||
**职责**：
|
||
- 将预处理后的源代码分解为 token 流
|
||
- 识别关键字、标识符、字面量、运算符、分隔符
|
||
- 跳过注释和空白
|
||
- 报告词法错误
|
||
|
||
**接口**：
|
||
```csharp
|
||
public interface ILexer
|
||
{
|
||
IEnumerable<Token> Tokenize(string source);
|
||
}
|
||
|
||
public enum TokenType
|
||
{
|
||
Keyword, Identifier, IntLiteral, FloatLiteral,
|
||
CharLiteral, StringLiteral, Operator, Separator,
|
||
EOF, Error
|
||
}
|
||
|
||
public record Token(
|
||
TokenType Type,
|
||
string Lexeme,
|
||
object? Value,
|
||
SourceLocation Location
|
||
);
|
||
```
|
||
|
||
### 3. Parser (语法分析器)
|
||
|
||
**职责**：
|
||
- 实现递归下降解析器
|
||
- 构建抽象语法树（AST）
|
||
- 处理 C 语言的运算符优先级
|
||
- 报告语法错误
|
||
|
||
**接口**：
|
||
```csharp
|
||
public interface IParser
|
||
{
|
||
AstNode Parse();
|
||
}
|
||
|
||
public abstract record AstNode(SourceLocation Location);
|
||
public record ProgramNode(List<DeclarationNode> Declarations, SourceLocation Location) : AstNode(Location);
|
||
public record FunctionDeclarationNode(
|
||
TypeNode ReturnType,
|
||
string Name,
|
||
List<ParameterNode> Parameters,
|
||
BlockStatementNode Body,
|
||
SourceLocation Location
|
||
) : AstNode(Location);
|
||
```
|
||
|
||
### 4. Semantic Analyzer (语义分析器)
|
||
|
||
**职责**：
|
||
- 类型检查与类型推断
|
||
- 符号表管理
|
||
- 作用域管理
|
||
- 语义错误报告
|
||
|
||
**接口**：
|
||
```csharp
|
||
public interface ISemanticAnalyzer
|
||
{
|
||
void Analyze(AstNode root);
|
||
}
|
||
|
||
public interface ISymbolTable
|
||
{
|
||
void EnterScope();
|
||
void ExitScope();
|
||
void AddSymbol(string name, Symbol symbol);
|
||
Symbol? Lookup(string name);
|
||
}
|
||
```
|
||
|
||
### 5. IR Generator (中间表示生成器)
|
||
|
||
**职责**：
|
||
- 将 AST 转换为三地址码形式的 IR
|
||
- 构建控制流图（CFG）
|
||
- 支持基本优化（常量折叠、死代码消除）
|
||
|
||
**接口**：
|
||
```csharp
|
||
public interface IIrGenerator
|
||
{
|
||
IrProgram Generate(AstNode ast);
|
||
}
|
||
|
||
public record IrProgram(List<IrFunction> Functions);
|
||
public record IrFunction(string Name, List<IrBasicBlock> BasicBlocks);
|
||
public record IrBasicBlock(string Label, List<IrInstruction> Instructions);
|
||
public abstract record IrInstruction;
|
||
```
|
||
|
||
### 6. Code Generator (代码生成器)
|
||
|
||
**职责**：
|
||
- 将 IR 转换为 x86/x64 机器码
|
||
- 寄存器分配
|
||
- 栈帧管理
|
||
- 遵循平台调用约定
|
||
|
||
**接口**：
|
||
```csharp
|
||
public interface ICodeGenerator
|
||
{
|
||
byte[] Generate(IrProgram program, TargetArchitecture architecture);
|
||
}
|
||
|
||
public enum TargetArchitecture { X86, X64 }
|
||
```
|
||
|
||
### 7. Object File Writer (目标文件写入器)
|
||
|
||
**职责**：
|
||
- 生成 PE 格式文件（Windows）
|
||
- 生成 ELF 格式文件（Linux）
|
||
- 处理重定位信息
|
||
- 设置入口点
|
||
|
||
**接口**：
|
||
```csharp
|
||
public interface IObjectFileWriter
|
||
{
|
||
byte[] WriteExecutable(byte[] machineCode, TargetPlatform platform);
|
||
}
|
||
|
||
public enum TargetPlatform { WindowsX86, WindowsX64, LinuxX86, LinuxX64 }
|
||
```
|
||
|
||
### 8. Compiler Driver (编译器驱动)
|
||
|
||
**职责**：
|
||
- 协调各个编译阶段
|
||
- 处理命令行参数
|
||
- 错误汇总与报告
|
||
- 管理编译流程
|
||
|
||
**接口**：
|
||
```csharp
|
||
public class CompilerDriver
|
||
{
|
||
public int Run(string[] args);
|
||
public CompilationResult Compile(CompilationOptions options);
|
||
}
|
||
```
|
||
|
||
## Data Models
|
||
|
||
### Token 模型
|
||
|
||
```csharp
|
||
public readonly struct SourceLocation
|
||
{
|
||
public string FileName { get; }
|
||
public int Line { get; }
|
||
public int Column { get; }
|
||
}
|
||
|
||
public enum TokenType
|
||
{
|
||
// 关键字
|
||
Int, Char, Float, Double, Long, Short, Void,
|
||
If, Else, While, For, Do, Switch, Case, Default,
|
||
Break, Continue, Return, Struct, Union, Typedef,
|
||
// 字面量
|
||
IntLiteral, FloatLiteral, CharLiteral, StringLiteral,
|
||
// 标识符
|
||
Identifier,
|
||
// 运算符
|
||
Plus, Minus, Star, Slash, Percent,
|
||
Equal, NotEqual, Less, Greater, LessEqual, GreaterEqual,
|
||
Assign, PlusAssign, MinusAssign, StarAssign, SlashAssign,
|
||
And, Or, Not, BitAnd, BitOr, BitXor,
|
||
LeftShift, RightShift,
|
||
// 分隔符
|
||
LeftParen, RightParen, LeftBrace, RightBrace,
|
||
LeftBracket, RightBracket,
|
||
Semicolon, Comma, Dot, Arrow, Colon,
|
||
// 预处理器
|
||
HashInclude, HashDefine, HashIf, HashIfdef, HashIfndef, HashElse, HashEndif,
|
||
// 特殊
|
||
EOF, Error
|
||
}
|
||
```
|
||
|
||
### Type System 模型
|
||
|
||
```csharp
|
||
public abstract record CType(string Name);
|
||
public record PrimitiveType(TypeKind Kind) : CType(Kind.ToString())
|
||
{
|
||
public enum TypeKind { Void, Char, Short, Int, Long, Float, Double }
|
||
}
|
||
public record PointerType(CType BaseType) : CType($"{BaseType}*");
|
||
public record ArrayType(CType ElementType, int Size) : CType($"{ElementType}[{Size}]");
|
||
public record StructType(string Name, List<FieldDeclaration> Fields) : CType(Name);
|
||
public record FunctionType(CType ReturnType, List<CType> ParameterTypes) : CType("function");
|
||
```
|
||
|
||
### IR 指令模型
|
||
|
||
```csharp
|
||
public abstract record IrInstruction;
|
||
public record IrBinaryOp(IrTemp Dest, IrBinaryOpType Op, IrValue Left, IrValue Right) : IrInstruction;
|
||
public record IrUnaryOp(IrTemp Dest, IrUnaryOpType Op, IrValue Source) : IrInstruction;
|
||
public record IrLoad(IrTemp Dest, IrValue Address) : IrInstruction;
|
||
public record IrStore(IrValue Address, IrValue Value) : IrInstruction;
|
||
public record IrCall(IrTemp? Dest, string FunctionName, List<IrValue> Arguments) : IrInstruction;
|
||
public record IrJump(string TargetLabel) : IrInstruction;
|
||
public record IrBranch(IrValue Condition, string TrueLabel, string FalseLabel) : IrInstruction;
|
||
public record IrReturn(IrValue? Value) : IrInstruction;
|
||
public record IrLabel(string LabelName) : IrInstruction;
|
||
|
||
public enum IrBinaryOpType { Add, Sub, Mul, Div, Mod, And, Or, Xor, Shl, Shr, Eq, Ne, Lt, Gt, Le, Ge }
|
||
public enum IrUnaryOpType { Neg, Not, BitNot, Deref }
|
||
|
||
public abstract record IrValue;
|
||
public record IrTemp(string Name, CType Type) : IrValue;
|
||
public record IrConstant(long Value, CType Type) : IrValue;
|
||
public record IrGlobal(string Name, CType Type) : IrValue;
|
||
```
|
||
|
||
## Correctness Properties
|
||
|
||
### 不变量
|
||
|
||
1. **类型安全**: 所有 IR 指令的操作数类型必须匹配
|
||
2. **作用域正确性**: 符号查找必须遵循词法作用域规则
|
||
3. **控制流完整性**: 所有基本块必须有明确的前驱和后继
|
||
4. **寄存器一致性**: 代码生成前后寄存器状态必须一致
|
||
|
||
### 约束条件
|
||
|
||
1. 生成的机器码必须符合 x86/x64 指令集规范
|
||
2. 函数调用必须遵循目标平台的 ABI（Application Binary Interface）
|
||
3. 栈帧布局必须保证栈指针对齐（x64 要求 16 字节对齐）
|
||
4. 可执行文件格式必须符合 PE 或 ELF 规范
|
||
|
||
## Error Handling
|
||
|
||
### 错误分类
|
||
|
||
| 错误类型 | 阶段 | 处理方式 |
|
||
|---------|------|---------|
|
||
| 词法错误 | Lexer | 报告错误位置，跳过错误 token |
|
||
| 语法错误 | Parser | 报告期望的 token，尝试错误恢复 |
|
||
| 类型错误 | Semantic | 报告类型不匹配详情 |
|
||
| 未声明符号 | Semantic | 报告符号名称和位置 |
|
||
| 代码生成错误 | CodeGen | 报告不支持的 IR 指令 |
|
||
|
||
### 错误报告接口
|
||
|
||
```csharp
|
||
public record ErrorInfo(
|
||
ErrorLevel Level, // Warning, Error, Fatal
|
||
string Message,
|
||
SourceLocation Location,
|
||
string? Suggestion = null
|
||
);
|
||
|
||
public interface IErrorReporter
|
||
{
|
||
void Report(ErrorInfo error);
|
||
bool HasErrors { get; }
|
||
IEnumerable<ErrorInfo> GetErrors();
|
||
}
|
||
```
|
||
|
||
## Test Strategy
|
||
|
||
### 单元测试
|
||
|
||
1. **Lexer 测试**：验证各种 token 的正确识别
|
||
2. **Parser 测试**：验证各种 C 语法的 AST 构建
|
||
3. **Semantic 测试**：验证类型检查和符号表
|
||
4. **IR 测试**：验证 AST 到 IR 的转换
|
||
5. **CodeGen 测试**：验证 IR 到机器码的转换
|
||
|
||
### 集成测试
|
||
|
||
1. **端到端测试**：编译简单 C 程序并验证输出
|
||
2. **回归测试**：使用 TCC 测试套件进行对比测试
|
||
3. **性能测试**：测量编译速度和生成代码质量
|
||
|
||
### 测试用例示例
|
||
|
||
```c
|
||
// test_hello.c
|
||
#include <stdio.h>
|
||
|
||
int main() {
|
||
printf("Hello, World!\n");
|
||
return 0;
|
||
}
|
||
|
||
// test_arithmetic.c
|
||
int add(int a, int b) {
|
||
return a + b;
|
||
}
|
||
|
||
int main() {
|
||
int result = add(3, 4);
|
||
return result - 7; // should return 0
|
||
}
|
||
|
||
// test_control_flow.c
|
||
int factorial(int n) {
|
||
if (n <= 1) return 1;
|
||
return n * factorial(n - 1);
|
||
}
|
||
```
|
||
|
||
## References
|
||
|
||
[^1]: (TCC Source) - Tiny C Compiler 源码 https://repo.or.cz/tinycc.git
|
||
[^2]: (PE Format) - Microsoft PE 和 COFF 规范 https://docs.microsoft.com/en-us/windows/win32/debug/pe-format
|
||
[^3]: (ELF Format) - ELF 规范 https://refspecs.linuxfoundation.org/elf/elf.pdf
|
||
[^4]: (x64 ABI) - System V AMD64 ABI https://github.com/hjl-tools/x86-psABI/wiki/x86-64-psABI-1.0.pdf
|
||
[^5]: (x86 Calling Conventions) - x86 调用约定 https://en.wikipedia.org/wiki/X86_calling_conventions
|