【正文】 =N then X：＝X＋1；Else X:= X 1。翻譯成四元式序列或P代碼。100（j,A,B,102）101(j,,,115)102(j,C,D,104)103(j,,,115)104(jND,M,,108)105(j,,,106)106（j,B,N,108）107(j,,,1114)108(j=,M,N,110)109(j,,,112)110(+,X,1,X)111(j,,,104)112(,X,1,X)113(j,,,114)114(j,,,100) 115四、為以下字符集編寫正規(guī)表達(dá)式，并構(gòu)造其Thompson結(jié)構(gòu)圖以及與之等價(jià)的最簡(jiǎn)DFA（寫出詳細(xì)的具體過(guò)程）：在字母表S = {0,1}上的包含偶數(shù)個(gè)0且含有任意數(shù)目1的所有字符串。（15分）正規(guī)表達(dá)式： (1*01*01*)* 最簡(jiǎn)DFA： 1 0 1 0 a b c S L R 1 S6 S4 2 5 3 2 Acc 3 R2 4 R4 R4 5 S7 R5 6 S6 S4 8 9 7 S12 S13 11 10 8 R5 R5 9 R3 R3 10 R1 11 R5 12 S12 S13 11 14 13 R4 14 R3 五、已知文法G： S 224。 LaR|R L224。 bR|c R224。L1） 判斷該文法是否為L(zhǎng)R(1)文法。2）若是則構(gòu)造文法G的LR(1)項(xiàng)目集規(guī)范族。3）若是則構(gòu)造文法G的LR(1)預(yù)測(cè)分析表。 （15分）因?yàn)闋顟B(tài)機(jī)中沒(méi)有沖突，所以是LR(1)文法。 LR(1)分析表如下： (1) S224。 LaR (2) S224。 R (3) L224。 bR (4) L224。 c (5) R224。 L 六、把下面程序段：for I:=1 setp 1 until N dowhile AB if CD then x:= C else X:= D 翻譯成四元式序列。（寫上注釋，15分）100（:=,1_,i）101(j,_,_,103)102(+,I,1,I)103(j,I,N,105)104(j,_,_,114)105(j,A,B,107)106(j,_,_,113)107(j,C,D,109)108(j,_,_,111)109(:=,C,_x)110(j,_,_,112)111(:=,D,_,x)112(j,_,_,105)113(j,_,_,102)114,四、構(gòu)造一個(gè)DFA，它接受∑={a,b}上的所有滿足下述條件的字符串，其條件是：字符串中的每個(gè)b后面都有a直接跟在右邊。要求： （1）寫出正則表達(dá)式； （2）由NFA構(gòu)造DFA；（3）DFA狀態(tài)最小化（寫出詳細(xì)的具體過(guò)程）（15分）正則表達(dá)式：(a*baa*)*最簡(jiǎn)DFA：四、構(gòu)造一個(gè)DFA，它接受∑={0,1}上的所有滿足下述條件的字符串，其條件是：字符串中的每個(gè)0后面都有1直接跟在右邊。要求： （1）寫出正則表達(dá)式； （2）由NFA構(gòu)造DFA；（3）DFA狀態(tài)最小化（寫出詳細(xì)的具體過(guò)程）（15分）正則表達(dá)式：(1*011*)* 最簡(jiǎn)DFA：1000111五、考慮以下的文法： （1）S→A　?。?）S→B　　（3）A→aAb　?。?）A→c　　（5）B→aBb　?。?）B→d　試構(gòu)造相應(yīng)的LR（0）項(xiàng)目集規(guī)范族及相應(yīng)的分析表。解答：六、把語(yǔ)句if a＞0 then a：＝a－1elseWhile　a＞0 ∨ b＜0　do　　 Begin　　　　 X：＝X＋1； End；翻譯成四元式序列。 （15分）100(j,a,0,102)101(j,_,_,104)102(,a,1,a)103(j,_,_,110)104(j,a,0,108)105(j,_,_,106)106(j,b,0,108)107(j,_,_,110) 108(+,x,1,x)109(j,_,_,104) while循環(huán)110四、詞法分析——確定性有窮自動(dòng)機(jī)為以下字符集編寫正規(guī)表達(dá)式，并構(gòu)造與之等價(jià)的最簡(jiǎn)DFA（寫出詳細(xì)的具體過(guò)程）： 在字母表{0,1}上的串，串中至少要包含兩個(gè)連續(xù)的0或兩個(gè)連續(xù)的1。（15分）（0|1）*（00|11）（0|1）* 0 0 1 0 1，0 1 1五、語(yǔ)法分析——自頂向下分析法 （20分）說(shuō)明如下文法是否是LL（1）文法，若不是，將其轉(zhuǎn)換為L(zhǎng)L（1）文法。最后給出該文法的LL（1）分析表。 G[A]： A 224。 B e B 224。 B b | a 文法中有左遞歸，不是LL(1)文法。 轉(zhuǎn)換為 G′ :A224。 B e B224。 a B′ B′224。b B′ | λ Predict(A224。 B e) ={ a } Predict(B224。 a B′) ={ a } Predict(B′224。b B′) ={ b } Predict(B′224。λ ) ={ e } LL(1)分析表: a b e A 224。 B e B 224。 a B′ B′ 224。 b B′224。λ六、構(gòu)造運(yùn)行時(shí)環(huán)境有如下一段C語(yǔ)言程序：(計(jì)算兩個(gè)非負(fù)整數(shù)的最大公約數(shù))include int x,y 。 int gcd ( int u , int v){ if (v==0) return u 。 else return gcd(v , u%v)}main(){ scanf(“%d%d”,amp。x,amp。y)。 printf(“%d\n”,gcd(x,y))。 return 0。}當(dāng)輸入x,y分別為20，10時(shí)，最后一次調(diào)用gcd()時(shí)的運(yùn)行時(shí)環(huán)境。(10分)當(dāng)輸入20和10時(shí)，main就初始化調(diào)用gdc（20，10）。這個(gè)調(diào)用導(dǎo)致了另一個(gè)遞歸調(diào)用gdc（10，0），它將返回值10。運(yùn)行時(shí)環(huán)境示意圖如下：abbbaaa五、已知文法G： （15分） E224。TE’E’ 224。 +E |ε T 224。 F T’ T’ 224。T|ε F224。PF’ F’ 224。*F’ |ε P224。(E) | ^|a |b1）求文法G中每個(gè)非終結(jié)符的First集和Follow集。2）證明該文法G是LL(1)文法。3）構(gòu)造文法G的預(yù)測(cè)分析表。（15分）2） First(E)=First(T)=First(F)=First(P)+{(,^,a,b)First(T’)={(,^,a,b,ε)First(E’)={+, ε}First(F’)={*, ε}Follow(P)={(, ^,a,b,),+}Follow(F’)={(, ^,a,b,),+}Follow(F)={(, ^,a,b,),+}Follow(E)= {,}}Follow(E’)= {,}}Follow(T)= {,),+}Follow(T’)= {,},+}2)判定該文法是否是LL(1)文法的充要條件是對(duì)于G的每個(gè)非終結(jié)符A的任何兩個(gè)不同產(chǎn)生式Aα|β，有下述條件成立： First(α)∩ First(β)=Ф 若β=*ε，則First(α)Follow(A)=Ф顯然，（1）所求的First集合和Follow集合滿足要求，因此該文法為L(zhǎng)L(1)文法。+*（）ab^EETE’ETE’ETE’ETE’E’E’+EE’εE’εTTFT’TFT’TFT’TFT’T’T’εT’TT’εT’TT’TT’TT’εFFPF’FPF’FPF’FPF’F’F’εF’*F’F’εF’εF’εF’εF’εF’εPP(E)PaPbP^六、把語(yǔ)句if a＞0 thenWhile　a＞0 ∨ b＜0　do　　 Begin　　　　 X：＝X＋1；　　　　 End；else b：＝b＋1翻譯成四元式序列。 （15分）100(j,a,0,102)101(j,_,_,108)102(j,a,0,106)103(j,_,_,104)104(j,b,0,106)105(j,_,_,108)106(+,x,1,x) 107(j,_,_,102) while循環(huán)108(j,_,_,110)109(+,b,1,b)110四、詞法分析——確定性有窮自動(dòng)機(jī)為以下字符集編寫正規(guī)表達(dá)式，并構(gòu)造與之等價(jià)的最簡(jiǎn)DFA（寫出詳細(xì)的具體過(guò)程）： 在字母表{0,1}上的串，串中至少要包含兩個(gè)連續(xù)的0或兩個(gè)連續(xù)的1。（15分）（0|1）*（00|11）（0|1）* 0 0 1 0 1，0 1 1五、語(yǔ)法分析——自頂向下分析法 （20分）說(shuō)明如下文法是否是LL（1）文法，若不是，將其轉(zhuǎn)換為L(zhǎng)L（1）文法。最后給出該文法的LL（1）分析表。 G[A]： A 224。 B e B 224。 B b | a 文法中有左遞歸，不是LL(1)文法。 轉(zhuǎn)換為 G′ :A224。 B e B224。 a B′ B′224。b B′ | λ Predict(A224。 B e) ={ a } Predict(B224。 a B′) ={ a } Predict(B′224。b B′) ={ b } Predict(B′224。λ ) ={ e } LL(1)分析表: a b e A 224。 B e B 224。 a B′ B′ 224。 b B′224。λ六、構(gòu)造運(yùn)行時(shí)環(huán)境有如下一段C語(yǔ)言程序：(計(jì)算兩個(gè)非負(fù)整數(shù)的最大公約數(shù))include int x,y 。 int gcd