编译原理实践

make it

May 19, 2026 - 1 minute read -
note

前置

Linux命令

Git使用方法

GDB/LLDB使用方法

Makefile使用方法

编译器元语言词汇表

符号分为两类:token和Grammer symbol(非终结符)

Token表(lexer输出)

  1. NUMBER:数字字面量(1,2,3…)
  2. IDENT:标识符(变量名/函数名)
  3. PLUS:+
  4. MINUS:-
  5. STAR:*
  6. SLASH:/
  7. ASSIGN:=
  8. EQ:==
  9. NE:!=
  10. LT/GT:< >
  11. LE/GE:<= >=

环境配置

Docker

docker run maxxing/compiler-dev ls -l /

拉取docker镜像

docker run maxxing/compiler-dev ls -l /

这个命令是按照compiler-dev这个镜像文件创建一个临时容器,运行ls -l后关闭容器

如果需要在这个临时容器在运行命令后自己删除可以使用

docker run --rm maxxing/compiler-dev ls -l /

有时候我们需要在这个镜像中做多个操作可以使用

docker run -it maxxing/compiler-dev ls -l /

这样docker会为容器创建一个终端并开启容器的stdin

输入exit可以退出这个容器

挂载宿主机的存储器命令:docker run -it –rm -v /home/max/compiler:/root/compiler maxxing/compiler-dev bash

RISC-V

一个完全开源的ISA,指令系统体系结构

由基础指令系统 (base instruction set) 和指令系统扩展 (extension) 构成

常用的基础指令系统有两种:

  • RV32I: 32 位整数指令系统.
  • RV64I: 64 位整数指令系统. 兼容 RV32I.

常用的标准指令系统扩展包括:

  • M 扩展: 包括乘法和除法相关的指令.
  • A 扩展: 包括原子内存操作相关的指令.
  • F 扩展: 包括单精度浮点操作相关的指令.
  • D 扩展: 包括双精度浮点操作相关的指令.
  • C 扩展: 包括常用指令的 16 位宽度的压缩版本.

mian函数

编译器的结构

编译器把源代码变成二进制的过程分为:

  • 编译:将源代码变成汇编
  • 汇编:将汇编代码变成目标文件
  • 链接:将目标文件链接为可执行文件

在课程中实现的编译器只需要将SysY源代码编译到RISV-V汇编即可

所以编译器由:

  • 前端:通过词法分析和语法分析将源代码解析为抽象语法树(AST),通过语义分析扫描抽象语法树检查是否有误
  • 中端:将抽象语法树转换为中间表示IR,并在此基础上完成机器无关优化
  • 后端:将中间表示转换为目标平台的汇编代码,并在此基础山完成一些机器优化

词法/语法分析

对于这样一段保存在文件里的源程序:

int main() {
  // 我是注释诶嘿嘿
  return 0;
}

逐字符进行字节流操作是难以分析的,因为有意义的是token

词法分析的作用就是将字节流变成token流,词法分析器(lexer)会讲字节流读取并输出一个个token传递给语法分析器(parser),忽略无意义的空格,换行和注释

词法分析器输出的token会带有token种类信息,例如:

  1. 种类: 关键字, 内容: int.
  2. 种类: 标识符, 内容: main.
  3. 种类: 其他字符, 内容: (.
  4. 种类: 其他字符, 内容: ).

语法分析的目的就是将token流转换为AST,Parser会根据语法规则和语法分析算法例如LL分析法或LR分析法,对token流做一系列分析并输出AST

语义分析

在语义分析分析阶段编译器通常会:

  • 建立符号表:追踪程序里变量的声明和使用,确定程序在某处用了哪一个变量,同时发现重复定义,未定义变量等错误
  • 进行类型检查:检查是否对整数做数组访问这类操作,同时标注程序中表达式的类型
  • 进行必要的编译期计算:SysY支持使用变量作为数组长度,所以在生成IR之前需要对此进行计算

IR生成

IR的存在使得前后端分离得以实现,现在将M种高级语言编译为N种平台的编译语言只需要M+N个模块

LLVM IR就是一种被广泛使用的IR,支持将Swift,Rust,Julia等翻译为LLVM IR并翻译为RISC-V,ARM,x86等平台上

目标代码生成

  • 决定IR中的指令应该被翻译为哪些目标指令系统的指令
  • 寄存器分配:决定IR中的值被放在指令系统的哪个寄存器中,某些值会被放在内存中
  • 指令调度:决定IR生成的指令序列最终顺序如何

词法/语法分析初见

有很多工具可以根据正则表达式和EBNF生成词法/语法分析器

看懂EBNF

EBNF即扩展巴克斯范式,用于描述编程语言的语法

EBNF以A ::= B的规则组成,这告诉我们当我们遇到A时可以用B将其代替,A被称为非终结符

写蛇形命名法的符号, 或者被双引号引起的字符串, 被称为终结符

目标是, 利用 EBNF 中的规则, 把开始符号(CompUnit)推导成一系列终结符

​

Loading...