编译原理 学习笔记

DEAD

课程30平时70考试,线下闭卷,应该是大三下唯一一门考试的课了.

平时

10 课程分
10 大作业(写一个小编译器,网上有一堆实现随便抄一个,但是线下有答辩,会问你你对于编译的理解,某某算法的理解等,不过据说8分起评,答的好就是10分,去实习不来答辩的就是8分)
10 小作业(平时留的几个课堂作业,好像是不让补交的)

大头还是在考试,所以更新一下Fluu做考试的准备.

考试

几个小约定

$ABC$ 这几个是非终结符.
$abc$ 这几个是终结符.
$\alpha \beta$ 这几个是任意符号串(可以混合)

id num 这些有意义的词在编译原理中视作一个token,所以求first集的时候要写一起,不要只写一个 i 或者 n 完事.

语言的种类

机器语言(01,计算机能直接执行)
汇编语言(用符号化的助记符表示机器语言,例如ADD MOV等)
高级语言(将汇编语言进一步抽象,用便于理解的自然语言表达)

机器语言

操作码,地址码.
操作码负责告诉机器这一步要作什么,地址码告诉机器操作数的地址在哪或者操作数本身

  1. 难学、难记忆、难理解、出错率高、难以维护，也不能直观地反映⽤计算机解决问题的基本思路。
  2. 机器语⾔描述算法⼗分繁琐，只供初等的运算、数据结构和控制⽅式：
  3. 机器语⾔程序依赖于具体的机器, 不具备移植性。
  4. 机器语言执行速度快.

汇编语言

用助记符代表操作码,用地址符号或者标号代替地址码,例如 ADD SUB [rax] ,通常是为了特定计算机专门设计的.

  1. 汇编语言比机器语言易学一些,易记忆和理解
  2. 占用内存空间少,运行很快,
  3. 依赖具体的机器,不具备可移植性.

高级语言

对汇编语言进一步抽象的语言,面向程序员,更易学易用,易修改,具备移植性,但是实现起来很麻烦,需要翻译成机器码.

有三种实现方式: 编译,解释和转换.
举例: C++ 是编译型语言, python 是解释性语言, typescript(ts) 是转换型语言.
转换型语言可以理解为为了兼容新特性,同时还想要原有语言的生态,所以就需要转换一下.

语法树

每一个节点要么是叶节点,里面装着数据,要么是操作符,然后有两个子节点,例如

1
2
3
4
5
6
3+4*2的语法树
    '+'
   /   \
  3     '*'
       /   \
      4     2

语法树的构建:目前已知的可以是两个栈一个数字栈一个操作符栈模拟一下,然后还有后续会讲到的递归下降.
语法树的计算:直接dfs然后逐层计算结果即可.

编译过程

源程序->词法分析->语法分析->语义分析->中间代码生成->中间代码优化->目标代码生成->目标程序

中间还有错误处理,表处理等过程.

词法分析

正确识别程序的字符都是什么意思.这里单词的英文是 token.

单词类型划分

标识符:用户自己定义的对象名称,例如 int a 里面的 a.
保留字:语言自身定义的有固定含义的字符,例如 int a 里面的 int.
常量:一些写进代码的固定的常量,比如字符串常量,数字常量等.
特殊符号:具体:

  • 运算符: + - * / <= 等.
  • 界限符:标识程序分界的符号,例如 ; , ' ".
  • 控制符:控制语言格式的,例如 EOF 文件结束.

    单词的描述

    可以用正则或者自动机.

符号串

字母表:用 $\sum$ 代表整个字符集合,用 $\varepsilon$ 代表空字符串,用绝对值代表长度.
符号串的连接就是正常字符串的连接.

方幂:就是把多个字符串拼多少次,对应集合就是集合重复乘多少次.

符号串集合:用符号串组成的集合.
符号串集合的乘法:正常的笛卡尔积.
符号串集合的闭包:有两种闭包.

$A^+$ :所有用A中字符串拼成的字符串都算.
$A^*$ :所有用A中字符串拼成的字符串都算,但是额外算上空集.

