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