编译原理复习.docx

编译原理复习.docx

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

编译原理复习

编译原理复习

第1章概述

1．计算机语言的发展：

☐机器语言汇编语言高级语言

☐从对机器的依赖性将语言划分为：

⏹低级语言：

与机器密切相关，面向机器的；

⏹高级语言：

与机器无关，面向人的。

2．翻译过程

☐翻译程序：

将一种语言程序（源程序）转换成另一种等价的语言程序（目标程序）。

☐汇编语言（输出结果）

☐机器语言（输出结果）

3．翻译程序的分类

☐编译程序：

将源程序翻译成等价的目标程序（汇编语言或机器语言）。

☐解释程序：

按源程序中语句动态顺序，边解释，边执行。

☐汇编程序：

将汇编语言编写的程序翻译成机器指令序列。

4．高级语言的翻译方式

☐编译方式（类似笔译）

☐解释方式（类似口译）

☐编译方式与解释方式的区别在于是否生成目标代码。

5．编译程序的特点

☐翻译过程是一种功能上等价的翻译。

☐输出结果是（机器语言或汇编语言）低级语言。

6．编译程序的阶段划分

☐词法分析

☐语法分析

☐

语义分析

☐中间代码生成

☐代码优化

☐目标代码生成

7．编译程序的逻辑结构

8．遍的概念

☐遍:

指对源程序或源程序的中间形式（如单词，中间代码）从头到尾扫描一次，并作相应的加工处理，称为一遍。

第2章文法和语言

1．上下文无关文法的形式定义

☐文法G是一个四元组G=（VN，VT，S，P）

☐VN：

非终结符号的有穷集合。

代表所定义的语法单位（用大写字母表示）。

☐VT：

终结符号的有穷集合。

代表语言的基本符号（用小写字母表示）。

☐S：

文法的开始符号，SVN。

代表语言的目标语法单位。

☐P：

产生式的（有限）集合。

定义语言的语法规则。

文法的一些说明：

☐①VN∩VT=，用V表示文法中所有的符号集合：

V=VN∪VT

☐②每条产生式一般形式：

A→，其中“→”表示“定义为”，AVN，（VN∪VT）*

示例：

写出下列文法的VN、VT和S。

⏹E→E+T|T

⏹T→T*F|F

⏹F→i|（E）

解：

⏹VN=｛E,T,F}

⏹VT=｛+,*,I,（,）}

⏹S=E

2．推导

☐从文法G的开始符号出发，逐步用产生式的右部符号替换左部符号，直至推出给定的句子（输入串），这个过程称为推导。

☐直接推导：

设x,y是符号串（V*），若用一次产生式可以从x推导出y，则称y为x的直接推导。

☐间接推导：

如果用若干次推导，可以从符号串x推出符号串y，则称y为x的推导。

记为：

x+y。

若x=y或x+y，则记为：

x*y。

☐最左（右）推导：

每次推导总是选择句型中最左（右）边的非终结符，用其产生式的右部来代替它，这样的推导称为最左（右）推导。

☐

示例：

✓最左推导：

EE+TT+TF+Ti+Ti+T*F

i+F*Fi+i*Fi+i*i

✓最右推导：

EE+TE+T*FE+T*iE+F*i

E+i*iT+i*iF+i*ii+i*i

☐语法树：

用一张图表示一个句型的推导过程称为语法树。

3．句型与句子

☐句型：

设G是一个文法，S是文法的开始符号，是符号串，如果S，则称是此文法的一个句型。

（即：

由文法开始符号推出的所有符号串）

☐句子：

只包含终结符的句型。

4．文法的二义性

☐如果一个文法G存在某个句子，该句子对应两棵不同的语法树，则称该文法是二义的。

☐二义性问题是不可判定的。

☐二义性的解决方法：

允许文法有二义性，而在分析过程中使用某些规则，在出现二义时根据这些规则来确定哪棵语法树是正确的（如规定算符的优先级）。

第3章词法分析

