2023年編譯原理期末復(fù)習(xí)

千里之行，始于足下讓知識(shí)帶有溫度。第第2頁/共2頁精品文檔推薦編譯原理期末復(fù)習(xí)編譯原理期末復(fù)習(xí)

鑒于編譯原理馬上就要期末考試，我將手中集中的一些資料上的題目舉行了收拾歸類，每種類型題目給出了所涉及到的基本學(xué)問，然后對每類題目中的第一道例題舉行了做法舉行了講解，剩下的例題請給大家作為練習(xí)，答案也都給出，希翼對大家復(fù)習(xí)有所協(xié)助，最后因?yàn)闀r(shí)光很緊，收拾的有些倉促，收拾中難免有遺漏或錯(cuò)誤，請大家見諒。

注：下面浮現(xiàn)的字母中，若無特殊說明，小寫英文字母為終結(jié)符，大寫英文字母為非終結(jié)符，希臘字母為終結(jié)符與非終結(jié)符的隨意組合。

1、簡答題（或者名詞解釋）

下面涉及到的概念中，加下劃線的都是在以往一些試卷中浮現(xiàn)的原題，務(wù)必把握。

注：這類題目教師說答案不會(huì)超過一百個(gè)字，否則寫的再多也不給分，有些點(diǎn)到即可，不要重復(fù)啰嗦。（1）簡述編譯程序的概念及其構(gòu)成

答：1）編譯程序：它特指把某種高級程序設(shè)計(jì)語言翻譯成等價(jià)的低級程序設(shè)計(jì)語言的翻譯程序。

2)構(gòu)成：

（2）簡述詞法分析階段的主要任務(wù)（也有可能問語法分析階段主要任務(wù)）答：詞法分析的任務(wù)是輸入源程序，對源程序舉行掃描，識(shí)別其中的單詞符號，把字符串形式的源程序轉(zhuǎn)換成單詞符號形式的源程序。

語法分析的主要任務(wù)是對輸入的單詞符號舉行語法分析（按照語規(guī)矩則舉行推導(dǎo)或者歸約），識(shí)別各類語法單位，推斷輸入是不是語法上正確的程序

(3)簡述編譯程序的構(gòu)造過程（這個(gè)大家看看，是對（1）和（2）的綜合）

答：1）構(gòu)造詞法分析器：用于輸入源程序舉行詞法分析，輸出單詞符號；

2）構(gòu)造語法分析器：對輸入的單詞符號舉行語法分析，識(shí)別各類語法單位，推斷輸入是不是語法上正確的程序

3）構(gòu)造語義分析和中間代碼產(chǎn)生器：根據(jù)語義規(guī)章對已歸約出的語法單位舉行語義分析并把它們翻譯成中間代碼。

4）構(gòu)造優(yōu)化器：對中間代碼舉行優(yōu)化。

5)構(gòu)造目標(biāo)代碼生成器：把中間的代碼翻譯成目標(biāo)程序。

6)構(gòu)造表格管理程序：記下源程序的各類信息和編譯各階段的發(fā)展?fàn)顩r。

7)構(gòu)造錯(cuò)誤處理程序：對出錯(cuò)舉行處理。

(4)說明編譯和解釋的區(qū)分：

1)編譯要程序產(chǎn)生目標(biāo)程序，解釋程序是邊解釋邊執(zhí)行，不產(chǎn)生目標(biāo)程序；

2)編譯程序運(yùn)行效率高而解釋程序便于人機(jī)對話。

（5）文法：描述語言語法結(jié)構(gòu)的形式規(guī)章，普通用一個(gè)四元式表示：G=(VT，VN，S，P)，其中VT：終結(jié)符集合(非空)VN：非終結(jié)符集合(非空)，且VT?VN=?S：文法的開頭符號，S?VNP：產(chǎn)生式集合(有限)。

（6）二義性文法：一個(gè)文法中存某個(gè)句子，它有兩個(gè)不同的最左（或者最右推導(dǎo)），則稱該文法是二義性的。例子如文法G：S→ifexprthenS|other

S→ifexprthenSelseS句子ife1thenife2thens1elses2

是二義性的。

（7）文法的形式（注：文法的形式一定要銘記，特殊是2型和3型文法一定要銘記，不僅在概念題中實(shí)用，在下面的按照語言寫文法題中也有重要作用，假如所寫的文法形式不對，一切都是無用功……）

1）0型文法(短語文法，圖靈機(jī))：產(chǎn)生式形式為：???，其中：??(VT?VN)*且至少含有一個(gè)非終結(jié)符；??(VT?VN)*

2）1型(上下文有關(guān)文法，線性界限自動(dòng)機(jī))：產(chǎn)生式形式為:???其中：|?|?|?|，僅S??例外但是S不得浮現(xiàn)在任何產(chǎn)生式右部。

3）2型文法（上下文無關(guān)文法，非確定下推自動(dòng)機(jī))：產(chǎn)生式形式為：P??，P?VN，??(VT?VN)*

