1、第二章 P36-6 (1) LG( )1 是 09 组成的数字串 (2) 最左推导 : N ND N D D N D D D D D D D DDD DD DN ND DD DN ND N D D DDD DD D 0 01 0 1 2 0 1 2 73 345 56 5 6 8 最右推导 : N ND N ND N ND N DN ND N DN ND N ND N D 7 7 27 27 127 127 0 1 2 74 4 348 8 68 68 568 P36-7 G(S) ON OD NS O AOA AD N1 3 5 7 92 4 6 80| | | | | | | P36-8
2、文法： E T E T E TT F T F T FF E i | | * | /( )|最左推导 : E E T T T F T i T i T F i F F i i F i i iE T T F F F i F i E i E T i T T i F Ti i T i i F i i i * * * * * * * ( ) * ( ) * ( ) * ( )* ( ) * ( ) * ( ) 最右推导 : E E T E T F E T i E F i E i i T i i F i i i i iE T F T F F F E F E T F E F F E iF T i F F i
3、F i i i i i * * * * * * * * * ( ) * ( ) * ( ) * ( )* ( ) * ( ) * ( ) * ( ) 语法树： /* EE FTE +TFFT+iiiEE FTE -TFFT-iiiEEFT+TFFTii i*i+i+i i-i-i i+i*i*/ P36-9 句子 iiiei 有两个语法树： S iS e S iS e i ii S e i ii ie iS iS ii S e S ii S e i ii ie i P36-10 /* ) (|)( |ST TTSS */ P36-11 /* L1: |cCCabaAbAACS L2: bcbB
4、cBaAAABS| L3: |aBbBaAbAABS L4: ABBAABAS|01|10| */ 第三章习题参考答案 P64 7 (1) 101 101( | )* 0 1 1 0 1 1 确定化： 0 1 X 1,2,3 1,2,3 2,3 2,3,4 2,3 2,3 2,3,4 2,3,4 2,3,5 2,3,4 2,3,5 2,3 2,3,4,Y 2,3,4,Y 2,3,5 2,3,4, 0 1 0 0 0 1 1 0 0 1 0 1 1 1 最小化： X 1 2 3 4 Y 5 X Y 6 0 1 2 3 5 4 , , , , , , , , , , , , , , , , , ,
5、 , , , , , , , , , , , , , , , , , , , , , , , , ,0 1 2 3 4 5 60 1 2 3 4 5 1 3 5 0 1 2 3 4 5 1 2 4 60 1 2 3 4 5 60 1 2 3 4 1 3 50 1 2 3 4 5 60 1 2 3 10 100 3 0 1 2 3 1 2 40 1 2 3 4 5 60 1 1 0 1 1 22 3 3 2 3 40 1 2 3 4 5 610 10 1 , , , , , , , , , , , , , , , , , , , , , 0 1 0 0 1 0 0 1 0 1 1 1 P64 8
6、 (1) 01)0|1( * (2) )5|0(|)5|0()9|8|7|6|5|4|3|2|1|0)(9|8|7|6|5|4|3|2|1( * (3) * )110|0(01|)110|0(10 P64 12 (a) a a,b a 确定化： a b 0 0,1 1 0,1 0,1 1 1 0 5 0 1 2 4 3 0 1 给状态编号： a b 0 1 2 1 1 2 2 0 3 3 3 3 a a a b b b b a 最小化： , , , , , , , , , , , 0 1 2 30 1 1 0 1 22 3 0 3 2 3 30 1 2 3a ba b a a b b a b
7、(b) b b a a b a a b b a a a 已经确定化了 ,进行最小化 0 1 2 3 0 1 2 0 2 3 1 4 5 最小化： , , , , , 0 1 2 3 4 50 1 1 0 1 2 42 3 4 5 1 3 0 5 2 3 4 5 2 3 4 52 4 1 0 2 4 3 53 5 3 5 3 5 2 40 1 2 4 3 50 1 1 0 1 2 42 4 , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , a ba ba ba ba ba , , , , , , , 1 0 2 4 3
8、 53 5 3 5 3 5 2 4ba b b b a a b a P64 14 (1) 0 1 0 (2): ( | )*010 0 1 0 确定化： 0 1 X,1,Y 1,Y 2 0 1 2 0 1 Y X Y X 2 1 1,Y 1,Y 2 2 1,Y 给状态编号： 0 1 0 1 2 1 1 2 2 1 3 3 3 3 0 0 1 0 1 1 1 0 最小化： , , , , , , , , , , , 0 1 2 30 1 1 0 1 22 3 1 3 2 3 30 1 2 30 10 1 0 1 1 1 0 0 第四章 P81 1 (1) 按照 T,S 的顺序消除左递归 |,)(
9、|)(TSTTSTTaSSG递归子程序： procedure S; begin if sym=a or sym= then abvance else if sym=( 0 2 1 3 0 1 3 then begin advance;T; if sym=) then advance; else error; end else error end; procedure T; begin S; T end; procedure T ; begin if sym=, then begin advance; S; T end end; 其中 : sym:是输入串指针 IP 所指的符号 advance:
10、是把 IP 调至下一个输入符号 error:是出错诊察程序 (2) FIRST(S)=a,( FIRST(T)=a,( FIRST( T )=, FOLLOW(S)=),# FOLLOW(T)=) FOLLOW( T )=) 预测分析表 a ( ) , # S S a S S T( ) T T ST T ST T ST T T T ST, 是 LL(1)文法 P81 2 文法： |)(|*|baEPFFFPFTTTFTEEETE(1) FIRST(E)=(,a,b, FIRST(E)=+, FIRST(T)=(,a,b, FIRST(T)=(,a,b, FIRST(F)=(,a,b, FIRS
11、T(F)=*, FIRST(P)=(,a,b, FOLLOW(E)=#,) FOLLOW(E)=#,) FOLLOW(T)=+,),# FOLLOW(T)=+,),# FOLLOW(F)=(,a,b,+,),# FOLLOW(F)=(,a,b,+,),# FOLLOW(P)=*,(,a,b,+,),# (2) 考虑下列产生式 : E ET TF FP E a b|* |( )| | |FIRST(+E) FIRST( )=+ = FIRST(+E) FOLLOW(E)=+ #,)= FIRST(T) FIRST( )=(,a,b, = FIRST(T) FOLLOW(T)=(,a,b, +,)
12、,#= FIRST(*F) FIRST( )=* = FIRST(*F) FOLLOW(F)=* (,a,b,+,),#= FIRST(E) FIRST(a) FIRST(b) FIRST()= 所以 ,该文法式 LL(1)文法 . (3) + * ( ) a b # E E TE E TE E TE E TE E E E E E T T FT T FT T FT T FT T T T T T T T T T T T T F F PF F PF F PF F PF F F F F* F F F F F F P P E( ) P a P b P (4) procedure E; begin if
13、 sym=( or sym=a or sym=b or sym= then begin T; E end else error end procedure E; begin if sym=+ then begin advance; E end else if sym# then error end procedure T; begin if sym=( or sym=a or sym=b or sym= then begin F; T end else error end procedure T; begin if sym=( or sym=a or sym=b or sym= then T else if sym=* then error end procedure F; begin if sym=( or sym=a or sym=b or sym= then begin P; F end else error end procedure F; begin if sym=* then begin advance; F end end procedure P; begin if sym=a or sym=b or sym= then advance else if sym=( then
