編譯技術與理論課件

第一章引論第一章引論1.1什麼叫編譯程序編譯程序:是指這樣的程式，它能夠把某種語言的程式轉換成另一種語言的程式，而後者與前者在邏輯上是等價的。如果源語言是諸如FORTRAN、Pascal、C、Ada、Smalltalk或Java這樣的“高級語言”，而目標語言如組合語言之類的“低級語言”這樣的翻譯程式則稱之為編譯程序。第一章引論

注意編譯程序與解釋程式的區(qū)別，一個語言的解釋程式是著樣的程式：它以該語言寫的根源程式作為輸入，但不產生目標程式，而是邊解釋邊執(zhí)行根源程式本身。術語“編譯”的內涵是實現(xiàn)從源語言表示的演算法向目標語言表示的演算法的等價變換。第一章引論1.2編譯過程概述掌握編譯過程的五個基本階段，是我們學習編譯原理課程的基本內容，把編譯的五個基本階段與英譯中的五個步驟相比較，有利於對編譯過程的理解：第一章引論英譯與編譯的比較1。識別出句子中的一個個單字2。分析句子的語法結構3。初步翻譯句子的含意4。譯文修飾5。寫出最後譯文1。詞法分析2。語法分析3。語義分析中間代碼生成4。優(yōu)化5。目標代碼生成第一章引論1。2。1詞法分析輸入根源程式，對構成根源程式的字串進行掃描和分解，識別出一個個單詞（也稱單詞符號，或簡稱符號）在詞法分析階段工作所依循的是語言的詞法規(guī)則。描述詞法規(guī)則的有效工具是正規(guī)式和有限自動機。第一章引論1。2。2語法分析語法分析的任務：在詞法分析的基礎上，根據語言的語法規(guī)則，把單詞符號分解成各類語法單位（語法範疇），如“短語”、“句子”、“子句”、“程式段”等。語法規(guī)則通常用上下文無關文法描述。第一章引論1。2。3語義分析與中間代碼的產生這一階段通常包括兩方面的工作首先對各種語法範疇進行靜態(tài)語義檢查，如果正確則進行另一方面的工作，即進行中間代碼的翻譯。通常使用屬性文法描述語義規(guī)則所謂“中間代碼”是一種含義明確，便於處理的記號系統(tǒng)。中間代碼除四元式外，還有三元式、間接三元式、逆波蘭記號、樹形表示等。第一章引論1。2。4優(yōu)化優(yōu)化的任務在於對前段產生的中間代碼進行加工，以期在最後階段產生更為高效（省時間和空間）的代碼優(yōu)化所依循的原則是程式的等價變換規(guī)則其方法有：公共子運算式的提取、迴圈優(yōu)化、刪除無用代碼等。第一章引論1。2。5目標代碼生成這一階段的任務：把中間代碼（或經優(yōu)化處理後）變換成特定機器上的低級語言代碼。它有賴於硬體系統(tǒng)結構和機器指令含義。第一章引論1。3編譯程序的結構表格管理詞法分析器語法分析器語義分析與中間代碼產生優(yōu)化器目標代碼生成器根源程式單詞符號語法單位中間代碼中間代碼目標代碼出錯處理第一章引論

我們可以按照上頁的總框圖設計編譯程序。從圖中我們可以看到除編譯的五個基本階段外，一個完整的編譯程序還應包括“表格管理”和“出錯處理”兩部分

1。3。2表格與表格管理在編譯程式使用的表格中最重要的是符號表它用來登記根源程式中出現(xiàn)的每一個名字以及名子的各種屬性。如一個名字是常量名、變數(shù)名，還是過程名等；如果是變數(shù)名它的類型又是什麼、所站記憶體是多大、地址是什麼等。第一章引論1。3。3出錯處理一個編譯程序不僅能對書寫正確的程式進行編譯，而且應能對處現(xiàn)在根源程式中的錯誤進行處理。如果根源程式有錯，編譯程序應設法發(fā)現(xiàn)錯誤，把有關錯誤報告給用戶。這部分的工作是由專門的一組程式（叫做處錯處理程式）完程的。第一章引論1。3。5編譯前端與後端

前端主要由與源語言有關但與目標機無關的那些部分組成。通常包括詞法分析、語法分析、語義分析與中間代碼產生，有的代碼優(yōu)化工作，也可以包括在前端。

後端包括編譯程序中與目標代碼有關的部分，如與目標機有關的有關的優(yōu)化，和目標代碼的生成等。第一章引論1。4編譯程序的生成以前構造編譯程序大多是用機器語言或組合語言作工具的。為了充分發(fā)揮各種不同硬體系統(tǒng)的效率，為了滿足各種不同的具體要求，現(xiàn)在許多人仍然使用這種工具來構造編譯程序（或編譯程序的核心部分）但是越來越多的人已經使用高級語言作工具來編譯程序。因為這樣可以大大節(jié)省程式設計的時間，熱切構造出來的編譯程序易於閱讀、維護和移植。第一章引論

為此我們用T形圖來表示源語言S、目標語言T和編譯語言I之間的關係，如果A機器上已有一個用A機器碼實現(xiàn)的某高級語言L1的編譯程序，則我們可以用L1語言編寫另一種高級語言L2的編譯程序，把寫好的L2編譯程序經過L1編譯程序編譯後就可得到A機器代碼實現(xiàn)的L2編譯程序。2.1.1語法：任何語言程式都可以看成是一定字元集（稱為字母表）上的字串（有限序列）。但是什麼樣的字串才算是一個合適的程式呢？所謂一個語言的語法是指這樣的一組規(guī)則，用它可以形成和產生一個合適的程式。這些規(guī)則一部分稱為詞法規(guī)則，另一部分能稱為語法規(guī)則（或產生規(guī)則）。注意這裏提到三個概念：a.一個程式只是用一個有限字元集作為字母表；b.詞法規(guī)則是指單詞符號的形成規(guī)則。單詞符號一般包括：各類型的常數(shù)、識別字、基本字、算符和界符等。C.語言的語法規(guī)則規(guī)定了如何從單詞符號形成更大的結構（即語法單位），換言之，語法規(guī)則是語法單位的形成規(guī)則。一般程式語言的語法單位有：運算式、語句、分程式、函數(shù)、過程和程式等。

2.1.2語義：

對於一個語言來說，不僅要給出它的詞法、語法規(guī)則，而且要定義它的單詞符號和語法單位的意義。這就是語義問題。語義是指這樣的一組規(guī)則，使用它可以定義一個程式的意義。我們採用的方法為：基於屬性文法的語法制導翻譯方法。

一個程式語言的基本功能是描述數(shù)據和對數(shù)據的運算。所謂程式，從本質上來說是描述一定數(shù)據的處理過程。在現(xiàn)今的程式語言中，一個程式大體可以視為下麵所示的層次結構