正则表达式

用字符串来表达正则集的代数表达式.

所有能用表达式 $r$ 表达的符号串集合,被称为正则集,记作 $L(r)$, $L(r)$ 也被称为由 $r$ 定义的语言.

运算规则:

优先级: 括号> * 运算 > 连接运算 > 或运算
正则表达式的性质: 交换律 结合律 分配律 幂等律 同一律($\varepsilon A=A\varepsilon =A$ 匹配空串等于什么也不做)

正则表达式的局限

  1. 配对结构
    例如 qwq qqwqq (两边出现次数相同)

  2. 嵌套结构
    例如完美匹配的括号 (())

  3. 重复串结构
    例如 ww 形式,其中 w 是一个任意串,且要求两次出现相同,例如 w=a|b 但是正则能匹配 ab

DFA 确定有限自动机

定义: $M=(S,\sum,S_0,f,Z)$ ,看起来参数很多很吓人,实际上是纸老虎.

$S$: 有穷状态集(就是整个图有这么多个节点,每个节点都是 $S_i$ 命名的,这些节点之间只有编号的差异)
$\sum$:有穷字母表(就是这个值域有多大)
$S_0$:初始状态
$f$:状态转换函数, $f:S\times \sum \to S$ 直观理解 $f$ 就是图上的边.
$Z$:终止状态集,走到哪了被接受, $Z$ 可以是空集.

DFA的表示:

  1. 状态转换矩阵
    输入字符为列标,状态为行标
    初始状态右上角表注 + ,终止状态右上角标注 * 或者 - .
状态 \ $\sum$ a b
$S_0^+$ $S_1$ $S_2$
$S_1$ $S_3$ $S_2$
$S_2$ $S_1$ $S_3$
$S_3^*$ $S_3$ $S_3$

映射 $f$ 必须对每一个状态的每一个字符都有定义.

  1. 状态转换图
    直接看图吧.

记DFA能接受的串为 $L(M)$ ,和上文正则表达式一样,感觉DFA就是实现了一下正则.

自动机等价:如果 $L(M_1)=L(M_2)$ 则称两个自动机等价.

DFA的化简与新DFA的作图

  1. 删除无用状态
    直接dfs一下然后看哪个点没有入边就行.

  2. 合并相同状态
    这个不好看.

有一个固定的方法可以处理这个问题,Fluu看的这个视频,因为涉及到新加内容了,笔记这种固定的知识载体有点难描述的.

NFA 非确定有限自动机

同一个节点的同一个输入可以有多个对应状态的自动机,也就是函数 $f$ 并不要求是单值的.

  1. 一个状态输入字符相同的条件下可以转向多个不同后继
  2. 可以有多个开始状态
  3. 允许有 $\varepsilon$ 空边,即在没有任何输入的情况下转换状态.

NFA接受的字符串:通过任意方式只要能走到终止状态的就接受.

NFA的确定化

通过某种方式把NFA转成DFA就叫确定化.

Fluu看的这个视频.
特别注意一下,右上角的 + 和 * 是开始结束标志,所有包含原nfa结束状态的都可以变成结束节点.

正则转自动机 自动机转正则

直接做题就行

语法分析

语言的三个基本要素:语法(如何组合成合法的语句)语义(句子的含义)语用(句子在特定条件下的使用)

文法

文法的定义是一个四元组 $G=(V_N,V_T,S,P)$ 其中
$V_N$ 是非终结符集合
$V_T$ 是终结符集合
$S$ 是开始符号
$P$ 是产生式集合

产生式形式为 $A\to \alpha$ 的文法,其中

  1. $A$ 被称为左部,左部必须是一个非终结符.
  2. $\alpha$ 被称为右部,$\alpha \in (V_T\cup V_N)^*$ 即右部是由终结符和/或⾮终结符组成的任意有限序列,可以为空串
  3. $\to$ 被称为推导出
  4. 开始符号必须至少在某个产生式出现一次
  5. 产生式能够合并,例如 $P\to\alpha_1$ $P\to\alpha_2$ 可以合并成一个 $P\to\alpha_1|\alpha_2$ 被称为候选式, | 读作或.

