【编译原理】期末 龙书概念梳理+做题方法（混子保过指南+学霸提分秘籍）_编译原理 龙书

编译原理期末总结 龙书概念梳理+做题方法

---

编译概述

1 编译过程

1 词法分析 从左至右逐个字符的对源程序进行扫描 产生一个个单词符号 即把字符串形式的源程序改造为单词符号串形式的中间程序
2 语法分析 以单词符号串为基础 分析该串是否符合源语言的语法规则 并给出语法树
3 语义分析与中间代码生成 针对各类不同的语法范畴 按语言的语义规则进行语义分析（检查）和初步翻译工作 产生某种形式的中间代码（即一种结构简单、含义明确的记号系统）
4 代码优化 对前阶段产生的中间代码进行加工变换 以期在最后阶段能产生出高效（节省时、空）的目标代码 这一任务是由优化器来完成的
5 目标代码生成 把中间代码翻译成目标代码 如汇编代码或机器代码
这一过程涉及到内存管理 寄存器调度 指令选择等工作 因此与计算机系统的体系结构 CPU指令集 OS等密切相关

编译过程的前端和后端
前端： 主要由与源语言有关而与目标机无关的部分组成
包括词法分析 语法分析 语义分析和中间代码产生
与目标机无关的代码优化一般也包含在前端
后端： 主要由与目标机有关的部分组成 包括目标代码生成和与目标机有关的优化等

2 编译&解释

编译：将高级语言编写的源程序翻译成等价的机器语言或汇编语言
解释：将高级语言编写的源程序翻译一句执行一句 不生成目标文件 直接执行源代码文件
编译器：编译和运行分离
解释器：边解释边运行

编译和解释的根本区别：是否产生低级语言形式的目标程序

3 GCC的处理过程

---

词法分析

1 词法分析的任务

从左至右逐个字符地对源程序进行扫描 产生一个个单词符号
即把字符串形式的源程序改造为单词符号串形式的中间程序

词法分析工作由词法分析器完成，又称扫描器

2 词法分析器（Scnner 扫描器）的构造方法

3 词法分析器的工作原理

1 与语法分析器的连接

通常把词法分析器安排成语法分析器的一个子程序 而不是单独的一遍
当被调用时 词法分析器就从源程序字符串中识别出一个/一批单词符号
把它交给语法分析器去处理
语法分析器处理完毕 就开始下一次调用
如此重复 直至源程序处理完毕

2 输入&预处理

输入串一般放在一个缓冲区中 这个缓冲区称为：源程序输入缓冲区
但在许多情况下 把输入串预处理一下 对单词符号的识别工作将是比较方便的
预处理工作包括对空白符、跳格符、回车符和换行符等编辑性字符的处理及删除 注释等
于是 可以构造一个预处理子程序 它从源程序输入缓冲区读入字符串 预处理后
装入 扫描缓冲区 以备扫描器使用

3 扫描&输出

扫描器对扫描缓冲区进行扫描时 一般使用两个指示器
一个指向当前正在识别单词的开始位置（新单词的首字符）
另一个用于向前搜索以寻找单词的终点（新单词的尾字符）
但是不论扫描缓冲区设得多大 都不能保证单词符号不会被缓冲区的边界所打断
一个常用的技术是：把扫描缓冲区一分为二 并使两区首尾相接
形成一个 对半互补缓冲区
将识别出的单词符号交给语法翻译器
词法翻译器的工作就完成啦

4 正规表达式&正规集

相关基础知识
字母表（alphabet）
串（string）
串的连接：串的前后拼接
“幂”运算：串自身多次连接
空串：ε幺元（类似代数系统中乘法的1）
语言（language） ：串的集合
语言的运算
并：L∪M = {s| s∈Lor s∈M}
连接：LM = {st| s∈Land t∈M}
闭包（closure）：L*= ∪Lⁱ (i的取值从0到+∞)
正闭包：L+= ∪Lⁱ (i的取值从1到+∞)

