【正文】 7747g1654667 by是素短語(yǔ)，其中1x或者yn之一成立。 證：只要證u中不含有除自身以外的素短語(yǔ)。 （2）、（3）類(lèi)似可證。 證：(1) 用反證法。 證明略。 證明略. 證：（1）對(duì)于a=…aU…是句型，必有ST*a(=…aU…) T+…ab….即在歸約過(guò)程中,b先于a被歸約,從而,a(2)的情況類(lèi)似可以證明。 （2）的證明與（1）類(lèi)似，略。 (1)證明：由設(shè)句型a =…Ua…中含a的短語(yǔ)不含U，即存在A，A=*ay,則a可歸約為a =…Ua…252。 將E→ET中的減號(hào)與F→P中的賦值運(yùn)算符強(qiáng)制規(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*,由于文法不含無(wú)用產(chǎn)生式，則必存在含有U的句型dUb，即存在推導(dǎo)ST*。 我們?cè)龠M(jìn)行一步推導(dǎo)，得STkdAbTdub, 其中，A→u是文法中的產(chǎn)生式，由定義，u中不含兩個(gè)非終結(jié)符相鄰情況，從而dub兩個(gè)非終結(jié)符相鄰情況。n=1時(shí)，STa,即S→a是文法的產(chǎn)生式，根據(jù)定義，它不含上述情況。,ir|n|b|cDW=T=L=a=:=。 解：為描述方便，用符號(hào)表示各非終結(jié)符：D=變量說(shuō)明,L=變量表, V= 變量,T=類(lèi)型，a=VAR,則消去V，并采用分層法改寫(xiě)文法，得到：D→aW:T。反之，若xjxj+1...xi是句柄，由簡(jiǎn)單優(yōu)先關(guān)系的定義，必滿(mǎn)足上述條件。即存在產(chǎn)生式 U→xjxj+1...xi設(shè) ST* aUb其中，aT*... xj1 ,bT* xi+1... 對(duì)于aUb可構(gòu)造一語(yǔ)法樹(shù)，并通過(guò)對(duì)其剪枝（歸約），直到U出現(xiàn)在句柄中。又因xj1xj可知xj1與xj不處于同一產(chǎn)生式，且xj是某右部的首符。 證明：設(shè)xjxj+1...xi是滿(mǎn)足條件xj1xj=xj+1=...=xi xi+1的最左子串。 提示：分析教材中給出的算法，選擇一種合適的表示給定文法的方法（盡量簡(jiǎn)單），使得對(duì)文法的輸入比較簡(jiǎn)單的同時(shí)(需要把輸入轉(zhuǎn)化為計(jì)算機(jī)語(yǔ)言表示，這種轉(zhuǎn)化應(yīng)該盡量簡(jiǎn)單)，能夠比較簡(jiǎn)單地構(gòu)造3個(gè)基本關(guān)系矩陣（=，LEAD和LAST）。o 首先消去無(wú)用產(chǎn)生式Z→E, Z→E+T SZTi()SZ==T=I(=)化簡(jiǎn)后的文法是簡(jiǎn)單優(yōu)先文法；(2)SRT()∧a,S=R=T(=)∧a,=是簡(jiǎn)單優(yōu)先文法。 1）為方便書(shū)寫(xiě)，記：布爾表達(dá)式為A，布爾因子為B，布爾二次量為C，布爾初等量為D，原文法可以簡(jiǎn)化為： A→A∨B | B B→B∧C | CC→┐D | DD→(A) | true | false,顯然，文法含有左遞歸，消去后等價(jià)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|ε消除無(wú)用產(chǎn)生式得：S→bZ11|aZ21Z11→bZ11|εZ21→bZ11|aZ21此文法已滿(mǎn)足LL(1)文法的三個(gè)條件，所以　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ì)矛盾。即存在著句子α有兩個(gè)不同的最左推導(dǎo)。 ：LL（1）文法的分析句子過(guò)程的每一步，永遠(yuǎn)只有唯一的分析動(dòng)作可進(jìn)行。得證。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第四章 習(xí)題解答}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。 由’和’括住的，中間由兩個(gè)’’或者非’和\n組成的任意次的字符串。（3）識(shí)別\r\n和除數(shù)字字符外的任何字符。26（1）由{}括住的,中間由任意個(gè)非{組成的字符串, 如{},{}},{a},{defg}等等。 用來(lái)識(shí)別Dn的DFA至多需要2n＋1個(gè)狀態(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 下面舉一個(gè)能夠識(shí)別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,…}所以?xún)烧叩葍r(jià)。狀態(tài)轉(zhuǎn)換圖如圖15從略。11將右線性文法化為左線性文法的算法：o （1）對(duì)于G中每一個(gè)形如A→aB的產(chǎn)生式且A是開(kāi)始符，將其變?yōu)锽→a,否則若A不是開(kāi)始符，B→Aa。5 6 根據(jù)文法知其產(chǎn)生的語(yǔ)言是L={ambnci| m,n,i≧1}可以構(gòu)造如下的文法VN={S,A,B,C}, VT={a,b,c}P={ S →aA, A→aA, A→bB, B→bB, B→cC, C→cC, C→c}其狀態(tài)轉(zhuǎn)換圖如下:7 (1) 其對(duì)應(yīng)的右線性文法是:A →0D, B→0A,B→1C,C→1|1F,C→1|0A,F→0|0E|1A,D→0B|1C,E→1C|0B(2) 最短輸入串011(3) 任意接受的四個(gè)串011,0110,0011,000011(4) 任意以1打頭的串.8 從略。 G1的產(chǎn)生式中 A→aB, 則B也有B→bC ,C→cD …. 所以有 A →abc…B’,a,b,c…∈VT,B’∈VN所以與G等價(jià)。[] |[S]（3）消除后的產(chǎn)生式如下：E→E+T | T*F | (E) | P↑F | iT→T*F | (E) | P↑F | i F→P↑F | (E) | i P→(E) | i第三章 習(xí)題解答最右推導(dǎo)：E TT=F=FP↑T FE↑T FET+↑T FEF+↑T FEP+↑T FEi+↑TFTi+↑T FTF*i+↑TFTP*i+↑T FTi*i+↑TFFi*i+↑T FPi*i+↑TFii*i+↑T Pii*i+↑Tiii*i+↑：充分性：當(dāng)前文法下的每一符號(hào)串僅有一個(gè)句柄和一個(gè)句柄產(chǎn)生式T對(duì)當(dāng)前符號(hào)串有唯一的最左歸約T對(duì)每一步推導(dǎo)都有唯一的最右推導(dǎo)T有唯一的語(yǔ)法樹(shù)。對(duì)應(yīng)的語(yǔ)法樹(shù)為：全部的短語(yǔ)：第一個(gè)a (a1)是句子bbaacb相對(duì)于非終結(jié)符A (A1) (產(chǎn)生式A?a）的短語(yǔ)（直接短語(yǔ)）；b1a1是句子bbaacb相對(duì)于非終結(jié)符A2的短語(yǔ)；b2b1a1是句子bbaacb相對(duì)于非終結(jié)符A3的短語(yǔ)；c是句子bbaacb相對(duì)于非終結(jié)符S1（產(chǎn)生式S?c）的短語(yǔ)（直接短語(yǔ)）；a2cb3是句子bbaacb相對(duì)于非終結(jié)符B的短語(yǔ)；b2b1a1a2cb3是句子bbaacb相對(duì)于非終結(jié)符S2的短語(yǔ)；注：符號(hào)的下標(biāo)是為了描述方便加上去的。：因?yàn)榇嬖诰渥樱篴bc，它對(duì)應(yīng)有兩個(gè)語(yǔ)法樹(shù)（或最右推導(dǎo)）：STABTAbcTabcSTDCTDcTabc所以，本文法具有二義性。得證；（2）同（1），假設(shè)：β的首符號(hào)為非終結(jié)符時(shí)，α首符號(hào)為終結(jié)符。即設(shè)：α=aω；β=Aω’且 α=*β。：(1)用反證法。即n=k+1時(shí)亦成立。存在βi ：i=1,2,..,k，b39。αk+1可推導(dǎo)出b的一個(gè)后綴=b(不妨稱(chēng)為b k+1)。：用歸納法于n，n=1時(shí)，結(jié)論顯然成立。（4）aacabcbcccaacdca不是文法G[S]中的句子因?yàn)榻K結(jié)符d后必然要跟終