【正文】 5S8S7365R46R27S5S9108R69S5S8S7101110R311R5（3）是LR(0)文法，其SLR(1)分析表如下：FOLLOW(S)={,a,b,c}ACTIONGOTOabcS0S3S211ACC2R3R3R3R33S3S244S3S255S3S6S276R1R1R1R17R2R2R2R2（4）因為I2中含有沖突項目，所以不是LR(0)文法，其SLR(1)分析表如下：FOLLOW(S)={}∩=φ(所以可以用SLR(1)規(guī)則解決沖突), FOLLOW(A)={b,}ACTIONGOTOabSA0S3121ACC2S4R13R3R34R2R2I4S→AbS→AaSAaI1I2I3I1S’ →SAA→（4）狀態(tài)項目集經(jīng)過的符號到達的狀態(tài)I0S’ →cSabcI7I3I6I2I6S→aSSbaSSbS→bS→aSSaSSSS→SSS→cScaI4I2I3I4S→aSaSSbS→SSbS→aI2S→caSSSS→SS→I11B→ccBcAA→ccBB→BA→caCAaI9I10I5I8B→bAA→I7B→caBAcbaI6I5I7I8I5I5A→abA→AB→I4S→cccAA→AS→cI1II1S’ →ScAS→（2）識別全部活前綴的DFA如下：狀態(tài)項目集經(jīng)過的符號到達的狀態(tài)I0S’ →I5S→aSbbS→aSaScS→bS→SbS→aabSaI1I2I1S’ →SaSbS→）狀態(tài)項目集經(jīng)過的符號到達的狀態(tài)I0S’ → 解：用Floyd方法對已知的優(yōu)先矩陣構(gòu)造的優(yōu)先函數(shù)為： zbMLa()f1567747g1654667 by是素短語，其中1x或者yn之一成立。 證：只要證u中不含有除自身以外的素短語。 （2）、（3）類似可證。 證：(1) 用反證法。 證明略。 證明略. 證：（1）對于a=…aU…是句型，必有ST*a(=…aU…) T+…ab….即在歸約過程中,b先于a被歸約,從而,a(2)的情況類似可以證明。 （2）的證明與（1）類似，略。 (1)證明：由設(shè)句型a =…Ua…中含a的短語不含U，即存在A，A=*ay,則a可歸約為a =…Ua…252。 將E→ET中的減號與F→P中的賦值運算符強制規(guī)定優(yōu)先關(guān)系； 文法為：E→E↑A | AA→A*T | A/T | TT→T+V | TV | VV→i | (E) 不失一般性，設(shè)其形為U→xABy,x,y∈V*,由于文法不含無用產(chǎn)生式，則必存在含有U的句型dUb，即存在推導ST*。 我們再進行一步推導，得STkdAbTdub, 其中，A→u是文法中的產(chǎn)生式，由定義，u中不含兩個非終結(jié)符相鄰情況，從而dub兩個非終結(jié)符相鄰情況。n=1時，STa,即S→a是文法的產(chǎn)生式，根據(jù)定義，它不含上述情況。,ir|n|b|cDW=T=L=a=:=。 解：為描述方便，用符號表示各非終結(jié)符：D=變量說明,L=變量表, V= 變量,T=類型，a=VAR,則消去V，并采用分層法改寫文法，得到：D→aW:T。反之，若xjxj+1...xi是句柄，由簡單優(yōu)先關(guān)系的定義，必滿足上述條件。即存在產(chǎn)生式 U→xjxj+1...xi設(shè) ST* aUb其中，aT*... xj1 ,bT* xi+1... 對于aUb可構(gòu)造一語法樹，并通過對其剪枝（歸約），直到U出現(xiàn)在句柄中。又因xj1xj可知xj1與xj不處于同一產(chǎn)生式，且xj是某右部的首符。 證明：設(shè)xjxj+1...xi是滿足條件xj1xj=xj+1=...=xi xi+1的最左子串。 提示：分析教材中給出的算法，選擇一種合適的表示給定文法的方法（盡量簡單），使得對文法的輸入比較簡單的同時(需要把輸入轉(zhuǎn)化為計算機語言表示，這種轉(zhuǎn)化應(yīng)該盡量簡單)，能夠比較簡單地構(gòu)造3個基本關(guān)系矩陣（=，LEAD和LAST）。o 首先消去無用產(chǎn)生式Z→E, Z→E+T SZTi()SZ==T=I(=)化簡后的文法是簡單優(yōu)先文法；(2)SRT()∧a,S=R=T(=)∧a,=是簡單優(yōu)先文法。 1）為方便書寫，記：布爾表達式為A，布爾因子為B，布爾二次量為C，布爾初等量為D，原文法可以簡化為： A→A∨B | B B→B∧C | CC→┐D | DD→(A) | true | false,顯然，文法含有左遞歸，消去后等價LL(1)文法為：A→BA’ A’ →∨BA’|ω B→CB’,B’ →∧CB’|ωC→┐D|DD→(A)| true|false(2)略 ： (1)消除左遞歸性,得：S→bZ11|aZ21A→bZ12|aZ22Z11→bZ11|εZ12→bZ12Z21→bZ11|aZ21Z22→bZ12|aZ22|ε消除無用產(chǎn)生式得：S→bZ11|aZ21Z11→bZ11|εZ21→bZ11|aZ21此文法已滿足LL(1)文法的三個條件，所以　G’[S]: S→bZ11|aZ21Z11→bZ11|εZ21→bZ11|aZ21(2) G’文法的各非終結(jié)符的FIRST 集和FOLLOW集：產(chǎn)生式FIRST 集FOLLOW集S→bZ11→aZ21{a}{}Z11→bZ11→ε{ε}{}Z21→bZ11→aZ21{a}{}LL(1)分析表為：abSaZ21bZ11Z11bZ11εZ21aZ21bZ11(2)此文法具有左遞歸性，據(jù)第5題結(jié)論，不是LL(1)的。 與LL（1）性質(zhì)矛盾。即存在著句子α有兩個不同的最左推導。 ：LL（1）文法的分析句子過程的每一步，永遠只有唯一的分析動作可進行。得證。Return。Ep:=true。Function Ep:boolean。E:=false。If V thenIf Ep then return。BeginSave。End。Restore。C:=true。Function C:boolean。S:=false。If C then return。If A then return。BeignSave。End。Restore。A:=true。Function A:boolean。P:=false。If next_token=”begin” thenIf S thenIf next_token=”end” then return。BeginSave。End。’ thenIf next_token=’s’ thenIf Y then return。Y=true。Function Y:boolean。X:=false。If next_token=’s’ thenIf Y then return?！?thenIf X then return。X:=true。Function X:boolean。P:=false。’ thenIf X thenIf next_token=”end” then return。P:=true。Function P:boolean。 ：以下Save表示save token_pointer value, Restore表示restore token_pointer value。 ： (1)S→(S)Z21|()Z21|[S]Z31|[]Z31A→(S)Z22|()Z22|[S]Z32|[]Z32B→(S)Z23|()Z23|[S]Z33|[]Z33Z11→ε|AZ11|BZ21Z12→AZ12|BZ22Z13→AZ13|BZ23Z21→Z11Z22→ε|Z12Z23→Z13Z31→Z21Z32→Z22Z33→ε|Z23(2)S→bZ11|aZ21A→bZ12|aZ22Z11→ε| AZ21Z12→AZ22Z21→SZ21Z22→ε|SZ22(3)S→(T)Z11 | aZ11 | Z11S→(T)Z12 | aZ12 | Z12Z11→ε| Z21Z12→Z22Z21→,SZ21Z22→ε|,SZ22第四章 習題解答}30 從略。}return。}if (c==3)printf( )。yytext[0]=39。yytext[i]。exit(0)。if (argc==2){if ((yyin=fopen(argv[1],r))==NULL){printf(can39。\t| +returnWHITE。 由’和’括住的，中間由兩個’’或者非’和\n組成的任意次的字符串。（3）識別\r\n和除數(shù)字字符外的任何字符。26（1）由{}括住的,中間由任意個非{組成的字符串, 如{},{}},{a},{defg}等等。 用來識別Dn的DFA至多需要2n＋1個狀態(tài)。return。default:break。case TE:i+=10。case TWENT: i+=20。else i+=2。c=yylex()。break。if (c==HUNDRE)i+=100。label。}}while ((c=yylex())!=0){switch(c){case ON:c=yylex()。t open %s\n,argv[1])。char tmp[30]。\nreturn0。HUNDREDreturn HUNDRE。TENreturn TE。TWOreturn TW。 23 下面舉一個能夠識別1,2,3,10,20,100的例子，讀者可以推而廣之。 21 從略。 G1: S=aA+B(1) B=cC+b(2)A=abS+bB (3)C=D(4)D=bB+d(5)把（4）（5）代入（2），得B＝c(bB+d)+b=cbB+cd+b 得B=(cb)*(cd|b),代入（3）得A=abS+b(cb)*(cd|b)把它打入（1）得S=a(abS+b(cb)*(cd|b))+ (cb)*(cd|b)=aabS+ab(cb)*(cd|b) + (cb)*(cd|b)=(aab)*( ab(cb)*(cd|b)| (cb)*(cd|b))G2:S=Aa+B (1)A=Cc+Bb (2)B=Bb+a(3)C=D+Bab(4)D=d(5)可得 D=dB=ab*C=ab*ab|bA=(ab*ab|b)c + ab*bS=(ab*ab|b)ca+ab*ba +ab*=(ab*ab|b)ca| ab*ba| ab*20(2)（rs）*r表示的正規(guī)式集是{ε,rs,rsrs,rsrsrs,…}r ={r,rsr,rsrsr,rsrsrsr,…}r(sr)* 表示的正規(guī)式集是r{ε,sr,srsr,srsrsr,…} ={ r,rsr,rsrsr,rsrsrsr,…}所以兩者等價。狀態(tài)轉(zhuǎn)換圖如圖