(完整)2014上学期编译原理试题及答案中南大学,推荐文档

中南大学考试试卷

2013 -- 2014 学年 二 学期 时间100分钟

编译原理 课程64 学时 4 学分 考试形式：开卷

专业年级：计算机，信安，物联网 11 总分100分，占总评成绩70% 注：此页不作答题纸，请将答案写在答题纸上

1. 已知文法G[S]

S→(L)| a

L→L,S| S

给出句子((a,a),a)的最右推导；(本题共10 分) 2. 证明文法G[S]

S→aS | aSbS |ε 是二义性的。(本题共10分)

3. 写出正规表达式b(ab)*等价的文法。(本题共10分)

4. 写一个文法使其语言为L={a2m-1, ba2n| m, n ≥1} (本题共10分)

5. 以下两题目任选择一题目，如果两题都做以第一题计分。(本题共10分) (1) 将正规表达式1(0|1)*101转化为NFA，DFA并最小化。 (2) 设有基本块：

T1=3 T2=D+E T3=G – B T4=T1 / 2 X=T2*T4 Y=X

T5=D + E T6=T3 / T5 Y=T6

画出该基本块的DAG图，根据DAG图写出其等价的基本块。 6. 已知文法G[S]: S→(L)| a L→L,S| S

试为每个产生式配语义动作，输出配对括号个数。例如对于句子(a,(a,a))，输出2。(本题共10分) 7. 已知文法G[S]

S→SaA

1

S→bB A→aB A→c B→Bb B→d

(1) 消除左递归；(5 分)

(2) 构造相应的FIRST和FOLLOW集合；(5 分) (3) 构造LL(1)分析表。 (5 分) (本题共15分) 8. 把语句

while ad do

if x>y then z:=z+1

else z:=z*x;

翻译成三地址代码，假设三地址代码语句标号从100开始。(本题共10分) 9. 以下两题目任选择一题目，如果两题都做以第一题计分。(本题共15分) (1) 已知文法G[S]

(0)S’→S (1)S→V=E (2)S→E (3) E→V (4)V→x (5)V→*E

构造LR(1) 分析表。 (2)令文法G[S]为：

S→S ; B| B B→B * T | T T→a|(S)

(a) 请写出文法G[S] 的 FIRSTVT 集和LASTVT集。 (b)构造优先关系表

(c)分析符号串 a;a*a 是否为文法的句子

2

《编译原理》试卷参考答案

1. 已知文法G[S]

S→(L)| a L→L,S| S

给出句子((a,a),a)的最右推导。(本题共10 分)

S=>(L)=(L,S)=>(L,a)=>(S,a)=>((L),a)=>((L,S),a)=>((L,a),a)=>((a,a),a) 2. 证明文法G[S]

S→aS | aSbS | ε 是二义性的。(本题共5分)

因为对于句子aab有两个不同的最左推导

S=>aS=>aaSbS=>aabS=>aab S=aSbS=>aaSbS=>aabS=>aab 因此，文法是二义性的。

3. 写出与正规表达式b(ab)*等价的文法。(本题共10分)

G[S] S→bA A→abA A→ε

4. 写一个文法使其语言为L={a2m-1, ba2n| m, n ≥1} (本题共10分)

G[S] S→A

S→bB A→aaA A→a B→aaB B→aa

5. (1) 将正规表达式1(0|1)*101转化为NFA，DFA并最小化。(本题共10分)

状态 输入 0 1 X A A A B B C B

3

C D X:初态

A C D B D :终态(1) 已知文法G[S]:

(2) 设有基本块：

T1=3 T2=D+E T3=G – B T4=T1 / 2 X=T2*T4 Y=X

T5=D + E T6=T3 / T5 Y=T6

画出该基本块的DAG图,根据DAG图写出其等价的基本块。

T6,Y X,Y/ *

T3T2,T5T4

-+1.5 T1

GB3DE2

等价的基本块

T1=3 T2=D+E T3=G – B T4=1.5 X=T2*T4 T6=T3 / T2 Y=T6

6. 已知文法G[S]:

S’→S S→(L)| a L→L,S| S

试为每个产生式配语义动作，输出配对括号个数。例如对于句子(a,(a,a))，输出2。

4