編譯原理總結(jié)

1、(1)程序設(shè)計語言 機器語言: 由0、1代碼構(gòu)成，不需翻譯就可直接執(zhí)行其程序。 匯編語言: 機器指令助記符（偽代碼）形式，匯編后才可執(zhí)行其程序。 高級程序設(shè)計語言: 類自然語言和數(shù)學公式形式(2) 基本術(shù)語 源程序(Source Program)：用源語言寫的程序。源語言可以是匯編語言，也可以是高級程序設(shè)計語言。 目標程序(Target Program) ：也稱為“結(jié)果程序”，是源程序經(jīng)翻譯程序加工以后所生成的程序。目標程序可以用機器語言表示，也可以用匯編語言或其它中間語言表示。 翻譯程序(Translating Program)：是指把一個源程序翻譯成邏輯上等價的目標程序的程序。源程序為其輸

2、入，目標程序為其輸出。 匯編程序(Assembler)：是指把一個匯編語言寫的源程序轉(zhuǎn)換成等價的機器語言表示的目標程序的翻譯程序。 編譯程序(Compiler)：若源程序是用高級程序設(shè)計語言所寫，經(jīng)翻譯程序加工生成目標程序，則該翻譯程序就稱為“編譯程序”，也可稱為編譯器。 解釋程序：是高級語言翻譯程序的一種，他將源語言書寫的源程序作為輸入，解釋一句后就提交計算機執(zhí)行一句，并不形成目標程序，就像外語翻譯中的“口譯”一樣，不產(chǎn)生全文的翻譯文本。 運行系統(tǒng)(Running System)：目標程序執(zhí)行時，需要有一些子程序（如一些連接裝配程序及一些連接庫等）配合進行工作，由這些子程序組成的一個子程序庫

3、稱為運行系統(tǒng)。 編譯系統(tǒng)(Compiling System)：編譯程序和運行系統(tǒng)合稱編譯系統(tǒng)。(3) 程序的翻譯 除機器語言程序外，用其它語言書寫的程序都必須經(jīng)過翻譯才能被計算機識別。這一過程由翻譯程序來完成。 編譯方式是一種分階段進行的方式，包括翻譯和運行兩部分。 前一階段：翻譯 后一階段：運行，由運行系統(tǒng)配合完成。(4) 過程1、詞法分析階段 這個階段的任務是從左到右一個字符一個字符地讀入源程序，對構(gòu)成源程序的字符流進行掃描和分解，從而識別出一個個單詞（也稱單詞符號或符號TOKEN）。 某源程序片斷如下：begin var sum, first, count: real; sum:=fir

4、st+count*10 end.保留字begin var real end標識符sum first count sum first count 界符 .逗號， 逗號, 冒號： 分號； 加號+ 乘號* 賦值號：= 整數(shù)10102、語法分析階段 是編譯過程的第二個階段。語法分析的任務是在詞法分析的基礎(chǔ)上將單詞序列分解成各類語法短語，如“程序”，“語句”，“表達式”等等。一般這種語法短語，也稱語法單位，或語法成分，或語法范疇。 語法分析所依據(jù)的是語言的語法規(guī)則，即描述程序結(jié)構(gòu)的規(guī)則。通過語法分析確定整個輸入串是否構(gòu)成一個語法上正確的程序。 3、語義分析階段 依據(jù)語言的語義規(guī)則，對語法分析得到的語法結(jié)

5、構(gòu)分析其含義以及應進行的運算，審查源程序中有無語義錯誤，為代碼生成階段收集類型信息。4、中間代碼生成 在進行了上述的語法分析和語義分析階段的工作之后，有的編譯程序?qū)⒃闯绦蜣D(zhuǎn)變成一種內(nèi)部表示形式，這種內(nèi)部表示形式叫做中間代碼。所謂“中間代碼”是一種結(jié)構(gòu)簡單，含義明確的記號系統(tǒng)，這種記號系統(tǒng)可以設(shè)計為多種多樣的形式。重要的設(shè)計原則：一是容易生成；二是容易將它翻譯成目標代碼。5、代碼優(yōu)化 任務：對前階段產(chǎn)生的中間代碼系列進行變換或改造。目的是使生成的目標代碼更高效，即省時間省空間。例如上例四個四元式可優(yōu)化為下面兩個四元式。6、目標代碼生成 任務：將中間代碼變換成特定機器上的絕對指令代碼或可重定位的指

6、令代碼或匯編指令代碼。它的工作與硬件系統(tǒng)結(jié)構(gòu)和指令含義有關(guān)。 7、表格管理編譯過程中源程序的各種信息被保留在種種不同的表格里，編譯各階段的工作都涉及到構(gòu)造、查找或更新有關(guān)的表格，因此需要有表格管理的工作；8、出錯處理如果編譯過程中發(fā)現(xiàn)源程序有錯誤，編譯程度應報告錯誤的性質(zhì)和錯誤發(fā)生的地點，并且將錯誤所造成的影響限制在盡可能小的范圍內(nèi)，使得源程序的其余部分能繼續(xù)被編譯下去，有些編譯程序還能自動校正錯誤，這些工作稱之為出錯處理。(5) 前端與后端參考上面的圖，目的是為了在多種源語言和多種目標語言的開發(fā)過程中，可以靈活搭配組合，消除重復開發(fā)的工作量，提高編譯系統(tǒng)的開發(fā)效率。(6) 遍所謂遍，是對源程

7、序或源程序的中間形式從頭到尾掃視并完成規(guī)定任務的過程。 每一遍掃視可完成一個階段或多個階段的功能。一遍的編譯程序：以語法分析程序為核心 。多遍掃描的優(yōu)點：可以減少內(nèi)存容量的需求，分遍后，以遍為單位分別調(diào)用編譯的各個程序，各遍程序可以相互覆蓋。可使各遍的編譯程序相互獨立，結(jié)構(gòu)清晰。能夠進行充分優(yōu)化，產(chǎn)生高質(zhì)量的目標程序?？蓪⒕幾g程序分為前端和后端，有利于編譯程序的移植。多遍掃描的缺點每遍都要讀符號、送符號，增加了許多重復性的工作，降低編譯效率。(7) 程序設(shè)計語言范型（從支持的計算模式）1. 強制(命令)式語言:是面向動作的，即一個計算過程看做是一系列動作，其動作是命令驅(qū)動，以語言形式表示。也稱

