编译原理总结_编译原理 基础问题

其实我是想借着复习重构我的编译原理的，也是这样做的，但无奈之前浪费了一些时间，秉着功利化的角度，以下仅对考点部分进行整理。

题目1：正则表达式与自动机

正则表达式——描述词法单元规约

基本概念

id:字母开头的字母/数字串
id定义了一个集合，我们称之为语言(Language)
使用的字母与数字等符号集合，称之为字母表
该语言中每个元素(即标识符)称为串(String)

字母表是一个有限符号的集合(符号可以是任意符号)

串：字母表上的串(s)是由字母表中符号所构成的有穷集合，特别的空串的长度为0
串的运算：

• “连接”，拼接起来，和空串拼接为其本身
• “指数运算”，相同串的“连接”，0次为空串

语言：语言是给字母表上一个任意可数的串集合，区别空语言和只包含空串的集合
语言是串的集合，因此可以通过集合操作构造新的语言

ANTLR4如何知道上述规则？简洁、优雅、强大的正则表达式

每个正则表达式r对应一个正则语言L®，正则表达式是语法，描述构成，正则语言是语义，描述功能

对应正则表达式有正则语言

lexer-automata

自动机理论——自动化词法分析器

两大要素：状态集S以及状态转移函数

生命游戏：元胞自动机

根据表达/计算能力强弱，自动机可以分为不同层次

0是初始状态
3是接收状态
非确定性：

• 0状态可以转移到0或1状态
• 存在空串转移，即没有看任何字符情况下也可以自发跑到其他状态
• 为符合定义，遇到没有指明的状态的转移字符，默认跑到空状态集合上

我们关注的是非确定性有穷自动机的语义：

语言就是字符串的集合

可以通过状态转移图确认某状态(字符串)集合是否能被接受，也能通过NFA确认其所能识别的正则表达式

确定性：

• 只能通过消耗字符进行状态转移(不能通过空串转移)
• 识别一个字符，只有唯一确定的下一状态

约定：所有没有对应出边的字符默认指向一个“死状态”，“死状态”是无论接受何种字符，都指向自身的一种状态，不能再被任何接受状态所接受。

NFA简洁易于理解，便于产生描述语言L(A)
DFA易于判断x∈L(A)，适合产生词法分析器
所以我们用NFA描述语言，用DFA实现词法分析器，也就有了通过re构造词法分析器时：
RE->NFA->DFA->词法分析器

RE->NFA

Thompson构造法

推荐书籍：《UNIX传奇》

看一个例子：

就是按照上述规则，进行拼接。

NFA->DFA

N->D，要求L(D) = L(N)

子集构造法，思想：用NFA模拟构造DFA

步骤：
1.确认初始状态集合(不只是0状态，还有空串跳转的状态)
2.得到各转移状态集合
3.确认接受状态(包含接收状态的集合)

步骤1.2对应以下定义：

构造原理如下，不过是过于规范化的语言，没必要过度深究，理会其中意思即可。

子集构造法复杂度分析，最多为2^n

闭包
f(x) = x(x称为f的不动点)

DFA最小化

DFA最小化算法基本思想：等价的状态可以合并

如何定义状态等价？接受同一字符，跳转至相同状态则两状态等价，正确？
NO，转移至等价状态。

基于该定义，不断合并等价的状态，直到无法合并为止，但这是一个过渡时期递归定义，从哪里开始？所有接受状态都是等价吗？不是。

反其道而行，划分，而非合并！
从哪里开始？接受状态与非接受状态必定不等价，不断迭代。

下面看一个例子：

注意：不是通过状态转移后还是在原先集合中，而是看集合中各状态通过相同状态转移是否到达相同转移状态。上述例子就完成了A、C状态的合并。

划分到再也无法划分为止(不动点)，然后，将同一等价类中的状态合并。

需要注意事项：

这里其实还有一点个人理解，进行最小化划分时，先将每一个集合中所有状态转移均考虑，而非碰到异常便将其取出就结束进入下一轮迭代，不论对错，如果有相同状态转移情况的，先将其合并，在下一轮迭代再加以验证。

题目2：LL语法分析

使用预测分析表确认产生式

LL(1)文法：如果文法G的预测分析表是无冲突，则G是LL(1)文法。无冲突：每个单元格只有一个产生式。
对于当前选择的非终结符，仅根据输入中当前词法分析单元即可确定要使用哪条产生式

FIRST集合，最左端终结符的集合。

可能产生空串的情况，看下一个符号是否为终结符以及与当前指针所指向的符号是否匹配

FIRST(a)是从a推导得到的句型的首终结符的集合

