编译原理_习题.ppt

《编译原理_习题.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第2章习题及解答：试构造下述语言L的文法：L={ambn

2、m≥0,n≥1};【解1】G1(S):S->ABA->Aa

3、B->Bb

4、bS->ABA->aA

5、B->bB

6、b或G2(S):【解】分析：※产生式形式：1.此语言仅有一种句型：ambn；2.ambn中包含有两个短语：am和bn；于是：设：S(句子)，A（短语1），B（短语2）第2章习题及解答：试求下述文法G(Z)所定义的语言：G(Z):Z->b

7、bB,B->bZ【解】⒈推导运算法：L(G)={x

8、Zx,x∈VT*}=>+文法所定义的语言Z=>bB=>bbZ=>bbbZ=>bB=>bbZ=>bbbB=>bbbbZ=

9、>bbbbbZ=>b∴∵Z=>b2n-1,n≥1⒉正规方程式法：∵Z=b

10、bB,B=bZ即Z=b

11、bbZ※递推求解Z=b

12、bbZ可得：Z=b2n-1n≥1∴L(G)={b2n-1

13、n≥1}…第2章习题及解答：【解】根据文法G[S]:S->(AS)

14、(b);A->(SaA)

15、(a)⑵从语法述上，看(A((SaA)(b)))的短语、直接短语和句柄：S(AS)(AS)(SaA)(b)短语：①(A((SaA)(b)))②((SaA)(b))③(SaA)④(b)直接短语：③(SaA)④(b)句柄：③(SaA)⑴因为(a)不是句子，所以没有短语问题。已知文法G[S]:S->(AS)

16、

17、(b);A->(SaA)

18、(a)试找出符号串(a)和(A((SaA)(b)))的短语、直接短语(即简单短语)和句柄。SSAS第2章习题及解答：证明下面文法是二义性文法S->iSeS

19、iS

20、i【证】因为句型iiSeS有下述两棵不同的语法树：SiSeSiSSiSiSeS和所以所属文法是二义性文法！【习题】G(S):S->aAcBe;A->Ab

21、b;B->d⑴证明=aAbcde是一个句型；⑵画出句型的语法树；⑶指出句型的短语、简单短语和句柄。第2章习题及解答：已知文法G(S):E->E+T

22、E-T

23、T【解】∵消除直接左递归公式：整理:E->E+T

24、E–T

25、T∴有G`(S)

26、:E->T{T}A->A

27、≡A->{}A->A`,A`->A`

28、ε或G`(S):E->TE`E`->TE`

29、ε令：=+

30、-E->ET

31、T第2章习题及解答：已知文法G(S):S->aSab

32、bAB;A->bB

33、a;B->aA

34、bC->abB

35、baA;D->Cbc

36、abc;【解】删除无用产生式：自定己；不终结；不可达。⑴找自定己产生式（如A->A）无自定己者！⑵构造可终结非终结符集Vvt={},⑶构造可达非终结符集VAR={},G`(S):S->aSab

37、bAB;A->bB

38、a;B->aA

39、b∴删除不可达非终结符：C,D后得：无不终结者！A,B,C,D,S

40、S,A,B第3章习题及解答：试构造确定自动机DFA:⑴e=1(0

41、1)*101①+011-②1③④⑤01⑵e=(a

42、b)*(aa

43、bb)(a

44、b)*①+ab-②③④aabbabA{1}ba+DFA变换表DFA状态图ABCDE+--aaabbbbabaE{1,3,4}D{1,2,4}E{1,3,4}D{1,2,4}E{1,3,4}B{1,2}C{1,3}D{1,2,4}C{1,3}B{1,2}D{1,2,4}E{1,3,4}C{1,3}B{1,2}--确定化第3章习题及解答：试构造一个DFA,它接收∑={0,1}上所有满足如下条件的字符串：每一个1都有0直接跟在右边。【解】

45、①+01-②0③1-0①+-②010或给定正规语言，构造有限自动机：A={an,ban

46、n≥0}【解】①+-②baa-①+-②baa-第3章习题及解答：把下述NFA转换为DFA:①②③abab+-FA1:①②③abab+-FA2:ab+-DFA2:ABA{1}ba+B{2,3}B{2,3}B{2,3}-aab+-DFA1:ABCbC{2,3}B{2}C{2,3}B{2}C{2,3}B{2}-A{1}ba+第3章习题及解答消除NFA的边：②③①+a-ab③④-①+②babaFA3:FA4:【算法】⑶逆序删边,并补充新边。⑴闭路合而为一；⑵标记隐含初态和终态；

47、②①+-abaDFA1③④-①+②babaab③-①+②aabbaDFA2无用状态第3章习题及解答：已知符号串集合，构造正规式、自动机和正规文法：A={,an,ban

48、n≥1}【解】正规式:e=

49、a+

50、ba+或e=a*

51、ba+自动机DFA:aa+-12b-3a正规文法:SABS->aA

52、bB

53、A->aA

54、B->aA已知自动机DFA:②ab③⑤bcc①④bb-+-⑴扩展DFA(加入结束标记#),构造压缩变换表；⑵根据实现算法，写出识别abbc#的过程。⑵输入串abbc#识别过程：第3章习题及解答：【解】⑴扩展DFA:压