1．词法分析的核心功能

☐读入源程序的字符流，按构词规则识别出具有独立意义的词法单位（单词），同时，指出单词的属性（标识符、保留字、常数、…）。

2．词法分析产生的输出——单词记录

☐单词记录由两部分信息组成：

Ø单词符号：

对应某个特定意义的词法单位，如标识符、整型常数等

Ø属性值

☐通常将单词记录设计为二元式形式：

（单词符号，单词属性值）

☐示例：

假设关键字、运算符和界符都是一符一种，标识符单列一种，常数按类型分种。

☐While（i>=j）i--;生成的二元式：

1）（while,1）

2）（（,4）

3）（i,2）

4）（>=,3）

5）（j,2）

6）（）,5）

7）（i,2）

8）（--,6）

9）（；，9）

3．状态转换图

☐使用状态转换图是设计词法分析程序的一种好途径。

☐状态转换图是一个有限方向图。

☐结点代表状态（用○表示），结点间用箭弧线连接（），箭弧线上的符号，表示射出结点到达射入结点可能出现的输入符号，终态结点代表分析结束。

☐示例：

☐词法分析的实现：

Ø对应每个状态转换图中不同的情况进行不同的处理：

Ø每个状态对应一段子程序；

Ø对不含回路的分叉可以对应一组case语句或if…then…

Ø对于含有回路的结点应对应循环语句while和if。

4．正规式

☐中的符号为正规式的基本符号，单个符号或由符号与运算符组成的表达式称正规式。

☐示例：

a，ab*，ab，（ab）c

5．正规集

☐由正规式所表示的字符串的集合称为正规集。

☐若正规式用V表示，则正规集L（V）表示。

6．有限自动机

☐有限自动机是一种具有有限个状态的转移系统，

☐是具有离散输入和输出系统的一种数学模型，

☐它能准确地识别正规文法所定义的语言和正规式表示的正规集。

☐有限自动机分类：

Ø确定有限自动机（DFA）

Ø非确定有限自动机（NFA）

7．有限自动机的表示形式

☐

（1）状态图：

一个有限自动机可以用一个状态图（状态转换图）表示，即含有m个状态，n个输入符号，若f（ki,a）=kj，则从状态结点ki到状态结点kj画标记为a的弧。

弧上标记的符号表示当前识别的符号。

☐

（2）状态转换矩阵（不要求）

8．确定的有限自动机（DFA）

☐DFAM是一个五元组：

DFA（M）=（S，Σ,δ,S0,F），其中：

☐S是一个有限集，它的每个元素称为一个状态（自动机所有状态的集合）。

☐是一个有穷字母表，它的每个元素称为一个输入字符。

☐δ是一个从S→S的单值映射。

δ（S,a）=S’意味着：

当现行状态为S、输入字符为a时，将转换到下一个状态S’。

称S’为一个后继状态。

☐S0S是唯一的初态。

（仅有一个初态）。

☐FS是一个终态集。

（可有多个终态）。

9．非确定有限自动机NFAM

☐NFAM是一个五元组：

NFA（M）=（S,Σ,δ,S0,F），

☐S和Σ的含义同DFA；

☐δ是一个从S*到S的子集的映射，即δ：

S*2s；（即某一结点射出多条标记相同的弧线到达不同的结点。

）;

☐S0S，是一个非空初态集；

☐FS，是一个终态集。

10．NFAM与DFAM的区别

☐NFAM状态转换函数具有多值性；即δ（S,a）={S1,S2,……,Sn}；

☐NFAM可以存在ε弧；

☐NFAM可以有多个初态（初态集）。

11．DFA与NFA的关系

☐DFA是NFA的特例，对于每个NFAM都存在一个DFAM’，使：

L（M）=L（M’）

12．正规文法与NFA的关系

☐可根据NFA产生出其对应的正规文法；

☐也可根据正规文法画出对应的NFA。

13．从正规文法到NFA：

主要是由产生式P构造状态转换函数。

