# cpc

**Repository Path**: RimGo/cpc

## Basic Information

- **Project Name**: cpc
- **Description**: No description available
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 1
- **Created**: 2023-08-11
- **Last Updated**: 2023-08-11

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

## cpc
- 2021.7.1 突发奇想 “建党 100 周年！写一个名为 CPC 的 C 编译器，为党庆生！”

## 实现说明
1. C代码 tokenize -> symbol table
2. parse & generate -> VM instructions
3. run VM & 执行生成好的 instructions

> 思路来自于著名的 C4，一个 500 行的可自举的 C 编译器.   
> 我这个行数目测要超过 1000 行，anyway，just for fun.

最终，我只用了 700 行！GOODJOB！代码漂亮易读，哈哈。

## 原理解析
最核心的代码其实是两个函数：
- run_vm : 执行指令，依赖 init_vm
- parse  : 将 C 代码解析为指令，核心依赖 parse_fun/parse_stmt/parse_expr  

整个实现原理已制作成[B站视频](https://www.bilibili.com/video/BV1Kf4y1V783/)

#### VM 设计
##### 内存
虚拟机的内存包含三块空间
 - code // 存储指令（以及指令所需要的参数），pc 从 0 开始
 - data // 存储全局变量和常量，从小到大
 - stack // 栈空间，从大到小（由于这三块内存我们是分别存储的，所以stack并非一定要从大到小，只是习惯而已）

##### 寄存器
 - pc // 代码计数器，也就是 code 区域的指针，每步都是执行 pc 所指向的指令
 - sp // stack pointer, 栈指针
 - bp // base pointer，上一个栈的指针
 - ax // 通用寄存器，保存指令要用的数据，返回值也会保存在这里

##### 指令集
指令集一共有 4 大类
 - Save&Load：在寄存器和内存中间传递数据
   - IMM, LEA, PUSH, LC, LI, SC, SI
 - 四则运算、逻辑运算、位运算
   - OR, XOR, AND, EQ, NE, LT, GT, LE, GE, SHL, SHR, ADD, SUB, MUL, DIV, MOD
 - 跳转、函数调用
   - JMP/JZ/JNZ, CALL/NVAR/RET/DARG
   - //TODO: 有空再细讲一下函数调用
 - Native CALL：虚拟机通过调用原生函数支持的一些指令（以方便处理动态内存、IO等问题，简化实现）
   - OPEN, READ, CLOS, PRTF, MALC, FREE, MSET, MCMP, EXIT

#### Parse 设计
Parse 最关键的就是要将 C 代码翻译成 VM 指令写入 code 空间（同时把全局变量和常量写入 data 空间） 
在 VM 运行之前，stack 空间应该是空的，而 code 和 data 应该是写好不需要再修改了的  
Parse 过程需要保存一些关键的临时数据，比如说我 Parse 过一个全局变量 x，后面我再遇到变量 x 的时候，
我需要准确的知道 x 的类型、内存地址，这样我才能正确的处理 x 相关的语句和表达式  
这个保存 Parse 过程临时数据的地方就是：符号表（symbol_table）
- 符号表 & 关键字
  - Token: 符号类型标识，默认是 Id，但是关键字和运算符都有自己的Id
  - Hash: just hash，用于快速判断两个 Id 是否相同
  - Name: just name, 符号的全名
  - Class: 符号的类别：Num(枚举符号), Fun(函数), Sys(Native Call), Glo(全局变量), Loc(局部变量)
  - Type: 符号所代表的变量或者函数的返回类型
  - Value: 符号的值，不同类别的符号值的含义不同，例如：全局变量的值为地址，Loc的值为顺序（地址在stack中，可根据顺序计算）
  - GClass, GType, GValue: 用于进入局部空间后，对同名全局符号的遮蔽时临时保存全局属性
- Parse 全局定义  
全局定义一共有两种：变量、函数，由于枚举变量以 enum 开头有些特殊，我们也把它单拎出来处理
  - parse 枚举：这个很容易 enum [Id] {Id [= Num], Id ....};
  - parse 变量：这个更容易 type[\*] Id [,Id] ... ;
  - parse 函数：这个麻烦些 type[\*] Id (type Id [, type Id] ... ) { 这里面是函数内部，单独讲 } 
- Parse 函数
  - 处理传入参数
  - 处理局部变量（遮蔽同名全局变量）
  - 一条一条处理 parse 语句
  - 恢复同名全局变量
- Parse 语句
  - If 语句
  > JZ false point  
  > true point: true stmts ...  
  > JMP end point  
  > false point: false stmts ...  
  > end point  
  - While 语句
  > loop point  
  > while stmt  
  > JZ end point  
  > stmts...  
  > JMP loop point  
  - Return 语句
  - 普通语句：直接当做表达式处理
- Parse 表达式  
表达式 Parse 我在经典的「递归下降」(LL)和 C4 使用的「优先级爬山」(LALR)中犹豫了很久，最终使用简单的爬山法  
优先级爬山处理的方式也很优雅：
  - 遇到第一个 operator 直接压栈
  - 后续的 operator 与栈顶比较
    - 优先级更高的话直接处理
    - 优先级低的话则先处理栈中的 operator
  - 直到所有 operator 都处理完