四川大学编译原理复习要点.doc

四川大学 编译原理复习要点 2013版

一、 编译器各个阶段的功能，输入、输出，前端、后端
1） 词法分析：将字符序列收集到称作记号(t o k e n）的有意义单元中
扫描程序　　输入：源代码 输出：记号
2） 　语法分析：从扫描程序中获取记号形式的源代码，并完成定义程序结构的语法分析，语法分析定义了程序的结构元素及其关系。
输入：记号 输出：语法树
3） 语义分析程序：分析程序的静态语义， 包括声明和类型检查。
输入：语法树 输出：注释树
4） 源代码优化程序：编译器通常包括许多代码改进或优化步骤。绝大多数最早的优化步骤是在语义分析之后完成的，而此时代码改进可能只依赖于源代码。
【对源代码进行优化，并产生中间代码】
　　 输入：注释树 输出：中间代码
5） 目标代码生成：得到中间代码，生成目标机器的代码
代码生成器 输入：中间代码 输出：目标代码
6） 目标代码优化程序：编译器改进由代码生成器生成的目标代码。
输入：目标代码 输出：目标代码
扫描程序、分析程序和语义分析程序是前端，代码生成器是后端，
前后端分开的好处：可以给编译器带来更方便的可移植性，此时的编译器既能改变源代码，又能改变目标代码。
【遍】编译器发现，在生成代码之前多次处理整个源程序很方便，这些重复就是遍。首遍是从源中构造一个语法树或中间代码，在它之后的遍是由处理中间表示、向它增加信息、更换结构或生成不同的表示组成

二、 解释器和编译器的区别 与联系？ 
读入源语言后，解释器和编译器都要进行词法分析、语法分析和语义分析，之后，二者开始有所分别。解释器在语义分析后选择了直接执行语句；编译器在语义分析后选择将将语义存储成某一种中间语言，之后通过不同的后端翻译成不同的机器语言（可执行程序）
编译器是把源语言（如C,Pascal，java等高级语言）转换为目标语言（汇编语言、机器语言等低级语言），要产生目标代码。
解释器是以一个源语言（C，Pascal，java等高级语言）为输入，一边解释一边执行源程序，但不产生目标代码。

三、 算法描述（伪代码）p41
构造一个扫描程序的自动过程：正则表达式→NFA→DFA→程序
1、 正则表达式→NFA
（1） 建立字母表。输入的正则表达式由于一般不输入“与”操作符，因此
首先给表达式加入 .作为与操作。再利用逆波兰式的堆栈操作，把操作符与字母分开，便得到了字母表。 
（2） Thompson构造法。首先将构成正则表达式的各个元素分解，对于每
一个元素，按照下述规则1和规则2生成NFA。 注意：如果r中记号a出现了多次，那么对于a的每次出现都需要生成一个单独的NFA。
2、 NFA→DFA
从单个输入字符的某个状态中去除ε-转换和多重转换。
（1）利用ε-closure规则即闭包规则，把NFA状态划分成集合，而后把每个集合作为DFA的状态。
详细描述：从NFA的状态S开始经过ε到达的状态存储下，然后再把存储结果中的状态有经过ε到达的新状态也存储在一起，这样通过闭包规则就可以这些集合，再把集合作为DFA的状态。
（2）子集构造
3、 DFA→程序 DFA状态最小化
取出DFA状态中的不可达的状态。
构造最小状态的等价DFA的算法是通过创建统一到单个状态的状态集来进行。
构造NFA（使用Thompson结构）:
1) 基本正则表达式 基本正则表达式格式a或ε，其中a表示字母表中单个字符的匹配，
ε表示空串的匹配。与正则表达式a等同的N FA（即在其语言中准确接受）的是：

与ε等同的N FA是：

2) 并置 我们希望构造一个与正则表达式r s等同的N FA，其中r 和s 都是正则表达式。可将与rs 对应的N FA构造如下：

3) 在各选项中选择 我们希望在与前面相同的假设下构造一个与r | s 相对应的N FA。如下进行：

4) 重复 我们需要构造与r *相对应的机器，现假设已有一台与r 相对应的机器。那么就如下进行：

构造NFA的一个例子：
例：根据Thompson 结构将正则表达式a b | a 翻译为N FA。首先为正则表达式a 和b 分别构造机器：

接着再为并置a b 构造机器：

现在再为a 构造另一个机器复件，并利用它们组成a b | a 完整的N FA，如下图：

将NFA转换成DFA（最小子集法）：
ε- 闭包（ε - c l o s u r e）是可由ε转换从某状态或某些状态达到的所有状态集合，它总是包含状态本身
子集构造　　　　相关题目：2.1，2.12，2.16

四、提左因子和消除左递归
1、在建立LL(1)语法分析器的时候，提左因子和消除左递归的目的、原因 
目的：提取左因子---避免程序回溯；
消除左递归---消除无限循环
原因：当有公因子存在时，不能立即区分出文法规则右边的选择；
当有左递归时，将导致一个无限循环。

