编译原理第二第五章答案.docx
《编译原理第二第五章答案.docx》由会员分享，可在线阅读，更多相关《编译原理第二第五章答案.docx（12页珍藏版）》请在冰点文库上搜索。
编译原理第二第五章答案
第五章
第5章自顶向下语法分析方法
练习（P99）
1.文法
S->a|^|（T）
T->T,S|S
（1）对（a,（a,a）和（（（a,a）,^,（a））,a）的最左推导。
（3）经改写后的文法是否为LL
（1）的给出它的预测分析表。
（4）给出输入串（a,a）#的分析过程，并说明该串是否为G的句子。
（1）对（a,（a,a）的最左推导为：
S=>（T）
=>（T,S）=>（S,S）=>（a,S）=>（a,（T））
=>（a,（T,S））
=>（a,（S,S））
=>（a,（a,S））=>（a,（a,a））
对（（（a,a）,^,（a））,a）的最左推导为
S=>（T）=>（T,S）=>（S,S）=>（（T）,S）
=>（（T,S）,S）
=>（（T,S,S）,S）
=>（（S,S,S）,S）=>（（（T）,S,S）,S）=
>（（（T,S）,S,S）,S）
=>（（（S,S）,S,S）,S）
=>（（（a,S）,S,S）,S）=>（（（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
a
^
（
）
N
ε
）
对左部为N2的产生式可知：
FIRST（->,SN2）={，}FIRST（->ε）={ε}FOLLOW（N2）={）}
{，}∩{）}=?
所以文法是LL
（1）的。
预测分析表
a
^
（
）
#
S
->a
->^
->（T）
T
->SN
->SN
->SN
N
->ε
->,SN
也可由预测分析表中无多重入口判定文法是LL
（1）的。
（4）对输入串（a,a）#的分析过程为：
步骤
状态栈
当前字符
剩余输入串
操作
1
#S
（
a,a）#
S->（T）
2
#）T（
（
a,a）#
匹配
3
#）T
A
a）#
T->SN2
4
#）N2S
A
a）#
S->a
5
#）N2a
A
a）#
匹配
6
#）N2
a）#
N2->,SN2
7
#）N2S,
a）#
匹配
8
#）N2S
a
）#
S->a
9
#）N2a
a
）#
匹配
10
#）N2
）
#
N2->ε
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′）=FIRST（T）={（，a，b，^}SELECT（E′→+E）=FIRST（+E）={+}
SELECT（E′→ε）=（FIRST（ε）-{ε}）∪FOLLOW（′E）=FOLLOW（E′）={#，）}SELECT（T→FT′）=FIRST（FT′）=FIRST（F）={（，a，b，^}
SELECT（T′→T）=FIRST（T）={（，a，b，^}
SELECT（T′→ε）=（FIRST（ε）-{ε}）∪FOLLOW（′T）=FOLLOW（T′）={#，+，）}SELECT（F→PF′）=FIRST（PF′）=FIRST（P）={（，a，b，^}SELECT（F′→*F′）=FIRST（*F′）=FIRST（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集可以构造该文法的预测分析表如下：
+
（
）
a
b
^
#
E
→TE′
→TE′
→TE′
→TE′
E′
→+E
→ε
→ε
T
→FT′
→FT′
→FT′
→FT′
T′
→ε
→T
→ε
→T
→T
→T
→ε
F
→PF′
→PF′
→PF′
→PF′
F′
→ε
→*F′
→ε
→ε
→ε
→ε
→ε
→ε
P
→（E）
→a
→b
→^
voidP（）
{Getchar（）;
if
ch='（'
{
E（）;
Getchar（）;if
ch='
）'Getchar（）;}
else
ifch='a'
Getchar（）;
else
ifch='b'
Getchar（）;
elseerror（）,
}
}
voidF'（）{Getchar（）;
ifch='*'
F'（）;elseerror（）;
}
F'（）;
}
voidF（）
{
P（）;
F'（）;
}
voidT'（）{
T（）;
}
（4）不妨约定:
在进入一个非终结符号相应的子程序前，已读到一个单词ch：
存放当前
读到的单词，Getchar（）为一子程序，每调用一次，完成读取一单词的任务，Error（）为出错处理程序。
4.证明下述文法不是LL
（1）文法。
S->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）文法。
该文法含公共因子，消除后的文法为：
S->C$
C->bA|aB
A->aA'|bAA
A'->C|ε
B->bB'|aBB
B'->C|ε
【证明】因为SELECT（C->bA）∩SELECT（C->aB）=Φ
SELECT（A->Aa）∩SELECT（A->bAA）=Φ
SELECT（A'->C）∩SELECT（A'->ε）=（FIRST（C）-{ε}）∩FOLLOW（'A）≠Ф因此消除公共因子后得到文法也不是LL
（1）文法。
7．对于一个文法若消除了左递归，提取了左公共因子后是否一定为LL
（1）文法试对下面文
法进行改写，并对改写后的文法进行判断。
（1）A->baB|ε[1]
B->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|ε
B->Abb|a
先改写文法为：
0）A->baB
1）A->ε
2）B->baBbb
3）B->bb
4）B->a再改写文法为：
0）A->baB
FIRST
FOLLOW
A
{b}
{#}
B
{b,a}
{#,b}
N{b,a}{#,b}1）A->ε
2）B->bN
3）B->a
4）N->aBbb
5）N->b
预测分析表
a
b
#
A
->baB
->ε
B
->a
->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→aA′
A′→Abe|ε
B→dB′
B′→bB′|ε对此改写后的文法进行判断其是否是LL
（1）文法。
由分析得可推导出ε的非终结符表为：
A
A′
B
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）
（2）
A→bBA′
A′→aBA′|ε
B→ab
此文法中的
（1），
（2）产生式存在隐含的左公因子，消除隐含的左公因子后文法变成如下的形式：
S→bS′
S′→BA′a|ε
A→bBA′
A′→aBA′|ε
B→ab此形式中A→bBA′是不可达的产生式，是多余的，所以应将其去掉。
所以文法最终改写成的形式为：
S→bS′
S′→BA′a|ε
A′→aBA′|ε
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题：
S->AS|b
A->SA|a该文法含间接左递归，因此运用间接左递归的算法对文法进行改写后的文法为：
S->AS|b
A->bAA'|aA'
A'->SAA'|ε
SELECT（S->AS）∩SELECT（S->b）={b,a}∩{b}≠Φ,∴此改写后的文法不是LL
（1）的。
升级会员 