重庆师范大学第2005至2006学年度第 2 学期期末考核试卷
编译原理(B卷)
（闭卷）
课程性质：必修考核方式：考试专业：计算机科学与技术年级：2003
本科
一、填空题：（每空2分，共20分）
1．1．源程序是用高级语言编写的，目标程序是机器语言或汇编语言编写的，则其翻译程序称为。

2．2．编译的过程通常分为前端和后端，前端依赖于源语言而与目标机无关，如词法分析、语法分析、和中间代码生成。

3．3．Chomsky 3型文法又称为正规文法，其每个产生式都满足。

4．4．文法G的所有构成的集合称为该文法描述或产生的语言。

5．5．设文法G的产生式集为S→0P
S→01
P→S1
则该文法产生的语言L(G)为。

6．6．一个句型的最左直接短语称为该句型的。

7．7．由词法分析识别出的单词符号通常分为类。

8．8．自底向上的LR分析法是一种表驱动的方法，它是一个由分析栈、和总控程序以及输入串组成的下推自动机。

9．9．在语法分析后生成中间代码，通常是应用方法来实现的。

10．10．中间代码的局部优化是指局限于范围内的优化。

二题：（共8分）
），其中P为
S → a│b│(A)
A → B
B → SdB│S
写出句子((b)da) 的语法树、最左推导和最右推导，并指出其句柄。

三题：（共16分）
S → 0P | 1Q
P → 1S | 1
Q → 0S | 0
构造该文法相应的最小的DFA，请写出过程。

四题：（共10分）
t1:= b + c
t2:= a – t1
t3:= d + 1
t4:= e * f
t5:= t3 + t4
s:= t2 * t5
用简单代码生成方法生成目标代码，可用寄存器为R0、R1。

五题：（共15分）
：
S → S;E | E
E → E(F) | G
G → a│(S)
F → F+S | S
(1)(1)求出各非终结符的FIRSTVT集和LASTVT集；
(2)(2)构造该文法的算符优先关系表，并判断是否算符优先文法。

六题：（共16分）
S → Ec│c
E → Fb│b
F → Sa│a
(1)．试消除左递归、提取左公因子并化简；
(2)．判断所得文法是否为LL(1)文法。

七题：（共15分）
(1) j:=0 (8) goto (11)
(2) i:=0 (9) i:= i+1
(3) if i<8 goto (6) (10) if i<8 goto (4)
(4) A:=B+C (11) j:=j+1
(5) B:=D*C (12) if j<=3 goto (2)
(6) if B=0 goto (9) (13) halt
(7) write B
a)．请划分基本块，并构造程序流图；
b)．求出程序流图中所有结点的必经结点集，并找出回边及由回边组成的循环。