SDU编译原理复习笔记

本文最后更新于：2022年7月7日 上午

简答与计算

画图表示编译过程的各阶段（必考）

编译的前端和后端，一遍扫描

编译前端：与源语言有关但与目标机无关的部分，如词法分析、语法分析、语义分析与中间代码生成、与机器无关的优化

编译后端：与目标机有关的部分，如与目标机有关的优化、目标代码生成

一遍扫描：在语法分析的同时计算属性值，而不是语法分析构造语法树之后进行属性的计算，而且无需构造实际的语法树

判断文法二义性

如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义的

例$S\to iSeS|iS|i $，句子$iiiei$，画出两棵不同的语法树

上下文无关文法

一个上下文无关文法$G$是一个四元式$(V_T,V_N,S,P)$，其中

  • $V_T$：终结符集合

  • $V_N$：非终结符集合

  • $S$：文法的开始符号，属于非终结符

  • $P$：产生式集合，$S$必须在某个产生式的左部出现一次

短语 句柄 素短语

详解

短语：$S\Rightarrow^* \alpha A\delta$且$A\Rightarrow^+\beta$，则$\beta$是句型$\alpha\beta\delta$相对于非终结符$A$的短语

直接短语：$S\Rightarrow^* \alpha A\delta$且$A\Rightarrow\beta$

句柄：一个句型的最左直接短语

素短语：至少含有一个终结符的短语，且除它自身之外不再含有任何更小的素短语

画出语法树

短语：以某非终结符为根的子树叶节点组成的字符串

直接短语：只有两代的子树叶节点组成的字符串

句柄：最左的二层子树叶节点组成的字符串

素短语：从短语集合中找出所有含终结符的短语，然后选出除它自身外不再含素短语的

描述算符优先算法

用于分析任一产生式右部都不含两个连续的非终结符且任何终结符对仅满足$=,<,>$一种关系的算符优先文法

从算符优先文法构造优先关系表。使用一个符号栈，存放终结符和非终结符。从左到右扫描输入串，比较输入串符号与栈中终结符的优先关系，找到最左素短语则进行归约，直到扫描结束符号栈呈现#N#说明分析正确

描述LR语法分析算法

L表示从左到右扫描输入串，R表示构造一个最右推导的逆过程

根据文法产生式构造LR分析表，包括Action表和Goto表。使用一个分析栈，存放状态序列和已归约串。从左到右扫描输入串，根据分析栈的栈顶状态和输入串符号，参考LR分析表，进行输入串字符的移入或归约，通过不断改变分析栈内容，最终将句子归约至开始符号，LR分析结束。

解释综合属性

在语法树中，一个结点的综合属性的值由其子结点的属性值确定

解释继承属性

在语法树中，一个结点的继承属性由此结点的父节点和/或兄弟结点的某些属性确定

解释S-属性文法

S-属性文法是只含有综合属性的文法

解释L-属性文法

L-属性文法中的每个产生式，其语义规则中的属性要么是综合属性，要么是仅依赖于左边兄弟结点、父结点的继承属性

解释语法制导翻译

对单词符号串进行语法分析，构造语法分析树，然后根据需要遍历语法树并在语法树的各结点处按语义规则进行计算

语法制导翻译中$M\to \varepsilon$的作用

使所有嵌入的动作都出现在产生式的末尾，这样就可以自下而上处理继承属性

结合例子谈回填思想

生成一个跳转指令时暂时不确定它的目标标号，则建立一个链表暂存这些指令，同一个链表中所有的跳转指令具有相同的目标标号，待能确定正确的目标标号后再去填写链表中的指令

符号表作用

  • 收集符号属性

  • 上下文语义的合法性检查的依据

  • 目标代码生成阶段地址分配的依据

参数传递

  • 传地址：将实参的地址传递给相应的形参

  • 得结果：每个形参有两个单元，第一个存实参地址，第二个存实参的值。对形参的访问看作对第二个单元的访问，最终结果应当传递回去

  • 传值：将实参的值传递给相应的形参

  • 传名：将被调用段的过程抄到调用出现的位置，形参都替换成相应的实参

Display表及作用

是一个指针数组，称为嵌套层次显示表，自顶向下依次存放现行层、直接外层直至最外层的每层过程的最新活动记录的基地址

提高访问非局部量的速度

C语言活动记录结构

四个项目

  • 连接数据，有两个

    • 老SP值，即前一活动记录的地址

    • 返回地址

  • 参数个数

  • 形式单元：存放实在参数的值或地址

  • 局部数据区：过程的局部变量、数组内情向量和临时工作单元

允许过程嵌套的活动记录结构

法一：静态链

引入一个称为静态链的指针，指向直接外层的最新活动记录的基地址

法二：Display表

