当前位置:首页 >> 其它课程 >>

编译原理题库——综合题


编译原理 A 卷 已知文法 A->aAd|aAb| ε 判断该文法是否是 SLR(1) 文法,若是构造相应分析表,并对输入串 ab# 给出分析过程。 解:增加一个非终结符 S/后,产生原文法的增广文法有: S'->A A->aAd|aAb|ε 下 面 构 造 它 的 LR(0) 项 目 集 规 范 族 为 :

从 上 表 可 看 出

, 状 态 I0 和 I2 存 在 移 进 - 归 约 冲 突 , 该 文 法 不 是 LR(0) 文 法 。 对 于 I0 来 说 有 : FOLLOW(A)∩{a}={b,d,#}∩{a}=Φ,所以在 I0 状态下面临输入符号为 a 时移进,为 b,d,#时归约,为其他时 报错。对于 I2 来说有也有与 I0 完全相同的结论。这就是说,以上的移进-归约冲突是可以解决的,因此该 文法是 SLR(1)文法。 其 SLR(1)分析表为:

第 1 页共 6 页

对输入串 ab#给出分析过程为:

编译原理 B 卷 构造下述文法 G[S] 的自动机: S->A0 A->A0|S1|0 该自动机是确定的吗?若不确定,则对它确定化。 解:由于该文法的产生式 S->A0,A->A0|S1 中没有字符集 VT 的输入,所以不是确定的自动机。 要将其 他 确 定 化 , 必 须 先 用 代 入 法 得 到 它 对 应 的 正 规 式 。 把 S?A0 代 入 产 生 式 A?S1 有 : A=A0|A01|0=A(0|01)|0=0(0|01)*。 代入 S->A0 有该文法的正规式:0(0|01)*0,所以,改写该文法为确定的

自动机为: 由于状态 A 有 3 次输入 0 的重复输入,所以上图只是 NFA,下面将它确定化: 下 DFA: 表 由 子 集 法 将 NFA 转 换 为

第 2 页共 6 页

由上表可知 DFA 为: 编译原理 C 卷

6.(20 分)已知上下文无关文法: S → L=R | R L → *R | id R → L (1) 请构造非终结符的 FIRST 和 FOLLOW 集合。 分) (5 (2) 构造该文法的 LL(1)分析表。该文法是 LL(1)文法吗?(15 分 7. (20 分)考虑以下文法: S → A A → BA | ε B → aB| b 证明该文法是 LR(1)的。 (1)证明它是 LR(1)文法; (2)构造它的 LR(1)分析表。 7.(20 分)阅读下面的 LEX 程序,并回答: (1)该程序完成了什么功能? (2)修改该程序,使之能够计算输入的标识符个数。(直接改在试题上) LEX程序如下:
%{ # include <stdio.h> int num_int = 0; int num_float = 0; int num_line = 0; int num_id = 0; %} digit [0-9]
第 3 页共 6 页

integer flt letter id %%

[+\-]?{digit}+ [+\-]?{digit}+\.{digit}+ [a-zA-z] {letter}({letter}|{digit})*

{integer} num_int++ ; {flt} \n . {id} %% main() { yylex() ; printf(“\n%d integers, %d floating point numbers, %d lines, %d identifiers.\n”, num_int, num_float, num_line, num_id) ; } num_float++ ; num_line++ ; ; num_id++;

C 卷答案 6 解:(1)

根据 L → *R | id,可得到 FIRST(L)={*, id}; 根据 R → L,可得到 FIRST(R)= FIRST(L)={*, id}; 根据 S → L=R | R,可得到 FIRST(S)= FIRST(L)? FIRST(R)={*, id}; S 是开始符号,所以有$?FOLLOW(S); 又根据 S → L=R,可得到=?FOLLOW(L); 又根据 S → L=R | R,可得到 FOLLOW(S)?FOLLOW(L); 又根据 L → *R,可得到 FOLLOW(L)?FOLLOW(R); 又根据 R → L,可得到 FOLLOW(R)?FOLLOW(L); 所以有 FOLLOW(S)={$},FOLLOW{L}= FOLLOW{R}={$, =}。

(2) 构造 LL(1)分析表如下: * = id S S → L=R S → L=R S → R S → R L L → *R L → id R R → L R → L 由于分析的表目中存在冲突,该文法不是 LL(1)文法。 7. (20 分)考虑以下文法: S → A A → BA | ε
第 4 页共 6 页

$

B → aB| b 证明该文法是 LR(1)的。 (1)证明它是 LR(1)文法; (2)构造它的 LR(1)分析表;

第 5 页共 6 页

7答:该程序完成的功能:计算整数、浮点数的个数,统计行数,并分别输出。

修改见程序。
编译原理 D 卷 7、证明下面文法是 SLR(1)但不是 LR(0)的。 S→A A→Ab∣bBa B→aAc∣a∣aAb 8、证明下面的文法是 LL(1)的但不是 SLR(1)的。 S→AaAb∣BbBa A→ε B→ε 1.构造表达式(4*7+1)*2 的附注语法树。

四、 (20 分)设文法 G[S]为 S ? aAcB 问:1、该文法是否为算符文法,为什么? ? Ab|b A 2、构造算符优先关系表。 ?d B 3、该文法是否可改造为 LL(1)文法,为什么? 五、 (本题 20 分)设文法 G 为: E ? eAf|eBg A ? aA|a B ? Bb|a 对于输入串 eaaaf,采用 LR(0) 、LL(1) 、SLR(1)等方法中合适的一种进行分析。

六、 (25 分)有作控制用的布尔表达式文法 G[E]及其语义动作如下: 1、 构造 SLR(1)分析表(若不是 SLR(1))的,则说明理由) 2、 分析布尔式 a∨b<c 的四元式生成过程,并画出最后的真假链表。 3、 给出语句 IF a∨b<c THEN I:=m*n ELSE I:=m+n 的完整四元式序列。 文法 G[E]: (1)E ? i
?1?

<i

?2 ?

{E.TC:=NXQ;
?1?

E.FC=NXQ+1;
?1?

(2)E ? AE (3)A ? B∨ (4)B ? i 答案: 7 证明:

?1?

GEN(J<,ENTRY(i

),ENTRY(i

?2 ?

),O);GEN(J,
?1?

,

,0)}

{E.FC:=E .FC; E.FC:=MERGE(A.TC ,E .TC)} {BACKPATCH(B.FC ,NXQ); A.TC:=B.TC} {B.TC:=NXQ; B.FC:=NXQ+1; GEN(Jnz, ENTRY(i), ,0); GEN(J, , ,0)}

求该文法的 LR(0)项目集规范族如下: I0={S,A→·bBa} GO(I0,A)={S→A· ,A→A·b }=I1 GO(I0,b)={A→b·Ba,B→·aAc,B→·a,B→·aAb}=I2 GO(I1,b)={A→Ab·}=I3 GO(I2,B)={A→bB·a}=I4 GO(I2,a)={B→a·Ac,B→a· ,B→a·A b,A→·Ab,A→·b Ba}=I5 GO(I4,a)={ A→bBa·}= I6
第 6 页共 6 页

GO(I5,A)={ B→aA·c,B→aA·b,A→A·b}= I7 GO(I5,b)={ A→b·Ba,B→·aAc,B→·a,B→·aAb }= I2 GO(I7,c)={ B→aAc·}= I8 GO(I2,b)={ B→aAb· ,A→Ab·}= I9 考虑 I1,I5 都存在“移进—归约”冲突,所以该文法不是 LR(0)的。 由于 FOLLOW(S)={#},不包含 b,所以 I1 的冲突可以消解;由于 FOLLOW(B)={a},不包含 b,所以 I5 的 冲突可以消解;由于 FOLLOW(B)={a},FOLLOW(A)={c,b,#},二者不相交,所以 I9 的冲突也可以消解。 综上所述,该文法是 SLR(1)的。 8 证明: 因为 FIRST(AaAb)={a},FIRST(BbBa)={b} FIRST(AaAb)∩FIRST(BbBa)=? 所以该文法是 LL(1)的。 求该文法的 LR(0)项目集规范族如下: I0={S’→·S,S→·AaAb,S→·BbBa,A→· ,B→·} I1={S→S·} I2={S→A·aAb} I3={S→B·bBa} I4={S→Aa·Ab,A→·} I5={S→Bb·Ba,B→·} I6={S→AaA·b} I7={S→BbB·a} I8={S→AaAb·} I9={S→BbBa·} 考虑 I0:FOLLOW(A)=FOLLOW(B)={a,b} A→·和 B→·的冲突无法消解,所以该文法不是 SLR(1)的。 1 解:

第 7 页共 6 页

L

E.val = 58

n

T.val = 58

T.val = 29

*

F.val = 2

F.val = 29

digit.lexval= 2

(

E.val = 29

)

E.val = 28

+

T.val = 1

T.val = 28

E.val = 1

*

F.val = 7 digit.lexval=1 11111= 1 digit.lexval = 7

digit.lexval=4

四 答:1、该文法是算符文法。因为其任一产生式的右部都不含相继(并列)的非终结 符,即不含如下形式?QR?的产生式右部。 2、FIRST(S)={a}, FIRST(A)={b}, FIRST(B)={d}, 构造算符优先关系表如下: LAST(S)={c}, LAST(A)={b}, LAST(B)={d}。 (3 分) (5 分) (4 分)

第 8 页共 6 页

a a b c d # 原因: ① 消除左递归:S→aAcB A→bA’ A’→bA’|ε B→d; ② FIRST(A)={a}, FIRST(A’)={b, ε }, FIRST(B)={d}, FIRST(S)={a}, <

b < >

c = >

d

# > >

< < <

> > = (8 分)

3、该文法可以改造为 LL(1)文法。

FOLLOW(A)={c}, FOLLOW(A’)={c}, FOLLOW(B)={#}, FOLLOW(S)={#},

对于每个非终结符的各个产生式的 FIRST 集两两不相交; ③ 对于 A’,FIRST(A)∩FOLLOW(A)=Φ 。 综上所述,原文法可以改造成 LL(1)文法。 五、 (20 分) 原文法不是 LL(1)文法,故不能直接使用 LL(1)分析法进行分析。 步骤如下: 1、拓广文法:①E’→E ③E→eBg ⑤A→a ⑦B→a 2、项目集规范族: ②E→eAf ④A→aA ⑥B→Bb (2 分)

第 9 页共 6 页

1 E’→E. 0 E’→.E E→.eAf E→.eBg E 2 e E→e.Af A→.aA A→.a E→e.Bg B→.Bb B→.a A

3 E→eA.f 4 a A→a.A A→a. A→.aA A→.a B→B.b 5 B E→eB.g B→B.b

f

6 E→eAf. 7 A→aA. 8 A→a.A A→a. A→.aA A→.a 9 E→eBg. 10 B→Bb. A

A

a

a

g b

(6 分)

由此项目集规范族可判断,原文法非 LR(0)文法,故不能直接使用 LR(0)分析法进行 分析。因此,使用 SLR(1)分析法分析原文法。 3、构造 SLR(1)分析表如下: FOLLOW(A)={f};FOLLOW(B)={b,g};FOLLOW(E)={#}。 ACTION 状态 0 1 2 3 4 5 6 7 8 9 10 r6 r6 (6 分) 4、分析输入串 eaaaf 如下: S8 r4 r5 r3 7 S8 r7 S10 S4 S6 r5 r7 S9 r2 7 a b e S2 acc 3 5 f g # GOTO A B E 1

第 10 页共 6 页

步骤 1 2 3 4 5 6 7 8 9 10 11 六、 (25 分) 1、步骤: (1)拓广文法:①E’→E ③E→AE ⑤B→i
(1)

状态 0 02 024 0248

符号 # #e #ea #eaa

输入串 动作 eaaaf# 预备 aaaf# 移进 aaf# 移进 af# 移进 f# 移进 f# 归约 f# 归约 f# 归约 # 移进 # 归约 接受 (6 分)

02488 #eaaa 02487 #eaaA 0247 023 0236 01 #eaA #aA #aAf #E acc

②E→i <i ④A→B∨

(1)

(2)

(2 分)

(2)项目集规范族: 1 0 E E’→E. E’→.E 2 E→.i(1)<i(2) i E→i.(1)<i(2) < E→.AE(1) B→i. A→.B∨ 3 B→.i E A E→A.E(1) E→.i(1)<i(2) B 4 i E→.AE(1) A→B.∨ A→.B∨ B ∨ B→.i 5 A→B∨. A

6 E→i(1)<.i(2) 7 E→AE.(1) 2 4

i

8 E→i(1)<i.(2)

(6 分) (3)SLR(1)分析表如下: FOLLOW(E)={#};FOLLOW(A)={i};FOLLOW(B)={ ∨}。 ACTION GOTO

第 11 页共 6 页

状态 0 1 2 3 4 5 6 7 8 2、分析输入串 a∨b<c 如下:

i S2

<



# acc

E A B 1 3 4

S6 r4 S2 S5 r3 S8 r2 r1 (6 分) 7 3 4

步骤 状态栈 符号 1 2 3 4 5 6 7 8 0 02 04 045 03 032 0326 03268 # #i #B #B∨ #A #Ai #Ai< #Ai<i

输入串

动作 四元式

a∨b<c# 预备 ∨b<c# 移进 B.TC=1,B.FC=2; ∨b<c# 归约 Gen(Jnz,a,_,0); Gen(J,_,_,3); b<c# 移进 A.TC=B.TC=1; b<c# 归约 BackPatch(2,3); <c# 移进 C# 移进 # 移进 E.TC=3,E.FC=4; Gen(J<,b,c,0); # 归约 Gen(J,_,_,0); E.FC=4; # 归约 E.TC=MERG(1,3); 接受 (6 分)

9 10 11

037 01

#AE #E acc

整理: 1、Gen(Jnz,a,_,0) 2、Gen(J,_,_,3) 3、Gen(J<,b,c,1) 4、Gen(J,_,_,0)

真出口为 3; 假出口为 4。
第 12 页共 6 页

(2 分)

3、四元式: 1、 (Jnz,a,_,5) 2、(J,_,_,3) 3、(J<,b,c,5) 4、(J,_,_,8) 5、(*,m,n,T1) 6、(:=,T1,_,I) 7、(J,_,_,10) 8、(+,m,n,T2) 9、(:=,T2,_,I) 10、??
编译原理 E 卷 三、应用题(共 50 分) 1、有文法 G[E]:(16 分) E → T + E|T T → T * F|F F → ( E )|i (1)证明 T+T*F+i 是文法的一个句型。(3 分) (2)构造型 T+T*F+i 的语法树。(3 分) (3)指出该句型的所有短语、直接短语和句柄。(7 分) (4)指出该句型的所有素短语和最左素短语。(3 分) 2、将下列条件语句翻译成四元式的中间代码形式:(6 分) if a<b or c<d and e>f then s1 else s2 3、有正规文法 G[S]: (12 分) S→aA|bB A→bS|b B→aS|a (1)构造对应的正规式 R,使得 L(R)=L(G)。 (3 分) (2)构造对应的 NFA 状态图,使得 L(M)=L(R)。 (3 分) (3)将所得 NFA 确定化为 DFA。 (3 分) (4)将所得 DFA 最小化。 (3 分) 4、对表达式文法 G[E]: (16 分) E → E - T|T T → T ^ F|F F → ( E )|a (1)判断 G[E]是否为 LL(1)文法。若不是,改造为 LL(1)文法。(8 分) (2)构造预测分析表,并对输入串 w=a-a^a#进行预测分析。(8 分) 三、应用题参考答案(共 50 分) 1、 (1)证明(3 分):因为存在推导序列:E=>T+E=>T+T+E=>T+T*F+E=>T+T*F+T =>T+T*F+F=>T+T*F+i,即有 E=*>T+T*F+i 成立,所以,T+T*F+i 是文法的一个句型。 (2)语法树(3 分) :

(3 分)

第 13 页共 6 页

(3)句型分析(7 分) :该句型相对于 E 的短语:T+T*F+i、T*F+i 和 i ;相对于 T 的短语有:T*F 和 i, 相对于 F 的短语有 i。相对于 T→T*F 的直接短语:T*F,相对于 F→i 的直接短语:i。句柄:T*F。 (4) 该句型的所有素短语:T*F 和 I;T*F 为最左素短语。(3 分) 2、if a<b or c<d and e>f then s1 else s2 生成的三地址代码/四元式序列如下:(6 分) (1) if a < b goto (7) (2) goto (3) (3) if c < d goto (5) (4) goto (p+1) (5) if e > f goto (7) (6) goto (p+1) (7) s1 对应的四元式序列 … (p) goto (q) (p+1) s2 对应的四元式序列 … (q) 3、(1)代入后有 S 的规则右部=a(bS|b)|b(aS|a)=ab(S|ε)|ba(S|ε)=(ab|ba) (S|ε),故对应的正 规式 R=(ab|ba)(ab|ba)* 。 (3 分) (2)对应的 NFA 状态图如下左图所示: (3 分)

(3)将所得 NFA 确定化为 DFA 状态图如上右图所示: (3 分) (4)将所得 DFA 最小化:首先根据是否终态划分为非终态集 P1={S,A,B}和终态集 P2={Z};然后对 P1 根据 a 弧划分为 P11={S},P12={A},P13={B}。可见原 DFA 已是最小化的 DFA。 (3 分) 4、 (1)计算 G[E]的 SELECT 集如下:(2 分) SELECT(E→ E – T )={(,a} SELECT(E→ T )==,(,a} SELECT(T→ T ^ F)={(,a} SELECT(T→ F)={(,a} SELECT(F → ( E ))={( } SELECT(F → a)={a} 由于 SELECT(E→ E – T ) ∩ SELECT(E→ T )==,(,a-≠φ; SELECT(T→ T ^ F) ∩ SELECT(T→ F)={(,a-≠φ; SELECT (F →( E ))∩SELECT (F →a) = ,(-∩,a- =φ 故 G[E]不是 LL((1) 文法。(1 分) 对 G[E]的 E → E – T 和 T → T ^ F 两条规则消除左递归后变为:(2 分) E→T E’ E’→ – T E’|ε T→ F T’ T’→ ^ F T’|ε F→ ( E )|a 计算消除左递归后 G[E]的 SELECT 集如下:(2 分) SELECT(E→ T E’)=,(,a} SELECT(E’→ – T E’)=,– } SELECT(E’→ε)=,#,)} SELECT(T→ F T’)=,(,a} SELECT(T’→ ^ F T’)=, ^} SELECT(T’→ε)=,– ,#,)} SELECT(F→( E ))=,(SELECT(F→a)=,a第 14 页共 6 页

由于 SELECT(E’→ – T E’)∩SELECT (E'→ε) =φ SELECT (T'→ ^ F T') ∩SELECT (T'→ε) =φ SELECT (F →( E ))∩SELECT (F →a) = =φ 故消除左递归后的 G[E]是 LL((1) 文法。(1 分) (2)根据消除左递归后的 G[E]的 SELECT 集构造预测分析表如下:(3 分)

对输入串 w=a-a^a#的分析过程如下表所示(注意:规则右部以逆序入栈) :(5 分)

二、设?={0,1}上的正规集 S 由倒数第二个字符为 1 的所有字符串组成,请给出该字集对应 的正规式,并构造一个识别该正规集的 DFA。(8 分) 三、写一个文法使其语言为 L(G)={ anbmambn | m,n≥1}。(6 分)
四、对于文法 G(E): (8 分)

E?T|E+T T?F|T*F F?(E)|i 1. 写出句型(T*F+i)的最右推导并画出语法树。 2. 写出上述句型的短语,直接短语、句柄和素短语。

E

T

F

(

E

)

E

+

T

T

F

T
第 15 页共 6 页

*

F

i

五、设文法 G(S):(12 分)

S ? SiA | A A ? A?B|B B ?) A* | (

1. 构造各非终结符的 FIRSTVT 和 LASTVT 集合; 2. 构造优先关系表和优先函数。(12 分) 六、设某语言的 do-while 语句的语法形式为 (9 分) S ? do S(1) While E 其语义解释为: S(1)的代码 E的代码

真 假

针对自下而上的语法分析器,按如下要求构造该语句的翻译模式: (1) 写出适合语法制导翻译的产生式; (2) 写出每个产生式对应的语义动作. 七、(8 分)将语句 if (A<X) ? (B>0) then while C>0 do C:=C+D 翻译成四元式。(8 分)
八、(10 分) 设有基本块如下:

T1:=S+R T2:= 3 T3:= 12/T2 T4:=S/R A:=T1-T4 T5:=S+R B:=T5 T6:=T5*T3 B:=T6 (1)画出 DAG 图; (2)设 A,B 是出基本块后的活跃变量,请给出优化后的四元式序列。
九、(9 分) 设已构造出文法 G(S):

(1) S ? BB
第 16 页共 6 页

(2) B ? aB (3) B? b 的 LR 分析表如下
ACTION 状态 0 1 2 3 4 5 6 7 8 9 r2 r2 r2 s6 s7 r3 s6 s3 r3 s7 s4 r3 r1 9 a s3 b s4 acc 5 8 # S 1 GOTO B 2

假定输入串为 abab,请给出 LR 分析过程(即按照步骤给出状态,符号,输入串的变化过程)。 E 卷答案: 2 答: 构造相应的正规式:(0|1)*1(0|1) NFA: (2 分) 1
0

(3 分) 1 1
3 4

?

?

1

?

?

2

0 确定化:(3 分) I {0,1,2} {1,2} {1,2,3} {1,2,4} {1,2,3,4}
I0

0
I1

{1,2} {1,2} {1,2,4} {1,2} {1,2,4} 0

{1,2,3} {1,2,3} {1,2,3,4} {1,2,3} {1,2,3,4}

1 0
0 1

1
2

0
3

0
4

第 17 页共 6 页

0 1 3 答:文法 G(S): S ? aSb | B B ? bBa | ba 4 答: 1. (4 分) E?T?F?(E) ?(E+T) ?(E+F) ?(E+i) ?(T+i) ?(T*F+i) 2. (4 分) 短语:(T*F+i), T*F+i, T*F, i 直接短语:T*F, i 句柄:T*F 素短语:T*F, i 5 答:(6 分) FIRSTVT(S)={ i,+,),( } FIRSTVT(A)={ +,),( } FIRSTVT(B)={ ),( } LASTVT(S)={ i,+,*,( } LASTVT(A)={ +,*,( } LASTVT(B)={ *,( } 优先关系表: (3 分) i i > + > ( > ) * > 优先函数: (3 分) i f 2 g 1 。

1 1

+ < > > < >

( < < <

) < < <

* > > >

+ 6 4

( 6 6

) 1 6

* 6 1

6 答:(1). 适合语法制导翻译的文法(3 分) G(S): R? do
第 18 页共 6 页

U?R S?U

S(1) E

While

(2). (6 分) R? do { U?R { R.QUAD:=NXQ S(1) While }

U.QUAD:=R.QUAD; BACKPATCH(S.CHAIN, NXQ) }

S?U E { 答案二: (1) S ? do M ?ε (2) M1 S(1) While M2 E (6 分) M2 E (3 分) M1 S
(1)

BACKPATCH(E.TC, U.QUAD); S.CHAIN:=E.FC }

M ?ε { M.QUAD := NXQ } S ? do { While

BACKPATCH(S(1).CHAIN, M2.QUAD); BACKPATCH(E.TC, M1.QUAD); S.CHAIN:=E. FC } 7 答: 100 (j<, A, X, 102) 101 (j, -, -, 109) 102 (j>, B, 0, 104) 103 (j, -, -, 109) 104 (j>, C, 0, 106) 105 (j, -, -, 109) 106 (+, C, D, T1) 107 (:=, T1, -, C) 108 (j, -, -, 104) 109 (控制结构 3 分,其他 5 分) 8 答:(1) DAG 如右图:(6 分)
n7 A _
第 19 页共 6 页

n8 *

T6,B

n3 T1,T5, B /

n6

T4

(2) 四元式序列:(4 分) T1:=S+R T4:=S/R A:=T1-T4 B:=T1*4 9 答: 步骤 状态 符号 输入串 0 0 # abab# 1 03 #a bab# 2 034 #ab ab# 3 038 #aB ab# 4 02 #B ab# 5 026 #Ba b# 6 0267 #Bab # 7 0269 #BaB # 8 025 #BB # 9 01 #S # acc
编译原理 F 卷

四、问答题: 22、设有语言 L={ α | α∈ {0,1} + ,且 α 不以 0 开头,但以 00 结尾 } 。 ⑴试写出描述 L 的正规表达式; ⑵构造识别 L 的 DFA (要求给出详细过程,并画出构造过程中的 NDFA 、 DFA 的状态转换 图,以及 DFA 的形式化描述 ) 。 23、给定文法 G[S] : S → SaA|a A → AbS|b ⑴请构造该文法的以 LR(0) 项目集为状态的识别规范句型活前缀的 DFA 。 ⑵请构造该文法的 LR(0) 分析表。 ⑶什么是 LR(0) 文法?该文法是 LR(0) 文法吗?为什么? ⑷什么是 SLR(1) 文法?该文法是 SLR(1) 文法吗?为什么? 24、对下面的文法 G: S->aBc|bAB A->aAb|b B->b|ε (1)计算这个文法的每个非终结符的 FIRST 和 FOLLOW 集合; (2)证明这个文法是 LL(1)的;

第 20 页共 6 页

(3)构造它的预测分析表。 25、设字母表∑={ a,b},对于以 aa 或 ab 结尾的字的正规集。 (1)请写出描述该语言的正规式。 (2)构造该正规式所对应的 NFA(画出转换图) ; (3)将所求的 NFA 确定化(画出 DFA 的转换图) ; (4)将所求出的 DFA 最小化(画出极小化后的转换图) ; 26、设文法 G 为 S ? E E? TE | ε T ? eT | t (1)证明它是 LR(1)文法; (2)构造它的 LR(1)分析表; (3)给出输入符号串 etet 的分析过程。 27、对文法 G(S): S ? S ? a T | a T | ? a T T ? ? a T | ? a (1) 消除该文法的左递归和提取左公因子; (2) 构造各非终结符的 FIRST 和 FOLLOW 集合; (3) 构造该文法的 LL(1)分析表,并判断该文法是否是 LL(1)的。 F 答案: 22 答: 1 )正规表达式: 1(0|1) * 00 ( ( 2 )第一步:将正规表达式转换为 NDFA

第二步:将 NDFA 确定化为 DFA : 造表法确定化( 3 分) 确定化后 DFA M 的状态转换表 状态 输入 I 0 [S] [A,D,B] [D,B,C] [D,B] — [D,B,C] I 1 [A,D,B] [D,B] 重新命名 t q 0 q 1 q 2 q 3 q 4 0 — q 2 q 4 q 2 q 4 1 q 1 q 3 q 3 q 3 q 3

[D,B,C,Z] [D,B] [D,B,C] [D,B]

[D,B,C,Z] [D,B,C,Z] [D,B] DFA 的状态转换图
第 21 页共 6 页

第三步:给出 DFA 的形式化描述 DFA M = ( { q 0 , q 1 , q 2 , q 3 , q 4 }, {0,1}, t, q 0 , { q 4 } ) t 的定义见 M 的状态转换表。 2323 答: (1)拓广文法: G[S′]: S′→ S ⑴ A → AbS ⑷ S → SaA ⑵ A → b ⑸ S → a ⑶

该文法的以 LR(0) 项目集为状态的识别规范句型活前缀的 DFA :

⑵ 该文法的 LR(0) 分析表:

状态 0 1 2 3 4 5 6 7

ACTION a S 2 S 3 r 3 r 3 S 5 r 2 r 5 S 2 r 4 /S 3 r 4 r 4 r 2 /S 6 r 5 r 2 r 5 acc r 3 b #

GOTO S 1 A

4

7

⑶ LR(0) 文法: 该文法的以 LR(0) 项目集为状态的识别规范句型活前缀的 DFA 中没有冲突
第 22 页共 6 页

状态。 该文法不是 LR(0) 文法,因为存在冲突状态: I 4 和 I 7。 ⑷ SLR(1) 文法:该文法的以 LR(0) 项目集为状态的识别规范句型活前缀的 DFA 中有冲突 状态,冲突可用 FOLLOW 集解决。 该文法不是 SLR(1) 文法。因为 FOLLOW(S)={a,b,#} ,所以无法解决冲突。 24 答: (1)first(B)={b, ε},first(A)={a,b},first(S)={a,b} Follow(S)={#},follow(A)={b,#},follow(B)={c,#} (2)因为只有 FIRST(B)含有 ? , 所以只考虑: FOLLOW(B)=FIRST(c) ?FOLLOW(S)={c, ∴该文法的 LL(1)表 (3)该文法的 LL(1)分析表如下: a b c # S aBc bAB A aAb b B b ? ? (1 分) (1 分) #}

25 答: (1)正则式为: (a|b)*a(a|b) 。 (2)由正则式得到的转换系统如下图:

(3)由子集法构造的 DFA 如下图:

(4)DFA 最小化如下图:

26 答:(1)拓广文法 G’(1 分) : (0) S' ?S (1) S ? E (2) E? TE
第 23 页共 6 页

(3) E ?ε

(4) T ? eT

(5) T ? t

FIRST(A) = {ε, e,t} FIRST(B) = {e, t} 构造的 DFA 如下:

由项目集规范族看出,不存在冲突动作。 ∴该文法是 LR(1)文法。 (2) LR(1)分析表 Action e t S4 S5 Goto S E T 1 2 3

状态 0 1 2 3 4 5 6 7 (3)输入串 abab 的分析过程为:

S4 S4 r5 r4

# r3 acc r1 S5 r3 S5 r5 r5 r2 r4 r4

6 3 7

步骤 状态栈 符号栈 当前字符 剩余字符串 动作 (1) 0 # e tet# 移进 (2) 04 #e t et# 移进 (3) 045 #et e t# 归约 T?t
第 24 页共 6 页

(4) (5) (6) (7) (8) (9) (10) (11) (12) (13)

047 03 034 0345 0347 033 0336 036 02 01

#eT #T #Te #TeT #TeT #TT #TTE #TE # E #S

e e t # # # # # # #

t# t# #

归约 T?et 移进 移进 归约 T?t 归约 T?et 归约 E?ε 归约 E?TE 归约 E?TE 归约 S?E acc

27 答: (1)消除左递归 S ? a T S’ | S’ ? ? a T S’ T ? T ? ? a 提取左公因子 S ? a T S’ | S’ ? ? a T S’ T ? ? a T’ T’ ? T | ε FIRST(S)={a,?} FIRST(T')={ ?,ε} FOLLOW(T)={?,#}

? a T S’ | ε T | ? a ? a T S’ | ε

(2) 各非终结符的 FIRST 和 FOLLOW 集合: FIRST(S')={ ?,ε} FOLLOW(S)={#} FOLLOW(T')={?,#} FIRST(T)={ ? } FOLLOW(S')={#}

(3) LL(1)分析表如下(3 分) ,该文法是 LL(1)文法。 分) (1 a # ? ? S S?aTS' S??aTS' S' S'??aTS S’?ε ' T T??aT' T' T'?ε T'?T T'?ε

编译原理 G 卷 六、问答题 1、给出上下文无关文法的定义 2、文法 G[S]: S→aSPQ|abQ QP→PQ bP→bb bQ→bc cQ→cc
第 25 页共 6 页

(1)它是 Chomsky 哪一型文法? (2)它生成的语言是什么? 3、按指定类型,给出语言的文法。 L={aibj|j>i≥1}的上下文无关文法。 4、有文法 G:S→aAcB|Bd A→AaB|c B→bScA|b (1)试求句型 aAaBcbbdcc 和 aAcbBdcc 的句柄; (2)写出句子 acabcbbdcc 的最左推导过程。 S→(L)|aS|a 5、对于文法 G[S]: (1)画出句型(S,(a) )的语法树。 (2)写出上述句型的所有短语、直接短语、句柄和素短语。 6、考虑文法 G[T]: T→T*F|F F→F↑P|P P→(T)|i 证明 T*P↑(T*F)是该文法的一个句型,并指出直接短语和句柄。 T T * F F ↑ P P ( T ) L→L, S|S

T * F 图 2-8-4 句型 T*P↑(T*F)的语法树 G 卷答案: 1[解答] 一个上下文无关文法 G 是一个四元式(VT,VN,S, P) ,其中: ●VT 是一个非空有限集,它的每个元素称为终结符号; ●VN 是一个非空有限集,它的每个元素称为非终结符号,VT∩VN=Φ; ●S 是一个非终结符号,称为开始符号; ●P 是一个产生式集合(有限) ,每个产生式的形式是 P→α ,其中,P∈VN, α ∈(VT∪VN)*。开始符号 S 至少必须在某个产生式的左部出现一次。 2[解答] (1)由于产生式左部存在终结符号,且所有产生式左部符号的长度均小于等于产生式右部的符号长 度,所以文法 G[S]是 Chomsky1 型文法,即上下文有关文法。 (2)按产生式出现的顺序规定优先级由高到低(否则无法推出句子) ,我们可以得到: S?abQ?abc S?aSPQ?aabQPQ?aabPQQ?aabbQQ?aabbcQ?aabbcc S?aSPQ?aaSPQPQ?aaabQPQPQ?aaabPQQPQ?aaabPQPQQ?aaaPPQQQ? aaabbPqqq?aaabbQQQ?aaabbbcQQ?aaabbbccQ?aaabbbccc ?? 于是得到文法 G[S]生成的语言 L={anbncn|n≥1} 3【解答】 (1)由 L={aibj|j>i≥1}知,所求该语言对应的上下文无关文法首先应有 S→aSb 型产生式,以保证 b 的个数不少于 a 的个数;其次,还需有 S→Sb 或 S→bS 型的产生式,用以保证 b 的个数多于 a 的个数;也 即所求上下文无关文法 G[S]为: G[S]:S→aSb|Sb|b 4【解答】 (1)分别画出对应两句型的语法树,如图 2-8-2 所示
第 26 页共 6 页

句柄:AaB

Bd S S a A c B a A a B b S c A B S c A B d b (a) 图 2-8-2 语法树 (b) c B d c A c B

(2)句子 acabcbbdcc 的最左推导如下: S?aAcB?aAaBcB?acaBcB?acabcB?acabcbScA?acabcbBdcA ?acabcbbdcA?acabcbbdcc 5【解答】 (1)句型(S,(a) )的语法树如图 2-8-3 所示 ( L S (2)由图 2-8-3 可知: ①短语:S、a、(a)、S,(a)、(S,(a)); ②直接短语:a、S; ③句柄:S; ④素短语:素短语可由图 2-8-3 中相邻终结符之间的优先关系求得,即; # · , · ·a· ) ) # (· ( · · 因此素短语为 a。 6【解答】 首先构造 T*P↑(T*F)的语法树如图 2-8-4 所示。 由图 2-8-4 可知,T*P↑(T*F)是文法 G[T]的一个句型。 直接短语有两个,即 P 和 T*F;句柄为 P。 H卷 四、综合题 1、对于文法 G[S]: S→AS|b A→SA|a (1)列出所有 LR(0)项目 (2)列出构成文法 LR(0)项目集规范族。 解答:
第 27 页共 6 页

S L ) , S ( L ) S a 图 2-8-3 句型(S,(a) )的语法树

首先将文法 G 拓广为 G[S′]: S′→S S→AS|b A→SA|a (1)文法 G[S′]的 LR(0)项目是: 1、S′→·S 5、S→AS· 2、S′→S· 6、S→·b 3、S→·AS 7、S→b· 4、S→A·S 8、A→·SA

9、A→S·A 10、A→SA· 11、A→·a 12、A→a·

(2)列出构成文法 LR(0)项目集规范族。 用 ε -CLOSURE(闭包)办法构造文法 G′的 LR(0)项目集规范族如下: I0:1、S′→·S I3: 9、A→S·A I6:12、A→a· 3、S→·AS 8、A→·SA I7:7、S→b· 8、A→·SA 3、S→·AS 11、A→·a 6、S→·b 6、S→·b 11、A→·a I1:2、S′→S· 9、A→S·A 8、A→·SA 11、A→·a 3、S→·AS 6、S→·b I2:4、S→A·S 3、S→·AS 6、S→·b 8、A→·SA 11、A→·a I4:10、A→SA· 4、S→A·S 3、S→·AS 6、S→·b 8、A→·SA 11、A→·a I5: 5、S→AS· 9、A→S·A 8、A→·SA 11、A→·a 3、S→·AS 6、S→·b 注意:I1 中的 S′→S·和 A→·SA 是由状态 I0 中的 1 和 3 读入一个 S 字符后得到的下一个项目; ,而 I4 中 的 A→SA 和 A→A·S 则是由 I3 中的 9 和 3 读入一个 A 字符后得到的下一个项目;I5 中的 S→AS· A→S·A 和 则是由 I4 中的 4 和 8 读入一个 S 字符后得到的下一个项目。 状态全体构成了文法 G′的 LR(0)规范族。 编译原理 I 卷 四、综合题 1、给出下列表达式的逆波兰表示(后缀式) : ① a*(-b+c) ② (A∨B)∧(C∨┑D∧E) 2、写出算术表达式:A+B*(C-D)+E/(C-D)↑N 的 ①四元式序列;②三元式序列;③间接三元式序列 5. 已知文法 G[S] 为 S → aSb|Sb|b ,试证明文法 G[S] 为二义文法。 6 已知文法 A->aAd|aAb| ε

判断该文法是否是 SLR(1) 文法,若是构造相应分析表,并对输入串 ab# 给出分析过程。
答案: 解答 1、 ① ab@c+*; ② AB∨CD┑E∧∨∧
第 28 页共 6 页

2、 5 证明: ①表达式的四元式序列: ②表达式的三元式序列 (1)(-,C,D,T1) (1)(-,C,D) 由文法 G[S]:S→aSb|Sb|b,对句子 aabbbb 对应的两棵语法树为: (2)(*,B,T1,T2) (2)(*,B,(1)) (3)(+,A,T2,T3) (4)(-,C,D,T4) (5)(↑,T4,N,T5) ⑹ (/,E,T5,T6) ⑺ (+,T3,T6,T7) (3)(+,A,(2)) (4)(-,C,D) (5)(↑,(4),N) ⑹ (/,E,(5)) ⑺ (+,(3),(6)) ③间接三元式序列 ⑴ (1)(-,C,D) ⑵ ⑶ ⑴ ⑷ ⑸ ⑹ (2)(*,B,(1)) (3)(+,A,(2)) ⑷ (↑,(1),N) ⑸ (/,E,(4)) ⑹ (+,(3),(5))

因此,文法 G[S]为二义文法。 6 解:增加一个非终结符 S/后,产生原文法的增广文法有: S'->A A->aAd|aAb|ε 下 面 构 造 它 的 LR(0) 项 目 集 规 范 族 为 :

第 29 页共 6 页

从 上 表 可 看 出 , 状 态 I0 和 I2 存 在 移 进 - 归 约 冲 突 , 该 文 法 不 是 LR(0) 文 法 。 对 于 I0 来 说 有 : FOLLOW(A)∩{a}={b,d,#}∩{a}=Φ,所以在 I0 状态下面临输入符号为 a 时移进,为 b,d,#时归约,为其他时 报错。对于 I2 来说有也有与 I0 完全相同的结论。这就是说,以上的移进-归约冲突是可以解决的,因此该 文法是 SLR(1)文法。 其 SLR(1)分析表为:

对输入串 ab#给出分析过程为:

编译原理 J 卷 五、计算题: 1.设文法 G(S): S→^ | a | (T) T→T,S | S ⑴ 消除左递归; ⑵ 构造相应的 FIRST 和 FOLLOW 集合; ⑶ 构造预测分析表 2.语句 if E then S (1) 改写文法,使之适合语法制导翻译; (2) 写出改写后产生式的语义动作。 3.设文法 G(S) : S→(T) | a T→T+S | S (1)计算 FIRSTVT 和 LASTVT; (2)构造优先关系表。 4.设某语言的 for 语句的形式为 (1) (2) for i:=E to E do S 其语义解释为
第 30 页共 6 页

i:=E (2) LIMIT:=E again: if i<=LIMIT then Begin S; i:=i+1 goto again End; (1)写出适合语法制导翻译的产生式; (2)写出每个产生式对应的语义动作。 5.把语句 while a<10 do if c>0 then a:=a+1 else a:=a*3-1; 翻译成四元式序列。 6.设有基本块 D:=A-C E:=A*C F:=D*E S:=2 T:=A-C Q:=A*C G:=2*S J:=T*Q K:=G*5 L:=K+J M:=L 假设基本块出口时只有 M 还被引用,请写出优化后的四元序列。 7.已知文法 G(S) S→a | ^ | (T) T→T,S | S (1) 给出句子(a,(a,a))的最左推导; (2) 给出句型((T,S),a)的短语, 直接短语,句柄。 8.对于 C 语言 do S while E 语句 (1)改写文法,使之适合语法制导翻译; (2)写出改写后产生式的语义动作。 9.已知文法 G(S) S→aAcBe A→Ab| b B→d (1)给出句子 abbcde 的最左推导及画出语法树; (2)给出句型 aAbcde 的短语、素短语。 10.设文法 G(S): S→(T) | aS | a T→T,S | S ⑴消除左递归和提公共左因子; ⑵构造相应的 FIRST 和 FOLLOW 集合; ⑶构造预测分析表。 11.把语句

(1)

第 31 页共 6 页

if X>0 ∨ Y<0 then while X>0 do X:=A*3 else Y:=B+3; 翻译成四元式序列。 12.已知文法 G(S) E→E+T | T T→T*F| F F→(E)| i (1) 给出句型 (i+i)*i+i 的最左推导及画出语法树; (2) 给出句型 (E+T)*i+F 的短语,素短语和最左素短语。 13.设文法 G(S) : S→T | S∨T T→U |T∧U U→i |-U (1)计算 FIRSTVT 和 LASTVT; (2)构造优先关系表。

第 32 页共 6 页

答案:1(1)消除左递,文法变为 G’[S]:
S→^ | a | (T)' T→ST’ | S T’→,ST’ |ε 此文法无左公共左因子。 (2)构造相应的 FIRST 和 FOLLOW 集合: FIRST(S)={a, ^, (}, FOLLOW(S)={#, ,, )} FIRST(T)={a, ^, (} ,FOLLOW(T)={}} FIRST(T’)={,, ε } ,FOLLOW(F)={)} (3)构造预测分析表: a ^ ( S T T’ S→a T→ST’ S→^ T→ST’ S→(T)' T→ST’ T’→ε T’→,ST’

)

,

#

2. (1) C→if E then (1) S→CS (2) C→if E then {BACK(E.TC, NXQ); C.chain:=E.FC} (1) (1) S→CS {S.chain:=MERG(C.Chain, S . Chain)} 3. (1) FIRSTVT(S)={a, ( } FIRSTVT(T)={+, aa, (} LASTVT(S)={a, ) } LASTVT(T)={+, a, )} (2) a + ( a .> + <. .> <. ( <. <. <. ) .> .> (1) (2) 4. (1) F→for i:=E to E do (1) S→FS (1) (2) (2) F→for i:=E to E do (1) {GEN(:=, E .place, _, entry(i)); F.place:=entry(i); LIMIT:=Newtemp; (2) GEN(:=, E .place, _, LIMIT); Q:=NXQ; F.QUAD:=q; GEN(j≤, entry(i), LIMIT, q+2) F.chain:=NXQ; GEN(j, _, _, 0)} (1) S→FS (1) {BACKPATCH(S .chain, NXQ); GEN(+, F.place, 1, F.place); GEN(j, _, _, F.QUAD); S.chain:=F.chain } 5. (1) (j<, a, ‘10’, (3))

) .> .> =. >.

第 33 页共 6 页

(2) (j, _, _, (12)) (3) (j>, c, ‘0’, (5)) (4) (j, _, _, (8)) (5) (+, a, ‘1’, T1)) (6) (:=, T1, _, a) (7) (j, _, _, (1)) (8) (*, a, ‘13’, T2) (9) (-, T2, ‘1’, T3) (10) (:=, T3, _, a) (11) (j, _, _, (1)) 6.优化后的四元序列 D:=A-C E:=A*C F:=D*E M:=F+20 7. 最左推导 S=(T)=>(T,S)=>(S,S)=>(a,S)=>(a,(T))=>(a,(T,S))=>(a,(S,S))=>(a,(a,S))=>(a,(a, a)) 短语 ((T,S),a) (T,S),a (T,S) T,S a 直接短语 T,S a 句柄 T,S 8.(1) S→do M1 S1 while M2 E M→ε (2) M→ε {M.quad=nestquad;} S→do M1 S1 while M2 E {backpatch(s1.nextlist, M2.quad); backpatch(E.truelist, M1.quad); S.nextlist=E.falelist; } 9.(1) S=>aAcBe=>AAbcBe=>abbcBe=>abbcde (2) 短语: aAbcde, Ab, d 素短语: Ab, d 10.(1) S →(L) | aS’ S’→S |ε L→SL’ L’→,SL’ |ε (2) FIRST(S)={a, (} FIRST(S’)={a, (, ε } FIRST(L)={a, (} FIRST(L’)={,, ε } FOLLOW(S)={,, ), #} FOLLOW(S’)={,, ), #} FOLLOW(L)={ )} FOLLOW(L’)={ )}

第 34 页共 6 页

(3) ( S →(L) S’→S L→SL’ ) S’→ε L’→ε a S → aS’ S’→S L→SL’ , S’→ε L’→,SL’ # S’→ε

S S’ L L’

11.(1) (j>, X, 0, (5)) (2) (j, _, _, (3)) (3) (j<, Y, 0, (5)) (4) (j, _, _, (11)) (5) (j>0, X, 0, (7)) (6) (j, _, _, (7)) (7) (*, A, 3, T1) (8) (:=, T1, _, N) (9) (j, _, _, (5)) (10) (j, _, _, (13)) (11) (+, B, 3, T2) (12) (:=, T2, _, Y) 12.(1) E=>E+T=>T+T=>T*F+T=>F*F+T=>(E)*F+T=>(E+T)*F+T=>(T+T)*F+T =>(F+T)*F+T=>(i+T)*F+T=>(i+F)*F+T=>(i+i)*F+T=>(i+i)*i+T =>(i+i)*i+F=>(i+i)*i+i (2) 短语 i, F, E+T, (E+T), (E+T)*i, (E+T)*i+F 素短语 i, E+T 最左素短语 E+T 13.(1) FIRSTVT(S)={∨, ∧, i, - } FIRSTVT(T)={∧, i, -} FIRSTVT(U)={i, -} LASTVT(S)={∨, ∧, i, - } LASTVT(T)={∧, i, -} LASTVT(U)={i, -} (2) i S ∨ ∧ <. <. <. ∨ .> .> .> .> ∧ .> <. .> .> <. <. <.

编译原理 K 卷 四、对下面的文法 G: S→a | b | (T) T→T,S | S (1) 消去文法的左递归,得到等价的文法 G2; (2) 判断文法 G2 是否 LL(1)文法,如果是,给出其预测分析表。 (15) G2: S→a | b | (T)

第 35 页共 6 页

T→ ST’ T’→,S T’ | ε G2 是 LL(1)文法。 五、设有文法 G[A]: A→BCc | gDB B→bCDE |ε C→DaB | ca D→dD |ε E→gAf | c (1) 计算该文法的每一个非终结符的 FIRST 集和 FOLLOW 集; (2) 试判断该文法是否为 LL(1)文法。 (15) 是 LL(1)文法。 六、对表达式文法 G: E → E+T | T T → T*F | F F → (E) | I (1)造各非终结符的 FIRSTVT 和 LASTVT 集合; (2)构造文法的算符优先关系表。 (15) 七、有定义二进制整数的文法如下: L →LB | B B →0 | 1 构造一个翻译模式,计算该二进制数的值(十进制的值)(15) 。 K 答案 4 答: S T T’ a S→a T→ ST’ b S→b T→ ST’ ( S→(T) T→ ST’ ) , #

T’→ ε

T’ → , S T’

5 答: FIRST A B C D E A,b,c,d,g b A,c,d D C,g FOLLOW

A,c,d C,d,g A,b,c,g

6 答: FIRSTVT LASTVT

第 36 页共 6 页

E T F 算符优先关系表 + + > * > I > < ( > ) < #

*,+, (,i *, (,i (,i

*,+,,i ) *,,i ) ) ,i

* < > > < > <

I < < < <

( < < < <

) > > > = >

# > > > > =

7 答:引入 L、B 的综合属性 val,翻译模式为: S →L {print(L.val)} L →L1B {L.val= L1.val*2+B.val} L →B {L.val= B.val} B →0 {B.val=0} B →1 {B.val=1} 编译原理 L 卷

五、综合应用题(共 3 小题,每小题 10 分,共 30 分)
1.证明下述文法 G: S?aSbS|aS|d 是二义性文法。 2.对于文法 G[S]:S?AB,A?Aa|bB,B?a|Sb 求句型 baSb 的全部短语、直接短语和句柄? S 句型 baSb 的语法树如图五(2)所示。

A

B

b

B

S

b

3.设有非确定的有自限动机 NFA M=({A,B,C},{0,1},?,{A},{C}),其中: a ? (A,0)={C} ? (A,1)={A,B} ? (B,1)={C} ? (C,1)={C}。请画出状态转换距阵和状态转换 图。 答案: 1 解: 一个文法,如果存在某个句子有不只一棵语法分析树与之对应,那么称这个 文法是二义性文法。 句子 aadbd 有两棵语法树。如下图: S a S S

a a

S S

b

S d

第 37 页共 6 页

a

S

b

S

(1) 由此可知,S?aSbS|aS|d 定义的文法是二义性文法。

(2)

2 解:baSb 为句型 baSb 的相对于 S 的短语,ba 为句型 baSb 的相对于 A 的短语,Sb 为句型 baSb 的相对于 B 的短语,且为直接短语,a 为句型 baSb 的相对于 B 的短语,且为直接短语 和句柄。 3 解:状态转换距阵为: ? A B C 状态转换图为 1 1
A B

0 C ? ?

1 A,B C C

1 1
C 1

0 编译原理 M 卷

三 有穷自动机 M 接受字母表?={0,1}上所有满足下述条件的串:每个 1 都有 0 直接跟在右边。构造一个最小的 DFA M 及和 M 等价的正规式。 四 证明正规式(ab)*a 与正规式 a(ba)*等价 (用构造他们的最小的 DFA 方法) 。 五 写一个文法,使其语言是:
L = { 1n0m1m0n | m,n≥0 }

六 对文法 G[S] S → aSb | P P → bPc | bQc Q → Qa | a (1) 它是否是算符优先文法?请构造算符优先关系表 (2) 文法 G[S]消除左递归、提取左公因子后是否是 LL(1)文法?请 证实。 七 已知文法 G 为: (0) S′→ S (1) S → aAd (2) S → bAc

第 38 页共 6 页

(3) S → aec (4) S → bed (5) A → e 试构造它的 LR(1)项目集、可归前缀图和 LR(1)分析表。 八 已知源程序如下: prod:=0; i:=1; while i≤20 do begin prod:=prod+a[i]*b[i]; i:=i+1 end; 试按语法制导翻译法将源程序翻译成四元式序列(设 A 是数组 a 的起始地址,B 是 数组 b 的起始地址;机器按字节编址,每个数组元素占四个字节) 。

九 设有以下程序段 procedure P(x,y,z) begin Y:=y*3; Z:=X+z; end; begin a:=5; b:=2; p(a*b,a,a); print(a); end 若参数传递的方法分别为(1)传值、 (2)传地址、 (3)传名,试问结果分别什 么?

答案:

第 39 页共 6 页

5【答案】

文法 G:S → 1S0 | A A → 0A1 | ε

6【答案】1.求出 G[S]的 FIRSTVT 集和 LASTVT 集:
FIERSTVT(S)={a,b} LASTBVT(S)={b,c} FIERSTVT(P)={b} LASTBVT(P)={c} FIERSTVT(Q)={a} LASTBVT(Q)={a} 构造优先关系表为: a b c a < > < > b < > c > > 由于在优先关系中同时出现了 a<a 和 a>a 以及 b<b 和 b>b,所以该文法不是算符优先文法。 2. 消除左递归和提取左公因子后的文法为: S → aSb | P P → bP’ P’→ Pc |Qc Q → aQ’ Q’→ aQ’|ε 求具有相同左部的两个产生式的 Select 集的交集: Select(S→aSb)∩Select(S→P) = {a}∩First(P) = {a}∩{b} = Ф Select(P’→Pc)∩Select(P’→Qc) = First(P)∩First(Q)={b}∩{a}= Ф Select(Q’→aQ’)∩Select(Q’→ε) = {a}∩Follow(Q) = {a}∩{c} = Ф 所以修改后的文法是 LL(1)文法。

7【答案: 】

S I0: S′→·S , # S→·aAd , # S→ · bAc , #

I 1: S′→S ·, #
第 40 页共 6 页

a

I2: S→a ·Ad , #

A

d
I4:S→aA·d , # I8:S→aAd ·, #

构造 LR(1)分析表 如下:

action 状态 0 1 2 3 4 5 6 7 8 9 10 11 S9 S10 r5 S11 r1 r3 r2 r4 S8 r5 S5 S7 a S2 b S3 ac c c d e # S 1

goto A

4 6

九【答案】 (1)传值

5; (2)传地址

25;

(3)传名

45

编译原理 N 卷 1. 设有如下文法 G(S) ,试消除其左递归。

第 41 页共 6 页

G(S) :S—>Ac|c A—>Bb|b B—>Sa|a

2. 试构造与下面 G(S)等价的无左递归的文法。 G(S) :S—>Sa|Nb|c N—>Sd|Ne|f 3. 设有文法 G(S) : S—>aBc|bAB A—>aAb|b B—>b|ε ①求各产生式的 FIRST 集, FOLLOW(A)和 FOLLOW(B),以及各产生式的 SELECT 集。 ②构造 LL(1)分析表,并分析符号串 baabbb 是否是。 4. 已知文法 G(S): S—>a|(T) T—>T,S|S ①给出句子((a,a),a)的最左推导并画出语法树;②给出句型(T,a,(T))所有 的短语、直接短语、素短语、最左素短语、句柄和活前缀。 5. 设文法G(S)为: S—>a|aAb S—>b|bBa A—>1A0|ε B—>1B0|ε 求①LR(0)项目集族;②构造识别文法G(E)的DFA; 6. 设文法G(S)为: S—>a|aAb S—>b|bBa A—>1A0|ε B—>1B0|ε 求①LR(0)项目集族;②构造识别文法G(E)的DFA;

N 答案:
1 解:

S→abcS′|bcS′|cS′, S′→abcS′| ? S′→aS′|dN′bS′| ? , N′

2 解:S→fN′bS′|cS′,

→eN′| ?
3 解: (1) FIRST(aBc)={a}, FIRST(bAB)={b} FIRST(aAb)={a}, A→b: FIRST(A→b)={b}, B→b: FIRST(b) = {b}, FIRST(ε)={ε} FOLLOW(A)={b, #}, FOOLOW(B)={c, #} SELECT(S → aBc)={a}, SELECT(S → bAB) ={b}, SELECT(A → aAb)={a}, SELECT(A → b)={b}, SELECT(B→b)={b}, SELECT(B→ ? )={c, #} 因此,所得的 LL(1)分析表如表 A-4 所示。 表 A-4 LL(1)分析表



输入符号

第 42 页共 6 页

入 a b c # VN S S→aBc S→bAB A A→aAb A→b B B→b B→ ? B→ ?
(2)分析符号串 baabbb 成功,baabbb 是该文法的句子,如图 A-16 所示。
步骤 1 2 3 4 5 6 7 8 9 10 11 12 符号栈 #S #BAb #BA #BbAa #BbA #BbbAa #BbbA #Bbbb #Bbb #Bb #B # 输入串 baabbb# baabbb# aabbb# aabbb# abbb# abbb# bbb# bbb# bb# b# # # 所用的产生式
S ? bAB A ? aAb A ? aAb A?b

B?ε

成功

图 A-16

识别串 baabbb 的过程

4 解: (1)FIRSTVT(S)={(, i},FIRSTVT(D) ={i},FIRSTVT(R)={;, (, i},FIRSTVT(P)={i, (},LASTVT(S)={)},LASTVT(D)={i},LASTVT(R) = {;, ), i},LASTVT(P)={i, )} (2)算符优先矩阵,如表 A-5 所示。 表 A-5 优先矩阵

( ( ) ; i #
??

)
B
??

;
??

i
??

#
??

?? ?? ??
?? ??

??

?? ??

??
??

B
?

5 解 : ( 1 ) 最 左 推 导 : S ? (T) ? (a,S) ? (a,(T)) ? (a,(T,S)) ? (a,(S,S)) ? (a,(a, S)) ? (a,(a,a)) 语法树:如图 A-16 所示。

(T,S)

?

(S,S)

第 43 页共 6 页

S ( T S a T , ( T S a S T , ) S a )

图 A-16 (a,(a,a))的语法树 (2)句型(T, a, (T))的短语、直接短语、素短语、最左素短语、句柄、活前缀 及语法树(图 A-17) 。 短语:a || T,a || (T) || T , a , (T) || (T , a , (T)) 直接短语:a || (T) 素短语:a || (T) 最左素短语:a 句柄:a 活前缀: ? || ( || (T || (T , || (T , a
S ( T T , T , S ( a ) S T )

图 A-17

(T,a,(T))的语法树

6 解: (1)(2)LR(0)项目集族和识别活前缀的 DFA,如图 A-19 所示。 、 图 A-19 LR(0)

第 44 页共 6 页

A

b

I1: S′ ? S·
S a

I2: S ? a· S ? a· Ab A?· 1A0 A?· ?

I4: S ? aA· b
A

I8: S ? aAb· I9: A ? 1A· 0
0

1

I5: A ? 1· A0 A?· 1A0 A?· ?
1

I12: A ? 1A0·

I0: S′ ? · S S?· a S?· aAb S?· b S?· bBa

B b

I3: S ? b· S ? b· Ba B?· 1B0 B?· ?

I6: S ? bB· a

a B

I10: S ? bBa· I11: B ? 1B· 0
0 1

1

I7: B ? 1· B0 B?· 1B0 B?· ?

I13: B ? 1B0·

项目集族和 DFA
编译原理 O 卷 三、应用题(共 50 分) 1、有文法 G[S]:(12 分) S→aAS|a A→SbA|SS|ba (1)证明 aabbaa 是文法的一个句子。(3 分) (2)构造句子 aabbaa 的语法树。(3 分) (3)指出该句子的所有短语、直接短语和句柄。(6 分) 2、对文法 G[E']:(15 分) E'→#E# E→E+T|T T→T*F|F F→P^F|P P→(E)|i (1)计算 G[E']的 FIRSTVT 和 LASTVT。(5 分) (2)构造 G[E']的算符优先关系表,并说明 G[E']是否为算符优先文法。(5 分) (3)给出输入串 w=i+i# 的算符优先分析过程。(5 分) 3、对以下基本块: 分) (8 A:=5 B:=R+r T0:=A+B T1:=2*A T2:=B+A T3:=A+A X1:=T1+T2 X2:=T0*T3 (1)画出基本块的 DAG 图。(3 分) (2)根据 DAG 结点原来的构造顺序重写四元式。(2 分) (3)假设基本块出口后只有 X1,X2 还被引用,试写出优化后的四元式序列。(3 分) 4、对文法 G[S’]: (15 分) 0)S’→S 1)S →A 2)S →B 3)A →aAe 4)A →a 5)B →bBd 6)B →b (1)试构造 G[S’]的 LR(0)项目集规范族 DFA。(4 分) (2)试构造 G[S’]的 SLR(1)分析表,并判断它是否为 SLR(1)文法。(4 分) (3)试用 SLR(1)方法分析输入串 aae#。(4 分) (4)G[S’]是否为 LR(0)、LR(1)和 LALR(1)文法?为什么?(3 分)

第 45 页共 6 页

答案:
三、应用题参考答案(共 50 分) 1、 (1)证明(3 分):因为存在推导序列 S=>aAS=>aSbAS=>aabAS=>aabbaS=>aabbaa,即有 S=*>aabbaa 成立,所以,是文法的一个句子。 (2)语法树(3 分) :

(3)句型分析(6 分) :将句型改写为 a1a2b1b2a3a4,则:该句型相对于 S 的短语: a1a2b1b2a3a4 和 a4;相对于 A 的短语: a2b1b2a3 和 b2a3;对于 S→a 的直接短语:a2, a4;相对于 A→ba 的直接短语:b2a3;句柄:a2。 2、(1)计算 G[E']的 FIRSTVT 和 LASTVT 集如下:(5 分)

(2)构造 G[E']的算符优先关系表如下:(4 分)

由上表可知 G[E']是算符优先文法(1 分)。 (3)输入串 w=i+i# 的算符优先分析过程如下:(5 分)

3、 (1)基本块的 DAG 图如下:(3 分)

(2)根据 DAG 结点原来的构造顺序重写四元式如下:(2 分)

第 46 页共 6 页

A:=5 T1=10 T3=10 B:=R+r T0:=A+B T2:=T0 X1:=T0+T1 X2:=T0*T1 (3)假设基本块出口后只有 X1,X2 还被引用,则通过重新命名临时变量的基本块保结 构变换,可将基本块的四元式代码进一步优化为:(3 分) C:=R+r D:=5+C X1:=D+10 X2:=D*10 4、0)S’→S 1)S →A 2)S →B 3)A →aAe 4)A →a 5)B →bBd 6)B →b (1)G[S’]的 LR(0)项目集规范族 DFA 如下:(4 分)

(2)由于

,得 G[S’]的 SLR(1)分析表如下:(3 分)

由上左表可知 G[S’]是 SLR(1)文法(1 分) 。 (3)用 SLR(1)方法分析输入串 aae#过程如上右表所示:(4 分) (4)由于 G[S’ ]LR(0)项目集规范族 DFA 中 I4、 5 中都包含有移进—归约冲突, T 所以 G[S’ ] 不是 LR(0)文法,由于 G[S’]是 SLR(1)文法故一定是 LR(1)和 LALR(1)文法。(3 分) 编译原理 P 卷 一、综合题(30 分) 1、 构造下面文法的 LL(1)分析表。 S→aBc|bAB A→aAb | b B→b |ε 构造其 LL(1)分析表,并分析符号串 baabbb 是否是该文法的句子。 2、 设有文法 G(S) : S→CC (1) C→cC (2) C→d (3) 求 1)拓广文法, 2) 文法的转移图, 3) 构造规范 LR 语法分析表,

第 47 页共 6 页

4) 构造 LALR 语法分析表。 答案: 1 解: First(S)={a,b} First(A)={a,b} First(B)={b, ε } Follow(B)={c,$} a b S→aBc S→bAB A→aAb A→b B→b

c

$

S A B

B→ε

B→ε

分析符号串 baabbb 的过程 步骤 符号栈 输入串 1 $S baabbb$ 2 $BAb baabbb$ 3 $BA aabbb$ 4 $BbAa aabbb$ 5 $BbA abbb$ 6 $BbbAa abbb$ 7 $BbbA bbb$ 8 $Bbbb bbb$ 9 $Bbb bb$ 10 $Bb b$ 11 $B $ 12 $ $ 2 解答: 1) 拓广文法 S’ →S S→CC C→cC C→d

规则 S→bAB A→aAb A→aAb A→b

B→ε Acc

(1) (2) (3)

2)

第 48 页共 6 页

S’ →.S,$ S→.CC ,$ C→.cC ,c/d C→.d ,c/d I0

S

S’ →S.,$ I1

C

S→C.C ,$ C→.cC ,$ C→.d ,$ I2

C S→CC. ,$ I5 c c C→c.C ,$ C→.cC ,$ C→.d ,$ I6 d C C→cC.,$ I9

d

c

C→d. ,$ I7

c

C→c.C ,c/d C→.cC ,c/d C→.d ,c/d I3

C C→cC. ,c/d I8

d d C→d. ,c/d I4

第 49 页共 6 页

3)文法的规范 LR 语法分析表
状态 0 1 2 3 4 5 6 7 8 9 r2 r2 r2 s6 s7 r3 s6 s3 r3 s7 s4 r3 r1 9 c s3 ACTION d s4 $ acc 5 8 S 1 GOTO C 2

4)LALR 语法分析表
状态 ACTION c s36 d s47 $ GOTO S 1 C 2

0 1 2 36 47 5 89

acc s36 s36 r3 s47 s47 r3 r3 r1 r2 r2 r2 5 89

编译原理 Q 卷

五、请给对文法 G[S]进行改写成 LL(1)文法,并给出改写后文法的预测分析表, 要求计算出改写后文法各非终极符的 FIRST 和 FOLLOW 集合。 (15 分) S → S*aA | aA| *aA A→ +aA | +a 六、请构造出文法 G[S]识别文法活前缀的有限自动机,请确定是否是 SLR(1)

第 50 页共 6 页

文法,如果是,则构造出其 LR 分析表。 (12 分) A→aAd |aAb |ε 七、为文法 S?(L)|a L?L,S|S 写一个属性翻译文法,它输出文法中 a 的个数。(10 分) 八、考虑下面的三地址语句序列,完成下列任务。 (1)在该代码中用水平的横线将代码分成基本块,并给每个基本块一个序 号。 分) (2 (2)画出该代码的控制流图,每个基本块就用(1)的序号表示。 分) (3 (3)若有循环的话,列出构成每个循环的结点,并指出循环的入口结点。 (6 分) 答案: 5 答:改写文法如下: S?*aAS’ | aAS’ S’?*AS’ | ? A?+aA’ A’?A | ? FIRST {*,a} {*,?} {+} {+,?} * ?*aAS’ ?*AS’ ?? a ? aAS FOLLOW {#} {#} {*,#} {*,#} + # ?? ?+aA’ ?A ??

S S’ A A’ 预测分析表: S S’ A A’

6 答:拓广文法(1)S?A (2)A?aAd (3)A?aA
A S?.A I0 A?.aAd A?.aAb A?. S?A. a A?a.Ad A?a.Ab A?.aAd A?.aAb A?. I2 I1 A

(4)A?ε

A?aA.d I3 A?aA.b a b A?aAb. I5

d

A?aAd. I4

在 I0 和 I2,I3 中存在有移进 归约冲突

第 51 页共 6 页

但是 FOLLOW(A)={d,b,#} a I0 S2 I1 I2 S2 I3 I4 I5

{a }?{d,b,#}=?,所以文法是 SLR(1)文法 d # A r4 r4 1 acc r4 r4 r4 3 S5 S4 r2 r2 r2 r3 r3 r3 b r4

7 解:S’?S {printf(S.a)} S ? ( L ) {S.a=L.a} S? a {S.a=1} L ? L , S {L.a=L1.a+S.a} L? S {L.a=S.a} 8 解: (1) b := 1 b := 2 if w <= x goto L3 L1: e := b 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 goto L2 (2)
1

(1)

(2)

2 6

4

5

(3) (4) (5)

3

7

(6) (7)

(3)回边 3?4,结点 5、7、3 和 4 构成一个循环,其中 4 是入口结点。
编译原理 R 卷 1. (20 分)写出字母表? = {a, b}上语言 L = {w | w 中 a 的个数是偶数}的正规式,并画出接受 该语言的最简 DFA。 2. (15 分)考虑下面的表达式文法,它包括数组访问、加和赋值: E ? E[E] | E + E | E = E | (E) | id 该文法是二义的。请写一个接受同样语言的 LR(1)文法,其优先级从高到低依次是数组访问、 加和赋值,并且加运算是左结合,赋值是右结合。 3. (10 分)下面是产生字母表? = { 0, 1, 2}上数字串的一个文法: S?DSD|2 D?0|1 写一个语法制导定义,它打印一个句子是否为回文数(一个数字串,从左向右读和从右向左 读都一样时,称它为回文数) 。

第 52 页共 6 页

答案:
1.语言 L 的正规式是: (a b*a | b)* 或 b*(a b*a b*)* 接受该语言的最简 DFA 是: b start 1 a a 2 b

2.

E?T=E|T T?T+F|F F ? F[E] | (E) | id S? ? S S ? D1 S1 D2 S?2 D?0 D?1 print(S.val) S.val = (D1.val = D2.val) and S1.val S.val = true D.val = 0 D.val = 1

3.

编译原理 S 卷 1. (15 分) (a) 字母表? = { ( , ) }上的语言{ ( ), (( )( )), ((( ))), ( )( )( )( )( )}是不是正规语言?为什么? (b) 正规式 (0 | 1)* 和( (? | 0) 1* )*是否等价,说明理由。 2. (15 分)接受文法 S?Aa|bAc|dc|bda A?d 活前缀的 DFA 见下图。请根据这个 DFA 来构造该文法的 SLR(1)分析表,并说明该文法为什么 不是 SLR(1)文法。 S’ ? .S S ? .A a S ? .b A c S ? .d c S ? .b d a A ? .d I0 S S’ ? S . I1 S ? A .a I2 S ? b .A c S ? b .d a A ? .d I3 S?dc. I8 a S?Aa. I5 S ? b A .c I6 S ? b d .a A?d. I7 c S?bAc. I9 S?bda. I10

A

b d S ? d .c A?d. I4

A

d

a

c

3. (10 分)现有字母表?={ a },写一个和正规式 a*等价的上下文无关文法,要求所写的文法

第 53 页共 6 页

既不是 LR 文法,也不是二义文法。 4. (20 分) (a) 下面的文法定义语言 L = { anbncm | m, n ? 1}。写一个语法制导定义,其语义规则的作 用是:对不属于语言 L 的子集 L1= { anbncn | n ? 1}的句子,打印出错信息。 S?DC D?aDb|ab C?Cc|c (b) 语句的文法如下: S ? id := E | if E then S | while E do S | begin S ; S end | break 写一个翻译方案,其语义动作的作用是:若发现 break 不是出现在循环语句中,及时报告错 误。

答案
1. (a) 语言{ ( ), (( ) ( )), ((( ))), ( ) ( ) ( ) ( ) ( )}是正规语言,因为该语言只包括有限个句子,它 可以用正规式定义如下: ( ) | (( )( )) | ((( ))) | ( ) ( ) ( ) ( ) ( ) (b) 我们分析正规式( (? | 0) 1* )*表示的语言。 可以看出正规式(? | 0) 1*描述的语言是集合 {?, 1, 11, 111, …, 0, 01, 011, 0111, …-,它含长度为 1 的两个串 0 和 1。那么,(0 | 1)* 所描述的 语言是( (? | 0) 1* )* 所描述的语言的子集,因为(0 | 1)* 表示字母表{0, 1}上所有串的集合,因 此( (? | 0) 1* )* 所描述的语言不可能再有更多的句子,因而也是表示字母表{0, 1}上所有串的 集合。 2.分析表如下。因为有两处有移进-归约冲突,所以该文法不是 SLR(1)文法。 注:Fallow(A) = {a, c} 动作 转移 状态 S A a b c d $

0 1 2 3 4 5 6 7 8 9 10 3.满足条件的一个文法如下: S?aSa|a|? 4. (a) 语法制导的定义如下: S?DC D?ab D ? a D1 b C?c s10, r5 r5 s5

s3

s4 acc s7 s8, r5 r1 s9 r3 r2 r4

1

2

6

if D.length ? C.length then print (“error”) D.length := 1 D.length := D1.length + 1 C.length := 1

第 54 页共 6 页

C ? C1 c C.length := C1.length + 1 (b) 翻译方案如下: S? ? {S.loop := false}S S ? id := E S ? if E then {S1.loop := S.loop}S1 S ? while E do {S1.loop := true}S1 S ? begin {S1.loop := S.loop}S1 ; {S2.loop := S.loop}S2 end S ? break{if not S.loop then print(“error”) } 编译原理 T 卷 1、 (15 分) (a) 用正规式表示字母表{a, b}上,a 不会相邻的所有串。 b*(abb*)*(a| ?) (b) 画出一个最简的确定有限自动机,它接受所有大于 101 的二进制整数。 2、 (10 分)构造下面文法的 LL(1)分析表。 S?aBS|bAS|? A?bAA|a B?aBB|b 3、 (10 分)下面的文法是二义文法 S?E E ? while E do E | id := E | E + E | id | (E) 请你为该语言重写一个规范的 LR(1)文法,它为该语言中的各种运算体现通常的优先级和结 合规则。不需要证明你的文法是规范 LR(1)的。 4、 (10 分)为下面文法写一个语法制导的定义,它完成一个句子的 while-do 最大嵌套层次 的计算并输出这个计算结果。 S?E E ? while E do E | id := E | E + E | id | (E) 8、 5 分) ( 把下面左边的文件 file1.c 提交给编译器, 编译器没有报告任何错误。 而把文件 file2.c 提交给编译器,错误报告如下: file2.c: 2: error: conflicting types for ‘func’ file2.c: 1: error: previous declaration of ‘func’ 试分析原因。 (在这两个文件中, 1 行都是函数 func 的原型, 2 行都是函数 func 的定义, 第 第 函数体为空。 ) file1.c file2.c int func(double); int func(double); int func(f) float f; {} int func(float f) {} 9、 分)教材上第 342 页倒数第 7 行说“将 C++语言中一个类的所有非静态属性构成一个 (5 C 语言的结构类型,取类的名字作为结构类型的名字” 。在这一章都学过后,你认为这句话 需要修改吗?

答案
1、 (a) b*(abb*)*(a| ?) (b) 见下图。若不允许前缀的无效 0,则去掉状态 0 上的 0 转换。 0 start 0 1 1
3, 4, 5

1 0, 1

0

2

0, 1 >5
第 55 页共 6 页

0, 1

2、 开始符号集合和后继 符号集合 LL(1)分析表 First Follow S A B a, b, ? a, b a, b $ a, b, $ a, b, $ 3 、 S A B

a S?aBS A?a B?aBB

b S?bAS A?bAA B?b

$ S??

S?E E ? while E do E | A A ? id := A | T T?T+F|F F ? id | (E) 4、 语法制导的定义如下: S?E print(S.loop); E ? while E1 do E2 E.loop := max(E1.loop, E2.loop) +1; E ? id := E E.loop := E1.loop; E ? E1 + E2 E.loop := max(E1.loop, E2.loop); E ? id E.loop := 0; E ? (E1) E.loop := E1.loop; 8、文件 file1.c 中,函数 func 的定义采用传统的方式,形式参数 f 的类型被提升到 double。 函数原型中该参数也声明成 double 类型,两者类型相同,因此没有错误。 而在文件 file2.c 中,函数 func 的定义采用现在提倡的形式,形式参数的类型就是 float, 不会提升。它的类型和函数原型中声明的类型不相同,所以编译器会报告错误。 9、需要修改,增加虚方法表指针作为第一个域。 编译原理 U 卷 1. (20 分)写出字母表? = {a, b}上语言 L = {w | w 的最后两个字母是 aa 或 bb}的正规式,并 画出接受该语言的最简 DFA。 2. (15 分)说明下面的文法不是 SLR(1)文法,并重写一个等价的 SLR(1)文法。 S?Ma|bMc|dc|bda M?d 3. (10 分)为下面的语言写一个无二义的文法: ML 语言中用分号分隔语句的语句块,例如: ( (s ; s ) ; ( s ; s ; s ) ; s ) ; ( s ; s ) 6. (15 分)考虑下面的三地址语句序列: b := 1 b := 2 if w <= x goto L2

第 56 页共 6 页

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)若有循环的话,列出构成每个循环的结点。 7. 分)如果 (5 (1)用编译命令 cc test.c 会报告有未定义的符号; (2)用编译命令 cc test.c –lusr.a 会得到可执行程序(–lusr.a 表示连接库 libusr.a) 。 那么,用编译命令 cc test.c –lusr.a –lusr.a 是否会报告有多重定义的符号?请说明理由。 答案 1.语言 L 的正规式是: (a|b)*(aa|bb) 接受该语言的最简 DFA 是: a a start 0 b a 2 S’ ? S 1 b a a b b 4 M?d 3 b

2.

S?Ma|bMc|dc|bda

S’ ? .S S ? .M a S ? .b M c S?.dc S?.bda M ? .d

b

S ? b .M c S ? b .d a M ? .d

d

S ? b d .a M?d.

因为 a 是 M 的后继符号之一,因此在上面最右边一个项目集中有移进?归约冲突。 等价的 SLR(1)文法是 S?da|bdc|dc|bda 3. 6. (1) SL ? S | SL ; S S ? s | ( SL ) (2)

第 57 页共 6 页

b := 1 b := 2 if w <= x goto L2 (1) e := b goto L2 (2) L1: goto L3 (3) L2: c := 3 b := 4 c := 6 (4) L3: if y <= z goto L4 (5) goto L5 (6) L4: g := g + 1 h := 8 goto L1 (7) L5: h := 9 (8) (3)结点 5、7 和 3 构成一个循环,其中 5 是入口 结点。

1 2 5 6 7 4

8

3

7.不会。连接时,第一次遇到库 libusr.a 便能解决所有的外部引用。这样在第二次遇到库 libusr.a 时什么东西也不会加入目标程序。
12.试写出 VT={0,1}上下述集合的正则表达式: ⑴ 所有以 1 开始和结束的符号串。 ⑵ 恰含有 3 个 1 的所有符号所组成的集合。 ⑶ 集合{01,1}。 ⑷ 所有以 111 结束的符号串。
*

1(0|1) 1|1 * * * * 0 10 10 10 01|1 * (0|1) 111
*

⑴ 试写出非负整数集的正则表达式。 0|(1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9) ⑵ 试写出以非 5 数字为头的所有非负整数集的正则表达式。 * 0|(1|2|3|4|6|7|8|9)(0|1|2|3|4|5|6|7|8|9) 设 VT={a,b},试构造下述正则表达式的确定性有限状态自动机: * ⑴ a(a|b) baa

⑵ (a|b) bbb

*

*

编译原理 V 卷

1. (6 分)回答下列问题 在存储管理中,为什么在活动记录内为临时变量分配空间? 1)在符号表管理中,为什么将变量名保存在符号表中? 2. (8 分)试消除下列文法中的左递归。 S → SaA|Se|B A → BbA|B B → cSd|? 3. (15 分)写出下列文法中各候选式的 FIRST 集和各非终结符的 FOLLOW 集,构造 该文法的 LL(1)分析表,并说明它是否为 LL(1)文法。

第 58 页共 6 页

S → aA|BA A→ cB|? B → bB|? 4.(18 分)给定文法 G[S] S → L + L |L L → LB|B B → 0|1 (1) 构造拓广文法,按 LR(0)分析的需要画出识别这个拓广文法的所有规范句型 活前缀的 DFA。 (2) 求出这个文法的 SLR(1)分析表 5.(7 分)写出能产生字母表{x,y}上的不含两个相邻的 x,且不含两个相邻的y 的全体符号串的有限状态自动机。 6.(16 分)设文法 G[E]:E → RP|P P → (E)|i R → RP+| RP* |P+|P* 画出句子 i+i*(i+i)的语法分析树,给出其最右推导和最左归约,并指出它的 句柄。 7. (10 分)下面是关于文法 S → xYS|yXS|? X → yXX|x Y → xYY|y 的一个语法制导定义, S → xYS1 S.nx := S.ny := S → yXS1 S.nx := S.ny := S → ? S.nx := S.ny := X → yX1 X2 X.nx := X.ny := X → x X.nx := X.ny := Y → xY1 Y2 Y.nx := Y.ny := Y → y Y.nx := Y.ny :=

Y.nx + S1.nx + 1 Y.ny + S1.ny X.nx + S1.nx X.ny + S1.ny + 1 0 0 X1.nx + X2.nx X1.ny + X2.ny + 1 1 0 Y1.nx + Y2.nx + 1 Y1.ny + Y2.ny 0 1

(1) 请说明上述语法制导定义的作用是什么。 (2) 按照此语法指导定义给出句子 xxxyyyxy 的语义分析过程或画出带注 释的语法分析树.
答案: 1 答:在栈式存储管理方式中,以活动记录的形式为一次过程调用(函数调用)中的局 部数据提供存储空间,该活动记录随过程调用被分配,随过程调用的结束而释放;临时变量

第 59 页共 6 页

通常用于保存表达式计算中的中间结果,在活动记录中为临时变量分配空间,可以保证该空 间随过程调用被分配,随活动记录的释放被自动释放。 答:符号表中将保存变量名及其各种属性,变量名将用于变量的识别、涉及变变量名与 存储空间的绑定、以及类型、作用域、存储地址等各种变量属性的设置、获取等各种维护功 能。

2 解: 消除左递归 S → SaA|Se|B → S(aA | e )| B 引进非终结符 S’ S → BS’ S’→(aA | e )S’ | ?

提取左因子 A → BbA | B → B ( bA | ?) 引进非终结符 A’ A →B A’ A’ → bA | ?

改写后的文法 S → BS’ S’ → aA S’ | e S’ | ? A →B A’ A’ → bA | ? B → cSd|?

3 解:各候选式的 FIRST 集 (4 分) FIRST(aA)={a} FIRST(BA)={ b,c,? } FIRST(cB)={c} FIRST(?)={?} FIRST(bB)={ b } FIRST(?)={?} 各非终结符的 FOLLOW 集 (4 分) FOLLOW(S)= {#} FOLLOW(A)= {#} LL(1)分析表 a S A B S → aA (5 分) b S → BA B → bB

FOLLOW(B)= { c,#}

c S → BA A → cB B → ?

# S → BA A → ? B → ?

说明它是否为 LL(1)文法 (2 分) 判断 1 分,理由 1 分 因为 LL(1)分析表无冲突,所以该文法是 LL(1)文法。 4 解 1:相应的 DFA 如下图所示。 I0: I7: 解 ˊ→.S S 2: B L →LB. 0 S →.L+ 0L S 1 Sˊ→ B 1 S →0 L 2 + 6 L 8 I2: S →.L L S → L.+ L 2 S →0 L2 L →.LB 3 L →0,6 L 2,8 B 7 S → L. L →.B 4 L →0,6 B 3 L → L.B + B →.0 5 B →0,2,6,8 0 4 B →.0 I6: I8: 6 B →.→0,2,6,8 1 5 B 1 B →.1 S →L + .L I0:{(0,0)(1,0)(2,0)(3,0)(4,0)(5,0)(6,0)} S →L + L. , , , , , L L →.LB , 0 L → L.B I1:{(0,1)} 0 1 L →.B B B →.0 B B →.0 B →.1 I4: B →.1 B →0. I3: 第 60 页共 6 页 0 L →B. 1 I5:
0 1 S

I1: Sˊ→ S.

1

I2:{(1,1)(2,1)(3,1)(5,0)(6,0)} , , , , I3:{(4,1)} I4:{(5,1)} I5:{(6,1)} I6:{(1,2)(3,0)(4,0)(5,0)(6,0)} , , , , I7:{(3,2)} I8:{(1,3)(3,1)(5,0)(6,0)} , , , I0: (0,0) , (1,0) , (2,0) , (3,0) , (4,0) , (5,0) , (6,0)
0 1 S

I1: (0,1)
B

I7: (3,2)
B

L

I2: (1,1) , (2,1) , (3,1) , (5,0) , (6,0)
0 1

+

I4: (5,1) (2)解: I5: (6,1)

B

B

I3: (4,1)
0

I6: (1,2) , (3,0) , (4,0) , (5,0) , (6,0)
1

L

I8: (1,3) , (3,1) , (5,0) , (6,0)
0 1

给产生式编号:①S→L + L ②S→L ③L→LB ④L→B ⑤B → 0 ⑥B→1 FOLLOW(S)={#} FOLLOW(L)={0,1,+,#} FOLLOW(B)={0,1,+,#}
状态 0 1 2 3 4 5 6 7 8 ACTION 0 S4 S4 r4 r5 r6 S4 r3 S4 1 S5 S5 r4 r5 r6 S5 r3 S5 + # acc r2 r4 r5 r6 8 r3 r3 r1 S 1 GOTO L 2

B 3 7

S6 r4 r5 r6

3 7

5 解:

第 61 页共 6 页

x 1 0 y 2 y x

6 解: (1)语法分析树:
E R R P * ( P E ) P + i

P

+

i P

R

i i

(2) 最右推导: E? RP ? R(E) ? R(RP) ? R(Ri) ? R(P+i) ? R(i+i) ? RP*(i+i) ? Ri*(i+i) ? P+i*(i+i) ? i+i*(i+i)

最左归约: i+i*(i+i) ? P + i*(i+i) P+i*(i+i) ? Ri*(i+i) Ri*(i+i) ? RP*(i+i) RP*(i+i) ? R(i+i) R(i+i) ? R(P+i) R(P+i) ? R(Ri) R(Ri) ? R(RP) R(RP) ? R(E) R(E) ? RP RP ? E 句子 i+i*(i+i)的句柄为:i;
编译原理 W 卷 例1 求表达式文法的语法符号的 FIRST 集和 FOLLOW 集 表达式文法: E→TE' E'→+TE’|ε T→FT' T'→*FT’|ε F→(E)|id

第 62 页共 6 页

例 2 消除下述文法的左递归。 S→Ac|c A→Bb|b B→Sa|a 例 3 已知文法G: S → ( L | a L → S , L | ) (1)构造文法 G 的预测分析表。 (2)若输入串为“ (a,” ),请给出语法分析过程。 例 4 给定文法 G=( i,d,'(',')'}{E,A} { , ,E,P) 其中 P: E → iA E → EA A → i A → d A → ( E ) (1)消除左递归; (2)计算改写后文法中各非终结符的 FIRST 集和 FOLLOW 集; (3)构造改写后文法的预测分析表;该文法是 LL(1) 文法吗?。 例 5 if 语句的原始文法 S→ if E then S |if E then S else S |other 存在左因子 if E then S,改写此文法消除左因子。. 例 6 构造简单算术表达式的分析器

附加题 将左线性文法 G=(VN,VT,P,S)转换成等价的有限状态自动机 M=(Q,VT, δ ,q0,F)的一种等价变换中认为“对产生式 A→Ba∈P 则 M 中用移动 A∈δ (B, a)与之对应” ,请问这种对应使用的是自顶向下的分析思想还是自底向上的分析 思想?为什么?(本题第一问最高奖励 3 分,第二问最高奖励 7 分)
答案

1 解:FIRST(F)={(,id} FIRST(T)=FIRST(F)={(,id} FIRST(E)=FIRST(T)={(,id} FIRST(E')={+,ε } FIRST(T')={*,ε } FIRST(+)={+}, FIRST(*)={*} FIRST( ( )={(} FIRST( ) )={)} FIRST(id)={id} FOLLOW(E) = { #, ) } FOLLOW(E')= FOLLOW( E ) = { #, ) } FOLLOW(T) = FIRST(E’)∪FOLLOW(E)∪FOLLOW(E’) = ,+,),#FOLLOW(T')= FOLLOW(T)= {+,},#} FOLLOW(F) = FIRST(T’)∪FOLLOW(T)∪FOLLOW(T’) =,*,+,-,#2【解】先将间接左递归,变成直接左递归 将 B 的定义代入 A 产生式得:A→Sab|ab|b, 将 A 的定义代入 S 产生式得: S→Sabc|abc|bc|c 采用引进新的非终结符的方法消除直接左递归: S→abcS’|bcS’|cS’ S’→abcS’|ε

第 63 页共 6 页

删除“多余的”产生式:A→Sab|ab|b 和 B→Sa|a 得到文法 G[S]: S→abcS’|bcS’|cS’ S’→abcS’|ε 3【解】 (1) 1)求各非终结符的 FISRT 集和 FOLLOW 集: FIRST(S) = { (, a ) FIRST(L) = { a }? FIRST(S) = { (, ), a } FOLLOW(S) = , ’,’, # FOLLOW(L) = FOLLOW(S) =, ’,’, # 2)预测分析表: ( a , } # S S→ ( L S→ a L L→ S , L L→ S , L L → ) (2)对输入串 “ (a,”的分析处理过程如表 1 所示。 ) 表 1 对输入串 “ (a,”的分析过程 ) 步骤 分析栈 输入串 所用产生式 0 #S (a, )# 1 #L( (a, )# S → (L 2 #L a, )# 3 #L, S a, )# L → S,L 4 #L, a a, )# S→a 5 #L, , )# 6 #L )# 7 #) )# L → ) 8 # #

4【解】 (1)消除左递归后的文法为: E → iAE' E'→ ? | AE' A → i A →d A → (E) (2)各非终结符的 FISRT 集和 FOLLOW 集 FIRST( E ) ={i} FIRST(E') = {i, d, (, ?) FIRST( A ) ={i, d, () FOLLOW( E ) ={?, # } FOLLOW(E') ={ }, # } FOLLOW( A ) ={i, d, (, ), # } (3)改写后文法的预测分析表: ( ) i d E E→iAE' E' E'→AE' E'→AE' E'→AE' E →? A A→i A→d A→ (E) 预测分析表中无多重入口,因此该文法是 LL(1) 文法. # E→ ?

5【解】引进非终结符 S’ S'→ε |else S

第 64 页共 6 页

提取左因子:S→ if E then SS’|other 改写后的文法: S→ if E then SS’|other S'→ε |else S

6【解】E 的子程序(E→T(+T)*) procedure E; begin T; T的过程调用 while lookhead='+' do begin 当前符号等于+时 match(‘+’); 处理终结符+ T T的过程调用 end end; lookhead:当前符号 T 的子程序(T→F(*F)*) procedure T; begin F; F 的过程调用 while lookhead='*' then begin 当前符号等于*时 match('*'); 处理终结符* F F 的递归调用 end end; F 的子程序(F→(E)|id) procedure F; begin if lookhead='(' then begin 当前符号等于( match('('); 处理终结符( E; E 的递归调用 match(')'); 处理终结符) end else if lookhead=id then match(id) 处理终结符 id else error 出错处理 end 主程序 begin lookhead:=nexttoken; 调词法分析程序 E E 的过程调用 end 服务子程序 procedure match(t:token); begin if lookhead=t then lookhead:=nexttoken

第 65 页共 6 页

else error end; 7 解:

出错处理程序

(1)该语法制导定义的作用是统计句子中的 x 和 y 的个数; 分) (4 (2)按照该语法制导定义对句子 xxxyyyxy 进行语义分析的结果为: S.nx = 4;S.ny = 4; 分) (6

第 66 页共 6 页

附加题解:

使用的是自底向上的分析方法——归约。 A∈δ (B,a)表示在状态 B 遇到输入 a 时,到达状态 A,将状态看成是目前已 经分析出来的中间结果,这样就相当于目前的分析已经得到了前缀 B,加上 a 后 相当于获得前缀 A,也就是相当于 B 和紧接着的 a 可以归约成 A,这与产生式 A →Ba 所表示出来的意义是相同的, 所以产生式 A→Ba∈P 则 M 中用移动 A∈δ (B, a)与之对应。 (答到这里可以得 4 分) 要得满分 7 分,必须根据上述思路给出“对于任意的左线性文法 G,存在 FA M 与之等价:L(M)=L(G)”即:先构造与给定文法 G=(VN,VT,P,S)等价的 FA M,然后 证明所构造的 FA 与所给的文法 G 等价。
编译原理 X 卷
四、简述题(每题 4 分,共 24 分) 1、考虑下面程序 Var a:integer; Procedure S(X); Var X:integer; Begin a:=a+1; X:=a+X End; Begin a:=5; S(a); Print(a) End. 试问:若参数传递方式分别采取传名和传值时,程序执行后输出 a 的值是什么? 2、画出 Pascal 中实数(不带正负号,可带指数部分)的状态转换图。 3、写出表达式(a+b*c)/(a+b)-d 的逆波兰表示及三元式序列。 4、已知文法 G(S) S→a|∧|(T) T→T,S|S 写出句子((a,a),a)的规范归约过程及每一步的句柄。 5、何谓优化?按所涉及的程序范围可分为哪几级优化? 6、目标代码有哪几种形式?生成目标代码时通常应考虑哪几个问题? 五、计算题(共 41 分) 1、写一个文法,使其语言是奇数集,且每个奇数不以 0 开头。(5 分) 2、设文法 G(S): S→(L)|a S|a L→L,S|S (1)消除左递归和回溯; (2)计算每个非终结符的 FIRST 和 FOLLOW; (3)构造预测分析表。 3、While a>0 ∨b<0 do Begin X:=X+1; if a>0 then a:=a-1 else b:=b+1 End; 翻译成四元式序列。(7 分) 4、已知文法 G(E) E→T|E+T T→F|T *F F→(E)|i (1)给出句型(T *F+i)的最右推导及画出语法树; (2)给出句型(T *F+i)的短语、素短语。(7 分)

第 67 页共 6 页

5、设布尔表达式的文法为 E →E(1)∨E(2) E →E(1)∧E(2) E →i 假定它们将用于条件控制语句中,请 (1)改写文法,使之适合进行语法制导翻译和实现回填; (2)写出改写后的短个产生式的语义动作。(6 分) 6、设有基本块 T1:=2 T2:=10/T T3:=S-R T4:=S+R A:=T2 *T4 B:A T5:=S+R T6:=T3 *T5 B:=T6 (1)画出 DAG 图; (2)假设基本块出口时只有 A,B 还被引用,请写出优化后的四元序列。(6 分)

答案:
四、简述题 1、答:传名:a=12 (2 分) 传值:a=6 (2 分) 3、答:逆波兰表示: abc*+ab+/d- (2 分) 三元式序列: ① (*,b,c) ② (+,a,①) ③ (+,a,b) ④ (/,②,③) ⑤ (-,④,d) (2 分) 4、答: 句型 归约规则 句柄 ((a,a),a) S→a a ((S,a),a) T→S S ((T,a),a) S→a a ((T,S),a) T→T,S T,S ((S),a) T→S S ((T),a) S→S(T) (T) (S,a) T→S S (T,a) S→a a (T,S) T→T,S T,S (T) S→(T) (T) S (4 分) 5、 答:优化:对程序进行各种等价变换,使得从变换后的程序出发,能产生更有效的目标代码。 (2 分) 三种级别:局部优化、循环优化、全局优化。 (2 分) 6、 答:目标代码通常采用三种形式:机器语言,汇编语言,待装配机器语言模块。(2 分) 应着重考虑的问题: (1)如何使生成的目标代码较短; (2)如何充分利用寄存器,以减少访问内存次数; (3)如何充分利用指仅系统的的特点。 (2 分) 五、计算题 1、解:文法 G(N): N→AB|B A→AC|D B→1|3|5|7|9 D→B|2|4|6|8

第 68 页共 6 页

C→0|D 2、解:(1)

(5 分)

S→(L)|aS' S'→S|ε L→SL' L'→SL'|ε 评分细则:消除左递归 2 分,提公共因子 2 分。 (2) FIRST)S)={(,a} FOLLOW(S)={#,,)} , FIRST(S')={,a,εFOLLOW(S')={#,,)} , FIRST(L)={(,a} FOLLOW(L)={ )} FIRST(L')={, ,εFOLLOW(L'〕={ )} 3、解: (1) (j>,a,0,5) (2) (j,-,-,3) (5) (+,×,1,T1) (6) (:=,T1,-,×) (7) (j≥,a,0,9) (8) (j,-,-,12) (9) (-,a,1,T2) (10) (:=,T2,-,a) (11) (j,-,-,1) (12) (+,b,1, T3) (13) (:=,T3,-,b) (14) (j,-,-,1) (15) 评分细则:控制结构 4 分,其它 3 分。 4、解:(1) 最右推导: ETF(E)(E+T)(E+F)(E+i) (T+i)(T*F+i) (2) 短语:(T*F+i),T*F+i,T*F,i (2 分) 素短语:T*F,i 5、解:(1) E0→E(1) E→E0E(2) EA→E(1) E→EAE(2) E→i (2) E→E(1) {BACKPATCH(E(1)· FC,NXQ); E0· TC:=E(1)· TC} E→E0E(2) {E· FC:=E(2)· FC; E· TC:=MERG(E0· TC,E(2)· TC)} EA→E(1) {BACKPATCH(E(1)· TC,NXQ); E0· FC:=E(1)· FC} E→EAE(2) {E· TC:=E(2)· TC; E· FC:=MERG(EA· FC,E(2)· FC} E→i {E· TC:=NXQ;E· FC:=NXQ+1; GEN(jn2,entry(i),-0); GEN(j,-,-,0) 6、解:(1)DAG: (2) 优化后的四元式 T3:=S-R T4:=S+R A:=5*T4 B:=T3+T4

(1 分)

(3 分)

(3 分)

(3 分)

第 69 页共 6 页

编译原理 Y 卷 二、简答题(每小题 5 分,共 20 分) 1 . LL ( 1 )分析法对文法有哪些要求? 2 .常见的存储分配策略有几种?它们都适合于什么性质的语言? 3 .常见循环优化都有哪些项目? 4 .什么是活动记录?它主要由哪些内容构成? 三、 8 分)化简文法 G[S] : ( S → ASe | BCaD | aD | AC A → Cb | DBS C → bC | d B → Ac D → aD 四、 12 分) 设 L í{a,b,c}* 是满足下述条件的符号串构成的语言: ( (1)若出现 a ,则其后至少紧跟两个 c ; (2)若出现 b ,其后至少紧跟一个 c 。 试构造识别 L 的最小化的 DFA ,并给出描述 L 的正规表达式。 五、 12 分) 已给文法 G[S] : S → SaP | Sf | P P → qbP | q ( 将 G[S] 改造成 LL ( 1 )文法,并给出 LL ( 1 )分析表。 六、 12 分) 给定文法 G[S] : S → Aa|dAb|Bb|dBa A → c B → c ( 构造文法 G[S] 的 LR ( 1 )分析表。 七、 8 分) 将下面的条件语句表示成逆波兰式和四元式序列: ( if a>b then x:=a+b*c else x:=b-a; 八、 8 分) 给定基本块: ( A:=3*5 B:=E+F C:=A+12 D:=E+F A:=D+12 C:=C+1 E:=E+F 假定出基本块后,只有 A 、 C 、 E 是活跃的,给出用 DAG 图完成优化后的代码序列。 参考答案: 二、 1 .对于 G 中的每个产生式 A →γ 1 | γ 2 | … | γ m ,其各候选式均应满足: (1)不同的候选式不能推出以同一终结符号打头的符号串,即 FIRST( γ i ) ∩ FIRST( γ j )= φ( 1 ≤ i , j ≤ m ; i ≠ j ) (2)若有 γ j ε,则其余候选式 γ i 所能推出的符号串不能以 FOLLOW(A) 中的终结符号 开始,即有 FIRST( γ i ) ∩ FOLLOW(A)= φ( i ≤ 1,2, … ,m ; i ≠ j ) 2 .有三种分配存储空间的方式: 1 ) 静态分配 若在编译阶段就能确定源程序中各个数 ( 据实体的存储空间大小,则可以采用较简单的静态存储管理。 适合 静态管理 的语言应具 备条件: 数组上下界是常数、过程调用不允许递归、不允许动态建立数据实体。 ( 2) 栈 式分配 适用于允许递归调用的程序设计语言 ; 3 ) 堆式分配 对于允许程序在运行时为 ( 变量 动态申请和释放存储空间 的语言 , 采用 堆式分配 是最有效的解决方案 。 3 .不变运算外提;运算强度削弱;消除归纳变量;下标变量地址计算优化。 4 . 一个过程的一次执行所需信息的管理,是通过称为 活动记录 的连续存储块来实现的。 活动记录的主要内容有: 1) 临时变量域 存放目标程序临时变量的值; 2 )局部数据 ( ( 域 存放过程本次执行时的局部数据、简单变量及数组内情向量等; 3 )机器状态域 保存 ( 在调用过程前有关机器状态的信息, 包括各寄存器的当前值及返回地址等; 4 ) ( 存取链 为 访问其它活动记录中所存放的非局部数据所提供的链地址; 5 )控制链 指向主调过程的 ( 活动记录; 6 )实参 存放主调过程为被调用过程所提供的实参信息; 6 )返回值 为主 ( ( 调过程存放被调过程的返回值

第 70 页共 6 页

三、化简后: S → ASe|AC A → Cb C → bC | d 四、 DFA 如图所示。相应的正规式为 (c|acc|bc)* 。

五、 改造后的文法: S → PS' S' → aPS'| fS' | e P → qP' P' → bP | e 各候选式的 FIRST 集,各非终结符的 FOLLOW 集为 产生式 FIRST 集 FOLLOW 集 S → PS' {q} {#} S' → aPS' {a} {#} → fS' {f} →e {e} P → qP' {q} {a,f,#} P' → bP {b} {a,f,#} →e {e} LL(1) 分析表为

六、分析表如下图所示

七、 1 )逆波兰式: ( ,其中, BLE 表示汪或等于时的转向指 令; * … ] 表示标号。 ( 2 )四元式: (1) ( j>, a, b, (3)) (2) ( j, , , (7) ) (3) ( *, b, c, T1) (4) ( +, a, T1, T2) (5) ( :=, T2, , x) (6) ( j, , , (9)) (7) ( -, b, a, T3) (8) ( :=, T3, , x) (9) ( … … ) 八、化简后的的四元式序列为 A :=D+12 E :=E+F C :=28

第 71 页共 6 页

编译原理 Z 卷 三、 (10 分)给定文法 G=({S,L},{a, )},,S→(L)|a L→L,S|S-,S) (, 。给出句型”(S,(a))”的推 导和语法树并指出此句型的所有短语、直接短语、句柄和素短语。 四、 (12 分)设语言 L 是由奇数个 a 和偶数(可以是 0)个 b 组成的符号串之集。 1.构造识别 L 的 DFA;2. 给出定义 L 的正规文法; 五、 分) (10 将文法 G[S]: S→*A A→AS|B+ B→Bi|i 改写为等价的 LL(1)文法, 并给出相应的 LL(1) 分析表。 七、 分)某语言算术表达式的文法定义为 E→E+E|i| if B then E else E 其中,第三个候选式 (8 称为条件算术表达式,B 为布尔表达式,then 及 else 后的 E 均为算术表达式(即简单算术表 达式或条件表达式) ,其语义为,当 B 为真时,表达式的值取 then 后的 E 的值,否则取 else 的 E 的值。假定所有表达式是整型的,试将下面关于条件算术表达式的属性翻译文法填写完 全:

八、 (8 分)给定 PASCAL 程序语句 while a>b do if a>0 then a:=a-1 else a:=a+1; 1. 将该语句翻译成逆波兰式; 2. 给出编译程序扫描到 then 处及分号处时所得的四元式序列。 九、 (7 分)用 DAG 图对下面的基本块进行优化(假定出基本块后只有 A、G、L 是活跃的) : A=B*C D=B/C E=2*3 F=E+2 G=B*C K=E+F G=K*KL=B/C 参考答案: 三、 解:ST(L) T(L,S) T(L,(L)) T(L,(S)) T(L,(a)) T(S,(a)) 短语有:“a”,“(a)”,“S”,“S,(a)”,“(S,(a))”。 直接短语有:”S”,“a” 句柄:“S” 素短语:“a“ 语法树略。

第 72 页共 6 页

四、 解:1。见图: 2.S?aA|bB A?aS|bC|e B?bS|aC C?bA|aB 五、 解:B?iC C ?iC |e A?B+A’ A’ ?ASA’ | e S ? [A First(ASA’)=,i-, FOLLOW(A’)=, * + FIRST(iC)={i}, FOLLOW(C) ={ ]} 可知文法满足 LL(1)文法的条件。 分析表:

七、

八、 (8 分)给定 PASCAL 程序语句 while a>b do if a>0 then a:=a-1 else a:=a+1; 1. 将该语句翻译成逆波兰式; 2. 给出编译程序扫描到 then 处及分号处时所得的四元式序列。

第 73 页共 6 页

九、解: A=B*C G=196 L=B/C 编译原理 Aa 卷

一. (10 分)改写以下文法,使其满足采用自顶向下分析方法的要求。 S ? aXcY| Yd X ? XaY| c Y ? bYcX| b 二. (15 分)考虑文法 G[S]: S ? xSNy| Nx N ? zN|ε ε 1. 求出该文法的每个非终结符的 FOLLOW 集; 2. 构造该文法的预测分析表。 三. (20 分)符号串 xxyyyx 是如下文法 G[S]的句子, S ? xB | yA A ? xS | yAA | x B ? yS | xBB | y (1)构造该句子的分析树; (2)写出生成该句子的最左推导; (3)写出生成该句子的规范归约过程;指出每步归约中的句柄。

四. (20 分)考虑简单赋值语句的文法 G[S]: S ? id:= E E ? E + E E ? E * E E ? id (1) 试构造识别该文法所有规范句型活前缀的有限自动机。 (2) 判断该文法是否为 LR(0)文法(必须说明理由) 。 五. (15 分)考虑以下语法制导定义

第 74 页共 6 页

产生式 S ? L1 . L2 L ? L1 B

语义规则 Print( L1.val + L2.val * 2
-L2.num

)

L.val = 2 * L1.val + B.val

L.num = L1.num + 1 L ? B L.val = B.val L.num = 1 B ? 0 B.val = 0 B ? 1 B.val = 1 (1) 写出句子 11.01 的带注释分析树、或属性计算过程。 (2) 给出处理该句子的结果(Print 输出结果) 。 六(20 分)设语言 L 是“能被 5 整除的十进制正整数”组成的集合, (1)试写出描述语言 L 的正规表达式; (2)画出识别语言 L 的状态转移图。 答案: 一解: (1)消除 X ? XaY|c 的左递归 X ? cX’ X’? aYX’| ε (2)提取 Y ? bYcX|b 的左因子 Y ? bY’ Y’ ? YcX|ε 整理后,原文法变为 S ? aXcY | Yd X ? cX’ X’? aYX’|ε Y ? bZ Z ? YcX|ε 二解: 1、 FIRST(S) = { x, z } FIRST(N) = { z, ε } FOLLOW(S) = { #, y, z } FOLLOW(N) = { x, y } 2、预测分析表

x S N N?ε S?xSNy S?Nx

y

z S?Nx

#

N?ε

N ? zN

第 75 页共 6 页

3 解: (1)语法分析树
S x x B B

(6 分)

B S y A

y

y

x

(2) S?xB?xxBB?xxyB?xxyyS?xxyyyA?xxyyyx (3) 规范归约 (9 分) xxyyyx ? xxByyx 句柄为 y xxByyx ? xxByyA 句柄为 x xxByyA ? xxByS 句柄为 yA xxByS ? xxBB 句柄为 yS xxBB ? xB 句柄为 xBB xB ? S 句柄为 xB 编译原理 BB 卷

(5 分)

四、综合题
1. 已知文法 G(E) E →T|E+T T→F|T *F F →(E)|i (1)给出句型(T *F+i)的最右推导; (2)给出句型(T *F+i)的短语、简单短语、句柄、素短语、最左素短语。 解: (1) 最右推导:E ->T->F->(E)->(E + T)->(E + F)->(E + i)->(T+i)->(T*F+i) (2) 短语:(T*F+i) ,T*F+i ,T*F,i 简单短语:T*F,i 句柄:T*F 素短语:T*F,i 最左素短语:T*F 2. 构造正规式 1(0|1)*101 相应的 DFA 。 解:先构造 NFA :

第 76 页共 6 页

确定化:

重新命名,令 AB 为 B、AC 为 C、ABY 为 D 得:

第 77 页共 6 页

所以,可得 DFA 为:

3. 文法: S->MH|a H ->LSo| ε K ->dML| ε L ->eHf M->K|bLM 判断 G 是否为 LL(1) 文法,如果是,构造 LL(1) 分析表。 解:各符号的 FIRST 集和 FOLLOW集为:

各产生式SELECT集为:
SELECT S->MH S->a H ->LSo H ->ε K ->dML K ->ε L ->eHf M->K M-> bLM 预测分析表 {d,b,e,#,o} {a} {e} {#,f,o} {d} {e,#,o} {e} {d,e,#,o} {b}

第 78 页共 6 页

由于预测分析表中无多重入口,所以可判定文法是 LL(1)的。 4. 对下面的文法 G : E ->TE' E'->+E| ε T ->FT' T' ->T| ε F-> PF' F'-> *F'| ε P->(E)|a|b|^ (1)计算这个文法的每个非终结符的 FIRST 集和 FOLLOW 集。 (4 分) (2) 证明这个方法是 LL(1) 的。(4 分) (3) 构造它的预测分析表。(2 分) 解: (1)计算这个文法的每个非终结符的 FIRST 集和 FOLLOW 集。 FIRST 集合有: FIRST(E)=FIRST(T)=FIRST(F)=FIRST(P)={(,a,b,^}; FIRST(E')={+,ε } FIRST(T)=FIRST(F)=FIRST(P)={(,a,b,^}; FIRST(T')=FIRST(T)U{ε }={(,a,b,^, ε }; FIRST(F)=FIRST(P)={(,a,b,^}; FIRST(F')=FIRST(P)={*, ε }; FIRST(P)={(,a,b,^}; FOLLOW 集合有: FOLLOW(E)={),#}; FOLLOW(E')=FOLLOW(E)={),#}; FOLLOW(T)=FIRST(E')UFOLLOW(E)={+,),#};//不包含 ε FOLLOW(T')=FOLLOW(T)=FIRST(E')UFOLLOW(E)={+,),#}; FOLLOW(F)=FIRST(T')UFOLLOW(T)={(,a,b,^,+,),#};//不包含 ε FOLLOW(F')=FOLLOW(F)=FIRST(T')UFOLLOW(T)={(,a,b,^,+,),#}; FOLLOW(P)=FIRST(F')UFOLLOW(F)={*,(,a,b,^,+,),#};//不包含 ε (2)证明这个方法是 LL(1)的。 各产生式的 SELECT 集合有: SELECT(E->TE')=FIRST(T)={(,a,b,^}; SELECT(E'->+E)={+}; SELECT(E'->ε )=FOLLOW(E/)={),#} SELECT(T->FT')=FIRST(F)={(,a,b,^}; SELECT(T'->T)=FIRST(T)={(,a,b,^}; SELECT(T'->ε )=FOLLOW(T/)={+,),#}; SELECT(F->PF')=FIRST(P)={(,a,b,^}; SELECT(F'->*F')={*}; SELECT(F'->ε )=FOLLOW(F')={(,a,b,^,+,),#}; SELECT(P->(E))={(} SELECT(P->a)={a} SELECT(P->b)={b} SELECT(P->^)={^} 可见,相同左部产生式的 SELECT 集的交集均为空,所以文法 G[E]是 LL(1)文法。 (3)构造它的预测分析表。 文 法 G[E]的预测分析表如下:

第 79 页共 6 页

5.已知文法 G[S] 为: S->a|^|(T) T-> T,S|S (1) 计算 G[S] 的 FIRSTVT 和 LASTVT 。 (2) 构造 G[S] 的算符优先关系表并说明 G[S] 是否未算符优先文法。 (3) 给出输入串 (a,a)# 的算符优先分析过程。
解:(1)各符号的 FIRSTVT 和 LASTVT:

(2)算符优先关系表:

(3)句子(a,a)#分析过程如下:

6.已知文法为:
S->a|^|(T) T->T,S|S 构造它的 LR(0)分析表。 解:加入非终结符 S' ,方法的增广文法为: S'->S S->a S->^

第 80 页共 6 页

S->(T) T ->T,S T ->S 下面构造它的 LR(0)项目集规范族为:

从上表可看出,不存在移进- 归约冲突以及归约归约冲突, 该文法是 LR(0)文法。 从而有下 面的 LR(0)分析表:

7.已知文法为:
A ->aAd|aAb| ε 判断该文法是否是 SLR(1) 文法,若是构造相应分析表,并对输入串 ab# 给出分析过程。 解:增加一个非终结符 S/后,产生原文法的增广文法有: S'->A A ->aAd|aAb|ε 下面构造它 的 LR(0)项目集规范族为:

第 81 页共 6 页

从上表可看出, 状态 I0 和 I2 存在移进- 归约冲突,该文法不是 LR(0)文法。对于 I0 来说有:

FOLLOW(A)∩{a}={b,d,#}∩{a}=Φ ,所以在 I0 状态下面临输入符号为 a 时移进,为 b,d,# 时 归约,为其他时报错。对于 I2 来说有也有与 I0 完全相同的结论。这就是说,以上的移进 归约冲突是可以解决的,因此该文法是 SLR(1)文法。 其 SLR(1)分析表为:

对输入串 ab#给出分析过程为:

第 82 页共 6 页

4 解: (1) I0: S’ ? .S S ? .id = E I1: S’ ? S. I2: S ? id. = E I3: S ? id = .E E ? .E + E E ? .E * E E ? .id I4: S ? id = E. E ? E. + E E ? E. * E I5: E ? id. I6: E ? E + .E E ? .E + E E ? .E * E E ? .id I7: E ? E * E E ? .E + E E ? .E * E E ? .id I8: E ? E + E E ? E.+ E E ? E. * E I9: E ? E * E. E ? E .+ E E ? E .* E 5 解:

I1 S I0 id I2 = I3 id E I5 id I7 id + E I9 + E + *

I4

I6

I8

I7

(2)由于 I4、 I8、 I9 均有移进—归约冲突, 故该文法不是 LR(0)文法。

(1)句子 11.01 的带注释分析树:

第 83 页共 6 页

S L.val=2*L.val+B.val=3 L.num=L.num +1=2 L.val=B.val=1 L.num=1 L

print(3+1*2-2) L.val=2*L.val+B.val=1 L.num=L.num +1=2

L B.val=1

. L.val=B.val=0 L L.num=1

L

B

B

B.val=1

B.val=1

B

1

B.val=0

B

1

1

0

(2)处理该句子的结果(Print 输出结果)为 3.25 6 解: (1)语言 L 的正规表达式为: (1|2|??|9)(0|1|??|9)*(0|5)|5 (2)识别语言 L 的状态转移图为:

四、综合题
1. 已知文法 G(E) E →T|E+T T→F|T *F F →(E)|i (1)给出句型(T *F+i)的最右推导; (2)给出句型(T *F+i)的短语、简单短语、句柄、素短语、最左素短语。 2. 构造正规式 1(0|1)*101 相应的 DFA 。 所以,可得 DFA 为:

3. 文法: S->MH|a H ->LSo| ε K ->dML| ε L ->eHf M->K|bLM 判断 G 是否为 LL(1) 文法,如果是,构造 LL(1) 分析表。 4. 对下面的文法 G : E ->TE' E'->+E| ε

第 84 页共 6 页

T ->FT' T' ->T| ε F-> PF' F'-> *F'| ε P->(E)|a|b|^ (1)计算这个文法的每个非终结符的 FIRST 集和 FOLLOW 集。 (4 分) (2) 证明这个方法是 LL(1) 的。(4 分) (3) 构造它的预测分析表。(2 分)

5.已知文法 G[S] 为: S->a|^|(T) T-> T,S|S (1) 计算 G[S] 的 FIRSTVT 和 LASTVT 。 (2) 构造 G[S] 的算符优先关系表并说明 G[S] 是否未算符优先文法。 (3) 给出输入串 (a,a)# 的算符优先分析过程。

6.已知文法为:
S->a|^|(T) T->T,S|S 构造它的 LR(0)分析表。

7.已知文法为:
A ->aAd|aAb| ε 判断该文法是否是 SLR(1) 文法,若是构造相应分析表,并对输入串 ab# 给出分析过程。 答案: 1解: (1) 最右推导:E ->T->F->(E)->(E + T)->(E + F)->(E + i)->(T+i)->(T*F+i) (2) 短语:(T*F+i) ,T*F+i ,T*F,i 简单短语:T*F,i 句柄:T*F 素短语:T*F,i 最左素短语:T*F 2解:先构造 NFA :

确定化:

重新命名,令 AB 为 B、AC 为 C、ABY 为 D 得:

第 85 页共 6 页

4 解: (1)计算这个文法的每个非终结符的 FIRST 集和 FOLLOW 集。 FIRST 集合有: FIRST(E)=FIRST(T)=FIRST(F)=FIRST(P)={(,a,b,^}; FIRST(E')={+,ε } FIRST(T)=FIRST(F)=FIRST(P)={(,a,b,^}; FIRST(T')=FIRST(T)U{ε }={(,a,b,^, ε }; FIRST(F)=FIRST(P)={(,a,b,^}; FIRST(F')=FIRST(P)={*, ε }; FIRST(P)={(,a,b,^}; FOLLOW 集合有: FOLLOW(E)={),#}; FOLLOW(E')=FOLLOW(E)={),#}; FOLLOW(T)=FIRST(E')UFOLLOW(E)={+,),#};//不包含 ε FOLLOW(T')=FOLLOW(T)=FIRST(E')UFOLLOW(E)={+,),#}; FOLLOW(F)=FIRST(T')UFOLLOW(T)={(,a,b,^,+,),#};//不包含 ε FOLLOW(F')=FOLLOW(F)=FIRST(T')UFOLLOW(T)={(,a,b,^,+,),#}; FOLLOW(P)=FIRST(F')UFOLLOW(F)={*,(,a,b,^,+,),#};//不包含 ε (2)证明这个方法是 LL(1)的。 各产生式的 SELECT 集合有: SELECT(E->TE')=FIRST(T)={(,a,b,^}; SELECT(E'->+E)={+}; SELECT(E'->ε )=FOLLOW(E/)={),#} SELECT(T->FT')=FIRST(F)={(,a,b,^}; SELECT(T'->T)=FIRST(T)={(,a,b,^}; SELECT(T'->ε )=FOLLOW(T/)={+,),#}; SELECT(F->PF')=FIRST(P)={(,a,b,^}; SELECT(F'->*F')={*}; SELECT(F'->ε )=FOLLOW(F')={(,a,b,^,+,),#}; SELECT(P->(E))={(} SELECT(P->a)={a} SELECT(P->b)={b} SELECT(P->^)={^} 可见,相同左部产生式的 SELECT 集的交集均为空,所以文法 G[E]是 LL(1)文法。 (3)构造它的预测分析表。 文 法 G[E]的预测分析表如下:

第 86 页共 6 页

5解:(1)各符号的 FIRSTVT 和 LASTVT:

(2)算符优先关系表:

(3)句子(a,a)#分析过程如下:

6 解:加入非终结符 S' ,方法的增广文法为: S'->S S->a S->^ S->(T) T ->T,S T ->S 下面构造它的 LR(0)项目集规范族为:

第 87 页共 6 页

从上表可看出,不存在移进- 归约冲突以及归约归约冲突, 该文法是 LR(0)文法。 从而有下 面的 LR(0)分析表:

7解:增加一个非终结符 S/后,产生原文法的增广文法有: S'->A A ->aAd|aAb|ε 下面构造 它的 LR(0)项目集规范族为:

从上表可看出, 状态 I0 和 I2 存在移进- 归约冲突,该文法不是 LR(0)文法。对于 I0 来说有:

FOLLOW(A)∩{a}={b,d,#}∩{a}=Φ ,所以在 I0 状态下面临输入符号为 a 时移进,为 b,d,# 时 归约,为其他时报错。对于 I2 来说有也有与 I0 完全相同的结论。这就是说,以上的移进 第 88 页共 6 页

归约冲突是可以解决的,因此该文法是 SLR(1)文法。 其 SLR(1)分析表为:

对输入串 ab#给出分析过程为: 编译原理Dd卷

7-1

设有如下的三地址码(四元式)序列: read N I:=N J:=2 L1 : L2 : if I≤J goto L3

I:=I-J if if I>J goto L2 I=0 goto L4

J:=J+1 I:=N goto L1 L3 : Print ′YES′ halt L4 : Print ′NO′ halt 试将它划分为基本块,并作控制流程图。

7-2

考虑如下的基本块: D:=B*C
第 89 页共 6 页

E:=A+B B:= B*C A:=E+D (1) 构造相应的 DAG; (2) 对于所得的 DAG,重建基本块,以得到更有效的四元式序列。

7-3 (1)

对于如下的两个基本块: A:=B*C D:=B/C E:=A+D F:=2*E G:=B*C H:=G*G F:=H*G L:=F M:=L

(2)

B:=3 D:=A+C E:=A*C F:=E+D G:=B*F H:=A+C I:=A*C J:=H+I K:=B*5 L:=K+J M:=L

分别构造相应的 DAG,并根据所得的 DAG,重建经优化后的四元式序列。在进行优化时, 须分别考虑如下两种情况: (ⅰ)变量 G、L、M 在基本块出口之后被引用;
第 90 页共 6 页

(ⅱ)仅变量 L 在基本块出口之后被引用。

7-4

对于题图 7-4 所示的控制流程图:

(1) 分别求出它们各个结点的必经结点集; (2) 分别求出它们的各个回边; (3) 找出各流程图的全部循环。

2 3 4 4 5 6

1 1 2 3 5 6 3 2

4

7 7 8 (a) 8 (b) 题图7-4

6

5

7 (c)

7-5

对于如下的程序: I:=1 read J,K

L:

A:=K*I B:=J*I C:=A*B write C I:=I+1

第 91 页共 6 页

if halt

A<100 goto L

试对其中的循环进行可能的优化。 习题答案

7-1

解:划分情况及控制流程如答案图 7-1 所示:

B1 B2 L1 B3 L2

read N I:=N J:=2 if I≤J goto L3 I:=I-J if I>J goto L2 if I=0 goto L4 J:=J+1 I:=N goto L1 L3 Print ′YES′ halt

B4 B5 B6

B7
答案图 7-1

L4 Print ′NO′ halt
将四元式序列划分为基本块

7-2

解:

(1) 相应的 DAG 如答案图 7-2 所示。

第 92 页共 6 页

n3 D * n1 B0 (a) n2 C0 n4 A0

n5 E + n1 B0 (b)

n3 D * n2 C0

n6 A + n5 E + n4 A0 n1 B0 (c)
答案图 7-2 DAG

n3 D , B * n2 C0 n4 A0

n5 E + n1 B0 (d)

n3 D , B * n2 C0

(2) 优化后的代码为: D:=B*C E:=A+B B:=D A:=E+D

7-3

解:

(1) 相应的 DAG 如答案图 7-3-(1)所示。

第 93 页共 6 页

n9 F, L, M * n8 * H + n3 A, G * n1 B0 n4 D / n2 C0 答案图7-3-(1) n5 E

n7 F0 *

n6 2

若只有 G、L、M 在出口之后被引用,则优化后的代码为: G:=B*C H:=G*G L:=H*G M:=L 若只有 L 在出口之后被引用,则代码为: G:=B*C H:=G*G L:=H*G

(2) 相应的 DAG 如答案图 7-3-(2)所示。

第 94 页共 6 页

n7 G *

n9 L, M +

n6 F, J +

n4 D, H + n1 B 3 n6 5 n8 K 15 n2 A0 答案图7-3-(2)

n5 E, I * n3 C0

若只有 G、L、M 被引用,则代码为: D:=A+C E:=A*C F:=E+D G:=3*F L:=15+F M:=L 若只有 L 被引用,则代码为: D:=A+C E:=A*C F:=E+D L:=+F15

7-4 解: (a) 必经结点集: D2={2}

第 95 页共 6 页

D3 ={2,3}, D5 ={2,4,5} D7 ={2,4,7} 回边及相应的循环: 7→4:{4,5,6,7}

D4 ={2,4} D6 ={2,4,6} D8={2,4,7,8}

8→2:{2,3,4,5,6,7,8} (b) 必经结点集: D1 ={1} D3 ={1,2,3} D5 ={1,2,3,5} D7 ={1,2,7} 回边及相应循环: 7→2:{2,3,4,5,6,7} (c) 必经结点集: D1 ={1} D3 ={1,2,3} D5 =1,2,5} D7 ={1,2,7} 回边及相应循环: 5→2:{2,3,4,5} 6→6: {6} 注意:5→4 不是回边。因为 4 不是 5 的控制结点。 D2 ={1,2}, D4 ={1,2,4}, D6 ={1,2,3,6}, D2 ={1,2} D4 ={1,2,3,4} D6 ={1,2,3,6} D8 ={1,2,7,8}

7-5

解:

(1) 划分基本块后的流程图如答案图 7-5-(1)所示。

第 96 页共 6 页

(1) (2)

I:=1 read J,K

B1

(3) (4) (5) (6) (7) (8)

A:=K*I B:=J*I C:=A*B write C I:=I+1 if I<100 goto L

B2

(9)

halt

B3

答案图7-5-(1) 划分基本块后的流程图

(2) 削弱运算强度后的流程图如答案图 7-5-(2)所示。

(1) (2)

I:=1 read J,K

B1

(3)′T1:=K*I (4)′T2:=J*I (3) (4) (5) (6) (7) A:=T1 B:=T2 C:=A*B write C I:=I+1

B2 ′

B2

(3)〞T1:=T1+K (4)〞T2:=T2+J (8) (9) if I<100 goto B2 halt B3

第 97 页共 6 页

答案图 7-5-(2) 削弱运算强度后的流程图

(3) 消除归纳变量后的流程图如答案图 7-5-(3)所示。

(1) (2)

I:=1 read J,K

B1

(3)′T1:=K*I (4)′T2:=J*I (7)′T3:=K*100

B2 ′

B2 (3) (4) (5) (6) A:=T1 B:=T2 C:=A*B write C

(3)〞T1:=T1+K (4)〞T2:=T2+J (8) (9) if A<T3 goto B2 halt B3

答案图 7-5-(3) 消除归纳变量后的流程图

编译原理 Ee 卷

综合题:4-4

对于如下的文法 G[S]:

S→Sb|Ab|b A→Aa|a (1) 构造一个与 G 等价的 LL(1)文法 G′[S]; (2) 对于 G′[S],构造相应的 LL(1)分析表; (3) 利用 LL(1)分析法判断符号串 aabb 是否是文法 G[S]的合法句子。

综合题:4-5 设已给文法 S→SaB|bB A→S|a B→Ac

第 98 页共 6 页

(1) 构造一个与 G 等价的 LL(1)文法 G′[S]; (2) 对于 G′[S],构造相应的 LL(1)分析表; (3) 利用 LL(1)分析法判断符号串 bacabc 是否是文法 G[S]的合法句子。

第 4 章 习题答案

4-4

解:

(1) 文法中含有直接左递归的非终结符号 S 和 A,则消除直接递归性后,我们便得 到了与原文法等价且无任何左递归性的文法 G′[S]:: S→AbS′|bS′ S′→bS′|ε A→aA′ A′→aA′|ε 文法 G′[S]的各候选式的 FIRST 集和各非终结符号的 FOLLOW 集如答案表 4-4-(1)所示:

答案表 4-4-(1) 产 生 式 S→AbS′ S→bS′ S′→bS′ S′→ε A→aA′ A′→aA′ A′→ε

文法 G′[S]的各个 FIRST 集和 FOLLOW 集 FIRST {a} {b} {b} {ε } {a} {a} {ε } {b} {#} {b} FOLLOW {#}

下面来验证文法 G′[S]是否是 LL(1)文法。对于文法 G′[S],因为有: 对于产生式 S→AbS′|bS′,有 FIRST(AbS′)∩FIRST(bS′)={a}∩{b}=?;

第 99 页共 6 页

对于产生式 S′→bS′|ε ,有 FIRST(bS′)∩FOLLOW(S′)={b}∩{#}=?; 对于产生式 A′→aA′|ε ,有 FIRST(aA′)∩FOLLOW(A′)={a}∩{b}=?; 所以文法 G′[S]即为所求的与 G 等价的 LL(1)文法。

(2) 文法 G′[S]的 LL(1)分析表如答案表 4-4-(2)所示:

答案表 4-4-(2) a S S′ A A′ A→aA′ A′→aA′ S→AbS′

文法 G′[S]的 LL(1)分析表 b S→bS′ S′→bS′ S′→ε #

A′→ε

(3) 对符号串 aabb 进行 LL(1)分析的过程如答案表 4-4-(3)所示。

答案表 4-4-(3) 步骤 1 2 3 4 5 6 7 8 9 10 11 #S #S′bA #S′bA′a #S′bA′ #S′bA′a #S′bA′ #S′b #S′ #S′b #S′ # 分析栈

对 aabb 进行 LL(1)分析的过程 余留输入串 aabb# aabb# aabb# abb# abb# bb# bb# b# b# # # S′→ε 分析成功 S′→bS′ A′→ε A′→aA′ 所用产生式 S→AbS′ A→aA′

第 100 页共 6 页

因为分析成功,所以符号串 aabb 是文法 G[S]的合法句子。

4-5

解:

(1) 文法中含有直接左递归的非终结符号 S,则消除直接递归性后,我们便得到了 与原文法等价且无任何左递归性的文法 G′[S]:: S→bBS′ S′→aBS′|ε A→S|a B→Ac 文法 G′[S]的各候选式的 FIRST 集和各非终结符号的 FOLLOW 集如答案表 4-5-(1)所示:

答案表 4-5-(1) 产 生 式 S→bBS′ S′→aBS′ S′→ε A→S A→a B→Ac

文法 G′[S]的各个 FIRST 集和 FOLLOW 集 FIRST {b} {a} {ε } {b} {a} {a,b} { #,a,c} {#,c} {c} FOLLOW {#,c}

下面来验证文法 G′[S]是否是 LL(1)文法。对于文法 G′[S],因为有: 对于产生式 S′→aBS′|ε ,有 FIRST(aBS′)∩FOLLOW(S′)={a}∩{#,c}=?; 对于产生式 A→S|a,有 FIRST(S)∩FIRST(a)={b}∩{a}=?; 所以文法 G′[S]即为所求的与 G 等价的 LL(1)文法。

(2) 文法 G′[S]的 LL(1)分析表如答案表 4-5-(2)所示:

答案表 4-5-(2) a

文法 G′[S]的 LL(1)分析表 b c #

第 101 页共 6 页

S S′ A B S′→aBS′ A→a B→Ac

S→bBS′ S′→ε A→S B→Ac S′→ε

(3) 对符号串 bacabc 进行 LL(1)分析的过程如答案表 4-5-(3)所示。

答案表 4-5-(3) 步骤 1 2 3 4 5 6 7 8 9 10 11 12 13 #S #S′Bb #S′B #S′cA #S′ca #S′c #S′ #S′Ba #S′B #S′cA #S′cS 分析栈

对 bacabc 进行 LL(1)分析的过程 余留输入串 bacabc# bacabc# acabc# acabc# acabc# cabc# abc# abc# bc# bc# bc# bc# c# 分析失败 B→Ac A→S S→bBS′ S′→aBS′ B→Ac A→a 所用产生式 S→bBS′

#S′cS′Bb #S′cS′B

因为 LL(1)分析表中 B 行 c 列元素为空,即为“出错”,故分析失败,所以符号串 bacabc 不是文法 G[S]的合法句子。
编译原理 Ff 卷 五、计算题: 1.设文法 G(S): S→^ | a | (T) T→T,S | S ⑴ 消除左递归;
第 102 页共 6 页

⑵ 构造相应的 FIRST 和 FOLLOW 集合; ⑶ 构造预测分析表 2.语句 if E then S (1) 改写文法,使之适合语法制导翻译; (2) 写出改写后产生式的语义动作。 3.设文法 G(S) : S→(T) | a T→T+S | S (1)计算 FIRSTVT 和 LASTVT; (2)构造优先关系表。 4.设某语言的 for 语句的形式为 (1) (2) for i:=E to E do S 其语义解释为 (1) i:=E (2) LIMIT:=E again: if i<=LIMIT then Begin S; i:=i+1 goto again End; (1)写出适合语法制导翻译的产生式; (2)写出每个产生式对应的语义动作。 5.把语句 while a<10 do if c>0 then a:=a+1 else a:=a*3-1; 翻译成四元式序列。 6.设有基本块 D:=A-C E:=A*C F:=D*E S:=2 T:=A-C Q:=A*C G:=2*S J:=T*Q K:=G*5 L:=K+J M:=L 假设基本块出口时只有 M 还被引用,请写出优化后的四元序列。 7.已知文法 G(S) S→a | ^ | (T) T→T,S | S (1) 给出句子(a,(a,a))的最左推导; (2) 给出句型((T,S),a)的短语, 直接短语,句柄。 8.对于 C 语言 do S while E 语句 (1)改写文法,使之适合语法制导翻译; (2)写出改写后产生式的语义动作。
第 103 页共 6 页

9.已知文法 G(S) S→aAcBe A→Ab| b B→d (1)给出句子 abbcde 的最左推导及画出语法树; (2)给出句型 aAbcde 的短语、素短语。 10.设文法 G(S): S→(T) | aS | a T→T,S | S ⑴消除左递归和提公共左因子; ⑵构造相应的 FIRST 和 FOLLOW 集合; ⑶构造预测分析表。 11.把语句 if X>0 ∨ Y<0 then while X>0 do X:=A*3 else Y:=B+3; 翻译成四元式序列。 12.已知文法 G(S) E→E+T | T T→T*F| F F→(E)| i (1) 给出句型 (i+i)*i+i 的最左推导及画出语法树; (2) 给出句型 (E+T)*i+F 的短语,素短语和最左素短语。 13.设文法 G(S) : S→T | S∨T T→U |T∧U U→i |-U (1)计算 FIRSTVT 和 LASTVT; (2)构造优先关系表。

答案:1.
(1)消除左递,文法变为 G’[S]: S→^ | a | (T)' T→ST’ | S T’→,ST’ |ε 此文法无左公共左因子。 (2)构造相应的 FIRST 和 FOLLOW 集合: FIRST(S)={a, ^, (}, FOLLOW(S)={#, ,, )} FIRST(T)={a, ^, (} ,FOLLOW(T)={}} FIRST(T’)={,, ε } ,FOLLOW(F)={)} (3)构造预测分析表: a ^ ( S T T’ S→a T→ST’ S→^ T→ST’ S→(T)' T→ST’ T’→ε T’→,ST’

)

,

#

2. (1) C→if E then (1) S→CS
第 104 页共 6 页

(2) C→if E then {BACK(E.TC, NXQ); C.chain:=E.FC} (1) (1) S→CS {S.chain:=MERG(C.Chain, S . Chain)} 3. (1) FIRSTVT(S)={a, ( } FIRSTVT(T)={+, aa, (} LASTVT(S)={a, ) } LASTVT(T)={+, a, )} (2) a + ( ) a .> .> + <. .> <. .> ( <. <. <. =. ) .> .> >. (1) (2) 4. (1) F→for i:=E to E do (1) S→FS (1) (2) (2) F→for i:=E to E do (1) {GEN(:=, E .place, _, entry(i)); F.place:=entry(i); LIMIT:=Newtemp; (2) GEN(:=, E .place, _, LIMIT); Q:=NXQ; F.QUAD:=q; GEN(j≤, entry(i), LIMIT, q+2) F.chain:=NXQ; GEN(j, _, _, 0)} (1) S→FS (1) {BACKPATCH(S .chain, NXQ); GEN(+, F.place, 1, F.place); GEN(j, _, _, F.QUAD); S.chain:=F.chain } 5. (1) (j<, a, ‘10’, (3)) (2) (j, _, _, (12)) (3) (j>, c, ‘0’, (5)) (4) (j, _, _, (8)) (5) (+, a, ‘1’, T1)) (6) (:=, T1, _, a) (7) (j, _, _, (1)) (8) (*, a, ‘13’, T2) (9) (-, T2, ‘1’, T3) (10) (:=, T3, _, a) (11) (j, _, _, (1)) 6.优化后的四元序列 D:=A-C E:=A*C F:=D*E M:=F+20 7. 最左推导 S=(T)=>(T,S)=>(S,S)=>(a,S)=>(a,(T))=>(a,(T,S))=>(a,(S,S))=>(a,(a,S))=>(a,(a,
第 105 页共 6 页

a)) 短语 ((T,S),a) (T,S),a (T,S) T,S a 直接短语 T,S a 句柄 T,S 8.(1) S→do M1 S1 while M2 E M→ε (2) M→ε S→do M1 S1 while M2 E

{M.quad=nestquad;} {backpatch(s1.nextlist, M2.quad); backpatch(E.truelist, M1.quad); S.nextlist=E.falelist; } 9.(1) S=>aAcBe=>AAbcBe=>abbcBe=>abbcde (2) 短语: aAbcde, Ab, d 素短语: Ab, d 10.(1) S →(L) | aS’ S’→S |ε L→SL’ L’→,SL’ |ε (2) FIRST(S)={a, (} FIRST(S’)={a, (, ε } FIRST(L)={a, (} FIRST(L’)={,, ε } FOLLOW(S)={,, ), #} FOLLOW(S’)={,, ), #} FOLLOW(L)={ )} FOLLOW(L’)={ )} (3) ( S →(L) S’→S L→SL’ ) S’→ε L’→ε a S → aS’ S’→S L→SL’ , S’→ε L’→,SL’ # S’→ε

S S’ L L’

11.(1) (j>, X, 0, (5)) (2) (j, _, _, (3)) (3) (j<, Y, 0, (5)) (4) (j, _, _, (11)) (5) (j>0, X, 0, (7)) (6) (j, _, _, (7)) (7) (*, A, 3, T1) (8) (:=, T1, _, N) (9) (j, _, _, (5))
第 106 页共 6 页

(10) (j, _, _, (13)) (11) (+, B, 3, T2) (12) (:=, T2, _, Y) 12.(1) E=>E+T=>T+T=>T*F+T=>F*F+T=>(E)*F+T=>(E+T)*F+T=>(T+T)*F+T =>(F+T)*F+T=>(i+T)*F+T=>(i+F)*F+T=>(i+i)*F+T=>(i+i)*i+T =>(i+i)*i+F=>(i+i)*i+i (2) 短语 i, F, E+T, (E+T), (E+T)*i, (E+T)*i+F 素短语 i, E+T 最左素短语 E+T 13.(1) FIRSTVT(S)={∨, ∧, i, - } FIRSTVT(T)={∧, i, -} FIRSTVT(U)={i, -} LASTVT(S)={∨, ∧, i, - } LASTVT(T)={∧, i, -} LASTVT(U)={i, -} (2) i S ∨ ∧ <. <. <. ∨ .> .> .> .> ∧ .> <. .> .> <. <. <.

第 107 页共 6 页


相关文章:
编译原理题库——综合题
(直接改在试题上) LEX程序如下: %{ # include <stdio.h> int num_int =...(3 分) 编译原理 P 卷一、综合题(30 分) 1、 构造下面文法的 LL(1)...
编译原理试题及答案——加强版
编译原理试题及答案 <高级版> 一、对于文法 G[S] : S → 1A | 0B | ε A → 0S | 1AA B → 1S | 0BB ⑴ (3 分 ) 请写出三个关于 G[S]...
编译原理期末试题(8套含答案+大题集)
编译原理期末试题(8套含答案+大题集)_其它_高等教育_教育专区。编译原理的一些参考题 《编译原理》期末试题(一)一、是非题(请在括号内,正确的划√,错误的划×...
编译原理试题库
编译原理试题库_工学_高等教育_教育专区。一.名词解释: 1)前缀 答:前缀——...5)扫描遍 答:扫描遍——指编译程序对源程序或中间代码程序从头到尾扫描一次。...
编译原理试题汇总
编译原理试题汇总_工学_高等教育_教育专区。编译原理考试题及答案汇总 编译原理考试题及答案汇总 编译原理考试题及答案汇总一、选择 1.将编译程序分成若干个“遍”...
编译原理题库
关键词:吴海波编译原理题库湖南科技大学田戈 1/2 相关文档推荐 ...解:加入新开始符号 S'和产生式 S'→S,设 num 为综合属性,代表值属性,则...
《编译原理》考试试题及答案(汇总)
编译原理》考试试题及答案(汇总) 一、是非题(请在括号内,正确的划√,错误的划× )(每个 2 分,共 20 分) 1.编译程序是对高级语言程序的解释执行。(×)...
编译原理试题
编译原理试题_工学_高等教育_教育专区。编译原理题库 一、选择题: 1.编译原理是对(C) 。A、机器语言的执行 B、汇编语言的翻译 C、高级语言的翻译 D、高级...
编译原理考试复习题
编译原理考试复习题_其它考试_资格考试/认证_教育专区。河南城建学院 2010 学年...五、综合题(第 1 小题 10 分,第 2、3 小题各 15 分) 1、对下图的流...
华东交通大学编译原理试题库_试卷一
华东交通大学编译原理试题库_试卷一_教育学_高等教育_教育专区。一、选择题(每个选择题 2 分,共 20 分) 1 .文法 G 产生的 ⑴ 的全体是该文法描述的语言。...
更多相关标签:
编译原理题库 | 微机原理8255综合题 | 电路原理试题库与题解 | 管理学原理题库 | 计算机组成原理题库 | 自动控制原理题库 | 机械原理题库 | 通信原理题库 |