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

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

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

1）词法分析：将字符序列收集到称作记号（token）的有意义单元中

扫描程序输入：源代码输出：记号

2）语法分析：从扫描程序中获取记号形式的源代码，并完成定义程序结构的语法分析，语法分析定义了程序的结构元素及其关系。

输入：记号输出：语法树

3）语义分析程序：分析程序的静态语义，包括声明和类型检查。输入：语法树输出：注释树

4）源代码优化程序：编译器通常包括许多代码改进或优化步骤。绝大多数最早的优化步骤是在语义分析之后完成的，而此时代码改进可能只依赖于源代码。

【对源代码进行优化，并产生中间代码】输入：注释树输出：中间代码

5）目标代码生成：得到中间代码，生成目标机器的代码代码生成器输入：中间代码输出：目标代码

6）目标代码优化程序：编译器改进由代码生成器生成的目标代码。

输入：目标代码输出：目标代码

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

前后端分开的好处：可以给编译器带来更方便的可移植性，此时的编译器既能改变源代码，又能改变目标代码。

【遍】编译器发现，在生成代码之前多次处理整个源程序很方便，这些重复就是遍。首遍是从源中构造一个语法树或中间代码，在它之后的遍是由处理中间表示、向它增加信息、更换结构或生成不同的表示组成

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

读入源语言后，解释器和编译器都要进行词法分析、语法分析和语义分析, 之后，二者开始有所分别。解释器在语义分析后选择了直接执行语句；编译器在语义分析后选择将将语义存储成某一种中间语言，之后通过不同的后端翻译成不同的机器语言（可执行程序）

编译器是把源语言（如C,Pascal，java等高级语言）转换为目标语言（汇编语言、机器语言等低级语言），要产生目标代码。

解释器是以一个源语言（C，Pascal, java等高级语言）为输入，一边解释一边执行源程序，但不产生目标代码。

3、算法描述（伪代码）p41

构造一个扫描程序的自动过程：正则表达式T NFA T DFA T程序

1、正则表达式T NFA

（1）建立字母表。输入的正则表达式由于一般不输入“与”操作符，因此

首先给表达式加入?作为与操作。再利用逆波兰式的堆栈操作，把操作符与字母分开，便得到了字母表。（2）T hompson构造法。首先将构成正则表达式的各个元素分解，对于每

一个元素，按照下述规则 1和规则2生成NFA。注意：如果r中记号a出现了多次，那么对于a的每次出现都需要生成一个单独的NFA。

2、NFA T DFA

从单个输入字符的某个状态中去除￡ -转换和多重转换。

（1）利用￡ -closure规则即闭包规则，把 NFA状态划分成集合，而后把每个集合作为DFA的状态。

详细描述：从NFA的状态S开始经过￡到达的状态存储下，然后再把存储结果中的状态有经过￡到达的新状态也存储在一起，这样通过闭包规则就可以这些集合，再把集合作为DFA的状态。

（2）子集构造

3、 DFA T程序DFA状态最小化取出DFA状态中的不可达的状态。

构造最小状态的等价 DFA的算法是通过创建统一到单个状态的状态集来进行。

构造NFA（使用Thompson结构）：

1）基本正则表达式基本正则表达式格式 a或￡，其中a表示字母表中单个字符的匹配，￡表示空串的匹配。与正则表达式 a等同的NFA （即在其语言中准确接受）的是:

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 分别构造机

器：

将NFA 转换成DFA （最小子集法）：

& -闭包（& -closure ）是可由e 转换从某状态或某些状态达到的所有状态集合

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

:

图

: 现在再为a 构造另一个机器复件，并利用它们组成

a b | a 完整的N FA ，如下

|r - 2-6 11 I I'llionipsoti

L : hl 」：| F -'!0 ab a

它总是包含状态本身

子集构造 相关题目：2.1 , 2.12 , 2.16

四、提左因子和消除左递归

1、在建立LL ⑴ 语法分析器的时候，提左因子和消除左递归的目的、原因 目的：提取左因子---避免程序回溯；

消除左递归---消除无限循环

原因：当有公因子存在时，不能立即区分出文法规则右边的选择; 当有左递归时，将导致一个无限循环。 2、提左因子和消除左递归的算法描述 消除左递归 伪代码 P119

for i:=1 to m do

for j:=1 to i-1 do

replaceeachgrammerrule choice of theform Ai —Aj 3 by the rule

Ai — a 13 | a 2 3 |....| a k 3 , where Aj — a 1| a 2| | a k is

thecurrent rule for Aj

remove,if necessary,immediateeft recursioninvolving Ai

E'T +TE'| ￡

L FT' T'T *FT'| ￡ F T i| (E)

b) 消除间接左递归 【一般的左递归，不带有&产生式且不带有循环的文法】

对于间接左递归的消除需要先将间接左递归变为直接左递归，然后再按

a)清除左递归。 例4.13 :以文法G6为例消除左递归： (1)A T aB (2)A T Bb

(3) B T Ac

⑷B Td

解：用产生式(1) , (2)的右部代替产生式(3)中的非终结A 得到左部为］|B 的产生式:

(1) B T aBc

(2) B T Bbc

(3) B Td

消除左递归后得到：

B T aBcB' |dB'

B'T bcB' | &

再把原来其余的产生式

A T aB,A T Bb 加入，最终得到等价文法为： A T a

B A T Bb B T (aBc|d)B' B'T bcB'| &

c) 消除文法中一切左递归的算法 设非终结符按某种规则排序为

消除A 中的一切直接左递归

end (1

)

⑵

⑶ A 1, A 2,…，A n °

n

的产生式为:

…| S n Y

end

提取左因子伪代码P122

当两个或更多文法规则选择共享一个通用前缀时，需要提取左因子:

A Tap | aY

按如下规则提取左因子：

A Ta A'

5、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)中)

6、写递归下降子程序伪代码P10 6

递归下降：将一个非终结符A的文法规则看作将识别A的一个过程的定义一个if语句（简化了的）文法规则是：

if-stmt —if (exp) statement

| if (exp) statementelsestatement

伪代码：

procedure ifstmt;

beg in

match (if )；

match (()；

exp；

match ())；

stateme nt

if toke n = elsethe n

match (else；

stateme nt

en dif ；

en d ifstmt;

给出基于DFA进行词法分析的表驱动的实现算法

p44 state:=1;ch:=nextinput character;

while not accept[state]and not error(state) do

new state:=T[state,ch]；

if adva nce[state,ch]the n ch:=n ext in put chracter; State： =n ewstate

en d while;

if accept[state]the n accpet;

7、上下文无关文法 BNFEBNF 最左最右推导

1定义：上下文无关文法 G 是一个四元组G = (N , T , P, S),其中

N 是非终结符的有限集合；

T 是终结符或单词的有限集合，它与

N 不相交； P 是形如A F 的产生式的有限集合，其中

A

本文来源：https://www.bwwdw.com/article/5grq.html