。4）3型文法(正規(guī)文法，有限自動(dòng)機(jī))：右線性文法：產(chǎn)生式形如：A??B或A??其中：??VT*

；A，B?VN左線性文法：產(chǎn)生式形如：A?B?或A??其中：??VT*

；A，B?VN

例題：設(shè)G=(VT，VN，S，P)是一個(gè)上下文無關(guān)文法，產(chǎn)生集合P中的任一個(gè)產(chǎn)生式應(yīng)具有什么樣的形式？若G是1型文法呢？若G是正則文法呢？

上下文無關(guān)文法，產(chǎn)生式形式為：P??，P?VN，??(VT?VN)*。

1型文法：產(chǎn)生式形式為:???其中：|?|?|?|，僅S??例外。

正則文法：右線性文法：產(chǎn)生式形如：A??B或A??其中：??VT*

；A，B?VN

左線性文法：產(chǎn)生式形如：A?B?或A??其中：??VT*；A，B?VN(8)什么是PDA(下推自動(dòng)機(jī))?

答：PDA是下推自動(dòng)機(jī)，PDAM用一個(gè)七元組表示(K,Σ,f,H,h0,S,Z)K:有窮狀態(tài)集?：輸入字母表(有窮)H:下推棧符號的有窮字母表

h0:H中的初始符號f:K?（Σ?{?})?H–>K?H*S：屬于K是初始狀態(tài)。Z:包含于K，是終結(jié)狀態(tài)集合。(9)什么是DFA（有窮狀態(tài)自動(dòng)機(jī)）?

自動(dòng)機(jī)M是一個(gè)五元式M=(S,?,f,S0,F),其中：1）S:有窮狀態(tài)集，2）?：輸入字母表(有窮)，

3）f:狀態(tài)轉(zhuǎn)換函數(shù)，為S???S的單值部分映射，f(s，a)=s’表示：當(dāng)現(xiàn)行狀態(tài)為s，

輸入字符為a時(shí)，將狀態(tài)轉(zhuǎn)換到下一狀態(tài)s’。我們把s’稱為s的一個(gè)后繼狀態(tài)。4）S0?S是唯一的一個(gè)初態(tài)；5）F?S：終態(tài)集(可空)。

（10）推導(dǎo)：所謂推導(dǎo)就是對于一個(gè)含非終結(jié)符A的符號串，利用規(guī)章A→α，把A替換成α得到新符號串的過程。

最左推導(dǎo)：在推導(dǎo)的每一步，挑選符號串最左邊的非終結(jié)符舉行替換。最右推導(dǎo)：在推導(dǎo)的每一步，挑選符號串最右邊的非終結(jié)符舉行替換。(11)歸約：歸約是推倒的逆過程，即用產(chǎn)生式的左部非終結(jié)符替換右部符號串。(12)什么是句型？什么稱為句子？什么是語言？

句型：從文法的起始符號動(dòng)身，經(jīng)過有限步的推導(dǎo)能夠推導(dǎo)出來的符號稱為句子。句子：只由終結(jié)符構(gòu)成的句型稱為句子。語言：全部句子的集合構(gòu)成該文法描述的語言。

(13)什么是短語？什么是直接短語（也稱為容易短語）？什么是句柄？什么是素短語？什么是最左素短語？（以下幾個(gè)概念一定要理解，考試中絕對會(huì)考哪些是短語，直接短語，句柄等，詳細(xì)辦法請參見后面的）短語：假如存在某個(gè)文法非終結(jié)符P,滿足S*

?βPγ,并且P+

?α則稱α為句型βαγ相對于非終結(jié)符P的

短語。

直接短語：假如P?α,即從P動(dòng)身一步推出α，則α稱為直接短語。句柄：一個(gè)句型的最左直接短語稱為該句型的句柄。

素短語：至少含有一個(gè)終結(jié)符的短語，并且除了自身外，不包含更小的素短語。

最左素短語：句型中最左邊的素短語。

（14）自頂向下的語法分析辦法中需要解決的主要問題什么？如何表示？

答：1）主要需要解決回溯和左遞歸問題。

2）表示方式，回溯：文法中存在形如A→α1|α2|…|αn,即產(chǎn)生式右部存在多個(gè)候選，導(dǎo)致推導(dǎo)時(shí)不能確定到底應(yīng)當(dāng)挑選哪個(gè)候選式。

左遞歸：文法中存在形如P→Pα的形式，推導(dǎo)時(shí)會(huì)導(dǎo)致推導(dǎo)過程無休止的舉行下去。

注：解決辦法，對回溯實(shí)行的是提取左公因子，對左遞歸使消退左遞歸（包括直接左遞歸和間接左遞歸）。

(15)內(nèi)情向量：普通編譯程序?qū)?shù)組說明的處理是把數(shù)組的有關(guān)信息匯合在一個(gè)叫做“內(nèi)情向量”或“信息向量”的表格中，以便以后計(jì)算數(shù)組元素的地址時(shí)引用這些信息。每個(gè)數(shù)組有一個(gè)內(nèi)情向量。其中的信息包括，數(shù)組的類型，維數(shù)，各維的上、下界，以及數(shù)組的首地址。

