编译原理试卷及参考答案

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

学号： 姓名：

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

一、 概念题（15分）

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

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

字母 字母 0 1 数字 其中：状态2的过程为proc2.

3、文法G为： S?aAB A?a

B??|?|?

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

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

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

其他 2

（ ）

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）文法，为什么？ 五、（本题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

3、 给出语句IF a∨b

(1)E?i

?1?

?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班编译原理考试答案及评分细则

一：1、(5分)

源程序词法分析单词符号语法分析语法单位语义分析与中间代码产生中间代码优化中间代码目标代码生成目标代码

2、(5分)

Proc 0: getchar(); CASE char OF ‘a’,’b’,…,’z’: ‘A’,’B’,…,’Z’: proc 1 else error END CASE

3、(5分) 条件：

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

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

1、×； 2、×； 3、√； 4、√； 5、√。

三、（10分）

方法一：

句型AaBc的语法树为：

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

方法二：

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

a b c #

对于#AaBc#，##，则最左素短语为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分）

a > < b < < c = > < # > > > = a b c d # a < b < > < c = > < d < # > > > > = 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、项目集规范族：

1E’→E.0E’→.EE→.eAfE→.eBgE2eE→e.AfA→.aAA→.aE→e.BgB→.BbB→.aA4aA→a.AA→a.A→.aAA→.aB→B.b5BE→eB.gB→B.bA3E→eA.ff6E→eAf.7A→aA.8A→a.AA→a.A→.aAA→.a9E→eBg.10B→Bb.Aaagb（6分）

本文来源：https://www.bwwdw.com/article/txqx.html