編譯原理習題課答案市公開課金獎市賽課一等獎課件

chapter11、何謂源程序、目標程序、翻譯程序、編譯程序和解釋程序？它們之間可能有何種關系？源程序：用源語言編寫程序。目標程序：源程序經翻譯程序過加工處理后生成程序。翻譯程序：將源程序轉換為與其邏輯上等價目標程序。編譯程序：源語言為高級語言，目口號言為匯編語言或機器語言翻譯程序。解釋程序：源語言程序作為輸入，但不產生目標程序，而是邊解釋邊執(zhí)行源程序本身。①先翻譯后執(zhí)行①邊解釋邊執(zhí)行②執(zhí)行速度快②

有利于程序調試③屢次運算③1次運算第1頁2、一個經典編譯系統(tǒng)通常由有哪些部分組成？各部分主要功效是什么？chapter1編譯系統(tǒng)編譯程序語法分析語義分析與中間代碼生成優(yōu)化目標代碼生成運行系統(tǒng)詞法分析第2頁②語法分析(SyntaxAnalysis)：

在詞法分析基礎上將單詞序列分解成各類語法短語，如“程序”，“語句”，“表示式”等等。③語義分析(SyntacticAnalysis)：

語義分析是在語法分析程序確定出語法短語后，審查有沒有語義錯誤，并為代碼生成階段搜集類型信息。chapter1①詞法分析(LexicalAnalysis)：

從左到右一個字符一個字符讀入源程序，對組成源程序字符串進行掃描和分解，從而識別出一個個單詞（也稱單詞符號或簡稱符號）。

第3頁chapter1⑤代碼優(yōu)化(Optimizationofcode)：

為了使生成目標代碼更為高效，能夠對產生中間代碼進行變換或進行改造，這就是代碼優(yōu)化。⑥代碼生成(Generationofcode)：

目標代碼生成是編譯器最終一個階段。在生成目標代碼時要考慮以下幾個問題：計算機系統(tǒng)結構、指令系統(tǒng)、存放器分配以及內存組織等。④中間代碼生成(Generationofintermediatecode)：

完成語法分析和語義處理工作后，編譯程序將源程序變成一個內部表示形式，這種內部表示形式叫做中間語言或稱中間代碼，它是一個結構簡單、含義明確記號系統(tǒng)。第4頁chapter21.寫出C語言和Java語言輸入字母表。C語言：0~9數(shù)字，大小寫英文字母，鍵盤上可見字符Java語言：Unicode能夠包含全部字符。6.文法G6為:N→D|NDD→0|1|2|3|4|5|6|7|8|9

（1）G6語言是什么?G6語言是：

0~9數(shù)字組成任意非空串L(G6)={x|x∈{0,1,2,3,4,5,6,7,8,9}+}（2）給出句子0127、34和568最左和最右推導。第5頁7、寫一文法，使其語言是奇數(shù)集。要求：不以0打頭。復雜情況:分三部分末尾：以1|3|5|7|9結尾(一位):D→1|3|5|7|9開頭：除了0任意數(shù)字中間部分：空或者任意數(shù)字串D→1|3|5|7|9C→CA|εA→0|B所以題目要求文法G[N]能夠寫成：N→BCD|DD→1|3|5|7|9B→2|4|6|8|DC→CA|εA→0|BB→2|4|6|8|D第6頁9、證實文法:S→iSeS|iS|i

是二義。二義性含義:假如文法存在某個句子對應兩棵以上不一樣語法樹，或者兩種以上不一樣最左/右推導，則稱這個文法是二義。首先：找到此文法對應一個句子iiiei其次：結構與之對應兩棵語法樹SiSeSiSiiSiSiSeSii結論：因為該文法存在句子iiiei對應兩棵不一樣語法樹，因而該文法是二義。第7頁11、給出下面語言對應文法L1={anbnci|n≥1,i≥0}G1(S):S→ABA→aAb|abB→cB|ε從n，i不一樣取值來把L1分成兩部分：A→aAb|ab前半部分是anbn：

