编译原理期末复习资料.doc

《编译原理》期末复习资料完整版
《编译原理》期末复习资料
【题 1】
1. （a|b）*（aa|bb）（a|b）*画出状态转换图。

Ia
Ib
① 1,2,3
2,3,4
2,3,5
② 2,3,4
2,3,4,6,7,8
2,3,5
③ 2,3,5
2,3,4
2,,3,5,6,7,8
④ 2,3,4,6,7,8
2,3,4,6,7,8
2,3,5,7,8
⑤ 2,3,5,6,7,8
2,3,4,7,8
2,3,5,6,7,8
⑥ 2,3,5,7,8
2,3,4,7,8
2,3,5,6,7,8
⑦ 2,3,4,7,8
2,3,4,6,7,8
2,3,5,7,8

Ia
Ib
1
2
3
2
4
3
3
2
5
4
4
6
5
7
5
6
7
5
7
4
6
新的状态转换图如下：

（1）A={1,2,3}，B={4,5,6,7} Aa={2,4} ×
（2）A={1,3}，B={2}，C={4,5,6,7} Aa={2}B，Ab={3,5} ×
（3）A={1}，B={2}，C={3},D={4,5,6,7}（单元素可以不用看，必有，古先看D）
Da={4,7}D，Db={5,6}D，Aa={2}B，Ab={3}C，Ba={4}D，Bb={3}C，Ca={2}B，Cb={5}C，则有

a
b
A
B
C
B
D
C
C
B
D
D
D
D

2. （a*|b*）b（ba）*的状态转换图。

Ia
Ib
① 1,2,3,4
2,4
3,4,5,6,8
② 2,4
2,4
5,6,8
③ 3,4,5,6,8
---
3,4,5,6,7,8
④ 5,6,8
---
7
⑤ 3,4,5,6,7,8
6,8
3,4,5,6,7,8
⑥ 7
6,8
---
⑦ 6,8
---
7

Ia
Ib
1
2
3
2
2
4
3
---
5
4
---
6
5
7
5
6
7
---
7
---
6
新的状态转换图如下：

化简：（用终结状态及非终结状态，然后输出状态一致分一类）。
（1）A={1,2,6}，B={3,4,5,7} Aa={2} ×
（2）A={1,2}，B={6}，C={3,4,7}，D={5} Cb={5,6} ×（只要有一个不属于任何一个集合，就不行）
（3）A={1,2}，B={6}，C={3}，D={4,7}，E={5} Ab={3,4} ×
（4） A={1}，B={2}，C={6}，D={3}，E={4,7}，F={5} Aa={2}B，Ab={3}D，Ba={2}B，Bb={4}E，Ca={7}E，Db={5}F，Eb={6}C，Fa={7}E，Fb={5}F

a
b
A
B
D
B
B
E
C
E
---
D
---
F
E
---
C
F
E
F

[注意事项]：

[知识要点]：
u 正则表达式：
；；；
；
是最左边一个字母一定是，其余字母为的任意组合，不包括。
{a和若干个a（包括0的情形）后跟一个b构成的符号串集合}
{a和a后跟若干个（包括0的情形）b构成的符号串集合}
u 状态转换图（有穷状态自动机）：

【题 2】
1.求如下简单算术表达式文法中语法变量的FOLLOW集。