举一个例子:所有数字

1
2
3
4
5
6
7
8
9
G = (V_N, V_T, P, S)
V_N = {N, D} (N代表数字，D代表数位) （⾮终结符）
V_T = {0, 1, 2, ..., 9} （终结符）
P = {
	N → D
	N → ND
	D → 0 | 1 | ... | 9
}
S = N

非终结符:N表示一个或多个数字组成的整数
D表示单个数字
(为什么这里的S直接等于N:因为S)

终结符:最终生成的字符串只包含这些字符,实际出现在字符串中的符号

产生式规则:
N → D 一个数字串可以是单个数字
N → ND 可以通过在已有字符串后面加一个数字来拓展.(递归主体出现在左边所以是左递归)
D → 0 | 1 | ... | 9 非终结符D能变成哪些具体的数字

产生式规则可以理解为直接替换看看能换成什么.

四种文法

0型文法

具有形式 $\alpha\to\beta$ ,其中 $\beta\in(V_T\cup V_N)^*$ ,并且 $\alpha$ 至少包含一个非终结符,例如

1
2
AB → C
C → a

1型文法

在0型文法的基础上要求 $|\alpha|\le|\beta|$ , $S\to\alpha$ 是个例外,但是 $S$ 不得出现于产生式右部.

1
2
3
4
AB → ACB    （左部长度2，右部长度3）
A → a
B → b
C → c

2型文法

上下文无关文法,是1型文法的特例,要求产生式左部必须都是一个非终结符,例如 $A\to\alpha$

1
2
3
E → E + T | T
T → T * F | F
F → (E) | id

3型文法

正则文法,2型文法的特例,产生式右部至多有两个符号,而且至多有一个非终结符,例如

1
2
A → a
A → aB

推导

$\alpha\implies\beta$ 这是一步推导.

多步推导(线性推导)

至少进行一步是 $\implies ^+$ ,可以不进行推导的是 $\implies ^*$ .

句型

从开始符号出发能得到的符号串被称为句型

句子

所有字符都是终结符的句型被称作句子.

语言

文法G所定义的语言是其开始符所能推导的所有句子的集合.

最左推导

总是替换最左边非终结符的推导过程.

最左句型

最左推导过程中产生的所有符号串（包括非终结符）。

短语

如果有 $S\implies^* \alpha A\beta, A\implies \pi$ 那么称 $\pi$ 是句型 $\alpha\pi\beta$ 的一个简单短语.
某个非终结符经过至少以部推导得到的连续子串

推导树上所有非叶节点的该节点推导出来的所有叶节点.例如

1
2
3
4
5
6
7
S
 /   \
a     A
  / \
 b   A
	 |
	 b

然后第二个b是短语,bb也是短语,abb也是短语.
简单短语就是一步推导出来的短语,所以第二个b是短语.

句柄

一个句型可能有多个简单短语,取最左的简单短语

二义性文法

如果一个文法的某个句型有两种不同的最左推导,则称该文法为二义性文法.(推导树有两种不同结构)

语法树就是推导树,二义性包括但不限于手性语法树(不是).

消除二义性

拿if else举例,假设我们有 if A then if B then C else D 这个D该和哪个if匹配是一个问题,所以造成了二义性.

  1. 添加文法规则
    比如我们强制if的语句末尾必须有一个 fi 做结尾,改成
    if A then if B then C fi else D fi 或者 if A then if B then C else D fi fi

  2. 添加语义规则
    像C++一样,如果没有大括号限制就采用最近if结合的规则.

文法等价变换

拓广产生式

定理：对任一文法G1都可以构造文法G2，使得L(G1)=L(G2)，且G2的开始符唯一且不出现于任何产生式的右部。

人话:可以构造一个公用的开始符节点,然后开始符节点指向所有原先的开始符节点.

消除空产生式

定理：对任一文法G1，可构造文法G2，使得L(G1)=L(G2)，且G2中无空产生式。

人话:首先标记哪些字符串是可空的,然后遍历所有情况,最后找出来不空的串叠加起来.