步骤：

（1）A→B

（2）A→B，VT*

（3）A→，VT*增加一个终态

示例：

S→a|bB|bA

A→abaB|B

B→b|aS

14．从正规式到NFA的转换

给定上的正规式V，都有NFAM，使得L（V）=L（M）

转换步骤：

☐⑴用拓广表示图，初态结点x，终态结点y。

☐⑵用下述方法逐步分裂，增加新的结点，直到每个弧上的标记为上的字符或空弧为止。

示例：

（a|b）*abb对应的NFAM

15．从NFAM构造DFAM’的步骤（确定化）

☐⑴求NFAM的_CLOSURE（I）；

☐⑵求Ix的_CLOSURE（J）,（X）；

☐⑶构造DFAM’的转换矩阵（表）；

☐⑷确定DFAM’的初态和终态。

（1）ε-CLOSURE（I）闭包定义

假设I是NFAM状态集的一个子集，I的_闭包（_CLOSURE（I））的定义:

Ø若SI，则S_CLOSURE（I）；

Ø

若SI，则从S出发经过任意条弧而能到达的任何状态S都属于_CLOSURE（I）。

☐示例：

Ø若I={x,1},则_CLOSURE（I）={x,1,2,y}

Ø若I={x,2},则_CLOSURE（I）={x,2,y}

（2）Ia定义

假定I是NFAM状态集中的一个子集，a是中的一个字符号，Ia的定义:

ØIa＝_CLOSURE（J）

Ø其中：

J是所有那些可从_CLOSURE（I）中的某一状态出发，经过一条a弧到达的状态,即：

J={（_CLOSURE（I），a）}

☐示例：

✓

若I={1}

⏹_CLOSURE（I）={1,2}

⏹J=（1,a）U（2,a）={5,4,3}

⏹Ia=_CLOSURE（J）={5,4,3,6,2,7,8}

✓若I={5}

⏹_CLOSURE（I）={5,6,2}

⏹J=（5,a）U（6,a）U（2,a）={3}

⏹Ia=ε_CLOSURE（J）={3,8}

（3）构造状态转换矩阵（表），若中有k个元素a，状态转换矩阵形式为：

构造表的过程：

①第一列是DFAM中的初始状态，为NFAM中初始状态集的闭包（_CLOSURE（S0））；

②对NFAM初始状态集（空闭包）中的每一个状态，分别构造Ia1,Ia2，…，Iak的后继状态子集。

每一个状态子集均为DFAM的一个状态。

③将新出现的状态子集置于第一列（作为DFAM的新状态），如步骤⑵，直至不出现新的状态子集为止。

（4）确定DFAM’的初态和终态：

①含有NFAM初态的子集为DFAM’的初态结点；

②含有NFAM终态的子集为DFAM’的终态结点。

示例：

NFAMDFAM

16．确定有限自动机的化简

（1）化简目的：

对任意DFAM1，寻找一个状态个数比M1少的DFAM2，使得L（M2）=L（M1）。

☐等价状态（不可区分的）

Ø设p和q是DFAM中的两个不同状态，如果从p出发能扫描任意串w而停止于终态，那么从q出发也能扫描同一个串w而停止于终态。

Ø反之，若从q出发能扫描任意串w而停止于终态，则从p出发也能扫描同一个串w而停止于终态。

Ø则称p和q是等价的（不可区分的）。

即：

（p，w）F，（q，w）F

☐可区分的（不等价）

Ø如果M中的两个状态p和q不等价，则称这个状态是可区分的（不等价）

Ø即：

设p和q是DFAM中的两个不同状态，如果从p出发扫描任意串w到达终态，而从q出发扫描同一个w到达非终态，则称p，q是可区分的（可区别的，不等价）

Ø即：

（p，w）F，（q，w）F

（2）DFAM的化简步骤

①将DFAM中的状态划分成终态集F和非终态集S-F（显然它们是可区分的）。