程式副程式或分程式語句運算式數(shù)據引用算符函數(shù)調用

自上而下看上述層次結構：頂端是程式本身，他是一個完整的執(zhí)行單位。一個程式通常是由若干個子程式或分程式組成的，他們常常含有自己的數(shù)據（局部名）。副程式或分程式是由於語句組成的。而組成語句的成分是個種類型的運算式。運算式是描述數(shù)據運算的基本結構，它通常含有數(shù)據引用、算符和函數(shù)調用。

自下而上看上述層次結構：我們希望通過對下層成分的瞭解掌握上層成分，從而掌握整個程式。在學習編譯原理的過程中特別注意：程式語言的每個組成成分都有（抽象的）邏輯和電腦實現(xiàn)兩方面的意義。當從數(shù)學上考慮每一個組成成分時，我們注重它的邏輯意義，當從計算機這個角度來看時，我們注重他在機內的表示和實現(xiàn)的可能性與效率。2.2高級語言的一般特性

2.2.1高級語言的分類；a.強制式語言b.應用式語言c.基於規(guī)則的語言d.面向對象語言

2.2.2幾種程式的典型結構；

FORTRANMAIN

…

ENDSUBROUTINESUB1

…END

…SUBROUTINESUBn

…END一.FORTRAN

一個FORTRAN程式有一個主程序段和若干個（可以是0個）輔助程式段組成。(如右側）

輔助程式段可以是副程式、函數(shù)段或數(shù)據。每程式段由一系列說明語句和執(zhí)行語句組成。各程式段可以獨立編輯。這對模組設計甚為方便。一個FORTRAN程式個程式段所定義的各種名字通常是彼此獨立的。同一個識別字在不同的程式段中一般都可以代表不同的名字，即代表不同的存儲單元，個程式段對它們的引用或賦值是彼此無關的。但是，不同程式段裏的同名公用塊（CommonBlock)卻代表同一個存儲區(qū)域。因此，出現(xiàn)在COMMON語句中的名字所代表的單元在其他程式塊中也可以引用。所以說，公用區(qū)具有全局性。不出現(xiàn)在COMMON中的名字所代表的單元具有局部性。二.PascalPascal是一個允許副程式嵌套定義的語言。一個Pascal程式可以看作是操作系統(tǒng)調用的一個副程式，而副程式中又可以定義別的副程式。programmain

…procedureP1;

…procedureP11;

…begin

…end;begin

…end;procedureP2;

…begin

…end;begin

…end.Pascal這種嵌套結構中允許同一識別字在不同的副程式段中表示不同的名字。關於名字的作用域的規(guī)定是：

a.一個在副程式B1中說明的名字X只在B1中有效（局部於B1）。

b.如果B2是B1的一個內層副程式，且B2中對識別字X沒有新的說明，則原來的名字X在B2中仍然有效。如果B2對X重新作了說明，那麼，B2中對X的任何引用都是指重新說明過的這個X。

2.2.3數(shù)據類型與操作；一個數(shù)據類型通常包括以下三種要素：

a.用於區(qū)別這種類型的數(shù)據對象的屬性

b.這種類型的數(shù)據對象可以具有的值

c.可以作用於這種類型數(shù)據對象的操作

一。初等數(shù)據類型常見的初等數(shù)據類型有：

a.數(shù)值數(shù)據b.邏輯數(shù)據

c.字元數(shù)據d.指針類型

指針是指這樣一種類型的數(shù)據，他們的值指向另一些數(shù)據。一般意義是，假定P是一個指針，P:=addr(X)意味著P將指向X，或說P的值將是變數(shù)X的地址。有些語言用P↑表示指針P的內容。在P:=addr(X)的情況下，如令P↑:=0.3，則意味著X的值是0.3

用電腦術語來說，名字可以看成是代表一個抽象的存儲單元，這個單元可包含一位、一位元組、一字或相繼的許多個字。而這個單元的內容則認為是此名字的值。名字的值就是它所表示的對象。此外，我們還必須指出名字的屬性。一個名字的屬性包括類型和作用域。名字的類型決定了它能具有什麼樣的值，值在電腦內的表示方式，以及對他能施加什麼運算。名字的作用域規(guī)定了他的值存在範圍。二。數(shù)據結構許多程式語言提供了一種由初級數(shù)據定義複雜數(shù)據的手段。下麵我們將概述其中常見的定義方式：

a.數(shù)組從邏輯上說，一個數(shù)組是由同一類型數(shù)據所組成的某種n維矩形結構。沿著每一維的距離稱為一個下標。數(shù)組的每個元素是矩形結構中的一個點，它的位置可通過給出每維的下標來確定。

數(shù)組的每個元素（也稱為下標變數(shù)）是由數(shù)組名連同各維的下標值命名的。如A（i1,i2…,in）。根據數(shù)組的類型，每個數(shù)組元素在計算機中占有同樣大小的存儲空間。如果一個數(shù)組所需的存儲空間大小在編譯時就已知道則稱此數(shù)組是一個確定數(shù)組；否則稱為可變數(shù)組。

數(shù)組的存儲表示有多種形式，最簡單的一種是把整個數(shù)組按行（或按列）存放在一片連續(xù)存儲區(qū)中。數(shù)組元素的地址計算和數(shù)組的存儲方式密切相關。關於數(shù)組元素的地址計算公式，數(shù)據結構教材中有詳細的介紹。編譯程序要做的就是實現(xiàn)地址計算公式，使數(shù)組元素得到正確的引用。在編譯過程中，當碰到數(shù)組說明時，必須把數(shù)組的有關的資訊記錄在一個“內情向量”之中，以便以後計算數(shù)組元素的地址時引用這些資訊。每個數(shù)組的內情向量必須包括：維數(shù)，各維的上下限，首地址，以及數(shù)組元素的類型等。b.記錄從邏輯上說，記錄結構是由已知類型的數(shù)據組合起來的一種結構。記錄結構是許多程式語言的一類重要的數(shù)據結構。不同語言定義記錄結構的方式也不同。如：Pascal語言採用下麵形式定義記錄：CARD:recordNAME:array[1…20]ofchar;AGE:integer;MARRIED:booleanend;

這說明定義了一個記錄CARD.它是一個含有三個分量的記錄結構：NAME,字元數(shù)組；AGE,整型量；MARRIED,布爾量。記錄結構的每個分量（域）所需佔用的存儲單元（位元組）數(shù)，成為該域的長度。當知道一個記錄的地址後，通過每個域的長度就可算出個域的地址，因為我們容易推出每個域相對於記錄結構起點的相對數(shù)OFFSET：此域之前各域長度的總和。如：就CARD而言，NAME,AGE,MARRIED的相對數(shù)OFFSET分別為0、20、24。於是，假定CARD的首地址為a，那麼，

