編譯技術(shù)與理論課件

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

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

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

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

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

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

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

2.1.2語義：

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

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

程式副程式或分程式語句運(yùn)算式數(shù)據(jù)引用算符函數(shù)調(diào)用

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

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

2.2.1高級(jí)語言的分類；a.強(qiáng)制式語言b.應(yīng)用式語言c.基於規(guī)則的語言d.面向?qū)ο笳Z言

2.2.2幾種程式的典型結(jié)構(gòu)；

FORTRANMAIN

…

ENDSUBROUTINESUB1

…END

…SUBROUTINESUBn

…END一.FORTRAN

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

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

…procedureP1;

…procedureP11;

…begin

…end;begin

…end;procedureP2;

…begin

…end;begin

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

這說明定義了一個(gè)記錄CARD.它是一個(gè)含有三個(gè)分量的記錄結(jié)構(gòu)：NAME,字元數(shù)組；AGE,整型量；MARRIED,布爾量。記錄結(jié)構(gòu)的每個(gè)分量（域）所需佔(zhàn)用的存儲(chǔ)單元（位元組）數(shù)，成為該域的長度。當(dāng)知道一個(gè)記錄的地址後，通過每個(gè)域的長度就可算出個(gè)域的地址，因?yàn)槲覀內(nèi)菀淄瞥雒總€(gè)域相對(duì)於記錄結(jié)構(gòu)起點(diǎn)的相對(duì)數(shù)OFFSET：此域之前各域長度的總和。如：就CARD而言，NAME,AGE,MARRIED的相對(duì)數(shù)OFFSET分別為0、20、24。於是，假定CARD的首地址為a，那麼，

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

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

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

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

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

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

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

是一個(gè)有窮字母表，它的每個(gè)元素稱為一個(gè)符號(hào)。

上的一個(gè)符號(hào)串是指由

中的符號(hào)所構(gòu)成的又窮序列。不包含符號(hào)的序列稱為空字，記為

。用

*表示

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

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

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

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

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

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

令：V*=V0V1V2

…

稱V*是V的閉包。記V+=VV*,稱V+是V的正則包。閉包V*中的每個(gè)符號(hào)都是由V中的符號(hào)串經(jīng)有限次連接而成的。

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

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

；Ｓ是一個(gè)非終結(jié)符號(hào)，稱為開始符號(hào)；￡是一個(gè)產(chǎn)生式（有限）集合，每個(gè)產(chǎn)生式形式是Ｐ→

，其中，Ｐ∈ＶＮ，

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

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

），則稱

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

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

的一個(gè)句子。是因?yàn)橛?/p>

E(E)(E+E)(E*E+E)(i*E+E)(i*i+E)(i*i+i)從開始符號(hào)E至（i*i+i)的一個(gè)推導(dǎo)。而E,(E),(E*E+E)等是文法的句型。

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

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

求語言L(G).

解：

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

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

解;S→aSb|ab

為了對(duì)句子結(jié)構(gòu)進(jìn)行確定性分析，我們往往只考慮最左推導(dǎo)或最右推導(dǎo)。所謂最左推導(dǎo)是指：任何一步

都是對(duì)

中的最左非終結(jié)符進(jìn)行替換的。同樣，可定義最右推導(dǎo)。2.3.2語法分析樹與二義性

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

例如對(duì)於文法（2.1)關(guān)於（i*i+i)的推導(dǎo)形成語法樹如圖2。2

圖2。2語法樹

一個(gè)句型是否只對(duì)應(yīng)唯一的一棵語法樹呢？也就是說它是否只有唯一的一個(gè)最左（最右)推導(dǎo)呢？不盡然。如文法2.1,關(guān)於（i*i+i)就存在一個(gè)與2。2非常不同的推導(dǎo)：

E(E)(E*E)(i*E)(i*E+E)(i*i+E)(i*i+i)其對(duì)應(yīng)語法樹：

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

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

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

*P.

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

VT*,使得P

+

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

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

)是一個(gè)0型文法，如果它的每個(gè)產(chǎn)生式

是這樣的結(jié)構(gòu)

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

均滿足

|

|≤|

|（其中|

|和|

|分別為

和

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

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

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

其中1型文法也稱上下文有關(guān)文法。這種文法意味著，對(duì)非終結(jié)符進(jìn)行替換式務(wù)必考慮上下文並且一般不允許替換成空串

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

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

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

A→B

或A→

，其中

∈VT*,A、B∈VN

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

[例2.1]：試構(gòu)造生成語言L={anbnci|n

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

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

AabcAaBbcBbbBBcCbccbCCbaCaaBaCaa

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

aabbcc

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

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

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

如果一個(gè)種別只含有一個(gè)單詞符號(hào)，那麼對(duì)於這個(gè)單詞符號(hào)，種別編碼就完全代表它自身了。若一個(gè)種別含有多個(gè)單詞符號(hào)，那麼，對(duì)於它的每個(gè)單詞符號(hào)，除了給出種別編碼之外，還應(yīng)給出有關(guān)單詞符號(hào)的屬性資訊。

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

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

while(i>=j)i--;

經(jīng)詞法分析器處理後，它將轉(zhuǎn)換為如下的單詞符號(hào)序列：

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

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

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

第三章詞法分析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Σ,a是Σ上的一個(gè)正規(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))*（閉包）僅由有限次使用上述三步驟而得到的運(yùn)算式才是Σ上的正規(guī)式。僅由這些正規(guī)式所表示的字集才是Σ上的正規(guī)集。第三章詞法分析