（16）C語言的活動(dòng)記錄：

OldSP

返回地址

參數(shù)個(gè)數(shù)

形式單元

局部變量

內(nèi)情向量

暫時(shí)單元SP

TOP

2、最左最右推導(dǎo)，畫語法樹，找短語、直接短語、句柄等。

這種題目很容易，送分題，一定不能丟分！

考題：1）文法G[S]為：S→SdT|TT→T0}對應(yīng)文法S→aS|a假如是n>=0則為S→aS|ε(ε是空字)

{anbn|n>0}對應(yīng)文法S→aSb|ab

下面這四道題目老是在試卷中重復(fù)浮現(xiàn)，所以大家好好看看。

考題

1、按指定類型給出下列語言的文法,并指出語言的類型。（10分）

(1)L1={anbmcn|n≥0,m>0}

二型文法：S→aSc|BB→bB|b

(2)L2={0na1nbmcm|n>0，m≥0}

二型文法：S→ABA→0A1|0a1B→bBc|ε2、按指定類型給出下列語言的文法。（10分）

(1)L1={candbm|n≥0,m>0}用正規(guī)文法。

S→cAA→aA|dBB→bB|b(2)L2={0na1nbmcm|n>0,m≥0}用二型文法。

S→ABA→0A1|0a1B→bBc|ε

3、按指定的類型給出下列語言的文法（10分）

(1)L1={canbm|n≥0,m>0}用正規(guī)文法。

S→cAA→aA|BB→bB|b4、按指定的類型給出下列語言的文法（10分）

(1)L1={anbmc|n>=0,m>0}用正規(guī)文

法

(2)L2={0na1nbm|n>0，m≥0}用二型文法。S→ABA→0A1|0a1B→bB|ε

S→aS|AA→bA|bBB→c(2)L2={a0n1nbdm|n>0,m>0}用二型

文法

S→ABA→aTT→0T1|01

B→bDD→dD|d

這是書P36第11題的答案如下：大家作為練習(xí)，可以發(fā)覺比上述題目容易的多了。

或者G4:

4、詞法分析——

—正規(guī)式、NFA和

DFA之間的轉(zhuǎn)化：

（1）這類題目普通是三者之間的轉(zhuǎn)換，正規(guī)

式→NFA→確定化的DFA→最小化的DFA，有時(shí)已經(jīng)給出NFA了，則只需要確定化為DFA和最小化就行了，普通每一步都是五分。詳細(xì)怎么轉(zhuǎn)換請參照我期中考試時(shí)收拾的提綱，主要就是下面這幅關(guān)系對比圖，因時(shí)光和篇幅限制不再追溯。

（2）注重優(yōu)先級關(guān)系，閉包運(yùn)算*最高，銜接運(yùn)算.次之，或運(yùn)算|最低。

(3)考題1：

1）構(gòu)造正則式a*b|(ab)*b對應(yīng)的DFA。（15分）

①畫出NFA

②確定化DFA

XIaIb{X,1,2,3,4}{1,2,5}{Y}{1,2,5}{1,2}{3,4,Y}{Y}--

{1,2}{1,2}{Y}

{3,4,Y}{5}{Y}{5}-{3,4}

{3,4}{5}{Y}XIaIb

ABC

BDE

C--

DDC

EFC

F-G

GFC

注：C和E是終態(tài)

③最小化DFA

首先將集合分為{A,B,D,F,G},{C,E}。{A,B,D,G}都有a,b作為條件輸出，F(xiàn)惟獨(dú)b輸出，所以分為{A,B,D,G}和{F}同理{C,E}分為{C},{E}。{A,B,D}a={B,D}{G}a={F}所以{A,B,D,G}分為{A,B,D}和{G}。{A}b={C}

{B,D}a={D}所以分為{A}{B,D}

綜上所述：劃分的結(jié)果為{A},{B,D},{C},{E},{G}.

考題2：將NFA確定化為DFA(10分)

NFA:DFA:

IaIb{X,0,1,3}{0,2,1,3}{3,Y}{0,2,1,3}{0,2,1,3}{1,3,Y}{3,Y}Ф{Y}

ab

SAB

AAC

BФE

CDE

DФF

EФФ

G1:

S→AC

A→aAb|abC→cC|εG2:

S→AB

A→aA|ε

B→bBc|bc

G3:

S→AB

A→aAb|ε

B→aAb|ε

G4:

S→1S0|A

A→0A1|ε

{1,3,Y}{2}{Y}

{2}Ф{1,3}

{Y}ФФ

{1,3}{2}{Y}

含有Y的狀態(tài)子集為DFA的終態(tài),上例中的終態(tài)有B,C,E.

題目中要求是確定化，沒有要求最小化，如若最小化，劃分的集合為{S,A},{B,C}

{F},{D},{E}然后再畫出最小化后的DFA這里不再贅述。

