(2)构造预测分析表如下： S S’ E

5. 已知文法G(E)为：

E->TE’ E’->+TE’|ε T ->FT’ T’->*FT’|ε F->(E)|i 其预测分析表为： E E’

a S->a b E->b e S’->eS i t # S’->? S->iEtSS’ iE→TE’+E’→+TE’*(E→TE’)E’→ε#E’→εTT →FT’T’→εF→iT’→*FT’T →FT’T’→εF→(E)T’→εT’ F分析i+i*i是否为该文法的句子，写出分析过程 分析过程：见书P91

分析成功，所以i+i*i是文法所描述的语言中的句子

第 9 页 共 13 页

6. 将下列DFA，消去其无关状态 Q 1 2 3 4 5 6 7 8 9 （2）标记非无关状态 第一步，标记1

第二步，由f(1,a)=5,f(1,b)=2，标记5和2 由f(5,a)=6，标记6 由f(2,b)=3，标记3 由f(6,b)=9，标记9 由f(3,a)=8，标记8 9未产生新标记 由f(8,a)=9，没有新标记

不再有未处理的标记状态，所以非无关状态为：1、2、3、5、6、8、9 （3）删除未标记的状态，未标记的状态有：4、7，删除状态4、7及相关的转移得

第 10 页 共 13 页

5aa6bb1ba3b782a9a4（1）消除无关状态前的状态表为： a 5 8 7 6 9 b 2 3 9 9 到下表所示的状态表 Q 1 2 3 5 6 8 9

消除无关状态后的状态图为：

7. 有如下基本块 S0：=2 S1：=3/S0 S2：=T-C S3：=T+C R：=S0/S3 H：=R S4：=3/S1 S5：=T+C

第 11 页 共 13 页

a 5 8 6 9 b 2 3 9 5aa6bb1ba382a9S6：=S4/S5 H：=S6*S2

应用DAG对其进行优化，写出优化后的基本块中四元式 答案

（1）构造DAG：

n8*Hn7/R,H,S6n6+S3,S5n5S2-n12S0：=2 S4：=2 S1：=1.5 S2：=T-C S3：=T+C S5：=S3 R：=2/S3 S6：=R H：=S6*S2

(3)进一步优化，优化后的代码为： S2：=T-C S3：=T+C

第 12 页 共 13 页

S0,S4n21.5S1n3Tn4C（2）利用 DAG 进行优化：按照构造 DAG 的顺序重写代码可得优化代码为：