②对每个状态集构造新的划分，对每个字符a,求Iai（Ii表示化简到某个过程时的状态集中的某个子集），用a作为检测方法，设:

Ø（s’,a）=s,（t’,a）=t（s’，t’现属于同一个拟等价集）

Ø若s，t不等价，则s’，t’也不等价，说明此状态集也是可区分的。

Ø则将I（i）分成两半，使得一半含有s’：

I（i1）=｛s’|sI（i）且s’经弧a到达s｝，

另一半含有t’:

I（i2）=I（i）-I（i1）

③重复步骤②，直到每个子集均是不可区分的为止（子集个数不再增长）。

从每个子集中选取一个状态代表该子集。

示例：

1划分为终态集{4}和非终态集{0,1,2,3}

2{0,1,2,3}a=｛1｝

{0,1,2,3}b=｛2,3,4｝{0,1,2,3}

因此将{0,1,2,3}分为：

{0,1,2},{3}

（2.1）{0,1,2}a=｛1｝

{0,1,2}b=｛2,3｝{0,1,2}

将{0,1,2}分为{0,2},{1}

则现有状态集：

{0,2},{1},{3},{4}

（2.2）{0,2}a=｛1｝，{0,2}b=｛2｝

至此，状态集已不再扩大，最终的状态集为：

{0,2},{1},{3},{4}

第4章语法分析——自上而下

1．综述

☐语法分析是编译过程的核心部分。

☐语法分析的任务是分析一个文法的句子结构。

☐自上而下（自顶向下）分析，就是从文法的开始符号出发，每次选择一个产生式，用右部代替左部的逐步推导的过程。

☐问题：

当某个产生式有多个候选式时，应该选择哪个候选式？

☐解决办法：

（1）消除直接左递归：

避免死循环

对于P→P1P2…|Pm12…n，i≠

改写为：

✓P→1P2P………nP

✓P→1P2P………mP

示例：

EE+TT，改写为:

✓ETE

✓E+TE

（2）提取公因子：

避免回溯。

示例：

S→aA|aB，改写为：

S→aS’

S’→A|B

2．LL

（1）分析法

☐是按自左（第一个“L”）向右的顺序扫描输入字符串。

☐在分析过程中产生句子的最左（第二个“L”）推导；

☐“1”表示在分析过程中，每一步推导，最多只能向前（右）查看一个字符。

3．LL

（1）分析法的必要条件

☐文法不包含左递归;

☐对于文法中的每一个非终结符A的各个产生式的侯选首字符集两两不相交。

即：

对于产生式A

⏹若,则FIRST（）∩FIRST（）=Ф

⏹若＝ε,则FIRST（A）∩FOLLOW（A）=φ

☐如果文法G满足以上条件，则称该文法G为LL

（1）文法。

4．构造FIRST集合的算法

☐对每一文法符号X（VNUVT）*

（1）若XVT，则FIRST（X）={X}。

（2）若XVN，且有产生式Xa，aVT，则aFIRST（X）。

（3）若XVN，X，则FIRST（X）

（4）若XVN，Y1，Y2，，YiVN，

且有产生式XY1,,Yn。

若对于1≤i≤k≤n，都有Yi,则FIRST（Yk+1）-{}属于FIRST（X）

5．构造FOLLOW集算法

☐对文法开始符号S，将“#”置于FOLLOW（S）中。

（∵有句型#S#）

☐若有A→B，则把FIRST（β）-{ε}加至FOLLOW（B）

☐若有A→B或A→B，而；则把FOLLOW（A）加至FOLLOW（B）中。

示例：

E→TE’

E’→+TE’|ε

T→FT’

T’→*FT’|ε

F→（E）|i

FIRST（E）=FIRST（T）=FIRST（F）={（,i}

FIRST（E’）={+,ε}

FIRST（T’）={*,ε}

FOLLOW（E）=FOLLOW（E）=#，）

FOLLOW（T）=FOLLOW（T）=#，），+

FOLLOW（F）=#，），+，*