消除不可达产生式

定理：对任一文法G1都可以构造文法G2，使得L(G1)=L(G2)，且G2中的每个非终极符必出现在它的某个句型中。

人话:直接图论计数,然后删掉用不到的所有产生式即可.

消除特型产生式

首先了解一下特型产生式是什么:

$A\to B$,其中AB都是非终结符.

如何消除:首先对每个非终结符计算能通过特型产生式到达的所有非终结符,加进一个集合里面.
然后对这所有非终结符挨个检查有没有非特型产生式的结果,如果有就加到A的集合里面.
最后并起来即可.

消除公共前缀(左因子)

1
2
3
4
A → abcD
A → abE
A → aF
A → xY

然后开一个新点名为 A' ,然后承担了后续的字符串,然后A直接指向 A' :

1
2
A  → α A' | xY
A' → β1 | β2 | … | βn

然后如果ab有两层嵌套就得提取两次左因子.

消除左递归

  1. 直接左递归
    1
    A → Ab | c | d

对于这种式子能匹配上的正则为 c|db* ,所以我们可以利用 c|d 打头的特性消除左递归,变成:

1
2
A → cA' | dA'
A' → d A' | ε

如果式子的c或者d是空字符串相当于直接能匹配 b* 那直接反转就行了,没必要专门消除左递归.

  1. 间接左递归
1
2
A → Ba | c
B → Ab | d

解决方式:先通过dfs的方式找到左递归,然后直接转换即可.

自顶向下语法分析

从开始符S出发,采用最左推导的方式找完全匹配的句子(dfs剪枝,最左只是指定了顺序不代表一定要每次都取最左侧的)

三大集合(first follow predict)

首先注意一下要被计算的对象都是谁…

$first(\alpha)$ :从 $\alpha$ 能推导出的所有第一个终结符的集合.
算法:如果 $\alpha$ 以终结符开头,直接加入终结符
如果以非终结符(假设为 $A$ )则把 $first(A)$ 加入集合,然后继续推.
假设有 $A\to BCD$ ,这个时候要找空集:如果所有BCD都可以取到空集,证明整个式子可以完全消失,此时才能把空符加进去

$follow(A)$ 在推导过程中,紧跟在非终结符A后面可能出现的终结符集合,
算法:开始符号S要添加 # 进Follow(S).
遍历所有产生式的所有字符,直到最终所有非终结符的Follow集不再变化:
对每个形如 $A\to\alpha B \beta$ 的式子做下面操作:

  • 把 $First(\beta)$ 加进 $Folloe(B)$
  • 如果 $First(\beta)$ 包含 $\varepsilon$ ,或者B在末尾,则把 $Follow(A)$ 加进 $Follow(B)$

$predict(A\to\alpha)$ 又被称作 $select$ 集.
算法:如果 $First(\alpha)$ 不包含 $\varepsilon$ :

反之则为:

也就是非空的alpha first加上A的follow.

三大集合的意义:
First 集：我自己能产生什么开头？
Follow 集：我后面能跟着什么？
Predict 集：我这条产生式在遇到什么输入时可以用？

LL(1)文法

Predict集中对于任意A推导的多个结果都不相交.

  • first集除了空元素互不冲突
  • 如果first集有元素要把这个元素纳入考量

这样能保证查看符号后使用哪个产生式,不用回溯了.

  • 即使没有公共前缀和左递归,也不意味着这就是LL(1)文法
  • 已经被证明有非LL(1)文法不能转换为LL(1)文法.

LL(1):语法顺序将按照从左到右扫描进符号串.
分析器将使用每一个句子的最左推导.
每一步推导的时候只需要查看一个输入符号即可.

LL(1)分析:替换:匹配:成功:失败.

有下面式子

1
2
3
4
5
6
Z -> aBe {a}
Z -> Bd  {b,c}
B -> bB  {b}
B -> cK  {c}
D -> d   {d}
K -> 空  {d,e}
字符串 匹配字符串 操作
Z# ace# 替换
aBe# ace# 匹配
Be# ce# 替换
cKe# ce# 匹配
Ke# e# 替换
e# e# 匹配
# # 成功