后半部分是ci：B→Bc|ε所以整個文法G1[S]能夠寫為：第8頁L2={aibncn|n≥1,i≥0}G2(S):S→ABA→aA|εB→bBc|bcL3={anbnambm|m,n≥0}G3(S):S→ABA→aAb|εB→aBb|ε第9頁L4={1n0m1m0n|n,m≥0}能夠看成是兩部分：剩下兩邊部分就是：S→1S0中間部分是0m1m

：A→0A1|ε所以G4[S]能夠寫為：S→1S0|AA→0A1|ε|A第10頁chapter37.結構以下正規(guī)式對應DFA。步驟:①.依據(jù)正規(guī)式畫出對應狀態(tài)轉換圖;②.依據(jù)狀態(tài)轉換圖畫出對應狀態(tài)轉換矩陣;③.依據(jù)狀態(tài)轉換矩陣得到重命名后狀態(tài)轉換矩陣;④.依據(jù)重命名后狀態(tài)轉換矩陣得出最終DFA.問題：將狀態(tài)轉換圖與DFA混同。第11頁1(0|1)*101①.狀態(tài)轉換圖abadb1(0|1)*101a1(0|1)*101dcef1εε01101ggg第12頁②.狀態(tài)轉換矩陣II0I1{a}Φ{b,c,d}{b,c,d}{c,d}{c,d,e}{c,d}{c,d}{c,d,e}{c,d,e}{c,d,f}{c,d,e}{c,d,f}{c,d}{c,d,e,g}{c,d,e,g}{c,d,f}{c,d,e}1abdcef1εε0101g第13頁II0I1{a}Φ{b,c,d}{b,c,d}{c,d}{c,d,e}{c,d}{c,d}{c,d,e}{c,d,e}{c,d,f}{c,d,e}{c,d,f}{c,d}{c,d,e,g}{c,d,e,g}{c,d,f}{c,d,e}③.重命名后狀態(tài)轉換矩陣S01A(始態(tài))ΦBBCDCCDDEDECF(終態(tài))F(終態(tài))EDAB10C1D010E10101F④.DFA第14頁1(1010*|1(010)*1)*0abdc1εε0e0101fghiεε01110jklmnεε①.狀態(tài)轉換圖第15頁②.狀態(tài)轉換矩陣II

0I

1{0}Φ{1,2,3}{1,2,3}{4}{5,9,10,11}{5,9,10,11}{6,12}{2,3}{6,12}Φ{2,3,7,8,13}{2,3}{4}{5,9,10,11}{2,3,7,8,13}{2,3,4,8,10,11}{5,9,10,11}{2,3,4,8,10,11}{2,3,4,8,12}{2,3,5,9,10,11}{2,3,4,8,12}{2,3,4,8}{5,9,10,11,13}{2,3,5,9,10,11}{4,6,12}{2,3,5,9,10,11}{2,3,4,8}{2,3,4,8}{5,9,10,11}{5,9,10,11,13}{6,10,11,12}{2,3}{4,6,12}Φ{2,3,7,8,13}{6,10,11,12}{12}{2,3,7,8,13}{12}Φ{13}{13}{10,11}Φ{10,11}{12}{2,3}第16頁③.重命名后狀態(tài)轉換矩陣II

0I

11Φ22344565Φ7634784891091112101310111141214613Φ71415715Φ161617Φ17156④.DFA第17頁8、給出下面正規(guī)表示式（1）以01結尾二進制數(shù)串。(0|1)*01（2）能被5整除十進制數(shù)。0|5(0|5)|(1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)*（4）英文字母組成全部符號串，要求符號串中字母按字典序排列。(A|a)*(B|b)*(C|c)*…(Z|z)*（3）包含奇數(shù)個1或奇數(shù)個0二進制串0*1(0|10*1)*|1*0(0|10*1)*第18頁（5）沒有重複出現(xiàn)數(shù)字數(shù)字符號串全體令ri=i|,i=0,1,2...9R0|R1|R2|...|R9記為∑Rii(0,1,2...,9)P（0,1,2...,9)表示0,1,2...,9全排列∑ri0ri1...ri9ri0ri1...ri9

