期末复习——简答题、分析题 联系客服

发布时间 : 星期三 文章期末复习——简答题、分析题更新完毕开始阅读

(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 的顺序重写代码可得优化代码为: