«编译原理»笔记

编程语言是向人以及机器描述计算过程的 notations。 关于翻译 没办法，编译器是外国人发明的，所以很多词汇在编译原理中含义是不一样的，按惯用法翻译成中文，就无法一一对应（说实话，有些词语在英文里也是混用的）。比如有很多个单词，翻译成中文就都成了 “符号”。但是我实在不想中英夹杂， 因为切换输入法太麻烦了 所以我干脆自己做一个翻译规则表，当然也不是乱翻的，参考了别人的翻译。 英语 汉语 concept/notion 概念 character 字符 notation 记号 / 记法 annotation 标注 / 注解 denotation 直指 mark 标记 symbol (象征) 符号 token 词符 entry （符号表的）条目 sign 正负号 / 征象 - signifier 能指 - signified 所指 signification 意义 semiotics 符号学 * semantic 语义的 * pragmatic 语用的 * string 字符串 identifier 标识符 lexeme 词素 lexical 词法 syntax 句法 grammer 文法 pattern 规式 paradigm 范式 schema 方案 schema 章法 diagram 简图 model 模型 specification 规格 normal form 规范型 sentence 句子 clause 子句 function 函数 tag 挂签 label 标签 category 范畴 / 分类 parameter 形参 argument 实参 attribute 字段 property 函数属性 statement 陈述 assignment 赋值 operator 运算符 operand 运算对象 representation 表示法 1.

3.1 介绍 句法分析（syntax analysis，也叫 parsing）将会使用词符作为输入，用来创建一个树状中间层，从而表示词符流的语法结构。 解析算法有两个大类。 自上而下：将输入流与语法生成式进行预测匹配。（推导） 自下而上：从单词序列进行累加，直到显然地与生成式匹配（规约） 3.2 句法的表示 对于多数语言，句法使用 CFG 表示。 为什么不用 RE RE 只能记忆有限个状态，因此对于类似括号匹配这样状态无限的问题，规则式无能为力。 CFG 歧义问题 如 if-then-else 语句 Stmt -> if Expr then Stmt else Stmt | if Expr then Stmt | Asmt | ...(others) 语句： if Exp1 then if Exp2 then Asmt1 else Asmt2 会产生歧义，两种理解方式如下： if Exp1 then if Exp2 then Asmt1 else Asmt2 if Exp1 then if Exp2 then Asmt1 else Asmt2 因此必须增加规则来消歧义。 例如下面的规则：

3.2 (1) 以 0 开头和结尾的二进制串 (4) 含有三个 1 的二进制串 3.4 （1）S->AS|0|2|4|6|8 A->0|1|2|3|4|5|6|7|8|9 （2）S->AB A->1|2|3|4|5|6|7|8|9 B->CB|0|2|4|6|8 C->0|1|2|3|4|5|6|7|8|9 3.8 3.10 =+for 需要 (3)!=, <= 不需要

3.1 介绍 句法分析（syntax analysis，也叫 parsing）将会使用词符作为输入，用来创建一个树状中间层，从而表示词符流的语法结构。 解析算法有两个大类。 自上而下：将输入流与语法生成式进行预测匹配。（推导） 自下而上：从单词序列进行累加，直到显然地与生成式匹配（规约） 3.2 句法的表示 对于多数语言，句法使用 CFG 表示。 为什么不用 RE RE 只能记忆有限个状态，因此对于类似括号匹配这样状态无限的问题，规则式无能为力。 CFG 歧义问题 如 if-then-else 语句 Stmt -> if Expr then Stmt else Stmt | if Expr then Stmt | Asmt | ...(others) 语句： if Exp1 then if Exp2 then Asmt1 else Asmt2 会产生歧义，两种理解方式如下： if Exp1 then if Exp2 then Asmt1 else Asmt2 if Exp1 then if Exp2 then Asmt1 else Asmt2 因此必须增加规则来消歧义。 例如下面的规则：

如何表示语义信息？—— 使用语义属性 为 CFG 中的文法符号设置语义属性，用来表示语法成分对应的语义信息。如： id.value = 3 表示文法符号 id 的 value 属性值为 3. 语法规则：其实就是产生式 语法制导定义（SDD） SDD 将每个文法符号和一个语义属性集合相关联 将每个产生式和一组语义规则相关联，这些规则用于计算该产生式中各文法符号的属性值 例子： 产生式 语义规则 $D \to TL$ L.inh = T.type $T \to \text{int}$ T.type = int $T \to \text{real}$ T.type = real $L \to L_1, \text{id}$ L1.ih = L.inh 语法制导翻译方案（SDT） SDT 是在产生式右部嵌入了程序片段的 CFG, 这些程序片段称为语义动作。按照惯例，语义动作放在花括号内。