考虑非终结符A的所有产生式，如果它们对应的FIRST(ai)集合互不相交，则只需查看当前输入词法单元，即可确定选择哪一个产生式(或报错)

FOLLOW(A)是可能在某些句型中紧跟在A右边的终结符的集合

计算FIRST集合

不断应用上面规则，直到每个FIRST(X)都不再变化(不动点！！！)

不仅要计算左部的FIRST集合，还要计算右部的FIRST集合。

计算FOLLOW集合

不断应用上面的规则，直到每个FOLLOW(X)都不再变化(不动点！！！)

当下的选择未必正确，但你别无选择

构造预测分析表

值得注意的，通常情况下，文法的开始符号为第一条语句(这里困惑了半天)

如何构造预测分析表？
若当前a在FIRST(s)中，选择产生式A->s，如果FIRST中存在空串，再去FOLLOW集合中寻找是否存在。

上述认知存在错误，具体解题看下列过程：、

对于LL(1)文法，预测表中每个条目都唯一地指向一个产生式，或者标明Error，用以判断是否为LL(1)文法

L：从左往右扫描输入
L:构建最左推导
1：只需向前看一个输入符号便可确定使用哪条产生式

题目3：LR语法分析

只考虑无二义性的文法，这意味着，每个句子对应唯一的一棵语法分析树
今日主题：LR语法分析器

LL(k)的弱点：在仅看到右部的前k各词法单元时就必须预测要使用哪条产生式，自左向右扩展
LR(k)的优点：看到与正在考虑的这个产生式的整个右部对应的词法单元之后再决定，自右向左规约

自底向上的、不断规约的、基于句柄识别自动机的、适用于LR文法的、LR语法分析器

推导采取了最右推导，LL算法采取的是最左推导。最右推导是为了从左往右规约。
自底向上语法分析器为输入构造反向推导

LR语法分析器：

• L：从左往右扫描输入
• R：构建反向最右推导

句柄只有可能在栈顶往下某一段。

两大操作：移动输入符号与按产生式规约，直到栈中仅剩开始符号E，且输入结束，则成功停止

两问题：何时规约？以哪条产生式规约？

栈的状态影响使用的规约语句

一开始为0号状态

s5——shift 5，移入该单元，将词法分析器状态设为5

右侧非终结符goto是因为规约时出栈之后还要压入非终结符，此时也要进行状态转移。

时刻注意规约后栈顶的状态，以此来选择goto语句，最后栈顶应该剩余起始符号，停在acc状态。

规约必要条件：当前状态下，已观察到某个产生式的完整右部

句柄：
在输入串的（唯一）反向最右推导中，如果下一步是逆用产生式A->a规约，则称为句柄。

LR语法分析器关键就是搞笑寻找每个规约步骤所使用句柄。

存在一种LR语法分析算法，保证句柄总是出现在栈顶。

LR(0)句柄识别有穷自动机：
状态刻画了“当前观察到的针对所有产生式的右部的前缀”

项(使用小数点分隔)指明语法分析器已经观察到了的某个产生式的某个前缀。

项集：项集就是若干项构成的集合。
句柄识别自动机的一个状态可以表示一个项集
项集族：若干项集构成的集合
句柄识别自动机的状态集可以表示为一个项集族。

赠广文法：

纯粹技术上的处理。

初始状态：

如何求初始状态？增加一条增广文法作为0号产生式，求闭包，其后4号状态也是这样构建出来的。

为何状态4能扩展这么多？因为点移动后，右部为非终结符E，要闭包展开，其余初始状态进行转移时点后均为终结符，不需要再展开了。

切记不要忘记闭包。

接受状态——点在最右端，找到了可能的句柄

根据状态转移图构建分析表：
LR(0)分析表与SLR分析表标准是不同的，考试要求是SLR

LR语法分析表：

状态中有点已经到最右端，拿句柄做规约，无脑规约

LR(0)分析表每一行(状态)所选用的规约产生式是相同的，规约时不需要向前看，这就是’0’的含义

SLR(1)

SLR(1)是在LR(0)基础上增加求FOLLOW集合，判断碰到某字符是否能做规约操作，而非无脑规约

同样的，如果文法G的SLR(1)分析表是无冲突的，则G是SLR(1)文法

两类可能的冲突：“移入/归约”冲突，“归约/归约”冲突。

题目4：ANTLR4与“优先级上升算法”

不是LL(1)算法，怎么办？改造他，消除左递归，提取左公因子

改写成右递归，算法要求：

• 文法中不存在环
• 文法中不存在空产生式