正规表达式（Regular Expression）是说明单词的模式的一种重要的表示法（记号）
正规表达式所表示的所有的字符串的集合称为正规集（Regular Set）
设Σ为字母表
1 ε是Σ上的正规式 它所表示的正规集分别为{ε}
2 对于任何a∈Σ a都是Σ上的一个正规式 它所表示的正规集为{a}
3 假定U和V都是Σ上的正规式 它们所表示的正规集分别记为L(U)和L(V)
那么 (U|V)、(UV)和(U)也都是正规式 它们所表示的正规集分别为L(U)∪L(V), L(U)L(V)和(L(U))
即并集 连接和闭包
仅由有限次使用上述三步骤而得到的表达式才是Σ上的正规式RE（Regular Expression）
仅由这些正规式所表示的字集才是Σ上的正规集

正规表达式的运算顺序
括号> 闭包> 连接> 或

正规表达式的等价
若两个正规式所表示的正规集相同，则认为二者等价，记为‘=’

e.g. (a|b)*(aa|bb)(a|b)*对应的正规集是Σ上的所有含有两个相继的a或相继的b的字符串

5 确定的有穷状态自动机DFA

确定有限自动机（DFA）是—个五元式系统：
其中
DFA M＝( S，∑，δ，S0，F )
1 Ｓ是一个有限集 它的每个元素称为一个状态
2 ∑ 是一个有穷字母集 它的每个元素称为输入字符
3 δ 是一个从Ｓｘ ∑ -> S的单值部分映射
4 S0 属于S 是唯—的初态
5 Ｆ 属于S 是一个终态集（可空）

6 不确定的有穷状态自动机NFA

NFA M＝( S，∑，δ，S0，F )
1 Ｓ是一个有限集 它的每个元素称为一个状态
2 ∑ 是一个有穷字母集 它的每个元素称为输入字符
3 δ 是一个从Ｓｘ ∑* -> S的子集的映射 δ:S ｘ ∑* -> T（T属于S）
4 S0 属于S 是一个非空的初态集
5 Ｆ 属于S 是一个终态集（可空）

NFA的不确定性表现在
1 多值映射
2 带空转移

词法分析题型

需求转化为RL
RL转化为NFA
NFA的确定化
DFA的最小化

---

语法分析

相关基础知识
“=>”读作“推导出”或“派生出”。
“::=”/“→”读作“定义为”或 “由…组成”
“|”表示“或”
每一条规则被称作产生式或重写式

1 语法分析基础

1.1 高级语言的语法描述目的

为高级程序设计语言的语法规则寻求形式化的工具

1.2 语言

由文法G生成的语言记为L(G),它是文法G的所有句子的集合：
L(G)={x|S =>+x S为开始符号 且x ∈VT*}

语言研究的三个方面
语法(Syntax) – 表示构成语言句子的各个记号
（如： 单词，短语，固定搭配等）之间的组合规则
语义(Semantics) – 表示各个记号的特定含义
（各个记号和记号所表示的对象之间的关系）
语用(Pragmatics) --表示在各个记号所出现的行为中
它们的来源、使用和影响

e,g.
文法G[S]：S→0S1，S→01
L(G)={0ⁿ 1ⁿ|n≥1}

1.3 形式语言&文法定义

如果不考虑语义和语用 即只从语法这一侧面来看语言 这种意义下的语言称作形式语言
形式语言被抽象地定义为一个数学系统 该数学系统称为文法

1.4 上下文无关文法及其语言

上下文无关文法G定义为一个四元式(VN VT S P)
其中：
1 VN 为非终结符号的非空有穷集
2 VT 为终结符号的非空有穷集 VN ∩ VT = Ф
VN ∪ VT中的符号统称为文法符号
3 P 为产生式的集合 产生式也称重写式/生成式
形如A→α 其中： A ∈ VN α∈(VN ∪VT)*
A称为产生式的左部 α称作产生式的右部
4 S 称作识别符号或开始符号 S∈ VN
且至少要在一条产生式中作为左部出现

