编译原理期末试题及答案 下载本文

内容发布更新时间 : 2024/3/29 13:12:23星期一 下面是文章的全部内容请认真阅读。

1、 试为表达式 w+(a+b)*(c+d/(e-10)+8) 写出相应的逆波兰表示。 2、写出表达式a+b*(c-d)/e的逆波兰式和三元序列。

3、写出表达式a:=(b+c)*e+(b+c)/f的逆波兰式和三元序列。 4、已知文法G(S)及相应翻译方案 S→aAb {print “1”} S→a {print “2”} A→AS {print “3”} A→c {print “4”} 输入acab, 输出是什么? 5、 已知文法G(S)

S→bAa A→(B | a B→Aa)

写出句子b(aa)b的规范归约过程。 6、已知文法G[S]

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

消除文法左递归。 1、设文法G(S):

S→^ | a | (T) T→T,S | S

⑴ 消除左递归;

⑵ 构造相应的FIRST和FOLLOW集合; ⑶ 构造预测分析表 2.语句 if E then S (1) 改写文法,使之适合语法制导翻译; (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)写出每个产生式对应的语义动作。 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页共6页

(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集合; ⑶构造预测分析表。 12.已知文法G(S) E→E+T | T T→T*F| F F→(E)| i (1) 给出句型 (i+i)*i+i的最左推导及画出语法树; (2) 给出句型 (E+T)*i+F 的短语,素短语和最左素短语。

答案: (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)构造预测分析表: S T T’ a 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)}

(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));

第2页共6页

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 }

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

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 S’ L L’

12.(1)

( S →(L) S’→S L→SL’ ) S’→ε L’→ε a S → aS’ S’→S L→SL’ , S’→ε L’→,SL’ # S’→ε E=>E+T=>T+T=>T*F+T=>F*F+T=>(E)*F+T=>(E+T)*F+T=>(T+T)*F+T

第3页共6页

=>(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

《编译原理》期末试题(二)

对于函数f2,由于局部变量x的作用域只是函数体的一部分,不会出现上述问题,因而编译器不报错。

6、正规式b?a(bb?a) ?b?体现的特点是,每个a的左边都有若干b,除非a是第一个字母。该正规式定义的语言是:至少含一个a,但不含子串aa的所有a和b的串集。最简DFA如下:

b start

0

a b b

a 2 1

7、 消除左递归后的文法: B ? 1 B? B? ? 0 B? | 1 B? | ? 相应的翻译方案如下: B ? 1 {B?.i := 1 }B?{B.val := B?.val} B? ? 0 {B?1.i := B?.i ? 2 } B?1 {B?.val := B?1.val} | 1 {B?1.i := B?.i ? 2 +1} B?1 {B?.val := B?1.val} | ? {B?.val := B?.i}

《编译原理》期末试题(三) 2、写出表达式a=b*c+b*d对应的逆波兰式、四元式序列和三元式序列。 答:逆波兰式: abc*bd*+:= 3、对于文法G(S): S ?bMbM ?(L|aL ?Ma)

S 答:1) S?bMb?b(Lb?b(Ma)b 2) 短语: Ma), (Ma), b(Ma)b 直接短语: Ma) 句柄: Ma) b ( M M b T L a ) 三、

设有字母表{a,b}上的正规式R=(ab|a)*。 解:(1)

第4页共6页

2 - 0 ε a 1 b ε + 3 a

(2)将(1)所得的非确定有限自动机确定化 ε a b -0 1 2 +3 1 1 3 12 2 + -+ a 0 b a 1 + a (3)对(2)得到的DFA化简,合并状态0和2 为状态2: 2 -+ b a 1 + a (4)令状态1和2分别对应非终结符B和A G: A→aB|a|ε; B→aB|bA|a|b|ε;可化简为:G: A→aB|ε;B→aB|bA|ε 四、

设将文法G改写成等价的LL(1)文法,并构造预测分析表。 G:S→S*aT|aT|*aT; T→+aT|+a 解:消除左递归后的文法G’: S→aTS’|*aTS’ S’→*aTS’|ε T→+aT|+a 提取左公因子得文法G’’: S→aTS’|*aTS’ S’→*aTS’|ε T→+aT’

T’→T|ε Select(S→aTS’)={a} Select(S→*aTS’)={*}

Select(S→aTS’)∩Select(S→*aTS’)=Ф Select(S’→*aTS’)={*}

Select(S’→ε)=Follow(s’)={#}

第5页共6页