8、過程式語言，如C,FORTRAN等;2. 函數(shù)式語言：注重程序表示的功能也稱應用式語言，如ML和LISP等；3. 基于規(guī)則的語言：檢查一定的使能條件，滿足時執(zhí)行動作也稱邏輯程序設(shè)計語言，如PROLOG。4. 面向?qū)ο笳Z言：提供抽象數(shù)據(jù)類型，支持封裝性、繼承性和多態(tài)性。如C+和Java等。(1) 符號和符號串1、 字母表：元素的有窮非空集合。2、 符號串：由字母表中的符號組成的任何有窮序列。3、 符號串的頭尾，固有頭和固有尾：如果z=xy是一符號串，那么x是z的頭，y是z的尾，如果x是非空的，那么y是固有尾；同樣如果y非空，那么x是固有頭。如:設(shè)z=abc，那么z的頭是e，a, ab, abc,

9、 除abc外，其它都是固有頭；z的尾是e, c, bc, abc, z的固有尾是e, c, bc。4、 符號串的運算（1）符號串的連接：設(shè)x和y是符號串，x和y的連接xy是把y的符號寫在x的符號e后得的符號串。如：x=ST, y=abu, 則xy=STabu 顯然有ex=xe=x。（2）符號串的方冪：設(shè)x是符號串，把x自身連接n次得x的幾次方冪xn。 如：設(shè)x=ab則x0=e x1=ab x2=abab x3=ababab（3）符號串集合的乘積：設(shè)A和B為符號串集合，則A和B的乘積定義為AB=xy|xÎA且yÎB 如：a=a, b, B=00, 11 則AB=a00, a1

10、1, b00, b11 顯然：eA=Ae=A（4）符號串集合的方冪：設(shè)A為符號串集，則A的n次方冪An定義為:An=AAA=AAn-1=An-1A（5）符號串集合的正閉包A+：A+=A1 U A2 U U An U （6）符號串集合的閉包A*：A*=A0 U A+ = e U A+如：設(shè)有正字母表å=0，1 則å*=å0 U å1 U å2 U U ån U =e, 0, 1, 00, 01, 10, 11, 000, 001,(2) 文法文法G定義為四元組（VN ，VT，P，S）其中:（1）VN 為非終結(jié)符號集非終結(jié)符號表示一個語言

11、短語（或語法成分、語法單位）。 如 程序、語句、表達式等。一般用大寫字母或用 括起表示非終結(jié)符號。（2）VT 為終結(jié)符號集終結(jié)符號：組成語言的基本符號。是文法中不屬于非終結(jié)符號集合的符號。一般用小寫字母或不帶 的符號表示。如程序設(shè)計語言的單詞符號。設(shè)V=VN U VT，稱V為文法G的字母表。（3）P 為產(chǎn)生式（也稱規(guī)則）的集合。產(chǎn)生式的形式：ab或a=b，其中aV+，bV*（4）S 稱作識別符號或開始符號，是一個非終結(jié)符號。一般表示此文法定義的最大語法短語，至少要在一條產(chǎn)生式 中作為左部出現(xiàn)。 句型、句子的定義設(shè)GS是一文法，如果符號串x是從識別符號推導出來的，即有SÞ*x， 則稱x

12、是文法GS的句型。若x僅由終結(jié)符號組成，即SÞ*x, xÎV T ，則稱x為GS的句子。句型：在一棵樹生長過程的任何時刻，所有那些端末結(jié)點自左至右的排列，就是一個句型。語言的定義：文法G產(chǎn)生的語言記為L（G），它是文法G產(chǎn)生的全部句子的集合。文法等價定義：若L（G1）=L（G2）則稱文法G1和G2是等價的。(3) 文法的類型 N.Chomsky0型文法：定義0型語言，對應Turing機；1型文法：定義1型語言，對應線性限界自動機；箭頭后面的要比前面的長或相等2型文法：定義2型語言，對應非確定下推自動機；箭頭前面的是非終結(jié)符，后面是串3型文法：定義3型語言，對應有限自動機。非

13、終結(jié)符可以推出一個終結(jié)符或一個終結(jié)符和一個非終結(jié)符最右推導也稱為規(guī)范推導，所得句型稱為規(guī)范句型。如果一個文法存在某個句型對應兩棵不同的語法樹，則說這個文法是二義的。或者說，若一個文法中存在某個句型，它有兩個不同的最左（最右）推導，則這個文法是二義的。 上下文無關(guān)文法是否具有二義性是不可判定的。但有些特殊的2型文法例如LL（1）、LR（0）、LR（1）等文法是無二義性的。 一個文法兼有左遞歸和右遞歸是導致二義性的常見原因。排除文法二義性通常有兩種方法:（1）在語義上加些限制（2）重新構(gòu)造一個無二義性的文法 (4) 句型的分析句型的分析：就是識別一個符號串是否為某文法的句型。是某個推導的構(gòu)造過程。

14、分析方法分兩大類：自上而下分析法和自下而上分析法 推導與歸約，最右推導是規(guī)范推導，逆過程為規(guī)范規(guī)約 若SÞ*aAdÞ+abd （由AÞ+b得）則稱b是句型abd相對于非終結(jié)符A的短語。 若SÞ*aAdÞabd (由Ab得)則稱b是句型abd相對于Ab的直接短語（也稱簡單短語）。 一個句型的最左直接短語稱為該句型的句柄。一棵子樹（至少要有父子兩代）的所有端末結(jié)點自左至右排列起來形成相對于子樹根的短語。若子樹只有父子兩代，則得到直接短語。 (5) 有關(guān)文法（1）有害規(guī)則 文法中含形如UU的產(chǎn)生式。它對描述語言沒有必要，且會引起文法的二義性。（2）多

