【正文】 A∧()，f44244g55523 （4）輸入串（a，（a，a））的算符優(yōu)先分析過程如下：棧輸入字符串動作(a，(a，a))預備(a，(a，a))進(a，(a，a))進(s，(a，a))歸(t，(a，a))歸(t，(a，a))進(t，(a，a))進(t，(a，a))進(t，(s，a))歸(t，(t，a))歸(t，(ta))進(t，(t，a))進(t，(t，s))歸(t，(t))歸(t，(t))進(t，s)歸(t)歸(t)進s歸成功存在一種稱為簡單優(yōu)先的自下而上分析法，這種分析法不會把錯誤句子當作為正確句子。一個文法G，如果它不含ε產(chǎn)生式，也不含任何右部相同的不同產(chǎn)生式，并且它的任何符號對（X，Y）——X和Y為終結(jié)符或非終結(jié)符——頂多存在下述三種關(guān)系=、之一，則稱這個文法G是一個簡單優(yōu)先文法。這三種關(guān)系的定義是： A、X=Y當且僅當G中含有形如P→…XY…的產(chǎn)生式； B、XY當且僅當G中含有形如P→…XQ…的產(chǎn)生式，其中Q為非終結(jié)符，而且Q=Y…； C、XY當且僅當Y為文法G的終結(jié)符，且G 含有形為P→…QR…的產(chǎn)生式，使得Q=…X而Y∈FIRST(R)。例如，假定有規(guī)則S→(T)和推導T=S=a則S)和a)成立。注意，上述R可能是終結(jié)符也可能是非終結(jié)符。 D、對任何X，若S考慮文法： S→AS︱b A→SA︱a（1） 列出這個文法的所有LR(0)項目。（2） 構(gòu)造這個文法的LR(0)項目集規(guī)范族及識別活前綴的DFA。（3） 這個文法是SLR的嗎？若是，構(gòu)造出它的SLR分析表。（4） 這個文法是LALR或LR(1)的嗎？ 分析：構(gòu)造LR(0)項目集規(guī)范族有兩種方法：一種是利用有限自動機來構(gòu)造，另一種是利用函數(shù)CLOSURE和GO來構(gòu)造。本題采用第一種方法，先構(gòu)造識別活前綴的NFA，然后確定化，得到識別活前綴的DFA。 解： （1）、’→S ’ →S →AS →AS →AS →b →b →SA →SA →SA →a →a （2）、構(gòu)造識別活前綴的NFA如下圖所示： 01SA27εaAε9114681035SεεεεεεεSd 確定化的結(jié)果見轉(zhuǎn)換矩陣表：SAab{0，2，5，7，10}{1，2，5，7，8，10}{2，3，5，7，10}{11}{6}{1，2，5，7，8，10}{2，5，7，8，10}{2，3，5，7，9，10}{11}{6}{2，3，5，7，10}{2，4，5，7，8，10}{，3，5，7，10}{11}{6}{2，5，7，8，10}{2，5，7，8，10}{2，3，5，7，9，10}{11}{6}{2，3，5，7，9，10}{2，4，5，7，8，10}{2，3，5，7，10}{11}{6}{2，4，5，7，8，10}{2，5，7，8，10}{2，3，5，7，9，10}{11}{6}{11}216。216。216。216。{6}216。216。216。216。 （3）、不是SLR文法。 III7有“移進—歸約”沖突。 I3：FOLLOW(S’)={}不包含a，b。 I6：FOLLOW(S)={，a，b}包含a，b；“移進—歸約”沖突無法消解。 I7：FOLLOW(A)={a，b}包含a，b；“移進—歸約”沖突消解。 所以不是SLR文法。下面是一個描述∑={a，b}上的正規(guī)式的LALR文法（實際上也是SLR文法），只不過用‘+’代替‘∣’，用^代替ε（空字）。 E→E+T∣T T→TF∣F F→F*∣(E)∣a∣b∣∧ 構(gòu)造這個文法的LALR項目集和分析表。證明下面文法是SLR(1)但不是LR(0)的。 S→A A→Ab∣bBa B→aAc∣a∣aAb證明： 求該文法的LR(0)項目集規(guī)范族如下： I0={S，A→bBa} GO(I0，A)={S→A，A→Ab }=I1 GO(I0，b)={A→bBa，B→aAc，B→a，B→aAb}=I2 GO(I1，b)={A→Ab}=I3 GO(I2，B)={A→bBa}=I4 GO(I2，a)={B→aAc，B→a，B→aA b，A→Ab，A→b Ba}=I5 GO(I4，a)={ A→bBa}= I6 GO(I5，A)={ B→aAc，B→aAb，A→Ab}= I7 GO(I5，b)={ A→bBa，B→aAc，B→a，B→aAb }= I2 GO(I7，c)={ B→aAc}= I8 GO(I2，b)={ B→aAb，A→Ab}= I9 考慮I1，I5都存在“移進—歸約”沖突，所以該文法不是LR(0)的。 由于FOLLOW(S)={}，不包含b，所以I1的沖突可以消解；由于FOLLOW(B)={a}，不包含b，所以I5的沖突可以消解；由于FOLLOW(B)={a}，F(xiàn)OLLOW(A)={c，b，}，二者不相交，所以I9的沖突也可以消解。 綜上所述，該文法是SLR(1)的。證明下面的文法是LL(1)的但不是SLR(1)的。 S→AaAb∣BbBa A→ε B→ε證明： 因為FIRST(AaAb)={a}，F(xiàn)IRST(BbBa)= FIRST(AaAb)∩FIRST(BbBa)=216。 所以該文法是LL(1)的。 求該文法的LR(0)項目集規(guī)范族如下： I0={S’→S，S→AaAb，S→BbBa，A→，B→} I1={S→S} I2={S→AaAb} I3={S→BbBa} I4={S→AaAb，A→} I5={S→BbBa，B→} I6={S→AaAb} I7={S→BbBa} I8={S→AaAb} I9={S→BbBa} 考慮I0：FOLLOW(A)=FOLLOW(B)={a，b} A→和B→的沖突無法消解，所以該文法不是SLR(1)的。證明下面文法是LALR(1)但不是SLR(1)的。 S→Aa∣bAc∣Bc∣bBa A→d如果我們用下面的二義文法產(chǎn)生正規(guī)式E→E+E∣EE∣E*∣(E) ∣a∣b∣∧(1) 給出解決二義性的YACC說明，按照這個說明能正確的分析正規(guī)式。(2) 按照(1)的說明所規(guī)定的解決二義性的準則，構(gòu)造這個文法的LALR分析器。用這個分析器給出a+ba*的分析過程，并以此論證這個分析器能夠正確的分析正規(guī)式。 第六章 屬性文法和語法制導翻譯1. ，構(gòu)造表達式（4*7+1）*2的附注語法樹。 = 4 = 4 L = 58n = 58 = 29 = 2*= 2 = 29 ( = 29 ) = 28 = 1 + = 1=1 11111= 1 = 28 = 7 * = 7=42. 對表達式( (a) + (b) ):(1). 。(2). ，構(gòu)造該表達式的抽象語法樹。 +.. id.id. to entry for a to entry for b第七章P2171a*（b+c） 后綴式：abc+*a+b*（c+d/e） 后綴式：abcde/+*+a+b*（c+d） 后綴式：abcd+*+not A or not（C or not D） 后綴式：A not C D not or not or（A and B）or（not C or D） 后綴式：A B and C not D or or（A or B）and（C or not D and E）后綴式： A B or C D not E and or andXy+z*0= ab+c! abc!! If then else 或者 Xy+z*0= p1 jez ab+c! p2 jump abc!! p2條件語句IF﹤表達式﹥THEN﹤語句1﹥ELSE﹤語句2﹥的逆波蘭式 表示為：﹤表達式﹥﹤語句1﹥﹤語句2﹥IF THEN ELSE或﹤表達式﹥P1 Jez﹤語句1﹥P2 J P1：﹤語句2﹥P2：，其中Jez是﹤表達式﹥和P1這兩個運算對象的二元運算符，表示當﹤表達 式﹥等于0即取假值時轉(zhuǎn)去執(zhí)行由P1開始的﹤語句2﹥。否則，執(zhí)行﹤語句1﹥?nèi)缓筠D(zhuǎn)至P2所指地方；J是無條件轉(zhuǎn)移的一元運算符。2三元式 OpArg1Arg2(0)+aB(1)uminus(0)(2)+cd(3)*(1)(2)(4)+ab(5)+(4)c(6)(3)(5)間接三元式Opag1ag2(0)+ab(1)uminus(0)(2)+cd(3)*(1)(2)(4)+(0)d(5)(3)(4)間接代碼 (0),(1),(2),(3),(0),(4),(5)四元式序列opag1ag2result(0)+abT1(1)uminusT1T2(2)+cdT3(3)+T1cT4(4)*T3T4T5(5)T5T4T64產(chǎn)生三地址代碼6A or （B and not（C or D））：100：（jnz，A，，0）101：（j，，，102）102：（jnz，B，，104）103：（j，，，0）104：（jnz，C，，0）105：（j，，，106）106：（jnz，D，，0）107：（j，，，0）7100：（j，A，C，102）101：（j，，，114）102：（j，B，D，104）103：（j，，，114）104：（j=，A，‘1’，106）105：（j，，，109）106：（+，C，‘1’，T1）107：（:=，T1，，C）108：（j，，，100）109：（j≤，A，D，111）110：（j，，，100）111：（+，A，‘2’，T2）112：（:=，T2，，A）113：（j，，，109）114：第十章 代碼優(yōu)化 一 程序流圖第二題程序流圖第四題 優(yōu)化