2018年11月编译原理期中测试
一、概念题：（每题 分，共 30 分）
1、请写出由下列文法所确定的语言。（16分）
（1）G1: S →10S01 S →aA A →bA A →a 解：
n
m n n m n m
n n n n n n n
a a
b A ab abA aA S S S S )01()10()01()10()01()10()01()10()01()10(010*********⇒⇒⇒⇒⇒⇒⇒
所以语言{n
m
n
a a
b )01()10(} n>=0,m>=0
（2）G2: S →aSS S →a
2、解
：1
2*+⇒⇒⇒⇒⇒⇒n a S aaaaaaa aaSSaSS S aaaaa
aaSSS S aaa
S
所以语言{ 1
2+n a
} n>=0
（3）G3:S → aSb|c 解：
（4）G4: S->D|SD D->0|1|2|3|4|5|6|7|8|9 解：
2、已知语言L ，试构造相应文法。（6分）
构造产生语言 }1,0|{≥≥n m b d c a n m m n 的文法。
答：S → aAb | aSb A →ε | cAd
3、已知文法 G[S] 为 S → aSb|Sb|b ，试证明文法 G[S] 为二义文法。（8分） 解：一个文法，如果存在某个句子有不只一棵语法分析树与之对应，那么称这个 文法是二义性文法。句子aabbbb 有两棵语法树。如下图：
二、简答题：（每题分，共 70 分）
1、给定文法G[S]：bQ
aA
S|
→; b
bB
aA
A|
|
→；aQ
bD
B|
→;
b
bD
aQ
Q|
|
→；aA
bB
D|
→;bF
aB
E|
→; b
aE
bD
F|
|
→
构造相应的最小的DFA (必须给出中间构造过程)。（15分）
解：先构造其NFA：
用子集法将NFA确定化：
将S、A、Q、BZ、DZ、D、B重新命名，分别用0、1、2、3、4、5、6表示。因为3、4中含有z，所以它们为终态。
令P
P1＝（｛0,5, 6｝,｛1,2｝,｛3,4｝）再用b进行分割：
P2＝（｛0｝,｛5, 6｝,｛1,2｝,｛3,4｝）再用a、b 进行分割，仍不变。再令｛０｝为A，｛1，2｝为B，｛3，4｝为C，｛5，6｝为D。最小化为上右图。
2、构造一个正规式，它接受S={a，b,c}上符合以下规则的字符串：串内至多包含一个 a.（5分）
(b|c)* | (b|c)*a(b|c)*
3、设文法G(S):（15分）
S → S+aF | aF | +aF
F → *aF | *a
(1) 消除左递归和回溯； (2) 构造相应的FIRST和FOLLOW集合；
(3) 构造预测分析表
答：
（1）消除左递归（2分）和回溯（2分）：
S→aFS' | +aFS'
S'→+aFS' | ε
F→*aF'
F'→F | ε
（2）构造FIRST集合（1分）构造FOLLOW集合（2分）
FIRST(S)={a,+} FOLLOW(S)={$}
FIRST(S')={+,ε} FOLLOW(S')={$} FIRST(F)={*} FOLLOW(F)={+,$}
FIRST(F')={*,ε) FOLLOW(F')={+,$} （3）构造预测分析表（3分）
-
a + * $ S S→aFS' S→+aFS'
- - S' - S'→+aFS'
- S'→ε F - - F→*aF' - F'
-
F'→ε
F'→F
F'→ε
4、已知文法a
aT T aT
aT aT S S S G ++→→|*||*:)(
(1) 给出句型aT a a a ++*的最左推导并画出语法树；
(2) 写出上述句型的所有短语，直接短语、句柄和最左素短语。（10分） 解：（1）句型aT a a a ++*的最左推导为：
aT a a a aT a a aT aT aT S S ++⇒+⇒⇒⇒****,语法树如下图：
（2）短语：a +，a a +，aT +,aT a a a ++* 直接短语：a +, aT + 句柄：a +
最左素短语：a +
5、文法εε
ε||||:)(d D eT Db B Ba T TB M M G →→→→是否是LL(1)的，说明理由。（列出FIRST 和FOLLOW
集）（10分）（76页3.4）
解：计算文法的FIRST 集合和FOLLOW 集合：
FIRST(M)={a,b,e,d,ε} FIRST(T)={a,b,e,d,ε} FIRST(B)={b,e,d,ε} FIRST(D)={d,ε}
FOLLOW(M)={#} FOLLOW(T)={a,b,e,d,#} FOLLOW(B)={a,#} FOLLOW(D)={b} 检查文法的所有产生式，我们可以得出： （1）该文法不含左递归；
（2）该文法中每一个非终结符M,T,B,D 的各个产生式的候选首符集两两不相交；
（3）该文法的非终结符T,B 和D ，他们都有ε候选式，而且
φ≠=},,,{)()(d e b a T FOLLOW T FIRST I
所以该文法不是LL(1)文法。
6、已知文法S S A A a
A S S G ||)(:)(+→→
(1)求出该文法所有非终结符的FIRSTVT 集、LASTVT 集。 (2)构造该文法的算符优先关系表（15分） 100页 例4.3 解：FIRSTVT(S)={a,(} FIRSTVT(A)={+,a,(} LASTVT(S)={a,)} LASTVT(A)={+,a,)}