上下文无关文法不能完整地表述自然语言 但对程序设计语言来说
大多数语法结构都可以用上下文无关文法CFG（Context-Free Grammar）来准确表述

1.5 推导&归约

直接推导
A→γ是文法G的产生式 若有v,w满足：
v=αAβ w=αγβ 其中α,β∈(VN∪VT)*
则称v直接推导出w 记作v=>w
也称w直接归约到v 就是说归约是推导的逆过程
推导
若存在v =w0=>w1=>… =>wn= w, (n>0) 则记为
v =>+w 读作v推导出w 或者反过来说w归约到v
若有v=>+w 或v=w 则记为v=>*w

1.6 句子&句型

句型：有文法G 若S =>x x∈(VN∪VT) 则称x是文法G的句型
句子：有文法G 若S =>* x 且x∈VT* 则称x是文法G的句子
句子一定是句型 句型不一定是句子
e.g.
G：S→0S1，S→01
S =>0S1 =>00S11 =>000S111 =>00001111
句型:S 0S1 00S11 000S111 00001111
句子:00001111

1.7 文法的等价性

若L(G1)=L(G2) 则称文法G1和G2是等价的

1.8 文法的二义性

语法树
一个句型推导过程的树形表示称为语法分析树 简称语法树
从左到右读出叶子的标记而构成的串是句型
文法的二义性
若一个文法存在某个句子对于两棵不同的语法树
（两个不同的最左或最右推导） 则称这个文法是二义的
二义性问题的不可判定性
不能设计一个算法 在有穷的步骤内确切地判定一个文法是否为二义性的
因此 我们所能做的工作只能是为二义性寻找一组充分（而非必要）条件来改造二义性文法

文法的二义性不等于语言的二义性
原因是可能有两个不同的文法G和G‘ L(G)= L(G’) 其中G是二义性的 G’是无二义性的
e.g.
G[E]:E→E+E∣EE∣(E)∣i
G[E‘]:
E→T∣E+T
T→F∣TF
F→i∣(E)
G[E]是二义性的 G[E‘]是无二义的

1.9 文法的分类

①若文法G=(VN ,VT ,S,P ) 的每个产生式α→β满足：
α∈(VN∪VT)+ 且至少含有一个非终结符，
β∈(VN∪VT)* 则该文法称为0型文法 PSG-短语文法
②若0型文法G的任何产生式α→β 都有|β|≥|α|
（但 α→ε例外） 则该文法称为1型文法 CSG-上下文有关文法
③若文法G的任何产生式α→β 都有α∈VN
β∈(VN∪VT)* 则该文法称为2型文法 CFG-上下文无关文法
④若文法G的任何产生式的形式都为A→αB或A→α
其中A,B∈VN α∈VT * 则该文法称为3型文法 RG-正规文法

2 语法分析的功能

以单词符号串为基础 分析该串是否符合源语言的语法规则 并给出语法树

3 语法分析的分析方法

3.1自上而下语法分析（自顶向下）

3.1.1 自上而下语法分析的思想

从文法开始符号出发 自上而下地构造语法树
每一次都选取一个标记为非终结符的树结点作为父亲结点
用该非终结符对应的产生式右部符号构造孩子结点
然后重复这一过程 直至不再有新的树结点产生为止
显然 这一过程应该与一个最左推导相对应

3.1.2 自上而下语法分析的特点

自上而下 自左而右 最左推导

3.1.3 自上而下语法分析存在的问题

左递归问题 文法G 存在U∈VN 且U =>* U… 则G为左递归文法
解决方法 改写产生式 变左递归为右递归

左递归分类
直接左递归 直接变换
间接左递归 代入

回溯问题 走了一大段错误路径 不得不推倒重来
原因 父亲结点生成孩子结点时的盲目性
解决方法
提取公共左因子
使所有候选式的First集两两不相交

3.1.4 自上而下语法分析对文法的要求

