【正文】 {S3}=q3 (2) 記{S}=q0 {Z}=q1 {U R}=q2 {S X}=q3 {Y U R}=q4 {X S U}=q5 {Y U R Z}=q6 {Z S}=q714（1）從略(2)化簡后S0和S1作為一個狀態(tài)，S5和S6作為一個狀態(tài)。 (1) r*表示的正規(guī)式集是{ε,r,rr,rrr,…} (ε|r)*表示的正規(guī)式集是{ε, εε,…}∪{r,rr,rrr,…}={ε,r,rr,rrr,…}ε|rr*表示的正規(guī)式集是{ε,r,rr,rrr,…}(r*)*=r*={ε,r,rr,rrr,…}所以四者是等價的。 識別此語言的正規(guī)式是S=’LABEL’d(d|,d)*。22 構(gòu)造NFA其余從略。THREEreturn THRE。 +|\treturn WHITE。if (argc==2){if ((yyin=fopen(argv[1],r))==NULL){printf(can39。if (c==0) goto {i+=1。else i+=1。if (c==HUNDRE)i+=200。break。}}/*while*/label: printf(%d\n,i)。 此正規(guī)式的長度是2n （2）匹配一行僅由一個大寫字母和一個數(shù)字組成的串，如A1,F8,Z2等。如’’’’, ‘a(chǎn)’,’bb’,’def’，’’’’’’等等 27O[Xx][09]*[afAF]*|[09]+|(\’([azAZ]|\\[Xx][07][07afAF]|\\0[01][07][07]|\\[az])\’)28^[azAZ_]+[09]*[azAZ_]*29 參考程序如下：%{include include include define UPPER2define WHITE3%}upper[AZ]%%{upper}+returnUPPER。t open %s\n,argv[1])。i++)printf(%c,tolower(yytext[i]))。else printf(%s,yytext)。 ： SAbB1,(表示第1步，,以下同)CAbbB2,edAbbB3,edCAbbB4,ededAbbbB5,edaAbbbB5， (不符合，改寫第5步，)edBfbbB4,edCSdfbbB5,ededSdfbbB6,edaSdfbbB6,eddfbbB5,eddfbbCSd6,eddfbbedSd7,eddfbbaSd7,eddfbbd6,Begin Save。Restore。BeginSave。Restore。End。If next_token=’。(2)消去文法左遞歸，并記為：P→begin S endS→A|CA→V:=EC→ if E then SE→VE’E’ →+VE’|εV→IFunction P:boolean。Restore。BeignSave。A:=flase。S:=true。Restore。BeginSave。C:=false。E:=true。End。If next_token=’+’ thenIf V thenIf E’ then return。 ： 從而可知，用LL（1）方法進(jìn)行句子α的分析過程中的某步中，存在兩種不同的產(chǎn)生式替換，且均能正確進(jìn)行語法分析，即LL（1）分析動作存在不確定性。 ： (1)D產(chǎn)生式兩個候選式fD和f的first集交集不為空，所以不是LL(1)的。 ： (1)產(chǎn)生式first集follow集S→SaB→bB{,a,c}A→S→a{a}{c}B→Ac{a,b}{,a,c}(2)將S→SaB | bB改寫為S→bBS’,S’ →aBS’|ω,可驗(yàn)證，新文法是LL(1)的。 證：若LL（1）文法G有形如B→aAAb的產(chǎn)生式，且AT+ε及AT*ag,根據(jù)FIRST集FOLLOW集的構(gòu)造算法可知，F(xiàn)IRST(A)中一切非ε加到FOLLOW(A)中，則a∈FOLLOW(A)；又因?yàn)閍∈FIRST(ag),所以兩集合相交非空，因此，G不是LL(1)文法；與前提矛盾，假設(shè)不成立，得證。(3) SR(a,)S=R(=a,=)是簡單優(yōu)先文法。 同理，xi為某產(chǎn)生式的尾符號。 ,=ir|n|b|c是簡單優(yōu)先文法。設(shè)n=k時，上述結(jié)論成立，且設(shè)STkdAb，由歸納假設(shè)，A兩側(cè)必為終結(jié)符。 證：由于G不是算符文法，G中至少有一個產(chǎn)生式，其右部含有兩個非終結(jié)符相鄰的情況。 解： （1）構(gòu)造算符優(yōu)先矩陣：*（）i*(=)I（2）在（，）、（，*）和（*，）處有多重定義元素，不是算符優(yōu)先文法；（3）改寫方法：*…UA…=b，b是G的一個句型，這與G是算符文法矛盾，所以，a中含有a的短語必含U。 提示：根據(jù)27題的結(jié)論，只要證u是句型α的短語，根據(jù)=關(guān)系的定義容易知道u是句型α的素短語。 證：設(shè)不能含有素短語，則只能是含有短語（不能含有終結(jié)符號），則該短語只能含有一個非終結(jié)符號，否則不符合算符文法定義，得證。 解： （1）優(yōu)先矩陣如下：[]a[=]a（2）用Bell方法求優(yōu)先函數(shù)的過程如下：[]af5751g5561（3）顯然，文法不是算符優(yōu)先文法, 所以不能線性化。 解： （1）識別全部活前綴的DFA如下：（以表格的形式來表示，很容易可以轉(zhuǎn)化為圖的形式，本章中其余的題目也是采用這種形式表示。aScS→ScS→aabSabI3I2I4I3S→aSI6S→aScccBSccBA→BA→ccAA→cBA→cI9B→ccbA→所求的LR(0)項(xiàng)目規(guī)范族C={I0,I1,…,I11}（3）狀態(tài)項(xiàng)目集經(jīng)過的符號到達(dá)的狀態(tài)I0S’ →cScaI1I2I3I1S’ →SSSSS→SbS→aScScaI5I2I3I5S→aSSaSSSS→SS→I2S→A(SRS→(SRS→(SRS→I6R→, I8R→,SLR(0)分析表如下：ACTIONGOTOa(),SR0S3S211ACC2S3S243R2R2R2R2R24S3S2S7S655R1R1R1R1R16S3S287R4R4R4R4R48S7S699R3R3R3R3R3可見是LR(0)文法。SabS→RR→bRRSabI4I5I6I2I3S→SaabaI3I6R→aab },follow(R)={a},follow(R) ∩{a}={a},所以SLR(1)規(guī)則不能解決沖突，從而該文法不是SLR(1)文法。BAB→aSABS→aAA→ABA→r2I7A→abABabI10I8I7I4I8A→Br3I11S→aSABaSbS→SBS→aabSbaI4I5I2I3S→babSabI6I2I3I4S→aSr1I8S→bSaaAS→cAdA→BcI6I7r6I4S→aAAcI8I5r4I6S→bBBcI9I7r6I8A→cAddI12I12B→cBddD, q5→S end, q5→S。q3q2→begin Dq4→R1I3q1→q3DI6I5q3→beginS。 q5q5DSI10I11I9I7q3→beginq5q5end。Dq5q5→q5, q2→ε,q3→q3。ACCI2q1→beginq2q2I3R3I3(沖突項(xiàng)目)Q1→beginq2q3。q3Ddq4SI4I10I5I6R7I4q1→beginq2q3R5I6q4→Sq4q4→R4I10q2→q2dR2因?yàn)閒ollow(q4)={end,}，故沖突項(xiàng)目可以通過SLR(1)規(guī)則來解決，從而文法為SLR(1)文法。SS→AScA→A→SdA→aS→I5A→aAScA→AAdS→bbI2I9S→cAAAdS→SbA→ScS→AbA→aSAabcdI11I10I5I4I3I13I11A→ASI14S→cAdBAA→I2S→ABAB→aB,a,bB→,a,b相應(yīng)的LR(1)分析表為：STATEACTIONGOTOabSAB0S4S5R31231ACC2R23S4S5R3634S4S575R5R5R56R27R4R4R4用 LR(1)分析表對輸入符號串a(chǎn)bab的分析過程：步驟狀態(tài)棧中符號余留符號分析動作下一狀態(tài)10ababS44204ababS553045ababR574047aBabR43503BabS446034BabS5570345BabR4780347BaBR439033BBR36100336BBAR2611036BAR211201AaccAB,a,bA→B,a,bB→,a,bI5B→a,a,b相應(yīng)的LR(1)分析表為：STATEACTIONGOTOabSAB0R3R3R3121Acc2S5S4R13R2R2R24R5R5R55S5S466R4R4R4表中沒有多從定義的元素，所以文法是LR(1)文法。T/+T→+T/++I2I2E→E+/TI4T→aT)/+T→)/+E→ET)/+T→/+I11E→E++/)I13E→E+T+/)LALR(1)分析：（合并同心集）狀態(tài)項(xiàng)目集經(jīng)過的符號到達(dá)的狀態(tài)I0E’ →(E)/+T→T/+/）T→+/)/I5/I8T→((E)+/)T→+T+/)+)I2/I11I10/I15I10/I15T→(E) E+E,+,*E→+E,+,*E→EE+E,+,*E→E+E,+,*E→+E,+,*E→E*E,+,*+*I3I4依據(jù)以上圖求出該文法的LR(1)分析表知道由于項(xiàng)目I5,I6導(dǎo)致了有多重定義的元素，所以不是LR(1)文法。例如，假設(shè)表達(dá)式運(yùn)算滿足左結(jié)合律（即a+b+c=(a+b)+c而不是右結(jié)合律：