P(0,1,2...,9)8、給出下面正規(guī)表示式（6）最多有一個重複出現(xiàn)數(shù)字數(shù)字符號串全體∑i∑ri0ri1...ri9

i(0,1,2...,9)ri0ri1...ri9P(0,1,2...,9)（7）不包含字串abb由a和b組成符號串全體b*(a*|(ba)*)*第19頁9、對下面情況給出DFA及正規(guī)表示式：（1）{0,1}上含有子串010全部串。正規(guī)式：(0|1)*010(0|1)*DFA做法同第7題。（2）{0,1}上不含子串010全部串。正規(guī)式：1*(0|11*1)*1*0*1*(0|11)*(0|1)1*(0|11)*1*第20頁12、將圖3.18(a)和(b)分別確定化和最少化。(a)aaa,b10①.狀態(tài)轉換矩陣IIaIb

{0}{0,1}{1}{1}{0,1}{0,1}{1}{0}φ②.重命名后狀態(tài)轉換矩陣IIaIb

01221120φ0a2baba③.DFA④.最小化Π0=({0,1},{2})1{0,1}a={1}{0,1}b={2}所以，不能再分02baa第21頁023145aaaabbbbbbaa(b)這道題實質上已經是確定化了，所以我們只需最小化Π：{2，3，4，5}{0，1}{2，3，4，5}a={0，1，3，5}分屬兩區(qū)，所以分為{2，4}{3，5}{0，1}a={1}{0，1}b={2，4}所以0，1等價{2，4}a={0，1}{2，4}b={3，5}所以2，4等價{3，5}a={3，5}{3，5}b={2，4}所以3，5等價所以分為

{0，1}{2，4}{3，5}

023aabbba第22頁14、結構一個DFA，它接收Σ={0,1}上全部滿足以下

條件字符串：每個1都有0直接跟在右邊。思緒：先寫出滿足條件正規(guī)式，由正規(guī)式結構

NFA，再把NFA確定化和最小化。滿足條件正規(guī)式：(0|10)*0110yx(0|10)*xy12100第23頁xy12100確定化：01{X,1,Y}{1,Y}{2}{1,Y}{1,Y}{2}{2}{1,Y}φ給狀態(tài)編號：0101211221φ第24頁021

01100最小化：{0,1}，{2}{0,1}0={1}{0,1}1={2}{2}0={0}，{2}1=

??{2}或{0,1}所以{0,1}不可分，用狀態(tài)0代表它們02100第25頁15、給定右線性文法G：求一個與G等價左線性文法。S→0S|1S|1A|0BA→1C|1B→0C|0C→0C|1C|0|1SABCZ001110001101G[Z]:Z→Z0|Z1|B0|A1B→A0|0A→B1|1確定化、最小化后DFA為：SB0A110Z010,1第26頁補充：結構一右線性文法，使它與以下文法等價：

S→ABA→UTU→a|aUT→b|bTB→c|cB

并依據(jù)所得右線性文法，結構出對應狀態(tài)轉換圖。思緒：先寫出原文法所描述語言L(G)={ambnck|m,n,k≥1}G[S]:

S→aS|aBB→bB|bCC→cC|caSaCbcBbcT第27頁chapter44.1、考慮下面文法G1：S→a|∧|（T）

T→T，S|S（1）消去G1左遞歸；S→a|∧|（T）T→ST’T’→，ST’|ε（2）經改寫后文法是否是LL(1)文法，給出預測分析表。經改寫后文法滿足3個條件，所以是LL(1)第28頁預測分析表結構算法:1.對文法中每個產生式A→α執(zhí)行第二步和第三步;FIRST(S)={a,∧,(}FIRST(T)={a,∧,(}FIRST(T’)={,,ε}FOLLOW(S)={),,,#}

FOLLOW(T)={)}

FOLLOW(T)={)}

a∧（，）#S

T

T’