5.5 下面的文法产生对整型数和实型数应用 “+” 算符形成的表达式。两个整型数相加，结果仍为整型；否则为实型数， E -> E + T | T T -> num.num | num (1) 给出一个确定每个子表达式类型的语法制导定义。 解：可以定义属性 kind，取值 real int Production Semantic Rule E1 -> E2 + T E1.kind = (E2.kind == int && T.kind == int) ? int : real E -> T E.kind = T.kind T -> num.num T.kind = real E -> num E.kind = int 5.8 考虑如下产生 Pascal 声明语句的文法。 D -> L : T T -> integer | real L -> L, id | id (1) 给出确定变量类型的语法制导定义。

eg B：record i: integer; c: char; r: real end; 则 B 的类型表达式为 record( (i × integer) × (c × char) × (r × real) ) eg table: array[1..10] of row; table 的类型表达式为： array(1..10,row) eg struct stype { char[8] name; int score; }; stype[50] table; stype* p; 给出 stype table p 的类型表达式。 答： record ( ( name × array(8,char) ) × (score × integer) ) array(50,stype) pointer(stype) eg function fun(a: char, b: integer): ↑integer; 答：

#include <stdio.h>int k; int a[3]; void swap(int x,int y) { x=x+y; y=x-y; X=X-y; } void main() { k=1; a[0]=2; a[1]=1; a[2]=0; swap(k,a[k]); printf("k=%d,a[0]=%d,a[1]=%d,a[2]=%d\n" ,k,a[0],a[1],a[2]); swap(a[k],a[k]); printf("k=%d,a[0]=%d,a[1]=%d,a[2]=%d\n" ,k,a[0],a[1],a[2]); } 答： 我们看 swap 的实现。 x = x + y; // y = x - y; // y = (x + y) - y = x x = x - y; // x = (x + y) - (x) = y 在 main 的前四行，初始化 k = 1, a = {2, 1, 0}

运行时内存的划分 目标代码存放在固定大小的 代码区 大小可确定的变量、全局变量存放在固定大小的 静态区（可读可写） 栈存放活动记录（或称为栈帧），主要是一些短生命周期的数据。每个线程有自己的栈。 堆存放编译时大小无法确定的数据（而指向这些数据的指针，比如数组的首地址，则存放在栈中），通常是长生命周期的数据。线程之间可以共享堆。 过程起源于为了节省内存而可独立编译的程序片段。 一个过程的每一次执行称为一个活动。 每次活动时记录的状态称为活动记录。每个活动记录中有一系列的域。 用一棵树存放程序运行过程中所有的活动状态，称为活动树。 活动树和程序行为间存在对应关系： 1）过程调用的序列和活动树的前序遍历相对应； 2）过程返回的序列和活动树的后序遍历相对应； 3）亲节点是未结束活动，且路径顺序即调用顺序 假定控制流（当前状态）位于某个过程的特定活动中，且该活动对应于活动树上的某个结点 N。那么当前尚未结束的（即活跃的）活动就是结点 N 及其祖先结点对应的活动。这些活动被调用的顺序就是他们从根节点到 N 的路径上的出现顺序。这些活动将按照这个顺序的反序返回。 根据这样的性质，使得我们可以通过 栈 实现程序控制。 活动记录（栈帧）中各种域的作用 如下： # 名称 作用 1 临时数据 存放表达式中间结果 2 局部数据 存放局部数据。详见下文。 3 机器状态 调用前的状态，如之前的寄存器等，以便恢复现场 4 访问链 指向外层的作用域栈帧。由于只和代码有关，又叫静态链 5 控制链 指向调用方的（上一个）栈帧（比如 RSP，存放上个帧栈顶）由于在运行过程中不断压栈时形成，又叫动态链 6 实参 用于存放主调函数为被调用函数所提供的实参信息 7 返回值 被调用函数用来为主调函数存放返回值的域 斜体 表示非必须的 在实际实现时，返回值和部分实参通过寄存器传递。多数数据放在栈中。

$8.3$ 请把语句 if (x+y)*z=0 then s:=(a+b)*c else s:=a*b*c 翻译为: (2) 三地址代码。 解： 0 t1 = x + y 1 t2 = t1 * z 2 IF t2 == 0 GOTO 7 3 t3 = a + b 4 t4 = t3 * c 5 s = t4 6 GOTO 10 7 t5 = a * b 8 t6 = t5 * c 9 s = t6 10 8.4 有如下的 C 语言程序片断，请把其中的可执行语句翻译为:

中间代码表示 图形表示 三地址码 三地址码 一般形式： $$ x := y \operatorname{op} z $$ 表示： 四元式：$ (\operatorname {op} , \text {arg}_1, \text {arg}_2, \text {target}) $ 三元式：$ (\operatorname {op} , \text {arg}_1, \text {arg}_2) $ 通过语句指针消去显式的返回值 间接三元式：使用间接码表，映射序号到三地址语句序号。消除重复。 $8.3$ 请把语句 if (x+y)*z=0 then s:=(a+b)*c else s:=a*b*c 翻译为: (2) 三地址代码。 解： 0 t1 = x + y 1 t2 = t1 * z 2 IF t2 == 0 GOTO 4 3 GOTO 8 4 t3 = a + b 5 t4 = t3 * c 6 s = t4 7 GOTO 11 8 t5 = a * b 9 t6 = t5 * c 10 s = t6 11 要点就是分支语句满足条件，往近处跳，不满足，则往远处跳。

