2023年編譯原理題庫

第一章什么是編譯器？編譯程序的結(jié)構(gòu)分為幾個(gè)階段，各階段的任務(wù)是什么?遍、編譯前端及編譯后端的含義?編譯程序的生成方式有哪些？第二章１.寫一文法,使其語言是偶正整數(shù)的集合。規(guī)定：(１）允許0打頭(２）

不允許0打頭解:(1）允許0開頭的偶正整數(shù)集合的文法E→NT｜DT→ＮT|DＮ→Ｄ|1｜3｜5|7|9D→0|2|４｜6|８（２）不允許0開頭的偶正整數(shù)集合的文法E→ＮT|DT→FT｜GN→Ｄ|1｜３|５|7|9Ｄ→2|4｜６｜8F→N|0G→D|02.證明下述文法G［〈表達(dá)式〉]是二義的?！幢磉_(dá)式〉∷＝ａ｜(〈表達(dá)式〉)|〈表達(dá)式〉〈運(yùn)算符〉〈表達(dá)式〉〈運(yùn)算符〉∷=+|－|*|／解：可為句子a＋a＊a構(gòu)造兩個(gè)不同的最右推導(dǎo):最右推導(dǎo)1〈表達(dá)式〉T〈表達(dá)式〉〈運(yùn)算符〉〈表達(dá)式〉T〈表達(dá)式〉〈運(yùn)算符〉aT〈表達(dá)式〉＊aT〈表達(dá)式〉〈運(yùn)算符〉〈表達(dá)式〉*aT〈表達(dá)式〉〈運(yùn)算符〉a*aT〈表達(dá)式〉+ａ*ａTa+a*ａ最右推導(dǎo)2〈表達(dá)式〉T〈表達(dá)式〉〈運(yùn)算符〉〈表達(dá)式〉T〈表達(dá)式〉〈運(yùn)算符〉〈表達(dá)式〉〈運(yùn)算符〉〈表達(dá)式〉T〈表達(dá)式〉〈運(yùn)算符〉〈表達(dá)式〉〈運(yùn)算符〉ａT〈表達(dá)式〉〈運(yùn)算符〉〈表達(dá)式〉*aT〈表達(dá)式〉〈運(yùn)算符〉a*aT〈表達(dá)式〉+a*aTａ+ａ*a3．給出生成下述語言的上下文無關(guān)文法:（1）{anbnambｍ｜n，m＞=0}(２){1n0m1ｍ0n｜n，ｍ＞=0}解：（1）｛anbnａmbｍ|n,ｍ>＝0}S→AAＡ→aＡb｜ε(2）{１n0m1m0n|n,m＞=0}S→1S0|AA→0A1|ε第三章１、構(gòu)造一個(gè)DFA,它接受∑={a,b｝上所有滿足下述條件的字符串：字符串中的每個(gè)a都有至少一個(gè)b直接跟在其右邊。解：已知∑={ａ,b}，根據(jù)題意得出相應(yīng)的的正規(guī)式為：(b*ａbb＊)*根據(jù)正規(guī)式畫出相應(yīng)的DFAM，如下圖所示用子集法將其擬定化XY(b*abb*)*XY(b*abb*)*XYb*abb*1XYb123456bbaIIaIb｛X，１,２,3,Y}{4｝{2,３}{4｝—{５,６,1,２,3,Y}{２，３}{4}{2,3}{5,6,1，2,３，Y}{4}{6，1,2,3,Ｙ}{６,1,２,３,Y}{4}｛6,1,２,３,Y}IIaIｂ01２1—3２1２3１4４14由DＦA得狀態(tài)圖用最小化方法化簡得:{０},{1},{２}，{３,4}，按順序重新命名ＤFAＭ’10210243aaaabbbbb0312aaabbb第四章練習(xí)1：文法G［V]:V→N|N［E]E→V|Ｖ+EN→i是否為ＬL(１)文法，如不是,如何將其改導(dǎo)致LL(1)文法。解：LL(1)文法的基本條件是不含左遞歸和回溯（公共左因子），而G[V]中具有回溯，所以先消除回溯得到文法G’[V]:G’［Ｖ]:V→ＮＶ’V’→ε｜[E］E→VE’E’→ε|＋EN→i由LL（1)文法的充要條件可證G’[V]是LＬ(1)文法練習(xí)2：有文法G［s］:S→ＢＡA→BS|dＢ→aＡ|bS｜c(diǎn)(１)證明文法G是ＬL(1）文法。(２)構(gòu)造LL(1）分析表。(3)寫出句子ａdccd的分析過程解:(１)一個(gè)LL（1）文法的充要條件是：對(duì)每一個(gè)非終結(jié)符Ａ的任何兩個(gè)不同產(chǎn)生式A→α｜β,有下面的條件成立：①FＩＲST(α)∩ＦＩRST(β)=Φ;②若β*Tε,則有FIＲSＴ(α)∩FOLＬOＷ(A）=Φ對(duì)于文法G[s]：S→ＢAA→BS|dＢ→aＡ|ｂS|c其FIＲＳT集如下：ＦIRSＴ(B)＝{a,b,c};FIRST(Ａ)={a,b，c，ｄ};FIRST(S）＝{a,b,ｃ}。其FＯLLOW集如下:一方面,FOLLOW(S）＝{#};對(duì)Ｓ→ＢＡ有：ＦＩＲＳT(Ａ)\{ε}加入ＦOLLOＷ(B），即FＯＬLOＷ(B)={ａ,ｂ,ｃ,ｄ};對(duì)Ａ→BＳ有:FIRＳT（S)＼{ε}加入FOLLOW（B),即ＦＯＬLOW(B）＝{a,b,c，d}；對(duì)Ｂ→aA有：FOLLＯW(B)加入FＯLLOW(A),即ＦOLLOＷ(A）={ａ，b,c，ｄ};對(duì)B→bＳ有:FOＬLOW(B）加入FOLLＯW(S),即FOLLOＷ(S)={#,a,b，c，d};由A→BS|d得：FIRST(ＢＳ)∩ＦIRSＴ（d）={a,b,c}∩{ｄ｝=Φ;由B→aＡ|bS|c得:ＦIRST(ａA)∩FIRST(ｂS）∩ＦＩRSＴ(c）={a}∩∩{c｝=Φ。由于文法G[ｓ]不存在形如β→ε的產(chǎn)生式，故無需求解形如FＩRＳT（α)∩FOLLOＷ(A）的值。也即,文法G［S]是一個(gè)ＬＬ(1)文法。（２）由Ｇ［s]:Ｓ→BＡA→BS|dB→aＡ|ｂＳ|c的FIRSＴ（Ｂ）=｛ａ，b,c｝;FOＬLOW(B）={a,b,ｃ,d};ＦＩＲST（A)＝{a，b，c,ｄ｝;FOLLOW（A)={a,b,c,d};ＦIRST(S)={a,ｂ,c}。ＦOLＬＯＷ（Ｓ)={＃,a,b,ｃ,d}可構(gòu)造LL（１)預(yù)測(cè)分析表如下:

aｂｃｄ＃SＳ→BAＳ→BＡS→ＢA

ＡA→BSＡ→BSA→BＳA→d

BB→aＡＢ→bSＢ→c

SS→BAS→ＢAＳ→BA

AＡ→BSA→BＳA→BSＡ→d

ＢB→aＡＢ→ｂSＢ→c

(３）在分析表的控制下,句子adccd的分析過程如下:第五章1已知文法G［S］為:?S→a|∧|（Ｔ）Ｔ→Ｔ,Ｓ|S(１）計(jì)算G[Ｓ]的ＦIＲSTVＴ和LASTＶT。(2)構(gòu)造Ｇ［S]的算符優(yōu)先關(guān)系表并說明G[Ｓ]是否為算符優(yōu)先文法。（3）給出輸入串（a,(a,a)）#的算符優(yōu)先分析過程。解：文法:

S→a|∧|（Ｔ)T→T,S|S展開為：

Ｓ→aS→∧Ｓ→(T）

T→T,ＳT→Ｓ（1）FＩRＳＴVT--LＡSＴVT表非終結(jié)符FＩRＳTVT集LASTＶT集S{ａ∧(}｛ａ∧）}T{a∧(,}{a∧),}(2)算符優(yōu)先關(guān)系表如下：表中無多重入口所以是算符優(yōu)先（OPG）文法。

a∧（),#a

∧?()

,#?≮≮?≮

≮≮?≮?≮≮

≮≯≯≒≯≯≯≯≮≯≯≯≯≯≒(3)輸入串（ａ,(a，a))#的算符優(yōu)先分析過程為:棧當(dāng)前字符剩余輸入串動(dòng)作#?#(?＃(a

＃(Ｎ?#(N,?#(N，(?#(N,(ａ?＃(N，(Ｎ

#(N,(N,

＃（N,(N，ａ?#（N，(Ｎ,N

#(N,(N

#(N，(N）?#(N,N?#(Ｎ?＃(N）

#N(?a

,

,?(?ａ?,

,

a

)

)

)?)

）?)

#

#a,(a，a))#,(a，ａ))＃(a，a）)＃(ａ,a））＃

a，a))#

,a))#?a))#?a）)#)）#

)#?）#?)#?#

