北京工商局网-八年级语文上册教案

编译原理期末考试试卷（ C 卷）
一、单项选择题（每小题2分，共30分）
1、编译程序是对_ _____程序进行翻译。
A. 自然语言 B. 汇编语言
C. 高级语言 D. 机器语言
2、描述语言L={ a
m
b
n
| m≥1，n≥1 }的文法为 。
A. S→AB B. S→AB

A→Aa | a A→ a

B→Bb | b B→ b


→aSb | ab C. SD. S→aSb | ε

3、设有文法G=({b},{S,B}, S, { S→bB , B→bS |ε} )，下列哪个符号串 不
是该文法的句子。
A. b B. bb C. bbb D. bbbbb
4、下图DFA所识别的语言为_______ 。

A
0
B

0

1 1 1 1

0
C
D

0

A. 含有偶数个0偶数个1的二进制串
B. 含有偶数个0奇数个1的二进制串

C. 含有奇数个0偶数个1的二进制串
D. 含有奇数个0奇数个1的二进制串
5、下述正规式等价的是 。
A.(a|b)与(ab) B.(ab)与ab C.(a|b)与(ab) D. (a|b)与a|b
6、设有一个LR(1)项目集I ={ X→.bB,a B→.,a }则该项目集 __________。
A.不含冲突项目 B. 含有移进-归约冲突
C.含有归约-归约冲突 D. 含有移进-待约冲突
7、LR语法分析栈中存放的状态是识别文法规范句型__________的DFA状态。
A. 句柄 B.前缀 C. 活前缀 D. 项目
8、有文法如 S → r D
1
*
**
*
********

D → D,i | i
则FIRSTVT(D)=_________。
A.{ i } B. {i ,} C. { i r } D. { i r ,}
9、有文法如 S → r D
D → D,i | i
则 i 和 ，的优先关系是_________。
A.没有优先关系 B. 等于 C. 低于 D. 高于
10、算符优先分析法从左到右扫描输入串，采用移进- 归约的方式，当栈顶出现
___________时进行归约。
A. 素短语 B.最左素短语C. 句柄 D. 直接短语
11、局部优化是局限于一个_________范围内的一种优化。
A.程序 B. 函数 C.基本块 D. 循环
12、在编译中，动态存储分配的含义是_________。
A. 在运行阶段对源程序中的量进行存储分配
B. 在编译阶段对源程序中的量进行存储分配
C. 在说明阶段对源程序中的量进行存储分配
D. 以上都不正确
13、以下说法正确的是_________。
A. 对任何一个编译程序来说，产生中间代码不是不可缺少的一部分。
B. 在属性文法中，文法的终结符只有综合属性，不存在继承属性。
C. 自下而上语法制导翻译中语法分析栈与语义分析栈必需同步操作。
D. 以上都正确
14、后缀式abcd+*的中缀表达式是_________。
A. ab*(c+d) B. a(b*c+d)
C. a(b*(c+d)) D. a*(b+c)d
15、有翻译模式如下：
D → int L { print(L.s);}
L → id { L.s=1;}
L → L
1
,id { L.s= L
1
.s +1;}
采用移进归约的分析方法，当分析器的输入为int a,b,c 时，输出的结果
是 。
A. 4 B. 3 C.2 D.1

2

三、应用题（1、4、5每题10分，2、3每题15分，共60分）
2、有文法如下：
S → T L
T → int | float
L → id R
R → ,id R |ε
(1). 计算文法的每个非终结符的FIRST和FOLLOW集合；