LL(1)分析表:首先计算predict集,然后根据predict集选择产生式,如果没有合适的就直接爆error

LL(1)分析器的工作状态被称作格局(configuration).通常表示为 (栈内容,剩余输入流) ,就是俩字符串直接比对.

递归下降(自顶向下)

说白了就是暴力,每一条规则直接对应一个代码,也要求LL(1)文法.

1
2
Z → a B a
B → b B | c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
procedure Z();
begin
    if token = a then
        begin
            Match(a);   // 匹配第一个 a
            B;           // 递归调用 B
            Match(a);   // 匹配第二个 a
        end
    else
        error();
end;

procedure B();
begin
    if token = b then       // 产生式 B → b B
        begin
            Match(b);
            B;              // 递归调用自己
        end
    else if token = c then  // 产生式 B → c
        Match(c)
    else
        error();            // 既不是 b 也不是 c，出错
end;
  1. ReadToken() 读取输入流的下一个词法单元,存入全局 token 中.
  2. Match(a) 用于检验期望是否匹配
1
2
3
4
5
6
7
8
9
void main(){
	ReadToken(); //读取第一个符号
	S();         //调用S的程序
	if(token=='#){
		success();
	}else{
		fail();
	}
}

自底向上语法

移入规约:时刻判断当前的栈中式子满不满足产生式的右部,如果有就规约,如果没有就移入,一点点还原回去.
如何进行还原:使用 LR(1)

今年的LR全家桶不考,所以笔者没有这里的内容.

语义分析

静态语义

编译阶段就能检查的规则,例如标识符未声明,类型不匹配,参数数量或类型不符等.

动态语义

除0错误,移除错误,下标越界,空指针引用

符号表

一个标识变量各种信息的表.

看个例题:

1
2
3
4
5
const m=333;
const n-444;
Type at-array[1.10]ofreal;//类型声明，长度为10的实型数组
rt-recordijinteger end;//类型声明，含有整形iij的结构体。
Varab:at: X.X:real;//变量声明。

做出符号表:

变量名 类型 种类 访问 层数 偏移 值
m constKind intPtr dir L ↑(333)
n constKind intPtr dir L ↑(444)
a varKind at indir L Offset Null
b varKind at indir L Offset+20 Null
x varKind realPtr dir L Offset+42 Null
y varkind realPtr dir L Offset+44 Null
name kind type
at typeKind ptr

ptr-> 10 arrayType 1 10 realPtr

中间代码生成

抽象语法树

1
2
3
4
5
6
7
 :=
 / \
c   +
   / \
  *   *
 / \ / \
 a b a b

DAG有向无环图

1
2
3
4
5
6
7
8
 :=
 / \
c   +
   /\
   \/
    *
   / \
   a b

上面的图共享了 a*b 表达式.

四元式

(命令名称,操作符1,操作符2,运算结果的位置)

(READI, -, -, id) 整数输入
(READF, -, -, id) 实数输入
(WRITE, -, -, id) 输出 id

(FLOAT, id1, -, id2) 类型转换

(ASSIG, id1, -, id2) 赋值

(AADD, id1, id2, id3) 地址加: id3:=addr(id1)+id2

(LABEL, -, -, label) 定义标号 label

(JMP, -, -, label) 转向标号 label
(JMP0, id, -, label) 若 id=0则跳转
(JMP1, id, -, label) 若 id=1则跳转

(ENTRY, Label, Size, Level) 子程序入口
(CALL, f, -, Result) 过程或函数调用

(VarACT, Y, Offset2, 1) 变量参数传递,Y是等待被复制的变量地址,offset2是两个变量的偏移,1是变量大小.

(CALL, f, true, t2) 调用f函数,其中f是有返回值的函数,返回值在t2

GenCode(w,left,right,result) 产生一条四元式中间代码,万能翻译器(没用,因为这涉及写编译器)

(WHILE, -, -, label) 循环开始的标签
(DO, t0, L_exit_while, -) 条件为假时跳出循环
(ENDWHILE, label,-,-) 重新开始循环