文法无二义
有二义性 就改造之
文法没有左递归
有左递归 就变为右递归

对文法的任一非终结符 若其规则右部有多个选择
则各选择所推导出的终结符号串的首符号集合必须两两不相交
有交集 就提取公共左因子

符合上述条件的上下文无关文法就可以用于自上而下的语法分析

3.1.5 自上而下语法分析的分析方法

递归下降分析

概念
由一组递归函数或过程组成 每个函数或过程对应文法的一个非终结符的程序
称为递归下降分析器

基本思路
1 当遇到终结符a时 编写语句：if(当前读来的输入符号==’a’) 读入下一个输入符号
2 当遇到非终结符A时 则编写语句调用A()
3 当遇到A→ε产生式规则时 则编写语句：if(当前读来的输入符号∉Follow(A)) error();
4 当某个非终结符有多个候选产生式规则时 分两种情况处理：
if(当前读来的输入符号∈First(αi)) 按照规则A→αi进行推导
if(当前读来的输入符号∈Follow(A)且αi ⇒* ε) 按照规则A→αi进行推导

递归子程序法的优点
程序结构层次清晰，易于实现
递归子程序法的缺点
对文法有要求 适用范围受限
只有所使用的高级语言具有实现递归过程的编译系统时才有实际意义
程序运行速度慢 占用内存空间多 效率不高

非递归的预测分析 - LL(1)文法
#和文法开始符号进栈 从输入缓冲区读进输入符号a 弹出栈顶元素给X：
1 若X=a=’#’ 则分析器工作结束 分析成功
2 若X=a≠‘#’ 则分析器把X从栈顶弹出 让输入指针指向下一个输入符号
3 若X是一个非终结符号 则查阅预测分析表M
若在M[X,a]中存放着关于X的一个产生式规则 则先把X弹出
再把产生式规则右部符号串按逆序-压入栈中
若M[X,a]={X→ε} 则预测分析器把在栈顶的X弹出
若M[X,a]=error 则调用出错处理程序

通常把分析表不含多重定义入口的文法称为 LL(1) 文法
第一个L代表从左到右扫描输入串
第二个L代表产生最左推导
1代表在决定语法分析器的每步动作时向前看1个输入符号即可

3.1.6 LL(1) 文法

First集
设G[Z]=(VN，VT，P，Z)，α∈(VN∪VT)* 符号串α的首符号集合的定义为：
First(α)={a|α ⇒* a…且a∈VT}
若α ⇒* ε 则规定ε∈First(α)
Follow集
设G[Z]=(VN，VT，P，Z)，A∈VN，非终结符号A的后继符号集合的定义为：
Follow(A)={a|Z ⇒* …Aa…且a∈VT}
若Z ⇒* …A 则规定#∈First(A)

*** 判断是否为LL(1) 文法***
1 文法不含左递归
2 对于每个非终结符A的各个候选式的终结首符号集两两不相交 即A→α1|α2|…|αn 则First(αi)∩First(αj)=Ø(1≤i,j≤n且i≠j)
3 对于文法中每个非终结符A 若它的某个候选式的终结首符号集包含ε 则First(αi)∩Follow(A)=Ø(1≤i≤n)

3.2 自下而上语法分析（自底向上）

3.2.1 自下而上语法分析的思想

从单词符号串形式的源程序开始 自下而上地构造语法树
每取一个单词 就构造一个新的树结点 将其作为一个新子树的树根
查看所有已有的子树的树根标记
若能规约到一个产生式的左部符号 则以这些树根为孩子结点
构造其父亲结点 并以产生式左部符号为标记
从而得到一个新的子树
若不能规约 就再取一个单词 重复上述过程直至所有子树合并为一颗树
且树根标记为文法开始符号

3.2.2 自下而上语法分析的特点

自下而上 自左而右 最左归约

3.2.3 短语 直接短语 句柄

