【正文】 S8 11 S3 acc2 S2 S8 43 S2 S8 54 S6 S3 R25 R3 R3 R36 S2 S8 77 R1 S3 R1１８、對算術(shù)表達(dá)式文法Ｇ［Ｅ］ ；Ｅ→Ｅ＋Ｔ｜Ｔ　　　?。浴?Ｆ｜Ｆ　　?。啤ǎ牛黫(1) 構(gòu)造算符優(yōu)先關(guān)系表和ＬＲ分析表，并對Ｇ［Ｅ］進(jìn)行適合的改寫后構(gòu)造預(yù)測分析表。(2) 分別使用三種表對句子 i+i*i進(jìn)行分析。(3) 對于錯誤的輸入串：(i+(*i)和*+i)+(i*分別查看錯誤的發(fā)現(xiàn)時刻和輸入串出錯的位置。解：(1) 構(gòu)造算符優(yōu)先關(guān)系表，文法擴展后為E’→E E→E+T E→T T→T*F T→F F→(E) F→iFirstVT(E’)={} LastVT(E’)={}FirstVT(E)={+,*, (,i} LastVT(E)={ +,*, ),i }FirstVT(T)={ *, (,i } LastVT(T)={ *, ),i }FirstVT(F)={ (,i } LastVT(F)={ ),i }構(gòu)造算符優(yōu)先關(guān)系表：+ * （ ） i + ＞ ＜ ＜ ＞ ＜ ＞* ＞ ＞ ＜ ＞ ＜ ＞( ＜ ＜ ＜ ＝ ＜) ＞ ＞ ＞ ＞i ＞ ＞ ＞ ＞ ＜ ＜ ＜ ＜ ＝做 LR（0）分析,擴展后的文法為：（0）E’?E (1)E? E+T (2)E?T (3) T?T*F (4)T?F (5)F?(E) (6)F?iI0：E’?E E? E+T E?T T?T*F T?F F?(E) F?iI1: E’?E E?E+T（I1 產(chǎn)生移進(jìn)－規(guī)約沖突，但 Follow（E’ ） ∩{＋}=∮ 可以用 SLR（1）解決）I2：E?T T? T*F（I2 產(chǎn)生移進(jìn)－規(guī)約沖突，但 Follow（E） ∩{*}=∮ 可以用 SLR（1）解決）I3: T?FI4: F?(E) E?E+T E?T T?T*F T?F F?(E) F?iI5: F?iI6: E?E+T T?T*F T?F F?(E) F?iI7: T?T*F F?(E) F?i. . . .. . 學(xué)習(xí)好幫手I8: F?(E) E?E+TI9: E?E+T T?T*F （I2 產(chǎn)生移進(jìn)－規(guī)約沖突，但 Follow（E） ∩{*}=∮ 可以用 SLR（1）解決）I10: T?T*FI11: F?(E) 構(gòu)造 SLR（1）分析表 ACTION GOTO狀態(tài)+ * ( ) i E T F0 S4 S5 1 2 31 S6 acc2 R2 S7 R2 R23 R4 R44 S4 S5 8 2 35 R6 R6 R6 R66 S4 S5 9 37 S4 S5 108 S6 S119 R1 S7 R1 R110 R3 R3 R3 R311 R5 R5 R5 R5做 LL（1）分析：消除左遞歸，文法為：E?TE’E’?+TE’E’?εT?FT’T’?*FT’T’?εF?(E)F?i求 select集select (E?TE’)=first(TE’)=first(T)=first(FT’)=first(F)={(,i)select(E’?+TE’)={+}SELECT(E’?ε)=Follow(E’)=Follow(E)={,)}SELECT(T?FT’)= first(F)={(,i}Select(T’?*FT’)={*}Select(T’?ε)=follow(T’)={+,),}Select(F?(E))={(}Select(F?i)={i}. . . .. . 學(xué)習(xí)好幫手構(gòu)造預(yù)測分析表＋ * ( ) i E ?TE’ ?TE’E’ ?+TE’ ?ε ?εT ?FT’ ?FT’T’ ?ε ?*FT’ ?ε ?εF ?(E) ?i第八章while ab or cd and ef doif xy then t:=m+n 100：if ab goto 106101: goto 102102: if cd goto 104103: goto 111104: if ef goto 106105: goto 111106: if xy goto 108107: goto 100108: t1:=m+n109: L:=t1110: goto 100111:if AB then while AC do A:=AB else if D and F then A:=A+100100: if AB goto 102101 goto 107102 if AC goto 104103 goto 114104 t1:=AB105 A:=t1106 goto 102107 goto 114108 if D goto 110109 goto 114110 if F 112111 goto 114. . . .. . 學(xué)習(xí)好幫手112 t2:=A+100113 A:=t2114補充習(xí)題1．對下列各語言寫出它們的正規(guī)表達(dá)式和有限自動機（a） 字母表{a,b,c}上的串，其中第一個 a先于第一個 b解：我們關(guān)心的狀態(tài)是什么時候出現(xiàn)了第一個 a,可以設(shè)出現(xiàn)第一個 a后的狀態(tài)為 1,出現(xiàn)第一個 a之前的狀態(tài)為 0。必須保證在狀態(tài) 1之前不能出現(xiàn) b: c a,b,c ? 0 a 1轉(zhuǎn)換為正規(guī)式：c*a(a|b|c)*（b） 其中有偶數(shù)個 a的字母表{a,b,c}上的串解：我們關(guān)心的狀態(tài)是 a的個數(shù)的奇偶性，可以設(shè)定偶數(shù)個 a時的狀態(tài)是 0，奇數(shù)個 a的狀態(tài)是 1，我們要偶數(shù)個 a，因此 0狀態(tài)是終結(jié)狀態(tài)： b|c a b|c ? 0 1 a轉(zhuǎn)換為正規(guī)表達(dá)式：(b|c)*(a(b|c)*a)*（c） {0，1}上的串，該串看成二進(jìn)制是 4的倍數(shù)解：A=(0|1)*00（d） {0，1}上不含子串 011的串解：我們關(guān)心的狀態(tài)是出現(xiàn) 01時，這時只要保證 01后不能是 1即可： 1 0 00 0 1 1 21*0(0|10)*（e） {0，1}上的串有偶數(shù)個 0和奇數(shù)個 1解：我們關(guān)心的狀態(tài)是 0和 1的奇偶性，組合情況有 4個：0：偶數(shù)個 0，偶數(shù)個 11：偶數(shù)個 0，奇數(shù)個 1 ――終結(jié)狀態(tài)2: 奇數(shù)個 0，偶數(shù)個 1 3：奇數(shù)個 0，奇數(shù)個 1 1 ? 0 1 1 0 0 0 0 2 1 3 1正規(guī)表達(dá)式：(0(11)*0)*( 1 | 0(11)*10 )( 00 | 01(11)*10 | ( 1 | 01( 11 )* 0) (0 (11)* 0)* ( 1 | 0 (11)* 10) )*. . . .. . 學(xué)習(xí)好幫手2．試從文法 G[s] S?(L)|a L?L,S | S中消除左遞歸,并為之構(gòu)造一個遞歸預(yù)測分析器和 LL(1)分析表. 請說明句子(a,(a,a))在 LL(1)分析器中的動作.解：改寫為S?(L) | a L?SL’ L’?ε| ,SL’ 非終結(jié)符 是否 *?ε FIRST集 FOLLOW集S 否 {( , a} { , }L 否 {( , a) { )}L’ 是 { , ε} {) }SELECT(S?(L))={（ }SELECT(S?a)={a}SELECT(L?SL’)={(,a}SELECT(L’?ε)={ )}SELECT(L’?,SL’)={,}預(yù)測分析表：（ a , )S ?(L) ?aL ?SL’ ?SL’L’ ?,SL’ ?ε對符號串(a,(a,a))的分析過程步驟 分析棧 剩余輸入串 所用產(chǎn)生式1 S (a,(a,a)) S?(L)2 )L( (a,(a,a)) ( 匹配3 )L a,(a,a)) L?SL’4 )L’S a,(a,a)) S?a5 )L’a a,(a,a)) a 匹配6 )L’ ,(a,a)) L’?,SL’7 )L’S , ,(a,a)) ,匹配8 )L’S (a,a)) S?(L)9 )L’)L( (a,a)) ( 匹配10 )L’)L a,a)) L?SL’11 )L’)L’S a,a)) S?a12 )L’)L’a a,a)) a匹配13 )L’)L’ ,a)) L’?,SL’14 )L’)L’S, ,a)) , 匹配15 )L’)L’S a)) S?a. . . .. . 學(xué)習(xí)好幫手16 )L’)L’a a)) a匹配 17 )L’)L’ )) L’?ε18 )L’) )) )匹配19 )L’ ) L’?ε20 ) ) )匹配21 接受步驟 分析棧 剩余輸入串 所用產(chǎn)生式1 S (a,(a,a)) S?(L)2 )L( (a,(a,a)) ( 匹配3 )L a,(a,a)) L?SL’4 )L’S a,(a,a)) S?a5 )L,a a,(a,a)) a , 匹配6 )L (a,a)) L?SL’7 )L’S (a,a)) S?(L)8 )L’)L( (a,a)) ( 匹配9 )L’)L a,a)) L?SL’10 )L’)L’S a,a)) S?a11 )L’)L’a a,a)) a匹配12 )L’)L’ ,a)) L’?,SL’13 )L’)L’S, ,a)) , 匹配14 )L’)L’S a)) S?a15 )L’)L’a a)) a匹配 16 )L’)L’ )) L’?ε17 )L’) )) )匹配18 )L’ ) L’?ε19 ) ) )匹配20 接受3. 對于文法 G[bexpr] bexpr?bexpr or bterm | bterm bterm?bterm and bfactor | bfactor bfactor?not bfactor | (bfactor) | true | false構(gòu)造一個預(yù)測分析器解： bexpr：S bterm： A bfactor： B 原文法變?yōu)椋? S?S or A | A A?A and B | B B?not B | (B) | true | false 改寫為：. . . .. . 學(xué)習(xí)好幫手 S?AS’ S’?ε| or AS’ A?BA’ A’?ε| and BA’ B?not B | (B) | true | false非終結(jié)符 是否 *?ε FIRST集 FOLLOW集S 否 { not , ( , true , false }{}S’ 是 { or ε} {}A 否 { not , ( , true , false }{ , or}A’ 是 { and ε} { , or}B 否 {not , ( , true , false}{ , ) , and}SELECT(S?AS’)={ not , ( , true , false }SELECT(S’?ε)={}SELECT(S’?or A