CARD.NAME地址為aCARD.AGE地址為a+20CARD.MARRIED地址為a+24

2.2.4語句與控制結構一。運算式：一個運算式是由運算量（亦稱運算元，即數(shù)據引用或函數(shù)調用）和算符組成的。對於大多數(shù)程式語言來說，運算式的形成規(guī)則可概括為：（1）變數(shù)（包括下標變數(shù)）、常數(shù)是運算式；（2）若E1、E2為運算式，θ為二元算符，則E1θE2為運算式；（3）若E為運算式，θ為一元算符，則θE為運算式；（4）若E為運算式，則（E)是運算式。

在多數(shù)語言中算術算符和邏輯算符的優(yōu)先順序一般規(guī)定如下：乘冪（**或↑）一元負（-）乘、除（*，/，÷）加、減（+，-）關係符（<,=,>,<=,<>,>=)非（﹁，not,或.NOT.)與（∧，&,and或.AND.)或（∨，∣，or或.OR.)隱含（

或imp)等值（≡,～或equi)

算符的代數(shù)性質（交換率、結合率和分配率）常?？捎脕韮?yōu)化目標程式的品質。但是必須注意兩點：（1）代數(shù)性質引用到什麼程度視具體語言的不同而不同。如在ALGOL中把

A*B+C*D處理成C*D+A*B,則至少是對ALGOL不夠忠實。（2）數(shù)學上成立的代數(shù)性質在電腦上未必完全成立。如：(A+B)+C=A+(B+C)在電腦上並不普遍成立。二。語句不同程式語言含有不同形式和功能的各種語句。從功能上說語句大體可分執(zhí)行性語句和說明性語句兩大類，說明性語句旨在定義不同數(shù)據類型的變數(shù)或運算。執(zhí)行性語句旨在描述程式的動作。執(zhí)行性語句又可分賦值語句、控制語句和輸入/輸出語句.從形式上說，語句還可分為簡單句、複合句和分程式等。1。賦值語句我們知道，每個名字有兩方面的特徵：一方面它代表一定的存儲單元，另一方面它又以該單元的內容作為值。賦值語句A:=B的意義是：“把B的值送入A所代表的單元”也就是說：在賦值句中，賦值號‘：=’左右兩邊的變數(shù)名扮演著兩種不同的角色。對賦值號右邊的B我們需要的是它的值；對於左邊的A我們需要的是它們的所代表的存儲單元（的地址）。為了區(qū)分一個名字的這兩種特徵，我們把一個名字所代表的那個存儲單元（地址）稱為該名字的左值；把一個名字的值稱為該名字的右值。2。控制語句多數(shù)語言中所含的控制語句有：無條件轉移語句:gotoL條件語句：ifBthenSifBthenS1elseS2迴圈與句：whileBdoSrepeatSuntilBfori:=E1stepE2untilE3doS過程調用語句：callP(X1,X2,…,Xn)返回語句：return(E)

重要的是我們必須瞭解這些語句在不同語言中的不同含義。3。說明語句說明語句旨在定義名字的性質。編譯程序把這些性質登記在符號表中，並檢查程式中名字的引用和說明是否相一致。許多說明語句沒有相應的代碼。但有些語句，如過程說明語句，和可變數(shù)組說明語句則有相應的目標代碼。4。簡單句和複合句簡單句是指那些不含其他語句成分的基本句，如賦值句、goto句等。複合句則指那些句中有句的語句。本節(jié)內容是對高級語言中為編譯原理課程所關心特性的總結2.3程式語言的語法描述對於高級程式語言及編譯程序而言，語言的語法定義是非常重要的。本節(jié)將介紹語法結構的形式描述問題。首先引入幾個概念：設

是一個有窮字母表，它的每個元素稱為一個符號。

上的一個符號串是指由

中的符號所構成的又窮序列。不包含符號的序列稱為空字，記為

。用

*表示

上的所有符號串的全體，空字也包括在其中。如：若={a,b}則*={,a,b,aa,ab,bb,aaa,…}。

表示不含人何元素的空集{}。這裏要注意

、{}和{}的區(qū)別。

*的子集U和V中的（連接）積定義為:UV={∣U&V}

即集合UV中的符號串是由U和V的符號串連接而成的。注意，一般UVVU，但（UV)W=U(VW).V自身的n次（連接）積記為：

Vn=VV…V(n個V)規(guī)定V0={}.

令：V*=V0V1V2

…

稱V*是V的閉包。記V+=VV*,稱V+是V的正則包。閉包V*中的每個符號都是由V中的符號串經有限次連接而成的。

2.3.1上下文無關文法：文法是描述語言的語法結構的形式規(guī)則（即語法規(guī)則）。所謂上下文無關文法是這樣一種文法，它所定義的語法範疇（或語法單位)是完全獨立於這種範疇可能出現(xiàn)的環(huán)境的。請仔細閱讀課本P27頁的英文分析的例句，定義英文句子的規(guī)則可以說是一個上下文無關文法。其中He,me,book,gave,a等，稱為終結符號；<句子>、<主語>、<謂語>等為非終結符號；這個文法最終是要定義<句子>的語法結構，所以<句子>在這裏成為開始符號；<間接賓語>→<冠詞><名詞>這種書寫形式稱為產生式。歸納起來，一個上下文無關文法G包括四個組成部分：一組終結符號，一組非終結符，一個開始符號，以及一組產生式。所謂終結符號乃是組成語言的基本符號，即在程式語言中以前屢次提到的單詞符號，如基本字，識別字，常數(shù)，算符和界符等所謂非終結符號（也稱語法變數(shù)）用來代表語法範疇。如“算術運算式”、“布爾運算式”、“過程”等。一個非終結符代表一個一定的語法概念。因此非終結符是一個類（或集合）記號，而不是個體記號。開始符號是一個特殊的非終結符號，它代表所定義的語言中我們最感興趣的語法範疇，這個語法範疇通常稱為“句子”。但在程式語言中我們最終感興趣的是“程式”這個語法範疇，而其他的語法範疇都只不過是構造“程式”的一塊塊磚石。產生式（也稱為產生規(guī)則或簡稱規(guī)則）是定義語法範疇的一種書寫規(guī)則。一個產生式的形式是A→α,其中箭頭左邊的A是一個終結符，稱為產生式的左部符號；箭頭右邊的α是終結符號或與非終結符號組成的一符號串，稱為產生式的右部。產生式是定義語法範疇的。如要定義一類含+、*的算術運算式，這個定義可以這樣給出：“變數(shù)是一個算術運算式；若E1和E2是算術運算式，則E1+E2、E1*E2和(E1)也是算術運算式。對於這個定義，用產生式描述：