连接数据新增全局display地址，为调用过程的display表地址

优化的基本概念

目的：产生更高效的代码

原则：

  • 等价原则：优化后不应改变程序运行结果

  • 有效原则：优化后产生的目标代码运行时间较短，占用的存储空间较小

  • 合算原则：应尽可能以较低的代价取得较好的优化效果

手段：

  • 删除公共子表达式

  • 复写传播

  • 删除无用代码

  • 代码外提

  • 强度削弱

  • 删除归纳变量

根据语言求上下文无关文法

$L(G)=\{a^n b^n|n\ge 1\}$ $S\to aSb|ab$

$L(G)=\{a^n b^n|n\ge 0\}$ $S\to aSb|\varepsilon$

$L(G)=\{a^n b^m a^m b^n|m\ge 0, n\ge 0\}$ $S\to aSb|A,A\to bAa|\varepsilon$

写正规式

字母表包含$\{a,b\}$，偶数个$a$的正规式 $b^*(ab^*ab^*)^*$

以$01$结尾的二进制数串 $(0|1)^*01$

能被5整除的十进制整数 $(1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)^*(0|5)|(0|5)$

包含奇数个$1$或奇数个$0$的二进制数串 解析 $0^*1(0^*|10^*1)^*|1^*0(1^*|01^*0)^*$

所有大于101的二进制整数 $11(0|1)|1(0|1)^*(0|1)(0|1)(0|1)$

消除左递归

  • 把所有非终结符按任一种顺序排列成$P_1,P_2,…,P_n$

  • 按序处理

    • 使$P_i\rightarrow\alpha$ 中的 $\alpha$ 仅含有 $P_j,(j\ge i)$

    • 消除$P_i$的直接左递归

  • 化简，取出从开始符号出发永远到达不了的非终结符的产生规则

消除直接左递归

改写为

提左公因子消除回溯

改写为

中缀式改后缀式