15、余規(guī)則 文法中任何一個句子的推導都用不到的規(guī)則。（3）無用規(guī)則 文法中含形如UV的產(chǎn)生式，即單產(chǎn)生式。為保證文法G的任一非終結(jié)符A在句子推導中出現(xiàn)，必須滿足如下兩個條件：（1）A必須在某句型中出現(xiàn)，aAd。（2） 必須能夠從A推導出終結(jié)符號串t。有關(guān)文法的化簡和改造，包括以下幾項工作：（）無用符號和無用產(chǎn)生式的刪除。（） e產(chǎn)生式的消除。（）單產(chǎn)生式的消除。（）左遞歸的消除。(1) 詞法分析輸出單詞符號（TOKEN) 是一個程序設(shè)計語言的基本語法符號。程序設(shè)計語言的單詞符號一般可分成下列5種：1基本字，也稱關(guān)鍵字，如PASCAL語言中的begin，end，if，while和var等。2標識符，

16、用來表示各種名字，如常量名、變量名和過程名等。3常數(shù)，各種類型的常數(shù)，如25，3.1415，TRUE和"ABC"等。4運算符，如+，*，<= 等。5界符，如逗點，分號，括號等。詞法分析程序所輸出的單詞符號常常采用下二元式表示：（單詞種別，單詞自身的值）可用整數(shù)碼或助記符等表示。(2) 單詞的描述工具程序設(shè)計語言中的單詞(TOKEN)是基本語法符號。單詞符號的語法可以用有效的工具加以描述。正規(guī)式和它所表示的正規(guī)集的遞歸定義如下。設(shè)字母表為，輔助字母表 = |, ·, *, (, ) 定義（正規(guī)式和它所表示的正規(guī)集）：設(shè)字母表為，輔助字母表=，|，·，