6．构造预测分析表（LL

（1）分析表）方法

☐若a∈FIRST（α），则把A→α放入M[A,a]中;

☐若ε∈FIRST（α），则对每个终结符b∈FOLLOW（A）,将A→ε放入M[A,b]中；

☐对空项置出错标记（或用空表示出错）

示例：

上例表达式文法的LL

（1）分析表：

7.预测分析程序

☐使用一张分析表和一个分析栈来联合控制。

☐分析表是一个M[A,a]形式的矩阵（A∈VN,a∈VT或a=‘#’）。

M[A,a]中存放一条关于A的产生式，它指出当A面临输入符号a时应采用的候选式。

☐分析栈STACK用于存放文法的符号。

初始时放入一个‘#’，然后放入文法的开始符号。

☐预测分析总控程序:

（1）置栈的初态为#S（#:

输入串的开始标记，S:

文法开始符号），读入符号放a中；

（2）弹出栈顶符号放入x中；

（3）若x∈VT:

⏹若a=x：

则把下一个输入符号读到a中，转

（2）

⏹若a≠x：

出错。

（4）若x=‘#’且a=‘#’：

则分析结束，否则出错。

（5）若x∈VN：

则查预测分析表M[A,a]:

⏹若M[A,a]为空，则出错；

⏹若M[A,a]有一个产生式x→x1…xn，则将产生式右部符号串以反序进栈。

☐示例：

有文法G

S→AaS|BbS|d

A→a

B→ε|c

预测分析表：

分析：

aabd

实际推导过程为：

SAaSaaSaaBbSaabSaabd

∴预测分析实际使用的是最左推导。

第5章自下而上分析法

1．综述

☐从输入串开始，每次在句型中选择一个可归约串，用产生式左部来代替它，逐步进行归约，直到归约为文法的开始符号。

☐实际是一个不断进行直接归约的过程。

2．几个概念

☐短语：

设文法G的开始符号为S，S，且Aβ,则称β是句型相对于非终结符A的一个短语。

☐直接短语：

在短语定义的基础上，若有SA，且A,则称是句型相对于产生式A→的直接短语

☐句柄：

句型的最左直接短语称为该句型的句柄。

示例：

对文法：

E→E+T|E-T|T

T→T*F|T/F|F

F→i|（E）

分析句型E+T*F+i。

⏹短语：

T*F,i,E+T*F,E+T*F+i

⏹直接短语：

T*F,i

⏹句柄：

T*F

3.算符优先分析法

3.1算法文法

如果文法G中没有形如…QR…的产生式，其中Q,R∈VN，则称G为算符文法，记为OG文法。

（即产生式右部不包含有两个相邻的非终结符）

在这种文法中，可将非终结符看成是操作数，将终结符看成是运算符。

3.2算符优先关系

☐a≖b：

当且仅当有产生式P→…ab…或P→…aAb…，A∈VN

☐a

当且仅当有P→…aA…，且Ab…或ABb…（先归约b或Bb，再归约aA，则b的优先级高）

☐a>b：

当且仅当有P→…Ab…，且A…a或A…aB

3.3算符优先文法

如果一个算法文法OG中任何两个终结符之间最多只有一种优先关系成立，则称文法G为算法优先文法，记为：

OPG

3.4构造优先关系表

☐①将文法中所有的终结符和#作为关系表的行标和列标。

☐②当文法中有A→…ab…或A→…aQb…时，（Q∈VN,a,b∈VT），则置a≖b。

特别#≖#。

☐③按行求：

对每个终结符a∈VT，有无A→…aQ…形式的产生式，若有，则对每个b∈FIRSTVT（Q），置a<.b。

☐④按列求：

对每个终结符b∈VT，有无A→…Qb…形式的产生式，若有，则对每个a∈LASTVT（Q），置a.>b

☐⑤对左边的开始符#,对所有的a∈FIRSTVT（S）,置#<.b

对右边的结束符#，对所有的a∈LASTVT（S）,置a.>#