通過這一節(jié)的學(xué)習(xí)，根據(jù)給出的簡單正規(guī)式，應(yīng)會(huì)寫出其正規(guī)集。

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

ba*Σ上所有以b為首後跟著任意多個(gè)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)*Σ上的“識(shí)別字”的全體（0|1）（0|1）*Σ上“數(shù)”的全體若兩個(gè)正規(guī)式所表示的正規(guī)集相同，則認(rèn)為二者等價(jià)。兩個(gè)等價(jià)的正規(guī)式U和V記為U=V。例如：b(ab)*=(ba)*b等第三章詞法分析3.3.2確定有限自動(dòng)機(jī)（DFA)

確定有限自動(dòng)機(jī)(DFA)是一個(gè)五元式

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

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

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

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

第三章詞法分析

對(duì)於*中的任何一個(gè)字元，若存在一條從初態(tài)結(jié)點(diǎn)到某一終態(tài)結(jié)點(diǎn)的通路，且這條通路上所有箭弧的標(biāo)記符連接成的字等於，則稱為DFAM所識(shí)別（讀出或接受）。若M的初態(tài)結(jié)點(diǎn)同時(shí)又是終態(tài)結(jié)點(diǎn)，則為空字可以為M所識(shí)別。DFAM所能識(shí)別的字的全體記為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問：有幾個(gè)狀態(tài)？幾個(gè)輸入字元？並畫出其轉(zhuǎn)換圖。L(M)=?解：有0，1，2，3共四個(gè)狀態(tài)。輸入字元為a,b兩個(gè)。其狀態(tài)轉(zhuǎn)換圖如右L(M)為在上所有含相繼兩個(gè)a或相繼兩個(gè)b的字。第三章詞法分析3。3。3非確定有限自動(dòng)機(jī)(NFA)

一個(gè)非確定有限自動(dòng)機(jī)（NFA)是一個(gè)五元式

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

(4)S0

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

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

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

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

可以畫為：

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

[例]：畫出正規(guī)式：（a|b)*(aa|bb)(a|b)*對(duì)應(yīng)的NFA第三章詞法分析[例]：用狀態(tài)子集法構(gòu)造圖3。6的狀態(tài)轉(zhuǎn)換矩陣：表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對(duì)表3。3中狀態(tài)子集從新命名後狀態(tài)轉(zhuǎn)換矩陣

Sab012132215334465

565

634第三章詞法分析

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

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

3.3.6確定有限自動(dòng)機(jī)的化簡

是本節(jié)應(yīng)掌握的內(nèi)容。(參看P56)

我們這裏舉個(gè)例子幫助理解這個(gè)過程：

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

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

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

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

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

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

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

G[Z]:Z→(+|-

)A(0|5)

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

G[Z]:Z→(+|-)A(0|5)A→AB|CB→0|C|BBC→0|1|2|3|4|5|6|7|8|9正則運(yùn)算式：G[Z]:Z=(+|-)A*(0|5)A∈(0,1,2,3,4,5,6,7,8,9)第三章詞法分析[例3。2]寫一個(gè)文法，使其語言是奇數(shù)集，且每個(gè)奇數(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整除十進(jìn)位整數(shù)的文法和正則運(yùn)算式：解：能被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整則運(yùn)算式：

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

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

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

正則文法G(Z)為：

Z0Z|1Z|1AA1B|1B0B|1B|0|1（3）將圖中有限自動(dòng)機(jī)確定化：首先從處態(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}其相應(yīng)的DFA如下圖：第三章詞法分析

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

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

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

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

所以將DFA最小化的狀態(tài)圖如下：第三章詞法分析[例3.5]請構(gòu)造與正則式R=(a*b)*ba(a|b)*等價(jià)的狀態(tài)最少的DFA（確定有限自動(dòng)機(jī)）解：（1）首先構(gòu)造轉(zhuǎn)換系統(tǒng)圖：（2）由系統(tǒng)轉(zhuǎn)換圖構(gòu)造DFA（NFA確定化）設(shè)初態(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)圖如下：第三章詞法分析

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

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

4.3.1左遞歸的消除一般而言，假定P關(guān)於的全部產(chǎn)生式是

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

|n

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

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

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

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

消除左遞歸。解：將終結(jié)符排序?yàn)镽、Q、S。對(duì)於R不存在直接左遞歸。把R帶入到Q中有關(guān)的候選式：QSab|ab|b

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

SSabc|abc|bc|c

經(jīng)消除S的直接左遞歸後我們們得到整個(gè)文法

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

Sab|ab|bRSa|a

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

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

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

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

i和

j

FIRST(i)

FIRST(j)=

那麼，當(dāng)要求A匹配輸入串時(shí)，A就能根據(jù)它所面臨的第一個(gè)輸入符號(hào)a，準(zhǔn)確地指派某個(gè)候選前去執(zhí)行任務(wù)。這個(gè)候選就是那個(gè)終結(jié)首符集含a的。

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

A

1|2|。。。|n|

1|2|…|m（其中每個(gè)不以開頭）

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

1|2|…|mA’|1|

2|…|

n

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

[例]有產(chǎn)生式

BbBcA|b

由於FIRST(bBcA)FIRST(b)=

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

bCC

BcA|

4.3.3LL（1）分析條件假定S是文法G的開始符號(hào)，對(duì)於任何非終結(jié)符A我們定義：

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

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

A

1|

2|。。。|

n

則：FIRST(i)

FIRST(j