S→aS→∧S→(T)T→ST’T→ST’T→ST’T’→,ST’T’→ε第29頁預測分析表結構算法:1.對文法中每個產生式A→α執(zhí)行第二步和第三步;2.對每個終止符a∈FIRST(α),把A→a加到M[A,a]中;S→a;S→∧;S→(T);T→ST’;T’→,ST’T’→εFTRST（a）={a}FIRST（∧）={∧}FIRST（（T））={（}FIRST（ST’）={a，∧，（}FIRST（，ST’）={，}FIRST（ε）={ε}

a∧（，）#S

T

T’

S→aS→∧S→(T)T→ST’T→ST’T→ST’T’→,ST’3.若ε∈FIRST(α),則對于任何b∈FOLLOW(A)把A→α加至M[A,b]中FOLLOW(T’)=FOLLOW(T)={)}T’→ε第30頁遞歸子程序：procedureS;begin ifsym='a'orsym='^' thenabvanceelseifsym='(' thenbegin advance;T; ifsym=')'thenadvance; elseerror; end elseerrorend;第31頁procedureT;begin S;T’EndprocedureT’;begin ifsym=‘,’thenbenginadvance;S;T’endEndsym:是輸入串指針I(yè)P所指符號advance:是把IP調至下一個輸入符號error:是犯錯診察程序第32頁補充題：有文法：

E→TE’E’→ATE’|εT→FT’T’→MFT’|εF→（E）|iA→+|-M→*|/（1）求First、Follow集，判斷是否是LL（1）文法？（2）若是結構LL（1）分析表？（3）簡述LL（1）分析器工作原理。第33頁4.2：有文法：

