编译原理复习重难点.docx

编译原理复习重难点.docx

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

编译原理复习重难点

第一章

从本质上来说，程序设计语言是按一定规则排列的符号集合，而编译程序就是把这些符号集合变成机器指令的转换器，编译程序又称为编译器。

程序设计语言【高级语言，低级语言（机器语言和汇编语言）】

编译过程：

词法分析，语法分析，中间代码生成，优化，目标代码产生。

三元式定义为如下形式：

（op,a1,a2）

其中op为操作码或运算符，a1和a2为操作数或运算分量。

编译:

将高级语言程序翻译成另一种语言的等价程序。

解释：

翻译一句执行一句，边翻译边执行，直到程序结束。

与编译的区别：

不生成等价的目标代码程序。

优点：

解释方式便于程序的调试。

（编译方式只需翻译一次，且目标程序的执行速度快）

（1）词法分析

主要任务：

从左到右扫描源程序，逐一读入构成源程序的字符流，识别出

其中的一个个单词，识别出的单词称单词符号，也简称符号。

单词是高级语言程序中有实际意义的最小语法单位。

（2）语法分析

任务“组词成句”，根据单词分析出组成源程序的各类语法单位，

并指出其中的语法错误。

语法单位——由源程序的单词构成（如表达式、语句、……乃至整个程序。

）

语法单位的构成规则——语法规则。

一个语言的词法规则和语法规则定义了一个程序的形式结构。

语法单位的表示——语法树

（3）语义分析和中间代码生成

任务：

分析出语法单位具体的动作意义，进行初步翻译，生成与源程序等价的中间代码程序。

语义:

定义一个程序所表示的意义,用语义规则描述。

中间代码：

指令应结构简单、含义明确，易于实现源程序——中间代码

——目标代码三者之间的转换。

中间代码常用形式：

逆波兰式、三元式、四元式等。

四元式：

（运算符，对象1，对象2，结果）

例：

z=x+a%3*y

（1）（%a3t1）

（2）（*t1yt2）（3）（3）（+xt2t3）（4）（=t3_z）

（4）代码优化

任务：

对中间代码进行等价的加工变换，以便生成更有效更节省时间和空间的目标代码。

例：

z=x+a%3*y的四元式序列：

（1）%a3t1）

（2）（*t1yt2）

（3）（+xt2z）

（5）目标代码生成任务：

将中间代码程序变换成目标代码程序。

2．按“遍”组合方式

“遍”：

对源程序或等价的中间语言程序从头到尾扫描，完成规定的

任务，并生成新的中间结果或目标程序，称一“遍”。

编译程序的构造与三个方面有关:

源语言，目标语言，编译方法。

第二章形式语言与自动机理论基础

主要内容：

语言和文法、有限自动机、正则表达式。

语言：

符号串的集合。

元素——符号串——该语言的一个句子。

字母表——符号串中符号的来源。

【例2-1】Σ={a，b，c，……，z}，x=“laugh”，则|x|=5

Σ={I，you，he，am，is，are，a，student}，

y=“Iamastudent”，空格不计算长度，则|y|=4。

空符号串：

无任何符号的串，简称空串，用ε表示，|ε|=0

【例2-4】若U={a，b}，V={c，d}

则UV={ac，ad，bc，bd}

闭包：

若指定字母表Σ，则Σ*表示Σ上的所有有穷长的串的集合。

Σ*=Σ0∪Σ1∪Σ2∪……∪Σn∪……

Σ*称为集合Σ的闭包。

Σ+=Σ1∪Σ2∪……∪Σn∪……

Σ+称为集合Σ的正闭包。

成立的等式：

Σ*=Σ0∪Σ+，Σ+=ΣΣ*=Σ*Σ

若符号串x是Σ*的元素,则表示为x∈Σ*,否则xΣ*。

【例2-5】Σ={0,1}Σ*={ε,0,1,00,10,11,000,001,100,………}

文法的形式定义：

1：

终结符用VT表示、2：

非终结符用VN表示、3：

规则α→β、

4：

文法定义：

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

VN：

非终结符集（非空）；VT：

终结符集（非VN∩VT＝Ø；S：

识别符号或开始符号，S∈VN，且至少在一条规则中作为左部出现；P：

规则（产生式）的集合。

用V表示VN∪VT，称G的字母表或词汇表。

【例2-7】有一文法G（VN，VT，S，P）

其中:

VN={S}VT={0，1}开始符号是SP={S→0S1，S→01}