2、提左因子和消除左递归的算法描述
消除左递归 伪代码 P119
for i:=1 to m do
for j:=1 to i-1 do
replace each grammer rule choice of the form Ai→Aj β by the rule
Ai→α1β|α2β|....| αkβ, where Aj→α1|α2|.....|αk is
the current rule for Aj
remove,if necessary,immediate left recursion involving Ai
a)把直接左递归改写为右递归 【简单直接左递归】
设有文法产生式：A→Aβ|γ。其中β非空，γ不以A打头。
可写为：A→γA'
A'→βA'|ε
一般情况下，假定关于A的产生式是【普遍的直接左递归】
A→Aα1| Aα2 |… |Aαm|β1|β2 |…|βn
其中，αi(1≤i≤m)均不为空，βj(1≤j≤n)均不以A打头。
则消除直接左递归后改写为：
A→ β1A'| β2 A' |…| βnA'
A'→ α1A' | α2A' |…| αmA' |ε

例4.12：有文法G(E)：
E→E +T |T
T→T*F | F
F→i| (E)
消除该文法的直接左递归。
解：按转换规则,可得:
E→TE'
E'→+TE'|ε
T→FT '
T'→*FT'|ε
F→i| (E)

b)消除间接左递归 【一般的左递归，不带有ε产生式且不带有循环的文法】
对于间接左递归的消除需要先将间接左递归变为直接左递归，然后再按a)清除左递归。
例4.13：以文法G6为例消除左递归：
(1)A→aB
(2)A→Bb
(3)B→Ac
(4)B→d
解：用产生式(1)，(2)的右部代替产生式(3)中的非终结A得到左部为B的产生式：
(1)B→aBc
(2)B→Bbc
(3)B→d
消除左递归后得到：
B→aBcB' |dB'
B'→bcB' |ε
再把原来其余的产生式A→aB,A→Bb加入，最终得到等价文法为:
(1) A→aB
(2) A→Bb
(3) B→(aBc|d)B'
(4) B'→bcB'|ε

c)消除文法中一切左递归的算法
设非终结符按某种规则排序为A1，A2，…，An。
For i﹕=1 to n do
begin
For j﹕=1 to i-1 do
begin
若Aj的所有产生式为：
Aj →δ1| δ2 | … | δn
替换形如Ai → Aj γ的产生式为：
Ai →δ1γ |δ2γ | … |δnγ
end
消除Ai中的一切直接左递归
end

提取左因子 伪代码 P122
当两个或更多文法规则选择共享一个通用前缀时，需要提取左因子：
A→αβ|αγ
按如下规则提取左因子：
A→αA’
A’→β|γ

五、 first 集合 follow 集合 算法 伪代码P126 P131
具体看书上的例子
First集合求法：
1. 直接收取：对形如U－a…的产生式（其中a是终结符），把a收入到First(U)中
2. 反复传送：对形入U－P…的产生式（其中P是非终结符），应把First(P)中的全部内容传送到First(U)中。
Follow集合求法：
1. 直接收取：注意产生式右部的每一个形如“…Ua…”的组合，把a直接收入到Follow(U)中。
2．直接收取：对形如“…UP…”(P是非终结符)的组合，把First(P)除ε直接收入到Follow(U)中。
3．反复传送：对形如P－…U的产生式（其中U是非终结符），应把Follow(P)中的全部内容传送到Follow(U)中。(或 P－…UB且First(B)包含ε，则把First(B)除ε直接收入到Follow(U)中，并把Follow(P)中的全部内容传送到Follow(U)中)

六、 写递归下降子程序伪代码 　　　Ｐ１０６
递归下降：将一个非终结符Ａ的文法规则看作将识别Ａ的一个过程的定义
一个if语句（简化了的）文法规则是：

if-stmt →if (exp) statement
|　if (exp) statement else statement
伪代码：
procedure ifstmt；
begin
match （if）；
match （（）；
exp；
match （））；
statement；
if token　=　else then
match（else）；
statement；
end if；
end ifstmt；
给出基于DFA进行词法分析的表驱动的实现算法 p44
state:=1;ch:=next input character;
while not accept[state] and not error(state) do
new state:=T[state,ch]；
if advance[state,ch] then ch:=next input chracter;
State：=newstate；
end while;
if accept[state] then accpet;

七、 上下文无关文法 BNF EBNF　最左最右推导
1、定义 ：上下文无关文法G是一个四元组G = (N，T，P，S)，其中 
™ N是非终结符的有限集合； 
™ T是终结符或单词的有限集合，它与N不相交； 
™ P是形如A →α的产生式的有限集合，其中A∈N,α∈V﹡,V=T∪N 
™ S是N中的区分符号，称为开始符号或句子符号。V中的符号称为文法符号，包括终结符和非终结符。 

2、 Backus-Naur符号（就是众所周知的BNF或Backus-Naur Form）是描述语言的形式化的数学方法，由John Backus (也许是Peter Naur)开发，用于描述Algol 60编程语言的语法。

