编译原理第二版第五章答案Word格式文档下载.docx
《编译原理第二版第五章答案Word格式文档下载.docx》由会员分享，可在线阅读，更多相关《编译原理第二版第五章答案Word格式文档下载.docx（13页珍藏版）》请在冰点文库上搜索。
（（（a,a）,S,S）,S）=>
（（（a,a）,^,S）,S）=>
（（（a,a）,^,（T））,S）=>
（（（a,a）,^,（S））,S）=>
（（（a,a）,^,（a））,S）=>
（（（a,a）,^,（a））,a）
（3）改写文法为：
0）S->
a
1）S->
^
2）S->
（T）
3）T->
SN
4）N->
SN
5）N->
ε
FIRST
FOLLOW
S
a^（
#,）
T
）
N,ε）
对左部为N2的产生式可知：
FIRST（->
SN2）={，}FIRST（->
ε）={ε}FOLLOW（N2）={）}{，}∩{）}=?
所以文法是LL
（1）的。
预测分析表
（
#
->
N
也可由预测分析表中无多重入口判定文法是LL
（1）的。
（4）对输入串（a,a）#的分析过程为：
步骤
状态栈
当前字符
剩余输入串
操作
1
#S
a,a）#
2
#）T（
匹配
3
#）T
A
a）#
SN2
4
#）N2S
5
#）N2a
6
#）N2
a）#
N2->
SN2
7
#）N2S,
8
）#
9
10
11
#）
12
可见输入串（a,a）#是文法的句子。
2．对下面的文法G：
E→TE′
E′→+E|ε
T→FT′
T′→T|ε
F→PF′
F′→*F′|ε
P→（E）|a|b|^
（1）计算这个文法的每个非终结符的FIRST集和FOLLOW集。
（2）证明这个文法是LL
（1）的。
（3）构造它的预测分析表。
（4）构造它的预测下降分析程序
【解】
（1）由题意分析得可推导出ε的非终结符表为：
各非终结符的FIRST集为：
FIRST（E）=FIRST（T）={（，a，b，^}FIRST（E′）={+∪}{ε}={+，ε}FIRST（T）=FIRST（F）={（，a，b，^}
FIRST（T′）=FIRST（T）∪{ε}={（，a，b，^，ε}
FIRST（F）=FIRST（P）={（，a，b，^}FIRST（F′）={*∪}{ε}={*，ε}FIRST（P）={（，a，b，^}
∴最终求得各非终结符的FIRST集为：
FIRST（E）={（，a，b，^}FIRST（E′）={，+ε}FIRST（T）={（，a，b，^}
FIRST（T′）={（，a，b，^，ε}FIRST（F）={（，a，b，^}FIRST（F′）={，*ε}FIRST（P）={（，a，b，^}
各非终结符的FOLLOW集为：
FOLLOW（E）={#}∪FOLLOW（E′）∪{）}
FOLLOW（E′）=
FOLLOW（E）
FOLLOW（T）=
FOLLOW（T′）
∪（FIRST（E′-{）ε}∪）FOLLOW（E）
FOLLOW（T′）=
FOLLOW（T）
FOLLOW（F）=
（FIRST（T′-{）
ε}∪）FOLLOW（T）
FOLLOW（F′）=
FOLLOW（F）
∪FOLLOW（F′）
FOLLOW（P）=（FIRST（F′-{）ε}∪）FOLLOW（F）∴最终求得各非终结符的FOLLOW集为：
FOLLOW（E）={#，）}FOLLOW（E′）={#，）}FOLLOW（T）={#，+,）}
FOLLOW（T′）={#，+，）}FOLLOW（F）={（，a，b，^，#，+，）}
FOLLOW（F′）={（，a，b，^，#，+，）}FOLLOW（P）={*，（，a，b，^，#，+，）}
（2）各产生式的SELECT集为：
SELECT（E→TE′）=FIRST（TE′F）=IRST（T）={（，a，b，^}
SELECT（E′→+E）=FIRST（+E）={+}
SELECT（E′→ε）=（FIRST-（{ε）}∪）FOLLOW（E′）=FOLLOW（E′）={#，）}
SELECT（T→FT′）=FIRST（FT′F）=IRST（F）={（，a，b，^}
SELECT（T′→T）=FIRST（T）={（，a，b，^}
SELECT（T′→ε）=（FIRST（-{ε）}∪）FOLLOW（T′）=FOLLOW（T′）={#，+，）}
SELECT（F→PF′）=FIRST（PF′F）I=RST（P）={（，a，b，^}
SELECT（F′→*F′）=FIRST（*FF′IR）S=T（P）={*}
SELECT（F′→ε）=（FIRST（-{ε）}∪）FOLLOW（F′）=FOLLOW（F′）={（，a，b，^，#，+，）}
SELECT（P→（E））=FIRST（（E））={（}
SELECT（P→a）=FIRST（a）={a}
SELECT（P→b）=FIRST（b）={b}
SELECT（P→^）=FIRST（^）={^}∴由以上结果得相同左部产生式的SELECT交集为：
SELECT（E′→+E）∩SELECT（E′→ε{）+=}∩{#，）}SELECT（T′→T）∩SELECT（T′→ε{）（=，a，b，^）∩{#，+，）}=ΦSELECT（F′→*F′∩）SELECT（F′→ε）={*∩}{（，a，b，^，#，+，）}=Φ
SELECT（P→（E））∩SELECT（P→a）∩SELECT（P→b∩）SELECT（P→^）={（}∩{a}∩{b}∩{^Φ}=∴相同左部产生式的SELECT集合的交集为空。
∴这个文法是LL
（1）的。
（3）由以上算出的SELECT集可以构造该文法的预测分析表如下：
+
b
E
→TE′
→TE′
E′
→+E
→ε
→FT′
→FT′
T′
→T
F
→PF′
F′
→*F′
P
→（E）
→a
→b
→^
voidP（）
{Getchar（）;
ifch='
（'
{E（）;
Getchar（）;
ifch=elseifch='
a'
'
）'
Getcha
r（）;
}
Getchar（）;
elseifch='
b'
elseerror（）,
voidF'
（）
*'
F'
（）;
elseerror（）;
}
voidF（）
{
P（）;
}voidT'
（）{
T（）;
ch：
存放当前读
Error（）为出错处理
（4）不妨约定:
在进入一个非终结符号相应的子程序前，已读到一个单词到的单词，Getchar（）为一子程序，每调用一次，完成读取一单词的任务，程序。
4.证明下述文法不是LL
（1）文法。
C$
C->
bA|aB
A->
a|aC|bAA
B->
b|bC|aBB你能否构造一等价的文法，使其是LL
（1）？
并给出判断过程。
【解】因为SELECT（A->
a）∩SELECT（A->
aC）≠Ф,根据LL
（1）文法的判定条件：
（1）文法不含左递归
（2）对于文法U的任意两个不同的规则有:
Select（U→α）∩Select（U→）=Φ一个文法若满足以上条件，称该文法G为LL
（1）文法。
得出该文法不是LL
（1）文法。
该文法含公共因子，消除后的文法为：
aA'
|bAA
A'
C|ε
bB'
|aBB
B'
【证明】因为SELECT（C->
bA）∩SELECT（C->
aB）=Φ
SELECT（A->
Aa）∩SELECT（A->
bAA）=Φ
SELECT（A'
C）∩SELECT（A'
ε）=（FIRST（C）-{ε}）∩FOLLOW（'
A）≠Ф
因此消除公共因子后得到文法也不是LL
（1）文法。
LL
（1）文法？
试对下面
7．对于一个文法若消除了左递归，提取了左公共因子后是否一定为
文法进行改写，并对改写后的文法进行判断。
（1）A->
baB|ε[1]
Abb|a[2]
（2）A→aABe|a[1]
B→Bb|d[2]
（3）S→Aa|b[1]
A→SB[2]
B→ab[3]
【解】
对于一个文法若消除了左递归，提取了左公因子后不一定是LL
（1）文法。
1题：
A->
baB|ε
Abb|a
先改写文法为：
0）A->
baB
1）A->
2）B->
baBbb
3）B->
bb
4）
a再改写文法为：
B
bN
N->
aBbb->
b由预测分析表中无多重入口判定文法是LL
（1）的。
2题：
[2]将产生式[1]提取左公因子后得：
A→a（ABe|ε）进一步变换为文法G1：
A→aA′
A′→Abe
A′→ε
B→Bb|d消除
（2）中的直接左递归，将B→Bb|d变换为：
B→dB′
B′→bB′|ε该文法最终改写成的形式为：
A′→Abe|ε
B→dB′
B′→bB′|ε
对此改写后的文法进行判断其是否是LL
（1）文法。
由分析得可推导出ε的非终结符表为：
A′
B′
否
是
各非终结符的FIRST集为：
FIRST（A）={a}
FIRST（A′）=FIRST（A）∪{ε}={a，ε}
FIRST（B）={d}FIRST（B′）={b}∪{ε}={b，ε}各非终结符的FOLLOW集为：
FOLLOW（A）={#}∪（FIRST（B）-{ε}）={#，d}
FOLLOW（A′）=FOLLOW（A）={#，d}
FOLLOW（B）={e}
FOLLOW（B′）=FOLLOW（B′）∪FOLLOW（B）={e}
各产生式的SELECT集为：
SELECT（A→aA′）=FIRST（aA′）={a}
SELECT（A′→ABe）=FIRST（ABe）=FIRST（A）={a}
SELECT（A′→ε）=（FIRST（-{εε）}∪）FOLLOW（A′）=FOLLOW（A′）={#，d}
SELECT（B→dB′）=FIRST（dB′）={d}
SELECT（B′→bB′）=FIRST（bB′{b}）=
SELECT（B′→ε）=（FIRST（-{εε）}∪）FOLLOW（B′）=FOLLOW（B′）={e}由以上结果得相同左部产生式的SELECT交集为：
SELECT（A′→ABe）∩SELECT（A′→ε）={a}，∩d}{=#ΦSELECT（B′→bB′∩）SELECT（B′→ε）{=b}∩{e}=Φ∴相同左部产生式的SELECT集合的交集为空。
∴改写后的文法是LL
（1）的。
3题：
该文法的非终结符S，A为间接左递归，以S，A，B为序消除一切左递归。
将
（1）的右部代入
（2）得：
A→AaB|bB消除其直接左递归得：
A→bBA′A′→aBA′|ε此时文法变成如下形式：
S→Aa|b
（1）
A→bBA′
（2）
A′→aBA′|εB→ab此文法中的
（1），
（2）产生式存在隐含的左公因子，消除隐含的左公因子后文法变成如下的形式：
S→bS′
S′→BA′a|ε
A→bBA′
A′→aBA′|ε
B→ab
此形式中A→bBA′是不可达的产生式，是多余的，所以应将其去掉。
所以文法最终改写成的形式为：
B→ab相同左部产生式的SELECT集为：
SELECT（S′→BA′a）={a}SELECT（S′→ε）={#}SELECT（A′→aBA′）={a}
SELECT（A′→ε）={a}相同左部产生式的SELECT交集为：
SELECT（S′→BA′a）∩SELECT（S′→ε）={a}=Φ∩{#}
SELECT（A′→aBA′）∩SELECT（A′→ε）={a}∩≠Φ{a}∴关于A′的相同左部其产生式的SELECT集的交集不为空∴此改写后的文法不是LL
（1）的。
4题：
AS|b
SA|a该文法含间接左递归，因此运用间接左递归的算法对文法进行改写后的文法为：
S->
bAA'
|aA'
SAA'
|ε
LL
（1）的。
SELECT（S->
AS）∩SELECT（S->
b）={b,a}∩{b}≠∴Φ此,改写后的文法不是
升级会员 