17、*，(， 。 和都是上的正規(guī)式，它們所表示的正規(guī)集分別為和 ； 任何a，a是上的一個正規(guī)式，它所表示的正規(guī)集為a； 假定e1和e2都是上的正規(guī)式，它們所表示的正規(guī)集分別為L(e1)和L(e2)，那么，(e1), e1|e2, e1·e2, e1*也都是正規(guī)式,它們所表示的正規(guī)集分別為L(e1), L(e1)L(e2), L(e1)L(e2)和(L(e1)*。 僅由有限次使用上述三步驟而定義的表達式才是上的正規(guī)式，僅由這些正規(guī)式所表示的字集才是上的正規(guī)集。(3) 有窮自動機有窮自動機（也稱有限自動機）作為一種識別裝置，它能準確地識別正規(guī)集，即識別正規(guī)文法所定義的語言和正規(guī)式所表示的集合

18、，引入有窮自動機這個理論，正是為詞法分析程序的自動構(gòu)造尋找特殊的方法和工具。確定的有窮自動機（DFA）：定義：一確定的有窮自動機（DFA）M是一個五元組： M=（K， ，f, S, Z）其中1K是一個有窮集，它的每個元素稱為一個狀態(tài)；2 是一個有窮字母表，它的每個元素稱為一個輸入字符，所以也稱為輸入符號字母表；3f是轉(zhuǎn)換函數(shù)，是在K× K上的映像，即，如f(ki,a)= kj, 就意味著，當前狀態(tài)為ki，輸入字符為a時，將轉(zhuǎn)換到下一狀態(tài)kj，我們把kj稱為ki的一個后繼狀態(tài)；4S 是唯一的一個初態(tài)；5Z是一個終態(tài)集，終態(tài)也稱可接受狀態(tài)或結(jié)束狀態(tài)。DFA的作用：對于*中的任何字符串t，

19、若存在一條從初態(tài)到某一終態(tài)結(jié)的道路，且這條路上所有弧的標記符連接成的字符串等于t，則稱t可為DFA M所接受，若M的初態(tài)結(jié)同時又是終態(tài)結(jié)，則空字可為M所識別。DFA M所能接受的字符串的全體記為L（M）。不確定的有窮自動機（NFA）定義：一個不確定的有窮自動機（NFA）M是一個五元組，M=（K，f, S, Z）。3.f是一個從K×*到K的冪集的映象4.S屬于K，是一個非空初態(tài)集5.Z屬于K，是一個終態(tài)集區(qū)別：DFA：只有唯一初態(tài)。NFA：有初態(tài)集。DFA是NFA的特例。對于每個NFA M，存在一個DFA M ，使得L（M）=L（M ）對于任何兩個有窮自動機M和M ，如果L（M）=L（

20、M ），則稱M與M 是等價的。(1) 自頂向下語法分析語法分析的作用是識別由詞法分析給出的單詞符號序列是否是給定文法的正確句子。其中自頂向下分析，就是從文法的開始符號出發(fā)企圖推導出與輸入的單詞串完全匹配的句子，若輸入串是給定文法的句子，則必能推出，反之必然出錯。FIRST（a）=a|a Þab, a ÎVT, a, b ÎV*（1）求FIRST（x）， xÎV （a）若xÎVT，則FIRST（x）=x （b）若x是e，則FIRST（x）=e （c）若xÎVN，且xy1y2ym|z1z2zn則FIRST（x）= FIRST(y1y2ym

21、) FIRST(z1z2zn) （2）求FIRST(y1y2ym), 其中 y1, y2, , ymÎV。 （a）若y1ÎVT, 則FIRST（y1y2ym）=y1 （b）若y1ÎVN, e Ï FIRST(y1)，則FIRST（y1y2ym）=FIRST(y1) 若e Î FIRST(y1)，則 FIRST(y1y2ym)=(FIRST(y1)e)FIRST(y2y3ym) 按上法求FIRST（y2y3ym），類推下去。對文法中每一A ÎVN，計算FOLLOW（A）（a） 設(shè)S為文法的開始符號，則#ÎFOLLOW（S）（b

22、） 若有AaBb，則將FIRST（b）e加入到FOLLOW（B）中，如果其中b Þe，則將FOLLOW（A）加入到FOLLOW（B）中。計算SELECT集定義：SELECT ( Aa ) =FIRST ( a ),其中a Þe。若a Þe，則SELECT ( Aa ) = (FIRST（a） e) FOLLOW(A)判定LL（1）文法對每個非終結(jié)符A的兩個不同產(chǎn)生式，Aa，Ab，滿足SELECTC（Aa）SELECT（A b ）=f 其中a、b不能同時 Þe (2) 非LL（1）文法到LL（1）文法的等價變換由LL（1）文法的定義可知,若文法中含有直接或

23、間接左遞歸，或含有左公共因子,則該文法肯定不是LL（1）文法。 參考：文法含左遞歸不便于使推導按從左往右的順序匹配，甚至使分析發(fā)生死循環(huán)。（a）消除直接左遞歸一般情況下，直接左遞歸的形式為： AA a1|A a2|A am|b1|b2|bn消除左遞歸后改寫為： Ab1A¢|b2A¢|bnA¢ A¢ a1 A¢| a2 A¢ | | am A¢ | e（b）消除間接左遞歸先通過產(chǎn)生式的替換，將間接左遞歸變?yōu)橹苯幼筮f歸，然后再消除直接左遞歸。(3) 確定的自頂向下分析方法1、基本思想 對每一非終結(jié)符構(gòu)造一個過程，每個過程的功能是

24、識別由該非終結(jié)符推出的串。2、編寫程序 IP：是輸入串指示器，開始工作前IP指向串的第一個符號，每個程序工作完后，IP指向下一個未處理符號。 sym：表示IP所指符號。 ADVANCE：是過程，讓IP指向下一個符號。 ERROR：是出錯處理子程序。(4) 預測分析方法（1）預測分析表M 如下矩陣形式：矩陣M 行標題用文法的非終結(jié)符表示。 列標題用文法的終結(jié)符號和#表示。 矩陣元素MA, a的內(nèi)容是產(chǎn)生式Aa（或a）表明當對A進行推導，面臨輸入符號a時，應采用候選a進行推導。 出錯處理標志（即表中空白項）表明A不該面臨輸入符號a。（2）符號棧 用于存放文法符號，棧頂為推導過程中句型尚未匹配部分的

25、開頭符號。 分析開始時，棧底先放一個#，然后放進文法開始符號，即S#（3）預測分析總控程序 總是按棧頂符號x和當前輸入符號行事。 對于任何（x,a），總控程序每次都執(zhí)行下述三種可能動作之一： （a）若x=a=#，則宣布分析成功。 （b）若x=a¹#，則把x從棧頂逐出，指針指向下一輸入符號。 （c）若x是一個非終結(jié)符，則查看分析表M。 如果MA, a中存放關(guān)于X的一個產(chǎn)生式，那么，首先把X頂出棧，然后把產(chǎn)生式右部符號串按反序一一推進棧。 如果MA, a中存放“出錯標志”，則調(diào)用出錯處理程序ERROR。(1) 自底向上優(yōu)先分析法 自底向上分析方法，也稱移進歸約分析法，粗略地說它的實現(xiàn)思想

26、是對輸入符號串自左向右進行掃描，并將輸入符逐個移入一個后進先出棧中，邊移入邊分析，一旦棧頂符號串形成某個句型的句柄時，（該句柄對應某產(chǎn)生式的右部），就用該產(chǎn)生式的左部非終結(jié)符代替相應右部的文法符號串，這稱為一步歸約。重復這一過程直到歸約到棧中只剩文法的開始符號時則為分析成功，也就確認輸入串是文法的句子?？梢钥闯?，移進一歸約過程是自頂向下最右推導的逆過程。最右推導稱為規(guī)范推導。自左向右的歸約過程稱為規(guī)范歸約。 如何知道何時在棧頂符號串中已形成某句型的句柄，這是自底向上分析的關(guān)鍵。在自底向上分析方法中，本章主要介紹常用的算符優(yōu)先分析法和LR類分析法。(2) 算符優(yōu)先分析法算符文法的定義：設(shè)有一文法

27、G，如果G中沒有形如ABC的產(chǎn)生式，其中B和C為非終結(jié)符，則稱G為算符文法（Operater Grammar）也稱OG文法。（文法中沒有兩個非終結(jié)符相臨的情況，則稱是算符文法）性質(zhì)1 在算符文法中任何句型都不包含兩個相鄰的非終結(jié)符。性質(zhì)2 如果Ab或bA出現(xiàn)在算符文法的句型g中；其中AÎVN，bÎVT，則g中任何含b的短語必含有A。算符優(yōu)先文法的定義：設(shè)有一不含e產(chǎn)生式的算符文法G，如果對任意兩個終結(jié)符對a, b之間至多只有<、>和=三種關(guān)系的一種成立，則稱G是一個算符優(yōu)先文法。（Operator Precedence Grammar）即OPG文法。(3) 算符

28、優(yōu)先關(guān)系表的構(gòu)造FIRSTVT（B）=b|BÞb或BÞCb 構(gòu)造規(guī)則： （1）若Bb或BQb，則bÎFIRSTVT(B) （2）若BQ，則FIRSTVT(Q)ÍFIRSTVT（B）LASTVT（B）=a|BÞa或BÞaC構(gòu)造規(guī)則 （1）若Ba或BaQ，則aÎLASTVT(B) （2）若BQ，則LASTVT(Q)ÍLASTVT（B） 最左素短語：設(shè)有文法GS，其句型的素短語是一個短語，它至少包含一個終結(jié)符，并且除自身外不包含其它素短語，最左邊的素短語稱最左素短語。(4) 歸約步驟初始時棧底存#，輸入指針指向輸入串的首

29、字符?？刂瞥绦蚋鶕?jù)棧頂終結(jié)符a（若棧頂是非終結(jié)符，則次棧頂?shù)慕K結(jié)符稱為棧頂終結(jié)符）和輸入指針所指的輸入符b，查優(yōu)先關(guān)系表M，可能有四種情況： （1）Ma, b為<或=時移進b，即將b進棧，輸入指針指向下一輸入符。 （2）Ma, b為>時，則將棧頂含a的素短語按對應的產(chǎn)生式歸約，素短語與產(chǎn)生式右部需終結(jié)符對應相同，非終結(jié)符位置應相同名稱可不同。頂出棧中素短語，非終結(jié)符入棧。（3）Ma, b為空白，語法錯，調(diào)用相應出錯處理程序。（4）a=b=# 時分析結(jié)束。(5) 優(yōu)先函數(shù)用關(guān)系法構(gòu)造。 構(gòu)造步驟：（a）對每一終結(jié)符a（包括#），用fa，ga為結(jié)點名。（b）若ai>aj或ai=a

