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