¡¶±àÒëÔÀí¡·¸´Ï°Ìâ
I4: S¡¯¡ú aS? S a I0: S¡¯¡ú ?S S¡ú ?aS S¡ú ?bS S¡ú ?a b I2: S¡ú a?S S¡ú ?aS S¡ú ?bS S¡ú ?a S¡ú a? a S I1: S¡¯¡ú S? b a I5: S¡¯¡ú bS? I3: S¡ú b?S S¡ú ?aS S¡ú ?bS S¡ú ?a S b £¨2£©ÔÚ״̬I2´æÔÚ¡°Òƽü-¹éÔ¼¡±³åÍ»£¬Òò´Ë¸ÃÎÄ·¨²»ÊÇLR(0)ÎÄ·¨¡£
¼ÆËãSµÄFOLLOW¼¯ºÏ£º FOLLOW(S)= {#}
I2ÖеijåÍ»ÓÃFOLLOW¼¯ºÏ¿ÉÒÔ½â¾ö£¬ËùÒÔ¸ÃÎÄ·¨ÊÇSLR(1)ÎÄ·¨¡£ ¹¹ÔìSLR(1)·ÖÎö±íÈçÏ£º
״̬ 0 1 2 3 4 5
29£®½«ÏÂͼËùʾµÄ·ÇÈ·¶¨ÓÐÏÞ×Ô¶¯»ú(NFA)±ä»»³ÉµÈ¼ÛµÄÈ·¶¨ÓÐÏÞ×Ô¶¯»ú(DFA)¡£ÆäÖУ¬XΪ³õ̬£¬YΪÖÕ̬¡£
ACTION a s2 s2 s2 b s3 s3 s3 # acc r3 r1 r2 GOTO S 1 4 5 29
¡¶±àÒëÔÀí¡·¸´Ï°Ìâ
b2bab3b4baYaaX1??a?
¡¾½â¡¿ ÓÃ×Ó¼¯·¨½«NFAÈ·¶¨»¯£¬ÈçͼËùʾ¡£
IIaIbSab{X}{1}{3}012{1}{2,3,Y}{3,Y}134{3}¡ª{3,4}ÖØÐÂÃüÃû2¡ª5{2,3,Y}{2,3,Y}{2,3,4,Y}336{3,Y}{2,3,Y]{3,4}435{3,4}{3,4}{3,4,Y}557{2,3,4,Y}{2,3,4,Y}{2,3,4,Y}666{3,4,Y}{2,3,4,Y}{3,4,Y}767È·¶¨»¯µÄDFAÈçÏÂͼËùʾ£º
a3aaba1ba604bb2bab5b7ab30£®
¶ÔÕý¹æÊ½(a|b)*abb¹¹ÔìÆäµÈ¼ÛµÄNFA¡£ ¡¾½â¡¿
30
¡¶±àÒëÔÀí¡·¸´Ï°Ìâ
31£® ÏÂÃæµÄÎÄ·¨²úÉú0ºÍ1µÄ´®£¬¼´¶þ½øÖƵÄÕýÕûÊý£¬Çë¸ø³ö¾ö¶¨Ã¿¸ö¶þ½øÖÆÊýµÄÖµ£¨Ê®½øÖÆÐÎʽ£©µÄÓï·¨ÖÆµ¼¶¨Òå¡£
¡¾½â¡¿¶¨ÒåÖµÊôÐÔΪ.val£¬·Òë·½°¸ÈçÏ£º B ? B1 0 { B.val = B1.val ? 2 } B ? B1 1 { B.val = B1.val ? 2 + 1 } B ? 1 { B.val = 1 }
B ? 0 { B.val = 0 }
32£®°ÑËãÊõ±í´ïʽ?(a + b) ? (c + d) + (e+ f) ·Òë³ÉµÈ¼ÛµÄËÄԪʽÐòÁУ¨ÐòºÅ´Ó0¿ªÊ¼£©¡£ ¡¾½â¡¿
0£¨+£¬a, b ,T1£©
1£¨uminus£¬T1£¬-£¬T2£© 2£¨+£¬c, d , T3£© 3£¨*£¬T2£¬T3£¬T4£© 4£¨+£¬e£¬f£¬T5£© 5£¨+£¬T4£¬T5£¬T6£©
33£®ÉèÓÐÎÄ·¨G[S]:
S¡úa|£¨T£©|? T¡úT,S|S
ÊÔ¸ø³ö¾ä×Ó(a,a,a)µÄ×î×óÍÆµ¼¡£ ¡¾½â¡¿(1) (a,a,a)µÄ×î×óÍÆµ¼
S=>(T) =>(T,S) =>( T,S,S) =>( S,S,S) =>(a,S,S) =>(a,a,S) =>(a,a,a)
34£®ÒÑÖªÎÄ·¨£Ç£º S ¡ú ( L | a L ¡ú S , L | )
ÅжÏÊDz»ÊÇLL£¨1£©ÎÄ·¨£¬Èç¹ûÊÇÇë¹¹ÔìÎÄ·¨ £Ç µÄÔ¤²â·ÖÎö±í£¬Èç¹û²»ÊÇÇë˵Ã÷ÀíÓÉ¡£¡¾½â¡¿
1£©Çó¸÷·ÇÖÕ½á·ûµÄ FISRT ¼¯ºÍ FOLLOW ¼¯£º = { (, a ) FIRST(L) = { a }? FIRST(S) = { (, ), a } FOLLOW(S) = {, # }
FOLLOW(L) = FOLLOW(S) ={ , # } FIRST(( L)¡É{a}=¦µ FIRST(S , L)¡É{)}=¦µ ËùÒÔÊÇLL£¨1£©ÎÄ·¨
31
¡¶±àÒëÔÀí¡·¸´Ï°Ìâ
2£©Ô¤²â·ÖÎö±í£º S L
35£®ÎÄ·¨
S ? A a | b A c | d c | b d a A ? d
¹¹Ôìʶ±ð»îǰ׺µÄDFA¡£Çë¸ù¾ÝÕâ¸öDFAÀ´ÅжϸÃÎÄ·¨ÊDz»ÊÇSLR(1)ÎÄ·¨²¢ËµÃ÷ÀíÓÉ¡£ ¡¾½â¡¿ S¡¯ ? S . S¡¯ ? .S S
I1 S ? .A a S ? .b A c A a S ? A .a S ? A a . S ? .d c I2 I5 S ? .b d a A ? .d c S ? b A .c S ? b A c . A S ? b .A c b I0 I6 I9 S ? b .d a A ? .d d S ? b d .a I3 S ? b d a . a d A ? d . I10 S ? d .c I7 A ? d . c S ? d c . I4 I8 ( S¡ú ( L L¡ú S , L a S¡ú a L¡ú S , L , } L ¡ú ) # Follow(S)={#}
Follow(A)={a,c}
I4´æÔÚ³åÍ»ÇÒFollow(A)¡É{c}={ c} I7´æÔÚ³åÍ»ÇÒFollow(A)¡É{a}={ a} ËùÒÔ²»ÊÇSLR(1)ÎÄ·¨
36£®½«ÏÂͼËùʾµÄÈ·¶¨ÓÐÏÞ×Ô¶¯»ú(DFA)×îС»¯¡£ÆäÖУ¬XΪ³õ̬£¬YΪÖÕ̬¡£
aaXb21ba3abYb
¡¾½â¡¿ ÏÈ»®·ÖΪÖÕ̬¼¯{Y}ºÍ·ÇÖÕ̬¼¯I={X,1,2,3}
XÃæ¶ÔÊäÈë·ûºÅbʱÏÂһ״̬ÊôÓÚI£¬¶ø1,2,3Ãæ¶ÔÊäÈë·ûºÅbʱÏÂһ״̬ÊôÓÚ{Y}£¬¹Ê»®·ÖΪ{X}¡¢{1,2,3} ·ÇÖÕ̬2ºÍ·ÇÖÕ̬3Ãæ¶ÔÊäÈë·ûºÅaµÄÏÂһ״̬Ïàͬ£¬¶ø1²»Í¬£¬¼´×î¼ò״̬{X}¡¢{1}¡¢{2£¬3}¡¢{Y}¡£°´Ë³ÐòÖØÐÂÃüÃûΪ0¡¢1¡¢2¡¢3£¬ÔòµÃµ½×î¼òDFA£¬
32