编译原理期末复习题

3.2 是非判断，对下面的陈述，正确的在陈述后的括号内写t ，否则写 f。(1) 有穷自动机接受的语言是正则语言。（）(2) 若 r1 和 r2 是上的正规式，则 r1|r 2 也是。（）(3) 设 m 是一个 nfa ，并且 l(m) x,y,z ，则 m 的状态数至少为4 个。（）(4) 令 a,b ，则 上所有以 b 为首的字构成的正规集的正规式为b*(a|b) * 。（）(5) 对任何一个nfa m ，都存在一个dfa m ， 使 得 l(m)=l(m) 。（）(6) 对一个右线性文法g，必存在一个左线性文法g，使得 l(g)=l(g) ，反之亦然。（）答案(1)t(2)t(3)f(4)f(5)t(6) t3.3 描述下列各正规表达式所表示的语言。(1)0(0|1) *0(2)(|0)1 *)*(3)(0|1) * 0(0|1)(0|1)(4)0*10 *10 *10 *(5)(00|11) *(01|10)(00|11) * (01|10)(00|11) *)*答案(1) 以 0 开头并且以0 结尾的，由0 和 1 组成的符号串。(2) |0,1 *(3) 由 0 和 1 组成的符号串，且从右边开始数第3 位为 0。精品资料(4) 含 3 个 1 的由 0 和 1 组成的符号串。|0,1+ ，且 中含有 3 个 1 (5) |0,1 *,中 0 和 1 为偶数 3.4 对于下列语言分别写出它们的正规表达式。(1) 英文字母组成的所有符号串，要求符号串中顺序包含五个元音。(2) 英文字母组成的所有符号串，要求符号串中的字母依照词典顺序排列。(3) =0,1 上的含偶数个1 的所有串。(4) =0,1 上的含奇数个1 的所有串。(5) 具有偶数个0 和奇数个1 的有 0 和 1 组成的符号串的全体。(6) 不包含子串011 的由 0 和 1 组成的符号串的全体。(7) 由 0 和 1 组成的符号串 , 把它看成二进制数，能被3 整除的符号串的全体。答案(1) 令 letter 表示除这五个元音外的其它字母。(letter) *a(letter) * e(letter) *i(letter) *o(letter) *u(letter) *(2) a*b *z *(3) (0|10 *1) *(4) (0|10 * 1) *1(5) 分析 设 s 是符合要求的串，|s|=2k+1 (k 0）。则 s s 10|s 21 ， |s1 |=2k (k0 ）， |s 2 |=2k (k 0）。且 s 1 是0,1 上的串，含有奇数个0 和奇数个1 。s2 是0,1 上的串，含有偶数个0 和偶数个1 。考虑有一个自动机m 1 接受 s1，那么自动机m 1 如下：和 l(m 1)等价的正规表达式，即s 1 为：(00|11)|(01|10)(00|11)*(01|10) *(01|10)(00|11)*类似的考虑有一个自动机m 2 接受 s2 ，那么自动机m 2 如下：和 l(m 2)等价的正规表达式，即s 2 为：(00|11)|(01|10)(00|11)*(01|10) *因此， s 为：(00|11)|(01|10)(00|11)*(01|10) *(01|10)(00|11)*0| (00|11)|(01|10)(00|11)*(01|10) *1(6)1 *|1 *0(0|10) *(1| )(7) 接受 w 的自动机如下：对应的正规表达式：(1(01 * 0)1|0) *3.6给出接受下列在字母表0,1 上的语言的dfa 。(1)所有以 00 结束的符号串的集合。(2)所有具有 3 个 0 的符号串的集合。答案(a) dfam=(0 ， 1 ， q 0， q1 ， q2，q 0， q 2， )其中 定义如下 :（ q 0， 0 ） =q 1（ q 0，1 ） =q 0（ q 1， 0 ） =q 2（ q 1，1 ） =q 0（ q 2， 0 ） =q 2（ q 2，1 ） =q 0(b) 正则表达式 : 1 *01 * 01 *01 *dfa m=(0 ，1 ， q 0 ， q1， q 2， q3， q0 ， q 3 ，)其中 定义如下 :（ q 0， 0 ） =q 1（ q 0，1 ） =q 0（ q 1， 0 ） =q 2（ q 1，1 ） =q 1（ q 2， 0 ） =q 3（ q 2，1 ） =q 2（ q 3， 1 ） =q 33.7 构造等价于下列正规表达式的有限自动机。(1)10| （0|11 ） 0* 1 (2)(0|1) *|(11) *答案(1)dfa m=(0 ， 1 ， q 0 ，q1 ， q2， q 3， q0， q 3， )其中 定义如下 :(2) （ q0 ， 0） =q 1（ q0， 1 ） =q 2(3) （ q1 ， 0） =q 1（ q1， 1 ） =q 3(2) dfam=(0 ，1 ， q 0， q0 ， q 0 ，)其中 定义如下 :（ q0 ， 0） =q 0（ q0， 1 ） =q 0(4) （ q2 ， 0） =q 3（ q2， 1 ） =q 1(5)(6)(7)(8)(9)3.8 给定右线性文法g ： s-0s|1s|1a|0ba-1c|1b-0c|0c-0c|1c|0|1试求一个于 g 等价的左线性文法g3.9 试对于下列正规表达式使用证明定理3。5 的构造算法构造非确定的有限自动机。请给出每个自动机在处理输入符号串ababbab的过程中的动作序列。(1) (a|b) *(2) (a *|b*)*(3) ( |a)b *)*3.10 转换练习3.9 中的每个nfa 为 dfa。并给出每个dfa 在处理输入符号串ababbab的过程中的动作序列。3.11 试把练习 3.10 中得到的 dfa 的状态给以最小化。答案(1),(2),(3) 的 dfa m 相同，化简结果为：(4)3.12 我们可以证明两个正规表达式是等价的，如果它们的最小状态dfa 是相同的（除了状态的名字以外） 。利用这一结论，请说明下列正规表达式都是等价的。(1) (a|b) *(2) (a *|b*)*(3) ( |a)b *)*答案根据 3.11 的结果知这几个正规表达式是等价的。3.13 对于下列正规表达式构造最小状态的dfa 。(1) (a|b) *a(a|b)(2) (a)b) *a(a|b)(a|b)5 对如下文法：g s ： sa b s | a a b | a dbb b b | bsad分别给出句子abaabbb 和 ad 的 句 柄句子 ad 的语法分析树为：句子 abaabbb 的语法分析树为 :sabsaabbbbb所以句子 abaabbb的句柄是 b；句子 ad 的句柄是 ad .二、（10 分）说明如下文法是否是ll （1）文法，若不是，将其转换为ll （1 ）文法。最后给出该文法的ll （1 ）分析表。ga：ab eb b b | a文法中有左递归，不是ll(1) 文法。转换为g：ab eba b b b b | predict(a b e) = a predict(b a b ) = a predict(b b b ) = b predict(b ) = e ll(1) 分析表 :abeab ebba b b b 4. 给出识别正则表达式(（a|bc ） * d) +的 nfa。5. 已知文法gs ：s s； ggg g(t) hh a (s)t t+s s找出句型： a(t+s) ； h； (s) 的短语、简单短语和句柄。短语 : a,t+s,a(t+s) , h ,a(t+s);h ,(s)简单短语： a , t+s , h , (s)句柄是a .6. 已知文法gs 为：s ab | bca b | b ad | c ad | b d as | c对其每一个非终级符求first 集 和 follow集。first (s) = b , a ,first (a) = b ,first (b) = a ,first (c) = b , a , c first (d) = a , c follow (s) = # follow (a) = a , c , # follow (b) = # follow (c) = # follow (d) = # ib*esb|ec|.iec|二、（ 10 分）设有文法ga:absc判定该文法是否为ll(1) 文法？若是则给出它的ll(1) 分析表，否则说明理由。先计算各个产生式的predict集：predict (a- ib*e)= i ; predict (b- sb)= , .predict (b-)= * predict (s-ec) = predict (s-. i)= . predict (c- ec)= e predict (c-)= 因为 predict集没有冲突，所以是ll(1) 文法。ll(1) 分析表如下：i*e.a- ib*e-b-s b-s bs-e c-. ic-ec-1、证明下面文法是ll(1) 的但不是slr(1) 文 法s aaab|bbbaab 解：对于产生式s aaab|bbba来说first(aaab) first(bbba)=ab= 而 a， bvn 仅有一条候选式。因此，这个文法是ll(1) 的。下面构造这个文法的识别活前缀的dfa 。i0 = s s, saaab, s bbba, a , b i1 = s s i2 = s a aab i3 = s b bbai4 = s aaab, a i5 = s bbba, b i6 = s aaa bi7 = s bbb a i8 = s aaab i9 = s bbba 由 于 follow (a)= follow (b)=a, b因此项目集i0 中存在归约归约冲突。在i0 状态下，当输入符号是a 或是 b 时，不知用a 还 是 b 进行归约。故此文法不是slr(1) 的。但是，此文法是lr(1) 的。五、 已知文法gs ，其产生式如下：s(l)|al l，s|s从 gs 中消除左递归，并为之构造一个非递归预测分析器ll(1) 分析表。请说明在句子(a ， (a ，a) 上的分析器的动作。（20 分） 解：将所给文法消除左递归得g： s (l)|al sll ，sl |实现预测分析器的不含递归调用的一种有效方法是使用一张分析表和一个栈进行联合控制，下面构造预测分析表：根据文法g 有first(s) = ( , a )follow(s) = , , , $ first(l) = ( , a )follow(l) = first(l ) = , follow(l ) = 按以上结果，构造预测分析表m 如下：文法 g是ll(1) 的，因为它的ll(1) 分析表不含多重定义入口。预测分析器对输入符号串(a, (a, a) 做出的分析动作如下：例 5.3 的文法 g3s为：saa sd abas a不难看出由定义5.3 可得： select(s aa)=a select(s d)=d select(a bas)=b select(a )=a,d,# 所以select(s aa) select(s d)=a d= select(a bas) select(a )=b a,d,# =由定义 5.4 知例 5.3 文法是 ll(1) 文法，所以可用确定的自顶向下分析。而对例 5.5文法 g5s 为：saassb aba a则 select(s aas)=a select(s b)=b select(a ba)=b select(a )=a,b所以select(s aas) select(s b)=a b=select(a ba) select(a )=b a,b 因此，例5.5 文法不是ll(1) 文法，因而也就不可能用确定的自顶向下表达式文法为：ee+t|ttt*f|f fi|(e)构造步骤：(1)判断文法是否为ll(1) 文法4.5 已知文法 gs ，其产生式如下：s(l)|al l，s|s从 gs 中消除左递归，并为之构造一个非递归预测分析器ll(1) 分析表。请说明在句子(a， (a ，a) 上的分析器的动作。解：将所给文法消除左递归得 g： s (l)|a l sll ， sl | 实现预测分析器的不含递归调用的一种有效方法是使用一张分析表和一个栈进行联合控制， 下面构造预测分析表：根据文法 g 有first(s) = ( , a )follow(s) = ) , , , $ first(l) = ( , a )follow(l) = ) first(l ) = , follow(l) = ) 按以上结果，构造预测分析表m 如下：文法 g是 ll(1) 的，因为它的ll(1) 分析表不含多重定义入口。预测分析器对输入符号串(a,(a, a) 做出的分析动作如下：4.6 对于练习 4.1 的文法，构造它的ll(1) 分析表。解：从练习4.1 得到文法的产生式如下：r r | t | tt tf | f f f* | cc (r)| a | b消除上面文法中的左递归r trr | tr |t ftt ft | f cff *f | c (r) | a | b计算 first( )和 follow(a)构造 ll(1) 分析表。4.9 对于文法 gs ，其产生式如下s (l)|a (4.22)l l,s|s(1) 给出句子 (a ， (a， a)，(a ， a) 的一个最右推导，并指出右句型的句柄。(2) 按照 (a) 的最右推导，说明移进-归约分析器的工作步骤。解： (1)s =(l)=(l, s)=(l,(l)=(l,(l,s)=(l,(l,(l)=(l,(l,(l,s)=(l,(l,(l,a)=(l,(l,(s,a)=(l,(l,(a,a)=(l,(s,(a,a)=(l,(l),(a,a)=(l,(l,s),(a,a)=(l,(l,a),(a,a)=(l,(s,a),(a,a)=(l,(a,a),(a,a)=(s,(a,a),(a,a)=(a,(a,a),(a,a)右句型的句柄为每个右句型中用下划线标识出的部分。(2)对于 (a) 的最右推导，移进规约分析器的工作步骤如下：4.11 下列文法是否为slr(1) 文法？若是，请构造相应的分析表。若不是，请说明理由。(a)s sab|brr s|a解：该文法的拓广文法g 为(0) s s(1) s sab(2) s br(3) r s(4) r a其 lr(0) 项目集规范族和goto 函数 (识别活前缀的dfa) 如下 :i0 = s s, s sab, s bri1 = s s, s sabi2 = s br, r s, r a, s sab, s bri3 = s sa bi4 = s br i5 = r s, s s abi6 = r a i7 = s sab 求 follow集：follow (s)= follow (r)= follow (s)=a, 在 i5 中，出现移进归约冲突，且follow (r)a=a 因此，此文法不是slr(1) 文法。b)s asab|baa aa|bb b解：该文法的拓广文法g 为(0) s s(1) s asab(2) s ba(3) a aa(4) a b(5) b b其 lr(0) 项目集规范族和goto 函数 (识别活前缀的dfa) 如下 :i0 = s s, s asab, s ba, b bi1 = s s i2 = b bi3 = s asab, s asab, s ba, b bi4 = s b a, a aa, a b, b bi5 = s as ab, a aa, a b, b bi6 = s asa b, b bi7 = a aa, a aa, a b, b bi8 = a b i 9 = s ba i 10 = s asab i11 = a aa 求 follow集：follow (s)= follow (s)=a,b, follow (a)=a,b, follow (b)=a,b, 4.12 证明下面文法是slr(1) 文法，并构造其slr 分析表。ee+t|tttf|fff*|a|b解：该文法的拓广文法g 为(0) e e(1) e e+t(2) e t(3) t tf(4) t f(5) f f*(6) f a(7) f b其 lr(0) 项目集规范族和goto 函数 (识别活前缀的dfa) 如下 :i0 = e e, e e+t, e t, t tf, t f, f f*,fa, f b i1 = e e , e e+ti 2 = e t , t t f, f f*, f a, f bi3 = t f, f f *i 4 = f ai5 = f b i6 = e e+ t, t tf, t f, f f*, f a, f bi7 = t tf , f f*i8 = f f* i9 = e e+t , t tf, f f*, f a, f b求 follow集：follow(e)= , follow(t)= , , a, b follow(f)=, , a, b, *构造的slr 分析表如下：显然，此分析表无多重定义入口，所以此文法是slr 文法。4.13 下面文法属于哪类lr 文法？试构造其分析表。s (sr|ar,sr|)解：该文法的拓广文法g 为(0) s s(2) s a(4) r )(1) s(3) r (sr ,sr构造其lr(0) 项目集规范族和goto函数 (识别活前缀的dfa) 如下 :i0 =s s,s(sr, sai1 = s s i 2 = s (sr, s (sr, s ai3 = s ai 4 = s (s r, r ,sr,r)i5 = s (sr i6 = r )i7 = r ,sr, s (sr, s a i8 = r ,s r, r ,sr, r )i9 = r ,sr 每个 lr(0) 项目集中没有冲突。因此，此文法是lr(0) 文法。其分析表如下：4.14 设文法 g 为 saaba| b ab|b(1) 证明它是 lr(1) 文法。(2) 构造它的 lr(1) 分析表。(3) 给出输入符号串abab 的分析过程。解： (1)构造其拓广文法g 的产生式为(0) s s(1) s a(2) a ba(3) a (4) b ab(5) b b构造其 lr(0) 项目集规范族和goto 函数 (识别活前缀的dfa) 如 下 :i0 = s s, $, s a, $, a ba, $, a , $,bab, a/b/$, bb, a/b/$ i1 = s s, $i2 = s a, $i3 = a ba, $, a ba, $, a , $,bab, a/b/$, bb, a/b/$i4 = b b , a/b/$i5 = b a b, a/b/$, b ab, a/b/$,bb, a/b/$ i6 = a ba , $i7 = b ab , a/b/$该文法的lr(1) 项目集规范族中没有冲突，所以该文法是lr(1) 文法。(2) 构造 lr(1) 分析表如下：以上分析表无多的定义入口，所以该文法为lr(1) 文法。(3) 对于输入串abab ，其分析过程如下：4.15 为下面的文法构造lalr(1) 分 析 表 s ee e+t|tt(e)|a解：其拓广文法(0) sg： s(1) s e(2) e e+t(3) e t(4) t (e)(5) t a构造其 lr(1) 项目集规范族和goto 函数 (识别活前缀的dfa) 如 下 :i0 = s s, $, s e, $, e e+t, $/+, e t, $/+, t(e), $/+, t a, $/+i1 = s s, $i2 = s e , $, e e+t, $/+i3 = e t , $/+ i4 = t (e), $/+, e e+t, )/+, et, )/+,t(e), )/+, t a, )/+i5 = t a, $/+i6 = e e+ t, $/+, t (e), $/+, t a, $/+i7 = t (e ), $/+, e e +t, )/+i8 = e t, )/+i9 = t (e), )/+, e e+t, )/+, et, )/+, t (e), )/+, t a, )/+ i10 = t a , )/+i11 = e e+t , $/+i12 = t (e) , $/+i13 = e e+ t, )/+, t (e), )/+, t a, )/+i14 = t (e ), )/+, e e +t, )/+ i15 = e e+t , )/+i16 = t (e) , )/+合并同心的lr(1) 项目集，得到lalr的项目集和转移函数如下：i0 = s s, $, s e, $, e e+t, $/+, e t, $/+, t (e), $/+, t a, $/+i1 = s s, $i 2 = s e, $, e e+t, $/+i3,8 = e t , $/+/)i4,9 = t (e), $/+/), e e+t, )/+, et, )/+,t(e), )/+, t a, )/+i5,10 = t a , $/+/)i6,13 = e e+ t, $/+/), t (e), $/+/), ta, $/+/)i7,14 = t (e ), $/+/), e e +t, )/+i11,15 = e e+t , $/+/) i12,16 = t (e) , $/+/)lalr 分析表如下：br4.16 考虑文法 gs ，其产生式如下sas | b a sa | a(1) 构造文法gs 的 lr(0) 项目集规范族及相应的dfa 。(2) 如果把每一个 lr(0) 项目看成一个状态，并从每一个形如 b x 的状态出发画一条标识为 x 的箭弧到状态 b x ,而且从每一个形如 b a 的状态出发画标记为 的箭弧到所有形如 a 的状态。这样就得到了一个 nfa 。说明这个 nfa 与(a) 的 dfa 是等价的。 (3) 构造文法的 slr 分析表。(4) 对于输入串bab ，给出 slr 分析器所作出的动作。(5) 构造文法的lr(1) 分析表和 lalr 分析表。解： (1) 其拓广文法(0) s sg：(1) s as(2) s b(4) a a(3) a sa构造其 lr(0) 项目集规范族和goto 函数 (识别活前缀的dfa) 如 下 : i0 = s s, s as, s b, a sa, a ai1 = s s , a sa, a sa, a a, s as, s b i2 = s as, s as, s b, a sa, a a i3 = a a i4 = s b i5 = a sa , sa s, s as, s b, a sa, a a i6 = a sa, a sa, a a, s as, s bi7 = s as , as a, a sa, a a, s as, s b(2) 文法 gs 的 lr(0) 项目如下：(0) s s(1) s s(2) s as(3) s a s(4) s as (5) s b(6) s b(7) a sa(8) a s a(9) a sa (10)a a(11)a a对上面的nfa 通过求 -cloasure确定化，得到与(1) 相同的识别文法gs 活前缀的dfa 。因此，此nfa 与(1) 的 dfa 等价。(3) 求 follow集：follow (s) = a, b, follow (a) = a, b gs 的 slr 分析表：(4) (4)注： gs 的 slr 分析表中有移进归约冲突，因此它不是一个slr 文法。其实， gs 是一个二义性文法，对于句子abab 有下面两棵不同的分析树。因此，gs 不是任何lr 文法。(5) 文法 gs 的 lr(1) 项目集规范族及转移函数为：i0 = s s, $, s as, $/a, sb, $/a, a sa, a/b, aa, a/bi1 = s s, $, a sa, a/b, a sa,a/b, a a, a/b, s as, a/b, sb, a/bi2 = s as, $/a/b, sas, $/a/b, sb, $/a/b, a sa, a/b, aa, a/b, i3 = a a, a/bi4 = s b , a/b/$i5 = a sa, a/b, a sa, a/b, a a, a/b, s as, a/b, s b, a/b6 = a sa , a/b, s a s, a/b, s as, a/b, sb, a/b, a sa, a/b, aa, a/bi7 = s as , a/b/$, a s a, a/b, a sa, a/b, aa, a/b, s as, a/b, s b, a/bi8 = s as, a/b, s as, a/b, s b, a/b, a sa, a/b, a a, a/bi9 = s as , a/b/$, a s a, a/b, a sa, a/b, aa, a/b, s as, a/b, s b, a/b, i10 = s b , a/b合并同心项目集(i 2 和 i8 ， i7 和 i 9， i4 和 i10 )：i0 = s s, $, s as, $/a, sb, $/a, a sa, a/b, aa, a/b