E→iＥ→Ｅ＋ＥＥ→Ｅ＊ＥＥ→（Ｅ）其中Ｅ代表“算術運算式”，ｉ代表“變數(shù)”形式上定義一個上下文無關文法Ｇ是一個四元式（ＶＴ，ＶＮ，Ｓ，￡）其中ＶＴ是一個非空有限集，它的每一個元素稱為終結符號；ＶＮ是一個非空有限集，它的每一個元素稱為非終結符號，ＶＴ∩ＶＮ＝

；Ｓ是一個非終結符號，稱為開始符號；￡是一個產生式（有限）集合，每個產生式形式是Ｐ→

，其中，Ｐ∈ＶＮ，

∈（ＶＴ∪ＶＮ）＊開始符號S至少必須在某一產生式的左部出現(xiàn)一次。假定G是一個文法，S是它的開始符號。如果S

*(表示從S出發(fā)，經0步或若干步可推出

），則稱

是一個句型。僅含終結符號的句型是一個句子。文法G所產生的句子的全體是一個語言，將它記為L(G).L(G)={|S+&∈VT}例如：終結符號串（i*i+i)是文法

E→E+E|E*E|(E)|ｉ(2.1)

的一個句子。是因為有

E(E)(E+E)(E*E+E)(i*E+E)(i*i+E)(i*i+i)從開始符號E至（i*i+i)的一個推導。而E,(E),(E*E+E)等是文法的句型。

下麵介紹幾個簡單文法的例子：例2。1考慮一個文法G1:S→bAA→aA|a它定義了一個什么語言呢？從開始符S出發(fā)，我們可以推出如下句子：

SbAbaSbAbaAbaaSbAbaA…baa…a可以寫為：L(G1)={ban|n≥1}例2.2設有文法GS→P|aPPbP→ba|bQaQ→ab

求語言L(G).

解：

L(G)={ba,baba,abab,ababab…}例2。3構造一個文法G3使

L(G3)={anbn|n≥1}

解;S→aSb|ab

為了對句子結構進行確定性分析，我們往往只考慮最左推導或最右推導。所謂最左推導是指：任何一步

都是對

中的最左非終結符進行替換的。同樣，可定義最右推導。2.3.2語法分析樹與二義性

前面我們提到過可以用一張圖表示一個句型的推導，這種表示稱為語法分析樹，或簡稱語法樹。語法樹的根結由開始符號所標記。隨著推導的展開，當某個非終結符被它的某個候選式所替換時，這個非終結符的相應結就產生了下一代新結。每個新結和其父親結間都有一條連線。在一棵語法樹生長過程中的任何時刻，所有那些沒有後代的端末結自左至右排列起來就是一個句型。

例如對於文法（2.1)關於（i*i+i)的推導形成語法樹如圖2。2

圖2。2語法樹

一個句型是否只對應唯一的一棵語法樹呢？也就是說它是否只有唯一的一個最左（最右)推導呢？不盡然。如文法2.1,關於（i*i+i)就存在一個與2。2非常不同的推導：

E(E)(E*E)(i*E)(i*E+E)(i*i+E)(i*i+i)其對應語法樹：

圖2。2與圖2。3的不同之處在於從第二代三代過渡開始。對於前者，我們選用規(guī)則E→E+E,而後者我們選用E→E*E。這裏不是同代兄弟生兒子的先後次序的不同而是生什麼兒子的不同，後面的這個不同是本質上的的差異。這意味著我們可以用兩種完全不同的辦法產生同一個句子。

如果一個文法存在某個句子對應兩棵不同的語法樹，則稱這個文法是二義的。也就是說，若一個文法存在某個句子，它有兩個不同的最左（最右)推導，則這個文法是法是二義的。最後，作為描述程式語言的上下文無關文法，我們對它有幾點限制。（1）文法中不含任何下麵形式的產生式：P→P因為這種產生式除了產生二義性外沒有任何用處。

（2）每個非終結符P必須有用處。這一方面意味著，必須存在含P的句型；也就是，從開始符號出發(fā)，存在推導S

*P.

另一方面意味著，必須存在終結符串

VT*,使得P

+

；也就是，對於P不存在永不終結的回路。我們以後所討論的文法均假定滿足上述兩條件。

2.3.3形式語言鳥瞰：喬姆斯基把文法分為四種類型即0型、1型、2型、3型。0行強於1型，1行強於2型，2型強於3型。這幾文法的差別在於對產生式施加不同的限制。我們說G=(VT,VN,S,

)是一個0型文法，如果它的每個產生式

是這樣的結構

(VNVT)*且至少有一個非終結符，而(VNVT)*。0型文法也稱短語文法。如果對0型文法分別施加以下的第i條限制，則我們就得到第i型文法:(1)G的任何產生式

均滿足

|

|≤|

|（其中|

|和|

|分別為

和

的長度；僅S例外，但S不得出現(xiàn)在任何產生式的右部。

(2）G的任何產生式為A,AVN,(VNVT)*。

(3)G的任何產生式為AB或A，其中VT*，A、BVN。

其中1型文法也稱上下文有關文法。這種文法意味著，對非終結符進行替換式務必考慮上下文並且一般不允許替換成空串

。2型文法也稱上下文無關文法，注意其語言定義：

G的任何產生式為A→β，A∈VN，β∈（VN∪VT)*表明凡出現(xiàn)在產生式左邊的符號都是非終結符。

3型文法也稱右線性文法。3型文法還有另一種形式，稱左線性文法：一個文法G為左線性文法，如果G的任何產生式為

A→B

或A→

，其中

∈VT*,A、B∈VN

由於3型文法等價於正規(guī)式所以也稱正規(guī)文法。例題與習題解答

[例2.1]：試構造生成語言L={anbnci|n

1,i0}的文法解：G(Z):ZABAaAb|abBcB|[例2。2]：已知語言L={anbbn|n1},寫出產生L的文法。[解]：

G[S]:SaAbAaAb|b[例2。3]：已知文法G=({A,B,C},{a,b,c},A,P)其中產生式P由以下組成：

AabcAaBbcBbbBBcCbccbCCbaCaaBaCaa

問：此文法表式的語言是什麼？[解]：由於A為開始符。由於AaBbcabBcabCbccaCbbcc

aabbcc

語言為：{anbncn,n>0}[例2。4]：試構造語言L={anbnci|n>=1,i>=0}的文法。

[解]：G(Z):ZABAaAb|abBcB|第三章詞法分析

詞法分析器輸出的單詞符號常常表示為二元式：（單詞種別，單詞符號的屬性值）單詞種別通常用整數(shù)編碼。一個語言的單詞符號如何分種，分成幾種，怎樣編碼是一個技術問題。它取決於處理上的方便。識別字一般統(tǒng)歸為一種。常數(shù)則宜按類型（整、實、布爾等）分種。關鍵字可視其全體為一種，也可以一字一種。採用一字一種的分法實際處理起來較為方便。運算符可採用一符一種的分法，但也可以把具有一定共性的運算符視為一種。至於界符一般一符一種的分法。第三章詞法分析

