编译原理
2014—2015学年第二学期第四单元测试试卷（闭卷考试）时间：45分钟满分：100分
姓名班级出题人刘兵班级 2
一、选择题（5*2分）（每题1分，共10分）
1．编译过程中语法分析器的任务就是__________。
(1) 分析单词是怎样构成的（2）分析单词串是如何构成语句和说明的
（3）分析语句和说明是如何构成程序的（4)分析程序的结构
A （2）（3） B（2）（3）（4） C （1）（2）（3） D（1）（2）（3）（4）
2．给定文法G[S]及其非终结符A，FIRST(A)定义为：从A 出发能推导出的终结符号的集合（S 是文法的起始符号，为非终结符）。
对于文法G[S]：
S→[L] | a
L→L, S| S
其中，G[S]包含的四个终结符号分别为：a , [ ]
则FIRST(S)的成员包括。
A. a
B. a、[
C. a、[和]
D. a、[、]和，
3．若一个文法是递归的，则它产生的句子个数是( )
A．无穷个 B．不确定 C．有限个 D.根据具体情况而定
4．语法分析器则可以发现源程序中的__D___。
A．语义错误 B．语法和语义错误 C．错误并校正 D．语法错误
5．若文法 G 定义的语言是无限集，则文法必然是( ) 。
A．递归的 B．前后文无关的
C．二义性的 D．无二义性的
二、简答题（2*10分）（每题10分，共20分）
1．自上而下分析的前提？
2.若有文法A→(A)A|ε，说明该文法是LL(1)的文法。
三、分析题（4题共70分）
1．设有文法G[E]:
E→Aa|Bb
A→cA|eB
B→bd
试按照递归子程序法为该文法构造语法分析程序。
2．设有文法G[S]：
S→AB
A→bB|Aa
B→Sb|a
试消除该文法的左递归。
3.计算练习
4.2.2的文法的FIRST和FOLLOW集合
(1)S->S(S)S|ε
(2)S->(L)|a, L->L, S|S
4. 正规式(ab)*a与正规式a(ba)*是否等价？请说明理由。
编译原理
2014—2015学年第二学期第四单元测试试卷答案一、选择题
1—5 B、B、D、D、A
二、简答题（2*10分）（每题10分，共20分）
1
.解：消除左递规和消除回溯。
2.
解：该文法不含左递归；
FIRST（(A)A）={(}，FIRST（ε）={ε}，FIRST（(A)A）∩FIRST（ε）=Φ，且FOLLOW(A)＝｛)，#｝，FIRST（(A)A）∩ FOLLOW(A) =Φ，
因此，该文法满足LL(1)文法的条件，是LL(1)文法。
三、分析题（4题共70分）
1. 解：本题考查递归子程序的构造方法。
首先判断文法是否满足递归子程序法对文法的要求，然后再构造递归子程序。
因为：
（1）该文法无左递归。
（2）文法的产生式E→Aa|Bb和A→cA|eB的右部有若干选项，判断这两条产生式右部各候选式的终结首符号集合是否两两互不相交。
对产生式E→Aa|Bb，有
FIRST(Aa)∩FIRST(Bb)={c，e}∩{b}=ø
对产生式A→cA|eB，有
FIRST(cA)∩FIRST(eB)={c}∩{e}=ø
文法中其他产生式都只有一个非空ε的右部。
综合（1）、（2），该文法可以采用自上而下分析方法进行语法分析而不会出现回朔和无限循环。
下面为该文法的每一个非终结符号构造递归子程序。
假设用READAWORD代表读下一个单词。
用P(E)、P(A)、P(B)分别表示非终结符号E、A、B对应的子程序名。
约定输入符号串以“#”作为输入结束符。
P(E)的递归子程序为：
PROCEDURE P(E);
BEGIN
IF WORD IN FIRST(Aa)
THEN
BEGIN
P(A);
READAWORD;
IF WORD=’a’
THEN READAWORD
ELSE ERROR
END
ELSE IF WORD IN FIRST(Bb)
THEN
BEGIN
P(B);
READAWORD;
IF WORD=’b’
THEN READAWORD
ELSE ERROR
END
ELSE ERROR
END;
P(A)的递归子程序为：
PROCEDURE P(A);
BEGIN
IF WORDD=’c’
THEN
BEGIN
READAWORD;
P(A)
END
ELSE IF WORD=’e’
THEN
BEGIN
READWORD;
P(B)
END
ELSE ERROR
END;
P(B)的递归子程序为：
PROCEDURE P(B);
BEGIN
IF WORD=’b’
THEN
BEGIN
READAWORD;
IF WORD=’d’
THEN READAWORD
ELSE ERROR
END
ELSE ERROR
END;
主程序中的主要内容为：
READAWORD;
P(E);
IF WORD=”#”
THEN WRITE(“RIGHT!”)
ELSE WRITE(“ERROR!”)
2、解：本题考查消除左递归的方法。
应用消除文法左递归的算法对文法G[S]消除左递归的过程如下：（1）将非终结符排序为：U1=S，U2=A，U3=B
（2）进入算法排序：
i=1时，对文法无影响
i=2，j=1时：A→Aa有直接左递归，消去该直接左递归，得
A→bBA’
A’→aA’|ε
i=3，j=1时：改写文法，有
B→ABb|a
j=2时：改写文法，有
B→bBA’Bb|a无左递归。
（3）所以文法G[S]消除左递归后变为：
G’[S]：S→AB
A→bBA’
A’→aA’|ε
B→bBA’Bb|a
3、解：1)FIRST(S)={ ε,( } FOLLOW(S)={ (,),$ }
2)FIRST(S)={ (,a } FOLLOW(S)={ ),,,$ }
FIRST(L)={ (,a } FOLLOW(L)={ ),, }
4、
解：（1）FOLLOW(A)=First(B)∪{#}={b,#}
FOLLOW(B)={e,b}
（2）该文法中的规则B::=Bb|b为左递归，因此该文法不是LL(1)文法
（3）先消除文法的左递归（转成右递归），文法变为：A::=aABe|ε，B::=bB’，B’::=bB’|ε，该文法的LL(1)分析表为：
更常用且简单的LL(1)分析表：。