考題3：構(gòu)造奇數(shù)個(gè)0和奇數(shù)個(gè)1組成的自動(dòng)機(jī)。（10分）

狀態(tài)1：偶數(shù)個(gè)0偶數(shù)個(gè)1狀態(tài)2：奇數(shù)個(gè)0偶數(shù)個(gè)1

狀態(tài)3：奇數(shù)個(gè)0奇數(shù)個(gè)1狀態(tài)4：偶數(shù)個(gè)0奇數(shù)個(gè)1

假如題目改成偶數(shù)個(gè)0，奇數(shù)個(gè)1，只要將狀態(tài)4轉(zhuǎn)換成終態(tài)即可，其他類似。

5、語法分析——自頂向下分析法（LL（1）分析法和遞歸向下構(gòu)造子程序法）

注：自頂向下分析法本質(zhì)是由開頭符號，根據(jù)產(chǎn)生式逐步推導(dǎo)看能否產(chǎn)生需要分析的句子。

（1）自頂向下分析中存在的問題

左遞歸和回溯（詳細(xì)請參見簡答題中的第（14）題）

（2）消退回溯——提取公因子法

提取公共左因子:假定關(guān)于A的規(guī)章A→??1|??2|…|??n|?1|?2|…|?m(其中，每個(gè)?不以?開始)那么，可以把這些規(guī)章改寫成A→?A?|?1|?2|…|?m

A?→?1|?2|…|?n

（3）消退左遞歸

1)消退直接左遞歸：直接消退見諸于產(chǎn)生式中的左遞歸：假定關(guān)于非終結(jié)符P的規(guī)章為P→P?|?，其中?不以P開始。我們可以把P的規(guī)章等價(jià)地改寫為如下的非直接左遞歸形式：P→?P?P?→?P?|?

注：普通而言，假定P關(guān)于的所有產(chǎn)生式是P→P?1|P?2|…|P?m|?1|?2|…|?n

其中，每個(gè)?都不等于?，每個(gè)?都不以P開始那么，消退P的直接左遞歸性就是把這些規(guī)章改寫成：P→?1P?|?2P?|…|?nP?P?→?1P?|?2P?|…|?mP?|?

例：文法G(E):

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

經(jīng)消去直接左遞歸后變成：

E→TE?E?→+TE?|?T→FT?T?→*FT?|?F→(E)|i

2)消退間接左遞歸

這個(gè)請參見我期中收拾的提綱篇幅較多，這里不再重復(fù)贅述，請參照下面的考題2?？碱}1：將文法G[S]改寫為等價(jià)的G’[S],使得G’[S]不含左遞歸和左公因子。

S→[AA→B]|ASB→aB|a

答：消退左遞歸和左公因子后的文法為：

S→[AA→B]A’A’→SA’|?B→aB’B’→B|?

考題2：寫出文法G[A]:A→Ba|Cb|cB→dA|Ae|fC→Bg|h消退左遞歸后的文法。

答：(1)經(jīng)分析發(fā)覺文法G[A]并無直接左遞歸；

(2)消退間接左遞歸：將A,B,C根據(jù)B,C,A排序（建議將A放在最后）因?yàn)楦‖F(xiàn)C→Bg形式，將B代入C

得：C→dAg|Aeg|fg|h又因?yàn)锳浮現(xiàn)A→BaA→Cb將B,C帶入A得到：A→dAa|Aea|fa|dAgb|Aegb|fgb|hb|c等價(jià)于A→Aea|Aegb|dAa|fa|dAgb|fgb|hb|c

將A消退直接左遞歸A→dAaA’|faA’|dAgbA’|fgbA’|hbA’|cA’A’→eaA’|egbA’|?

此時(shí)，對于B→dA|Ae|f，C→dAg|Aeg|fg|h因?yàn)槲丛谌魏萎a(chǎn)生式的右部浮現(xiàn)，所以是多余的。

綜上所述:消退遞歸后的文法為：A→dAaA’|faA’|dAgbA’|fgbA’|hbA’|cA’

A’→eaA’|egbA’|?

(4)LL(1)分析法

1）含義：LL(1)分析辦法（也叫預(yù)測分析法）：是指從左到右掃描、最左推導(dǎo)(LL)和只查看一個(gè)當(dāng)前符號（括號中的1）。

2）推斷一個(gè)文法是否是LL(1)文法的充要條件：

1.文法不含左遞歸，

2.對于文法中每一個(gè)非終結(jié)符A的各個(gè)產(chǎn)生式的候選首符集兩兩不相交。即，若

A→?1|?2|…|?n則FIRST(?i)∩FIRST(?j)＝?(i?j)

3.對文法中的每個(gè)非終結(jié)符A，若它存在某個(gè)候選首符集包含?，則FIRST(?

i

)∩FOLLOW(A)=?i=1,2,...,n假如一個(gè)文法G滿足以上條件，則稱該文法G為LL(1)文法。

(5)LL(1)文法分析表的構(gòu)造與運(yùn)用