法一

  • 遇操作数直接输出

  • 栈为空时 运算符直接入栈

  • 遇( 入栈

  • 遇) 弹出栈中(以上元素 但不输出括号

  • 遇运算符 弹出栈顶优先级高于或等于它的 再入栈

  • 遇末尾 弹出所有元素

法二

  • 先按照运算符的优先级对中缀表达式加括号

  • 将运算符移到括号的后面

  • 去掉括号

优先级（由高到低）

  • ()圆括号 []下标运算符 ->

  • !逻辑非 ~按位取反 ++前缀增量 --前缀减量 -负号 (type)类型转换 *指针 &地址 sizeof长度

  • *乘法 /除法 %取余

  • +加法 -减法

  • <<左移 >>右移

  • < <= > >= 关系运算符

  • == != 关系运算符

  • & 按位与

  • ^ 按位异或

  • | 按位异或

  • && 逻辑与

  • || 逻辑或

  • ?: 条件

  • = += -= *= /= %= &= ^= |= <<= >>= 赋值运算符

  • ,逗号运算符

综合题

词法分析

给出正规式

① 构造NFA

  • 使初态终态唯一 引入新的初态X和终态Y

  • 分裂 使每条弧上或为$\varepsilon$或为单个字符

② 确定化 子集法

③ 最小化

LL(1)分析

给出文法

① 构造FIRST集合

② 构造FOLLOW集合

③ 判断是否为LL(1)文法

④ 构造LL(1)分析表（可能涉及消除二义文法冲突）

⑤ 识别句子

LR分析

给出文法

① 构造拓广文法

给文法添加一条产生式$S’\rightarrow S$，其中$S$是原文法的开始符号，使初始状态唯一

② 构造拓广文法的LR(0)/LR(1)项目集规范族

LR(1)还要求FIRST集合

$A\rightarrow\varepsilon$的LR项目表示为$A\to\cdot (,\#)$

③ 判断是否为LR(0)/LR(1)文法

LR(0)

  • 一个项目集中是否既有移进项目又有归约项目

  • 一个项目集中是否含有两个或两个以上的归约项目

LR(1)

  • 一个项目集中是否有移进-归约或归约-归约冲突（确保生成的分析表中每个单元格内的值唯一）

④ 构造LR(0)/LR(1)分析表（可能涉及消除二义文法冲突）

⑤ 识别句子

语法制导翻译

给出翻译模式和高级语言程序，翻译句子为三地址代码或四元式序列

一般涉及多种类型句子的综合，也可能涉及声明语句填写符号表

说明语句

IF 语句

if E then S1 else S2

  • 翻译E

  • 回填E的真出口，E的假出口未知

  • 翻译S1

  • 遇到else，S1结束，生成一条无条件转移四元式，但出口未知

  • 回填E的假出口

  • 翻译S2

  • 回填S1结束后的转移出口

1
2
3
4
if A>B or C then
    if D<E then F:=F+1
    else F:=F-1
else F:=0

三地址代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
100    if A>B goto (104)
101    goto (102)
102    if C goto (104)
103    goto (112)
104    if D<E goto (106)
105    goto (109)
106    T1:=F+1
107    F:=T1
108    goto (113)
109    T2:=F-1
110    F:=T2
111    goto (113)
112    F:=0
113

四元式形式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
100    (j>, A, B, 104)    
101    (j, _, _, 102)
102    (jnz, C, _, 104)		// 注意一下jnz
103    (j, _, _, 112)
104    (j<, D, E, 106)
105    (j, _, _, 109)
106    (+, F, 1, T1)
107    (:=, T1, _, F)
108    (j, _, _, 113)
109    (-, F, 1, T2)
110    (:=, T2, _, F)
111    (j, _, _, 113)
112    (:=, 0, _, F)
113

WHILE 语句

while E do S1

  • 翻译E

  • 回填E的真出口

  • 翻译S1

  • 无条件转移到E代码段的第一条四元式

  • 回填E的假出口

1
2
3
while a<b do
    a:=a+3
    b:=b-3

三地址代码

1
2
3
4
5
6
7
8
100    if a<b goto (102)
101    goto (107)
102    T1:=a+3
103    a:=T1
104    T2:=b-3
105    b:=T2
106    goto (100)
107

四元式形式

1
2
3
4
5
6
7
8
100    (j<, a, b, 102)
101    (j, _, _, 107)
102    (+, a, 3, T1)
103    (:=, T1, _, a)
104    (-, b, 3, T2)
105    (:=, T2, _, b)
106    (j, _, _, 100)
107

多类型句子的综合

1
2
3
while A<C and B<D do
    if A=1 then C:=C+1
    else while A<=D do A:=A+2

三地址代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
100    if A<C goto (102)
101    goto (115)
102    if B<D goto (104)
103    goto (115)
104    if A=1 goto (106)
105    goto (109)
106    T1:=C+1
107    C:=T1
108    goto (100)			// 已更正 不是goto(114)
109    if A<=D goto (111)
110    goto (100)			// 通通是S1.next的值
111    T2:=A+2
112    A:=T2
113    goto (109)
114    goto (100)
115

四元式形式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
100    (j<, A, C, 102)
101    (j, _, _, 115)
102    (j<, B, D, 104)
103    (j, _, _, 115)
104    (j=, A, 1, 106)
105    (j, _, _, 109)
106    (+, C, 1, T1)
107    (:=, T1, _, C)
108    (j, _, _, 100)
109    (j<=, A, D, 111)
110    (j, _, _, 100)
111    (+, A, 2, T2)
112    (:=, T2, _, A)
113    (j, _, _, 109)
114    (j, _, _, 100)
115

补个语法树的全过程分析草图

星星说涉及到的翻译模式都会给，时间充裕可以一步一步慢慢来

优化和目标代码生成

给出基本块代码

① 构造DAG

结点的左右位置要与操作数对应

② 写出优化后的中间代码

按照构造其结点的顺序生成中间代码，有常数的直接用常数

如果DAG某内部结点上附有多个标识符，由于计算该结点值的表达式是一个公共子表达式，当我们把该结点重新写成中间代码时，就可以删除多余运算

③ 写出DAG目标优化后的中间代码

DAG结点计算顺序

N个内部节点，线性表T[N]记录顺序，从后往前填写

1
2
3
4
5
6
7
8
while(存在不在T中的结点){
        找不在T中但其所有父结点在T中，或者没有父结点的内部节点n，n填入T
        while(n的左孩子m不是叶结点且它的所有父结点在T中){
                m填入T
                n=m
        }
}
// 有点像拓扑排序

还可进一步删除中间代码序列中其他情况的无用赋值

  • 如果DAG中某结点上附加的标识符在该基本块后面不会被引用，那么就不生成对该标识符赋值的中间代码

  • 如果某结点上不附有任何标识符或者其上附加的标识符在基本块后面不会被引用，而且它也没有前驱结点，这意味着基本块内和基本块后面都不会引用该结点的值，那么就不生成计算该结点值的代码

  • 如果有两条相邻的代码A := C op D和B := A，其中第一条代码计算出来的A值只在第二条代码中被引用，那么把相应结点重写成中间代码时，原来的两条代码将变换成B := C op D

④ 根据变量活跃性和寄存器信息写出目标代码

计算待用信息和活跃信息算法

寄存器分配算法

生成必要的存数指令

代码生成算法

处理完每个产生式后检查，如果寄存器中的某变量在基本块出口之后是活跃的，则需要用ST指令将其存储到主存单元中