发布时间 : 星期四 文章编译原理习题及答案（整理后）更新完毕开始阅读ddf7e3777fd5360cba1adb58
8、规范推导是最左推导，故选d。
9、由T→T,?和T→(? 得FIRSTVT(T))={(,，)}；
由T→S得FIRSTVT(S)?FIRSTVT(T)，而FIRSTVT(S)={b,∧,(}；即 FIRSTVT(T)={b,∧,(,，}； 因此选c。
10、d 11、c 12、b 13、b 14、b
多选解答 1、e、a、c 2、a、c、e 3、b、c、d 4、a、c 5、b、c 6、a、b、c、d、e 填空解答 1、空集 终结符 右 2、最左
3、自上而上 自下而上 4、自上而上
5、语法 分析 6、移进 接受
7、4 2 型 3型 上下文无关语言 正规语言 下推自动机 有限 判断解答 1、对 2、错 3、错 4、错 5、错 6、错
简答[解答]
1、句柄：一个句型的最左直接短语称为该句型的句柄。
2、素短语：至少含有一个终结符的素短语，并且除它自身之外不再含任何更小的素短语。 3、语法树：满足下面4个条件的树称之为文法G[S]的一棵语法树。 ①每一终结均有一标记，此标记为VN∪VT中的一个符号；
②树的根结点以文法G[S]的开始符S标记；
③若一结点至少有一个直接后继，则此结点上的标记为VN中的一个符号； ④若一个以A为标记的结点有K个直接后继，且按从左至右的顺序，这些结点的标记分别为X1,X2,?,XK，则A→X1,X2,?,XK，必然是G的一个产生式。 4、归约：我们称αγβ直接归约出αAβ，仅当A→γ 是一个产生式，且α、β∈(VN∪VT)*。归约过程就是从输入串开始，反复用产生式右部的符号替换成产生式左部符号，直至文法开始符。
5、推导：我们称αAβ直接推出αγβ，即αAβ?αγβ，仅当A→ γ 是一个产生式，且α、β∈(VN∪VT)*。如果α1?α2???αn，则我们称这个序列是从α1至α2的一个推导。若存在一个从α1αn的推导，则称α1可推导出αn。推导是归约的逆过程。
问答1[解答]
一个上下文无关文法G是一个四元式（VT,VN,S, P），其中： ●VT是一个非空有限集，它的每个元素称为终结符号；
●VN是一个非空有限集，它的每个元素称为非终结符号，VT∩VN=Φ； ●S是一个非终结符号，称为开始符号； ●P是一个产生式集合（有限），每个产生式的形式是P→α，其中，P∈VN， α∈(VT∪VN)*。开始符号S至少必须在某个产生式的左部出现一次。
2[解答] （1）由于产生式左部存在终结符号，且所有产生式左部符号的长度均小于等于产生式右部的符号长度，所以文法G[S]是Chomsky1型文法，即上下文有关文法。
（2）按产生式出现的顺序规定优先级由高到低（否则无法推出句子），我们可以得到： S?abQ?abc
S?aSPQ?aabQPQ?aabPQQ?aabbQQ?aabbcQ?aabbcc
S?aSPQ?aaSPQPQ?aaabQPQPQ?aaabPQQPQ?aaabPQPQQ?aaaPPQQQ? aaabbPqqq?aaabbQQQ?aaabbbcQQ?aaabbbccQ?aaabbbccc ??
于是得到文法G[S]生成的语言L={anbncn|n≥1} 3【解答】
（1）由L={aibj|j＞i≥1}知，所求该语言对应的上下文无关文法首先应有S→aSb型产生式，以保证b的个数不少于a的个数；其次，还需有S→Sb或S→bS型的产生式，用以保证b的个数多于a的个数；也即所求上下文无关文法G[S]为：
G[S]：S→aSb|Sb|b
4【解答】（1）分别画出对应两句型的语法树，如图2-8-2所示 句柄:AaB Bd
S a A c B S a A c B B S c A B d c (b)
A a B b S c A
B d c
b (a)
图2-8-2 语法树
（2）句子acabcbbdcc的最左推导如下：
S?aAcB?aAaBcB?acaBcB?acabcB?acabcbScA?acabcbBdcA ?acabcbbdcA?acabcbbdcc 5【解答】 S （1）句型（S,（a））的语法树如图2-8-3所示 （ L ）
L ， S
S ( L ) S （2）由图2-8-3可知：
①短语：S、a、(a)、S,(a)、(S,(a))； a ②直接短语：a、S； 图2-8-3 句型（S,（a））的语法树 ③句柄：S；
④素短语：素短语可由图2-8-3中相邻终结符之间的优先关系求得，即；
# ·（·， ·（ ·a· ）· ）· # 因此素短语为a。
6【解答】
首先构造T*P↑（T*F）的语法树如图2-8-4所示。
由图2-8-4可知，T*P↑（T*F）是文法G[T]的一个句型。 直接短语有两个，即P和T*F；句柄为P。
T T * F F ↑ P P （ T ） T * F 图2-8-4 句型T*P↑（T*F）的语法树 第三章
一、单项选择题
1、词法分析所依据的是 。
a. 语义规则 b. 构词规则 2、词法分析器的输出结果是 。
c. 语法规则
d. 等价变换规则
a. 单词的种别编码 b. 单词在符号表中的位置 c. 单词的种别编码和自身值 d. 单词自身值 3、正规式M1和M2等价是指 。
a. M1和M2的状态数相等 b. M1和M2的有向弧条数相等
c. M1和M2所识别的语言集相等 d. M1和M2状态数和有向弧条数相等 4、状态转换图（见图3-6-1）接受的字集为 。
0
X 1 Y 0
图3-6-1
a. 以 0开头的二进制数组成的集合 b. 以0结尾的二进制数组成的集合 c. 含奇数个0的二进制数组成的集合 d. 含偶数个0的二进制数组成的集合 5、词法分析器作为独立的阶段使整个编译程序结构更加简洁、明确，因此， 。 a. 词法分析器应作为独立的一遍 b. 词法分析器作为子程序较好
c. 词法分析器分解为多个过程，由语法分析器选择使用 d. 词法分析器并不作为一个独立的阶段 二、多项选择题
1、在词法分析中，能识别出 。 a. 基本字 b. 四元式 c. 运算符 d. 逆波兰式 e. 常数
2、令∑={a,b}，则∑上所有以b开头，后跟若干个ab的字的全体对应的正规式为 。 a. b(ab)* b. b(ab)+ c.(ba)*b
+
d. (ba)b e. b(a|b) 三、填空题
1、确定有限自动机DFA是 的一个特例。
2、若二个正规式所表示的 相同，则认为二者是等价的。 3、一个字集是正规的，当且仅当它可由 所 。 四、判断题
1、一个有限状态自动机中，有且仅有一个唯一终态。 （ ） 2、设r和s分别是正规式，则有L（r|s）=L(r)|L(s)。 （ ） 3、自动机M和M′的状态数不同，则二者必不等价。 （ ） 4、确定的自动机以及不确定的自动机都能正确地识别正规集。 （ ） 5、对任意一个右线性文法G，都存在一个NFA M，满足L(G)=L(M)。 （ ） 6、对任意一个右线性文法G，都存在一个DFA M，满足L(G)=L(M)。 （ ） 7、对任何正规表达式e，都存在一个NFA M，满足L(G)=L(e)。 （ ） 8、对任何正规表达式e，都存在一个DFA M，满足L(G)=L(e)。 （ ） 五、基本题
1、设M＝（{x,y}, {a,b}, f,x,{y}）为一非确定的有限自动机，其中f定义如下：
f（x,a）＝{x,y} f（x,b）＝{y} f（y,a）＝φ f（y,b）＝{x,y}
试构造相应的确定有限自动机M′。 2、对给定正规式b*（d|ad）（b|ab）+，构造其NFA M； 单选解答 1、b 2、c 3、c 4、d 5、b 多选解答 1、a、c、e 2、a、b、d
填空解答 1、NFA 2、正规集 3、DFA（NFA）所识别 判断解答 1 、2、3、错 4、5、6、7、8、正确
基本1解答：对照自动机的定义M=(S,Σ,f,S0,Z)，由f的定义可知f(x,a)、f(y,b)均为多值函数，所以是一非确定有限自动机，先画出NFA M相应的状态图，如图3-6-2所示。 a a b 用子集法构造状态转换矩阵表3-6-3所示。 X b Y I Ia Ib b {x} {x,y} {y} 图3-6-2 {y} — {x,y} NFA M {x,y} {x,y} {x,y}
将转换矩阵中的所有子集重新命名而形成表3-6-4所示的状态转换矩阵。 表3-6-4 状态转换矩阵 0 1 2 a 2 — 2 b 1 2 2 a 0 2 a,b 1 b b 即得到M′=（{0,1,2}, {a,b}, f,0, {1,2}），其状态转换图如图3-6-5所示。
将图3-6-5的DFA M′最小化。首先，将M′的状态分成终态组{1，2}与非终态组{0}；其次，考察{1,2}。由于{1,2}a={1,2}b={2}?{1,2}，所以不再将其划分了，也即整个划分只有两组{0}，{1,2}：令状态1代表{1,2}，即把原来到达2的弧都导向1，并删除状态2。最后，得到如图3-6-6所示化简DFA M′。
a
a,b 1 0
b
图3-6-6 化简后的DFA M′
2解答：首先用A+=AA*改造正规式得：b*(d|ad)(b|ab)(b|ab)*；其次，构造该正规式的NFA M，如图3-6-7所示。
b*(d|ad)(b|ab)(b|ab)* X Y
X b* b 1 (d|ad) d 1 ad d 1 a 2 (b|ab) b 2 *3 (b|ab) Y b|ab 3 ε 5 ε Y X ε 4 ε b 2 ab b b 3 ε 5 a ε Y b 8 X ε 4 ε a 6 d 7 b 图3-6-7 的 NFA M