提取左公因子：
antlr4可以处理有左公因子的文法

/*
decl : 'int' ID ';'
     | 'int' ID '=' ID ';'
     ;
*/

decl : 'int' ID optional_init ';' ;
optional_init
    : '=' ID
    |
    ;

/*
decl : 'int' ID ('=' ID)? ';'
*/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

很明显，提取左公因子无助于消除文法二义性？

antlr4自动将类似expr的左递归规则重写成非左递归形式
antlr4提供优秀的错误报告功能
antlr4使用AllStar算法
antlr4几乎能处理任何文法

将递归改造成了循环

优先级上升算法

后面调用expr时将优先级升了，因为如果要在里面展开更高优先级的操作，必然现在所需要的优先级是要更高的。

根本问题：究竟是在expr的当前调用中匹配下一运算符，还是让expr的调用者匹配下一运算符

左结合，优先级上升；右结合，优先级不变

题目5：语法制导的翻译

SDD唯一确定了语法分析树上每个非终结符节点的属性
SDD没有规定以什么方式、什么顺序计算这些属性值

综合属性：节点N上的综合属性只能通过N的子节点或N本身的属性来定义，如果一个SSD的每个属性都是综合属性，则它是S属性定义。

S属性定义的依赖图描述了属性实例之间自底向上的信息流。在LL语法分析器中，递归下降函数A返回时，计算相应节点A的综合属性。

继承属性：节点N上的继承属性只能通过N的父节点、N本身和N的兄弟节点来定义。

再通过综合属性加以返回。

L属性定义：一个SDD每个属性

• 要么是综合属性
• 要么是继承属性，规定其继承属性
  • 和产生头A关联的继承属性
  • 和左兄弟节点相关的继承属性或综合属性
  • 和本身相关继承属性或综合属性，不存在环

Offline(加listener)
Online属性和动作嵌入到语法分析树构建过程中去
Online(addParseListener)

SDT：

将语法的规则、动作以方括号的方式真正嵌入到文法中去。

如何将SDD转换为SDT？时机！

题目6：目标代码生成

给定指令，完形填空
返回地址、栈重点

精简指令集：一条指令只干一件事

ISA：软硬件接口

第一节课汇编都挺简单的，第二课没怎么听

寄存器：一般使用别名
ra寄存器：存储返回地址
t0-t6，保存临时变量
pc：下一条指令地址

课上实现的汇编代码：
add:

li t0, 20	# li: load immediate将20load到t0寄存器，li也是伪指令，实际为addi x5, x0, 20
li t1, 22
add t2, t0, t1
1
2
3

addi:

li t0, 100
addi t0, t0, 20	# addi: add immediate # 没有subi指令，做减法addi 负数
addi t0, t0, -20
1
2
3

sub-add

# f = (g + h) - (i + j)
# t6 = (t0 + t1) - (t3 + t4)

li t0, 0
li t1, 10
add t2, t0, t1

li t3, 30
li t4, 40
add t5, t3, t4

sub t6, t2, t5
1
2
3
4
5
6
7
8
9
10
11
12

ecall:系统调用

# f = (g + h) - (i + j)
# t6 = (t0 + t1) - (t3 + t4)

li t0, 0
li t1, 10
add t2, t0, t1

li t3, 30
li t4, 40
add t5, t3, t4

sub t6, t2, t5

li  a7, 1    //打印指令  
mv a0, t6    # add a0, t6, zero  //mv是伪指令 
ecall
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

分配内存空间，reserved、text、data、heap、stack

动态数据：堆区

data:

# f = (g + h) - (i + j)
# t6 = (t0 + t1) - (t3 + t4)

.data
g: .word 0  //4字节
h: .word 10
i: .word 30
j: .word 40

result: .word 0

msg: .string "The result is :"	# .ascii

.text
//规定的两步操作将值放到寄存器中
la t0, g		# la: load address，要先将内存的地址load到寄存器中，区别于li
lw t0, 0(t0)	# lw: load word

la t1, h		
lw t1, 0(t1)	
add t2, t0, t1

la t3, i		
lw t3, 0(t3)	
la t4, j		
lw t4, 0(t4)
add t5, t3, t4

sub t6, t2, t5

//将值放到对应内存地址
la t0, result
sw t6, 0(t0)	# sw: store word

li  a7, 4     # 打印字符串4号调用
la a0, msg
ecall

li  a7, 1      
mv a0, t6    # add a0, t6, zero   
ecall
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

a0-a8参数寄存器

数组array：

.data
numbers: .word -30, 30, -20, 20, -10, 10, 0

