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

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

《四川大学编译原理复习要点.docx》由会员分享，可在线阅读，更多相关《四川大学编译原理复习要点.docx（23页珍藏版）》请在冰点文库上搜索。

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

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

1、编译器各个阶段的功能，输入、输出，前端、后端

1） 词法分析：

将字符序列收集到称作记号（t o k e n）的有意义单元中

扫描程序　　输入：

源代码  输出：

记号

2） 　语法分析：

从扫描程序中获取记号形式的源代码，并完成定义程序结构的语法

分析，语法分析定义了程序的结构元素及其关系。

输入：

记号  输出：

语法树

3） 语义分析程序：

分析程序的静态语义， 包括声明和类型检查。

输入：

语法树  输出：

注释树

4） 源代码优化程序：

编译器通常包括许多代码改进或优化步骤。

绝大多数最早的优

化步骤是在语义分析之后完成的，而此时代码改进可能只依赖于源代码。

【对源代码进行优化，并产生中间代码】

　　  输入：

注释树输出：

中间代码

5） 目标代码生成：

得到中间代码，生成目标机器的代码

代码生成器  输入：

中间代码 输出：

目标代码

6） 目标代码优化程序：

编译器改进由代码生成器生成的目标代码。

输入：

目标代码输出：

目标代码

扫描程序、分析程序和语义分析程序是前端，代码生成器是后端，

前后端分开的好处：

可以给编译器带来更方便的可移植性，此时的编译器既能改变源代

码，又能改变目标代码。

【遍】编译器发现，在生成代码之前多次处理整个源程序很方便，这些重复就是遍。

首遍是从源中构造一个语法树或中间代码，在它之后的遍是由处理中间表示、向它增加信

息、更换结构或生成不同的表示组成

二、 解释器和编译器的区别 与联系？

读入源语言后，解释器和编译器都要进行词法分析、语法分析和语义分析，

之后，二者开始有所分别。

解释器在语义分析后选择了直接执行语句；编译器

在语义分析后选择将将语义存储成某一种中间语言，之后通过不同的后端翻译

成不同的机器语言（可执行程序）

编译器是把源语言（如 C,Pascal，java 等高级语言）转换为目标语言（汇编语言、机

器语言等低级语言），要产生目标代码。

解释器是以一个源语言（C，Pascal，java 等高级语言）为输入，一边解释一边执行源

程序，但不产生目标代码。

3、算法描述（伪代码）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 tomdo

for j:

=1 toi-1do

replace each grammer rule choice of the form Ai→Aj β by the rule

Ai→α1β|α2β|....| αkβ, where Aj→α1|α2|.....|αkis

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’→β|γ

5、first 集合 follow 集合 算法伪代码 P126P131

具体看书上的例子

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）中）

6、写递归下降子程序伪代码 　　　Ｐ１０６

递归下降：

将一个非终结符Ａ的文法规则看作将识别Ａ的一个过程的定义

一个 if 语句（简化了的）文法规则是：

if-stmt →if （exp） statement

|　if （exp） statement else statement

伪代码：

procedureifstmt；

begin

match （if）；

match（（）；

exp；

match （））；

statement；

iftoken　=　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;

7、上下文无关文法 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 → + | - | *

分析树与抽象语法树有什么不同？

对一个串按照某种文法进行推导的过程，可以用一颗树表示出来，这棵树

就是分析树。

分析树是表示记号串结构的一种十分有用的方法。

抽象语法树是真正的源代码记号序列的抽象表示，包含了转换所需的所有

信息，而且比分析树效率更高。

分析程序可以通过一个分析树表示所有步骤，但却通常只能构造出一个抽

象的语法树（或与它等同的）。

8、记号类型

1、保留字，如 IF 何 THEN，它们表示字符串“if”和“then”

2、特殊符号，如算数符号加（PLUS）和减（MINUS），它们表示“+”“— ”

3、表示多字符串的记号，如 NUM 和 ＩＤ，它们分别表示数字和标识符

9、语言、句子、句型

【语言】由推导从 exp 中得到的所有记号符号的串集是被表达式的文法定义的语言

【句型】从文法起始符号出发经过任意有限次推导出来的串

【句子】------------------------------------------------------------的只有终结符的串

10、自顶向下（第 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）简单

P153LR（0）项目的 DFA

自底向上的分析程序有两种可能的动作（除“接受”之外）：

1） 将终结符从输入的开头移进到栈的顶部。

2） 假设有B N F选择A→a，将栈顶部的串a归约为非终结符A。

11、综合题

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）的分析步骤