如果一個種別只含有一個單詞符號，那麼對於這個單詞符號，種別編碼就完全代表它自身了。若一個種別含有多個單詞符號，那麼，對於它的每個單詞符號，除了給出種別編碼之外，還應給出有關單詞符號的屬性資訊。

單詞符號的屬性是指單詞符號的特徵或特性。屬性值則是反映特性或特徵的值。例如，對於某個識別字，常將存放它有關資訊的符號表項的指針作為其屬性值；對於某個常數(shù)，則將存放它的常數(shù)表項的指針作為其屬性值。第三章詞法分析

作為例子考慮下述C++代碼段：

while(i>=j)i--;

經詞法分析器處理後，它將轉換為如下的單詞符號序列：

<while,-><(,-><id,指向i的符號表項的指針〉<>=,-><id,指向j的符號表項的指針><),-><id,指向i的符號表項的指針><--,-><;,->第三章詞法分析3.1.2詞法分析器作為獨立副程式我們把詞法分析器安排成一個獨立副程式，每當語法分析器需要一個單詞符號時就調用這個副程式。每一次調用，詞法分析器就從符號串中識別出一個單詞符號，把它交給語法分析器。這樣，把詞法分析器安排成一個副程式似乎比較自然。在後面的討論中，我們假定詞法分析器是按這種方式進行工作的。第三章詞法分析3。2詞法分析器的設計

3。2。1輸入、預處理詞法分析器工作的第一步是輸入根源程式文本。輸入串一般放在一個緩衝區(qū)中，這個緩衝區(qū)稱輸入緩衝區(qū)。詞法分析器的工作可以直接在這個緩衝區(qū)中進行。但在許多情況下，把輸入串預處理一下，對單詞符號的識別工作將是比較方便的。預處理工作包括對空白符、跳格符、回車符和換行符等編輯性字元的處理，及刪除注解等。我們可以設想構造一個預處理副程式，他完成上面的工作。每當詞法分析器調用它時就處理出一串確定長度的輸入字元，並將其裝入詞法分析器所指定的緩衝區(qū)中（稱為掃描緩衝區(qū)）。這樣分析器就可以在此緩衝區(qū)中直接進行單詞符號的識別工作。第三章詞法分析

分析器對掃描緩衝區(qū)進行掃描時一般使用兩個指示器，一個指向當前正在識別單詞的開始位置。（指向新單詞的首字元），另一個用於向前搜索以尋找單詞的終點。不論掃描緩衝區(qū)設得多大都不能保證單詞符號不會被緩衝區(qū)的邊界所打斷。因此，掃描緩衝區(qū)最好使用如下一分為二的區(qū)域：

第三章詞法分析

假定每半個區(qū)可容120個字元，而這兩個半區(qū)又是互補的。如果搜索指示器從單詞起點出發(fā)搜索到半區(qū)的邊緣但尚未達到單詞的終點，那麼就調用預處理副程式，令其把後續(xù)的120個字元裝入另半區(qū)。我們認定在另半區(qū)一定可以達到單詞的終點。這意味著得標示符和常數(shù)的長度實際上必須加以限制，否則即使緩衝區(qū)再大也無濟於事。第三章詞法分析圖3。1詞法分析器3。2。2單詞符號的識別：超前搜索詞法分析器的結構圖如圖3。1所示。第三章詞法分析

當詞法分析器調用預處理副程式處理出一串輸入字串放進掃描緩衝區(qū)之後，分析器就從此緩衝區(qū)中逐一識別單詞符號。當緩衝區(qū)裏的字串被處理完之後，它又調用預處理程式裝入新串。下麵我們來介紹單詞符號識別的一個簡單方法-----超前搜索第三章詞法分析

關鍵字的識別像FORTRAN這樣的語言，關鍵字不加保護（只要不引起矛盾，用戶可以用它們作為普通識別字），關鍵字和用戶自定義的識別字或標號之間沒有特殊的界符作間隔。這使得關鍵字的識別甚為麻煩。請看下麵例子：

1DO99K=1,102IF(5.EQ.M)I=103DO99K=1.104IF(5)=55

這四個語句都是正確的FORTRAN語句。語句1和2分別是DO和IF語句，它們都是以某基本字開頭的。語句3和4是賦值語句，它們都是以用戶自定義的識別字開頭的。第三章詞法分析

為了從1、2中識別出關鍵字DO和IF，我們必須要能夠區(qū)別1、3和區(qū)別2、4。語句1、3的區(qū)別在於等號之後的第一個界符：一個為逗號，另個為句末符。語句2、4的主要區(qū)別在於右括弧後的第一個字元：一個為字母，另一個為等號。這就是說，為了識別1、2句中的關鍵字，我們必須超前掃描許多個字元，超前到能夠肯定詞性的地方為止。對於1、3來說，儘管都以‘D’和‘O’兩個字母開頭，但不能一見‘DO’就認定是DO語句。我們們必須超前搜索，跳過所有的字母和數(shù)字，看看是否有等號。如果有，再向前搜索。若下一個界符是逗號，則可以肯定DO應為關鍵字。否則，DO不構成關鍵字，它只是用戶識別字的頭兩個字母。所以為了區(qū)別1和3，我們必須超前掃描到等號後的第一個界符處。第三章詞法分析

對於2和4來說，必須超前掃描到與IF後的左括弧相對應的那個右括弧之後的第一個字元為止。若此字元是字母，則得邏輯IF。若此字元為數(shù)字，則得算術IF。否則，應認為是用戶自定義識別字IF.

標識符的識別、常數(shù)的識別及算符和界符的識別相類似可以參考課本P40,P41這裏就不再多述。

3。2。3狀態(tài)轉換圖使用狀態(tài)轉換圖是設計詞法分析器的一種好途徑。轉換圖是一張有限方向圖。在轉換圖中，結點代表狀態(tài)，用園圈表示。狀態(tài)之間用箭弧連結。箭弧上的標記（字元）代表在射出結點（即箭弧始結點）狀態(tài)下可能出現(xiàn)的輸入字元或字元類。第三章詞法分析

例如圖3。2（a)表示：在狀態(tài)1下，若輸入字元為X，則讀進X，並轉換到狀態(tài)2。若輸入字元為y，則讀進Y，並轉換到狀態(tài)3。一張轉換圖只包含有限個狀態(tài)（即有限個結點），其中有一個被認為是初態(tài)，而且實際上至少要有一個終態(tài)（用雙圈表示）。圖3。2狀態(tài)轉換圖第三章詞法分析