E→TE’E’→+E|εT→FT’T’→T|εF→PF’F’→*F’|εP→(E)|a|b|^（1）求First、Follow集，判斷是否是LL（1）文法？（2）若是結構LL（1）分析表？（3）簡述LL（1）分析器工作原理。第34頁E→TE’E’→ATE’|εT→FT’T’→MFT’|εF→（E）|iA→+|-M→*|/FIRST(M)={*，/}FIRST(A)={+，-}FIRST(F)={(，i}FIRST(T’)={*，/，ε}FIRST(T)={(，i)FIRST(E’)={+，-，ε}FIRST(E)={(，i}FOLLOW(E)={#，)}FOLLOW(E’)={#，)}FOLLOW(T)={+，-，#，)}FOLLOW(T’)={+，-，#，)}FOLLOW(F)={*，/，+，-，#，)}FOLLOW(A)={(，i}FOLLOW(M)={(，i}EE→TE’

E→TE’

E’

E→ATE’E→ATE’

E’→εE’→εTT→FT’

T→FT’

T’

T’->εT’→εT’→MFT’T’→MFT’

T’→εT’→εFF→i

F→（E）

A

A→+A→-

M

M→*M→/

i+-*/（）#第35頁P81.2.對文法G:E→TE’E’→+E|εT→FT’T’→T|εF→PF’F’→*F’|εP→(E)|a|b|∧1)FIRST(E)=FIRST(T)=FIRST(F)=FIRST(P)={(,a,b,∧}FIRST(E’)={+,ε}FIRST(T’)=FIRST(T)∪{ε}={(,a,b,∧,ε}FIRST(F’)={*,ε}FOLLOW(E)={#,)}FOLLOW(E’)=FOLLOW(E)={#,)}FOLLOW(T)=FIRST(E’)\ε∪FOLLOW(E)={+,#,)}FOLLOW(T’)=FOLLOW(T)={+,#,)}FOLLOW(F)=FIRST(T’)\ε∪FOLLOW(T)={(,a,b,∧,+,#,)}FOLLOW{F’)=FOLLOW(F)={(,a,b,∧,+,#,)}FOLLOW(P)=FIRST(F’)\ε∪FOLLOW(F)={*,(,a,b,∧,+,#,)}(ab∧+*)#EE→TE’E→TE’ETE’ETE’E’E’+EE’εE’εTTFT’TFT’TFT’TFT’T’T’TT’TT’TT’TT’εT’εT’εFFPF’FPF’FPF’FPF’F’F’εF’εF’εF’εF’εF’F’F’εF’εPP(E)PaPbP^第36頁2)考慮以下產生式:FIRST(+E)∩FIRST(ε)={+}∩{ε}=φFIRST(+E)∩FOLLOW(E')={+}∩{#,)}=φFIRST(T)∩FIRST(ε)={(,a,b,^}∩{ε}=φFIRST(T)∩FOLLOW(T')={(,a,b,^}∩{+,),#}=φFIRST(*F')∩FIRST(ε)={*}∩{ε}=φFIRST(*F')∩FOLLOW(F')={*}∩{(,a,b,^,+,),#}=φFIRST((E))∩FIRST(a)∩FIRST(b)∩FIRST(^)=φ所以,該文法式LL(1)文法.第37頁(ab∧+*)#EE→TE’E→TE’ETE’ETE’E’E’+EE’εE’εTTFT’TFT’TFT’TFT’T’T’TT’TT’TT’TT’εT’εT’εFFPF’FPF’FPF’FPF’F’F’εF’εF’εF’εF’εF’F’F’εF’εPP(E)PaPbP^3)預測分析表：第38頁4)程序procedureE;begin ifsym='('orsym='a'orsym='b'orsym='^' thenbeginT;E'end elseerrorendprocedureE';begin ifsym='+' thenbeginadvance;Eend elseifsym<>')'andsym<>'#'thenerrorendprocedureT;begin ifsym='('orsym='a'orsym='b'orsym='^' thenbeginF;T'end elseerrorend 第39頁procedureT';begin ifsym='('orsym='a'orsym='b'orsym='^' thenT elseifsym='*'thenerrorendprocedureF;begin ifsym='('orsym='a'orsym='b'orsym='^' thenbeginP;F'end elseerrorend procedureF';begin ifsym='*' thenbeginadvance;F'endend第40頁procedureP;begin ifsym='a'orsym='b'orsym='^' thenadvance elseifsym='('then begin advance;E; ifsym=')'thenadvance elseerror end elseerrorend;第41頁4.3下面文法中，那些是LL(1)文法，說明理由結構不帶回溯自上而下分析文法條件

1.文法不含左遞歸，

2.對于文法中每一個非終止符A各個產生式候選首符集兩兩不相交。即，若A→1|2|…|n

則FIRST(i)∩FIRST(j)＝

(ij)3.對文法中每個非終止符A，若它存在某個候選首符集包含，則FIRST(A)∩FOLLOW(A)=

假如一個文法G滿足以上條件，則稱該文法G為LL(1)文法。 第42頁4.3.1SAbcAa|Bb|是，滿足三個條件4.3.2SAbAa|B|Bb|對于A不滿足條件34.3.3SABBAAa|Bb|A、B都不滿足條件34.3.4SaSe|BBbBe|CcCe|d滿足條件3第43頁解題思緒：構造文法預測分析表，通常應當按以下步驟進行：

1.消除文法左遞歸（包含全部直接左遞歸和間接左遞歸）

2.對消除左遞歸后文法，提取公因子

3.對經過上述改造后文法，計算它每個非終結符FIRST集合和FOLLOW集合；

4.根據(jù)FIRST集合和FOLLOW集合構造預測分析表：第1步對文法G每個產生式Aα執(zhí)行第1步和第3步；第2步對每個終結符a∈FIRST(α),把Aα加至M[A,a]中；第3步若∈FIRST(α),則對任何b∈FIRST(A),把Aα加至M[A,b]中；第4步把全部無定義M[A,a]標上“出錯標誌”4.4對下面文法：Expr-ExprExpr(Expr)|VarExprTailExprTail-Expr|VaridVarTailVarTail(Expr)|(1)構造LL(1)分析表(2)給出對句子id--id((id))分析過程第44頁4.4對下面文法：Expr-ExprExpr(Expr)|VarExprTailExprTail-Expr|VaridVarTailVarTail(Expr)|(1)構造LL(1)分析表(2)給出對句子id--id((id))分析過程解答：FIRST(Expr)={-,(,id}FOLLOW(Expr)={),#}FIRST(ExprTail)={-,}FOLLOW(ExprTail)={),#}FIRST(Var)={id}FOLLOW(Var)={-,),#}FIRST(VarTail)={(,}FOLLOW(VarTail)={-,),#}第45頁4.4對下面文法：Expr-ExprExpr(Expr)|VarExprTailExprTail-Expr|VaridVarTailVarTail(Expr)|(1)構造LL(1)分析表(2)給出對句子id--id((id))分析過程-id()#ExprExpr-ExprExprVarExprTailExpr(Expr)ExprTaiExprTail-ExprExprTailExprTailVarVaridVarTailVarTailVarTailVarTail(Expr)VarTailVarTail第46頁-id()#ExprExpr-ExprExprVarExprTailExpr(Expr)ExprTaiExprTail-ExprExprTailExprTailVarVaridVarTailVarTailVarTailVarTail(Expr)VarTailVarTail步驟符號棧輸入串所用產生式0#Exprid--id((id))#開始1#ExprTailvarid--id((id))#ExprVarExprTail2#ExprTailvarTailidid--id((id))#VaridVarTail3#ExprTailvarTail--id((id))#出棧，輸入串後移4#ExprTail--id((id))#VarTail5#Expr---id((id))#ExprTail-Expr(2)給出對句子id--id((id))分析過程第47頁-id()#ExprExpr-ExprExprVarExprTailExpr(Expr)ExprTaiExprTail-ExprExprTailExprTailVarVaridVarTailVarTailVarTailVarTail(Expr)VarTailVarTail步驟符號棧輸入串所用產生式5#Expr---id((id))#ExprTail-Expr6#Expr-id((id))#出棧，輸入串後移7#Expr--id((id))#Expr-Expr8#Exprid((id))#出棧，輸入串後移9#ExprTailVarid((id))#ExprVarExprTail10#ExprTailVarTailidid((id))#VaridVarTail11#ExprTailVarTail((id))#出棧，輸入串後移(2)給出對句子id--id((id))分析過程第48頁-id()#ExprExpr-ExprExprVarExprTailExpr(Expr)ExprTaiExprTail-ExprExprTailExprTailVarVaridVarTailVarTailVarTailVarTail(Expr)VarTailVarTail步驟符號棧輸入串所用產生式11#ExprTailVarTail((id))#出棧，輸入串後移12#ExprTail)Expr(((id))#VarTail(Expr)13#ExprTail)Expr(id))#出棧，輸入串後移14#ExprTail))Expr((id))#Expr(Expr)15#ExprTail))Exprid))#出棧，輸入串後移16#ExprTail))ExprTailVarid))#ExprVarExprTail17#ExprTail))ExprTailVarTailidid))#VaridVarTail(2)給出對句子id--id((id))分析過程第49頁-id()#ExprExpr-ExprExprVarExprTailExpr(Expr)ExprTaiExprTail-ExprExprTailExprTailVarVaridVarTailVarTailVarTailVarTail(Expr)VarTailVarTail步驟符號棧輸入串所用產生式17#ExprTail))ExprTailVarTailidid))#VaridVarTail18#ExprTail))ExprTailVarTail))#出棧，輸入串後移19#ExprTail))ExprTail))#VarTail20#ExprTail))))#ExprTail21#ExprTail))#出棧，輸入串後移22#ExprTail#出棧，輸入串後移23##ExprTail成功(2)給出對句子id--id((id))分析過程第50頁chapter51、令文法G1為：

E→E+T|TT→T*F|FF→(E)|i

證實E+T*F是它一個句型，指出這個句型全部短語、直接短語和句柄。EE+TT*FT*F是句型E+T*F相對于T短語E+T*F句型E+T*F相對于E短語T*F是句型E+T*F相對于T直接短語T*F是句柄第51頁2、考慮下面表格結構文法G2：

S→a|^|(T)

T→T,S|S（1）給出(a,(a,a))和(((a,a),^,(a)),a)最左和最右推導。(a,(a,a))最左推導：S(T)(T,S)(S,S)(a,S)(a,(T))(a,(T,S))(a,(S,S))(a,(a,S))(a,(a,a))(((a,a),^,(a)),a)最左推導：S(T)(T,S)(S,S)((T),S)((T,S),S)((T,S,S),S)((S,S,S),S)(((T,S),S,S),S)(((S,S),S,S),S)(((a,S),S,S),S)(((a,a),S,S),S)(((a,a),^,S),S)(((a,a),^,a),S)(((a,a),^,a),a)第52頁(((a,a),^,(a)),a)最右推導：S(T)(T,S)(S,S)(S,a)((T),a)((T,S,S),S)((S,S,S),S)(((T,S),S,S),S)(((S,S),S,S),S)(((a,S),S,S),S)(((a,a),S,S),S)(((a,a),^,S),S)(((a,a),^,a),S)(((a,a),^,a),a)(a,(a,a))最右推導：S(T)(T,S)(T,(T))(T,(T,S))(T,(T,a))(T,(S,a))(T,(a,a))(S,(a,a))(a,(a,a))第53頁2）指出(((a,a),^,(a)),a)規(guī)范歸約及每一步句柄。S(T)T,Sa(T)ST,ST,S(T)Sa^(T)ST,SaSa句型句柄歸約規(guī)則(((a,a),^,(a)),a)aS→a(((S,a),^,(a)),a)ST→S(((T,a),^,(a)),a)aS→a(((T,S),^,(a)),a)T,ST→T,S(((T),^,(a)),a)(T)S→(T)((S,^,(a)),a)ST→S((T,^,(a)),a)^S→^((T,S,(a)),a)T,ST→T,S((T,(a)),a)aS→a((T,(S)),a)ST→S((T,(T)),a)(T)S→(T)((T,S),a)T,ST→T,S((T),a)TS→(T)(S,a)ST→S(T,a)aS→a(T,S)T,ST→T,S(T)(T)S→(T)S第54頁依據(jù)這個規(guī)范規(guī)約，給出“移進—歸約”過程，并給出它語法樹自下而上結構過程。#符號棧輸入串：(((a,a),^,(a)),a)#S(T)T,Sa(T)ST,ST,S(T)Sa^(T)ST,SaSa(((aS,TaSS)T,^ST(aST)S)ST,aST)S歸約規(guī)則句柄aS→aST→SaS→aT,ST→T,S(T)S→(T)ST→S^S→^T,ST→T,S第55頁3、(1)計算練習2文法G2FIRSTVT和LASTVT。

G2：S→a|^|(T)

T→T,S|SFIRSTVT(S)={a，∧，(}FIRSTVT(T)={，，a，∧，(}LASTVT(S)={a，∧，)}LASTVT(T)={，，a，∧，)}S→（T）（）.T→T，S

，F(xiàn)IRSTVT(S)﹤.，a,，∧,

，(

﹤.﹤.﹤.T→T，SLASTVT(T)，﹥.a，,∧，,），,，，﹥.﹥.﹥.﹥.S→（T）(FIRSTVT(T)﹤.(a,(∧,((,(，﹤.﹤.﹤.﹤.S→（T）LASTVT(T))﹥.a),∧),)),，)﹥.﹥.﹥.﹥.對待特殊地#,把它看作句型開始和結束符.依據(jù)#S#同理可得#a,#∧,#(,﹤.﹤.﹤.##.a#,∧#,）#,﹥.﹥.﹥.#,)(^a#,)(^a=.>.>.>.>.>.>.>.>.>.>.>.<.<.<.<.<.<.<.<.<.<.=.1、文法是算術文法，且不含ε產生式。2、由優(yōu)先關系矩陣可知，任何兩個終止符之間優(yōu)先關系不多于一個。綜上，該文法是算術優(yōu)先文法。第56頁﹤.

，a∧（）#，

a

∧

(

)

#

﹥.﹥.﹥.﹥.﹥.﹥.﹥.﹥.﹥.﹥.﹥.﹤.﹤.﹤.﹤.﹤.﹤.﹤.﹤.﹤...輸入串(a,(a,a))算符優(yōu)先過程。步驟句型優(yōu)先關系最左素短語規(guī)約符號1#(a,(a,a))##2345678﹤.(﹤.a﹥.,﹤.(﹤.a﹥.,﹤.a﹥.)﹥.)﹥.#aS#(S,(a,a))#﹤