(>, a, b, t0) 在做 if 前首先要做表达式的真假计算
(THEN, t0, L_else, -) 如果假就跳转else,如果真就继续
(ELSE, L_endif,-,-) 跳过else部分(if部分写完了)
(ENDIF,-,-,-) 打一个标签作为结束的地址能够跳转

(LABEL,-,-,L_else) 贴else的标签

(ENTRY,Label,Size,Level) 子程序入口
(ENDPROC,-,-,-) 结束一个过程(没有返回值)
(ENDFUNC,-,-,-) 结束一个函数(有返回值)
(RET,val,-,-) 返回值,没有就不返回

语法制导

在进⾏语法分析的同时完成相应的语义动作。这些语义动作由⼀些程序组成，⽤于完成与⽤
⼾需求相关的任务。

引入语义动作符(相当于打印调试,比较原始),比如 #Init# .
动作符一般插到运算末尾,该运算结束后立刻打印调试.

不止可以用作打印调试,还可以用作统计字符串长度之类的.
对每一个产生式设置一个语义规则.

中间代码优化

就是卡常.
比如什么常量表达式节省(直接用常数结果代替原表达式)
公共表达式节省(用临时变量取代计算结果)
循环不变式外提(将循环中不变的计算结果挪到循环外面)
强度削减(多用加减少用乘除少用mod这种)

  • 除法表达式不要外提(防止溢出)
  • 赋值表达式不要外提(因为不一定执行该循环)

基本块划分

每一个基本块的代码要么都执行要么都不执行.

每一个基本块可以直接在四元式代码中框出来.

运行时存储空间管理

栈式管理的活动记录

1
2
3
4
5
6
7
8
9
10
11
12
13
14
^rop
|管理信息 
|       临时变量区
|       局部变量区
|       形参区    (上面三个都是数据)
|       变量访问环境(非局部数据的访问方式)
|       活动记录大小 (符号表size)
|       寄存器状态  (中断返回,现场恢复)
|       过程层数   
|       返回值     (地址是(call,Q,true,t)的t)
|       返回地址   (调用处)
|       动态链指针 (老sp)
|
|sp     活动过程记录

display表

表中存储了其外层过程中的最近局部变量的地址的基指针,所以按照调用链生成一个数组.
注意display表只有调用链中个过程的基指针,没有变量的偏移.

例如有调用链 (M,Q,H,R,S) ,同时M 是 level0，Q 是 level1，H 是 level2，R 是 level3，S 是 level3, S的局部display表的内容:

1
[M,Q,H,S]

为什么没有R:因为同一个level只存最近的,RS一个level S自己的当然优先.

只有调用内部嵌套过程的时候display才会++,否则不变,比如自己调用自己不变层号,

静态链和动态链

动态链的内容是谁调用了这个过程,level0的过程的静态链一般为空.

静态链的内容是这个过程外部一层的过程,用于访问变量的时候如果自己没有就要通过动态链往上层找.

做题

编译程序必须完成的工作有哪些?

词法分析
语法分析
语义分析
目标代码生成

错误

词法错误

数中出现非数字字符

语法错误

else没有匹配的if

语义错误

使用的函数没有定义(链接失败)
数组下标越界(语义错误,动态检查的时候爆出来)
类型操作符不匹配(比如string+int)
控制流错误(比如main函数中放break)
上下文错误(比如有返回值但是没return)

逆波兰式

例如 xabac+d*e+*+= 处理的时候读到一个字符就压栈,读到一个操作符就弹栈然后用弹出来的元素计算然后再压栈.

四元式

(ENDWHILE,-,-,-) 标明循环体的结束,转向循环头(endwhile用在循环末尾,作用是无条件跳转到循环头然后开启新一轮判断,如果判断合法就继续循环,因为这个通常在循环体末尾所以能标识循环体结束)

回填语句

目前不能确定地址,需要等待下一步操作的时候才进行填地址的操作叫做回填.
ENDWHILE 本身不涉及回填,但是需要触发回填把while的do回填掉.
IF 需要回填,因为不知道else的地址