3、EBNF（扩展的BNF）使用花括号{…}表示重复，方括号[...]表示可选
EBNF中注意重复和可选的表示方法，语法图【可视的表示EBNF规则的图形表示法】

上下文无关文法说明程序设计语言的语法结构，利用了与正则表达式中极为类似的命名惯例和运算。
二者的主要区别在于上下文无关文法的规则是递归的（recursive）

最左推导（ leftmost derivation）是指它的每一步中最左的非终结符都要被替换的推导
最右推导（ rightmost derivation）则是指它的每一步中最右的非终结符都要被替换的推导。最左推导和与其相关的分析树的内部节点的前序编号相对应；最右推导则和后序编号相对应

最右推导的一个例子：
文法规则：exp → exp op exp | (e x p) | n u m b e r
op → + | - | *

分析树与抽象语法树有什么不同？  
对一个串按照某种文法进行推导的过程，可以用一颗树表示出来，这棵树就是分析树。分析树是表示记号串结构的一种十分有用的方法。
抽象语法树是真正的源代码记号序列的抽象表示，包含了转换所需的所有信息，而且比分析树效率更高。
分析程序可以通过一个分析树表示所有步骤，但却通常只能构造出一个抽象的语法树（或与它等同的）。

八、 记号类型
1、 保留字，如IF何THEN，它们表示字符串“if”和“then”
2、 特殊符号，如算数符号加（PLUS）和减（MINUS），它们表示“+”“— ”
3、 表示多字符串的记号，如 NUM 和 ＩＤ，它们分别表示数字和标识符

九、 语言、句子、句型
【语言】由推导从exp中得到的所有记号符号的串集是被表达式的文法定义的语言
【句型】从文法起始符号出发经过任意有限次推导出来的串
【句子】------------------------------------------------------------的只有终结符的串

十、 自顶向下（第4章） 自底向上（第5章）
区别：
自顶向下语法分析：从文法的开始符号出发，从顶部开始构造语法分析树。
自底向上语法分析：从构成语法分析树的叶子节点的终结符号串开始，从底部开始构造语法分析树。
1、自顶向下的分析算法通过在最左推导中描述出各步骤来分析记号串输入
从文法的开始符号出发，从顶部开始构造语法分析树。
自顶向下的分析程序有两类：回溯分析程序、预测分析程序。
两类自顶向下分析的算法：递归下降分析、LL（1）分析。
LL(1)：第一个L指的是由左向右的处理输入，第2个L指的是为输入串描绘一个最左推导，括号里的1表示仅使用输入中的一个符号来预测分析的方向。
P106-112递归下降：将一个非终结符Ａ的文法规则看作将识别Ａ的一个过程的定义
First集合 follow集合
LL(1)文法的判断 及分析表

2、自底向上语法分析：从构成语法分析树的叶子节点的终结符号串开始，从底部开始构造语法分析树。
自底向上分析法也称移进-规约分析法。
思想：对输入串自左向右进行扫描，并将输入符逐个移入栈中，边移入边分析，一旦栈顶符号形成某个句型的句柄或可规约串时，就用产生式左部的非终结符代替之；这称为一步规约。

最普通的自底向上算法称作LR(1)分析：L表示自左向右处理输入，R表示生成了最右推导
SLR（1）分析是对LR（1）分析的改进
LALR（1）比SLR（1）略微强大 且 比一般的LR（1）简单

P153 LR（0）项目的 DFA

自底向上的分析程序有两种可能的动作(除“接受”之外)：
1) 将终结符从输入的开头移进到栈的顶部。
2) 假设有B N F选择A→a，将栈顶部的串a归约为非终结符A。

十一、 综合题
1、 编写正则表达式
2、 给定程序，最左、最右推导，画分析树和抽象语法树
3、 正则表达式，NFA，DFA之间的转换；DFA最小化;DFA用伪代码表示出来。
4、 二义性文法　可生成带有两个不同分析树的串的文法称作二义性文法
改二义性文法：基本步骤：把出现二义的部分优先级分块。
然后每个优先级用一个新的VN表示。
最底优先级的VN符号要能由VT符号定义如：A→…|a

5、 给定文法写递归下降分析，写DFA表驱动算法
6、 给定文法，提取左因子，消除左递归；
构造first、follow集合；
说明语法是否为LL（1）：
若满足以下条件，则BNF中的文法就是LL（1）文法：
1) 在每个产生式A→X1| X2|....|Xn中
对于所有的i和j： 1≦i,j≦n.i≠j,first(Xi)∩first(Xj）为空；
2)若对于每个非终结符A都有first(A)包含了ε，那么first(A)∩follow(A)为空

构造LL（1）分析表；
写出分析过程

7、 给定文法，构造LR(0)项目的DFA；
构造SLR(1)的分析表；
文法是否为SLR(1)或LR(0)?若不是，说明原因；
给出SLR(1)或LR(0)的分析步骤