（1）构造FIRSTVT（P）方法

☐规则1:

按定义，若有产生式P→a…或P→Qa…，则a∈FIRSTVT（P）。

☐规则2:

若a∈FIRSTVT（Q），且P→Q…，则a∈FIRSTVT（P）

（2）构造LASTVT（P）方法

☐规则1：

按定义，若有产生式P→…a或P→…aQ，则a∈LASTVT（P）。

☐规则2:

若a∈LASTVT（Q），且有P→…Q，则a∈LASTVT（P）

示例：

E→E+T|T

T→T*F|F

F→P↑F|P

P→（E）|i

FIRSTVT（E）={+,*,（,i,↑

FIRSTVT（T）={*,（,i,↑

FIRSTVT（F）={（,i,↑

FIRSTVT（P）={（,i

LASTVT（E）={+,*,,i,↑}

LASTVT（T）={*,,↑,i}

LASTVT（F）={,i,↑}

LASTVT（P）={,i}

优先关系表

4．算法优先分析算法

☐分析开始时，栈底放一个“#”，输入串之后放一个“#”；令θ代表从栈顶往下的第一个终结符号；a存放新读入的符号。

算法基本步骤为：

☐①把下一个输入符号读至a中，

☐②若θ>a：

从栈顶往下进行相应的归约处理，归约后的符号进栈，重新进入步骤②。

☐③若θ≖a：

⏹θ≖a≖#，则分析结束；

⏹其他：

将a入栈，转①。

☐④若θ

将a移入栈，转①。

☐⑤若θ与a不存在优先关系，则出错。

示例：

利用上述优先关系表，分析：

分析#i+i*i#

6．LR分析法

6.1LR分析法简介

☐从左（Left,L）向右扫描输入串，构造一个最右推导（Rightmost,R）的逆过程进行规范归约（最左归约），

☐每次归约的都是真正的句柄。

6.2LR分析法的基本原理

☐把每个句柄的识别过程划分为若干状态，每个状态从左至右识别句柄中的一个符号，若干个状态就识别句柄的一部分符号。

☐识别了句柄的一部分符号就相对于识别了当前规范句型的左起部分——这一部分称为规范句型的活前缀。

☐活前缀：

规范句型的一个前缀，它不包含句柄之后的任何符号。

6.3项目

（1）项目的定义

☐在文法的每一个产生式的右部添加一个圆点指示识别的位置，圆点右移一位代表LR（0）的一个项目（一个产生式项目的个数为右部符号个数+1）。

☐例：

产生式A→XYZ有四个项目：

✓A→·XYZ

✓A→X·YZ

✓A→XY·Z

✓A→XYZ·

直观上说，一个项目指明了在分析过程中的某个时刻能看到产生式的多大一部分。

（2）项目的分类

☐归约项目：

A→α.

☐移进项目：

A→α.aβ，a∈VT

☐待约项目：

A→α.Bβ,B∈VN

☐接受项目：

S’→α.,S’为文法开始符号。

（3）拓广文法

☐添加一个新的开始符号S′,并增加一个产生式：

S’→S。

☐目的是为了有唯一的接受状态，只有S′→S.是唯一的接受项目。

6.4构造识别活前缀的DFAM

☐构成识别一个文法活前缀的DFA的项目集（状态）的全体称为该文法的LR（0）项目集规范族。

（1）构造识别活前缀的DFAM方法：

☐构造DFAM=（S,VTUVN,δ,S0,F）,其中:

⏹S：

S的每个项目元素是个项目集。

⏹S0：

拓广文法的开始符号S’的闭包CLOSURE（S’→.S）

⏹δ（I,X）=CLOSURE（J）,J为所有形如A→αx.β项目而A→α.xβ∈I

⏹F：

终态集，所有的归约项目或接受项目。

（2）I的闭包的定义和构造

☐假定I是拓广文法G’的任一项目集，定义和构造I的闭包CLOSURE（I）：