【正文】 必須保證在狀態(tài) 1之前不能出現(xiàn) b: c a,b,c ? 0 a 1轉(zhuǎn)換為正規(guī)式：c*a(a|b|c)*（b） 其中有偶數(shù)個(gè) a的字母表{a,b,c}上的串解：我們關(guān)心的狀態(tài)是 a的個(gè)數(shù)的奇偶性，可以設(shè)定偶數(shù)個(gè) a時(shí)的狀態(tài)是 0，奇數(shù)個(gè) a的狀態(tài)是 1，我們要偶數(shù)個(gè) 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時(shí)，這時(shí)只要保證 01后不能是 1即可： 1 0 00 0 1 1 21*0(0|10)*（e） {0，1}上的串有偶數(shù)個(gè) 0和奇數(shù)個(gè) 1解：我們關(guān)心的狀態(tài)是 0和 1的奇偶性，組合情況有 4個(gè)：0：偶數(shù)個(gè) 0，偶數(shù)個(gè) 11：偶數(shù)個(gè) 0，奇數(shù)個(gè) 1 ――終結(jié)狀態(tài)2: 奇數(shù)個(gè) 0，偶數(shù)個(gè) 1 3：奇數(shù)個(gè) 0，奇數(shù)個(gè) 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)造一個(gè)遞歸預(yù)測(cè)分析器和 LL(1)分析表. 請(qǐng)說明句子(a,(a,a))在 LL(1)分析器中的動(dòng)作.解：改寫為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ù)測(cè)分析表：（ a , )S ?(L) ?aL ?SL’ ?SL’L’ ?,SL’ ?ε對(duì)符號(hào)串(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. 對(duì)于文法 G[bexpr] bexpr?bexpr or bterm | bterm bterm?bterm and bfactor | bfactor bfactor?not bfactor | (bfactor) | true | false構(gòu)造一個(gè)預(yù)測(cè)分析器解： 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 AS。I11: F?(E) T?T) E?E(E) F?iI7: T?T*F F?T T?iI5: F?iF F?T T?E) E?*F（I2 產(chǎn)生移進(jìn)－規(guī)約沖突，但 Follow（E） ∩{*}=∮ 可以用 SLR（1）解決）I3: T?F+T（I1 產(chǎn)生移進(jìn)－規(guī)約沖突，但 Follow（E’ ） ∩{＋}=∮ 可以用 SLR（1）解決）I2：E?TiI1: E’?EF F?T T?E E? ＝ ＜＞ ＜＞ ＞i ＞ ) ＝ ＜ ＞ ＞ ＜(3) 對(duì)于錯(cuò)誤的輸入串：(i+(*i)和*+i)+(i*分別查看錯(cuò)誤的發(fā)現(xiàn)時(shí)刻和輸入串出錯(cuò)的位置。根據(jù)算符優(yōu)先關(guān)系構(gòu)造該文法的 LR分析表：. . . .. . 學(xué)習(xí)好幫手ACTION GOTO狀態(tài)Do or ； act S0 S2 S8 11 S3 acc2 S2 S8 43 S2 S8 54 S6 S3 R25 R3 R3 R36 S2 S8 77 R1 S3 R1１８、對(duì)算術(shù)表達(dá)式文法Ｇ［Ｅ］ ；Ｅ→Ｅ＋Ｔ｜Ｔ　　　?。浴?Ｆ｜Ｆ　　?。啤ǎ牛黫(1) 構(gòu)造算符優(yōu)先關(guān)系表和ＬＲ分析表，并對(duì)Ｇ［Ｅ］進(jìn)行適合的改寫后構(gòu)造預(yù)測(cè)分析表。 歸約項(xiàng)目 Follow(s)={,or,；}S→S 歸約項(xiàng)目 Follow(s)={,or,；}S→SS 移進(jìn)項(xiàng)目 Follow(s)∩{；}≠∮ 在 I5中含有項(xiàng)目： S→S。 歸約項(xiàng)目 Follow(s)={,or,；}S→do S 歸約項(xiàng)目 Follow(S’)={}S→S S→SSS→do SS→SS→S→SSI5：S→S。or SS→do SSS→do SS→SS→SI3：S→S。actI1：S’→ SS。do S or SS→ S or SS→doactI8：S→actS。do S or SS→S (4)S→act 構(gòu)造該文法的活前綴 DFA：I0：S’→優(yōu)先性大于 or；請(qǐng)構(gòu)造該文法的 LR分析表。服從左結(jié)合；c) 。(2) 該文法是 LR（0）嗎？是 SLR（1）嗎？說明理由。b , a/b/. . . .. . 學(xué)習(xí)好幫手12 01 S acc1給定文法：S→do S or S|do S|S。 A ，a/b/A→ ，baAaSAbAabI1：S’→ S , a/b/I6：A→a AaA ，a/b/A→AS ，S→b , a/b/I2：S→A ，A→S ，S→所以該文法是 LR（1）文法。I8：A→bBaI9：B→aAbbA→AaI6：B→aAbBaI7：A→AbAbA→AcB→aaAbI1：S’→ SaAcB→bI3：A→bbBaI2：S→AAA→解： （0）S’→S (1)S→AS (2) S→ξ (3)A→aA (4)A→b證明： 構(gòu)造該文法的活前綴 DFA：SI0：S’→ 規(guī)約項(xiàng) Follow(A)={b,c,} Follow(B) ∩ Follow(A)= ∮文法的沖突項(xiàng)可以用 SLR（1）文法來解決，所以該文法是 SLR（1）文法，不是 LR（0）文法。bBa 移進(jìn)項(xiàng) Follow(B)∩=∮在 I9 項(xiàng)目集中有 B?aAbb 移進(jìn)項(xiàng) Follow(S)∩=∮在 I4項(xiàng)目集中含有：B→aS→A A→Ab|bBa B→aAc|a|aAb證明：（0）S’→ S (1)S→A (2)A→Ab (3)A→bBa (4)B→aAc (5) B→a (6)B→aAb構(gòu)造該文法的活前綴 DFA：. . . .. . 學(xué)習(xí)好幫手在 I2項(xiàng)目集中含有：S→A所以該文法是 SLR（1）文法，也是 LALR（1）文法，LR（1）文法。c. . . .. . 學(xué)習(xí)好幫手 產(chǎn)生移進(jìn)—規(guī)約喝規(guī)約－規(guī)約沖突 Follow(U)={d,e} Follow(T)={a,b} 可以用 SLR（1）的方法解決I9: S?UTa T?Sa S?TI6:T?ScdI3: S?I4: U?eS T?US U?UTa S?Ta U?U T?SSc T?e T?Tb U?S S? （2） 構(gòu)造相應(yīng)的分析表。endE→SS。d E→end構(gòu)造 LR（0）分析表：ACTION GOTO狀態(tài) begin ； d S end A B C D E0 S5 1 2 3 41 acc2 R1 R1 R1 R1 R1 R13 R2 R2 R2 R2 R2 R24 S65 S9 S7 8I6：B→D；I9：D→begin dI3：A→CI1：A’→ AI11：D→D； dSendE→EI13：E→S；S endE→ ED→begin；ED→DD。begin ED→CB→A A→d