编译原理习题答案(3)

传值: 5 传地址: 42 得结果: 7 传名: 77

143、目标代码有哪几种形式？生成目标代码时通常应考虑哪几个问题？

答：1、汇编语言2、机器语言 又可分为a可立即执行的机器语言b可重定位的机器语言 需要考虑：1.、如何使生成的目标代码最短2、如何分配寄存器的使用

144、下面的推导S ?rm … ? rm ? A b w ? rm ? l ? b w中，最后一步用的是A? l?，分别指出LL（1）方法和LR（1）方法在扫描到此句型的什么位置决定用此产生式？(5分) P79 答： LL(1)扫描到l的时候决定用此产生式；LR(1)扫描到b的时候决定使用次产生式

145、构造一个最简DFA，它接受正规式ab (a|b)*。

给出文法G[S]：S→SaA|A A→AbB|B B→cSd|e

(1)证实AacAbcBaAdbed是文法G[S]的一个句型； (2)请写出该句型的所有短语、素短语以及句柄。

答：1）这里用最右推导表示，省略树S→SaA→SaB→SacSd→SacAd→SacAbBd→SacAbed→SacAbBbed→SacAbcSdbed →SacAbcSaAdbed→SacAbcAaAdbed→SacAbcBaAdbed →AacAbcBaAdbed 2）短语：AacAbcBaAdbed cAbcBaAdbed AbcBaAdbe AbcBaAd cBaAd BaA e A 素短语：BaA e 句柄：A

146、写出表达式a+b*(c-d)对应的逆波兰表示、三元式三地址代码序列和抽象语法树。

147、什么是活动记录？它主要由哪些内容构成？ 148、对下列四元式序列生成目标代码 (10分) T=A-B S=C+D W=E-F U=W/T V=U*S

其中，V是基本块出口的活跃变量，R0和R1是可用寄存器。 答 MOV R0 ，A SUB R0 ，B MOV R1 ，A ADD R1 ，D MOV S ，R1 MOv R1 ，E SUB R1 ，F DIV R1 ，R0 MUL R1 ，S

149、设有如下的三地址码(四元式)序列：

Read N I∶=N J∶=2

———————— L1：if I≤J goto L3 ———————— L2：I∶=I-J

if I>J goto L2

————————

if I=0 goto L4

————————

J∶=J+1 I∶=N goto L1

———————— L3：Print ′YES′

Return

————————

L4：Print ′NO′

Return （1）、对题中代码划分基本块，并给每个基本块一个序号 （2）、画出基本块集合的控制流图，每个基本块就用（1）小题中的序号表示。 （3）、若有循环的话，列出构成每个循环的结点。 150、已知文法G(V)： V →N | N [E]

E →V | V+E

N→i (1)给出与G(V)等价的LL(1)文法G'(V)；

V →NV’ V’ →[E]| ε E →VE’ E’ →+E|ε N→i (2)求文法G'(V)的每个非终结符的FIRST集合和FOLLOW集合； First(V)={i} First(V’)={[ , ε}

First(E)={i} First(E’)={ + , ε} First(N)={i}

Follow(V)={$,+,]} Follow(V’)={$,+,]} Follow(E)={]} Follow(E’)={]} Follow(N)={[ , $ , + }

(3)构造文法G'(V)的LL(1)分析表。 V V’ + V’ →ε [ V’ →[E] ] V’ →ε i V →NV’ $ V’ →ε E E’ N

E’ →+E E’ →ε E →VE’ N→i

151、考虑下面的三地址语句序列： b := 1 b := 2 if w <= x goto L2 ———————— e := b goto L2 ———————— L1: goto L3 ———————— L2: c := 3 b := 4 c := 6

———————— L3: if y <= z goto L4 ———————— goto L5 ———————— L4: g := g + 1 h := 8 goto L1 ———————— L5: h := 9

（1）、在该代码中用水平的横线将代码分成基本块，并给每个基本块一个序号。 （2）、画出该代码的控制流图，每个基本块就用（1）小题中的序号表示。 （3）、若有循环的话，列出构成每个循环的结点。

152、对于文法G(S)：

S ?bMbM ?(L|a L ?Ma)(1) 写出句型b(Ma)b的最右推导并画出分析树。 S→bMb→b(Lb→b(Ma)b

(2) 写出上述句型的短语，直接短语和句柄。 短语：b(Ma)b (Ma) Ma) 句柄：Ma) 153、LL(1)分析法对文法有哪些要求？