.text
la t0, numbers
lw t1, 12(t0)//偏移12字节
addi t1, t1, 80
sw t1, 12(t0)
1
2
3
4
5
6
7
8

跳转指令branch-max

# c = max(a, b)

.data
a: .word 100
b: .word 200
c: .word 0

.text
lw t0, a//将两步简化为一步，不过是该工具提供，也不是基础指令
lw t1, b

bge t0, t1, greater_equal
mv t2, t1
j end	# j: jump,也是语法糖

greater_equal:
mv t2, t0

end:
sw t2, c, t3//la t3,c   sw t2,0(t3)，t3是中介
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

循环array-for

.data
numbers: .word -30, 30, -20, 20, -10, 10, 0
size: .word 7

positive_sum: .word 0
negative_sum: .word 0

.text
la t0, numbers		# t0: the address of the array
lw t1, size			# t1: size = 7

mv t2, zero			# counter, initially 0

li t3, 0				# t3: sum of positive numbers <- 0
li t4, 0				# t4: sum of negative numbers <- 0

loop:
	bge t2, t1, end_loop
	# numbers[t2]
	# mul t5, t2, 4
	slli t5, t2, 2		# slli: shift left logical immediate，左移操作代替乘法操作
	add t5, t0, t5
	lw t5, 0(t5)
	
	addi t2, t2, 1
	
	bltz	 t5, negative	# bltz: branch if less than zero
	add t3, t3, t5
	j loop
	
negative:
	add t4, t4, t5
	j loop

end_loop:
	sw, t3, positive_sum, t5
	sw, t4, negative_sum, t5
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

函数调用(栈)：a0-a7按顺序存放参数
proc-max:

# proc-max.asm

.data
max_result: .word 0

.text
.global main//申明为全局函数

max:
# a0 (argument 0), a1
blt a0, a1, smaller
j end_max

smaller:
mv a0, a1   //约定返回值放在a0、a1中

end_max:

ret
# jr ra	# jr: jump register
# jalr zero 0(ra)	# jalr: jump and link register，zero将不关心的值永远取0
# jal: jump and link

############### main ###############
.data
a: .word 100
b: .word 200

.text
main:
lw a0, a
lw a1, b

call max
# jal max           # 约定ra保存返回地址
# jal ra, max		# jal: jump and link	ra: return address register保存返回地址
# TODO
sw a0, max_result, t0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

斐波拉契数

.text
.global main

factorial:
beqz a0, base_case

addi sp, sp, -8//栈地址是由高到低，做减法
sw a0, 4(sp)
sw ra, 0(sp)

# n > 0: n * factorial(n - 1)
addi a0, a0, -1		# a0: n - 1
call factorial		# a0: factorial(n - 1) a0要保存参数，又要保存返回值？先使用栈保存起来
mv t0, a0			# t0: factorial(n - 1)

lw a0, 4(sp)			# a0: n
lw ra, 0(sp)
addi sp, sp, 8          //退栈

mul a0, a0, t0		# a0: n * factorial(n - 1)
j end

base_case:
	li a0, 1

end:
	ret


######### main ########
.data 
n: .word 10

.text
main:
lw a0, n
call factorial
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

被调用函数还要调用其他函数时，要将返回值也保存到栈上

RISC-V调用约定：那些寄存器的值由调用者还是被调用者保存
ra、t0-t2、a0-a1、a2-a7、t3-t6交给调用者保存。

斐波拉契数

.text
.global main

factorial:
beqz a0, base_case

addi sp, sp, -8//栈地址是由高到低，做减法
sw a0, 4(sp)
sw ra, 0(sp)

# n > 0: n * factorial(n - 1)
addi a0, a0, -1		# a0: n - 1
call factorial		# a0: factorial(n - 1) a0要保存参数，又要保存返回值？先使用栈保存起来
mv t0, a0			# t0: factorial(n - 1)

lw a0, 4(sp)			# a0: n
lw ra, 0(sp)
addi sp, sp, 8          //退栈

mul a0, a0, t0		# a0: n * factorial(n - 1)
j end

base_case:
	li a0, 1

end:
	ret


######### main ########
.data 
n: .word 10

.text
main:
lw a0, n
call factorial
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

[外链图片转存中…(img-Ea6u5A2k-1697288681744)]

被调用函数还要调用其他函数时，要将返回值也保存到栈上

RISC-V调用约定：那些寄存器的值由调用者还是被调用者保存
ra、t0-t2、a0-a1、a2-a7、t3-t6交给调用者保存。
考试应该会对于这点考察较为严苛，注意一下，不过也就是形式化的几句。