一個狀態(tài)轉換圖可用於識別一定的字串。例如，識別識別字的轉換圖如圖3。2（b)所示。其中0為初態(tài)，2為終態(tài)。這個轉換圖識別識別字的過程是：從初態(tài)0開始，若在狀態(tài)0下輸入字元是字母，則讀進它，並轉入狀態(tài)1。在狀態(tài)1之下，若輸入字元為字母或數(shù)字，則讀進它，並重新進入狀態(tài)1。一直重複這個過程直到發(fā)現(xiàn)輸入字元不再是字母或數(shù)字時（這個字元已經被讀進）就近入狀態(tài)2。狀態(tài)2是終態(tài)，它意味著到此已經識別出一個識別字。終態(tài)上打個*號，表示多讀進了一個不屬於識別字部分的字元，應把它退還給輸入串，如果在狀態(tài)0時輸入字元不為“字母”，則意味著這個轉換圖不工作。圖3。2狀態(tài)轉換圖第三章詞法分析

又如書中圖3。2（c)是識別整數(shù)的轉換圖。其中0為初態(tài)，2為終態(tài)。書中圖3。2（d)是一個識別FORTRAN實型常數(shù)的轉換圖。其中0態(tài)為初態(tài)，7態(tài)為終態(tài)。一個非常重要的事實是，大多數(shù)程式語言的單詞符號都可以用轉換圖予以識別。作為一個綜合例子，課本P42構造了一個識別某個簡單語言的所有單詞符號的轉換圖。希望同學們好好讀一下。第三章詞法分析3。2。4狀態(tài)轉換圖的實現(xiàn)轉換圖容易用程式實現(xiàn)。最簡單的辦法是讓每個狀態(tài)結點對應一小段程式。在編制程式的過程中課本引進了一組全局變數(shù)和過程。將它們作為實現(xiàn)轉換圖的基本成分。希望同學能記住它們。第三章詞法分析

3.3正規(guī)運算式與有限自動機為了更好地使用狀態(tài)轉換圖構造詞法分析器，為了討論詞法分析器的自動生成，還需要將轉換圖的概念形式化。為此我們引入：正規(guī)式，正規(guī)集，自動機等概念。

3.3.1正規(guī)式與正規(guī)集

對於字母表Σ，我們感興趣的是它的一些特殊的字集，即所謂正規(guī)集。我們使用正規(guī)式這個概念來表示正規(guī)集。第三章詞法分析

下麵是正規(guī)式和正規(guī)集的定義：（1）ε和都是

Σ上的正規(guī)式，他們所表示的正規(guī)集分別為{ε}和；（2）任何a

Σ,a是Σ上的一個正規(guī)式，它所表示的正規(guī)集為{a}；（3）假定U和V都是Σ上的正規(guī)式，他們所表示的正規(guī)集分別記為L(U)和L(V),並且，(U|V),(UV)*和（U)*也都是正規(guī)式，它們所表示的正規(guī)集分別為L(U)L(V),L(U)L(V)(連接積）和（L(U))*（閉包）僅由有限次使用上述三步驟而得到的運算式才是Σ上的正規(guī)式。僅由這些正規(guī)式所表示的字集才是Σ上的正規(guī)集。第三章詞法分析

通過這一節(jié)的學習，根據給出的簡單正規(guī)式，應會寫出其正規(guī)集。

[3。1]令Σ={a,b}其正規(guī)式和正規(guī)集如下：正規(guī)式正規(guī)集

ba*Σ上所有以b為首後跟著任意多個a

的字

a(a|b)*Σ上所有以a為首的字。（a|b)*(aa|bb)(a|b)*正規(guī)集是所有兩各相繼的a或相繼的b的字。

第三章詞法分析[3。2]令Σ={A,B,0,1},則：正規(guī)式正規(guī)集(A|B)(A|B|0|1)*Σ上的“識別字”的全體（0|1）（0|1）*Σ上“數(shù)”的全體若兩個正規(guī)式所表示的正規(guī)集相同，則認為二者等價。兩個等價的正規(guī)式U和V記為U=V。例如：b(ab)*=(ba)*b等第三章詞法分析3.3.2確定有限自動機（DFA)

確定有限自動機(DFA)是一個五元式

M=(S,Σ,δ,s0,F)其中:(1)S是一個有限集，它的每個元素稱為一個狀態(tài)。（2）是一個有窮字母集，它的每個元素稱為一個輸入字元。（3）δ是一個從Sx

至S的單值部分映射。δ(s,a）=S’。意味著：當現(xiàn)行狀態(tài)為s、輸入字元為a時，將轉換到下一個狀態(tài)S’。我們稱S’為s的後繼狀態(tài)。（4）S0S，是唯一的初態(tài)。（5）FS，是一個終態(tài)機（可空）第三章詞法分析

顯然，DFA可以用一個矩陣表示，該矩陣的行表示狀態(tài)，列表示輸入字元，矩陣元表示δ(s,a）的值，該矩陣稱為狀態(tài)轉換矩陣。

DFA也可以表示成一張（確定的）狀態(tài)轉換圖。假定DFAM含有m個狀態(tài)n個輸入字元，那末，這張圖含有m個狀態(tài)結點，每個結點頂多有n條箭弧射出和別的結點相連接，每條箭弧用上的一個不同字元作標記，整張圖含有唯一的初態(tài)和若干個（可以是0個）終態(tài)結點。

第三章詞法分析

對於*中的任何一個字元，若存在一條從初態(tài)結點到某一終態(tài)結點的通路，且這條通路上所有箭弧的標記符連接成的字等於，則稱為DFAM所識別（讀出或接受）。若M的初態(tài)結點同時又是終態(tài)結點，則為空字可以為M所識別。DFAM所能識別的字的全體記為L(M).第三章詞法分析[例]有DFAM=({0,1,2,3},{a,b},,0,{3})其中：（0,a)=1;（0,b)=2

（1,a)=3;（1,b)=2

（2,a)=1;（2,b)=3

（3,a)=3;（3,b)=3問：有幾個狀態(tài)？幾個輸入字元？並畫出其轉換圖。L(M)=?解：有0，1，2，3共四個狀態(tài)。輸入字元為a,b兩個。其狀態(tài)轉換圖如右L(M)為在上所有含相繼兩個a或相繼兩個b的字。第三章詞法分析3。3。3非確定有限自動機(NFA)

一個非確定有限自動機（NFA)是一個五元式

M=(S,Σ,δ,S0,F)其中:(1)S同3。3。2的1（2）同3。3。2的2（3）δ是一個從SxΣ*到S的子集的映照，即δ：SxΣ*→2s

(4)S0

S,是一個非空的初態(tài)集；（5）FS，是一個終態(tài)集（可空）第三章詞法分析