短语
若存在Z ⇒+ αAδ且A ⇒+ β 则称β是句型αβδ相对于非终结符A的短语
直接短语
若存在Z ⇒+ αAδ且A⇒β 则称β是句型αβδ相对于产生式规则A→β的直接短语
句柄
一个句型的最左直接短语称为该句型的句柄

3.2.4 规范推导 规范归约

1 最左推导 对一个推导序列中的每一步直接推导α⇒β
都是对α中的最左非终结符进行替换
2 最右推导(规范推导) 对一个推导序列中的每一步直接推导α⇒β
都是对α中的最右非终结符进行替换
最右推导也称为规范推导，所得句型称为规范句型
3 最左归约(规范归约) 规范推导的逆过程
4 最右归约 最左推导的逆过程

3.2.5 LR分析法

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

LR分析表
LR分析器的核心是一张分析表
这张表包括两部分 “动作”(Action)和“状态转换”(Goto) 它们都是二维数组 Action[s,a]规定了状态s面临输入符号a时应该采取什么动作
Goto[s,X]则指出状态面对文法符号X（终结符或非终结符）时下一状态是什么
实际上 Goto[s,X]定义了一个以文法符号为字母表的DFA

动作
Action[s,a]所规定的动作是下述四种可能之一：
a.移进 把(s,a)的下一状态s’=Goto[s,a]和输入符号a推进栈
下一输入符号变成现行输入符号
b.归约 指用某一产生式A→β进行归约
若|β|＝r 则把栈顶r个项托出 栈顶状态变成sm-r
然后把(sm-r,A)的下一状态s’=Goto[sm-r,A]和A进栈
归约动作不改变现行输入符号
这意味着Xm-r+1 …Xm=β是一个相对于A的句柄
c.接受 宣布分析成功 停止分析器的工作
d.报错 报告发现错误 调用出错处理程序