這類題目，主要就是推斷文法是否滿足LL(1)文法的三個(gè)充要條件，分為以下幾步：

1）首先將文法分解，推斷是否有左遞歸好，有的話絕對不是LL(1)文法；

2）算非終結(jié)符的First集合和Follow集合，詳細(xì)辦法請參見期中考試的提綱，其實(shí)最本質(zhì)的要抓住first集

合是U

*

?a…，F(xiàn)ollow集合石…Ua…即可。

3）算Select集合，書上沒有提到Select集合，計(jì)算Select集合實(shí)質(zhì)就是計(jì)算First(?)，固然考試時(shí)不一定非要寫成Select集合形式，可以直接計(jì)算First(?)來推斷交集是否為空，從而是否為LL(1)文法，請看考題1。

4）至于推斷一個(gè)句子的分析過程，大家注重一下，所給的句子不一定是能通過該文法分析出來的，實(shí)際上在分析之前可以自己按照文法推推看，請看考題1.

5）分析表中沒有填的空格代表出錯(cuò)，假如分析時(shí)碰到了代表該句子不符合該文法。

考題1：推斷下面文法是否為LL(1)文法，若是，請構(gòu)造相應(yīng)的LL(1)分析表并分析句子aabe的分析過程。（15分）

S→aDD→STe|εT→bMM→bHH→M|ε

分析：推斷一個(gè)文法是否為LL(1)文法是否為LL(1)文法，主要就是推斷是否滿足LL(1)文法的充要條件，有一個(gè)不滿足就不是LL(1)文法。對于aabe按照文法S?aD?aSTe?aaDTe?aaTe?aabMe因?yàn)镸不能為空字ε，所以最后絕對推不出來，也就是該句子不能由該文法推出，出錯(cuò)。

固然普通題目都是LL(1)文法，否則題目就不好往下做，沒故意義。

答：(1)經(jīng)分析該文法無左遞歸；

(2)①非終結(jié)符的First和Follow集合如下表所示

非終結(jié)符XFirst(X)Follow(X)

Sa#b

Dεa#b

Tbe

Mbe

Hεbe

②將文法分解為：S→aDD→SteD→εT→bMM→bHH→MH→ε

依次計(jì)算：

First(aD)={a}First(Ste)={a}