目标代码生成概述 目标代码生成程序的任务 将前端产生的源程序的中间代码表示转换为等价的目标代码。 对目标代码生成程序的要求： 正确 高质量 代码生成程序的位置 输入： 中间代码 符号表 记录了与名字有关的信息 决定中间表示中的名字所代表的数据对象的运行地址 输出： 与源程序等价的目标代码 逻辑地址空间 划分成为四个代码及数据区域: 一个静态确定的代码区 Code。这个区存放可执行的目标代码。目标代码的大小可以在编译时刻确定。 一个静态确定的静态数据区 Static。这个区存放全局常量和编译器生成的其他数据。全局常量和编译器数据的大小也可以在编译时刻确定。 一个动态管理的堆区 Heap。这个区存放程序运行时刻分配和释放的数据对象。Heap 的大小不能在编译时刻静态确定。 一个动态管理的栈区 Stack。这个区存放过程的活动记录。活动记录会随着过程的调用和返回被创建和消除。和堆区 - 样，栈区的大小也不能在编译时刻确定。 目标代码的形式 绝对地址的机器语言程序 可把目标代码放在内存中固定的地方、立即执行 可重定位的机器语言程序 .obj(DOS)、.o(UNIX) 开发灵活，允许各子模块单独编译 由连接装配程序将它们连接在一起，生成可执行文件 汇编语言程序 代码生成程序设计的相关问题。 基本块与流图 断句 如何划分基本块（考点）： 龙书说： 把中间代码划分成为基本块 (basic block)。每个基本块是满足下列条件的最大的连续三地址指令序列。 ①控制流只能从基本块中的第 - 一个指令进人该块。也就是说，没有跳转到基本块中间的转移指令。 ②除了基本块的最后一个指令，控制流在离开基本块之前不会停机或者跳转。 GOTO 后断。 GOTO 到的语句之前断。 GOTO 前不断后断。

掌握基本块优化技术，主要包括： 公共表达式的删除、复制传播、常数合并及常数传播、削弱计算强度等； 掌握循环优化技术，主要包括： 循环展开、代码外提、削弱计算强度、删除归纳变量； 概述 代码优化程序的任务 对中间代码或目标代码进行等价变换，使变换后的代码质量更高。 对代码优化程序的要求 等价变换 提高目标代码的执行速度 减少目标代码占用的空间 代码优化程序的位置 目标代码生成之前的中间代码优化 目标代码生成之后的目标代码优化 基本块优化 注意：不能轻易跨越基本块进行优化 如： i = 0 -------------- LOOP: i = i + 1 // 不能优化为 i = 1 ... if i < n goto LOOP 常数合并 计算常数表达式。$ x= 3*2+1 \Rightarrow x = 7$ 常数传播 常量作为值代入表达式 删除公共表达式 反复使用某个求值，而求值所依赖的变量状态皆未改变，则没必要反复求值，用第一次的即可。 复制传播 a = b, c = a，则后文实际上都可以用 b 来表示 a, c 删除死代码 求值后却没有使用的值 无法到达的块（如恒假条件里的块） 死块的后面很可能也是死块 削弱计算强度 例如 x = y**2 变成 x = y * y 例如 x = x + 0, x = 1 * x 可能是无意义的。 改变计算次序（没看懂有何意义） 循环优化 为循环语句生成的中间代码包括如下 4 部分：

(2) （1）三地址码： 1 i = 1 2 if i > m goto 17 3 j = 1 4 if j > n goto 15 5 t1 = i * n 6 t2 = t1 + j 7 t3 = t2 * 4 8 t4 = i * n 9 t5 = t4 + j 10 t6 = t5 * 4 11 t7 = b[t6] 12 a[t3] = t7 13 j = j + 1 14 goto 4 15 i = i + 1 16 goto 2 （2）

2000 https://www.docin.com/p-49445805.html 2009~2010 https://www.doc88.com/p-3147137767954.html?r=1 课后答案 https://www.doc88.com/p-1127198788108.html 基本技能 消除左递归 题型 LL (1) 语法分析 有如下文法 $G [S]$: $$ \begin{align} E & \to E + T \mid T \\ T & \to (E) \mid a \end{align} $$ (1) 判断该文法是否为 LL (1) 文法，说明原因。若不是， 做 (2)， 若是， 做 (3)。 (2) 是否可以将其改造为 LL（1）文法？ 如果可以，给出改造过程和结果，继续做（3）； 如果不可以，说明理由。 (3) 构造文法中非终结符号的 FIRST 和 FOLLOW 集合。 (4) 构造文法的 LL (1) 分析表。 （1）不是，因为有左递归 $E \to E + T$ 考虑文法 $G [S]$:

答：