【正文】 在此意義下，利用上一節(jié)圖4．9中的語義動作可為每一個記錄類型建立一張單獨(dú)的符號表。前一子項(xiàng)隨i1, i2 而改變是一個變數(shù)。文法中end之后的語義動作是將offset的棧頂?shù)目傆驅(qū)捵鳛榫C合屬性T．width的值。假定整數(shù)類型域?qū)挒?；實(shí)數(shù)域?qū)挒?；一個數(shù)組的域?qū)捒梢酝ㄟ^把數(shù)組元素?cái)?shù)目與一個元素的域?qū)捪喑双@得；每個指針類型的域?qū)捈俣橐?增加。對于后面給出的三地址代碼中，用戶定義的名字在實(shí)際實(shí)現(xiàn)時將由指向符號表中的相應(yīng)名字入口的指針?biāo)妗，F(xiàn)在我們可以在分析棧中使用一個附域來存放綜合屬性值。 35＋4n ： 在語法樹中，一個結(jié)點(diǎn)的繼承屬性由此結(jié)點(diǎn)的父結(jié)點(diǎn)和/或兄弟結(jié)點(diǎn)的某些屬性確定。授課題目（教學(xué)章、節(jié)或主題）：第四章 語法制導(dǎo)翻譯和中間代碼產(chǎn)生課時安排8授課時間 第11周 第4節(jié) 第12周 第14節(jié)第13周 第2節(jié)教學(xué)目的、要求（分掌握、熟悉、了解三個層次）：理解屬性文法的定義，語法制導(dǎo)翻譯方法熟悉中間代碼的形式掌握中間代碼形式變換掌握簡單賦值語句的翻譯、布爾表達(dá)式的翻譯、控制語句的翻譯教學(xué)重點(diǎn)和難點(diǎn)：屬性文法的定義，屬性的計(jì)算、中間代碼的形式、簡單賦值語句的翻譯、布爾表達(dá)式的翻譯、控制語句的翻譯授課類型（請打√）：理論課254。這本質(zhì)上是一種折衷方法。即在構(gòu)造LR分析表的算法中做一些改變：1）若當(dāng)前輸入符a=b，做移進(jìn)；2）若當(dāng)前輸入符a 206。S?的狀態(tài)，這就是唯一的接受態(tài)。 LR分析器模型。每一項(xiàng)ACTON[s，a]所規(guī)定的動作不外是下述四種可能之一。現(xiàn)在必須證明：若a= 算符優(yōu)先分析算法 在正確的情況下，算法工作完畢時，符號棧S應(yīng)呈現(xiàn)：N。LASTVT(P),我們有a和(2) ab當(dāng)且僅當(dāng)G中含有形如P174。基于這一點(diǎn)，我們可用句柄來刻畫移進(jìn)—?dú)w約過程的“可歸約串”。最右推導(dǎo)常被稱為規(guī)范推導(dǎo)。(3)如果把FIRST(A)中的符號加入非終結(jié)符A的同步符號集，那么，當(dāng)FIRST(A)中的一個符號在輸人中出現(xiàn)時，可以根據(jù)A恢復(fù)語法分析。我們現(xiàn)在要介紹的預(yù)測分析程序就是屬于這種類型的LL(1)分析器 預(yù)測分析程序工作過程 預(yù)測分析程序的總控程序在任何時候都是按STACK棧頂符號X和當(dāng)前的輸入符號a行事的。dA’|g1|g2|… |gmA’174。 αp39。授課題目（教學(xué)章、節(jié)或主題）：第三章 語法分析——自上而下分析課時安排12授課時間 第4周 第36節(jié) 第6周 第16節(jié) 第7周 第12節(jié) 教學(xué)目的、要求（分掌握、熟悉、了解三個層次）：了解確定的自頂向下分析思想熟悉某些非LL（1）文法到LL（1）文法的等價變換掌握LL（1）文法的判別、確定的自頂向下分析方法教學(xué)重點(diǎn)和難點(diǎn)：語法分析器的功能、確定的自頂向下分析思想、LL（1）文法的判別、某些非LL（1）文法到LL（1）文法的等價變換、不確定的自頂向下分析思想、確定的自頂向下分析方法授課類型（請打√）：理論課254。P2β, ……,Pn1 222。這幾類文法的差別在于對產(chǎn)生式施加不同的限制。開始符號是一個特殊的非終結(jié)符號，它代表所定義的語言中我們最終感興趣的語法范疇，這個語法范疇通常稱為“句子”。這個推導(dǎo)提供了一個證明，證明(i+i)是文法()所定義的一個算術(shù)表達(dá)式。我們可以從E出發(fā)，進(jìn)行一系列的推導(dǎo)，推出種種不同的算術(shù)表達(dá)式來。 LEX的實(shí)現(xiàn) LEX的編譯程序旨在將一個LEX源程序改造為一個詞法分析器L，這個詞法分析器L將像有限自動機(jī)那樣工作。上述結(jié)論加上前面章節(jié)所證明的結(jié)論，說明正規(guī)文法、正規(guī)式、確定有限自動機(jī)和非確定有限自動機(jī)在接收語言的能力上是互相等價的。稱為s的一個后繼狀態(tài)；4. S0206。8. RETRACT 子程序過程，把搜索指示器回調(diào)一個字節(jié)位置，把CHAR中的字符置為空白。（a）狀態(tài)轉(zhuǎn)換圖示例 狀態(tài)轉(zhuǎn)換圖的實(shí)現(xiàn) 一個狀態(tài)轉(zhuǎn)換圖可用于識別（或接受）一定的字符。 預(yù)處理的工作包括：剔除無用的空白、跳格、回車和換行符等編輯性字符；預(yù)處理工作還可以包括源程序和出錯信息的列表打印。 模型□ 實(shí)物□ 掛圖□ 音像□ 其他□討論、思考題、作業(yè)：P63：3，6，7，8，12，14教學(xué)內(nèi)容第二章 詞法分析 對于詞法分析器的要求 首先討論詞法分析器輸出的單詞符號的一般形式，然后研究詞法分析器應(yīng)如何和語法分析器相銜接。如：編譯程序編譯程序、編譯程序產(chǎn)生器、翻譯程序書寫系統(tǒng)等，它們是按照對源語言和目標(biāo)語言（或機(jī)器）的形式描述（作為輸入數(shù)據(jù)）而自動產(chǎn)生編譯程序的。只要實(shí)際使用的操作平臺上實(shí)現(xiàn)了的Java解釋器，這個操作平臺就可以執(zhí)行各種Java程序。但遍數(shù)多勢必增加輸入／輸出所消耗的時間。 編譯過程的每一階段都可能檢測出錯誤，其中，絕大多數(shù)錯誤可以在編譯的前三階段檢測出來。合理地設(shè)計(jì)和使用表格是編譯程序構(gòu)造的一個重要問題。 高級語言程序除了像上面所說的先編譯后執(zhí)行外，有時也可“解釋”執(zhí)行。一個源語言的解釋程序是這樣的程序，它以該語言寫的源程序作為輸入，但不產(chǎn)生目標(biāo)程序，而是 邊解釋邊執(zhí)行源程序本身。在編譯程序使用的表格中，最重要的是符號表。源程序中的錯誤通常分為語法錯誤和語義錯誤兩大類。因此，在主存可能的前提下，一般還是遍數(shù)盡可能少一點(diǎn)為好。這就是所謂Java語言操作平臺無關(guān)性。本課程將把自動產(chǎn)生器作為一個重要課題來討論。 詞法分析器的功能和輸出形式 詞法分析器的功能是輸入源程序，輸出單詞符號。 單詞符號的識別：超前搜索詞法分析器的結(jié)構(gòu)如下圖所示：當(dāng)詞法分析器調(diào)用預(yù)處理子程序處理出一串輸入字符放進(jìn)掃描緩沖區(qū)之后，掃描器就從此緩沖區(qū)中逐一識別單詞符號。大多數(shù)程序語言的單詞符號都可以用轉(zhuǎn)換圖予以識別。 正規(guī)表達(dá)式與有限自動機(jī) 正規(guī)式與正規(guī)集 設(shè)Σ是一個有窮字母表，它的每個元素稱為一個字符。S，是唯一的一個初態(tài)；5. Z205。 確定有限自動機(jī)的化簡 等價狀態(tài)；最少化。相關(guān)介紹：人們已建立了多種編制部分編譯程序或整個編譯程序的有效工具。例如，根據(jù)規(guī)則E一(E)我們可以說：從‘E’可直接(一步地)推出‘(E)’。注意，推導(dǎo)每前進(jìn)一步總是引用一條規(guī)則(產(chǎn)生式),而符號‘222。但在程序語言中，我們最終感興趣的是“程序”這個語法范疇，而其它的語法范疇都只不過是構(gòu)造“程序”的一塊塊磚石。 0型文法：也稱短語文法，其能力相當(dāng)于圖靈機(jī)。Pnγ，Pn 222。 討論課□ 實(shí)驗(yàn)課254。|ε(ε 為空字)這種形式和原來的形式是等價的，也就是說，從P推出的符號串是相同的。|b1|b2|…|bn LL(1)分析條件 假定S是文法G的開始符號，對于任何非終結(jié)符A我們定義： FOLLOW(A) = { a | S222。 預(yù)測分析表的構(gòu)造 為了構(gòu)造預(yù)測分析表M，我們需要先構(gòu)造與文法G有關(guān)的集合FIRST和FOLLOW. 消除左遞歸和提取左因子將有助于獲得無多重定義的分析表M。(4)如果一個非終結(jié)符產(chǎn)生空串，那么，推導(dǎo)6的產(chǎn)生式可以作為缺省的情況，這樣做可以推遲某些錯誤檢查，但不能導(dǎo)致放棄一個錯誤。由規(guī)范推導(dǎo)所得的句型稱為規(guī)范句型。因此，規(guī)范歸約的實(shí)質(zhì)是，在移進(jìn)過程中，當(dāng)發(fā)現(xiàn)棧頂呈現(xiàn)句柄時就用相應(yīng)產(chǎn)生式的左部符號進(jìn)行替換。…aR…的產(chǎn)生式，R而R222。的終結(jié)符對，我們需要對G的每個非終結(jié)符P 構(gòu)造兩個集合FIRSTVT(P)和LASTVT(P): FIRSTVT(P)={a | P222。b.我們首先討論構(gòu)造集合FIRSTVT(P)的算法。注意，在上述算法中，我們并沒有指出應(yīng)把所找到的最左素短語歸約到哪一個非終結(jié)符號‘N’。b，則f(a)＝g(b)；若a(1)移進(jìn) 把(s，a)的下一狀態(tài)s’=GOTO[s，a]和輸入符號a推進(jìn)棧，下一輸人符號變成現(xiàn)行輸入符號。 LR分析器 一個LR分析器實(shí)質(zhì)上是一個帶先進(jìn)后出存儲器（棧）的確定有限狀態(tài)自動機(jī)。 假定一個文法G 的拓廣文法G39。 Follow(A)，按A174。LALR分析表比規(guī)范分析表要小得多，能力也差一點(diǎn)，但它卻能對付一些SLR所不能對付的情形。 討論課□ 實(shí)驗(yàn)課254。用繼承屬性來表示程序語言結(jié)構(gòu)中的上下文依賴關(guān)系很方便。State val… …X Y Z … … L—屬性文法和自頂向下翻譯 一個屬性文法稱為L—屬性文法：如果對于每個產(chǎn)生式A174。三地址語句類似于匯編語言代碼。 保留作用域信息 過程readarray，exchange和quicksord的符號表有指針指向其外圍過程的符號表。類型T．type通過對指向本記錄符號表的指針施用類型構(gòu)造符record而得到。特別是當(dāng)low=1， 時有：V=(i1*n2+i2)*w C= base –(n2+1)*w應(yīng)該牢記。如果t是一個指向某個記錄類型的指針，把類型構(gòu)造符record 施于該指針，返回所形成的類型record(t)作為屬性T．type的值。這樣做的好處是可以把用在符號表中查找名字的程序同樣用來查找域名。即若high2為i2的上界，則n2=high2 – low2 +1.假定i1,i2是編譯時唯一尚未知道的值，我們可以重寫上述表達(dá)式為： ( (i1*n2) + i2) *w +( base –（ (low1 *n2) + low2) *w）后一項(xiàng)子表達(dá)式( base – （(low1 *n2) + low2) *w ）的值是可以在編譯時確定的,為常數(shù)。當(dāng)記錄的所有域名都被檢查過之后，在offset的棧頂將存放著記錄之內(nèi)的所有數(shù)據(jù)對象的總域?qū)挕７墙K結(jié)符號T有兩個綜合屬性T．type和 T．width，分別表示名字的類型和名字的域?qū)?即該類型名字所占用的存儲單元個數(shù))。之所以稱為三地址代碼是因?yàn)槊織l語句通常包含三個地址，兩個用來表示操作數(shù)，一個用來存放結(jié)果。我們使用一個棧來存放已經(jīng)分析過的子樹的信息。僅僅使用綜合屬性的屬性文法稱S—屬性文法。YACC輸入用戶提供的語言的語法描述規(guī)格說明，基于LALR語法分析的原理，自動構(gòu)造一個該語言的語法分析器，同時，它還能根據(jù)規(guī)格說明中給出的語義子程序建立規(guī)定的翻譯。 LALR分析表的構(gòu)造 現(xiàn)在來討論構(gòu)造分析表的LALR方法。 Follow(B),則可以根據(jù)當(dāng)前讀頭下符號a來消除沖突。這樣，便會產(chǎn)生一個僅含項(xiàng)目S39。棧頂狀態(tài)為Sm，符號串X1X2…Xm是至今已移進(jìn)歸約出的部分。顯然，[s，X]定義了一個以文法符號為字母表的DFA。如果有矛盾，那么，就不存在優(yōu)先函數(shù)。 Xi+1 END 至此我們完成了從文法G構(gòu)造優(yōu)先表的算法。 類似地，假定有產(chǎn)生式的一個候選式為…Pb…那末，對任何a206。為了找出所有滿足關(guān)系…aQb…的產(chǎn)生式。對于規(guī)范句型來說，句柄的后面不會出現(xiàn)非終結(jié)符I號(即，句柄的后面只能出現(xiàn)終結(jié)符)。因此，規(guī)范規(guī)約也稱最左規(guī)約。這樣，在一個賦值語句后少一個分號就可能導(dǎo)致作為下一語句開頭的關(guān)鍵字被跳過。實(shí)現(xiàn)LL(1)分析的另一種有效方法是使用一張分析表和一個棧進(jìn)行聯(lián)合控制。db1|db2|…|dbn|g1|g2|… |gm （其中每個g不以d開頭）那么，可以把這些規(guī)則改寫成：A174。p39。 我們以后所討論的文法均假定滿足上述兩條件。 P1α，P1 222。0型強(qiáng)于1型，1型強(qiáng)于2型，2型強(qiáng)于3型。因而，也可以說，每個非終結(jié)符號表示一定符號串的集合(由終結(jié)符號和非終結(jié)符號組成的符號串)。我們稱這樣的一串替換序列是從E推出(i+i)的一個推導(dǎo)。例如，我們考慮下面的文法G: EE十E | E*E | (E) |i 其中，唯一的非終結(jié)符E可以看成是代表一類算術(shù)表達(dá)式。 超前搜索 在某些語言中，要識別一個單詞符號必須超前看若干字符。（2） 對任何的正規(guī)式r，都存在一個FA M，使得L（M）＝L（r）。我們把s39。 7. RESERVE 整型函數(shù)過程，對TOKEN中的字符串查找保留字表，若它是一個保留字則返回它的編碼，否則返回0值(假定0不是保留字的編碼)。一張轉(zhuǎn)換圖只包含有限個狀態(tài)（即有限個結(jié)點(diǎn)），其中有一個被認(rèn)為是初態(tài)，而且實(shí)際上至少要有一個終態(tài)（用雙圈表示）。但在許多情況下，把輸入串預(yù)處理一下，對單詞符號的識別工作將是比較方便的。 其他□教學(xué)資源（請打√）：多媒體254。有些能用于自動產(chǎn)生掃描器，有些可用于自動產(chǎn)生語法分析器，有些甚至可用來自動產(chǎn)生整個的編譯程序。 又如，在Java語言環(huán)境中，為了使編譯后的程序從一個平臺移到另一個平臺，Java定義一種虛擬機(jī)代碼Bytecode。遍數(shù)多一點(diǎn)有個好處，即整個編譯程序的邏輯結(jié)構(gòu)可能清晰一點(diǎn)。但是，自動校正錯誤的代價是非常高的。 編譯程序在工作過程中需要保持一系列的表格，以登記源程序的各類信息和編譯各階段的進(jìn)展?fàn)顩r。如果 源語言是諸如FORTRAN、Pascal、C、Ada、Smalltalk或Java這樣的“高級語言”，而目標(biāo)語言是諸如匯編語言或機(jī)器語言之類的“低級語言”，這樣的一個翻譯程序就稱為編譯程序。本書將不對解釋程序作專門的討論。它用來登記源程序中出現(xiàn)的每個名字以及名字的各種屬性。語法錯誤是指源程序中不符合語法(或詞法)規(guī)則的錯誤，它們可在詞法分析或語法分析時檢測出來。應(yīng)當(dāng)注意的是，并不是每種語言都可以用單遍編譯程序?qū)崿F(xiàn)。 編譯程序與程序設(shè)計(jì)環(huán)境 開發(fā)通常還需要一些其它的工具；如編輯程序、連接程序，調(diào)試工具等等。 近些年來，有些人主張采用“自編譯方式”產(chǎn)生編譯程序。單詞符號是一個程序語言的基本語法符號，程序語言的單詞符號一般可分為下列五種：1 基本字 如FORTRAN中的DIMENSION、IF和DO 等等；2 標(biāo)識符 用