2.扩展的BNF表示法

（1）“{}”表示符号串t的多次重复，n为重复的最小次数，m为重复的最大次数，省略n、m表示t可以重复0到任意多次。

【例2-9】文法规则S→0S1|01

简化为S→0（S1|1）或S→（0S|0）1或S→0（S|ε）1

（3）“[]”：

[t]表示符号串t可选（即可有可无）。

【例2-11】C语言条件语句的语法图：

文法相关概念：

定义1：

如α→β是文法G（VN，VT，S，P）的一条规则，γ、δ∈V*，

若有符号串v、w满足v=γαδ，w=γβδ则称v（应用规则α→β）直接产生w，或称w是v的直接推导，反过来称w直接归约到v，记作v⇒w。

【例2-13】对文法G：

S→0S1S→01有直接推导序列：

S⇒0S1⇒00S11⇒000111

定义2：

如果存在直接推导序列：

v=w0⇒w1⇒w2⇒……⇒wn=w则称v推导（产生）出w，推导长度为n，反过来称w归约到v，记作v⇒w。

如果有v⇒w，或v=w，则记作v⇒w。

【例2-14】S⇒0S1⇒00S11⇒000111S推导出“000111”，推导长度3“000111”归约到S，表示成S⇒000111

2．句型和句子

定义：

文法G（VN，VT，S，P），若符号串x可由开始符号S推导出（S⇒x），则称x是G的一个句型，若x仅由终结符组成，则称x为G的一个句子。

3．形式语言

定义：

文法描述的语言是该文法的所有句子的集合，记作L（G）。

集合形式表示：

L（G）={α|S⇒α∧α∈VT*}

【例2-16】文法G：

S→0S1S→01描述的语言：

L（G）={0n1n|n≥1}

4．文法的等价性定义：

若有文法G1、G2，它们描述的语言相同，即L（G1）=L（G2）则称两文法G1和G2等价。

【例2-17】有文法G[A]：

A→0RA→01R→A1描述的语言L（G）={0n1n|n≥1}。

定义：

若有文法G1、G2，它们描述的语言相同，即L（G1）=L（G2）则称两文法G1和G2等价。

5.递归规则和递归文法

递归规则：

形如P→α1Pα2的规则称递归规则。

若α1=ε则称左递归规则;

若α2=ε则称右递归规则。

递归文法：

含有递归规则的文法称递归文法。

P⇒α1Pα2的递归称间接递归,含间接递归的文法也是递归文法。

文法分类：

1、0型文法（无限制文法或短语文法）定义2-7设G=（VN，VT，P，S），如果它的每个产生式α→β满足α、β∈（VN∪VT）*，且α至少含有一个非终结符，则G是一个0型文法。

结论：

0型文法的能力相当于图灵机。

任何0型语言都是递归可枚举的，反之，递归可枚举集也必定是一个0型语言。

2、1型文法（上下文有关文法）

定义2-8设G=（VN，VT，P，S），如果它的每个产生式α→β满足|β|≥|α|（仅S→ε除外），则G是一个1型文法。

另一种描述：

文法的产生式形如α1Aα2→α1βα2其中A∈VN，α、β∈（VN∪VT）*且β≠ε。

【例2-18】1型文法G[S]：

S→xSYZ|xYZyZ→yz

xY→xyZY→YZ

yY→yyzZ→zz

3、2型文法（上下文无关文法）

定义2-9设G=（VN，VT，P，S），如果它的每个产生式α→β中的α是一个非终结符，则G是一个2型文法或上下文无关文法。

【例2-19】2型文法G[S]：

S→ET→P|T﹡PF→i|（E）E→T|E＋TP→F|F↑P

4、3型文法（正规文法或正则文法）

定义2-10设G=（VN，VT，P，S），如果它的每个产生式均形如A→aB或A→a其中A、B∈VN，a∈VT。

【例2-20】3型文法G[S]：

S→aAA→aAA→a

S→aA→dAA→d

消除空产生式

定理：

对任一文法G1，可构造文法G2，使得L（G1）=L（G2），且G2中无空产生式。

证明：

根据G1，构造G2的方法如下：

（1）令={A|A}

（2）={A|A+,+}。

（3）从G1中删除所有空产生式。

（4）从G1中删除只能导出空串的非终极符。

（5）对于文法中任意产生式AX1X2…Xi-1XiXi+1…Xn

a.若XiVT，不做动作；

