【文章內(nèi)容簡(jiǎn)介】 Z21aZ21bZ11 ： (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)的。 ： 1）為方便書寫，記：布爾表達(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)略 證：若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è)不成立，得證。 解： (1)SA(a)bS==A==(==a=)b不是簡(jiǎn)單優(yōu)先文法。(2)SRT()∧a,S=R=T(=)∧a,=是簡(jiǎn)單優(yōu)先文法。(3) SR(a,)S=R(=a,=)是簡(jiǎn)單優(yōu)先文法。o 首先消去無(wú)用產(chǎn)生式Z→E, Z→E+T SZTi()SZ==T=I(=)化簡(jiǎn)后的文法是簡(jiǎn)單優(yōu)先文法； 解： SA/ASA===/aA和/之間同時(shí)有關(guān)系=和,所以不是簡(jiǎn)單優(yōu)先文法； 提示：分析教材中給出的算法，選擇一種合適的表示給定文法的方法（盡量簡(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）。 證明：設(shè)xjxj+1...xi是滿足條件xj1xj=xj+1=...=xi xi+1的最左子串。由=關(guān)系的定義，可知xjxj+1...xi必出現(xiàn)在某產(chǎn)生式的右部中。又因xj1xj可知xj1與xj不處于同一產(chǎn)生式，且xj是某右部的首符。同理，xi為某產(chǎn)生式的尾符號(hào)。即存在產(chǎn)生式 U→xjxj+1...xi設(shè) ST* aUb其中，aT*... xj1 ,bT* xi+1... 對(duì)于aUb可構(gòu)造一語(yǔ)法樹，并通過(guò)對(duì)其剪枝（歸約），直到U出現(xiàn)在句柄中。從而xjxj+1...xi必為句柄。反之，若xjxj+1...xi是句柄，由簡(jiǎn)單優(yōu)先關(guān)系的定義，必滿足上述條件。 解：為描述方便，用符號(hào)表示各非終結(jié)符：D=變量說(shuō)明,L=變量表, V= 變量,T=類型，a=VAR,則消去V，并采用分層法改寫文法，得到：D→aW:T。W→LL→L,i|iT→r|n|b|c 其全部簡(jiǎn)單優(yōu)先關(guān)系是：DWTLa:。,ir|n|b|cDW=T=L=a=:=。,=ir|n|b|c是簡(jiǎn)單優(yōu)先文法。 證：設(shè)STna,我們對(duì)n用歸納法，證明a不含兩個(gè)非終結(jié)符相鄰情況。n=1時(shí)，STa,即S→a是文法的產(chǎn)生式，根據(jù)定義，它不含上述情況。設(shè)n=k時(shí)，上述結(jié)論成立，且設(shè)STkdAb，由歸納假設(shè)，A兩側(cè)必為終結(jié)符。我們?cè)龠M(jìn)行一步推導(dǎo)，得STkdAbTdub, 其中，A→u是文法中的產(chǎn)生式，由定義，u中不含兩個(gè)非終結(jié)符相鄰情況，從而dub兩個(gè)非終結(jié)符相鄰情況。得證。 證：由于G不是算符文法，G中至少有一個(gè)產(chǎn)生式，其右部含有兩個(gè)非終結(jié)符相鄰的情況。不失一般性，設(shè)其形為U→xABy,x,y∈V*,由于文法不含無(wú)用產(chǎn)生式，則必存在含有U的句型dUb，即存在推導(dǎo)ST*。 文法為：E→E↑A | AA→A*T | A/T | TT→T+V | TV | VV→i | (E) 解： （1）構(gòu)造算符優(yōu)先矩陣：*（）i*(=)I（2）在（，）、（，*）和（*，）處有多重定義元素，不是算符優(yōu)先文法；（3）改寫方法： 將E→ET中的減號(hào)與F→P中的賦值運(yùn)算符強(qiáng)制規(guī)定優(yōu)先關(guān)系； 或者將FP中的賦值運(yùn)算符改為別的符號(hào)來(lái)表示； (1)證明：由設(shè)句型a =…Ua…中含a的短語(yǔ)不含U，即存在A，A=*ay,則a可歸約為a =…Ua…252。*…UA…=b，b是G的一個(gè)句型，這與G是算符文法矛盾，所以，a中含有a的短語(yǔ)必含U。 （2）的證明與（1）類似，略。 證：（1）對(duì)于a=…aU…是句型，必有ST*a(=…aU…) T+…ab….即在歸約過(guò)程中,b先于a被歸約,從而,a(2)的情況類似可以證明。 證明略. 證明略. 證明略。 證：(1) 用反證法。設(shè)沒(méi)有短語(yǔ)包含b但是不包含a，則a,b一定同時(shí)位于某個(gè)短語(yǔ)中，從而必使得a,b同時(shí)位于同一產(chǎn)生式的右部，所以a=b，與G是算符優(yōu)先文法（=與不能并存）矛盾。 （2）、（3）類似可證。 證：只要證u中不含有除自身以外的素短語(yǔ)。設(shè)有這樣的素短語(yǔ)存在，即存在bxby是素短語(yǔ)，其中1x或者yn之一成立。因素短語(yǔ)是短語(yǔ)，根據(jù)短語(yǔ)定義，則必有：1xTbx1bx或ynTbyby+1，與bx1=bx及 by=by+1矛盾，得證。 提示：根據(jù)27題的結(jié)論，只要證u是句型α的短語(yǔ)，根據(jù)=關(guān)系的定義容易知道u是句型α的素短語(yǔ)。 證：與28題的不同點(diǎn)只是a0,an+1可以是’’,不影響結(jié)論。 證：設(shè)不能含有素短語(yǔ)，則只能是含有短語(yǔ)（不能含有終結(jié)符號(hào)），則該短語(yǔ)只能含有一個(gè)非終結(jié)符號(hào)，否則不符合算符文法定義，得證。 解： （1）算符優(yōu)先矩陣：+*↑（）i+*↑(=)I（2）用Floyd方法將優(yōu)先矩陣線性化得到得的優(yōu)先函數(shù)為：+*↑()iF3551771G2466161 解：用Floyd方法對(duì)已知的優(yōu)先矩陣構(gòu)造的優(yōu)先函數(shù)為： zbMLa()f1567747g1654667 解： （1）優(yōu)先矩陣如下：[]a[=]a（2）用Bell方法求優(yōu)先函數(shù)的過(guò)程如下：[]af5751g5561（3）顯然，文法不是算符優(yōu)先文法, 所以不能線性化。 略。 35解： （1）識(shí)別全部活前綴的DFA如下：（以表格的形式來(lái)表示，很容易可以轉(zhuǎn)化為圖的形式，本章中其余的題目也是采用這種形式表示。）狀態(tài)項(xiàng)目集經(jīng)過(guò)的符號(hào)到達(dá)的狀態(tài)I0S’ →SS→aSbS→aScS→abSaI1I2I1S’ →SI2S→aSbS→aScS→abS→aSbS→aScS→abSabI3I2I4I3S→aSbS→aScbcI5I6I4S→abI5S→aSbI6S→aSc（2）識(shí)別全部活前綴的DFA如下：狀態(tài)項(xiàng)目集經(jīng)過(guò)的符號(hào)到達(dá)的狀態(tài)I0S’ →SS→cAS→ccBScI1II1S’ →SI2S→cAS→ccBA→cAA→aAcaI3I4I5I3S→cAI4S→ccBA→cAB→ccBB→bA→cAA→aBAcbaI6I5I7I8I5I5A→aI6S→ccBI7B→ccBA→cAA→cAA→aCAaI9I10I5I8B→bI9B→ccBA→cAB→ccBB→bA→cAA→aBAcbaI11I10I7I8I5I10A→cAI11B→ccB所求的LR(0)項(xiàng)目規(guī)范族C={I0,I1,…,I11}（3）狀態(tài)項(xiàng)目集經(jīng)過(guò)的符號(hào)到達(dá)的狀態(tài)I0S’ →SS→aSSbS→aSSSS→cScaI1I2I3I1S’ →SI2S→cI3S→aSSbS→aSSSS→aSSbS→aSSSS→cScaI4I2I3I4S→aSSbS→aSSSS→aSSbS→aSSSS→cScaI5I2I3I5S→aSSbS→aSSSS→aSSbS→aSSSS→cSabcI7I3I6I2I6S→aSSbI7S→aSSS（4）狀態(tài)項(xiàng)目集經(jīng)過(guò)的符號(hào)到達(dá)的狀態(tài)I0S’ →SS→AA→AbA→aSAaI1I2I3I1S’ →SI2S→AS→AbbI4I3A→aI4S→Ab36解： （1）是LR(0)文法，其SLR(1)分析表如下：FOLLOW(S)={,b,c}ACTIONGOTOabcS0S211ACC2S2S433S5S64R3R3R35R1R1R16R2R2R2（2）是LR(0)文法，其SLR(1)分析表如下：FOLLOW(S)=FOLLOW(A)=FOLLOW(B)={}ACTIONGOTOabcSAB0S211ACC2S5S433R14S5S8S7365R46R27S5S9108R69S5S8S7101110R311R5（3）是LR(0)文法，其SLR(1)分析表如下：FOLLOW(S)={,a,b,c}ACTIONGOTOabcS0S3S211ACC2R3R3R3R33S3S244