30、j，則從fai到gaj畫一條箭弧。若ai<aj或ai=aj，則從gaj到fai畫一條箭弧。（c）給每個結(jié)點賦一個數(shù)，此數(shù)等于從該結(jié)點出發(fā)所能到達的結(jié)點（包括該結(jié)點自身在內(nèi)）的個數(shù)。賦給結(jié)點f (ai)的數(shù)，就是函數(shù)f(ai)的值，賦給g (aj)的數(shù)，就是函數(shù)g(aj)的值。（d）對構(gòu)造出的優(yōu)先函數(shù)，按優(yōu)先關(guān)系矩陣檢查一遍是否滿足優(yōu)先關(guān)系的條件，若不滿足時，則在關(guān)系圖中有回路說明不存在優(yōu)先函數(shù)。優(yōu)先函數(shù)的優(yōu)缺點優(yōu)點：（1）節(jié)省存儲空間；（2）執(zhí)行整數(shù)比較運算比查優(yōu)先關(guān)系表方便。缺點：（1）有些優(yōu)先關(guān)系表不存在優(yōu)先函數(shù)。（2）原先不存在優(yōu)先關(guān)系的兩個終結(jié)符變成可比較其函數(shù)值大小了，需加以克

31、服。(1) LR分析法LR分析法是一類對上下文無關(guān)文法進行“自左向右的掃描和最左歸約（即最右推導的逆過程）”分析的方法，是一種規(guī)范歸約過程。LR(k)分析方法是1965年Knuth提出的，其中k表示向右查看輸入符號串的個數(shù)。（1）總控程序 所有LR分析器的總控程序都是相同的，共有四種動作：移進、歸約、接受、出錯。（2）分析表 常見的有四種:LR（0）分析表 適應文法范圍小，是其它類型分析表構(gòu)造的基礎(chǔ)。SLR（1）分析表 是LR（0）分析表的改進，適應文法范圍強于LR（0）。LR（1）分析表 分析能力強（指適應范圍，查錯速度），但狀態(tài)太多。LALR（1）分析表 是LR（1）分析表的改進，分析能力

32、強于SLR而稍弱于LR（1），但狀態(tài)少于LR（1）（3）分析棧 包括文法符號棧和相應的狀態(tài)棧。(2) LR(0)分析可歸前綴規(guī)范句型中，包括句柄及句柄以左的部分，稱為可歸前綴。有些可歸前綴的前綴是相同的，不僅僅屬于某一個規(guī)范句型。我們把可歸前綴的前綴稱為活前綴。 進行語法分析時，只要將待分析符號串的當前部分符號與aiPi進行比較，便可知是否歸約，以及應按哪條產(chǎn)生式歸約。 為了得到所有可歸前綴，可以對文法G構(gòu)造一個有窮自動機，該有窮自動機能識別文法G的所有可歸前綴。構(gòu)造識別可歸前綴的有窮自動機項目：文法的識別可歸前綴的有窮自動機以文法的“項目”作為它的狀態(tài)，所謂文法的項目，是在文法的每一條規(guī)則的

33、右部添加一個圓點而形成。之所以這樣構(gòu)造項目，是受可歸前綴的啟發(fā)。圓點表示在識別可歸前綴的過程中，對句柄（即某產(chǎn)生的右部）已識別過的部分。項目分四類 （a）圓點在最右端的項目，形如Aa·，表示已從輸入串看到能由一條產(chǎn)生式右部推導出的符號串，即已達一可歸前綴末端，已識別出句柄可以歸約，這種項目稱為歸約項目，相應狀態(tài)稱為歸約狀態(tài)。即為可歸前綴識別態(tài) （b）對形如S¢S·的項目，其中S是文法開始符號，稱為接受項目，相應狀態(tài)稱為接受狀態(tài)，表明可由S推導的輸入串已全部識別完，整個分析過程成功結(jié)束。 （c）對于形如Aa·ab的項目，表明尚未識別一可歸前綴，需將a移進符

34、號棧，故稱移進項目，相應狀態(tài)為移進狀態(tài)。 （d）對于形如Aa·Bb的項目，表明期待分析由B所推出的串歸約到B，從而識別B。故稱為待約項目，相應狀態(tài)為待約狀態(tài)。方法一：首先構(gòu)造識別可歸前綴的NFA，然后將NFA確定化，得DFA（部分）。方法二：根據(jù)文法直接構(gòu)造識別文法可歸前綴的DFA。拓廣文法 對文法G加一條產(chǎn)生式 S¢S 得 G¢，目的是使開始狀態(tài)唯一，接受狀態(tài)易于識別。定義項目集I的閉包CLOSURE(I)a) I的項目均屬于CLOSURE( I );b) 若AaBb屬于CLOSURE（I）,則每一形如B 的項目也屬于CLOSURE（I）;c) 重復b），直到C

35、LOSURE（I）不再增大為止。定義狀態(tài)轉(zhuǎn)換函數(shù)GO（I，X）其中I是項目集，X是文法符號。GO（I，X）=CLOSURE( J )，其中J=任何形如Aaxb的項目|AaxbI，以上可以避免出現(xiàn) e 弧，避免從同狀態(tài)射出相同標記弧。構(gòu)造DFA a) DFA的初態(tài)集：CLOSURE(S¢S)b) 對初態(tài)集或其它所構(gòu)造的項目集應用轉(zhuǎn)換函數(shù)，GO (I, X) =CLOSURE（J）求出新的項目集。c) 重復b)直到不出現(xiàn)新的項目集為止。DFA中所有狀態(tài)組成的集合也稱為該文法的LR（0）項目集規(guī)范族。 構(gòu)造算法a) 若項目Aa·ab屬于Ik且轉(zhuǎn)換函數(shù)GO（ Ik, a）=Ij，當