b.若XiVN-，不做动作；

c.若Xi，补充规则AX1X2…Xi-1Xi+1…Xn；

例：

AaBcDBb|DBB|d

详见Page18

消除不可达产生式

定理：

对任一文法G1都可以构造文法G2，使得L（G1）=L（G2），且G2中的每个非终极符必出现在它的某个句型中。

证明：

根据G1，构造文法G2的方法如下：

（1）令={Z|Z是文法的开始符}。

（2）递归扩充直到收敛为止，即={B|AxByG1,BVN,A}

（3）若一个产生式左部非终极符A，则删除以A为左部的所有产生式。

消除特型产生式

注：

形如A->B（B为非终极符）的产生式为特型产生式，特型产生式在语法分析中会降低分析速度，因此应该消除。

定理：

对任一文法G1，可以构造文法G2，使得L（G1）=L（G2），且在G2中没有特型产生式。

证明：

构造无特型产生式的文法G2的方法如下：

（1）对文法G1中任意非终极符A，求集合A={B|A+B,BVN}。

（2）若BA，且B是文法G中的一个非特型产生式，则补充如下规则A

（3）去掉文法G1中的所有的特型产生式。

（4）去掉新的文法中的无用产生式。

例：

AB|D|aB

BC|b

Cc

DB|d

消除左递归

一个文法含有下列形式的产生式时

（1）AAa|bAVN,a,（VNVT）*

（2）AB|BA|bA,BVN,a,,（VNVT）*

其中

（1）为直接左递归，

（2）为间接左递归，因此文法中只要有A+A…，则称文法为左递归的。

文法的化简：

文法应没有多余的或有害的规则。

化简：

（1）删除形如A→A的产生式。

（2）删除不可到达的文法符号及其相应的产生式。

（3）删除不可终止的非终结符及其相应的产生式。

【例2-21】文法G：

S→aS|W|UU→aV→bV|acW→aW

化简后的文法G：

S→aS|UU→a

W是不可终止的、V是不可到达的。

文法的二义性

可见：

（1）一棵语法树表示了一个句型的多种可能的不同推导过程，但未必是所有的。

（2）一个句型未必只有一棵语法树。

最左推导：

在推导的任何一步α⇒β（α、β是句型）都是对α中的最左非终结符进行替换。

最右推导：

在推导的任何一步α⇒β（α、β是句型）都是对α中的最右非终结符进行替换。

也称规范推导，推出的句型称规范句型。

例如最左推导：

E⇒E*E⇒i*E⇒i*E+E⇒i*i+E⇒i*i+i

最右推导：

E⇒E*E⇒E*E+E⇒E*E+i⇒E*i+i⇒i*i+I

显然，一棵语法树表示的最左（右）推导是唯一的！

定义：

若一个文法存在某个句子，它对应两棵（或以上）不同的语法树，或

它有两个不同的最左（右）推导，则该文法是二义的（具有二义性）。

二义性文法：

如果一个文法的某个句型有两棵不同的语法分析树，则称该文法二义性为二义性文法。

文法G=（{+,*,I,（,）},{E},E,P）,其中P为：

E®i

E®E+E

E®E*E

E®（E）

1.正规式和正规集的定义

定义：

设有字母表Σ，则

（1）ε和Ø都是Σ上的正规式，所表示的正规集是{ε}和Ø；

（2）若a∈Σ，则a是Σ上的正规式，所表示的正规集是{a}；

（3）若U、V都是Σ上的正规式，它们所表示的正规集分别记为L（U）

和L（V），则U|V（或）、U·V（连接，也可写UV）和U*（闭包）也

都是正规式，它们所表示的正规集分别为L（U）∪L（V）、L（U）L（V）

（乘积）和（L（U））*；

（4）仅由有限次使用上述三步骤得到的表达式才是Σ上的正规式，

仅由这些正规式所表示的集合才是Σ上的正规集。

优先级从高到低为“*”（闭包）、“·”（连接）、“|”（或），括号优先。

1.正规式正规文法

有限自动机【确定的有穷自动机DFA、不确定的有穷自动机NFA】

确定的有穷自动机DFA

DFA的意义：

对于Σ*中的任何字符串t，若存在一条从初态到终态的路径（该路径

上的字符串为t），则t可为DFAM所接受（或说t是该DFA可识别的）。

若初态结也是终态结，则空字可接受。

DFAM所能接受的字符串的全体称为该自动机识别的语言，记为L（M）。

