传值: 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