LR分析器的工作过程
一个LR分析器的工作过程可以看成是栈里的状态序列
已归约串和输入串所构成的三元式的变化过程：
初始三元式 (s0, #, a1a2…an#)
中间三元式 (s0s1…sm, #X1X2…Xm, aiai+1…an#)
接受 (s0sk,#X,#) (X为开始符号，而Action[sk,#] 为接收)
分析器的下一步动作完全由sm和ai唯一决定 即执 行Action[sm,ai]

LR文法
对于一个文法 如果能够构造出一张分析表
使得它的每个入口均是唯一的 则称该文法为LR文法

LR(k)文法
一个LR分析器有时需要“展望”未来的k个输入符号才能
决定应采取什么样的“移进－归约”决策
于是又有如下定义:
对于文法G 若能用一个每步顶多向前查看k个输入符号的LR 分析器进行分析 则称之为LR(k)文法
但是对大多数的程序语言来说 k≤1就足够了
因此 我们只研究LR(0)和LR(1)

语法分析题型

文法的转换
消除左递归
消除回溯
画语法树 最左最右推导
求解First Follow集 画预测分析表 写出预测分析过程
短语 直接短语 句柄

---

属性文法&语法制导翻译

1 属性文法

1.1 属性文法的概念

属性文法是在上下文无关文法的基础上为每个文法符号（终结符或非终结符）配备若干个相关的“值”（称为属性）

1.2属性文法的分类

综合属性 用于“自下而上”传递信息
继承属性 用于“自上而下”传递信息

综合属性

在语法树中 一个结点的综合属性的值由其子结点或其自身的某些属性值确定
通常使用自下而上的方法在每一个结点处使用语义规则计算综合属性的值
仅仅使用综合属性的属性文法称 S-属性文法

继承属性

在语法树中 一个结点的继承属性值由该结点的父结点 兄弟结点和其自身的某些属性值确定
通常用继承属性来表示程序语言结构中的上下文依赖关系

ps.
终结符只有综合属性 由词法分析器提供
非终结符既可以有综合属性也可以有继承属性
文法开始符号的所有继承属性作为属性计算前的初始值

1.3 良定义的属性文法

属性之间不存在循环依赖关系的属性文法称为良定义的属性文法
这类文法的依赖图是有向无环图

1.4 基于属性文法的处理方法

基础文法用于构造输入符号串的语法分析树
在此基础之上 根据属性间的依赖关系建立依赖图
再按照图的某一种拓扑排序来遍历语法树 遍历的同时使用语义规则进行处理

输入串⇒语法树⇒依赖图⇒拓扑序⇒遍历语法树

1.5 S-属性文法

只含有综合属性的属性文法

1.6 L-属性文法

如果对于每个产生式A→X1X2…Xn的每个语义规则中 每个属性或者是综合属性
或者是Xj(1≤j≤n)的一个继承属性且这个继承属性仅依赖于
1 产生式Xj的左边符号X1,X2,…Xj-1的属性
2 A的继承属性

L-属性文法也就是“左属性”文法 计算每一个继承属性时不能引用右边符号的属性
也就是说 在这类属性文法的依赖图中 不能有从右到左的边
由此定义可知 S属性文法一定是L属性文法

2 语法制导定义SDD

语法制导定义(Syntax-Directed Definition)把：
①每个文法符号和一个属性（attribute）集合相关联
②每个产生式和一组语义规则（semantic rules）相关联 这些规则用于计算与该产生式中符号相关联的属性值

3 语法制导翻译SDT

由源程序的语法结构所驱动的基于属性文法的处理办法

工具-依赖图

依赖图(Dependency Graph)描述了语法树中结点属性之间的相互依赖关系
依赖图是一个有向图 在图中为每一个属性设置一个结点
如果属性b依赖属性c 则从属性c的结点有一条有向边连到属性b的结点

---

语义分析

1 语义分析的任务

审查每一个语法结构的静态语义 即验证语法正确的结构是否有意义

2 语义规则

属性传递和计算的过程即是语义处理的过程
其相应的规则就称为语义规则

3 语义分析的方法

后缀表达式
图表示法
三地址代码
四元式
三元式

---

运行时存储空间组织

1 活动

活动的含义

一个过程的活动指的是该过程的一次执行

活动的生存期

过程P一个活动的生存期 指的是从执行该过程的第一步操作到最后一步操作之间的操作序列 包括执行P时调用其他过程花费的时间

2 存储分配策略

运行时的存储空间组织基本使用三种分配策略：

2.1 静态分配策略

在编译时对所有对象分配固定的存储单元 且在运行时保持不变

2.2 栈式动态分配策略

在运行时把存储器作为一个栈进行管理
每当调用一个过程 它所需要的存储空间就动态地分配于栈顶
调用完毕 它所占空间就予以释放

2.3 堆式动态存储策略

在运行时把存储器组织成堆结构 以方便用户对存储空间的申请与归还（分配与回收）

3 存储组织

4 存储空间的栈式分配

活动记录

编译程序使用一个连续的存储块来管理过程在一次执行中所需要的所有信息

当某个过程被调用时 就在栈顶创建该过程对应的活动记录
当该过程运行完毕 就将其活动记录从栈顶撤销

活动记录包含

连接数据
返回地址 执行call指令时程序计数器的值
动态链（控制链） 指向调用该过程前的最新活动纪录的指针
运行时 运行栈上各数据区按动态建立的次序结成链 链头在栈顶
静态链（访问链） 指向静态直接外层的活动纪录的指针 用来访问非局部数据
形式单元
存放相应的实在参数的地址或值
局部数据区
局部变量、内情向量、临时工作单元（例如表达式求值的中间结果）

C语言的活动记录

C语言的特点是：不含分程序结构 过程定义不允许嵌套 但允许过程的递归调用
并且活动记录简化为：

C的非局部数据：全局变量 全部放入静态数据区即可

---

优化技术

代码外提
删除公共子表达式
强度削弱
删除归纳变量
合并已知量
复写传播
删除无用代码

---

常见概念辨析题

辨析DFA和NFA的异同
辨析自上而下语法分析和自下而上语法分析的异同
比较栈和堆
常见的优化方法