编译原理实践

make it

May 19, 2026 - 3 minute read -
note

前置

Linux命令

Git使用方法

GDB/LLDB使用方法

Makefile使用方法

正则表达式regex

正则表达式是描述字符串模式的语言

  • 普通字符:abc 匹配abc
  • 任意单字符: .
  • 0个或多个: * a* 匹配: ,a,aa,aaa,…….
  • 1个或多个:+ a+ 匹配: a,aa,aaa,…….
  • 0个或1个:?
  • 任意选一个:[] [abc] 匹配:a/b/c任选一个 [0-9]表示任意数字 [a-z]表示任意字母 [A-Z]表示任意大写字母

identifier:[a-zA-Z_][a-zA-Z0-9_]*

编译器元语言词汇表

符号分为两类: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:<= >=
  12. LPAREN / RPAREN:()
  13. LBRACE/RBRACE:{}
  14. LBRACKET / RBRACKET:[]
  15. SEMI:;
  16. COMMA:,
  17. EOF:文件结束
  18. 关键字token:IF,INT,RETURN,WHILE

Grammar Symbol

  1. Expr:表达式(1+2;a*b)
  2. Stmt:Statement(a=b if a==0 else 2)
  3. Decl:Declaration(声明)(int a)
  4. Func:函数
  5. Type:类型(int,float)
  6. Program:整个程序
  7. Term:
  8. Factor

环境配置

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)推导成一系列终结符

C/C++实现

如何用Flex和Bison自动生成compiler前端

Flex是lexer,用于将源代码解析为terminal

Flex文件sysy.l实际上在描述字符模式与token的对应关系

例如:

"+"       return PLUS;
[0-9]+    return NUMBER;

描述的是看到+返回PLUS,看到一个或多个数字返回NUMBER

Bison文件sysy.y在定义文法

Expr:
	Expr '+' Expr
	|NUMBER
;

Expr 可以是：

Expr + Expr 或者 NUMBER

整个流程就是Flex读取sysy.l,生成lexer.c,里面有yylex()用于读取字符返回token;

Bison读取sysy.y,生成parser.c,里面有yyparser(),用于读取token构建AST

Parser需要Lexer提供token,而Lexer又需要Parser提供token编号

.l和.y的共同结构
// 选项

%{

// C/C++ 全局代码

%}

// Flex/Bison 自己的定义

%%

// 规则

%%

// 用户自定义 C/C++ 代码

1.选项区

例如 Flex 里会写：

%option noyywrap
%option nounput
%option noinput

这里是给生成器看的配置

2. %{ ... %}：原样复制到生成出来的 C/C++ 文件里

%{

#include <cstdlib>
#include <string>
#include "sysy.tab.hpp"

using namespace std;

%}

Flex/Bison 会把里面的内容直接复制到生成出来的 .cpp 文件中，所以通常放：

#include
using namespace std
函数声明
全局变量声明

3. 中间定义区：给规则起名字 / 定义 token 类型

在 .l 文件里，这一段通常写正则表达式别名：

WhiteSpace    [ \t\n\r]*
Identifier    [a-zA-Z_][a-zA-Z0-9_]*
Decimal       [1-9][0-9]*

WhiteSpace 代表空白符正则 Identifier 代表标识符正则 Decimal 代表十进制整数正则

在 .y 文件里，这一段通常写：

%token INT RETURN
%token <str_val> IDENT
%token <int_val> INT_CONST
%type <str_val> FuncDef FuncType Block Stmt Number

lexer 会返回哪些 token 这些 token 携带什么类型的值 非终结符会产生什么类型的值

4.第一个 %% 到第二个 %%：规则区

这个区域对 Flex 来说是 lexer 扫描到 token 后做的操作；对 Bison 来说是 parser 遇到某种语法规则后做的操作。

5. 最后的用户代码区

如果你想在规则描述里调用自己定义的辅助函数，就可以把函数声明放前面，把函数定义放最后。

错误处理函数 辅助函数定义 你希望规则区调用的函数

Flex和Bison是怎么生成代码的
sysy.l
   ↓ flex
sysy.lex.cpp

sysy.y
   ↓ bison
sysy.tab.cpp
sysy.tab.hpp

然后：

main.cpp
+
sysy.lex.cpp
+
sysy.tab.cpp

一起编译

Loading...