顯然，NFA也可以表示成一張狀態(tài)轉換圖。假定NFA含有m個狀態(tài)n個輸入字元，那末，這張圖含有m個狀態(tài)結點，每個結點可以射出若干條箭弧和別的結點相連接，每條箭弧用*上的一個字（不一定要不同的字而且可以是空字）作標記（稱為輸入字），整張圖至少含有一個的初態(tài)和若干個（可以是0個）終態(tài)結點。某結點既可以是初態(tài)也可以是終態(tài)結點。第三章詞法分析

對於*中的任何一個字元，若存在一條從初態(tài)結點到某一終態(tài)結點的通路，且這條通路上所有箭弧的標記符連接成的字（忽略那些標記為的?。┑褥?，則稱為NFAM所識別（讀出或接受）。若M的初態(tài)結點同時又是終態(tài)結點，或者存在一條某處態(tài)結點到某各終態(tài)結點的通路，則為空字可以為M所識別。這裏應注意DFA與NFA的異同點。第三章詞法分析顯然DFA式NFA的特例。對於每個NFAM存在一個DFAM”，使L(M)=L(M”)。其證明如下（略）（這個證明需要掌握）在這個證明中我想特別強調的是課本P49頁下邊提到的對M的狀態(tài)轉換圖進一步施行圖3。7所示的替換，其中k是新引入的狀態(tài)。第三章詞法分析

書中的這個圖3。7同時也是從正規(guī)式畫有限自動機狀態(tài)轉換圖的重要方法。對於正規(guī)式中的連接可按1式畫其轉換圖，對於或可用2式，對於閉包可用3式將正規(guī)式轉換為狀態(tài)轉換圖靈活使用這些規(guī)則非常重要的。如：正規(guī)式：R=(a*b)*ba(a|b)*

可以畫為：

第三章詞法分析其中（a*b)*和(a|b)*分別可以看成一個閉包。形成A和G結點。

[例]：畫出正規(guī)式：（a|b)*(aa|bb)(a|b)*對應的NFA第三章詞法分析[例]：用狀態(tài)子集法構造圖3。6的狀態(tài)轉換矩陣：表3。3IIaIb{X,5,1}{5,3,1}{5,4,1}{5,3,1}{5,3,1,2,6,Y}{5,4,1}{5,4,1}{5,3,1}{5,4,1,2,6,Y}{5,3,1,2,6,Y}{5,3,1,2,6,Y}{5,4,1,6,Y}{5,4,1,6,Y}{5,3,1,6,Y}{5,4,1,2,6,Y}{5,4,1,2,6,Y}{5,3,1,6,Y}{5,4,1,2,6,Y}{5,3,1,6,Y}{5,3,1,2,6,Y}{5,4,1,6,Y}第三章詞法分析

表3。4對表3。3中狀態(tài)子集從新命名後狀態(tài)轉換矩陣

Sab012132215334465

565

634第三章詞法分析

圖3。8未化簡DFA第三章詞法分析

3.3.4,3.3.5正規(guī)文法，正規(guī)式與有限自動機的等價性證明不作要求

3.3.6確定有限自動機的化簡

是本節(jié)應掌握的內容。(參看P56)

我們這裏舉個例子幫助理解這個過程：

[3。6例]：圖3。8所示的化簡過程是：首先把M的狀態(tài)分為兩組：終態(tài)組{3，4，5，6}，和非終態(tài)組{0，1，2}

其次考察終態(tài)組，由於

{3，4，5，6}a{3,4,5,6}和

{3，4，5，6}b{3,4,5,6}所以不能再劃分第三章詞法分析

再考察{0，1，2}由於

{0，1，2}a{1，3}，它既不屬於{0，1，2}也不屬於{3，4，5，6}，因此應將其一分為二，由於1態(tài)經a弧到達3態(tài)，而且狀態(tài)0，2經a弧到達1態(tài)故應把1態(tài)分出形成{1}，{0，2}?，F(xiàn)在劃分已經有3個組：{3，4，5，6}，{1}，{0，2}。由於{0，2}b={2,5}未包括在上述分組中，故{0，2}應一分為二{0}，{2}。到此四個分組{3，4，5，6}，{0}，{1}，{2}。每個組都不可再分。最後，令狀態(tài)3代表{3，4，5，6}。把原來到達4，5，6的弧都導入3，並刪除4，5，6狀態(tài)。得到化簡的DFA.第三章詞法分析3.4詞法分析器的自動產生我們用正規(guī)式描述單詞符號，並研究如何從正規(guī)式產生識別這些單詞符號的詞法分析程式。首先介紹一個描述詞法分析器的語言LEX，討論LEX的實現(xiàn)，從而，用它來描述和自動產生所需的各種詞法分析器。

3。4。1語言LEX的一般描述

一個LEX根源程式主要包括兩部分。一部分是正規(guī)定義式，另一部分是識別規(guī)則第三章詞法分析3。4。2超前搜索為超前搜索，我們引進一個正規(guī)式運算符‘/’，用它來指出一個單詞符號的截取點。於是關於“DO”的識別規(guī)則可以寫為：

DO/(letter|digit)*=(letter|digit)*,{動作}

這意味著要求詞法分析器L向前掃描到逗號處，識別除具有下列詞形的輸入子串：

DO/(letter|digit)*=(letter|digit)*

在尋找到這種匹配後，就按識別規(guī)則中斜線所指處將輸入串截斷，取其前一部分字串作為詞法分析器的輸出，而將後一部分歸還輸入串。3。4。3LEX的實現(xiàn)請讀書P61.第三章詞法分析例題與習題解答[例3。1]寫能被5整除的十進位整數(shù)的文法及正則運算式。解：能被5整除的文法：

G[Z]:Z→(+|-

)A(0|5)

A→0|1|2|3|4|5|6|7|8|9|AA如果要求：除零以外不以0開頭，責文法為：

G[Z]:Z→(+|-)A(0|5)A→AB|CB→0|C|BBC→0|1|2|3|4|5|6|7|8|9正則運算式：G[Z]:Z=(+|-)A*(0|5)A∈(0,1,2,3,4,5,6,7,8,9)第三章詞法分析[例3。2]寫一個文法，使其語言是奇數(shù)集，且每個奇數(shù)不以0開頭。解：文法G(N)：

N→AB|B

A→AC|D

B→1|3|5|7|9

D→B|2|4|6|8

C→0|D

第三章詞法分析[例3。3]寫出能被3整除十進位整數(shù)的文法和正則運算式：解：能被3整除的文法：

G=({0,1,2,3,4,5,6,7,8,9},{S,A,B},S,P,)其中P為：S->(0|3|6|9)S|εS->(1|4|7)A|(2|5|8)BA->(0|3|6|9)A|(1|4|7)B|(2|5|8)SB->(0|3|6|9)B|(2|5|8)A|(1|4|7)S整則運算式：