总结

讲一讲Fluu预习编译原理的感受.

整个编译原理就是一个傻逼课程,然后整个课程的教材也是非常的防自学.

为什么说编译原理是傻逼课程?

编译原理太不说人话了.

比个例子, A->ab 这就是很正常的字符串替换,然后编译原理非得起一个名词,叫做推导.
对于这些规则,编译原理又起了一个名词叫做产生式,这不就是字符串的替换规则嘛,为什么要起这么拗口的名字?

编译原理难吗?

其实不难的,整个编译原理的课程很顺,就是你自然而然就能想到该怎么办.

以写程序的角度考虑,编译原理就是让你手写一个程序,这个程序能够识别对应的代码输入然后生成一个正确的计算程序,然后这个程序能够根据输入得到期望的输出,这就是个大模拟.

那么首先我们要把各种单词都认识出来,所以要做词法分析,因为用户自定义的变量比如 int aaaaa=0; 这种变量名很多很杂我们不可能枚举出来所有用户可能起的名字,所以我们要学习用正则表达式去匹配.

但是很多规则可能有一个前缀A,我们如何确定选择哪个呢?
朴素的dfs枚举规则涉及回溯肯定会超时,所以我们考虑”走一步算一步”,匹配一个字符,然后转换一个状态,这就是字典树,也称trie树,也就是有限状态自动机的具体代码实现.

但是可能有很多抽象规则,比如 A->B,B->c 这种多层嵌套的只看一个A看不出来,我们怎么知道能不能匹配c呢?
这个时候就需要求first集,follow集和predict集了,理解了集合意义之后公式就会非常好记.

然而有的正则的规则使用一些比如空边的才能转换,但是空边在trie树是不允许的,所以我们需要学习一下如何把NFA转成DFA.同时如果程序很大,trie树会有很多节点,我们也要学习一下如何精简DFA,这就顺下来了.

把单词都匹配出来之后就变成了token序列,这个时候我们要尝试看看用户写的对不对,算式写的对不对,所以需要语法分析,比如 3*2+5 这个式子该怎么算?需要建立一颗二叉树代表整个的计算方式,同时用递归下降等方法去得到这个二叉树,这个二叉树就叫语法树(也叫推导树),然后照着二叉树dfs去得到算式的答案.

但这还没完,刚刚只是进行了语法分析,但是程序还不真正的理解程序的意思,比如 int a="123" 这显然是不对的,因为 "123" 是一个string,而 a 是一个int,所以我们还需要认出来什么是什么,就有了符号表,记录变量的各种信息.那么想象一下符号表里面有什么?变量名,变量值,变量位置(偏移),变量大小,是否const,变量层数(因为cpp里面允许多层的同名变量),变量类型…

然后如果变量很多该怎么查找?可以用比如散列,顺序查找等…

然后我们把语义分析都做完了之后就该生成代码了,四元式嘛,考试不会让手写四元式生成程序的,所以你不用管具体偏移是咋算的,只需要根据代码写四元式代码就行(人肉编译器简称什么?),所以这部分也不难,会口胡就行.

然后为了管理自己的变量和外部的变量,我们需要维护一个神秘的地址,这个地址能够找到外部变量在哪.有两种方式:第一种逐层向外找(动态链和静态链),第二种是我自己直接记录了所有上级,不用逐层了(display表).

综上所述,整个编译原理不涉及非常高深的知识,就是个大模拟,而且思路很顺,本身其实是不难的,但是因为编译原理有一堆名词和很吓人的公式,可能看起来会很难.

后记

22年的编译原理有chengeng佬满分了,然后23年的编译原理就很抽象.

不是题目抽象,而是判卷很抽象.

Fluu喜提 66.4 分,然后看了看就业群一堆 60.1 感谢老师捞的,光就业群有七八个 60-61 的.
听同学说一个四人寝只有一个过了,其他三个全挂了,有点离谱的.

就这判卷的结果真的不是教学事故吗,就听说过一个七十多,还有同学是88,太抽象了.