《课后作业.doc》由会员分享，可在线阅读，更多相关《课后作业.doc（8页珍藏版）》请在三一办公上搜索。
1、第四章 词法分析P72 1.构造正规式1(0|1)*101相应的DFA. 答案 先构造NFA 确定化 0 1 X A A A AB AB AC AB AC A ABY ABY AC AB 重新命名，令AB为B、AC为C、ABY为D 0 1 X A A A B B C B C A D D C B DFA： 3.将下图确定化：答案 0 1 S VQ QU VQ VZ QU QU V QUZ VZ Z Z V Z QUZ VZ QUZ Z Z Z 重新命名，令VQ为A、QU为B、VZ为C、V为D、QUZ为E、Z为F。 0 1 S A B A C B B D E C F F D F E C E F F
2、 F DFA： 4.把下图最小化：答案 初始分划得0：终态组0，非终态组1,2,3,4,5 对非终态组进行审查： 1,2,3,4,5a 0,1,3,5 而0,1,3,5既不属于0，也不属于1,2,3,4,5 4 a 0，所以得新分划 1：0，4，1,2,3,5 对1,2,3,5进行审查： 1,5 b 4 2,3 b 1,2,3,5，故得新分划 2：0，4，1, 5，2,3 1, 5 a 1, 5 2,3 a 1,3，故状态2和状态3不等价，得新分划 3：0，2，3，4，1, 5 这是最后分划了最小DFA： 5.构造一个DFA，它接收=0,1上所有满足如下条件的字符串：每个1都有0直接跟在右边。
3、并给出该语言的正规式和正规文法。 答案 按题意相应的正规表达式是0*(0 | 10)*0*或0*( 100*)*0* 构造相应的DFA，首先构造NFA为 用子集法确定化 I I0 I1 S 0 1 X,0,1,3,Y 0,1,3,Y 2 1,3,Y 0,1,3,Y 0,1,3,Y 1,3,Y 1,3,Y 2 2 / 2 1 2 3 4 2 2 4 4 3 3 3 DFA：可最小化，终态组为1,2,4，非终态组为3，1,2,40 1,2,4，1,2,41 3，所以1,2,4为等价状态，可合并。 8给出下列文法所对应的正规式： S-0A|1B A-1S|1 B-0S|0 答案 解方程组S的解： S
4、=0A|1B A=1S|1 B=0S|0 将A、B产生式的右部代入S中 S=01S|01|10S|10=（01|10）S|（01|10） 所以：S= (01|10)*(01|10) 第五章 自顶向下优先分析法P991. 文法 S-a|(T) T-T,S|S (1) 对(a,(a,a)和(a,a),(a),a)的最左推导。 (2)对文法G改写，然后对每个非终结符写出不带回溯的递归子程序。 (3)经改写后的文法是否为LL（1）的？给出它的预测分析表。 (4)给出输入串(a,a)#的分析过程，并说明该串是否为G的句子。 答案 (1) 对(a,(a,a)的最左推导为： S=(T) =(T,S) =(S
5、,S) =(a,S) =(a,(T) =(a,(T,S) =(a,(S,S) =(a,(a,S) =(a,(a,a) 对(a,a),(a),a) 的最左推导为： S=(T) =(T,S) =(S,S) =(T),S) =(T,S),S) =(T,S,S),S) =(S,S,S),S) =(T),S,S),S) =(T,S),S,S),S) =(S,S),S,S),S) =(a,S),S,S),S) =(a,a),S,S),S) =(a,a),S),S) =(a,a),(T),S) =(a,a),(S),S) =(a,a),(a),S) =(a,a),(a),a) (3)改写文法为： 0) S-
6、a 1) S- 2) S-( T ) 3) T-S N2 4) N2-, S N2 5) N2- FIRST FOLLOW S a ( # , ) T a ( ) N2 , ) 对左部为N2的产生式可知： FIRST （-, S N2）=， FIRST （-）= FOLLOW （N2）=) ， )= 所以文法是LL(1)的。 预测分析表 a ( ) , # S -a - -( T ) T -S N2 -S N2 -S N2 N2 - -, S N2 也可由预测分析表中无多重入口判定文法是LL(1)的。 (4)对输入串（a,a）#的分析过程为： 步骤 状态栈 当前字符 剩余输入串 操作 1 #S
7、 ( a,a)# S-(T) 2 #)T( ( a,a)# 匹配 3 #)T A ,a)# T-SN2 4 #)N2S A ,a)# S-a 5 #)N2a A ,a)# 匹配 6 #)N2 , a)# N2-,SN2 7 #)N2S, , a)# 匹配 8 #)N2S a )# S-a 9 #)N2a a )# 匹配 10 #)N2 ) # N2- 11 #) ) # 匹配 12 # # 可见输入串（a,a）#是文法的句子。 3文法： S-MH|a H-LSo| K-dML| L-eHf M-K|bLM 判断G是否为LL(1)文法，如果是，构造LL(1)分析表。 答案 源文法G展开为： 0）
8、 S-M H 1） S-a 2） H-L S o 3） H- 4） K-d M L 5） K- 6） L-e H f 7） M-K 8） M-b L M FIRST FOLLOW S a,d,b,e #,o M d, ,b e,#,o H ,e #,f,o L e a,d,b,e,o,# K d, e,#,o 预测分析表 a o d e f b # S -a -MH -MH -MH -MH -MH M -K -K -K -bLM -K H - -LSo - - L -eHf K - -dML - - 由预测分析表中无多重入口判定文法是LL(1)的。 第六章 自底向上优先分析法P1161、已知文
9、法GS为： Sa|(T) TT,S|S (1)计算GS的FIRSTVT和LASTVT。 (2)构造GS的算符优先关系表并说明GS是否未算符优先文法。 (3)计算GS的优先函数。 (4)给出输入串(a,a)#和(a,(a,a)#的算符优先分析过程。 答案 (1) FIRSTVT和LASTVT FIRSTVT LASTVT S a、（ a、） T ，、a、（ ，、a、) (2) 算符优先关系 a ( ) , # a ( ) , # (3) 对应的算符优先函数为： a ( ) , # S 2 1 2 2 2 1 T 3 3 1 1 3 1 (4) 句子(a,a)#分析过程如下： 步骤 栈 优先关系
10、当前符号 剩余输入串 移进或归约 1 # #( ( a,a)# 移进 2 #( (a a ,a)# 移进 3 #(a a, , a)# 归约 4 #(F (, , a)# 移进 5 #(F, ,a A )# 移进 6 #(F,a A) ) # 归约 7 #(F,F ,) ) # 归约 8 #(F () ) # 移进 9 #(F) )# # 归约 10 #F # # 接受 句子(a, (a, a)分析过程如下： 步骤 栈 优先关系 当前符号 剩余输入串 移进或归约 1 # #( ( a,(a,a)# 移进 2 #( (a a , (a,a)# 移进 3 #(a a, , (a,a)# 归约 4
11、#(F (, , (a,a)# 移进 5 #(F, ,( ( a,a)# 移进 6 #(F,( (a a ,a)# 移进 7 #(F,(a a, , a)# 归约 8 #(F,(F (, , a)# 移进 9 #(F,(F, ,a a )# 移进 10 #(F,(F,a a) ) )# 归约 11 #(F,(F,F ,) ) )# 归约 12 #(F,(F () ) )# 移进 13 #(F,(F) ) ) # 归约 14 #(F,F ,) ） # 归约 15 #(F () ) # 移进 16 #(F) )# # 归约 17 #F # # 接受 第七章 LR分析法P1521、已知文法 A-aA
12、d| aAb| 判断该文法是否SLR（1）文法，若是构造相应分析表，并对输入串ab#给出分析过程。 答案 (1)拓广文法 (0)S-A (1) A-aAd (2)A- aAb (3)A- (1)构造识别活前缀的DFA FOLLOW(A)=d,b,# 对于状态I0：FOLLOW(A)a= 对于状态I1：FOLLOW(A)a= 因为，在DFA中无冲突的现象，所以该文法是SLR(1)文法。 (3)SLR(1)分析表 状态 ACTION GOTO a B d # A 0 S2 r3 r3 r3 1 1 acc 2 S2 r3 r3 r3 3 3 S5 S4 4 r1 r1 r1 5 r2 r2 r2 (4)串ab#的分析过程 步骤 状态栈 符号栈 当前字符 剩余字符串 动作 1 0 # a b# 移进 2 02 #a b # 归约A- 3 023 #aA b # 移进 4 0235 #aAb # 归约A- aAb 5 01 #A # 接受 部分文档在网络上收集，请下载后24小时内删除，不得传播，不得用于商业目的，如有侵权，请联系本人。谢谢
