资源描述:
《编译原理课后答案_第三版.doc》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、三12将图a确定化最小化10a,baa图a解:引入新的初态结点X和终态结点Y(X,Y不属于源非确定集)得图如下:YaεεX0εεa,ba1列出状态转换矩阵如下所示:abA{X,0,Y}{0,1,Y}{1}B{0,1,Y}{0,1,Y}{1}C{1}{0,Y}øD{0,Y}{0,1,Y}{1}CDBADFA如下:aabbbba最少化:终态{A,B,D}a={A,B}∈{A,B,D}{A,B,D}b={B,}∈{A,B,D}∴最少化为:10aba(b)将图b最少化b154320babaaabbaab图b解:终态{0,1}a∈{0,1}{0,1}b={2,4}
2、∈{2,3,4,5}∴{0,1}不能再分非终态{2,3,4,5}a={0,1,3,5}{2,4}a={0,1}{2,4}b={3,5}{3,5}a={3,5}{3,5}b={2,4}0代表{0,1},2代表{2,4},3代表{3,5}得最少化为:320ababba14.构造一个DFA,它接收∑={0,1}上所有满足如下条件的字符串:每个1都有0直接跟在右边。解:构造正规式为:(0
3、10)*则可构造如下NFA:εGBAFEDCqfq00εεεεε10εε列出状态转换矩阵如下:01A{q0,F,A,C,qf}{B,G,F,A,C,qf}{D}B{B,G,F,
4、A,C,qf}{B,G,F,A,C,qf}{D}C{D}{E,G,F,A,B,C,qf}øD{E,G,F,A,B,C,qf}{B,G,F,A,C,qf}{D}则得DFA如下:CDBA0001101最少化得{A,B,D}0={B}{A,B,D}1={C}A0C1015.给定右线性文法G:S->0S
5、1S
6、1A
7、0BA->1C
8、1B->0C
9、0C->0C
10、1C
11、0
12、1求出一个与G等价的左线性文法。BSC解:由G得NFA=<{S,A,B,C}∪{f},{0,1},δ,S,{f}>A1f0,1110,10,1000由NFA得左线性文法:GL=<{0,1},{A,
13、B,C,f},f,ρ’>ρ’:A->1B->0C->A1
14、B0
15、C0
16、C1f->A1
17、B0
18、C0
19、C1四1.考虑下面文法G:S->a
20、^
21、(T)T->T,S
22、S(1)消除G的左递归(2)改写后的文法是否是LL(1)的?给出预分析表。解:(1)S->a
23、^
24、(T)T->ST’T’->,ST’
25、ε(2)FIRSTFOLLOWSa,^,(#,,,)Ta,^,()T’,,ε)预分析表:a^(),#SS->aS->^S->(T)TT->ST’T->ST’T->ST’T’T’->εT->,ST’是LL(1)的。五5.文法S->AS
26、bA->SA
27、a(1)列出所有LR
28、(0)项目(2)构造LR(0)项目集规范族及识别活前缀的DFA(3)该文法是SLR的么?若是构造它的SLR分析表。解:扩展文法:S’->SSI6:A->S·AA->SA·A->·aS->·ASS->·bS->AS
29、bA->SA
30、abI1:S’->S·A->S·AA->·aS->·ASS->·bI0:S’->·SS->·AS S->·bA->·SAA->·aAaSI5:A->SA·S->A·SS->·ASS->·bA->·SAA->·aAaSbAI2:S->A·S S->·ASS->·bA->·SAA->·aI3:S->b·bbSI4:A->a·aaI7:
31、S->AS·A->S·AA->·SA A->·aS->·ASS->·bSAbAaaSbA(3) FollowFirstS’#a,bS#,a,ba,bAa,ba,b冲突项目I1中:有接受项目和移进冲突,可解决. #a,bI5,I7存在移进,归约冲突,不可解决.∵Follow(S)∩a∩b≠○所以,该文法不是SLR的8.证明下面的文法S->AaAb
32、BbBaA->εB->ε是LL(1)文法。①不含左递归;②First(α1)∩First(α2)∩…=○③First(A)∩Follow(A)=○∴该文法是LL(1)文法七1.给出下面表
33、达式的逆波兰表示(后缀式):a*(-b+c)a+b*(c+d/e)notAornot(CornotD)(AandB)or(notCorD)后缀式分别为:ab-c+*abcde/+*+AnotCDnotornotorABandCnotDoror3.请将表达式-(a+b)*(c+d)-(a+b+c)分别表示成三元式、间接三元式和四元式序列。三元式:(0)(+,a,b)(1)(-,(0),_)(2)(+,c,d)(3)(*,(1),(2))(4)(+,a,b)(5)(+,(4),c)(6)(-,(3),(5))间接三元式:(1)(+,a,b)(2)(-,(1)
34、,_)(3)(+,c,d)(4)(*,(2),(3))(5)(+,(1),c)(