(1)（8分） FIRST(S) ={ int,float} FOLLOW(S) ={#}

FIRST(T) ={ int,float} FOLLOW(T) ={id}

FIRST(L)={ id} FOLLOW(L) ={# }
FIRST(R)={ , ε} FOLLOW(R) ={# }

4、
有定义算术表达式的文法如下：
E → E+T | E-T | T
T → T*F | TF | F
F → PF | P
P → (E) | i
构造句型E-T*PF+i的语法树；并指出该句型的所有短语、直接短语、素短语、
句柄。
4、句型E-T*PF+i的语法树：（5分）
短语：E-T*PF+i、E-T*PF、T*PF、PF、i
直接短语：PF、i
素短语：PF、i
句柄：PF



1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
C A B D A A C B D B C A D C B
3

编译原理期末考试试卷（ B卷）

一、简述编译程序的工作过程。（10）

编译程序的工作过程，是指从输入源 程序开始到输出目标程序为止的
整个过程，是非常复杂的，就其过程而言，一般可以划分为五个工作阶段 ：
①词法分析，对构成源程序的字符串进行扫描和分解，识别出一个个的单
词；②语法分析，根 据语言的语法规则，把单词符号串分解成各类语法单
位；③语义分析与中间代码产生，即对各类语法单位 ，分析其汉一并进行
初步翻译；④代码优化，以期产生更高效的代码；⑤目标代码生成，把中
间 代码变换成特定机器上的低级语言指令形式。

二、给出下面的正规表达式（15）
（1） 以01结尾的二进制数串；
（2） 能被5整除的十进制整数；
（3） 包含偶数个1或偶数个0的二进制数串。

（1）（0|1）*01
（2）digit=0|1|2|3|4|5|6|7|8|9
digit*（0|5）
（3）（（0*10*1）*0*）|（（1*01*0）*1*）
三、对下面的文法G：
S→a | b | （T）
T→T，S | S
(1) 消去文法的左递归，得到等价的文法G2；
(2) 判断文法G2是否LL（1）文法，如果是，给出其预测分析表。（15）

G2：
S→a | b | （T）
T→ ST’
T’→，S T’ |
ε
G2是LL（1）文法。
a b
S S→a S→b
T T→ ST’ T→ ST’
T’

四、对下面的文法G：

（
S→（T）
T→ ST’

）


T’→
ε

，


T’→，S
T’
#



S→AB
4

A→A00 | 0
B→B11 | 1

(1) 消去文法的左递归，得到等价的文法G2；
(2) 判断文法G2是否LL（1）文法，如果是，给出其预测分析表。（15）

G’： S→AB
A→0A’
A’→00A’ | ε
B→1B’
B’→11B’ |ε
文法G’[S]是LL(1)文法。
预测分析表：
0
S S→AB
A A→0A’
A’ A’→00A’
B
B’


五、设有文法G[A]：
A→BCc | gDB
1


A’→ε
B→1B’
B’→11B’
#




B’→ε
B→bCDE |
ε
C
→DaB | ca
D→dD |
ε

E→gAf | c
(1) 计算该文法的每一个非终结符的FIRST集和FOLLOW集；
(2) 试判断该文法是否为LL（1）文法。（15）
FIRST FOLLOW
A A,b,c,d,g
B b
C A,c,d
D D
E C,g

（2） 是LL（1）文法。




A,c,d
C,d,g
A,b,c,g
5

编译原理期末考试试卷（D卷）


三、应用题（1、4、5每题10分，2、3每题15分，共60分）
1、为正规式(a|b)a(a|b)构造等价且状态最少的确定有限自动机。
（要求给出主要步骤）
*

2、有文法如下：
S → BA
A → BS | d
B → aA | bS | c
(1). 计算文法的每个非终结符的FIRST和FOLLOW集合；
(2). 判断文法是否LL（1）文法，如果是，给出其预测分析表，否则说明理由。

4、
有文法如下：
T → T*F | F
F → PF | P
P → (T) | i
证明T*iP是该文法的一个句型，但不是规范句型；
指出T*iP的所有短语、直接短语、素短语、句柄。

三、应用题（1、4、5每题10分，2、3每题15分，共60分）
1、(a|b)a(a|b) 状态最少的DFA。


NFA如图（5分）：

（也可是其它等价的FA）
A
b
I

*
a
a
B
a
b
C



用子集法得到的状态转换矩阵：




确定化（3分）后的DFA如

图，已是状态最少的。如不说

明是最简的扣1分。

2分）

化简（


注：初态或终态错扣1分

I
a

1 { A} {A,B}
2 {A,B} {A,B,C}
3 {A,B,C} { A,B,C}
4 {A,C}

a
1
b b
2
b
a
I
b

{A}
{A,C}
{A,C}
{A}
a
a
3
b
4
{ A,B}
6

2、(1)（6分） FIRST(S) ={ a,b,c )} FOLLOW(S) ={#,a,b,c,d }

FIRST(A) ={ a,b,c,d )} FOLLOW(A) ={#,a,b,c,d }

FIRST(B)={ a,b,c} FOLLOW(B) ={a,b,c,d }

(2) 因为文法不含左递归，关于A的两个规则的SELECT集不相交，关于B的3个
规则的SELECT集两两不相交，所以文法是LL（1）文法（2分）。
预测分析表（7分）如下：

S
A
B
a
S → BA

A → BS

B → aA

b
S → BA

A → BS

B → bS

c
S → BA

A → BS

B → c

d

A →d


#




4、对于符号串T*iP存在如下推导：（或画一颗语法树证明是句型）
T  T*F  T*PF  T*PP  T*iP
所以T*iP是该文法的一个句型，但不存在一 个规范推导能推导出该句型，所
以不是规范句型。（5分）
短语：T*iP、iP、i、p
直接短语：i、p
素短语：i
句柄：i



2. 考虑文法 G[S]:
S → (T) | a+S | a
T → T,S | S
消除文法的左递归及提取公共左因子。
解：消除文法G[S]的左递归：
S→(T) | a+S | a
T→ST′
T′→,ST′| ε
提取公共左因子：
S→(T) | aS′
S′→+S | ε
T→ST′
T′→,ST′| ε
7

24.已知文法G[S]
S→S*aF | aF | *aF
F→+aF | +a
消除文法左递归和提公共左因子。
答：消除左递归
S→aFS’ | *aFS’
S’→*aFS’ | ε
F→+aF | +a
提公共左因子,文法 G’(S)
S→aFS’ | *aFS’
S’→*aFS’ | ε
F→+aF’
F’→F |ε

1、设文法G(S):
S→^ | a | (T)
T→T,S | S
⑴ 消除左递归；
⑵ 构造相应的FIRST和FOLLOW集合；
⑶ 构造预测分析表
(1)消除左递，文法变为G’[S]：
S→^ | a | (T)'
T→ST’ | S
T’→,ST’ |ε
此文法无左公共左因子。

10.设文法G(S):
S→(T) | aS | a
T→T,S | S
⑴消除左递归和提公共左因子；
⑵构造相应的FIRST和FOLLOW集合；
⑶构造预测分析表。
.(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)
8

S
S’
L
L’

(
S →(L)
S’→S
L→SL’

)

S’→ε

L’→ε
a
S → aS’
S’→S
L→SL’

,

S’→ε
L’→,SL’

#

S’→ε


1. 已知文法G(S)：
S—>a|(T)
T—>T,S|S
①给出句子((a,a),a)的最左推导并 画出语法树；②给出句型
(T,a,(T))所有的短语、直接短语、素短语、最左素短语、句柄和活< br>前缀。
解：（1）最左推导：S

(T)

(T,S)
(S,S)

(a,S)

(a,(T))
(a,(T,S))

(a,(S,S))

(a,(a, S))

(a,(a,a))
语法树：如图A-16所示。
S
( T )
T , S
S
a
( T )
T , S
S
a
a

图A-16 (a,(a,a))的语法树
（2）句型(T, a, (T))的短语、直接短语、素短语、最左素短语、句柄、
活前缀及语法树（图A-17）。
短语：a || T,a || (T) || T , a , (T) || (T , a , (T))
直接短语：a || (T)
素短语：a || (T)
最左素短语：a
句柄：a
活前缀：

|| ( || (T || (T , || (T , a
S
( T )
T , S
T , S
( T )
a

9
图A-17 (T,a,(T))的语法树

二、构造下列正则表达式的确定性的有限状态自动机。 （12%）
aba(a|b)*a

答：

1
a
2
b
3
a
b
a
4
b
5
a


二、设={0，1}上的正规集S由倒数第二个字符为1的所有字 符串组成，
请给出该字集对应的正规式，并构造一个识别该正规集的DFA。(8分)
答：
构造相应的正规式：(0|1)*1(0|1) (3分)
NFA: (2分)
1 1

    1
0 1 2 3
4


0 0
确定化：(3分)
I
I
1

I
0

{0,1,2} {1,2} {1,2,3}
{1,2} {1,2} {1,2,3}
{1,2,3} {1,2,4} {1,2,3,4}
{1,2,4} {1,2} {1,2,3}
{1,2,3,4} {1,2,4} {1,2,3,4}

0
1
0 1 0 0
0 1 2
3 4

0 1

1 1


10