36、a為終結(jié)符時則置ACTIONk, a為Sj，其動作含意為將終結(jié)符a移進符號棧，狀態(tài)j進 入狀態(tài)棧，（即當狀態(tài)k遇a時轉(zhuǎn)向狀態(tài)j）。b) 若項目Aa·屬于Ik ，則對a為任何終結(jié)符或#號，置ACTIONk,a為“rj”，j為在文法G¢中某產(chǎn)生式Aa的序號。rj 動作的含義是把當前文法符號棧頂?shù)姆柎產(chǎn)歸約為A，且將棧指針從棧頂向下移動|a|的長度（或符號棧中彈出|a|個符號），非終結(jié)符A變?yōu)楫斍懊媾R的符號。c) 若GO（Ik, A）= Ij，則置GOTOk, A為 “j”，其中A為非終結(jié)符，表示當前狀態(tài)為“k”時，遇文法符號A時狀態(tài)應轉(zhuǎn)向j，因此A 移入文法符號棧，j 移入狀

37、態(tài)棧。d) 若項目S¢S·屬于Ik，則置ACTIONk, #為“acc”，表示接受。e) 凡不能用上述方法填入的分析表的元素，均應填上“報錯標志”。為了表的清晰我們令在表中用空白表示錯誤標志。LR（0）分析器的工作過程（1）若ACTION q i , a k = S j ，則將狀態(tài) S j , a k 進棧，三元式變化過程:（2）若ACTION q i, a k = r j ，且第 j 條產(chǎn)生式為 A b ，|b| = r ，則按 第 j 條產(chǎn)生式歸約。（3）若ACTIONqi, ak=acc 則結(jié)束分析，輸入串被接受。（4）若ACTIONqi, ak=ERROR 或表中為

38、空白，表示出錯，進行相應出錯處理。(2) 非LR（0）文法的判斷判斷方法一： 考察識別文法可歸前綴的DFA，若某個狀態(tài)（即項目集）中既含移進項目又含歸約項目；或含不只一個歸約項目， 則會發(fā)生分析動作的沖突，可知該文法不是LR（0）的。判斷方法二： 若文法的LR（0）分析表中含多重定義，即表中某項動作不唯一，則該文法不是LR（0）文法。(3) SLR（1）分析用SLR（1）方法，對于當前狀態(tài)中的歸約項目，如Aa·，必須當前輸入符號屬于FOLLOW（A）時，才可做歸約。有望解決LR（0）方法中的分析動作沖突問題。SLR（1）分析表的構(gòu)造 將LR（0）分析表構(gòu)造算法中的 b）改為： 若項目

39、Aa ·屬于Ik，則對a為任何終結(jié)符或#號，且滿足aÎFOLLOW(A)時，置ACTIONk, a為“rj”，j為在文法G¢中某產(chǎn)生式Aa的序號。(4) 非SLR文法的判斷判斷方法一：對識別文法可歸前綴DFA中任一狀態(tài)下，F(xiàn)OLLOW(B1)FOLLOW(Bn)，兩兩不相交，否則，文法不是SLR的。只求需要歸約Follow集判斷方法二：若構(gòu)造的SLR分析表含多重定義，則文法不是SLR的。(5) LR（1）分析 對某些文法，用SLR（1）方法仍解決不了分析動作的沖突問題，可采取以下措施：若某歸約項目Aa · Î I ，當 I 為當前狀態(tài)，面臨當前

40、輸入符號a 時，只有a 是在 I 狀態(tài)下A 的后繼符號時 才用 A a 產(chǎn)生式歸約，而不是對A的所有后繼符號都可以歸約。從而有望解決沖突。A a ·，F(xiàn)ollow(A) 是向前搜索符，構(gòu)造項目集是其他與LR(0)相似，只是加上向前搜索符 將LR（0）分析表構(gòu)造算法中的 b) 中：若項目 A a · 屬于Ik ，則對 a 為任何終結(jié)符或 # 號，置ACTIONk, a為 rj改為：若項目 Aa·, a 屬于Ik ，則置 ACTION k,a = rjLR（k）分析表如果用 LR（1）方法仍不能解決沖突，則可再向前多搜索幾個符號，這時的項目為 Aa·b ,

41、a1 a2 ak 稱為 LR（k）項目，相應的分析表構(gòu)造方法類似 LR（1）分析表的構(gòu)造。(6) LALR（1）分析在LR（1）項目中，有很多狀態(tài)中的項目除了向前搜索符號不同外，產(chǎn)生式部分是完全相同的，稱這樣的狀態(tài)是同心的，為了克服LR（1）分析中狀態(tài)太多的問題，可以將這些同心集合并。如果合并后得到的新狀態(tài)沒有沖突出現(xiàn)。則按新狀態(tài)構(gòu)造分析表。這就是LALR（1）分析法的基本思想。LR(0) LR(1) SLR(1) 這三種文法很重要。(1) 語義處理語義分析：主要檢查各種語法成分的語義是否符合語義規(guī)定，例如參與運算的表達式類型是否一致，賦值語句的賦值左部和右部類型的一致性，數(shù)組元素的維數(shù)與數(shù)組

42、說明維數(shù)的一致性，每一維的下標是否越界，在相同作用域中名字是否被重復說明等。 目前尚無公認的、統(tǒng)一的形式化語義描述工具。但研究者已提出一些針對某些特殊語言的語義描述工具，例如：公理語義、指稱語義、代數(shù)語義、操作語義等。中間代碼生成：對說明語句，通常將其中定義的名字及其屬性信息，在符號表中進行登記；對于執(zhí)行語句，生成語義上等價的中間語言代碼。屬性文法：一個屬性文法，包含一個上下文無關(guān)文法和一系列語義規(guī)則，這些語義規(guī)則附在文法的每個產(chǎn)生式上。ET1+T2 T1·t=int AND T'2·t=int ET1 or T2 T1·t=bool AND T2

