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

编译原理题库——综合题


编译原理 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 页


赞助商链接
相关文章:
编译原理期末复习题(含答案2011-5)
18、文法符号的属性有( 继承属性 )和( 综合属性 文法符号的属性来计算的。 ...35页 5下载券 编译原理期末试题(8套含... 53页 免费 喜欢此文档的还喜欢...
编译原理练习题及答案
第一章练习题(绪论) 第一章练习题(绪论)一、选择题 1.编译程序是一种常用...习题见本章课件) 2012-5-3 第五章练习题(自上而下语法分析) 第五章练习题...
编译原理课后习题答案
编译原理课后习题答案_理学_高等教育_教育专区。第一章 1.解答:程序设计语言:程序设计语言是遵守一定规范的、描述“计算”(Computing)过程的形式语言。一般可以划分...
编译原理习题及答案(整理后)
编译原理习题及答案(整理后)_工学_高等教育_教育专区。第一章 1、将编译程序...四、综合题 1、对于文法 G[S]: S→AS|b A→SA|a (1)列出所有 LR(0)...
编译原理题库——选择题
编译原理题库——选择题_计算机软件及应用_IT/计算机_专业资料。编译原理 a 二...a.传递 b.继承 c.抽象 d.综合 答案:1 c d 2b 3b 4d 5d 6c 7 3、在...
编译原理复习题
文法 G[S]及其语法制导翻译定义如下: 产生式 语义动作 S’ → S print(S.num) S → (L) S.num = L.num +1 4 《编译原理》复习题 S→a S.num ...
编译原理复习题
68.编译原理各阶段工作都涉及 B. 表格 A. 词法分析 管理 B. 表格管理 C....执业医师实践技能考试模拟试题 80份文档 家装材料选购攻略 高端水龙头贵在哪儿 ...
各章练习题(编译原理)
编译原理第二章练习题(注... 2页 免费 编译原理 第3章习题解答 8页 1下载券 编译原理第6章 习题与答... 3页 1下载券 编译原理教程课后习题答... 2页...
编译原理复习题及参考答案
编译原理复习题及参考答案_从业资格考试_资格考试/认证_教育专区。中南大学网络教育...软件工程复习题及参考答... 数据结构复习题及参考答... 数据库原理与技术复习...
编译原理习题
6. 分)代码优化中的强度削弱是什么意思,举一例加以说明 (5 2001 年编译原理试题 1. (10 分)处于/* 和 */之间的串构成注解,注解中间没有*/。画出接受...
更多相关标签: