# 编译原理大作业

**Repository Path**: zhizhemodi/compile

## Basic Information

- **Project Name**: 编译原理大作业
- **Description**: microC ZUCC编译原理大作业
- **Primary Language**: Unknown
- **License**: MIT
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2022-04-13
- **Last Updated**: 2024-06-06

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

<!-- vscode-markdown-toc -->
* 1. [文件说明](#)
	* 1.1. [interpreter  解释器](#interpreter)
	* 1.2. [compiler  编译器](#compiler)
	* 1.3. [continuation compiler  优化编译器](#continuationcompiler)
* 2. [构建与执行](#-1)
	* 2.1. [A 解释器](#A)
		* 2.1.1. [A.1  解释器 interpc.exe 构建](#A.1interpc.exe)
		* 2.1.2. [A.2 dotnet命令行fsi中运行解释器](#A.2dotnetfsi)
	* 2.2. [B 编译器](#B)
		* 2.2.1. [B.1 microc编译器构建步骤](#B.1microc)
		* 2.2.2. [B.2 dotnet fsi 中运行编译器](#B.2dotnetfsi)
		* 2.2.3. [B.3 编译并运行 example 目录下多个文件](#B.3example)
	* 2.3. [C 优化编译器](#C)
		* 2.3.1. [C.1  优化编译器 microcc.exe 构建步骤](#C.1microcc.exe)
		* 2.3.2. [C.2 dotnet fsi 中运行 backwards编译器](#C.2dotnetfsibackwards)
	* 2.4. [D 虚拟机构建与运行](#D)
		* 2.4.1. [D.1 c#](#D.1c)
		* 2.4.2. [D.2 C](#D.2C)
		* 2.4.3. [D.3 Java](#D.3Java)
		* 2.4.4. [E 编译到x86_64](#Ex86_64)
		* 2.4.5. [预备软件](#-1)
		* 2.4.6. [步骤](#-1)
		* 2.4.7. [调用约定](#-1)
		* 2.4.8. [数据在栈上的保存方式](#-1)
		* 2.4.9. [x86 bugs](#x86bugs)
		* 2.4.10. [tasks.json](#tasks.json)

<!-- vscode-markdown-toc-config
	numbering=true
	autoSave=true
	/vscode-markdown-toc-config -->
<!-- /vscode-markdown-toc -->##  1. <a name=''></a>文件说明

###  1.1. <a name='interpreter'></a>interpreter  解释器

```sh
Absyn.fs micro-C abstract syntax                              抽象语法
grammar.txt informal micro-C grammar and parser specification 文法定义
CLex.fsl micro-C lexer specification                          fslex词法定义
CPar.fsy micro-C parser specification                         fsyacc语法定义
Parse.fs micro-C parser                                       语法解析器
Interp.fs micro-C interpreter                                 解释器
example/ex1.c-ex25.c micro-C example programs                 例子程序
interpc.fsproj                                                项目文件

```

###  1.2. <a name='compiler'></a>compiler  编译器

```sh
StackMachine.fs definition of micro-C stack machine instructions  VM 指令定义
Machine.java micro-C stack machine in Java                   VM 实现 java
machine.c micro-C stack machine in C                         VM 实现 c 
machine.cs micro-C stack machine in CSharp                   VM 实现 c#
machine.csproj  machine project file                         VM 项目文件

Comp.fs compile micro-C to stack machine code             编译器 输出 stack vm 指令序列
Backend.fs x86_64 backend                                 编译器后端 翻译 stack vm 指令序列到 x86_64
driver.c     runtime support                                 运行时支持程序
prog0 example stack machine program: print numbers           字节码 案例，输出数字
prog1 example stack machine program: loop 20m times          字节码 案例，循环2千万次
microc.fsproj                                                编译器项目文件
```

###  1.3. <a name='continuationcompiler'></a>continuation compiler  优化编译器

```sh
Contcomp.fs compile micro-C backwards                   优化编译器
microcc.fsproj                                          优化编译器项目文件
```

##  2. <a name='-1'></a>构建与执行

###  2.1. <a name='A'></a>A 解释器

####  2.1.1. <a name='A.1interpc.exe'></a>A.1  解释器 interpc.exe 构建

```sh
# 编译解释器 interpc.exe 命令行程序 
dotnet restore  interpc.fsproj   # 可选
dotnet clean  interpc.fsproj     # 可选
dotnet build -v n interpc.fsproj # 构建./bin/Debug/net6.0/interpc.exe ，-v n查看详细生成过程

# 执行解释器
./bin/Debug/net6.0/interpc.exe example/ex1.c 8
dotnet run --project interpc.fsproj example/ex1.c 8
dotnet run --project interpc.fsproj -g example/ex1.c 8  # 显示token AST 等调试信息

# one-liner 
# 自行修改 interpc.fsproj  解释example目录下的源文件
# 
# <MyItem Include="example\function1.c" Args ="8"/> 

dotnet build -t:ccrun interpc.fsproj
```

####  2.1.2. <a name='A.2dotnetfsi'></a>A.2 dotnet命令行fsi中运行解释器

```sh
# 生成扫描器
dotnet "C:\Users\gm\.nuget\packages\fslexyacc\10.2.0\build\/fslex/netcoreapp3.1\fslex.dll"  -o "CLex.fs" --module CLex --unicode CLex.fsl

# 生成分析器
dotnet "C:\Users\gm\.nuget\packages\fslexyacc\10.2.0\build\/fsyacc/netcoreapp3.1\fsyacc.dll"  -o "CPar.fs" --module CPar CPar.fsy

# 命令行运行程序
dotnet fsi 

#r "nuget: FsLexYacc";;  //添加包引用
#load "Absyn.fs" "Debug.fs" "CPar.fs" "CLex.fs" "Parse.fs" "Interp.fs" "ParseAndRun.fs" ;; 

open ParseAndRun;;    //导入模块 ParseAndRun
fromFile "example\ex1.c";;    //显示 ex1.c的语法树
run (fromFile "example\ex1.c") [17];; //解释执行 ex1.c
run (fromFile "example\ex11.c") [8];; //解释执行 ex11.c

Debug.debug <-  true  //打开调试

run (fromFile "example\ex1.c") [8];; //解释执行 ex1.c
run (fromFile "example\ex11.c") [8];; //解释执行 ex11.
#q;;

```

解释器的主入口 是 interp.fs 中的 run 函数，具体看代码的注释

###  2.2. <a name='B'></a>B 编译器

编译器生成 `example` 目录下的栈式虚拟机 `*.out` 文件，
`*.out` 文件 用 `步骤 D` 中的虚拟机执行。

####  2.2.1. <a name='B.1microc'></a>B.1 microc编译器构建步骤

```sh
# 构建 microc.exe 编译器程序 
dotnet restore  microc.fsproj # 可选
dotnet clean  microc.fsproj   # 可选
dotnet build  microc.fsproj   # 构建 ./bin/Debug/net6.0/microc.exe

dotnet run --project microc.fsproj example/ex1.c    # 执行编译器，编译 ex1.c，并输出  ex1.out 文件
dotnet run --project microc.fsproj -g example/ex1.c   # -g 查看调试信息

./bin/Debug/net6.0/microc.exe -g example/ex1.c  # 直接执行构建的.exe文件，同上效果


```

####  2.2.2. <a name='B.2dotnetfsi'></a>B.2 dotnet fsi 中运行编译器

```sh
# 启动fsi
dotnet fsi

#r "nuget: FsLexYacc";;

#load "Absyn.fs"  "CPar.fs" "CLex.fs" "Debug.fs" "Parse.fs" "StackMachine.fs" "Backend.fs" "Comp.fs" "ParseAndComp.fs";;   

# 运行编译器
open ParseAndComp;;
compileToFile (fromFile "example\ex1.c") "ex1";; 

Debug.debug <-  true;;   # 打开调试
compileToFile (fromFile "example\ex4.c") "ex4";; # 观察变量在环境上的分配
#q;;


# fsi 中运行
#time "on";;  // 打开时间跟踪

# 参考A. 中的命令 比较下解释执行解释执行 与 编译执行 ex11.c 的速度
```

####  2.2.3. <a name='B.3example'></a>B.3 编译并运行 example 目录下多个文件

- 用到了 build  -t 任务 选项

- 运行编译器生成的 *.out  文件 需要先完成 D.2 ，在当前目录生成虚拟机`machine.exe`

```sh
dotnet build -t:cclean microc.fsproj    # 清除编译器生成的文件  example/*.ins *.out
dotnet build -t:ccrun microc.fsproj     # 编译并运行 example 目录下多个文件 

```


###  2.3. <a name='C'></a>C 优化编译器

####  2.3.1. <a name='C.1microcc.exe'></a>C.1  优化编译器 microcc.exe 构建步骤

```sh

dotnet restore  microcc.fsproj
dotnet clean  microcc.fsproj
dotnet build  microcc.fsproj           # 构建编译器

dotnet run --project microcc.fsproj ex11.c    # 执行编译器
./bin/Debug/net6.0/microcc.exe ex11.c  # 直接执行

```

####  2.3.2. <a name='C.2dotnetfsibackwards'></a>C.2 dotnet fsi 中运行 backwards编译器  

```sh
dotnet fsi 

#r "nuget: FsLexYacc";;

#load "Absyn.fs"  "CPar.fs" "CLex.fs" "Debug.fs" "Parse.fs" "StackMachine.fs" "Backend.fs" "Contcomp.fs" "ParseAndContcomp.fs";;  

open ParseAndContcomp;;
contCompileToFile (fromFile "example\ex11.c") "ex11.out";;
#q;;
```

###  2.4. <a name='D'></a>D 虚拟机构建与运行
虚拟机有 `c#` `c` `java` 三个版本
- 运行下面的命令 查看 fac 0 , fac 3 的栈帧
- 理解栈式虚拟机执行流程

执行前，先在B中 编译出 *.out 虚拟机指令文件

####  2.4.1. <a name='D.1c'></a>D.1 c#

```sh
dotnet clean machine.csproj
dotnet build machine.csproj   #构建虚拟机 machine.exe 

./bin/Debug/net6.0/machine.exe ./example/ex9.out 3  # 运行虚拟机，执行 ex9.out 
./bin/Debug/net6.0/machine.exe -t ./example/ex9.out 0  # 运行虚拟机，执行 ex9.out ，-t 查看跟踪信息
./bin/Debug/net6.0/machine.exe -t ./example/ex9.out 3  // 运行虚拟机，执行 ex9.out ，-t 查看跟踪信息
```

####  2.4.2. <a name='D.2C'></a>D.2 C

```sh
# 编译 c 虚拟机
gcc -o machine.exe machine.c

# 虚拟机执行指令
machine.exe ./example/ex9.out 3

# 调试执行指令
machine.exe -trace ./example/ex9.out 0  # -trace  并查看跟踪信息
machine.exe -trace ./example/ex9.out 3

```

####  2.4.3. <a name='D.3Java'></a>D.3 Java

```sh
javac Machine.java
java Machine ./example/ex9.out 3

javac Machinetrace.java
java Machinetrace ./example/ex9.out 0
java Machinetrace ./example/ex9.out 3
```

####  2.4.4. <a name='Ex86_64'></a>E 编译到x86_64

####  2.4.5. <a name='-1'></a>预备软件
nasm, gcc

```sh
#Linux
$sudo apt-get install build-essential nasm gcc

# Windows

# nasm 汇编器
https://www.nasm.us/pub/nasm/releasebuilds/2.15.05/win64/

# gcc 编译器
https://jmeubank.github.io/tdm-gcc/download/

w10 在 9.2.0 版本测试通过

```

####  2.4.6. <a name='-1'></a>步骤

栈式虚拟机指令编译到x86_64，简单示例

分步构建

```sh

# 生成 ex1.asm 汇编码 nasm 格式
dotnet run --project microc.fsproj example/ex1.c

# 汇编生成目标文件
nasm -f win64 example/ex1.asm -o example/ex1.o   # win
# nasm -f elf64 ex1.asm -o ex1.o   # linux  

# 编译运行时文件
gcc -c driver.c

# 链接运行时，生成可执行程序
gcc -g -o example/ex1.exe driver.o example/ex1.o

# 执行
example/ex1.exe 8 

```

单步构建

```sh
# 使用 build target 编译 ex1.c
# 可修改 microc.fsproj 编译其他案例文件

dotnet build -t:ccrunx86 microc.fsproj

```

####  2.4.7. <a name='-1'></a>调用约定

- caller
  - 调用函数前，在栈上放置函数参数，个数为m
  - 将rbp入栈，调用函数
- callee
  - 保存返回地址r，老的栈帧指针bp
  - 将参数搬移到本函数的栈帧初始位置
  - 将rbp设置到第一个参数的位置
  - rbx 保存函数的返回值

####  2.4.8. <a name='-1'></a>数据在栈上的保存方式

- 如数组 a[2] 的元素按次序排在栈上，末尾保存数组变量a，内容是首元素 e0的地址
- e0, e1, a  

访问数组，先通过`BP`得到`a`的位置，然后通过`a` 得到首地址 e0，最后计算数组下标偏移地址，访问对应数组元素

- 全局变量在栈上依次保存，x86 汇编中，glovar 是全局变量的起始地址

####  2.4.9. <a name='x86bugs'></a>x86 bugs

- *(p + 2) 指针运算不支持

####  2.4.10. <a name='tasks.json'></a>tasks.json

默认任务`build & run`
- Ctrl+Shift+B