43、3;t=boolTnum T·t=int Ttrue T·t:=bool Tfalse T·t:=bool語法制導翻譯：在語法分析過程中，隨著分析的步步進展，根據(jù)每個產(chǎn)生式對應的語義子程序（或語義規(guī)則描述的語義動作）進行翻譯的辦法稱作語法制導翻譯。語法制導翻譯的具體實現(xiàn)途徑：假定有一個LR語法分析器，現(xiàn)在把它的分析棧擴充，使得每個文法符號都跟有語義值，即把棧的結(jié)構(gòu)看成下圖所示那樣。同時把LR分析器能力擴大，使它不僅執(zhí)行語法分析任務，且能在用某個產(chǎn)生式進行歸約的同時調(diào)用相應的語義子程序，完成有關(guān)的語義動作。每步工作后的語義值保存在擴充的分析棧里“語義值”欄中。(2)

44、 中間代碼形式常見的有逆波蘭記號、三元式、四元式和樹等。1.逆波蘭表示（也稱后綴表示）逆波蘭表示的特點：（1）運算符緊跟在運算對象的后面出現(xiàn)，沒有括號。（2）運算對象出現(xiàn)的順序（從左到右）和原有順序（中綴）相同。（3）運算符是按實際運算順序（從左到右）出現(xiàn)的。逆波蘭表示的最大優(yōu)點是易于計算機處理表達式，使用棧進行運算很方便?？蓪⒛娌ㄌm表示形式擴充，用來描述程序設(shè)計語言中的其它語法成分。2.三元式表示 三元式的形式為：（op，ARG1，ARG2）其中op為運算符，ARG1為運算對象1，ARG2為運算對象2。三元式出現(xiàn)的先后順序與表達式的運算順序一致。三元式的缺點是不便于優(yōu)化，動一式，其它式子被牽

