编译作业答案.docx

Standardization of sany group #QS8QHH-HHGX8Q8-GNHHJ8-HHMHGN#
编译作业答案
7-2给定文法G：
SAa|Ab|c
AAd|Se|f
请消除文法的左递归，并提取公共左因子。
解：
（1）消除文法G的②产生式直接左递归。
A→SeA' | fA' ③
A'→dA' | ④
（2）消除间接左递归：按排序（按算法i=2,j=1时）将S的①产生式代入③有
A→AaeA' | AbeA' | ceA' | fA' ⑤
（3）消除⑤的直接左递归有
A→ceA'A" | fA'A" ⑥
A"→aeA'A" | beA'A" | ⑦
（4）对S的①产生式提公因子有
S→AB | c ⑧
B→| a | b ⑨
（5）最后，文法G提取公因子，消除左递归后的产生式由⑧, ⑨, ⑥, ⑦和④组成，无
多余的产生式。
（6）若按排序，得到的产生式组合是另外的形式，但它们是等价的文法。
7-3给定文法G：
S(L)|a
LL，S|S
消除文法G的左递归，并写出递归下降分析的相应递归过程。
解：
消除左递归后，得文法G':
S→(L) | a
L→SL'
L'→, SL' |
递归下降过程：
procedure advance( )
begin
sym =getchar( )
end
procedure S;
begin
if sym ='a' then advance( )
else if sym ='(' then
begin
advance( )
L( );
if sym =')' then advance( ) else error()
end
else
error()
end
procudure L;
begin S;
L';
end
procudure L';
begin
if sym =',' then begin
advance( )
S;
L'
end
end
7-5解：
（1）G'（S）：S→AS'
S'→:AS' |
A→BA'
A'→+BA'|
B→bS* | a
（2）FIRST集和FOLLOW集
FIRST
FOLLOW
S
b，a
#，*
S'
:，
#，*
A
b，a
#，*，:
A'
+，
#，*，:
B
b，a
#，*，:，+
预测分析表
a
:
+
b
*
#
S
S→AS'
S→AS'
S'
S'→:AS'
S'→
S'→
A
A→BA'
A→BA'
A'
A→
A→+BA'
A→
A→
B
B→a
B→bS*
（3）因为预测分析表无多重定义入口，所以G'是LL（1）文法。
7-6解：
对****题7-3的文法G消除左递归后，得文法G'：
S→(L) | a
L→SL'
L'→,SL' |
FIRST集和FOLLOW集
FIRST
FOLLOW
S
(，a
)，’，#
L
(，a
)
L'
’，
)
预测分析表
（
）
a
,
#
S
S→(L)
S→a
L
L→SL'
L→SL'
L'
L'→)
L'→,SL'
因为预测分析表无多重定义入口，所以文法G是LL（1）文法。
8-1
已知文法G：
SAB
AAb|bB
Ba|Sb
（1）写出bBABb的规范推导。
（2）画出bBABb的语法树。
（3）求bBABb的短语、直接短语、句柄和最左素短语。
解：
（1）规范规范推导（最右推导）最右推导SABASbAABbbBABb
（2）语法树（推导树）
（3）短语 bB, AB, ABb, bBABb
直接短语 bB, AB
句柄 bB