编译原理知识点索引

声明

本文档只包含一些关键的知识点

词法分析-正则表达式和自动机理论

对应Lecture-3

定义

字母表

$$字母表\Sigma是一个有限的符号集合$$

串

$$字母表\Sigma上的串s是由\Sigma中符号构成的一个有穷序列$$

$空串:\epsilon$

语言

$语言是给定字母表\Sigma上一个任意的可数的串的集合$

正则表达式

$给定字母表\Sigma, \Sigma上的正则表达式由且仅由以下规则定义:$

(1) $\epsilon是正则表达式$

(2) $\forall a\in\Sigma, a是正则表达式$

(3) $如果r是正则表达式, 则(r)是正则表达式$

(4) $如果r, s都是正则表达式, 则 r|s, rs, r^*也是正则表达式$

NFA(Nondeterministic Finite Automaton)

$非确定性有穷自动机\mathcal{A}是一个五元组\mathcal{A}=(\Sigma,S,s_0,\delta,F)$

见课件-3-26

DFA(Deterministic Finite Automaton)

见课件-3-34

RE, NFA, DFA等价转化

RE->NFA - Thompson构造法

见课件-3-40:45

NFA->DFA - 子集构造法

原理见课件-3-54

为什么叫子集构造法:

• 构造出的DFA的每一个状态$s_D\in S_D$, 对应原来NFA的状态的一个子集$s_D\subseteq 2^{S_N}$

总结:

• 对NFA的每个状态求其对应**$\epsilon$闭包**, 即只通过$\epsilon$转移可达的状态集合. 这个集合中的状态可以被视作DFA中的一个状态
• 新的DFA中的状态的转移函数是其对应NFA状态集合中每个状态的转移函数构成的. 这一条课件讲的更清楚

DFA->DFA - DFA最小化

IR-LLVM

LLVM

Low Level Virtual Machine

但是现在已经不止上面的含义了

Three Address Code (TAC)

三地址指令

一条指令所含操作数和地址的数量不超过3

Static Single Assignment (SSA)

静态单赋值

静态:

单赋值: 每个寄存器只在赋值号左边出现一次

Control Flow Graph (CFG)

控制流图

节点: 基本块(跳转与分支只能在基本块退出点执行, 跳转到另一个基本块的进入点)

边: 跳转关系

$\phi$ 指令(phi)

根据控制流的来源决定返回值

%3 = phi i32 [1, %1], [2, %2]
// 如果从%1控制流来, 就给%3赋值1, 否则赋值2