45、動，使用間接三元式，可以克服這個缺點。間接三元式：使用二個表（1）三元式：存放不相同的三元式（2）運算順序表（也叫間接碼表）：按運算的先后順序列出有關(guān)三元式在三元式表中的位置。 3.樹形表示 三元式表示也可用相應的樹形表示。 簡單變量或常量的樹就是該變量或常量本身，如果表示表達式e1和e2的樹為T1和T24.四元式：表示形式（op; ARG1, ARG2, RESULT）四元式表示較利于代碼優(yōu)化。(3) 簡單賦值語句翻譯（1） 語義變量，表示變量即標識符字符串。（2）E. place 語義變量，表示存放E值的變量名在符號表中的入口位置或一整數(shù)碼（臨時變量）。（3）Lookup(i

46、d. name)語義過程(函數(shù)），對查符號表，若找到，則返回其在符號表中的位置，否則返回nil，體現(xiàn)先定義后使用的原則。（4）GEN(op, ARG1, ARG2, RESULT)語義過程(函數(shù)）,生成四元式，填進四元式表。（5）newtemp 語義過程，生成一臨時變量Ti。(4) 布爾表達式的翻譯布爾表達式的翻譯是指轉(zhuǎn)換成最終能計算出該表達式的結(jié)果為真或假（1 或0）的四元式序列的過程。Eg. a or b and not c 的四元式序列為： (1) t1:=not c(2) t2 :=b and t1(3) t3 :=a or t2(1) 控制語句的代碼結(jié)構(gòu) 真出口E.tr

47、ue 假出口E.false(2) “回填”技術(shù) 控制語句中布爾表達式翻譯成四元式序列時，有的轉(zhuǎn)移地址不能在產(chǎn)生這些四元式的同時得知，需要在適當?shù)臅r候回填這個地址。(3) “拉鏈”技術(shù) 為了記錄需要回填地址的四元式，常采用“拉鏈”技術(shù)。把需回填E.true 的四元式拉成一條鏈，稱為“真”鏈；把需回填E.false的四元式拉成一條鏈，稱為“假”鏈。 (5) 控制結(jié)構(gòu)的翻譯for 循環(huán)語句的文法及其相應的語義動作第八章 錯誤的診查與校正對于源程序，由于種種原因，往往含有或多或少的錯誤，因此，一個好的編譯程序應具有較強的查錯和改錯能力。1、語法錯誤 指程序結(jié)構(gòu)、單詞和拼寫不符合語法要求的規(guī)則。都是在詞

48、法分析階段和語法分析階段發(fā)現(xiàn)的。 如 關(guān)鍵字拼寫錯誤;某些語法成分未按語言的語法規(guī)則編寫等。 2、語義錯誤 指程序不符合語義規(guī)則或超越具體計算機系統(tǒng)的限制。包括以下幾種類型: 說明錯：對變量未說明就引用，某些量被重復說明，或不符合有關(guān)作用域的規(guī)定。 類型不相容錯：某些運算的操作數(shù)的類型不相容，形一實參在種屬或類型上不相對應等。 對某些值超越限制錯：如對各類變量數(shù)值范圍的限制；對數(shù)組維數(shù)、形參個數(shù)、循環(huán)嵌套數(shù)的限制。 另外，我們將在編譯階段就能發(fā)現(xiàn)的錯誤，稱為靜態(tài)錯;到目標代碼運行時才能發(fā)現(xiàn)的錯誤稱為動態(tài)錯，如溢出，動態(tài)數(shù)組的下標越界。出錯處理主要有兩種處理方法：1、校正法 試圖對錯誤進行校正。

49、 當編譯程序發(fā)現(xiàn)錯誤時，給用戶指出錯誤的性質(zhì)、錯誤的位置，以及如何校正等方面的信息。2、局部化法 當發(fā)現(xiàn)錯誤時，跳過錯誤所在的語法單位，繼續(xù)往下分析。以便把錯誤限制在盡可能小的局部范圍內(nèi)。只需給用戶報告出錯誤位置，出錯性質(zhì)即可。一些語義錯誤的處理：1、遏止株連錯誤 株連錯誤：由于第一次錯誤，而派生出后面若干額外錯誤。只要消除第一個錯誤，后面若干錯誤也就自動消失。 遏止方法：第一次發(fā)現(xiàn)是標識符引起錯誤時，輸出出錯信息，并用一個“正確”的標識符代替它，并把此新的標識符填進符號表，盡可能正確地填入各種屬性且加上標記。 以后發(fā)現(xiàn)一個引起錯誤的標識符時，查看符號表中相應登記項，如果它已被標記，則不再打印

50、出錯信息。2、遏止重復錯誤 重復錯誤：一種錯誤，發(fā)現(xiàn)n次，報n次錯。 如：x未被說明，程序中出現(xiàn)n次，則n次報x未被說明。 遏止方法： 設(shè)出錯標識符為x 1、若x未經(jīng)說明，則將x填入符號表，并填入鑒別出的屬性。 2、若x已被說明，則查錯誤類表。 如果表中沒有同類錯誤，則輸出出錯信息，并填進錯誤類表中。 如果表中有同類錯誤，則不輸出錯誤信息。第九章 符號表符號表的作用 編譯程序在詞法分析到代碼生成的各階段，不斷地積累和更新表中的信息，并按各自的需要從表中獲取信息。符號表的功能歸結(jié)為以下三個方面：1、收集符號屬性 在分析語言程序中標識符說明部分時，編譯程序根據(jù)說明信息收集有關(guān)標識符的屬性，并在符號

51、表中建立符號的相應屬性信息。如PL/0語言編譯的符號表。2、上下文語義的合法性檢查的依據(jù) 通過符號中屬性記錄可檢查標識符屬性在上下文中的一致性和合法性。如：是否未說明就引用，說明與引用，其屬性、類型是否一致。是否有重復定義。運算量間運算類型是否一致等。3、作為目標代碼生成階段地址分配的依據(jù) 源程序中的變量在目標代碼生成時需要確立其在存儲分配的位置（主要是相對位置）。而地址分配主要根據(jù)變量的類型，在源程序中被說明的位置。 如在第幾層分程序，是靜態(tài)區(qū)還是動態(tài)區(qū)等，分配其在相應數(shù)據(jù)區(qū)中的相對地址，而這些地址分配的依據(jù)都是作為變量的語義信息被收集在該變量的符號表屬性中。符號表的內(nèi)容：1、符號名源程序中

52、一個標識符可以是一個變量名、常量名、函數(shù)名或過程名，登記在符號表中，通常把一個標識符在符號表中的位置（通常是一個整數(shù)）稱之為該標識符的內(nèi)部代碼，從而取代該標識符。2、符號的類型信息符號的種類：如常量、變量、數(shù)組、標號、函數(shù)或過程等，符號的類型，如整型、實型、字符型、布爾型等。數(shù)組：應包括維數(shù)、上下界、計算下標地址時涉及的常量等，放在數(shù)組信息向量表即內(nèi)情向量表中，用于確定存儲分配時所占空間，確定數(shù)組元素的位置。過程或函數(shù)：應包括參數(shù)的個數(shù)、類型、排列次序等用來作調(diào)用過程的匹配處理和語義檢查。記錄結(jié)構(gòu)：應包括其成員的類型、個數(shù)、排列次序等信息。以便確定結(jié)構(gòu)型變量應分配的空間及結(jié)構(gòu)成員的位置。3、符

53、號變量的存儲分配信息存儲類別：如全局量還是局部量，靜態(tài)存儲變量，還是動態(tài)存儲變量等，作為存儲分配的依據(jù)。地址表示：簡單變量或常量，一般是該量在數(shù)據(jù)區(qū)所占單元的絕對或相對地址。數(shù)組，是該數(shù)組在數(shù)據(jù)區(qū)中的首地址，過程或函數(shù)，是該過程或函數(shù)的分程序入口地址。4、層次信息對于分程序嵌套或過程嵌套結(jié)構(gòu)型程序設(shè)計語言，還應包括每個標識符所屬分程序（過程）的層次。符號表的組織： 符號表的組織直接關(guān)系到語義功能的實現(xiàn)和語義處理的時空效率，關(guān)于符號表的組織可從符號表的總體組織和表項屬性信息組織來分別討論。1、符號表的總體組織第一種：按照屬性完全相同的那些符號組織在一起。第二種：把語言中的所有符號都組織在一張符號

54、表中。 優(yōu)點：總體管理集中單一。缺點：若各表項相等，則增加了無用的屬性空間，從而增加了空間開銷。 若各表項不等長，則增加 了對符號表管理的復雜度。第三種：折中方式 根據(jù)符號屬性相似程度分類組織成若干張表，使管 理復雜性及時空效率方面都取得折中的效果。2、符號表項的排列：在編譯程序的整個工作中，符號表被頻繁地用來建立表項，找查表項，填充和引用表項的屬性，因此表項的排列組織對該系統(tǒng)運行的效率起著十分重要的作用。傳統(tǒng)上采用三種構(gòu)造方法:（1）線性組織（按其出現(xiàn)順序）表項按它的符號被掃描到的先后順序建立。線性組織管理簡單但運行效率低。適用于事先能確定符號個數(shù)且符號個數(shù)不大時。（2）排序組織及二分法（a

55、bcd排列）表項按其符號的字符代碼串的值的大小排列。關(guān)于表項的建立和查找通常采用二分法。排序表的運行效率比線性表高，算法復雜性也高于線性表。（3）散列組織 表項位置是由對表項的符號值（即字符代碼串）進行某種函數(shù)操作（通常稱為“雜湊”）所得到的函數(shù)值來確定的，這種函數(shù)通常被稱為雜湊函數(shù)。 符號表的散列組織具有較高的運行效率，因而絕大多數(shù)編譯程序中的符號表采用散列組織。3、關(guān)鍵字域的組織： 在編譯程序中，符號表的關(guān)鍵字域就是符號本身。也稱名字域。（1）等長關(guān)鍵字段 可設(shè)置關(guān)鍵字段為標識符的最大長度。由于程序中的標識符不會總是使用很長的拼寫字，關(guān)鍵字段的這種組織方式在實際使用中會有很多空間是冗余的。（2）關(guān)鍵字池的索引結(jié)構(gòu) 符號表中關(guān)鍵字段是指針，指向該關(guān)鍵字在池中的位置，4、其它域的組織 符號表屬性域的組織，根據(jù)屬性性質(zhì)大致分成兩類：一類是符號表中符號的該屬性值具有相同的類型且