发布时间 : 星期六 文章编译练习题答案 - 图文更新完毕开始阅读09fc6a7df18583d048645932
2-22.设有语言L(G)={ada| a∈(a,b),a为a之逆}，试构造产生此语言的上下文无关文法G。 解：根据题义，可知a为a之逆的含义就是句子中的符号a、b以d为中心呈左右对称出现；由于a∈(a,b)，所以a、b的个数可以为零。所以可构造产生此语言的上下文无关文法G[S]为：S→aSa|bSb|d 2-23.证明下面文法G[N]是二义性文法。 G[N]： N →SE∣E S →SD∣D E →0∣2∣10
D →0∣1∣2
答：10是文法G[N]的一个句子，并且有两个不同的最右推导。
（1）1S => E => 10
（2）S => SE => S0 => D0 => 10 因此说明此文法有二义性。 3-03．简述DFA与NFA有何区别 ?
答：DFA与NFA的区别表现为两个方面:一是NFA可以若干个开始状态，而DFA仅只一个开始状态。另一
方面，DFA的映象M是从K×∑到K，而NFA的映象M是从K×∑到K的子集，即映象M将产生一个状态集合（可能为空集），而不是单个状态。 3-04.试给出非确定自动机的定义。
答：一个非确定的有穷自动机（NFA）M是一个五元组：M=（K，Σ，f，S ，Z）。
其中:
1. K是一个有穷集，它的每个元素称为一个状态；
2. Σ是一个有穷字母表，它的每个元素称为一个输入符号，所以也称Σ为输入符号表；
3. f是状态转换函数，是在K×Σ*→K的子集的映射，即，f: K×Σ*→2K ；表明在某状态下对于
某输入符号可能有多个后继状态； 4. S﹙K是一个非空初态集； 5. Z﹙K是一个终态集（可空）。
3-05. 为正规式（a|b）a(a|b) 构造一个等价的确定的有限自动机。
解答：
3-06. 给定下列自动机，将其转换为确定的自动机。
解答：(1)消除ε边，得到NFA：
＋ start S ＋ ― A d d d B ― d C · E d a,b ? 0 a 1 b a 2 *
R
*
R *R
d D ― G d 注：带＋号的结点为初始状态； 带―号的结点为终止状态
ε ε · H ― d
(2)确定化，得到DFA： S A B C D E G H
3-07. 给定下列自动机：
a a b
(1)把此自动机转换为确定自动机DFA。 (2)给出此DFA的正则表达式。 解答：（1）： 有状态矩阵如图：
a b
?0 0,1 2 1 2 －2 1 2
a b ?0 01 2 01 01 2 －2 1 2 1 2
1 a b 2 b
其中：开始状态：0 终止状态：2
G d ＋ ― A ＋ d d d B ― d C · E d d D ― G d ＋ S 注：带＋号的结点为初始状态； 带―号的结点为终止状态
d d · d · H ― d ＋ A ― A d BCE BCE B C D E H H d · G D G +[SA] [A] [BCE] [G] [DG] [H] [DH] ＋ [A] ― [A] d [BCE] [BCE] [BCE] [H] [DH] [H] [DH] · [G] [G] [DG] · ＋ SAA d H ― 注：带＋号的结点为初始状态；
带―号的结点为终止状态
＋ · ― A d d BCE· DGd DH― d A d A ―A ? 0 ?
从而可得DFA如图：
（2）此DFA的正则表达式为： (aab?b)(b?ab) 或 ab（b?ab）。 4-13.消除下列文法G[E]的左递归。
E→E-T∣T T→T/F∣F F→( E )∣i 解答：
消除文法G[E]的左递归后得到： E→TE’
E’→ -TE’∣ε T→FT’ T’→/FT’∣ε F→( E )∣i
4-14.在LL(1)分析法中,LL分别代表什么含义?
答:第一个L代表从左到右的扫描，第二个L代表每次进行最左推导。 4-15.自顶向下分析思想是什么？
答：从开始符出发导出句型并一个符号一个符号地与给定终结符串进行匹配。如果全部匹配成功，则表示
开始符号可推导出给定的终结符串。因此判定给定终结符号串是正确句子。 4-16.自顶向下的缺点是什么？
答：在推导过程中，如果对文法不做限制。那么产生式的选择成为无根据的，只好一一去试所有可能的产
生式，直至成功为止。这种方法的致命弱点是不断地回溯，大大影响速度。 4-17.LL（1）文法的定义是什么？
答：一个上下文无关文法是LL(1)文法的充分必要条件是每个非终结符A的两个不同产生式，A→α,A→
β；满足SELECT(A →α)∩SELECT(A →β)=Ф。其中，α、β不能同时4-18.什么是文法的左递归？
答：一个文法含有下列形式的产生式之一时：
1)A→Aβ，A∈VN，β∈V*
2)A→Bβ，B→Aα，A、B∈VN，α、β∈V*
ε。
*
*
*
*
a
01 a ? 0 b b 1 极小化后： a ? 0 b b 1 a 2 b b 2 b a - 则称该文法是左递归的。 4-19.递归下降法的主要思想是什么？
答：对每个非终结符按其产生式结构写出相应语法分析子程序。因为文法递归相应子程序也递归，子程序
的结构与产生式结构几乎一致。所以称此种方法称为递归子程序法或递归下降法。 5-19.自底向上分析法的原理是什么？
答：在采用自左向右扫描，自底向上分析的前提下，该类分析方法是从输入符号串入手，通过反复查找当
前句型的句柄（最左简单短语），并使用文法的产生式把句柄归约成相应的非终极符来一步步地进行分析的。最终把输入串归约成文法的开始符号，表明分析成功。 5-20.简单优先方法基本思想是什么？
答：简单优先方法基本思想是首先规定文法符号之间的优先关系和结合性质，然后在利用这种关系，通过
比较两个相邻的符号之间的优先顺序来确定句型的“句柄”并进行归约。 5-21.三种优先关系的定义是什么？ 答：三种优先关系的定义是：
1. si2. si3. si
sj 当且仅当存在形如下面的产生式U→?SiSj?
sj 当且仅当存在形如下面的产生式U→?SiW?的生产式，且有 Wsj 当且仅当存在形如下面的产生式U→?VW?的生产式,且有 V
Sj Si和W
Sj
5-22.如何确定简单优先文法的句柄？
答：设S1S2?Sn是简单优先文法的规范句型，其子串SiSi+1?Sj是满足下列条件的最左子串：
Si-1 Si Sj
Si Si+1Sj+1
??
Sj-1
Sj
则SiSi+1?Sj定是S1S2?Sn的句柄。 5-23. 给定文法G[Z]：
a) 构造此文法的LR(0)项目集规范族，并给出识别活前缀的DFA。 b) 构造其SLR（1）分析表。
解答：1.首先拓广文法：在G中加入产生式0．Z′→Z，然后得到新的文法G′，再求G′的识别全部活
前缀的DFA：
I0：Z′→.Z
Z→.C S
C→.if E then I1：Z′→Z. I2：Z→C .S
S→.A＝E A→.i
I3：C→if .E then
E→.E∨A E→.A A→.i I4：Z→C S.
I7：C→if E .then
E→E.∨A I9：S→A＝.E
E→.E∨A E→.A A→.i
I10：C→if E then. I11：E→E∨.A
A→.i
I12：S→A＝E.
E→E.∨A I13：E→E∨A.
1． Z→C S
2． C→if E then 3． S→A＝E 4． E→E∨A 5． E→A 6． A→i
其中：Z、C、S、A、E∈VN ； if、then、＝、∨、i∈VT
I0 Z C A I1 I2 S A i I6 i I3 E I7 ∨ I4 I5 ＝ i i I11 then I9 E I12 ∨ A I13