结论：

Σ上的一个字符串集U是正规的，当且仅当存在一个Σ上的确定的

有穷自动机DFAM，使U=L（M）。

不确定的有穷自动机NFA

NFA与DFA的等价性

2.NFA的确定化

定义：

一个状态集合I的ε—闭包ε—closure（I）：

①若q∈I，则q∈ε—closure（I）；

②若q∈I，则q经任意条ε弧而能到达的任何状态q:

qε—closure（I）

定义：

一个状态集合I的a弧转换为Ia=ε—closure（J）

其中:

J是所有那些可以从I中的某一状态经过一条a弧而到达的状态的集合。

NFA与DFA的等价性

NFAM=（Q,Σ,δ,Q0,Z）DFAM=（Q,Σ,δ,q0,Z）

Q¢=Ø；Z¢=Ø；

Q0¢=e—Closure（Q0）

将Q0¢置为未标记，并加入到Q¢中；

While（Q¢中存在未标记的状态子集I）

{

对每个a∈Σ做

{

求Ia;

若Ia不在Q¢中，则把它置为未标记后加入到Q¢中；

若Ia至少有一个是M的终态，则同时把Ia加入到Z¢中；

}

给I加上标记；

}

重新命名Q¢中的所有状态子集为新的状态；

Q0¢对应的新状态q0¢即为DFAM¢的初态；

Z¢中的所有状态子集对应的新状态为DFAM¢的终态；

DFA的化简

构造与FA等价的正规式

构造与正规式等价的FA

构造正规文法等价的FA

构造正规文法G（VN，VT，P，S）等价的FAM=（Q,Σ,δ,q0,Z）

1、字母表Σ：

M的字母表Σ对应G的VT

2、状态集Q:

M的Q对应G的VN

3、初态q0：

M的q0对应G的S

4、转换函数δ：

M的转换函数δ对应G的A→aB，A→a

A→aB：

δ（A,a）=B

A→a：

δ（A,a）=Z

构造与FA等价的正规文法

第三章词法分析

任务：

识别单词。

完成词法分析任务的程序也称词法分析器或扫描器。

单词的种类

单词：

程序中最小的有意义的单位。

五类单词：

关键字、标识符、常数、运算符、界符。

单词的机内表示方法

二元式：

（单词种别，属性）

单词的形式描述

正规式描述

正规文法描述正规文法：

每个产生式均形如A→aB或A→a。

预处理：

删除无用空格、换行符、注释，源程序输入／输出等。

第4章自顶向下语法分析

把句子分析的过程称为语法分析，即完成这个任务的程序称为语法分析程序或称为识别程序。

分析算法又称识别算法。

语法错误类别

1）程序的开始符，语句（表达式）的开始

符（后继符）错

  2）标识符（常量）错：

该出现时未出现

    3）括号类错误：

不匹配

  4）分隔符错：

assignment

分析算法可分为：

自上而下分析法：

从文法的开始符号出发，寻找与输入符号串匹配的推导，或者说，为输入串寻找一个最左推导。

自下而上分析法：

从输入符号串开始，逐步进行归约，直至归约到文法的开始符号。

语法分析中语法错误处理

要求：

报告错误出现的位置、修复错误并继续检查后续部分、执行开销不应太大。

处理策略：

1）紧急方式恢复；2）短语级恢复；3）出错产生式4）全局纠正；

语法描述工具：

上下文无关文法

产生式形如A→β（A∈VN，β∈V*）

自顶向下语法分析概述

问题的本质：

识别一个符号串是否为某文法的一个句型。

即试图按文法的规则为符号串构造推导或语法树。

语法分析方法：

自顶向下的语法分析方法、自底向上的语法分析方法。

4.2.1自顶向下的语法分析方法

方法：

从文法的开始符号出发，反复选用各产生式进行最左推导，以“匹配”于输入符号串，若推导成功，则输入串是该语言的一个合法句型，否则就不是。

需解决的主要问题：

若同一个非终结符有多个产生式，则推导时究竟选用哪一个？

两种分析方法（确定的自顶向下语法分析方法，不确定的自顶向下语法分析方法）

4.2.2确定的自顶向下的语法分析方法

【例4-4】有文法G：

S→xA

S→yB

A→aA|c

B→bB|d

句子“xaa…c”或“ybb…d”的推导过程?

确定的自顶向下的语法分析方法：

若在推导时每次都能根据输入串当前所要匹配的符号选择唯一的

