中南大学软件工程2005年《编译原理》试卷及参考答案

中南大学软件工程2005年《编译原理》试卷及参考答案

《编译原理》软件工程2005级期终考卷

学号： 姓名：

说明:1.本考卷中大写字母∈VN ，其他符号∈VT； 2、试卷中一、二两题请作在考卷上

一、 概念题（15分）

1、编译过程一般分为几个阶段？各阶段的输入输出分别为什么？

2、对下列状态转换图，写出状态0的处理过程：

其中：状态2的过程为proc2. 3、文法G为： S aAB A a

B | |

则判断G为LL（1）文法的条件是：

二、判断题（10分。注：每答对一题得+2分；答错一题得-2分；不答者得0分）

1、设∑为{a，b}，则a，ba，{∑}，Ø都是∑上的正规式。

（ ）

2、对于上下文无关文法G[S]，若 S αAB αβγ则A 一定是一条产生式规则，其中α,β,γ∈（VT∨VN）* （ ） 3、对于逆波兰后缀式，无论从哪头开始分析均可得到唯一正确的分解。（ ） 4、LR（0）分析法是一种规范归约法。 （ ） 5、算符优先分析法只能用来分析算符优先文法。 （ 三、（10分）设文法G3为：S AaBc

A Aa|a B b 求句型AaBc的最左素语。

四、（20分）设文法G[S]为

S aAcB 问：1、该文法是否为算符文法，为什么？ A Ab|b 2、构造算符优先关系表。

B d 3、该文法是否可改造为LL（1）文法，为什么？

）

中南大学软件工程2005年《编译原理》试卷及参考答案

五、（本题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; E.FC=NXQ+1;

GEN(J<,ENTRY(i

1

),ENTRY(i

2

),O);GEN(J, , ,0)}

1

(2)E AE {E.FC:=E.FC; E.FC:=MERGE(A.TC ,E.TC)} (3)A B∨ {BACKPATCH(B.FC ,NXQ); A.TC:=B.TC} (4)B i {B.TC:=NXQ; B.FC:=NXQ+1;

GEN(Jnz, ENTRY(i), ,0); GEN(J, , ,0)}

1 1

软件0501班编译原理考试答案及评分细则

Proc 0:

getchar();

CASE char OF

‘a’,’b’,…,’z’:

‘A’,’B’,…,’Z’: proc 1 else error END CASE

2、(5分)

3、(5分) 条件：

（1）文法G不含左递归；

（2）对于每个非终结符，First(α)、First(β)、First(γ)两两不相交；

中南大学软件工程2005年《编译原理》试卷及参考答案

（3）对于每个非终结符，不含能推出ε的产生式，故不考虑非终结符的First集和Follow集相交的情况。 二、（每小题2分）

1、×； 2、×； 3、√； 4、√； 5、√。 三、（10分） 方法一：

句型AaBc的语法树为：

c

故AaBc即为所求最左素短语。

方法二：

FIRSTVT(S)={a}, LASTVT(S)={c}, FIRSTVT(A)={a}, LASTVT(A)={a}, FIRSTVT(B)={b}, LASTVT(B)={b}。 则有：

对于#AaBc#，#<a，a=c，c>#，则最左素短语为AaBc。 四、（20分）

1、该文法是算符文法。因为其任一产生式的右部都不含相继（并列）的非终结符，即不含如下形式…QR…的产生式右部。 （4分）

2、FIRST(S)={a}, LAST(S)={c}, FIRST(A)={b}, LAST(A)={b},

FIRST(B)={d}, LAST(B)={d}。 （3分） 构造算符优先关系表如下：

（5分）

中南大学软件工程2005年《编译原理》试卷及参考答案

原因：

3、该文法可以改造为LL（1）文法。 （8分） ① 消除左递归：S→aAcB A→bA’ A’→bA’|ε

B→d； ② FIRST(A)={a}, FOLLOW(A)={c}, FIRST(A’)={b, ε}, FOLLOW(A’)={c}, FIRST(B)={d}, FOLLOW(B)={#}, FIRST(S)={a}, FOLLOW(S)={#},

对于每个非终结符的各个产生式的FIRST集两两不相交；

③ 对于A’，FIRST（A）∩FOLLOW（A）=Φ。

综上所述，原文法可以改造成LL（1）文法。 五、（20分）

原文法不是LL（1）文法，故不能直接使用LL（1）分析法进行分析。 步骤如下：

1、拓广文法：①E’→E ②E→eAf

③E→eBg ④A→aA

⑤A→a ⑥B→Bb

⑦B→a （2分） 2、项目集规范族：

中南大学软件工程2005年《编译原理》试卷及参考答案

1

E’→E.

0E’→.EE→.eAfE→.eBg

2e

E→e.AfA→.aAA→.aE→e.BgB→.BbB→.a

3

E→eA.f4a

A→a.AA→a.A→.aAA→.aB→B.b5

B

E→eB.gB→B.b

f

6

E→eAf.7

A→aA.8

A→a.AA→a.A→.aAA→.a9

E→eBg.10B→Bb.

A

A

a

a

g（6分）

由此项目集规范族可判断，原文法非LR（0）文法，故不能直接使用LR（0）分析法进行分析。因此，使用SLR（1）分析法分析原文法。

3、构造SLR（1）分析表如下： FOLLOW(A)={f}；FOLLOW(B)={b,g}；FOLLOW(E)={#}。

（6分）

4、分析输入串eaaaf如下：

中南大学软件工程2005年《编译原理》试卷及参考答案

六、（

25分）

1、步骤：

（6分）

（1）拓广文法：①E’→E ②E→i<i

③E→AE ④A→B∨

⑤B→i （2分） （2）项目集规范族：

E’→.E

E→.i(1)<i(2)E→.AE(1) A→.B∨B→.iB4

A→B.∨∨5

A→B∨.

i

1

E’→E.2

<B→i.

EiB

6

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

E→AE.(1) 24

(1)

(1)(2)

i

8

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

3

AE→A.E(1) E→.i(1)<i(2)E→.AE(1) A→.B∨B→.i

A

（6分）

（3）SLR（1）分析表如下：

FOLLOW(E)={#}；FOLLOW(A)={i}；FOLLOW(B)={ ∨}。

中南大学软件工程2005年《编译原理》试卷及参考答案

2、分析输入串a∨b<c如下：

（6分）

（6分）

整理：

真出口为3； 假出口为4。 （2分）

中南大学软件工程2005年《编译原理》试卷及参考答案

3、四元式：

1、（Jnz,a,_ …… 此处隐藏：1881字，全部文档内容请下载后查看。喜欢就下载吧 ……