对文法中任意A→α|β型产生式需满足： First(α)∩First(β)=空集

若β=>ε 则First(α)∩Follow(A)=空集

154、写出语句a:=b*(-c)+b*(-c)的后缀式、抽象语法树、DAG图、四元式三地址代码和三元式三地址代码。

155、设有文法G[A]： A → iB*e B → SB | ε S → [eC] | . i C → eC | ε

判定该文法是否为LL(1)文法？若是则给出它的LL(1)分析表，否则说明理由。 (20分) First(A)={i} First(B)={[ , ε , . } First(S)={ [ , . } First(C)={e, ε}

Follow(A)={$} Follow(B)={*} Follow(S)={*} Follow(C)={]} 对产生式B → SB | ε

First(SB)=First(S)= { [ , . } First(ε)={ ε} 所以First(SB)∩First(ε)=空集 First(SB)∩Follow(B)=空集 对产生式S → [eC] | . i

First([eC])= { [} First(. i)={ . i } 所以First([eC])∩First(. i)=空集 对产生式C → eC | ε

First(eC) { e } First(ε)={ ε} 所以First(eC)∩First(ε)=空集 First(eC)∩Follow(C)=空集 所以此文法是LL(1)文法 A B S C . S →. i * i [ ] e C → eC $ A→ iB*e B → SB B → ε B → SB S→ [eC] C →| ε

156、构造一个DFA，它接受∑={0，1}上能被5整除的二进制数。

157、正规式 (0 | 1)* 和 ( (? | 0) 1* )*是否等价，说明理由。

158、写出字母表? = {a, b}上语言L = {w | w的最后两个字母是aa或bb}的正规式，并画出接受该语言的最简DFA。 (a|b)*aa|bb 159、文法G(S)及其LR分析表如下，请给出串baba$的分析过程。

(1) S → DbB (4) B → a

(2) D → d

(3) D → ε (6) B → ε

(5) B → Bba

LR分析表

0 1 2 3 4 5 6 7 8 ACTION b r3 s4 r2 r6 r4 s7 r5 d s3 a S5 S8 $ acc r6 r4 r1 r5 GOTO S 1 B 6 D 2

(注：答案格式为 步骤 栈 步骤 1 2 3 4 5 6 7 8 9 栈 0 0D2 0D2b4 0D2b4a5 0D2b4B6 0D2b4B6b7 0D2b4B6b7a8 0D2b4B6 0S1 输入串 动作) 输入串 动作) 按B → ε规约 移进 移进 按B → a规约 移进 移进 按B → Bba规约 按S → DbB规约 接受 baba$ baba$ aba$ ba$ ba$ a$ $ $ $

160、已知文法G(A)： A → aABl | a

B → Bb | d

(1)消除文法中的左递归，提取公共左因子，给出与G(A)等价的LL(1)文法G'(A)； (2)求文法G'(A)的每个非终结符的FIRST集合和FOLLOW集合； (3)构造文法G'(A)的LL(1)分析表。

答：1）A →aA’ A’→ABl|ε B → dB’ B’ →bB’ |ε

2) First(A)={a} First(B)={d} First(A’)={a, ε} First(B’)={b, ε} Follow(A)={$,d} Follow(B)={l} Follow(A’)={$,d} Follow(B’)={l} 3) a b l d $ A A →aA’ A’→ABl A’→ε A’→ε A’ B B’ →bB’ B’ →ε B’ 161、设文法G(S)：

S→S+aF | aF | +aF F→*aF | *a

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库编译原理习题答案(3)在线全文阅读。