[解答]：（1）求表达式文法的语法符号的FIRST集：
FIRST(F)={（, id}
FIRST(T)=FIRST(F)={（, id}
FIRST(E)=FIRST(T)={（, id}
FIRST(E')={+，ε}
FIRST(T')={*,ε}
FIRST(+)={+}, FIRST(*)={*}
FIRST(（)={（}
FIRST(）)={）}
FIRST(id)={id}
（2）求表达式文法的语法变量的 FOLLOW集：
FOLLOW(E) = { #, ) }
FOLLOW(E')= FOLLOW( E ) = { #, ) }
FOLLOW(T) = {FIRST(E')-{ε}}∪FOLLOW(E)∪FOLLOW(E')= {+,),#}
FOLLOW(T')= FOLLOW(T)= {+,),#}
FOLLOW(F) = FIRST(T’)∪FOLLOW(T)∪FOLLOW(T') ={*,+,),#} 6
[知识点]
First集合的求法：
First集合最终是对产生式右部的字符串而言的，但其关键是求出非终结符的First集合，由于终结符的First集合就是它自己，所以求出非终结符的First集合后，就可很直观地得到每个字符串的First集合
1. 直接收取：对形如U->a…的产生式（其中a是终结符），把a收入到First(U)中
2. 反复传送：对形入U->P1P2P3…Pn的产生式（其中P是非终结符），应先把First(P1)中的全部内容传送到First(U)中,如果P1中有ε，把First(P2)中的内容传送到First(U)中,类推直到Pi中无ε。
Follow集合的求法：
Follow集合是针对非终结符而言的，Follow(U)所表达的是句型中非终结符U所有可能的后随终结符号的集合，特别地，“$”是识别符号的后随符,先直接加入到S中。
1. 直接收取：注意产生式右部的每一个形如“…Ua…”的组合，把a直接收入到Follow(U)中。
2. 直接收取：对形如“…UP…”(P是非终结符)的组合，把First(P)中非ε收入到Follow(U)中。
3. 反复传送：对形如U－>aP的产生式（其中P是非终结符）或U->aPQ(P,Q为非终结符且Q中含ε)，应把Follow(U)中的全部内容传送到Follow(P)中。
[例] 文法：S→ABc A→a|ε B→b|ε
First集合求法:能由非终结符号推出的所有的开头符号或可能的ε，但要求这个开头符号是终结符号。如此题A可以推导出a和ε，所以FIRST（A）=｛a，ε｝；同理 FIRST（B）={b,ε};S可以推导出aBc，还可以推导出bc，还可以推导出c，所以FIRST(S）=｛a，b，c｝
Follow集合的求法:紧跟随其后面的终结符号或＃。但文法的识别符号包含＃，在求的时候还要考虑到ε。 具体做法是把所有包含你要求的符号的产生式都找出来，再看哪个有用。 Follow（S）=｛＃｝如求A的，产生式：S→ABc A→a|ε ，但只有S→ABc 有用。跟随在A后面的终结符号是FIRST（B）=｛b，ε｝，当FIRST（B）的元素为ε时，跟随在A后的符号就是c，所以 Follow（A）=｛b，c｝同理Follow（B）=｛c｝
2.对下面的文法 G ：
(1)计算这个文法的每个非终结符的 FIRST 集和 FOLLOW 集。
(2) 证明这个方法是 LL(1) 的。
(3) 构造它的预测分析表。

解：（1）计算这个文法的每个非终结符的FIRST集和FOLLOW集。
FIRST集合有：
FIRST(E)=FIRST(T)=FIRST(F)=FIRST(P)={(,a,b,^};
FIRST(E')={+,ε}
FIRST(T)=FIRST(F)=FIRST(P)={(,a,b,^};
FIRST(T')=FIRST(T)∪{ε}={(,a,b,^,ε};
FIRST(F)=FIRST(P)={(,a,b,^};
FIRST(F')=FIRST(P)={*,ε};
FIRST(P)={(,a,b,^};
FOLLOW集合有：
FOLLOW(E)={),#};
FOLLOW(E')=FOLLOW(E)={),#};
FOLLOW(T)=FIRST(E')∪FOLLOW(E)={+,),#};//不包含ε
FOLLOW(T')=FOLLOW(T)=FIRST(E')∪FOLLOW(E)={+,),#};
FOLLOW(F)=FIRST(T')∪FOLLOW(T)={(,a,b,^,+,),#};//不包含ε
FOLLOW(F')=FOLLOW(F)=FIRST(T')∪FOLLOW(T)={(,a,b,^,+,),#};
FOLLOW(P)=FIRST(F')∪FOLLOW(F)={*,(,a,b,^,+,),#};//不包含ε
(2)证明这个方法是LL(1)的。
各产生式的SELECT集合有：
SELECT(E->TE')=FIRST(T)={(,a,b,^};
SELECT(E'->+E)={+};
SELECT(E'->ε)=FOLLOW(E/)={),#}
SELECT(T->FT')=FIRST(F)={(,a,b,^};
SELECT(T'->T)=FIRST(T)={(,a,b,^};
SELECT(T'->ε)=FOLLOW(T/)={+,),#};
SELECT(F->PF')=FIRST(P)={(,a,b,^};
SELECT(F'->*F')={*};
SELECT(F'->ε)=FOLLOW(F')={(,a,b,^,+,),#};
SELECT(P->(E))={(}
SELECT(P->a)={a}
SELECT(P->b)={b}
SELECT(P->^)={^}
可见，相同左部产生式的SELECT集的交集均为空，所以文法G[E]是LL(1)文法。
(3)构造它的预测分析表。
文法G[E]的预测分析表如下：

【题 3】
考虑下面的文法：
（1） 求出所有语法变量的FIRSTOP集合和LASTOP集合。
（2） 构造文法的算符优先关系表，并判断是否为算符优先文法。
（3） 计算文法的算符优先函数。
（4） 给出表达式和id*(id+id)的算符优先分析过程。

[解答]：
（1） 所有语法变量的FIRSTOP集合和LASTOP集合如下：

（2）文法的算符优先关系表
算符
关 系
算 符
+
-
*
/
(
)
id
+

-

*

/

（

）

id

因为文法中任意两个终结符之间只存在一种关系，因此该文法为算符优先文法。
（3） 文法的算符优先函数
优先函数
算符
+
-
*
/
（
）
id
#
（栈内优先函数）
2
2
4
4
0
4
4
0
（栈外优先函数）
1
1
3
3
5
0
5
0

（4） 表达式的算符优先分析过程

步骤
栈
输入串
优先关系
动作
1
#
+#

2
#
+#
#
移进
3
#F
+#
##
用归约
4
#F+
#

移进+
5
#F+
#

移进
6
#F+F
#
+#
用归约
7
#E
#
#+#
用归约
表达式id*(id+id)的算符优先分析过程
步骤
栈S
优先关系
当前输入字符R
输入字符串
0
#

id
*(id+id)#
1
#id

*
(id+id)#
2
#N

*
(id+id)#
3
#N*

（
id+id)#
4
#N*(

id
+id)#
5
#N*(id

+
id)#
6
#N*(N

+
id)#
7
#N*(N+

id
)#
8
#N*(N+id

)
#
9
#N*(N+N

)
#
10
#N*(N

)
#
11
#N*(N)

#

12
#N*N

#

13
#N
停止
#

2.已知文法 G[S] 为：
S->a|^|(T)
T-> T,S|S
(1) 计算 G[S] 的 FIRSTVT 和 LASTVT 。
(2) 构造 G[S] 的算符优先关系表并说明 G[S] 是否为算符优先文法。
(3) 计算 G[S] 的优先函数。
(4) 给出输入串 (a,a)# 的算符优先分析过程。
解：（1）各符号的FIRSTVT和LASTVT：

（2）算符优先关系表：

因为文法中任意两个终结符之间只存在一种关系，因此该文法为算符优先文法。
（3）对应的算符优先函数为：

（4）句子(a,a)#分析过程如下：

[知识点]
FIRSTVT 及 LASTVT 求法
构造集合 FIRSTVT （ P ）的两条规则。
（i）若有产生式 P→a… ，或 P→Qa… ，则 a ∈ FIRSTVT （ P ）。
（ii）若 a ∈ FIRSTVT （ P ），且有产生式 P→Q… ，则 a ∈ FIRSTVT （ P ）。
构造集合 FIRSTVT （ P ）的两条规则
（i）有产生式P→…a，或P→…aQ，则a∈LASTVT（P）。
（ii）若 a ∈ LASTVT （ Q ），且有产生式 P→Q… ，则 a ∈ FIRSTVT （ P ）。
【题 4】
1. 令文法G：S→ BB B→ aB B→ b 判断该文法是否LR（1）文法，若是构造LR（1）分析表。
解1）将文法G拓广为G`：（0）S`→S （1）S→BB （2）B→Ab （3）B→b
2)求出G`的非终结符的FOLLOW和FIRST集
A
FOLLOW(A)
FIRST(A)
S`
#
a,b
S
#
a,b
B
a,b,#
a,b
3）构造个G`的LR(1)的项目集族及GO函数
I5:S→BB.,#
I2:S→B.B,#
B→.Ab,#
B→.b,#
I1:S`→S.,#
B

I7:B→b.,#
I6:B→a.B,#
B→.Ab,#
B→.b,#
S B a b
I0:S`→.S,#
S→.BB,#
B→.aB,a|b
B→.b,a|b

I9:B→aB.,#
B
I3:B→a.B,a|b
B→.aB,a|b
B→.b,a|b
a
a a
I8:B→aB.,a|b
B
b
I4:B→b.,a|b

b

3)判断文法是否为LR（1）文法。
该文法构出的C＝{I0, I1, I2, I3, I4, I5, I6, I7, I8, I9}中，每个状态集均无冲突，所以该文法是LR（1）文法。
4）构造LR(1)分析表
状态
ACTION
GOTO
a
b
#
S
B
0
S3
S4

1
2
1

acc

2
S6
S7

5
3
S3
S4

8
4
r3
r3

5

r1

6
S6
S7

7

r3

8
r2
r2

9

r2

填空题
1.消除左递归（P124）
文法左递归问题:一个文法是含有左递归的，如果存在非终结符P。
u 直接消除见诸于产生式中的左递归：
假定关于非终结符P的规则为P→Pa | b,其中b不以P开头。那么，我们可以把P的规则等价地改写为如下的非直接左递归形式：
P→bP¢
P¢→aP¢|e
一般而言，假定关于P的全部产生式是P→Pa1 | Pa2 | … | Pam | b1 | b2|…|bn,其中，每个a都不等于e，而每个b都不以P开头,那么，消除P的直接左递归性就是把这些规则改写成：
P→b1P¢ | b2P¢ | … | bnP¢
P¢→a1P¢ | a2P¢ |… | amP¢ | e
[例] 文法
E→E＋T | T
T→T*F | F
F→(E) | i
经消去直接左递归后变成：
E→TE¢
E¢→+TE¢ | e
T→FT¢
T¢→*FT¢ | e
F→(E) | i
例如文法
S→Qc|c
Q→Rb|b
R→Sa|a
虽没有直接左递归，但S、Q、R都是左递归的 SÞQcÞRbcÞSabc
u 一个文法消除左递归的条件：
1) 不含以e为右部的产生式（无空产生式）；
2) 不含回路。
u 消除左递归的算法：
1. 把文法G的所有非终结符按任一种顺序排列成P1，P2，…，Pn；按此顺序执行；
2. FOR i:=1 TO n DO
BEGIN
FOR j:=1 TO i-1 DO
把形如Pi→Pjg的规则改写成
Pi→d1g|d2g|…|dkg ;
(其中Pj→d1|d2|…|dk是关于Pj的所有规则)
消除关于Pi规则的直接左递归性
END
3. 化简由2所得的文法。即去除那些从开始符号出发永远无法到达的非终结符的产生规则。
[例] 考虑文法G(S)
S→Qc|c
Q→Rb|b
R→Sa|a
令它的非终结符的排序为R、Q、S。对于R，不存在直接左递归。
把R代入到Q的有关候选后，把Q的规则变为Q→Sab | ab | b，现在的Q不含直接左递归。
把Q代入到S的有关候选后，S变成S→Sabc | abc | bc | c，由于S→Sabc | abc | bc | c存在直接左递归，消除S的直接左递归后：
S→abcS¢ | bcS¢ | cS¢
S¢→abcS¢ | e
Q→Sab |ab | b
R→Sa|a
关于Q和R的规则已是多余的，化简为：
S→abcS¢ | bcS¢ | cS¢
S¢→abcS¢ | e
注意：由于对非终结符排序的不同，最后所得的文法在形式上可能不一样。但不难证明，它们都是等价的。
同样：[例] 考虑文法G(S)
S→Qc|c
Q→Rb|b
R→Sa|a
非终结符排序选为S、Q、R，那么，
R →Qca|ca|a
R →Rbca|bca|ca|a
最后所得的无左递归文法是：
S→Qc | c
Q→Rb | b
R→bcaR¢ | caR¢ |a R¢
R¢→ bca R¢ | e
不同排序所得的文法的等价性是显然的。
2. 文法的分类(Chomsky体系)（P41）
（1）短语结构文法（PSG）
如果G满足文法定义的要求，则Ｇ是０型文法（短语结构文法PSG: Phrase Structure Grammar ）。
L(G)为PSL。
（1）上下文有关文法(CSG)
如果对于，均有|β|≥|α|成立(Ｓ→ε除外)，则称Ｇ为１型文法。即：上下文有关文法（CSG）
L(G)为1型/上下文有关/敏感语言(CSL)。其他定义方法：设文法G[S]，若P中任一产生式α→β的形式为→ ,其中,β,∈(V∪T）*,β≠ε,A ∈V。
（2） 上下文无关文法(CFG)
如果对于，均有|β|≥|α|，并且α∈V成立，则称G为２型文法。即：上下文无关文法(CFG:)
L(G)为2型/上下文无关语言（CFL），CFG能描述程序设计语言的多数语法成分。
（3）正规（则）文法(RG)
设Ａ,Ｂ∈Ｖ，w∈T+或为，如果对于,均具有如下形式：
右线性(Right Linear)文法：或
左线性(Left Linear)文法：或
都是３型文法(正规文法RG)，L(G)为3型/正规集/正则集/正则语言（RL），能描述程序设计语言的多数单词。左、右线性文法不可混用。
[例]正规文法（RG）：
G1：S®0 | 1 | 00 | 11
G3：S®0 | 1 | 0A | 1B，A ®0，B ®1
G5：S®0 | 0S
G8：A®aS | bS | cS | a | b | c
上下文无关文法（CFG）：
G2：S®A | B | AA | BB, A ®0，B ®1
G4：S®A | B | BB, A ®0，B ®1
G14：S®0 | 1 | 2 | 3 | 0S0 | 1S1 | 2S2 | 3S3
上下文有关文法（CSG）：
G：
S→CD
C→aCA
CA→Ca
CaD→daD
dAc→dec
l Ｇ = (Ｖ，T，Ｐ，Ｓ)是一个文法,α→β ∈ P
* G是0型文法，L(G)是0型语言；---其能力相当于图灵机
* |α|≤|β|:G是1型文法，L(G)是1型语言(除Ｓ→ε);---其识别系统是线性界限自动机
* α∈ＶN : G是2型文法，L(G)是2型语言;---其识别系统是不确定的下推自动机
* A→aB或A→a: G是右线性文法，L(G)是3型语言
A→Ba或A→ａ: G是左线性文法，L(G)是3型语言---其识别系统是有穷自动机
3.逆波兰表示法，请注意IF---ELSE及 FOR循环 的特例
逆波兰表达式又叫做后缀表达式。在通常的表达式中，二元运算符总是置于及之相关的两个运算对象之间，所以，这种表示法也称为中缀表示。波兰逻辑学家J.Lukasiewicz于1929年提出了另一种表示表达式的方法。按此方法，每一运算符都置于其运算对象之后，故称为后缀表示。
将一个普通的中序表达式转换为逆波兰表达式的一般算法是： 　　
(1) 首先构造一个运算符栈，此运算符在栈内遵循越往栈顶优先级越高的原则。 　　
(2) 读入一个用中缀表示的简单算术表达式，为方便起见,设该简单算术表达式的右端多加上了优先级最低的特殊符号“#”。 　　
(3) 从左至右扫描该算术表达式，从第一个字符开始判断，如果该字符是数字，则分析到该数字串的结束并将该数字串直接输出。 　　
(4) 如果不是数字，该字符则是运算符，此时需比较优先关系。做法如下：将该字符及运算符栈顶的运算符的优先关系相比较。如果，该字符优先关系高于此运算符栈顶的运算符，则将该运算符入栈。倘若不是的话，则将栈顶的运算符从栈中弹出，直到栈顶运算符的优先级低于当前运算符，将该字符入栈。 　　
(5)重复上述操作(3)-(4)直至扫描完整个简单算术表达式，确定所有字符都得到正确处理，我们便可以将中缀式表示的简单算术表达式转化为逆波兰表示的简单算术表达式。
逆波兰表达式，它的语法规定，表达式必须以逆波兰表达式的方式给出。逆波兰表达式又叫做后缀表达式。这个知识点在数据结构和编译原理这两门课程中都有介绍，下面是一些例子： 　　
正常的表达式 逆波兰表达式 　　
a+b ---> a,b,+ 　　
a+(b-c) ---> a,b,c,-,+ 　　
a+(b-c)*d ---> a,b,c,-,d,*,+ 　　
a+d*(b-c)--->a,d,b,c,-,*,+ 　　
a=1+3 ---> a=1,3 + 　　
http=(smtp+http+telnet)/1024 --->http=smtp,http,telnet,+,+,1024,/
例9 将下列语句翻译为逆波兰表示(后缀式)、三元式和四元表示：
a:=(b+c)*e+(b+c)/f
【解】解题思路
把中缀式转换为后缀式的简单方法：按中缀式中各运算符的优先规则，从最先执行的部分开始写，一层层套。如a≤b+c∧a＞d∨a+b≠e，先把b+c写为bc+；然后把a≤套上去，成为abc+≤；再把a＞d表示为ad＞；然后把∧套上去，成为abc+≤ad＞∧，依此类推。
［练习］给出下列表达式的逆波兰表示

（１）
（２）
５． 句柄
设有CFG G=(V,T,P,S),G的句型的最左直接短语称为句柄。
附：定义2.27 设有CFG G=(V，T，P，S)，，γ，β∈(V∪T)*，S，Aα，则称α是句型的相对于变量A的短语(phrase)；如果此时有Aα，则称α是句型的相对于变量A的直接短语。在无意义冲突时，简称为句型的直接短语,直接短语也叫做简单短语。
[例] 对于文法的句型来说，它的短语有：，，，。其中直接短语有：，。而就是句型的句柄。
6. 综合属性和继承属性 2012---2013年已经取消这题
如果节点的属性值是通过分析树中该节点或其子节点的属性值计算出来的，则称其为综合属性；如果节点的属性值是由该节点、该节点的兄弟节点或父节点的属性值计算出来的，则称其为继承属性。
[例1] 文法符号的属性有综合属性和继承属性两种。
[例2] S—属性文法中的每个文法符号，只含有综合属性。
[例3] 终结符只有综合属性，它们有词法分析器提供。
7. 语法制导定义，出现在第四大题的最后一步
（0） s'->s{printf（“0”）；}
（1） s->BB {printf（“1”）；}
（2） B->aB {printf（“2”）；}
(3)B->b {printf（“3”）；} 输入#bab# 输出结果是33210
15 / 15