編譯原理教案(存儲(chǔ)版)

　　

【正文】 時(shí)間 第7周 第34節(jié)第8周 第14節(jié) 第9周 第14節(jié)第10周 第14節(jié)第11周 第12節(jié)教學(xué)目的、要求（分掌握、熟悉、了解三個(gè)層次）：熟悉自下而上分析思想了解算符優(yōu)先分析法掌握LR分析法教學(xué)重點(diǎn)和難點(diǎn)：自下而上分析思想、算符優(yōu)先分析法、LR分析法授課類型（請(qǐng)打√）：理論課254。我們可用句柄來(lái)刻畫(huà)移進(jìn)—?dú)w約過(guò)程的“可歸約串”。＋β則稱β是句型αβδ相對(duì)于非終結(jié)符A的短語(yǔ)。請(qǐng)注意句柄的“最左”特征，這一點(diǎn)對(duì)于移進(jìn)—?dú)w約來(lái)說(shuō)是重要的。也就是說(shuō)，算符優(yōu)先分析法不是一種規(guī)范歸約法。對(duì)于任何一對(duì)終結(jié)符a、b，我們說(shuō)：（1） a=b 當(dāng)且僅當(dāng)文法G中含有形如P174。…Rb…的產(chǎn)生式， R而R222。 通過(guò)檢查G的每個(gè)產(chǎn)生式的每個(gè)候選式，可以找出滿足a=VN } LASTVT(P)={a | P222。FISTVT(P),我們有aFIRSTVT(P)(2)若a206。Xi+2 IF Xi為終結(jié)符而Xi+1為非終結(jié)符 THEN FOR FISTVT(Xi+1)中的每個(gè)a DO 置 XiQ)進(jìn)行歸約。(3)檢查所構(gòu)造出來(lái)的函數(shù)f和g，看它們同原來(lái)的關(guān)系表是否有矛盾。其缺點(diǎn)是，原先不存在優(yōu)先關(guān)系的兩個(gè)終結(jié)符，由于與自然數(shù)相對(duì)應(yīng)，變成可比較的了。ACTONIs，a]規(guī)定了當(dāng)狀態(tài)s面臨輸入符號(hào)a時(shí)應(yīng)采取什么動(dòng)作。歸約動(dòng)作不改變現(xiàn)行輸入符號(hào)。棧的每一項(xiàng)內(nèi)容包括狀態(tài)s和文法符號(hào)X兩部分。 文法G的每一個(gè)產(chǎn)生式右部添加一個(gè)圓點(diǎn)就稱為G的一個(gè)LR(0)項(xiàng)目。那么，我們稱G39。使用LR(0) 表的分析器叫做一個(gè)LR(0)分析器。α?}LR(0)項(xiàng)目集，若Follow(A) ∩Follow(B)= f且b 207。 規(guī)范LR分析表的構(gòu)造在構(gòu)造SLR分析表的方法中，若項(xiàng)目集Ik中含有A174。?對(duì)策：給每個(gè)LR(0)項(xiàng)目添加展望信息，即：添加句柄之后可能跟的終結(jié)符，因?yàn)檫@些終結(jié)符確實(shí)是規(guī)范句型中跟在句柄之后的。 二義文法的應(yīng)用 任何二義文法決不是一個(gè)LR文法，因而也不是SLR或LALR文法。發(fā)現(xiàn)錯(cuò)誤后，便進(jìn)入相應(yīng)的出錯(cuò)處理子程序。 其他□教學(xué)資源（請(qǐng)打√）：多媒體254。都有一套與之相關(guān)聯(lián)的語(yǔ)義規(guī)則，每條語(yǔ)義規(guī)則的形式為： b:=f(c1,c2,…,ck) 這里f是一個(gè)函數(shù)，而且或者 （1）b是A的一個(gè)綜合屬性并且c1,c2,…,ck是產(chǎn)生式右邊文法符號(hào)的屬性； 或者 （2）b是產(chǎn)生式右邊某個(gè)文法符號(hào)的一個(gè)繼承屬性并且c1,c2,…，ck是A或 產(chǎn)生式右邊任何文法符號(hào)的屬性 在這兩種情況下，我們都說(shuō)屬性b依賴于屬性c1,c2，…,ck.： 在語(yǔ)法樹(shù)中，一個(gè)結(jié)點(diǎn)的綜合屬性的值由其子結(jié)點(diǎn)的屬性值確定。依賴圖中為每一個(gè)屬性設(shè)置一個(gè)結(jié)點(diǎn)，如果屬性b依賴屬性c，則從屬性c的結(jié)點(diǎn)有一條有向邊連到屬性b的結(jié)點(diǎn)。 下面我們討論分析棧中的綜合屬性。 后綴式后綴式表示法是波蘭邏輯學(xué)家盧卡西維奇發(fā)明的一種表示表達(dá)式的方法，因此又稱逆波蘭表示法。 圖表示法 這里的圖表示法包括DAG（無(wú)循環(huán)有向圖）與抽象語(yǔ)法樹(shù)。對(duì)每個(gè)局部名字，我們都將在符號(hào)表中建立相應(yīng)的表項(xiàng)，并填入有關(guān)的信息如類型、在存儲(chǔ)器中的相對(duì)地址等。在處理第一條說(shuō)明語(yǔ)句之前，先置offset為0，以后每次遇到一個(gè)新的名字，便將該名字填入符號(hào)表中并置相對(duì)地址為當(dāng)前offset之值，然后使offset加上該名字所表示的數(shù)據(jù)對(duì)象的域?qū)挕Ｖ羔榩revious 之值放在新符號(hào)表表頭，表頭中還可存放一些其它信息如過(guò)程嵌套深度等。產(chǎn)生式D174。作為翻譯賦值語(yǔ)句為三地址代碼的一個(gè)部分，我們將討論如何在符號(hào)表中查找名字及如何存取數(shù)組和記錄的元素。假定數(shù)組的每個(gè)元素的寬度為w，則一維數(shù)組A[i] 這個(gè)元素的起始地址為： base + (i – low)*w （）其中l(wèi)ow為數(shù)組下標(biāo)的下界， 并且base是分配給數(shù)組的相對(duì)地址，即base為A的第一個(gè)元素A[low]的相對(duì)地址。其目的是使我們?cè)谡麄€(gè)下標(biāo)表達(dá)式串Elist的翻譯過(guò)程中隨時(shí)都知道符號(hào)表中相應(yīng)于數(shù)組名字id的全部信息。 記錄中域的作用 編譯器必須將記錄中的域的類型和相對(duì)地址保持下來(lái)。于是p的類型是record(t)，t可由此先取出來(lái)。如果類型像圖4．8和圖4．9一樣構(gòu)造，則p173。 （ …( ( i1*n2 +i2)n3)…)nm + im利用如下的遞歸公式進(jìn)行計(jì)算： e1 = i1, em = em1* nm + im于是 當(dāng)m=k時(shí)將ek乘以元素的寬度w便可計(jì)算出（）的第一個(gè)子項(xiàng)。 id 出現(xiàn)的地方也允許下面產(chǎn)生式中的L出現(xiàn)，則可把數(shù)組元素引用加入到賦值語(yǔ)句中。 數(shù)組元素的引用現(xiàn)在討論包括數(shù)組元素的表達(dá)式和賦值語(yǔ)句的翻譯問(wèn)題。有關(guān)類型構(gòu)造符和類型表達(dá)式概念將在4．7節(jié)介紹。 記錄中的域名 當(dāng)遇到保留字record時(shí)，與標(biāo)記非終結(jié)符號(hào)I相應(yīng)的語(yǔ)義動(dòng)作為記錄中的各域名創(chuàng)建一張新的記錄符號(hào)表。在下面的語(yǔ)義規(guī)則中用到如下操作： (1)mktable(previous)創(chuàng)建一張新符號(hào)表，并返回指向新表的一個(gè)指針。從而我們需要一個(gè)全程變量如offset來(lái)跟蹤下一個(gè)可用的相對(duì)地址的位置。符號(hào)標(biāo)號(hào)代表存放中間代碼的數(shù)組中三地址代碼語(yǔ)句的下標(biāo)。只要我們知道每個(gè)算符的目數(shù)，對(duì)于后綴式，不論從哪一端進(jìn)行掃描，都能對(duì)它正確進(jìn)行唯一分解。L—屬性文法允許通過(guò)一次遍歷就計(jì)算出所有屬性值。XY對(duì)應(yīng)的語(yǔ)義規(guī)則還有： :=g(,) 那么，圖中還應(yīng)有兩條有向邊，,. S—屬性文法的自下而上計(jì)算 這一節(jié)我們考慮這樣一類屬性文法：S—屬性文法，它只含有綜合屬性。在一顆語(yǔ)法樹(shù)中的結(jié)點(diǎn)的繼承屬性和綜合屬性之間的相互依賴關(guān)系可以用稱作依賴圖的一個(gè)有向圖來(lái)描述。屬性加工的過(guò)程即是語(yǔ)義處理的過(guò)程，對(duì)于文法的每一個(gè)產(chǎn)生式都配備了一組屬性的計(jì)算規(guī)則，則稱為語(yǔ)義規(guī)則。 其他□教學(xué)方式（請(qǐng)打√）：講授254。用這種方法改變算符的優(yōu)先級(jí)是非常方便的。對(duì)于ALGOL一類語(yǔ)言來(lái)說(shuō)，一般要用幾百個(gè)狀態(tài)，但若用規(guī)范LR分析表，同一類語(yǔ)言，卻要用幾千個(gè)狀態(tài)。因此此時(shí)用A174。 Follow(B)，按B174。δ?bβ , A174。 由于假定LR(0) 文法規(guī)范族的每一個(gè)項(xiàng)目集不含沖突項(xiàng)目，因此，按上述方法構(gòu)造的分析表的每一個(gè)入口都是唯一的（即不含多重定義）。 是G39。所謂活前綴是指規(guī)范句型的一個(gè)前綴，這種前綴不含句柄之后的任何符號(hào)。不管什么分析表，總控程序都是一樣地工作。b進(jìn)行歸約。這張分析表包括兩部分，一是“動(dòng)作”(ACTION)表，另一是“狀態(tài)轉(zhuǎn)換”(G0TO)表。b，則f(a) g(b).在實(shí)際實(shí)現(xiàn)算符優(yōu)先分析算法時(shí)，一般不用上述這樣的優(yōu)先表，而是用兩個(gè)優(yōu)先函數(shù)f和g相對(duì)應(yīng)，函數(shù)f稱為人棧優(yōu)先函數(shù)，g稱為比較優(yōu)先函數(shù)。(2)對(duì)每個(gè)結(jié)點(diǎn)都賦予一個(gè)數(shù)，此數(shù)等于從該結(jié)點(diǎn)出發(fā)所能到達(dá)結(jié)點(diǎn)(包括出發(fā)結(jié)點(diǎn)自身在內(nèi))的個(gè)數(shù)。由于非終結(jié)符對(duì)歸約沒(méi)有影響，因此，非終結(jié)符根本可以不進(jìn)符號(hào)棧S。X1X2…Xn FOR i:=1 TO n1 DO BEGIN IF Xi 和 Xi+1 均為終結(jié)符THEN 置 Xi=a…或P174。的所有終結(jié)符對(duì)。+Qa…,a206。b 則稱G是一個(gè)算符優(yōu)先文法。Qb…。在后面的定義中，a、b代表任意終結(jié)符；P、Q、R代表任意非終結(jié)符；‘…’代表有終結(jié)符和非終結(jié)符組成的任意序列，包括空字。這種方法特別有利于表達(dá)式分析，宜于手工實(shí)現(xiàn)。由規(guī)范推導(dǎo)所得的句型稱為規(guī)范句型。 句柄：令G是一個(gè)文法，S是文法的開(kāi)始符號(hào)，假定αβδ是文法G的一個(gè)句型，如果有S222。 模型□ 實(shí)物□ 掛圖□ 音像□ 其他□討論、思考題、作業(yè)：P133：1，2，3，5教學(xué)內(nèi)容第三章 語(yǔ)法分析程序自下而上分析所謂自下而上分析法就是從輸入串開(kāi)始，逐步進(jìn)行“歸約”，直至歸約到文法的開(kāi)始符號(hào)；或者說(shuō)從語(yǔ)法樹(shù)的末端開(kāi)始，步步向上“歸約”，直到根結(jié)。(5)如果不能匹配棧頂?shù)慕K結(jié)符號(hào)，一種簡(jiǎn)單的想法是彈出棧頂?shù)倪@個(gè)終結(jié)符號(hào)，并發(fā)出一條信息，說(shuō)明已經(jīng)插入這個(gè)終結(jié)符，繼續(xù)進(jìn)行語(yǔ)法分析。(1)把FOLLOW(A)中的所有符號(hào)放人非終結(jié)符A的同步符號(hào)集。 LL(1)分析中的錯(cuò)誤處理 我們以預(yù)測(cè)分析為例。j ） (3) 對(duì)文法中每一個(gè)終結(jié)符A，若它存在某個(gè)候選首符集包含ε，則 FIRST(A) 199。VT}特別是，若S222。FIRST(aj) = f那么，當(dāng)要求A匹配輸入串時(shí)，A 就能根據(jù)它所面臨的第一個(gè)輸入符號(hào)a，準(zhǔn)確地指派某個(gè)候選前去執(zhí)行任務(wù)。前面已經(jīng)說(shuō)過(guò)，欲實(shí)行自上而下的分析，文法不得含左遞歸。 自上而下分析面臨的問(wèn)題 本節(jié)主要是通過(guò)例子使我們認(rèn)識(shí)到，作自上而下分析所遇到的主要困難是語(yǔ)法的左遞歸性使分析陷入無(wú)限循環(huán)；回溯的不確定性，要求我們將已經(jīng)完成工作推倒重來(lái)，為解決這些問(wèn)題我們要消除左遞歸和消除回溯。 其他□教學(xué)方式（請(qǐng)打√）：講授254。這一方面意味著，必須存在含P的句型；也就是，從開(kāi)始符號(hào)出發(fā)，存在推導(dǎo) S222。其中P,P1, …,Pn ∈ VN, α, β, γ,δ ∈ (VN∪ VT)*。+ Pα,則稱該文法含有左遞歸。 1型文法：也稱上下文有關(guān)文法，對(duì)非終結(jié)符進(jìn)行替換時(shí)務(wù)必聯(lián)系上下文，并且一般不允許替換成空串。這樣的一棵語(yǔ)法樹(shù)是這些不同推導(dǎo)過(guò)程的共性抽象，是它們的代表。語(yǔ)法樹(shù)有助于理解一個(gè)句子語(yǔ)法結(jié)構(gòu)的層次。例如，“算術(shù)表達(dá)式”、“布爾表達(dá)式”、“賦值句”、“分程序”、“過(guò)程”等，它們都是現(xiàn)今程序語(yǔ)言常見(jiàn)的語(yǔ)法范疇。我們可以用一種圖示化的方法來(lái)表示這種推導(dǎo)，說(shuō)明He gave me a book是一個(gè)語(yǔ)法正確的句子。再對(duì)‘(E+E)’中的E相繼兩次使用規(guī)則Ei之后，我們就有(E) 222。’表示“直接推出”，這樣，這句話就可表示為:E222。在后面的討論中，根據(jù)不同情況，我們將用大寫(xiě)字母A、B、C…或漢語(yǔ)詞組(如，算術(shù)表達(dá)式)代表非終結(jié)符號(hào)，特別是用小寫(xiě)字母a、b、c…代表終結(jié)符，用α、β、γ等代表由終結(jié)符和非終結(jié)符組成的符號(hào)串。這些構(gòu)造編譯程序的工具稱為編譯程序——編譯程序、編譯程序產(chǎn)生器或翻譯程序書(shū)寫(xiě)系統(tǒng)，它們是按對(duì)源程序和目標(biāo)語(yǔ)言(或機(jī)器)的形式描述(作為輸入數(shù)據(jù))而自動(dòng)產(chǎn)生編譯程序的。例如，令i 代表已定義的范疇“變量”，那么，產(chǎn)生式 算術(shù)表達(dá)式174。 語(yǔ)言LEX的一般描述 一個(gè)LEX源程序主要包括兩部分。S，是一個(gè)終態(tài)集（可空）。 一個(gè)DFA可用一個(gè)矩陣表示，該矩陣的行表示狀態(tài)，列表示輸入字符，矩陣元素表示f（s，a）的值，這個(gè)矩陣稱為狀態(tài)轉(zhuǎn)換矩陣。兩個(gè)等價(jià)的正規(guī)式U和V記為U=V。不包含任何字符的序列稱為空字，記為ε。C39。下面我們將引進(jìn)一組全局變量和過(guò)程，把它們作為實(shí)現(xiàn)轉(zhuǎn)換圖的基本成分。箭弧上的標(biāo)記（字符）代表在射出結(jié)(即箭弧始節(jié))狀態(tài)下可能出現(xiàn)的輸入字符或字符類。 詞法分析器下面我們來(lái)介紹一下單詞符號(hào)識(shí)別的一個(gè)簡(jiǎn)單方法——超前搜索。 詞法分析器的設(shè)計(jì) 我們將按照詞法分析的任務(wù)和作為一個(gè)獨(dú)立子程序的要求來(lái)考慮詞法分析器的設(shè)計(jì)。 標(biāo)識(shí)符一般統(tǒng)歸為一種。 討論課□ 實(shí)驗(yàn)課254。意思是，先對(duì)語(yǔ)言的核心部分構(gòu)造一個(gè)小小的編譯程序（可用手編實(shí)現(xiàn)），再以它為工具構(gòu)造一個(gè)能夠編譯更多語(yǔ)言成分的較大編譯程序。為了發(fā)揮各種不同硬件系統(tǒng)的效率，為了滿足各種不同的具體要求，現(xiàn)在許多人仍然采用這種工具來(lái)構(gòu)造編譯程序。編譯程序與這些程序設(shè)計(jì)工具一起構(gòu)成所謂的程序設(shè)計(jì)環(huán)境。然而，由于不同語(yǔ)言存在某些微妙的區(qū)別，因此在這方面所取得的成果還非常有限。 編譯前端與后端 概念上，我們有時(shí)把編譯程序劃分為編譯前端和編譯后端。 當(dāng)一遍中包含若干階段時(shí)，各階段的工作是穿插進(jìn)行的。例如，詞法分析階段能夠檢測(cè)出“非法字符”之類的錯(cuò)誤；語(yǔ)法分析階段能夠檢測(cè)出諸如“括號(hào)不匹配”、“缺少；”之類的錯(cuò)誤。如果源程序有錯(cuò)誤，編譯程序應(yīng)設(shè)法發(fā)現(xiàn)錯(cuò)誤，把有關(guān)錯(cuò)誤信息報(bào)告給用戶。例如，一個(gè)名字是常量名、變量名，還是過(guò)程名等等；如果是變量名，它的類型是什么、所占內(nèi)存是多大、地址是什么等等。 編譯程序總框 編譯程序的結(jié)構(gòu)可以按照這五個(gè)階段的任務(wù)分模塊進(jìn)行設(shè)計(jì)。實(shí)際上，許多編譯程序的構(gòu)造與實(shí)現(xiàn)技術(shù)同樣適用于解釋程序。 討論□ 示教□ 指導(dǎo)254。第一章 引論 什么叫編譯程序？ 通常所說(shuō)的翻譯程序是指這樣的一個(gè)程序，它能夠把某一種語(yǔ)言程序(稱為源語(yǔ)言程序)轉(zhuǎn)換成另一種語(yǔ)言程序(稱為目標(biāo)語(yǔ)言程序)，而后者與前者在邏輯上是等價(jià)的。現(xiàn)在很多編譯程序同時(shí)提供了調(diào)試、優(yōu)化等多種功能，用戶可以通過(guò)“開(kāi)關(guān)”進(jìn)行選擇。在編譯程序使用的表格中，最合理的是符號(hào)表。但這時(shí)不能完全確定名字的屬性，它的各種屬性要在后續(xù)的各階段才能填人。如果不僅能夠發(fā)現(xiàn)錯(cuò)誤，而且還能自動(dòng)校正錯(cuò)、誤，那當(dāng)然就更好了。 遍 遍:是對(duì)源程序或源程序的中間結(jié)果從頭到尾掃描一次，并作有關(guān)的加工處理，生產(chǎn)新的中間結(jié)果或目標(biāo)程序。 一個(gè)編譯程序究竟應(yīng)分成幾遍，如何劃分，是與源語(yǔ)言、設(shè)計(jì)要求、硬件設(shè)備等諸因素有關(guān)的，因此難于統(tǒng)一劃定。后端包括編譯程序中與目標(biāo)機(jī)有關(guān)的那些部分，如與目標(biāo)機(jī)有關(guān)的代碼優(yōu)化和目標(biāo)代碼生成等。編譯前端與不同的編譯后端以Diana為界面，實(shí)現(xiàn)編譯程序的目標(biāo)機(jī)改變。一個(gè)集成化的程序設(shè)計(jì)環(huán)境的特點(diǎn)是，它將相互獨(dú)立的程序設(shè)計(jì)工具集成起來(lái)，以便為程序員提供完整的、一體化的支持，從而進(jìn)一步提高程序開(kāi)發(fā)效率，改善程序質(zhì)量。 人們已經(jīng)建立了多種編制