一个产生式往下推，则这种分析方法就称为确定的自顶向下的语法分

析方法。

显然，能否进行确定的自顶向下的语法分析是由文法决定的。

4.2.3不确定的自顶向下的语法分析方法

例4-5】有文法G：

S→xAS→xBA→aA|aB→bB|b

句子“xaa…”或“xbb…”的推导过程？

句型的推导过程带“回溯”——不确定的自顶向下语法分析方法。

不确定性：

每一步推导不一定能根据当前输入的单词符号唯一地确定选用的产生式。

4.3.1“回溯”的原因

1．提取左公共因子

若有：

A→αβ1│αβ2│……│αβn则：

A→α（β1│β2│……│βn）

再引入一个新的非终结符A：

A→αA

A→β1│β2│……│βn

注意：

α提取出来后，β1、β2、……、βn中的某几个βi还可能

含有左公共因子，则可以进一步进行提取。

4.3.2“回溯”的消除

4.3.3LL

（1）文法的定义

问题：

何种文法能进行确定的自顶向下的语法分析？

分两种情况进行分析

1，不含ε产生式的文法、2．含ε产生式的文法

Conclusion：

当文法中非终结符A不含ε产生式时，若其不同产生式的右部的FIRST集两两互不相交，则当用A的产生式进行推导时能唯一确定应

选用的产生式。

{

FOLLOW（A）=Ø;

对文法的开始符号S置FOLLOW（S）={‘#’};

对所有形如B→αAβ的产生式做：

{

FOLLOW（A）=FOLLOW（A）U（FIRST（β）-{ε}）；

FOLLOW（A）=FOLLOW（A）UFOLLOW（B）

}

对所有形如B→αA的产生式做：

FOLLOW（A）=FOLLOW（A）UFOLLOW（B）

}

Conclusion:

当文法中非终结符A含有ε产生式时，若满足以下条件，则当用A

的产生式进行推导时仍能唯一确定应选用的产生式：

（1）A的非ε产生式的右部的FIRST集两两互不相交；

（2）FOLLOW（A）也不与A的任一非ε产生式的右部的FIRST集相交。

另一种描述：

当文法中有A→α，A→β时，若α、β不能同时推出ε

（设αε，βε），且满足条件

FIRST（α）∩（FIRST（β）∪FOLLOW（A））=Ø

则对非终结符A的替换仍能确定唯一的产生式。

3．LL

（1）文法

定义：

上下文无关文法是LL

（1）文法的充分必要条件是：

（1）文法不含左递归；

（2）对每个非终结符A的两个不同的产生式A→α、A→β

（其中α、β不能同时推出ε），满足条件:

SELECT（A→α）∩SELECT（A→β）=Ø

判别LL

（1）文法的方法和步骤：

（1）根据定义计算每个产生式的SELECT集；

（2）对左部相同的产生式，查看它们的SELECT集，若两两互不相交，则为LL

（1）文法。

预测分析法也叫LL

（1）分析法

采用这种方法进行语法分析的程序就叫做预测分析器或LL

（1）分析器。

预测分析器由三部分组成（一张预测分析表、一个分析用的栈、预测分析程序）

4.4.1预测分析表

预测分析表:

矩阵M表示，其中

（1）行——以文法的非终结符为行，一个非终结符一行；

（2）列——以文法的终结符或句子括号“#”为列，一个终结符或“#”占一列；

（3）M[A，a]——两种值：

关于A的一条产生式；空着（出错处理）。

值的获得：

根据产生式的SELECT集，

若a∈SELECT（A→α），则M[A，a]=“A→α”。

4.4.3预测分析程序

4.5递归下降分析法

组成：

每个非终结符对应一个递归过程或函数，其功能是按产生式的右部识别由该非终结符推出的串。

分析过程：

从读入第一个单词起，由开始符号出发，按语言的文法向下进行分析：

（1）遇非终结符时，调用该非终结符的递归过程；

（2）遇终结符时，看当前输入单词与该终结符是否相符：

若相符则输入单词正确，再读入下一单词继续分析；

若不符则输入单词错误，进行出错处理。

第五章自底向上语法分析

5.1自底向上语法分析概述

5.1.2自底向上语法分析的实现

实现过程:

使用一个栈，把输入符号一个个地逐步移进栈里，当栈顶形成某个产生式的右时，就把栈顶的这一部分（称“可归约串”）替换

成该产生式的左部非终结符，这一动作就实现了归