Follow(D)={#b}First(bM)=

First(bH)=First(M)=Follow(H)={e}

∵First(Ste)∩Follow(D)=ФFirst(M)∩Follow(H)=Ф

∴該文法是LL(1)文法

LL(1)分析表如下：

abe#

SS→aD

DD→STeD→εD→ε

TT→bM

MM→bH

HH→MH→ε

(3)aabe的分析過程如下：

步驟符號棧輸入串所用產(chǎn)生式

0#Saabe#

1#Daaabe#S→aD

2#Dabe#

3#eTSabe#D→STe

4#eTDaabe#

5#eTDbe#

6#eTbe#D→ε

7#eMbbe#T→bM

8#eMe#出錯(cuò)

考題2：推斷下面文法是不是LL(1)文法，若是請構(gòu)造相應(yīng)的LL(1)分析表，寫出aaabd的分析過程。S→aHH→aMd|dM→Ab|?A→aM|e

答：（1）可以推斷該文法無左遞歸。

（2）將文法分解為分解：S→aHH→aMdH→dM→AbM→?A→aMA→e求First和Follow集合

非終結(jié)符XFirst(X)Follow(X)

Sa#

Ha,d#

M

?,a,e

d,b

Aa,eb

求Select集合

Select(S→aH)=First(aH)={a}Select(H→aMd)=First(aMd)={a}

Select(H→d)=tbbdx9vSelect(M→Ab)=First(Ab)={a,e}

Select(M→?)=First(?)UFollow(M)=Follow(M)={d,b}

Select(A→aM)=First{aM}={a}Select(A→e)=First(e)={e}

∵Select(H→aMd)∩Select(H→d)=Ф

Select(M→Ab)∩Select(M→e)=Ф

Select(A→aM)∩Select(A→e)=Ф

∴該文法是LL(1)文法。

（3）LL(1)分析表如下：

ad

be

SS→aH

HH→aMdH→d

MM→AbM→?M→?M→Ab

AA→aMA→e

aaabd#的分析過程如下：

步驟符號棧輸入串所用產(chǎn)生式

0#Saaabd#

1#Haaaabd#S→aH

2#Haabd#

3#dMaaabd#H→aMd

4#dMabd#

5#dbAabd#M→Ab

6#dbMaabd#A→aM

7#dbMbd#

8#dbbd#M→?

9#dd#

10##

考題3：構(gòu)造LL(1)分析辦法的總控流程圖

6、構(gòu)造遞歸下降識(shí)別程序

這類題目首先看文法有無左遞歸和左公因子，有的話一定要消退，我期中給大家的答案錯(cuò)了，考題1為更正后的答案。

考題1：為文法G[E]：E→V|V+EV→N|N[E]N→i構(gòu)造遞歸下降識(shí)別程序（10分）

解：（1）提取左公因子：E→VE’E’→+E|?V→NV’V’→[E]|?N→i

(3)構(gòu)造遞歸下降識(shí)別程序

PROCEDUREE；BEGIN

V;E’?

END;PROCEDUREE’；

IFSYM=‘+’THEN

BEGIN

ADVANCE；

E

PROCEDUREＶ；

BEGIN

N;V’

END;

END

PROCEDUREF；

IFSYM=‘[’THEN

BEGIN

ADVANCE;

E；

IFSYM=‘]’

THEN

ADVANCE

ELSEERROREND

ELSEERROR;PROCEDUREN；IFSYM=‘i’THEN

ADVANCEELSEERROR;

考題2：為文法G[E]:E→E+T|TT→T*F|FF→(E)|i構(gòu)造遞歸下降識(shí)別程序

解：（1）消退左遞歸：E→TE'E'→+TE'|εT→FT'T'→*FT'|εF→(E)|i

(2)構(gòu)造遞歸下降識(shí)別程序

PROCEDUREE；BEGIN

T；E'END；PROCEDURET；

BEGIN

F；T'

END

PROCEDUREF；

IFSYM=‘i’THEN

ADVANCE

ELSE

IFSYM=‘(’THEN

BEGIN

ADVANCE;

E；

IFSYM=‘)’

THENADVANCE

ELSEERROR

END

ELSEERROR;

PROCEDUREE'；

IFSYM=‘+’THEN

BEGIN

ADVANCE；

T；E'

ENDPROCEDURET'；

IFSYM=‘*’THEN

BEGIN

ADVANCE；

F；T'

END

7、自底向上分析法——LR（0）分析法

注：自底向上分析法本質(zhì)是從輸入串開頭，逐步舉行“歸約”，直到文法的開頭符號,其關(guān)鍵問題是尋覓句柄。

自底向上分析法還有算符優(yōu)先分析法，SLR(1),LR（1）等等，教師那天重點(diǎn)講了一道LR(0)分析法的題目，他說算符優(yōu)先分析法A卷不考，但是補(bǔ)考的B卷會(huì)考，根據(jù)他的意思，這次期末考試LR(0)是考定的了，

SLR(1),LR（1）應(yīng)當(dāng)不考，由于LR(0)分析法個(gè)人感覺也是全部題目中最繁的了，下面已教師講的題目為例這，也是一份試卷上的考題，首先介紹一些相關(guān)學(xué)問。

（1）LR(0)項(xiàng)目：通俗點(diǎn)講，文法G中的任何一個(gè)產(chǎn)生式的右部的任何位置添加一個(gè)圓點(diǎn)就成了LR(0)項(xiàng)目，比如A→Ab是產(chǎn)生式，則A→?AbA→A?bA→Ab?都是該產(chǎn)生式對應(yīng)的所有項(xiàng)目。項(xiàng)目動(dòng)態(tài)的表示歸約的一個(gè)階段：對于項(xiàng)目A→A?b，可以這樣理解它：“?”之前的A表示的是在識(shí)別Ab過程中已輸入到棧終的部分；“?”之后的表示在識(shí)別Ab過程中期望浮現(xiàn)的部分；“?”表示則是在識(shí)別Ab過程中當(dāng)前的識(shí)別進(jìn)度的定位。項(xiàng)目A→Ab?已經(jīng)具備了識(shí)別Ab的一切條件，因此被稱為歸約項(xiàng)目。

項(xiàng)目可以分為以下四類：P→α?aβ稱為移進(jìn)項(xiàng)目其中,P→α?Xβ稱為待約項(xiàng)目，其中X為非終結(jié)符，P→α?

稱為歸約項(xiàng)目，S’→S稱為接收項(xiàng)目

（2）LR(0)的分析?？梢钥闯蓛刹糠譅顟B(tài)棧

LR分析器的核心是一張分析表：

ACTION[s，a]：當(dāng)狀態(tài)s面臨輸入符號a時(shí)，應(yīng)實(shí)行什么動(dòng)作.

GOTO[s，X]：狀態(tài)s面向文法符號X時(shí)，下一狀態(tài)是什么.

下面幾張PPT大家看看，對基本概念有個(gè)印象：

這一章的概念較多較抽象，我一時(shí)半會(huì)也講不完講不清晰，這里不再贅述，直接看題目，知道怎么做就行，下面以一道考題這也是教師講的原題為例講解如何做這類題目，首先普通這種題目分三步走：

(1)拓廣文法：假定文法G是一個(gè)以S為開頭符號的文法，我們構(gòu)造一個(gè)G'，它包含了囫圇G，但它引進(jìn)了一個(gè)不浮現(xiàn)在G中的非終結(jié)符S'，并加進(jìn)一個(gè)新產(chǎn)生式S'→S，而這個(gè)S'是G'的開頭符號。那么，我們稱G'是G的拓廣文法。這樣，便會(huì)有一個(gè)僅含項(xiàng)目S'→S.的狀態(tài)，這就是唯一的“接受”態(tài)。

（2）構(gòu)造識(shí)別文法活前綴的DFA:對于隨意的項(xiàng)目即I,其閉包CLOSURE(I)計(jì)算辦法如下，I中的全部項(xiàng)目都屬于CLOSURE(I);假如P→α?Xβ,并且X為非終結(jié)符，則全部形如X→?γ的項(xiàng)目也屬于ClOSURE(I)定義函數(shù)GO(I,X)，其中I是項(xiàng)目集，X是隨意的文法符號（終結(jié)符，非終結(jié)符都可以），GO(I，X)=CLOSURE(J).J是從I中項(xiàng)目動(dòng)身后讀取X后到達(dá)的后繼項(xiàng)目,即J={P→αX?β|P→α?Xβ∈I}

有了上述CLOSURE和GO的定以后，從CLOSURE({S'→?S})動(dòng)身，利用GO函數(shù)，產(chǎn)生出它在每個(gè)可能的文法符號下，要轉(zhuǎn)移的項(xiàng)目集，再對新產(chǎn)生的項(xiàng)目集實(shí)行同樣的辦法直到?jīng)]有新產(chǎn)生的項(xiàng)目集未被處理為止。

(4)按照計(jì)算出的項(xiàng)目集之間的關(guān)系畫出DFA和LR(0)分析表，其中LR(0)構(gòu)造辦法如

下:

(5)對詳細(xì)的句子運(yùn)用LR(0)分析的辦法如下：

每一項(xiàng)ACTION[s，a]所規(guī)定的四種動(dòng)作:

1.移進(jìn)把(s，a)的下一狀態(tài)s’和輸入符號a推動(dòng)棧，下一輸入符號變成現(xiàn)行輸入

符號.

2.歸約指用某產(chǎn)生式A→β舉行歸約.假若β的長度為r，歸約動(dòng)作是，去除

棧頂r個(gè)項(xiàng)，使?fàn)顟B(tài)sm-r變成棧頂狀態(tài)，然后把(sm-r,A)的下一狀態(tài)s’=GOTO[sm-r,A]和文法符號A推動(dòng)棧.

3.接受（即acc）宣布分析勝利，停止分析器工作.

4.報(bào)錯(cuò)

考題：構(gòu)造文法G[E]的LR(0)分析表，并給出accd的分析過程。

（0）S'→E（1）E→aA（2）E→bB（3）A→cA（4）A→d（5）B→cB（6）B→d

分析：題中已經(jīng)舉行了推廣文法，所以第一步就不需要了，下面就是開頭構(gòu)造識(shí)別活前綴的DFA，然后構(gòu)造出LR（0）分析表，最后在舉行分析，實(shí)際上對于accd我們自己可以先推一下，E?aA?acA?accA?accd所以該句子符合文法，那么終于構(gòu)造出的LR（0）分析表對該句子舉行分析后必然得到“acc”（接受的意思），否則構(gòu)造的LR(0)分析表出錯(cuò)。

答：（1）構(gòu)造識(shí)別活前綴的DFA:

I0=Closure({S'→?E})={S'→?E,E→?aA,E→?bB}

I1=GO(I0,E)=Closure({S'→E?})={S'→E?}

I2=GO(I0,a)=Closure({E→a?A})={E→a?A，A→?cA，A→?d}

I3=GO(I0,b)=Closure({E→b?B})={E→b?B,B→?cB，B→?d}

（為了便利，下面計(jì)算中的Closure不再寫了，直接給出答案,考試時(shí)可以不寫，固然計(jì)算I0是必需要的）I4=GO(I2,A)={E→aA?}I5=GO(I2,c)={A→c?A，A→?cA，A→?d}

I6=GO(I2,d)={A→d?}I7=GO(I3,B)={E→bB?}

I8=GO(I3,c)={B→c?B，B→?cB，B→?d}I9=GO(I3,d)={B→d?}

I10=GO(I5,A)={A→cA?}GO(I5,c)=I5GO(I5.d)=I6

I11=GO(I8,B){B→cB?}GO(I8,c)=I8GO(I8.d)=I9

畫出DFA:

注：實(shí)際上構(gòu)造LR(0)分析表時(shí)這個(gè)圖沒有須要畫，按照上述計(jì)算結(jié)果即可填寫下表。

（2）畫出LR(0)分析表

注：至于怎么填這個(gè)表請參見上一頁中的PPT,這里不再贅述,Action表中si代表跳轉(zhuǎn)到第i個(gè)狀態(tài)，ri代表挑選文法中第i條規(guī)章舉行歸約,acc代表接受，即分析勝利。Goto表中數(shù)字i代表跳轉(zhuǎn)到第i個(gè)狀態(tài)。（3）對accd#舉行分析

步驟分析棧輸入串操作

1#0accd#s2

2#0a2ccd#s5

3#0a2c5cd#s5

4#0a2c5c

5d#s6

5#0a2c5c5d

6#r4

6#0a2c5c5A10#r3

7#0a2c5A10#r3

8#0a2A4#r1

9#0E1#acc

8、寫出表達(dá)式或者程序的中間形式

逆波蘭式和四元式是三地址代碼的兩種記錄表現(xiàn)形式，固然表示形式還有三元式、間接三元式等等，按照教師的意思應(yīng)當(dāng)不考，四元式和逆波蘭式必考。

（1）逆波蘭表達(dá)式

逆波蘭表達(dá)式即后綴表達(dá)式，就是中綴表達(dá)式（也就是我們普通看到的表達(dá)式形式）對應(yīng)的后續(xù)遍歷結(jié)果，這個(gè)辦法有無數(shù)，個(gè)人認(rèn)為搞清晰運(yùn)算優(yōu)先級，觀看一下就可寫出，先算誰就將其對應(yīng)的操作數(shù)寫出，運(yùn)算符放在后面就行很容易：

例如：寫出下列各式的逆波蘭表示

（1）-a-(b*c/(c-d)+(-b)*a)

(2)-A+B*C↑(D/E)/F

解：（1）a@bc*cd-/b@a*+-（2）A@BCDE/↑*F/+

注：@代表負(fù)號“-”

（2）四元式

四元式形式如下（op,arg1,arg2,Result）從左至右分離代表運(yùn)算符，第一操作數(shù)，其次操作數(shù),運(yùn)算結(jié)果。

如：A+B*(C-D)+E/(C-D)^N對應(yīng)的四元式序列如下:

四元式:(1)(-,C,D,T1)(2)(*,B,T1,T2)

(3)(+,A,T2,T3)(4)(-,C,D,T4)

(5)(^,T4,N,T5)(6)(/,E,T5,T6)

(7)(+,T3,T6,T7)

注：T1,T2等等位存放結(jié)果的暫時(shí)變量。

條件語句等四元式的表示

（jnz,a,--,p)表示ifagotop

(jrop,x,y,p)表示ifxropygotop（rop代表關(guān)系運(yùn)算符，如等等）(j,--,,p)表示gotop

例如：寫出條件語句IFa>0THENx:=x+1ELSEx:=4*(x-1)四元式序列

解：

(1)(j>,a,0,(3))

(2)(j,-,-,(6))

(3)(+,x,1,T1)

(4)(:=,T1,-,T2)

(5)(j,-,-,(9))

(6)(-,x,1,T3)

(7)(*,4,T3,T4)

(8)(:=,T4,-,x)

(9)

注重：（5）和（9）不能寫丟，否則一分沒有！上述四元式中其次第三個(gè)位置的“-”代表沒有元素。

其實(shí)四元式就是對上述程序舉行解釋，假如滿足則跳轉(zhuǎn)到哪里執(zhí)行，不滿足則跳轉(zhuǎn)到哪里執(zhí)行，大家自己分析一下，應(yīng)當(dāng)能夠看懂。

考題：按照要求寫出下列表達(dá)式的中間形式。

（1）5+6*（a+b）寫出表達(dá)式的逆波蘭式逆波蘭表達(dá)式為：56ab+*+

（2）

答案（1）答案（2）

ifx>ythen{

y:=y-1;

x：=y*z+10

}

else

x:=z+y

寫出上述代碼的四元式

或者三址碼。

（有的試卷上問法是寫出下列表達(dá)式三地址形式的中間表示，答案一樣）(0)(j>,x,y,(2))

(1)(j,-,-,(8))

(2)(-,y,1,T1)

(3)(:=,T1,-,y)

(4)(*,y,z,T2)

(5)(+,T2,10,T3)

(6)(:=,T3,-,x)

(7)(j,-,-,(10))

(8)(+,z,y,T4)

(9)(:=,T4,-,x)

(10)

100:ifx>ygoto102

101:goto108

102:T1:=y-1

103:y:=T1

104:T2:=y*z

105:T3:=T2+10

106:x:=T3

107:goto110

108:T4:=z+y

109:x:=T4

110:

注重：同上題，本題答案加紅色的部分此外上述編號任意，從0開頭也行從100開頭也行。不能丟，否則一分沒有！

9、參數(shù)傳遞

這種題目很容易，是送分題，一定要做對！

參數(shù)傳遞方式分為三種，值傳遞，地址傳遞和傳名。

值傳遞過程中形參值的轉(zhuǎn)變不會(huì)影響實(shí)參值的轉(zhuǎn)變，地址傳遞形參值的轉(zhuǎn)變導(dǎo)致對應(yīng)是實(shí)參值的轉(zhuǎn)變，傳名傳遞類似于C語言中的宏綻開，將實(shí)參原封不動(dòng)的替換相應(yīng)的形參（文字替換）。

請看下題：

(1)高級語言程序中常用的參數(shù)傳遞方式有哪些？請按照這些傳遞方式寫出程序的運(yùn)行結(jié)果。

staticinta=1;

intp(intx,inty,intz){

y=y+1;

z=z+x;

cout<<"InP"<{

inta