Z=a*|(bc)*|(cb)*|(a|cibi)*|(ciabi)*(i>=1)a∈(0,3,6,9)b∈(1,4,7)c∈(2,5,8)

第三章詞法分析[例3。4]：已知有限自動機如圖(1)以上狀態(tài)轉換圖表示的語言有什麼特徵？(2)寫出其正規(guī)式與正規(guī)文法.(3)構造識別該語言的有限自動機DFA.第三章詞法分析

解：（1）L={W|W{0,1},並且W至少有兩個連續(xù)的1}（2）正則式為（0|1)*11(0|1)*

正則文法G(Z)為：

Z0Z|1Z|1AA1B|1B0B|1B|0|1（3）將圖中有限自動機確定化：首先從處態(tài)A出發(fā)：第三章詞法分析

II0I1(1){A}(1){A}(2){A,B}(2){A,B}(1){A}(3){A,B,C}(3){A,B,C}(4){A,C}(3){A,B,C}(4){A,C}(4){A,C}(3){A,B,C}其相應的DFA如下圖：第三章詞法分析

將這個DFA最小化：首先分終態(tài)和非終態(tài)兩個集K1={1,2}和K2={3,4}

由於狀態(tài)1輸入1到達狀態(tài)K1集，而狀態(tài)2輸入1到達K2集故將k1分為K11={1},K12={2}

由於狀態(tài)3，和4輸入1，或0都到達k2集所以狀態(tài)3，4等價。則可以分割成三個子集：

{1}，{2}，{3，4}第三章詞法分析

所以將DFA最小化的狀態(tài)圖如下：第三章詞法分析[例3.5]請構造與正則式R=(a*b)*ba(a|b)*等價的狀態(tài)最少的DFA（確定有限自動機）解：（1）首先構造轉換系統(tǒng)圖：（2）由系統(tǒng)轉換圖構造DFA（NFA確定化）設初態(tài)為[S,A,B,G,F]第三章詞法分析

NFA確定化為DFA的過程：

IIaIb(1)[S,A,B,G,F](2)[G,F](3)[A,B,C,G,F](2)[G,F](2)[G,F](4)[A,B,G,F](3)[A,B,C,G,F](5)[D,F,G,E,Z](3)[A,B,C,G,F](4)[A,B,G,F](2)[G,F](3)[A,B,C,G,F](5)[D,F,G,E,Z](6)[G,F,E,Z](7)[A,B,E,Z,G,F](6)[G,F,E,Z](6)[G,F,E,Z](7)[A,B,E,Z,G,F](7)[A,B,E,Z,G,F](6)[G,F,E,Z](8)[A,B,C,E,Z,G,F](8)[A,B,C,E,Z,G,F](5)[D,F,G,E,Z](8)[A,B,C,E,Z,G,F]

DFA這狀態(tài)圖如下：第三章詞法分析

確定有限自動機圖如下：第四章語法分析--自上而下分析根源程式編譯前端中間代碼代碼優(yōu)化中間代碼代碼生成器目標程式符號表代碼生成器的位置第四章語法分析--自上而下分析

按照語法分析樹的建立方法，我們可以粗略地把語法分析方法分為兩類：一類是自上而下分析法，另一類為自下而上分析法。4.2自上而下分析面臨的問題本節(jié)主要是通過例子使我們認識到，作自上而下分析所遇到的主要困難是語法的左遞歸性使分析陷入無限迴圈；回溯的不確定性，要求我們將已經完成工作推倒從來，為解決這些問題我們要消除左遞歸和消除回溯。4.3LL(1)分析法

4.3.1左遞歸的消除一般而言，假定P關於的全部產生式是

PP1|P2|…|P1m|1|2|…

|n

其中，每個都不等於，而每個都不以P開頭，那末，消除P的直接左遞歸性就是把這些規(guī)則改寫成：

P|1P’|2P’|…|nP’P’1P’|2P’|…|mP’|第四章語法分析--自上而下分析

直接左遞歸，和非直接左遞歸的消除方法均在必須掌握之列。這裏我們切不可被形式描述消除左遞歸的演算法嚇倒，多做幾個例題後再來理解是很有好處的：

[例4。3]：考慮文法：SQc|cQRb|bRSa|a

消除左遞歸。解：將終結符排序為R、Q、S。對於R不存在直接左遞歸。把R帶入到Q中有關的候選式：QSab|ab|b

現(xiàn)在Q同樣不含直接左遞歸，把它帶入S的有關候選式：

SSabc|abc|bc|c

經消除S的直接左遞歸後我們們得到整個文法

SabcS’|bcS’|cS’S’abcS’|Q

Sab|ab|bRSa|a

由於關於Q,R的規(guī)則式多餘的則可化簡第四章語法分析--自上而下分析

得到：SabcS’|bcS’|cS’S’abcS’|4.3.2消除回溯、提左因數(shù)我們首先來看一下在不得回溯的情況下對於文法有什麼要求。前面已經說過，欲實行自上而下的分析，文法不得含左遞歸。令G是一個不含左遞歸的文法，對G的所有的非終結符號的每個候選定義它的終結首符集FIRST()為：

FIRST()={a|*a…,aVT}

特別是，若*，則規(guī)定FIRST()。換句話說FIRST(）是的所有可能推導的開頭終結符或可能的。如果非終結符A的所有候選首符集兩兩不相交，即A的任何兩個不同的候選

i和

j

FIRST(i)

FIRST(j)=

那麼，當要求A匹配輸入串時，A就能根據它所面臨的第一個輸入符號a，準確地指派某個候選前去執(zhí)行任務。這個候選就是那個終結首符集含a的。

如何把一個文法改造成任何終結首符集的所有候選首符集兩兩不相交呢？其辦法是提取公共左因數(shù)。例如，假定關於A的規(guī)則是

A

1|2|。。。|n|

1|2|…|m（其中每個不以開頭）

那末，可以把這些規(guī)則改寫成：AA’|

1|2|…|mA’|1|

2|…|

n

第四章語法分析--自上而下分析

[例]有產生式

BbBcA|b

由於FIRST(bBcA)FIRST(b)=

則需要提取公共左因數(shù)將產生式改寫成：B

bCC

BcA|

4.3.3LL（1）分析條件假定S是文法G的開始符號，對於任何非終結符A我們定義：

FOLLOW(A)={a|S*…Aa…,aVT}

特別是，若S*…A，則規(guī)定#FOLLOW(A).也就是說，F(xiàn)OLLOW(A)是所有舉行中出現(xiàn)在緊接A之後的終結符活‘#’。判斷某給定文法是否為LL(1)文法其條件為：（1）文法不含左遞歸。（2）對於文法中每個非終結符A的各個產生式的候選首符集兩兩不相交。即，若

A

1|

2|。。。|

n

則：FIRST(i)

FIRST(j