＃?＃Mｏveiｎ

Ｍovein?Rｅdｕcｅ:S→a

Moｖeiｎ

Moveｉn?Moｖｅin

Reduce:S→a?Ｍoｖｅin?Moｖeｉｎ

Ｒeduce：Ｓ→a

Reduce:T→Ｔ，S

Moｖｅｉｎ

Redｕce:S→(T)

Rｅduce:Ｔ→Ｔ,S

Movｅiｎ?Reduce:S→(T)第六章例１:有文法:Ｓ→(L）｜aL→L,S|S給此文法配上語義動(dòng)作子程序(或者說為此文法寫一個(gè)語法制導(dǎo)定義),它輸出配對(duì)括號(hào)的個(gè)數(shù)。如對(duì)于句子(ａ，(a，a))，輸出是２。解：加入新開始符號(hào)S'和產(chǎn)生式Ｓ＇→Ｓ,設(shè)num為綜合屬性,代表值屬性,則語法制導(dǎo)定義如下:產(chǎn)生式語義規(guī)則S'→Spｒint(Ｓ.ｎum）S→(L)Ｓ.nuｍ:=L.ｎｕm+１Ｓ→aS.num：=0Ｌ→L1,ＳL.num:=L１.num+Ｓ.ｎｕmL→SＬ．ｎum:=S．nｕm例２:構(gòu)造屬性文法，能對(duì)下面的文法，只運(yùn)用綜合屬性獲得類型信息。D→L，id|LL→TidT→int|reaｌ解:屬性文法（語法制導(dǎo)）定義:產(chǎn)生式語義規(guī)則D→L,idD．tｙpe：=Ｌ.tyｐｅａdｄtype(id.entry，Ｌ．typｅ）D→ＬD.type：=L.tｙpeL→TｉdL．type:=T.ｔypeａddｔype(ｉd．entry,T．ｔｙpe)T→ｉｎｔＴ.type:=integeｒT→rｅａlＴ.tｙpe：=ｒｅaｌ第七章例1：給出下面表達(dá)式的逆波蘭表達(dá)(后綴式)：(1)a*(－ｂ+ｃ)(２)if(x＋ｙ)＊z=0tｈens:=(a＋ｂ)*cｅlses:=a*b*c解:(１)ab-c＋*（2)ｘy+z*0=saｂ＋c*:=sab＊c＊：=￥（注:￥表達(dá)if-then-ｅｌse運(yùn)算)例2:請(qǐng)將表達(dá)式－(a+ｂ)*(ｃ+d）-(a+b）分別表達(dá)成三元式、間接三元式和四元式序列。解:三元式間接三元式(1)(＋a,b)間接三元式序列間接碼表(2)(＋c,ｄ)(1)(+ａ,b)(１）(3)(*(１),(2））(2)(＋c,ｄ）(２）(4）(-(3),／)(3)(*(1）,(２）)(３)(5)（+a，ｂ)（4)(-(3），/)(4)(6)(-(4)，(5))（5)（－(4),（1)）(１)（5)四元式(１)（+,a,b，t1）(２）(+,c,d,t2)（３)(*,t1,t2,t3）(４）(－,t3，／,t4）(5)（+,a，b,ｔ5)(6）(-,t４,ｔ5,t6)例3：請(qǐng)將下列語句ｗhｉle(Ａ＜B)ｄoif（C>D)tｈenX：=Y+Z翻譯成四元式解:假定翻譯的四元式序列從（10０）開始：（10０）ifA＜Bgｏto（１０2）(101）ｇｏtｏ（1０7)（102）ifC>Dｇoｔo（10４)(103）ｇoto(100)（104）T∶＝Y(jié)+Z（105)X∶＝T(106）gotｏ（100）(107)例４:寫出for語句的翻譯方案解:產(chǎn)生式動(dòng)作S→foｒEdoS1S.ｂeｇｉn:＝ｎewｌabｅlＳ.fｉｒst:=ｎｅwteｍpS．lａst：=nｅwtemｐＳ．cｕrr:＝ｎewtempS.ｃｏde:=ｇｅn(S.fiｒst“:=”Ｅ.init)｜|ｇｅn(S.ｌast“：=”E.final）|｜gen(“iｆ”S.ｆirsｔ“>”S．lａst“goto”S．neｘt)|｜gen(S.ｃurr“:=”S.fｉrst)|｜gen(S.beｇｉn“：”)||gｅｎ(“iｆ”S.curr“＞”S.Ｌａｓt“goto”S.neｘt)|｜S1.cｏdｅ|｜gen(Ｓ.curr：=ｓucc(S.ｃurr)）||geｎ(“ｇｏｔo”S．bｅgin)Ｅ→v:=initｉaltｏfinaｌＥ.init:=ｉｎitial.placｅＥ.fiｎａl:=finａl.pｌａce第八章例1：C語言中規(guī)定變量標(biāo)記符的定義可分為exｔern,exterｎstａｔic,ａｕto,ｌocalstatic和ｒｅgisｔeｒ五種存儲(chǔ)類:（１)對(duì)五種存儲(chǔ)類所定義的每種變量，分別說明其作用域。(2)試給出適合上述存儲(chǔ)類變量的內(nèi)存分派方式。（３)符號(hào)表中登記的存儲(chǔ)類屬性，在編譯過程中支持什么樣的語義檢查。解:(１)exterｎ定義的變量，其作用域是整個(gè)C語言程序。extｅrｎsｔａt(yī)ic定義的變量,其作用域是該定義所在的Ｃ程序文獻(xiàn)。ａuｔo定義的變量，其作用域是該定義所在的例程。ｌocａlｓｔａt(yī)ic定義的變量，其作用域是該定義所在的例程。且在退出該例程時(shí),該變量的值仍保存。rｅgiｓtｅr定義的變量，其作用域與auto定義的變量同樣。這種變量的值,在寄存器有條件時(shí)，可存放在寄存器中,以提高運(yùn)營效率。(2）對(duì)extern變量,設(shè)立一個(gè)全局的靜態(tài)公共區(qū)進(jìn)行分派。對(duì)exｔernstatiｃ變量,為每個(gè)C程序文獻(xiàn)，分別設(shè)立一個(gè)局部靜態(tài)公共區(qū)進(jìn)行分派。對(duì)ａuto和ｒegiｓter變量，設(shè)定它們?cè)谠摾痰膭?dòng)態(tài)區(qū)中的相對(duì)區(qū)頭的位移量。而例程動(dòng)態(tài)區(qū)在運(yùn)營時(shí)再做動(dòng)態(tài)分派。對(duì)ｌocaｌｓtａt(yī)ｉｃ變量,為每個(gè)具有這類定義的例程,分別設(shè)立一個(gè)內(nèi)部靜態(tài)區(qū)進(jìn)行分派。(３)實(shí)行標(biāo)記符變量反復(fù)定義合法性檢查，及引用變量的作用域范圍的合法性檢查。第九章例１：下面的程序執(zhí)行時(shí)，輸出的a分別是什么？若參數(shù)的傳遞辦法分別為(1）傳名;(2)傳地址;（3)得結(jié)果;4）傳值。?prｏgrａmmａｉn（input,output)；

pｒｏcedureｐ（x，y,z);?beｇｉn

y∶＝ｙ+１;

z∶=ｚ＋x;

enｄ；?begｉn?a∶=2;?b∶=３;

p(a+b,a，a);?prｉnta

end．解：(1)參數(shù)的傳遞辦法為“傳名”時(shí)，a為9。(2)參數(shù)的傳遞辦法為“傳地址”,ａ為8。(３)參數(shù)的傳遞辦法為“得結(jié)果”，a為7。（4)參數(shù)的傳遞辦法為“傳值”，a為2。例2：過程參數(shù)的傳遞方式有幾種?簡述“傳地址”和“傳值”的實(shí)現(xiàn)原理。解:參數(shù)的傳遞方式有下述幾種：傳值，傳地址，傳名,得結(jié)果“傳值”方式，這是最簡樸的參數(shù)傳遞方法。即將實(shí)參計(jì)算出它的值，然后把它傳給被調(diào)過程。具體來講是這樣的:1．形式參數(shù)當(dāng)作過程的局部變量解決，即在被調(diào)過程的活動(dòng)記錄中開辟了形參的存儲(chǔ)空間,這些存儲(chǔ)位置即是我們所說的實(shí)參或形式單元。２．調(diào)用過程計(jì)算實(shí)參的值,并將它們的右值（r－ｖaluｅ)放在為形式單元開辟的空間中。3．被調(diào)用過程執(zhí)行時(shí)，就像使用局部變量同樣使用這些形式單元?！皞鞯刂贰狈绞?，也稱作傳地址,或引用調(diào)用。調(diào)用過程傳給被調(diào)過程的是指針,指向?qū)崊⒋鎯?chǔ)位置的指針。1．如實(shí)參是一個(gè)名字或是具有左值的表達(dá)式，則左值自身傳遞過去。2.如實(shí)參是一個(gè)表達(dá)式,比方ａ+b或２，而沒有左值，則表達(dá)式先求值，并存入某一位置，然后該位置的地址傳遞過去。3.被調(diào)過程中對(duì)形式參數(shù)的任何引用和賦值都通過傳遞到被調(diào)過程的指針被解決成間接訪問。例3:下面是一個(gè)Paｓcａl程序?pｒｏgramＰP（input,ｏuｔｐｕt)

varK：ｉｎtｅｇer;

funcｔionF(N:ｉntegeｒ):inteｇeｒ

bｅgin

ｉfN<=0thenF:=1?elseF:＝N*Ｆ(Ｎ-1)；?eｎｄ;?begin?Ｋ:=Ｆ(10);

...?end；?當(dāng)?shù)诙危ㄟf歸地）進(jìn)入F后,DISＰLAY的內(nèi)容是什么？當(dāng)時(shí)整個(gè)運(yùn)營棧的內(nèi)容是什么？解:第十章例１:何謂代碼優(yōu)化?進(jìn)行優(yōu)化所需要的基礎(chǔ)是什么？解：對(duì)代碼進(jìn)行等價(jià)變換,使得變換后的代碼運(yùn)營結(jié)果與變換前代碼運(yùn)營結(jié)果相同,而運(yùn)營速度加快或占用存儲(chǔ)空間減少,或兩者都有。優(yōu)化所需要的基礎(chǔ)是在中間代碼生成之后或目的代碼生成之后。例2：編譯過程中可進(jìn)行的優(yōu)化如何分類？最常用的代碼優(yōu)化技術(shù)有哪些？解:依據(jù)優(yōu)化所涉及的程序范圍,可以分為：局部優(yōu)化、循環(huán)優(yōu)化和全局優(yōu)化。最常用的代碼優(yōu)化技術(shù)有1.刪除多余運(yùn)算2.代碼外提３.強(qiáng)度削弱４.變換循環(huán)控制條件5．合并已知量與復(fù)寫傳播６.刪除無用賦值例3:試對(duì)以下基本塊B2:B:=3D:＝Ａ＋CE：=A＊CF:=D＋EG:＝B＊FH:=A+ＣI:=Ａ*CＪ:=H+IK:=Ｂ＊5L：=K+JＭ:=L應(yīng)用DＡG對(duì)它們進(jìn)行優(yōu)化，并就以下兩種情況分別寫出優(yōu)化后的四元式序列:(1）假設(shè)只有G、L、M在基本塊后面還要被引用。（２)假設(shè)只有L在基本塊后面還要被引用。解：基本塊相應(yīng)的DAG如下:Ｂ:=3D:=A+CE:=Ａ＊CF:＝Ｄ+EG:=B*FH：＝A+CI:=A*CＪ:=H+IＫ:＝Ｂ＊5L：=K＋JＭ：=L例1一個(gè)編譯程序的代碼生成要著重考慮哪些問題?解：代碼生成器的設(shè)計(jì)要著重考慮目的代碼的質(zhì)量問題，而衡量目的代碼的質(zhì)量重要從占用空間和執(zhí)行效率兩個(gè)方面綜合考慮。課后習(xí)題答案:Ｐ3６-6(１)是0~9組成的數(shù)字串(２)最左推導(dǎo):最右推導(dǎo):Ｐ36-８文法:最左推導(dǎo):最右推導(dǎo):語法樹:/***＊**＊********＊***＊＊*＊＊**＊*＊**＊P3６－９句子iｉiei有兩個(gè)語法樹:Ｐ64–７（１)XYXYX1X1234Y5110１１擬定化:０１｛X}φ{(diào)１，2,3}φφφ{(diào)1,２，3}{2,3｝{２,３，4｝{２,3}｛2,3}{2,3,4}{２，３,４｝{2,3,5}{2，3,4}｛２,3,5｝{２,3}｛2,3,４,Y}{2,３，4，Y}{２,3,5}{２,3,4｝0320１032010０110165401654０111最小化：０02102100１01543０15430111P６4–１２(a)a10a,b10a擬定化：ａb{0}{0,１}{1}{0，1｝{0,1}｛１｝{1｝｛0}φφφφ給狀態(tài)編號(hào)：aｂ0１2112203３33ａ10a10ａｂbb3232ba最小化：aa210bb210ab(b)032bba032ａbａab541ba541aa已經(jīng)擬定化了,進(jìn)行最小化最小化：021bｂa021abａP81–１(1)按照T,S的順序消除左遞歸遞歸子程序:ｐｒocedｕreS;ｂｅｇｉｎ?ifsｙｍ='a'orｓym=＇^' ?ｔheｎabvａｎcｅ elseｉｆsｙｍ=＇(' ??thenｂeｇiｎ? ?adｖance；Ｔ； ?? ｉfｓｙｍ=＇)'theｎaｄvaｎｃe;?? ??elseerrｏr;???end ? elseerrorend;procｅdｕreＴ;beｇiｎ S;enｄ;ｐrocedure;ｂｅgiｎ?ifsｙｍ=＇,'??thｅnbｅgｉn? advａｎcｅ；? ?Ｓ； ?ｅndend；其中:ｓym：是輸入串指針ＩP所指的符號(hào)adｖａnce：是把ＩＰ調(diào)至下一個(gè)輸入符號(hào)erｒor:是犯錯(cuò)診察程序(2)ＦＩRST(S)＝{a，^，（}ＦＩRST(T)={ａ,^，(｝FIＲSＴ()＝{,,｝ＦOLLOW(S)={),，,＃｝ＦOＬＬＯＷ(Ｔ)={)｝FOLLOW（)={)}預(yù)測(cè)分析表a^(),#ＳT是ＬL(１）文法 P81–2文法：(1)FIRST(Ｅ）=｛（,a,b,^}ＦＩRＳT(E')={＋,ε}ＦＩRST(T)=｛(,a,ｂ,^｝FIRST(Ｔ＇）=｛(,a，b,^，ε}FIRST(F）＝{（,ａ,ｂ，^}FIRＳT(Ｆ')={＊,ε｝FIＲST(P)=｛(,a，ｂ,＾}FＯＬＬOＷ(Ｅ）={#,）}FＯＬＬＯW(E')={#,)｝FOLLOW（Ｔ)={＋,),＃｝ＦＯＬLOW(Ｔ')=｛+,)，＃｝FＯLＬOＷ(F)={(，a，b,^,＋,)，#｝FOＬLOW(F＇)={(,a,b，＾,+,),＃}FOLLOW(Ｐ)={*,（,a,b,^,＋,),#}(2)考慮下列產(chǎn)生式:FIRＳT(+E）∩FIRST（ε)={+｝∩{ε}=φＦＩRST(+E）∩FOLLOW(E')={＋}∩｛#,)｝=φＦIRST(T)∩FIＲST(ε)={(,a，b,^}∩{ε}=φＦＩＲSＴ(T)∩FＯLLＯW(T'）=｛(,a,b,^}∩{+,）,＃}=φFIRST(＊Ｆ＇)∩FＩRST(ε)=｛*}∩{ε}=φFIRSＴ(*F＇）∩FOLLOW(F')＝｛＊}∩{(,ａ，ｂ，^,+,),＃}=φFIRSＴ(（E))∩ＦIＲＳT(a）∩FIRST(b)∩ＦIRST（^)=φ所以,該文法式LL(1）文法.（3)+*（）ab＾#EE'TT'FＦ'P（4)prｏｃｅdureE;beｇin ifｓym='('orsｙm=＇a＇orｓｙm='b'orsyｍ='^＇?tｈenｂeginＴ;E'ｅnd elｓｅe(cuò)ｒrorｅndproceduｒeE';beｇｉｎ?ifsym='+'?ｔｈeｎbｅginaｄｖａnce;Ｅend elseifsym<＞')＇aｎdsym＜>＇#'thenerroｒｅｎdproｃeｄureＴ；bｅｇiｎ?ifsym=＇(＇oｒsym＝＇a'oｒｓym=＇ｂ'orsym＝'^' ｔheｎbegiｎＦ;T'end?elseｅrｒorend?proceｄuｒeＴ'；begiｎ ifsyｍ='('orsyｍ='a'orｓym＝'b'ｏrｓym='^＇?theｎＴ?elseｉfsym=＇*'ｔhenｅrrｏreｎdpｒocｅduｒｅF;ｂｅｇｉn ｉfｓym='('oｒｓym='a'orｓym=＇b＇orsyｍ＝＇^' theｎbｅgｉnP;F'eｎｄ?elsｅe(cuò)ｒｒｏrend?proｃedureF＇;ｂegin ifsyｍ＝＇*'?ｔhenbeginａdvａnｃe;F'ｅnｄｅndprocedｕrｅP;bｅgin?ifｓym='a'orｓym='b'orsym='＾＇?thenａdvance?elseifｓｙm='('tｈen ?beｇin ??advancｅ;E;???ifsｙｍ=')'ｔhenadvａnce? ?elseerror??end??elｓeerrorend;P１3３–1短語:E＋T*F,Ｔ*F,直接短語:T*F句柄:Ｔ*FＰ１33–２文法：(１)最左推導(dǎo)：最右推導(dǎo):(２)（(（a,a),^,(ａ)),a）(((Ｓ，a),^,(a）)，a)(((T,a）,^,(ａ）),a）(((T,S),^,（a))，a）(((T）,＾,(a)),ａ）((Ｓ,^,（ａ)）,a）((T,^,(a))，a)((T,S,(a)），a）(（T，（a))，a)(（T,(S)),a）((T,(T)),ａ)((Ｔ,S)，ａ)((T),a)(S,a)(T,Ｓ）（Ｔ)S“移進(jìn)-歸約”過程：環(huán)節(jié) 棧 ?輸入串 ? 動(dòng)作0 ＃ ?(（（a，a),^，(a)),a)＃??預(yù)備1??#（ ((a,a),^,(a)),a)# 進(jìn)2 ＃(( ?(ａ，ａ)，＾,(ａ）),a)#? ?進(jìn)3 ?#((( ? a，a）,＾，（a)),a)＃?? 進(jìn)4 ?#(((ａ ,a）,^,（a）),a)＃ ?? 進(jìn)5 ?#（((S ?,a),^,(a)),a)# ???歸６ ?＃（（(T??,a),^,(ａ)),ａ)＃????歸７ ＃(（(T, a),^，(a）),a)#????進(jìn)８? ＃(((Ｔ,a ?),^,(a)),ａ)# ? 進(jìn)9??#(((T,S ),^,(ａ))，ａ)#????歸10 ?#((（T ),^，（ａ)）,ａ)#??? 歸11??#（（（T)??,^,（a)),a)#? 進(jìn)12 ?#((S ，^,(a)）,ａ)# ? 歸13 ＃((T ? ,^,（a)),ａ）# ??歸14? #((T,??^，(ａ)）,a）＃?????進(jìn)1５??#（(T，＾ ?，(ａ))，a)＃? ???進(jìn)16 ?＃(（T,Ｓ ,(a)）,a）# ? ? 歸17 ?＃((Ｔ?? ,(a)）,a）＃ ? 歸1８ #(（Ｔ,? （a)),a)＃ ?? ?進(jìn)19??#（（T,(? a)),ａ)# ?? ?進(jìn)20??＃（(T，(ａ ?）),a)#?? ?進(jìn)21 ?＃((Ｔ,（S? ）),a)＃? 歸２2 #((Ｔ,(T??)),a）# ??? 歸２3? ＃((T,(Ｔ） ?)，ａ)#? ??進(jìn)24 ?#((T,S ),ａ)# ?歸25 ＃((Ｔ ?),a)# ? ?歸26 ?#((Ｔ) ，a)#? ???進(jìn)２７? #（S ? ，ａ)# ? ?歸２8 ?＃（T ?,a)# ????歸29??#（Ｔ,???a)＃?? ?進(jìn)30 ?#(T，a ?)＃? ? ??進(jìn)31 ?＃(T,Ｓ? )#??? ? ?歸32 ?#（T ?)#? ?歸33? #(T) ??# ?進(jìn)3４ ?#S? #? ?? 歸Ｐ13３–3（1)FＩRSTＶT（S）={a，^，(}FIＲSＴＶT(Ｔ）={，,a，^，(}LAＳTVT（S)＝{ａ,^，)｝ＬASTVT（T）={,,a，^，）}（2)ａ＾(),a>>^>>（<＜＜=<)>>，<<＜>>是算符文法,并且是算符優(yōu)先文法(3）優(yōu)先函數(shù)a^()，f４42４4g55523 ? ? ?? ??? （4)棧 ?? 輸入字符串 ? 動(dòng)作# ? ? ? （a,（a,ａ））# ? 預(yù)備#(? ? ???a，(a,ａ))＃ ? ?進(jìn)#(ａ?? ?? ??,(a，a))#?? 進(jìn)#（s ?? ?? ,（a,ａ))＃?? 歸#（ｔ ?? ? ?,(a,a）)#?? 歸#（t,? ?? ?(a,a）)#?? 進(jìn)＃(t,( ? ?a,a））＃ ?進(jìn)#（ｔ,(a ? ,ａ））＃? ? ?進(jìn)＃（t,（s ? ? ,a)）# ??? 歸＃（t,(t ?? ??,ａ))#??? 歸#（ｔ,(t，? ????a)）# ? 進(jìn)＃（ｔ,（t,a??? ?）)# ? ??進(jìn)#（t,（ｔ,ｓ? )）# ? 歸＃(t,（ｔ? ??))# ??歸#（t,（t) ? ）# ? 進(jìn)#(t,s???? )# ? ? 歸#（t ? ??）#?? ? ?歸＃（ｔ?) ? ??# ? 進(jìn)#s ? ? ?#??? ?歸P164–1答:表達(dá)式(4*７+１）*２的附注語法樹如下圖：digit.lexval=2F.val=2Edigit.lexval=2F.val=2E.val=58ndigit.lexval=4digit.lexval=7digit.lexval=1F.val=4F.val=7F.val=1T.val=4*T.val=28E.val=28+T.val=1E.val=1E.val=29()F.val=29T.val=29T.val=58*L答:(1)aab+(２）aab+P1６5–11答:(1)D→idL ?{D.type:=L.type;addtype（id.type,L．type)}L→,ｉdＬ1? ｛Ｌ．ｔyｐe:=Ｌ1.type;addtｙpe(ｉd.type，L１.ｔype）}L→：T?? ｛L．typｅ:=Ｔ.type}T→iｎteger? {T．type:=iｎteger}T→rｅａl? ?{T.tｙpe:=reａl}P217–1a＊（-b+c)?? ? HYPERＬINKmａiｌto:ab@c+＊ａｂ@ｃ＋*a+ｂ＊(c+d/e)? ? ?abcde/+*+-a+b*(-ｃ+d)???? HYPERLＩＮKmａilｔo:a@ｂc@d＋＊+a@bｃ@d+*+A（CornotD)?? ? AnｏtCD not?ornoｔ ｏｒ (AanｄB)or（noｔCorD) ?ABａｎdCnotDoror(AorＢ)ａnd（ＣornｏtDandE)??ABｏrCDnｏtEanｄorand?if(x+y)＊z=0theｎ(a+ｂ)↑c(diǎn)ｅlseａ↑b↑ｃ xy+ｚ*0＝ab＋c↑abc↑↑￥ ??或ｘy+z*0=Ｐ１jｅzab+c↑P2jumpabｃ↑↑P1P2P217–3-(a＋b)*（ｃ+ｄ)-（a＋b+c)的三元式序列：＋,a,b＠,(1),-+,ｃ，d＊，(2),(3)＋,a,b+,(5),c－,(4）,(６)間接三元式序列:三元式表：+，a,b@,(1),－+,c,d*,(2）,（3)＋,(1）,c－,（4),(5）間接碼表:(1）(２)（３)(４)(1）(5)（６)四元式序列:+,a,b,@,,－,＋,c,d,*,，,+,a,