編譯原理實(shí)用教程ppt課件(完整版)

1、21世紀(jì)高等院校規(guī)劃教材編譯原理實(shí)用教程 第一章 編譯程序概論本章學(xué)習(xí)目標(biāo)編譯程序是高級(jí)語(yǔ)言的支撐基礎(chǔ)，是計(jì)算機(jī)系統(tǒng)中重要的系統(tǒng)軟件之一，本章主要內(nèi)容：編譯程序的功能編譯程序的體系結(jié)構(gòu)編譯程序的工作過(guò)程編譯程序的設(shè)計(jì)1.1 程序設(shè)計(jì)語(yǔ)言程序設(shè)計(jì)語(yǔ)言分成兩大類(lèi)，一類(lèi)是高級(jí)語(yǔ)言，一類(lèi)是低級(jí)語(yǔ)言。低級(jí)語(yǔ)言又包括機(jī)器語(yǔ)言和匯編語(yǔ)言，主要是面向機(jī)器的。高級(jí)語(yǔ)言則是面向應(yīng)用的，分成很多種，如FORTRAN、Pascal、C、Ada、Java等。 機(jī)器語(yǔ)言本身是有由0和1組成的，符合計(jì)算機(jī)的硬件特性，因此能夠直接執(zhí)行。但用機(jī)器語(yǔ)言編寫(xiě)程序很不方便且容易出錯(cuò)，因此就用助記符代替機(jī)器語(yǔ)言，產(chǎn)生了匯編語(yǔ)言。匯編語(yǔ)

2、言比機(jī)器語(yǔ)言在可讀性方面有了進(jìn)步，但是其依賴具體機(jī)器的特性無(wú)法改變，給程序設(shè)計(jì)語(yǔ)言增添了難度。高級(jí)語(yǔ)言不能直接在機(jī)器上運(yùn)行，它不是面向機(jī)器，而是面向應(yīng)用的，因此，要想讓高級(jí)語(yǔ)言運(yùn)行必須有編譯程序。編譯程序就是這樣的一種程序，它能將高級(jí)語(yǔ)言編寫(xiě)的源程序轉(zhuǎn)換成與之在邏輯上等價(jià)的低級(jí)語(yǔ)言形式的目標(biāo)程序。高級(jí)語(yǔ)言程序的執(zhí)行通常分為兩個(gè)階段，即編譯階段和運(yùn)行階段，源程序的運(yùn)行過(guò)程如圖1-1所示。編譯階段將源程序變換成目標(biāo)程序；運(yùn)行階段則由所生成的目標(biāo)程序連同運(yùn)行系統(tǒng)（數(shù)據(jù)空間分配子程序、標(biāo)準(zhǔn)函數(shù)程序等）接受程序的初始數(shù)據(jù)作為輸入，運(yùn)行后輸出計(jì)算結(jié)果。如果目標(biāo)程序是匯編語(yǔ)言的形式，則需要在編譯階段和運(yùn)行階

3、段之間加一個(gè)匯編階段。源程序目標(biāo)程序機(jī)器語(yǔ)言計(jì)算結(jié)果編譯程序匯編程序圖1-1源程序的編譯、匯編和運(yùn)行階段高級(jí)語(yǔ)言編寫(xiě)的程序除了可以通過(guò)編譯方式外，還可以通過(guò)解釋程序執(zhí)行。所謂解釋程序是一種語(yǔ)言翻譯程序，讀入一條語(yǔ)句，解釋一條語(yǔ)句，執(zhí)行一條語(yǔ)句，邊讀入邊執(zhí)行。解釋程序與編譯程序的主要區(qū)別是：編譯程序?qū)⒃闯绦蚍g成目標(biāo)程序后再執(zhí)行目標(biāo)程序，而解釋程序是逐條讀出源程序中的語(yǔ)句并執(zhí)行，即在解釋程序的執(zhí)行過(guò)程中并不產(chǎn)生目標(biāo)程序。1.2編譯程序的編譯過(guò)程和結(jié)構(gòu)編譯程序的功能是把高級(jí)語(yǔ)言源程序翻譯成等價(jià)的低級(jí)語(yǔ)言目標(biāo)程序。源程序是由一些基本符號(hào)構(gòu)成的，我們?cè)谶\(yùn)行這個(gè)程序時(shí)，先編譯，若某處有錯(cuò)誤，就報(bào)錯(cuò)，無(wú)錯(cuò)

4、誤就運(yùn)行。編譯程序在編譯時(shí)，先將程序中的單詞一個(gè)個(gè)分離出來(lái)，登記在一個(gè)表中，這叫詞法分析，然后檢查語(yǔ)句格式，叫做語(yǔ)法分析。然后檢查類(lèi)型是否一致，計(jì)算表達(dá)式的值叫語(yǔ)義分析。這些功能都是由編譯程序相應(yīng)的程序完成的。一般來(lái)說(shuō)，整個(gè)編譯過(guò)程可以劃分成五個(gè)階段：詞法分析階段、語(yǔ)法分析階段、語(yǔ)義分析和中間代碼生成階段、中間代碼的優(yōu)化和目標(biāo)代碼的生成。1.詞法分析階段詞法分析是編譯過(guò)程的基礎(chǔ)，其任務(wù)是掃描源程序，根據(jù)語(yǔ)言的詞法規(guī)則，分解和識(shí)別出每個(gè)單詞，并把單詞翻譯成相應(yīng)的機(jī)內(nèi)表示。當(dāng)然，詞法分析在識(shí)別單詞的過(guò)程中，同時(shí)也做了詞法檢查。在高級(jí)語(yǔ)言中，所謂單詞，就是指邏輯上緊密相連的一組字符，這些字符具有集體

5、含義。單詞是語(yǔ)言中最小的語(yǔ)義單位，如語(yǔ)言中的關(guān)鍵字、標(biāo)識(shí)符、運(yùn)算符和界限符。詞法分析的依據(jù)是詞的構(gòu)造。單詞的構(gòu)造規(guī)則在高級(jí)語(yǔ)言中有明確的規(guī)定，比如哪些為保留字、變量如何定義、常量如何構(gòu)造、分界符有哪些等。 例如，用C 語(yǔ)言編寫(xiě)的程序段如下：main( )float x=2,y=3,s;s=x+y*5;識(shí)別出的單詞序列為表1-1所示表1-1詞法分析程序類(lèi)型名單詞類(lèi)型名單詞保留字main左括號(hào)(右括號(hào))花括號(hào)保留字float標(biāo)識(shí)符x等號(hào)=常量2逗號(hào),標(biāo)識(shí)符y等號(hào)=常量3逗號(hào),標(biāo)識(shí)符s分號(hào);標(biāo)識(shí)符s等號(hào)=標(biāo)識(shí)符x運(yùn)算符+標(biāo)識(shí)符y運(yùn)算符*常量5分號(hào);花括號(hào)2.詞法分析語(yǔ)法分析是在詞法分析的 基礎(chǔ)上進(jìn)行

6、的，是編譯過(guò)程的第二個(gè)階段。語(yǔ)法分析的任務(wù)是根據(jù)語(yǔ)言的語(yǔ)法規(guī)則，把單詞符號(hào)串分解成各類(lèi)語(yǔ)法單位，如表達(dá)式、語(yǔ)句等。通過(guò)語(yǔ)法分析，可以確定整個(gè)輸入符號(hào)串是否構(gòu)成一個(gè)正確的程序。3語(yǔ)義分析和中間代碼的生成語(yǔ)義分析的任務(wù)是對(duì)各種不同語(yǔ)句進(jìn)行翻譯，包括兩方面的工作：一是對(duì)每種語(yǔ)法范疇進(jìn)行語(yǔ)義檢查，如變量是否定義、類(lèi)型是否正確等；二是在語(yǔ)義檢查正確的情況下，進(jìn)行中間代碼的翻譯。中間代碼是介于高級(jí)語(yǔ)言語(yǔ)句和低級(jí)語(yǔ)言語(yǔ)句之間的一種獨(dú)立于具體硬件的記號(hào)系統(tǒng)，它即有一定程度的抽象，又和低級(jí)語(yǔ)言十分接近，因此，轉(zhuǎn)換成目標(biāo)代碼很容易。中間代碼的表示形式有很多種，常見(jiàn)的有四元式、三元式、間接三元式和逆波蘭式。其中四元

7、式的形式為（運(yùn)算符，運(yùn)算對(duì)象1，運(yùn)算對(duì)象2，結(jié)果） 4.中間代碼優(yōu)化中間代碼優(yōu)化通過(guò)調(diào)整和改變中間代碼中某些操作次序，以最終產(chǎn)生更加高效的目標(biāo)代碼。優(yōu)化的主要手段有刪除冗余運(yùn)算、刪除無(wú)用賦值、合并已知量、循環(huán)優(yōu)化等。 5目標(biāo)代碼的生成這一階段的任務(wù)是對(duì)前一階段的中間代碼變換成特定機(jī)器上的機(jī)器語(yǔ)言或匯編語(yǔ)言程序，實(shí)現(xiàn)機(jī)器的最終翻譯。最后階段的工作因?yàn)槟繕?biāo)語(yǔ)言的關(guān)系而十分依賴機(jī)器的硬件系統(tǒng)，即如何充分利用機(jī)器現(xiàn)存的寄存器，合理的選擇指令，生成盡可能短的目標(biāo)代碼，這與機(jī)器的硬件有關(guān)。 編譯過(guò)程可以劃分成五個(gè)階段，這種劃分是編譯程序的邏輯組織形式。實(shí)際上，編譯過(guò)程往往分成前端和后端。前端包括詞法分析、

8、語(yǔ)法分析、語(yǔ)義分析、中間代碼生成和中間代碼優(yōu)化，主要依賴于源程序；后端包括目標(biāo)代碼生成，依賴于計(jì)算機(jī)硬件系統(tǒng)和機(jī)器指令系統(tǒng)。這種組織方式，便于編譯程序的移植，若要將編譯程序移植到不同類(lèi)型的機(jī)器，只需要修改編譯程序的后端即可。編譯程序還采用“分遍”的形式，即編譯過(guò)程可以由一遍或多遍編譯程序來(lái)完成。對(duì)于源程序或中間代碼，從頭到尾掃描一次并完成所規(guī)定的工作稱為一遍。在一遍中，可以完成一個(gè)或相連幾個(gè)邏輯步驟的工作。例如可以把詞法分析作為第一遍；語(yǔ)法分析和語(yǔ)義分析作為第二遍；代碼優(yōu)化和存儲(chǔ)分配作為第三遍；代碼生成作為第四遍；從而構(gòu)成一個(gè)四遍掃描的編譯程序。詞法分析器語(yǔ)法分析器語(yǔ)義分析器中間代碼生成器中間

9、代碼的優(yōu)化目標(biāo)代碼生成器源程序表格管理出錯(cuò)處理目標(biāo)程序圖1-3編譯程序結(jié)構(gòu)示意圖1.3編譯程序的設(shè)計(jì)技術(shù)編譯程序的任務(wù)是把源程序翻譯成某臺(tái)計(jì)算機(jī)上的目標(biāo)程序。因此編程人員首先要熟悉源程序語(yǔ)言，對(duì)源程序語(yǔ)言的語(yǔ)法和語(yǔ)義要準(zhǔn)確無(wú)誤的理解，同時(shí)要確定開(kāi)發(fā)方案。同時(shí)還要選擇合適的語(yǔ)言編寫(xiě)編譯程序，目前一般采用PASCAL、C、ADA等高級(jí)語(yǔ)言編寫(xiě)，不僅減少了開(kāi)發(fā)的工作量，縮短了開(kāi)發(fā)周期。最后，開(kāi)發(fā)人員還要熟悉目標(biāo)機(jī)的特點(diǎn)，產(chǎn)生質(zhì)量較高的目標(biāo)代碼。1高級(jí)語(yǔ)言的自編譯技術(shù)用某種該高級(jí)語(yǔ)言書(shū)寫(xiě)自己的編譯程序稱為自編譯。2.交叉編譯交叉編譯是指用A機(jī)器上的編譯程序來(lái)產(chǎn)生可在B機(jī)器上運(yùn)行的目標(biāo)代碼。例如，若A機(jī)

10、器上已有C程序可以運(yùn)行，則可以在A機(jī)器上的C程序書(shū)寫(xiě)一個(gè)編譯程序，它的源程序是C語(yǔ)言程序，而產(chǎn)生的目標(biāo)程序則是基于B機(jī)器上的，即能夠在B機(jī)器上執(zhí)行的低級(jí)語(yǔ)言程序。3編譯程序的自展技術(shù)Ln=LL1L0圖1-4編譯系統(tǒng)的自展過(guò)程自展的方法是：首先確定一個(gè)非常簡(jiǎn)單的核心語(yǔ)言L0，然后用機(jī)器語(yǔ)言或匯編語(yǔ)言書(shū)寫(xiě)它的編譯程序T0；再把語(yǔ)言L0擴(kuò)充到L1,此時(shí)有L0屬于L1，并用L0編寫(xiě)出L1的編譯程序T1，然后再把語(yǔ)言L1擴(kuò)充為L(zhǎng)2，此時(shí)，L1屬于L2，并用L1編寫(xiě)L2的編譯程序T2,這樣不斷的擴(kuò)展下去，直到完成所要求的編譯程序?yàn)橹?。自展技術(shù)的使用如圖1-4所示。4編譯程序的移植技術(shù)編譯程序可以通過(guò)移植得

11、到，即可以將一個(gè)機(jī)器（宿主機(jī)）上的一個(gè)具有自編譯性的高級(jí)語(yǔ)言編譯程序移植到另一個(gè)機(jī)器（目標(biāo)機(jī)）上。5編譯程序的自動(dòng)化在編譯程序的自動(dòng)化開(kāi)發(fā)過(guò)程中，開(kāi)發(fā)較早的是詞法分析程序生成器和語(yǔ)法分析程序生成器 。使用的工具是在UNIX 操作系統(tǒng)下的軟件工具LEX和YACC。1.4形式語(yǔ)言和編譯實(shí)現(xiàn)技術(shù)形式語(yǔ)言是一種不考慮含義的符號(hào)語(yǔ)言，形式語(yǔ)言的理論研究的是組成這種符號(hào)語(yǔ)言的符號(hào)串集合、它們的表示法、結(jié)構(gòu)和特性。按Chomsky文法分類(lèi)法，文法可以分成四大類(lèi)，即短語(yǔ)結(jié)構(gòu)文法、上下文有關(guān)文法、上下文無(wú)關(guān)文法和正則文法。通常的程序設(shè)計(jì)語(yǔ)言，其符號(hào)的定義和正則文法相關(guān)聯(lián)，語(yǔ)法定義和上下文無(wú)關(guān)文法相關(guān)聯(lián)，而語(yǔ)義一

12、般需要上下文有關(guān)文法來(lái)定義。形式語(yǔ)言理論采用數(shù)學(xué)那樣的符號(hào)形式表示，數(shù)學(xué)那樣的嚴(yán)格推理。采用形式語(yǔ)言方式討論程序設(shè)計(jì)語(yǔ)言及其編譯程序的構(gòu)造，可以使我們不僅了解一些編譯實(shí)現(xiàn)技術(shù)如何應(yīng)用，而且還可以理解如此做的原因。對(duì)編譯程序的設(shè)計(jì)中所采用的技術(shù)，不但要知其然，而且還要知道所以然。從理論高度上去掌握編譯技術(shù)?？梢杂孟铝泄絹?lái)表示一種關(guān)系，即：編譯原理=形式語(yǔ)言理論+編譯技術(shù)小結(jié)自FORTRAN語(yǔ)言產(chǎn)生后，計(jì)算機(jī)高級(jí)語(yǔ)言得到了迅速發(fā)展。高級(jí)語(yǔ)言的種類(lèi)越來(lái)越多。但計(jì)算機(jī)只能執(zhí)行機(jī)器語(yǔ)言，不能直接執(zhí)行高級(jí)語(yǔ)言編寫(xiě)的程序。要執(zhí)行高級(jí)語(yǔ)言程序，必須提供該高級(jí)語(yǔ)言的翻譯程序。翻譯有編譯和解釋兩種方式。編譯程序

13、將源程序翻譯成目標(biāo)程序，然后再執(zhí)行目標(biāo)程序。解釋方式則是邊翻譯邊執(zhí)行。編譯程序一般包括詞法分析程序、語(yǔ)法分析程序、語(yǔ)義分析程序、中間代碼生成程序、代碼優(yōu)化程序、目標(biāo)代碼生成程序和出錯(cuò)處理程序等。編譯過(guò)程可以分遍編譯。編譯程序的構(gòu)造有多種技術(shù)。主要有自編譯、移植、交叉編譯、自展和自動(dòng)化技術(shù)。 LEX是一個(gè)具有代表性的詞法分析程序生成器。YACC是一個(gè)基于LALR（1）分析法的語(yǔ)法分析程序生成器。習(xí)題 1.1完成下列選擇題(1) 構(gòu)造編譯程序應(yīng)掌握 。 a.源程序 b.目標(biāo)語(yǔ)言 c.編譯方法 d .以上三項(xiàng)都是 (2)編譯程序絕大多數(shù)時(shí)間花在 。 a.出錯(cuò)處理 b.詞法分析 c.目標(biāo)代碼生成 d

14、.表格管理(3)編譯程序是對(duì) 。 a.匯編語(yǔ)言的翻譯 b.高級(jí)語(yǔ)言程序的解釋執(zhí)行 c.機(jī)器語(yǔ)言的執(zhí)行 d .高級(jí)語(yǔ)言的翻譯 （4）高級(jí)語(yǔ)言程序設(shè)計(jì)是根據(jù) 定義的。a.詞法規(guī)則 b.語(yǔ)法規(guī)則 c.語(yǔ)義規(guī)則 d .以上三項(xiàng)都不是。 （5）編譯程序的各階段都設(shè)及到 。a.詞法分析 b.表格管理 c.語(yǔ)法分析 d .語(yǔ)義分析（6）編譯程序?qū)⒃闯绦蚣庸こ赡繕?biāo)程序是 之間的轉(zhuǎn)換。 a.詞法 b.語(yǔ)義 c.語(yǔ)法 d .規(guī)則（7）解釋程序和編譯程序的區(qū)別是 之間的轉(zhuǎn)換。 a.是否生成中間代碼 b.加工的對(duì)象不同 c.使用的實(shí)現(xiàn)技術(shù)不同 d .是否生成目標(biāo)代碼（）編譯程序不能夠檢查、處理的錯(cuò)誤是程序中的 。 a

15、.靜態(tài)語(yǔ)義錯(cuò)誤 b.動(dòng)態(tài)語(yǔ)義錯(cuò)誤 c.語(yǔ)法錯(cuò)誤 d .詞法錯(cuò)誤（9）中間代碼生成所依據(jù)的是語(yǔ)言的 。 a.詞法規(guī)則 b.語(yǔ)法規(guī)則 c.語(yǔ)義規(guī)則 d .產(chǎn)生規(guī)則（10）開(kāi)發(fā)一個(gè)編譯程序應(yīng)掌握 。 a.源語(yǔ)言 b.目標(biāo)語(yǔ)言 c.編譯技術(shù) d .以上三項(xiàng)都不是1.2判斷題（）用高級(jí)語(yǔ)言編寫(xiě)的源程序都必須通過(guò)編譯，產(chǎn)生目標(biāo)程序后才能運(yùn)行。（2）源程序和目標(biāo)程序在功能上具有等價(jià)關(guān)系。（3）高級(jí)語(yǔ)言程序到低級(jí)語(yǔ)言程序的轉(zhuǎn)換是結(jié)構(gòu)上的變換。（4）解釋程序雖然不產(chǎn)生目標(biāo)代碼，但是它可能產(chǎn)生中間代碼。（5）目標(biāo)程序一定是機(jī)器語(yǔ)言程序。1.3問(wèn)答題（1）.計(jì)算機(jī)執(zhí)行用高級(jí)語(yǔ)言編寫(xiě)的程序有那些途徑?它們之間的區(qū)別是

16、什么?（2）.畫(huà)出編譯程序的構(gòu)造圖.（3）.什么是編譯程序的前端？什么是編譯程序的后端？第二章形式語(yǔ)言概述本章學(xué)習(xí)目標(biāo)形式語(yǔ)言由Chomsky于1956年提出，主要討論語(yǔ)言和文法的數(shù)學(xué)機(jī)制以及語(yǔ)言和文法的分類(lèi)。形式語(yǔ)言 的形成和發(fā)展，對(duì)編譯原理和技術(shù)產(chǎn)生了重要的影響。本章主要內(nèi)容是:文法和語(yǔ)言的形式定義文法的分類(lèi)句型的分析和語(yǔ)法樹(shù)2.1字母表和符號(hào)串任何一種語(yǔ)言都是由基本符號(hào)構(gòu)成的。計(jì)算機(jī)高級(jí)語(yǔ)言作為計(jì)算機(jī)的語(yǔ)言，程序有語(yǔ)句構(gòu)成，語(yǔ)句有一些基本符號(hào)構(gòu)成，這些基本符號(hào)是保留字如main，if，then等、字母、數(shù)字和專用符號(hào)等。每個(gè)程序可以看成基本符號(hào)串。將所有的基本符號(hào)定義成一個(gè)基本符號(hào)集合，

17、則語(yǔ)言可以看成是在這個(gè)基本符號(hào)集合上定義的，按一定的規(guī)則構(gòu)成的一切基本符號(hào)串組成的集合，給出如下的一些基本概念。 2.1.1字母表定義2.1 字母表是元素的非空有窮集合，字母表中的元素稱為符號(hào)，因此字母表也稱為符號(hào)表。高級(jí)語(yǔ)言如C語(yǔ)言的字母表是由字母、數(shù)字、特殊符號(hào)和一些專用符號(hào)構(gòu)成。例=a,b， =0,1，=0,1，2，3，4，5，6，7，8，9，=a,b,c,z,if,then,else,main,1,2,3,4,9,0,=,=,0)3字母表的閉包與正閉包的運(yùn)算設(shè)有字母表A，由它做方冪A0，A1，A2， An, 。A的閉包定義如下：定義 2.8 A的閉包A*=A0A1 A2 An,其中，A

18、n （n=0，1，2，3，）中所有的符號(hào)串的長(zhǎng)度為n，因此字母表A的閉包 A*為字母表上一切長(zhǎng)度為n的符號(hào)串所組成的集合。如果不允許包含空串，則得到字母表A的正閉包。定義2.9 A的正閉包 A+=A1 A2 An顯然，A*= A0 A+ ，且A+=AA*=A*A。 例題2.7 設(shè)字母表=a,b,c,依次寫(xiě)出長(zhǎng)度為1、2的符號(hào)串，可得到 的正閉包+ ：+=a,b,c,aa,ab,ac,bb,bc,在+上添入空串即得*。說(shuō)明：根據(jù)閉包和正閉包的定義，則有+=*=* 由于一個(gè)字母表的正閉包包含了該字母表中的符號(hào)所能組成的一切符號(hào)串，而語(yǔ)言是該字母表上某個(gè)符號(hào)串的集合，因此，在某個(gè)字母表上的語(yǔ)言是該字

19、母表上正閉包的子集，且是真子集。對(duì)于C語(yǔ)言，可以說(shuō)，C語(yǔ)言是基本符號(hào)集合的正閉包的真子集。 2.2 文法的定義及其分類(lèi)什么是文法，文法的直觀概念是，文法作為一種工具，不僅嚴(yán)格地定義句子的結(jié)構(gòu)，也是為了用適當(dāng)條數(shù)的規(guī)則把語(yǔ)言的全部句子描述出來(lái)，是以有窮的集合刻劃無(wú)窮的集合的工具。2.2.2文法的形式定義1重寫(xiě)規(guī)則定義2.10重寫(xiě)規(guī)則，也叫產(chǎn)生式規(guī)則，或稱為生成式，是形如或:的（,）有序?qū)?其中, 是某個(gè)字母表V+中的一個(gè)元素，是V* 中的一個(gè)元素。稱為規(guī)則的左部，稱為規(guī)則的右部。例如 AB讀作“A定義為B”，也就是說(shuō)它是一條關(guān)于A的規(guī)則（產(chǎn)生式）。2文法定義2.11 文法G是一個(gè)四元組，G=（V

20、N，VT，P，S），其中，VN、VT分別是非空有限的非終結(jié)符號(hào)集和終結(jié)符號(hào)集，VNVT=，P是產(chǎn)生式的集合，SVN 稱為文法的識(shí)別符號(hào)或開(kāi)始符號(hào)。例題2.8在程序設(shè)計(jì)語(yǔ)言中，假設(shè)我們定義標(biāo)識(shí)符的命名規(guī)則為字母a、b、c開(kāi)頭的，字母a、b、c和數(shù)字1、2、3的序列。命名規(guī)則為：abc123我們一般用大寫(xiě)字母代表左邊的非終結(jié)符，設(shè)N 代表，D代表，L代表，則定義標(biāo)識(shí)符的文法是：G=(VN，VT，P，N)其中，VN=N，L，DVT=a,b,c,1,2,3P為產(chǎn)生式的規(guī)則：NL， NNL ，NND ，La ，Lb ，Lc ，D1 ，D2，D3S 是開(kāi)始符號(hào),為N.關(guān)于產(chǎn)生式的規(guī)則說(shuō)明一點(diǎn)，即若A，A，

21、A可寫(xiě)成A| ?！皘”讀做“或者”。上面的產(chǎn)生式規(guī)則可以改寫(xiě)為：P為產(chǎn)生式的規(guī)則：NL|NL|NDLa|b| cD1|2|32.2.3文法的分類(lèi)自從喬姆斯基（Chomsky）于1956年建立形式語(yǔ)言的描述以來(lái)，把文法分成四種類(lèi)型，即0型、1型、2型和3型文法。0型文法(短語(yǔ)文法)設(shè)G=（VN，VT，P，S），如果它的每個(gè)產(chǎn)生式是這樣一種結(jié)構(gòu)：（VNVT ）+ ，且至少含有一個(gè)非終結(jié)符，而（VNVT ）*，則稱G是一個(gè)0型文法。0型文法又稱短語(yǔ)文法，它的能力相當(dāng)于一個(gè)圖靈機(jī)。例如，A1型文法（上下文有關(guān)文法）設(shè)G=（VN，VT，P，S）為一文法，若P中的每一個(gè)產(chǎn)生式均滿足，僅僅S除外，則文法G是

22、1型文法或上下文有關(guān)文法。所謂上下文有關(guān)文法即：=1A2，=12，符號(hào)串1 和2可以認(rèn)為是上下文，A只有出現(xiàn)在上下文之間中，才可以被符號(hào)串替代，成為=1A2=12因此，1型文法又稱為上下文有關(guān)文法。 32型文法（上下文無(wú)關(guān)文法）設(shè)G=(VN，VT，P，S)，若P中的每個(gè)產(chǎn)生式滿足: 是一個(gè)非終結(jié)符, (VNVT ) *，則此文法稱為2 型文法或上下文無(wú)關(guān)文法。有時(shí)將2型文法的產(chǎn)生式表示為形如：A，其中AVN 。 也就是當(dāng)用取代非終結(jié)符A時(shí)，與A所在的上下文無(wú)關(guān)。上下文無(wú)關(guān)文法有足夠的能力描述現(xiàn)今的程序設(shè)計(jì)語(yǔ)言。例題2.102 型文法G=（VN，VT，P，N）其中，VN=N，DVT=0，1，2，

23、3，4，5，6，7，8，9P=NNDD，D0123456789該文法描述的符號(hào)串的集合是整數(shù)。3型文法（右線性文法或正規(guī)文法）對(duì)2型文法的產(chǎn)生式做進(jìn)一步的限制，限制產(chǎn)生式右部是單一終結(jié)符或單一終結(jié)符跟著單一非終結(jié)符，即：Aa AaB則稱該文法為3型文法，又稱為右線性文法或正規(guī)文法，其中A、BVN，aVT.例題2.113型文法 G=（VN，VT，P，S）其中，VN=S，A，BVT=0，1P=S011A0B，A1A0B，B010B該文法產(chǎn)生的是二進(jìn)制整數(shù)。2.2.4文法舉例例題2.15正規(guī)文法G=（VN，VT，P，A）其中, VN=A,B,C,DVT=x,y,z P=AxByCBzB yyC Cx

24、DD yDx例題2.162型文法G=（VN，VT，P，E）其中，VN=E，T，F(xiàn)VT=+，*，（，），iP=EE+T|T, TT*F|T, F(E)|i該文法能推出具有乘和加運(yùn)算的算術(shù)表達(dá)式。例題2.17正規(guī)文法G=（VN，VT，P，S）其中VN=S，A，B，G，H，VT=d，+，P=SdB|+A|A|.GAdB|.GBdB|.H|dGdHHdH|d其中，d代表十進(jìn)制數(shù)字。 根據(jù)以上我們對(duì)文法的定義我們不難發(fā)現(xiàn)3型文法類(lèi)是2型文法類(lèi)的特殊情況，2型文法類(lèi)是1型文法類(lèi)的特殊情況。每一類(lèi)文法都是在前一類(lèi)文法的基礎(chǔ)上加上一些限定規(guī)則而產(chǎn)生的。因此，四類(lèi)文法產(chǎn)生的語(yǔ)言就會(huì)有如下關(guān)系：3型語(yǔ)言2型語(yǔ)言1

25、型語(yǔ)言0型語(yǔ)言2.2.5各類(lèi)文法與自動(dòng)機(jī)的關(guān)系語(yǔ)言是句子的集合，而句子又是由字母表上的符號(hào)串組成的。對(duì)于程序設(shè)計(jì)語(yǔ)言來(lái)講，程序由語(yǔ)句構(gòu)成，語(yǔ)句則有數(shù)字、標(biāo)識(shí)符、保留字、數(shù)字等單詞構(gòu)成。因此對(duì)程序的編譯事實(shí)上就是對(duì)句子進(jìn)行檢查。方法就是編寫(xiě)一個(gè)檢查過(guò)程，運(yùn)行該過(guò)程來(lái)判斷編寫(xiě)的程序是否合法。合法就回答“正確”，不合法就回答“不正確”，并且將錯(cuò)誤報(bào)出。編寫(xiě)該過(guò)程的算法，抽象成一個(gè)數(shù)學(xué)模型，該數(shù)學(xué)模型稱為自動(dòng)機(jī)。將算法對(duì)程序的合法與否的檢查轉(zhuǎn)化為數(shù)學(xué)模型對(duì)程序中的句子的識(shí)別過(guò)程。自動(dòng)機(jī)給出了用有窮方式來(lái)描述潛在的無(wú)窮的語(yǔ)言的另一種手段。自動(dòng)機(jī)能夠識(shí)別的句子的集合稱為語(yǔ)言。對(duì)于每一類(lèi)Chomsky語(yǔ)言類(lèi)

26、，正好有一類(lèi)自動(dòng)機(jī)與它相對(duì)應(yīng)。10型語(yǔ)言與圖靈機(jī)圖靈機(jī)是識(shí)別0型文法的識(shí)別裝置。圖靈機(jī)被引進(jìn)作為描述過(guò)程的數(shù)學(xué)模型，過(guò)程的直觀概念被看成是能機(jī)械實(shí)現(xiàn)的有窮指令的序列。圖靈機(jī)的基本模型如圖2-1所示。它有一個(gè)有限控制器、一個(gè)被分成若干單元的輸入帶和一個(gè)一次讀入一個(gè)單元的讀頭組成 有限控制器a1a2a3aian讀頭圖2-121型文法與線性界限自動(dòng)機(jī)相對(duì)應(yīng)。上下文有關(guān)文法所對(duì)應(yīng)的自動(dòng)機(jī)稱為線性界限自動(dòng)機(jī)。其功能是能夠識(shí)別上下文無(wú)關(guān)語(yǔ)言，縮寫(xiě)為L(zhǎng)BA。32型語(yǔ)言與下推自動(dòng)機(jī)2型語(yǔ)言或上下文無(wú)關(guān)語(yǔ)言對(duì)應(yīng)的自動(dòng)機(jī)稱為下推自動(dòng)機(jī)。它是識(shí)別上下文無(wú)關(guān)語(yǔ)言的數(shù)學(xué)模型。縮寫(xiě)為PDA。3型語(yǔ)言與有窮狀態(tài)自動(dòng)機(jī)3型語(yǔ)

27、言或正則語(yǔ)言所對(duì)應(yīng)的自動(dòng)機(jī)稱為有窮自動(dòng)機(jī)。縮寫(xiě)為FA。無(wú)論那種自動(dòng)機(jī)都分為確定性和非確定性之分 2.2.6文法分類(lèi)的意義一個(gè)文法實(shí)際上是某種語(yǔ)言的一個(gè)簡(jiǎn)明、確切的描述，它表示了該語(yǔ)言中所允許的一類(lèi)語(yǔ)法結(jié)構(gòu)。從一個(gè)文法能推導(dǎo)出多個(gè)終結(jié)符的句子。但是知道了如何去構(gòu)造屬于某一個(gè)語(yǔ)言的一個(gè)合法串只是問(wèn)題的一個(gè)方面。同時(shí)我們還要有能力判定一個(gè)串是否合法。也就是說(shuō)，我們需要確定這個(gè)給定串的推導(dǎo)序列。如果從文法出發(fā)找不到這個(gè)推導(dǎo)序列，則該串就是非法的。以上四類(lèi)文法都分別與一個(gè)相當(dāng)簡(jiǎn)單但功能很強(qiáng)的自動(dòng)機(jī)相關(guān)。右線性文法可由一種有窮狀態(tài)自動(dòng)機(jī)識(shí)別。2.3文法產(chǎn)生的語(yǔ)言和句型的語(yǔ)法樹(shù)2.3.1推導(dǎo)和規(guī)范推導(dǎo)為了定

28、義文法產(chǎn)生的語(yǔ)言，我們必須給出推導(dǎo)的概念。推導(dǎo)分為三大類(lèi)：直接推導(dǎo)、，長(zhǎng)度為n(n1)的推導(dǎo)和長(zhǎng)度為n（ n0）的推導(dǎo)。定義2.12如是文法G=(VN,VT,P,S)的規(guī)則（或說(shuō)是P中的一產(chǎn)生式），,(VNVT)*，則稱符號(hào)串為符號(hào)串應(yīng)用產(chǎn)生式所得到的直接推導(dǎo)。記為。定義2.13推導(dǎo)長(zhǎng)度大于0的推導(dǎo)：如果 對(duì)于符號(hào)串v 與w存在一個(gè)直接推導(dǎo)序列u0 u1u2u3un (n0)其中u0=v與un =w,則稱符號(hào)串v推導(dǎo)出w或稱w歸約到v，記作v *w，稱這個(gè)直接推導(dǎo)序列是長(zhǎng)度為n的推導(dǎo)，且稱符號(hào)串w是相對(duì)于符號(hào)串v的一個(gè)字。定義2.14推導(dǎo)長(zhǎng)度大于等于0的推導(dǎo)：如果對(duì)于符號(hào)串v和w，v=w或v=

29、w，則記作v *w，稱符號(hào)串v廣義推導(dǎo)到符號(hào)串w，或稱w廣義歸約到v。例2.18根據(jù)文法，考慮以C語(yǔ)言中的無(wú)正負(fù)號(hào)整數(shù)作為識(shí)別符號(hào)的文法。（1）（2）| (3 ) 0|1|2|3|4|5|6|7|8|9VT =0,1,2,3,4,5,6,7,8,9 VN = , ,判斷數(shù)據(jù)2634是否是C語(yǔ)言合法的數(shù)據(jù)。給出數(shù)據(jù)2634的推導(dǎo)。4434346342634由此可見(jiàn)，2634是C 語(yǔ)言的合法數(shù)據(jù)。每一步推導(dǎo)都是直接推導(dǎo)。可以表示為2634定義2.15如果在推導(dǎo)的任何一步，其中、是句型，都是對(duì)中的最左非終結(jié)符進(jìn)行替換，則稱這種推導(dǎo)為最左推導(dǎo)。定義2.16如果在推導(dǎo)的任何一步，其中、是句型，都是對(duì)中的

30、最右非終結(jié)符進(jìn)行替換，則稱這種推導(dǎo)為最右推導(dǎo)。定義2.17在形式語(yǔ)言中，最右推導(dǎo)常稱為規(guī)范推導(dǎo)，由規(guī)范推導(dǎo)所得的句型稱為規(guī)范句型。定義2.15如果在推導(dǎo)的任何一步，其中、是句型，都是對(duì)中的最左非終結(jié)符進(jìn)行替換，則稱這種推導(dǎo)為最左推導(dǎo)。定義2.16如果在推導(dǎo)的任何一步，其中、是句型，都是對(duì)中的最右非終結(jié)符進(jìn)行替換，則稱這種推導(dǎo)為最右推導(dǎo)。定義2.17在形式語(yǔ)言中，最右推導(dǎo)常稱為規(guī)范推導(dǎo)，由規(guī)范推導(dǎo)所得的句型稱為規(guī)范句型。例2.19給出了下列文法G（1）（2）| (3 ) 0|1|2|3|4|5|6|7|8|9VT =0,1,2,3,4,5,6,7,8,9 VN = , ,判斷數(shù)據(jù)2634是否是C

31、語(yǔ)言合法的數(shù)據(jù)。【解】（1）用最右推導(dǎo)，每次用產(chǎn)生式的規(guī)則替換最右邊的非終結(jié)符，推導(dǎo)過(guò)程如下：4434346342634（2）用最左推導(dǎo)，每次直接推導(dǎo)都替換最左邊的非終結(jié)符，推導(dǎo)過(guò)程如下：22626326342.3.2句型、句子和語(yǔ)言定義2.18句型：設(shè)GS是一個(gè)文法，如果符號(hào)串x是從開(kāi)始符號(hào)S推導(dǎo)得到的，即有S=+x，xV+，則稱符號(hào)串x是該文法G的一個(gè)句型。定義2.19句子：GS是一個(gè)文法，如果符號(hào)串x是從開(kāi)始符號(hào)S推導(dǎo)得到的，即有S=+x，并且xVT，則稱該符號(hào)串為該文法的一個(gè)句子。實(shí)質(zhì)上，句子是句型的特殊情況，句子是由終結(jié)符組成，而句型是有終結(jié)符和非終結(jié)符組成。定義2.20語(yǔ)言GS是一

32、個(gè)文法，文法G產(chǎn)生的語(yǔ)言L(G)=x|S=x，并且xVT，即文法的語(yǔ)言是文法所有句子的集合。例2.20 2型文法G=(VN，VT，P，S)其中，VN=SVT=0,1P=S0S1,S01該文法產(chǎn)生的語(yǔ)言是L(G)=0n1n,其中n1例2.21 文法GS定義如下Sif E then S| if E then S else S|while E do S|begin L end|A該文法產(chǎn)生的語(yǔ)言就是程序設(shè)計(jì)語(yǔ)言中的單分支、雙分支、循環(huán)語(yǔ)句和順序語(yǔ)句，其中每個(gè)非終結(jié)符的意義是：S代表語(yǔ)句，L代表語(yǔ)句串、A代表賦值語(yǔ)句，E代表布爾表達(dá)式。例2.22 設(shè)文法GS：EE+T|TTT*F|FF(E)|i證明符

33、號(hào)串E+(E+T)*i是文法的句型，i+i*i 是文法的句子；并說(shuō)明該文法產(chǎn)生的語(yǔ)言是什么。【證明】由于EE+TE+T*FE+T*iE+F*iE+(E)*i E+(E+T)*i所以 E+(E+T)*i是文法的句型。由EE+TE+FE+F*iE+i*iT+i*iF+i*ii+i*i所以i+i*i 是文法的句子。該文法產(chǎn)生的語(yǔ)言是程序設(shè)計(jì)語(yǔ)言中的算術(shù)運(yùn)算式，其中包括加、乘和括號(hào)運(yùn)算。2.3.3語(yǔ)法樹(shù)在自然語(yǔ)言中，句子結(jié)構(gòu)可以借助一種樹(shù)形表示進(jìn)行分析。如下面的句子：They are students and teachers of the Physics Department。對(duì)該句子的結(jié)構(gòu)進(jìn)行分析

34、，其樹(shù)型結(jié)構(gòu)如圖2-3所示，由此可以看出，該句子是由主語(yǔ)、系詞和表語(yǔ)組成，是一個(gè)語(yǔ)法正確的句子。句子主語(yǔ)系詞表語(yǔ)代詞Theyare名詞student連接詞and名詞teacher定語(yǔ)前置詞冠詞名詞ofthePhysics名詞Department圖2-3句子結(jié)構(gòu)在自然語(yǔ)言中，可以通過(guò)樹(shù)型表示直觀地分析句子的結(jié)構(gòu)；在形式語(yǔ)言中，我們提到了句型、推導(dǎo)的概念，在證明某個(gè)符號(hào)串是否是某個(gè)文法的句型時(shí)，采用從文法開(kāi)始符號(hào)推導(dǎo)的方法，這個(gè)推導(dǎo)過(guò)程可以用語(yǔ)法樹(shù)直觀的表示出來(lái)。語(yǔ)法樹(shù)也稱為推導(dǎo)樹(shù)，其定義如下：給定文法G=(VN,VT,P,S) ，對(duì)于G的任何句型都能構(gòu)造與之關(guān)聯(lián)的語(yǔ)法樹(shù)，這棵樹(shù)滿足下列四個(gè)條件：

35、（1）每個(gè)結(jié)點(diǎn)都有一個(gè)標(biāo)記，此標(biāo)記是V的一個(gè)符號(hào)。（2）根的標(biāo)記是S。（3）若一結(jié)點(diǎn)n至少有一個(gè)它自己除外的子孫，并且有標(biāo)記A，則A肯定在VN中。（4）如果結(jié)點(diǎn)n的直接子孫，從左到右的次序是結(jié)點(diǎn)n1,n2,n3.nk，其標(biāo)記分別為A1，A2，A3，AK。那么AA1A2A3AK一定是P中的一個(gè)產(chǎn)生式。例2.23 設(shè)文法GS ：EE+T|TTT*F|FF(E)|i證明符號(hào)串E+(E+T)*i是文法的句型。EE+Ti*FF()TE+ET2.3.4二義性文法及其他1二義性文法及其定義一個(gè)文法，如果它的一個(gè)句子或句型有兩棵或兩棵以上的語(yǔ)法樹(shù)，則稱此句子具有二義性。如果一個(gè)文法含有二義性的句子，則稱該文法

36、具有二義性。例2.24 設(shè)文法GS：Sif B then S|if B then S else S|i：=E給出符號(hào)串if B then if B then S else S的語(yǔ)法樹(shù)。語(yǔ)法樹(shù)的結(jié)構(gòu)如圖2-5所示。從上面的語(yǔ)法圖我們可以看出，字符串if B then if B then S else S能夠畫(huà)出兩棵語(yǔ)法樹(shù)，所以該文法是一個(gè)二義性文法。在語(yǔ)言中，為了避免二義性的文法，往往對(duì)文法加以一定的限制，如限制條件語(yǔ)句then之后不允許再是條件語(yǔ)句，或者從語(yǔ)義解釋方面限制條件語(yǔ)句中的else只能與其前面的、還沒(méi)有和其他else配對(duì)的then配對(duì)。如此限制之后，符號(hào)串if B then if B

37、 then S else S就只有圖2-5左邊的樹(shù)形結(jié)構(gòu)了。SifBthenSifBthenelseSSSifBthenelseSSifBthenS2二義性文法的證明要判定一個(gè)文法是否是二義性文法，或它是否產(chǎn)生一個(gè)先天二義性的上下文無(wú)關(guān)語(yǔ)言，是個(gè)遞歸不可解的。即不存在一個(gè)算法，它能在有限的步驟內(nèi)，確切的判斷出某個(gè)給定的文法是否是一個(gè)二義性文法。我們要證明一個(gè)文法是否是一個(gè)二義性文法，就是找到該文法的一個(gè)句型特例，能夠畫(huà)出這個(gè)句型的兩棵語(yǔ)法樹(shù)，該文法就是二義性文法。例2.25 文法G=（E，+，*，I,(,)，P，E）其中P為：Ei EE+EEE*EE(E)證明該文法是二義性文法，并將該文法改為

38、等價(jià)的非二義性文法（等價(jià)的文法是指產(chǎn)生的語(yǔ)言相等的文法）?！咀C明】取句型i*i+i，寫(xiě)出該句型的兩個(gè)不同的推導(dǎo)。畫(huà)出推導(dǎo)的兩棵不同的語(yǔ)法樹(shù)。推導(dǎo)1：EE+EE*E+Ei*E+Ei*i+Ei*i+i推導(dǎo)2：EE*Ei*Ei*E+Ei*i+Ei*i+i推導(dǎo)的兩棵語(yǔ)法樹(shù)如圖2-6所示。將文法改為非二義性文法為：ET |E+TTF |T*FF（E）|iEEE+E*EiiiEEEE*E*Eiii2.3.5文法產(chǎn)生的語(yǔ)言和產(chǎn)生語(yǔ)言的文法例2.26 設(shè)G=（VN，VT，P，S），VN=S,B,E，VT=a,b,c，P由下列產(chǎn)生式組成：SaSBESaBEEBBEaBabbBbbbEbeeEee（1）問(wèn)該文法是

39、Chomsky哪一類(lèi)型的文法？（2）它生成的語(yǔ)言是什么？答：根據(jù)文法分類(lèi)定義，由于文法中存在產(chǎn)生式，其左部由長(zhǎng)度大于1的符號(hào)串構(gòu)成，如產(chǎn)生式“EBBE”，顯然不符合Chomsky 的2型和3型文法的定義。該文法產(chǎn)生式左部串的長(zhǎng)度均小于等于右部串的長(zhǎng)度，符合1型文法的定義，所以該文法是上下文有關(guān)文法。（2）根據(jù)如下推導(dǎo)：對(duì)于每一個(gè)n1，我們將號(hào)產(chǎn)生式使用n-1次，得到推導(dǎo)序列：S an-1S(BE)n-1，然后使用產(chǎn)生式(2)一次，得到：S an(BE)n，然后從an(BE)n.繼續(xù)推導(dǎo)，總是對(duì)EB使用產(chǎn)生式的右部進(jìn)行替換，而最終在得到的串中，所有的B都限于所有的E。設(shè)n=3，aaBEBEBEa

40、aaBBEEBEaaaBBEBEEaaaBBBEEE。即有：S anBnEn.接著，使用產(chǎn)生式(4)一次,得到SanbBn-1En，然后使用產(chǎn)生式n-1 次得到：S anbnEn，然后使用產(chǎn)生式一次，使用產(chǎn)生式n-1次，得到：S anbnen 因此該文法產(chǎn)生的語(yǔ)言是L(G)=anbnen|n1。 例2.27 設(shè)有上下文無(wú)關(guān)文法如下：GS：SABAUTUa|aUTb|bTBc|cC將文法的產(chǎn)生式代入產(chǎn)生如下文法：GS： SUTB Ua| aUTb|bTBc|cC考察文法，用L(S)，L(U)，L(T)和L(B)分別表示從終結(jié)符S，U，T和B出發(fā)推導(dǎo)出的符號(hào)串的集合，不難發(fā)現(xiàn)：L（U）=ai|i1

41、=a+L（T）=bj|j1=a+L（B）=ck|k1=a+由于有SUTB，則有：L（S）=L(U)L(T)L(B)=(aibjck|i1,j1, k1)=a+b+c+例2.28 構(gòu)造一個(gè)上下文無(wú)關(guān)文法G，使其描述的語(yǔ)言L（G）是能夠被5整除的無(wú)符號(hào)整數(shù)集合。能夠被5整除的整數(shù)其結(jié)構(gòu)特點(diǎn)是，末位數(shù)一定是0或5。所以，只要保證生成的整數(shù)末位數(shù)字是0或5即可。據(jù)此，構(gòu)造描述能被5整除的無(wú)符號(hào)整數(shù)集合的文法如下：GS：SN0|N5NDN|D0|1|2|3|4|5|6|7|8|9例2.29 寫(xiě)出一個(gè)上下文無(wú)關(guān)文法G，使得L(G)=anbmcmdn|n0，m1分析該語(yǔ)言的特點(diǎn)，可以看出，a和d的個(gè)數(shù)是一樣

42、的，b和c的個(gè)數(shù)是一樣的。m的取值范圍從1開(kāi)始，所以至少有一個(gè)bc，n的最小值為0。寫(xiě)出文法為：SaAd|A AbAc|bc2.4句型分析與句柄對(duì)于上下文無(wú)關(guān)文法，語(yǔ)法樹(shù)是句型推導(dǎo)過(guò)程的幾何表示；是進(jìn)行句型分析極好的工具。所謂句型分析就是識(shí)別一個(gè)符號(hào)串是否是某一個(gè)文法的句型。進(jìn)一步說(shuō)就是給定一個(gè)符號(hào)串時(shí)，按照某文法的規(guī)則為該符號(hào)串構(gòu)造推導(dǎo)或語(yǔ)法樹(shù)，以此來(lái)識(shí)別它是文法的一個(gè)句型。對(duì)于上下文無(wú)關(guān)文法，其句型分析方法有兩大類(lèi)，一類(lèi)是自上而下的分析方法（又稱自頂向下），另一類(lèi)是自下而上（自底向上）的分析方法。2.4.1 自上向下的分析方法1基本思想 自上而下的分析方法就是從識(shí)別符號(hào)出發(fā)，看是否能推導(dǎo)出

43、待檢查的符號(hào)串，如果能推導(dǎo)出這個(gè)符號(hào)串，則表明此符號(hào)串是該文法的句型或句子，否則就不是。或者說(shuō)，以文法的識(shí)別符號(hào)作為根結(jié)點(diǎn)，看是否能構(gòu)造出一個(gè)語(yǔ)法樹(shù)，而且此語(yǔ)法樹(shù)所有葉子結(jié)點(diǎn)從左到右所構(gòu)成的符號(hào)串恰好是待檢查的符號(hào)串。如果能生成這樣的語(yǔ)法樹(shù)，則表明待檢查的符號(hào)串是該文法的一個(gè)句型或句子，否則就不是。例2.30 設(shè)文法GS：SaAbc| aBAbaBbeB|d輸入串：abed，識(shí)別該串是否是該文法的一個(gè)句子。方法：從文法的識(shí)別符號(hào)S開(kāi)始出發(fā)，選擇它的一個(gè)產(chǎn)生式SaAbc 得到直接推導(dǎo)S aAbc以識(shí)別符S作為根結(jié)點(diǎn)，構(gòu)造語(yǔ)法樹(shù)，如下圖2-7所示SaAbcba圖2-7自上而下的推導(dǎo)過(guò)程SaAbcS

44、aBSaBBebSaBebBd（a）（b）（c）（d）（e）2分析過(guò)程符號(hào)串a(chǎn)Abc與待檢查的符號(hào)串a(chǎn)bed的第一個(gè)符號(hào)相匹配。由于符號(hào)串a(chǎn)Abc的第2個(gè)符號(hào)是非終結(jié)符，因此需要對(duì)它進(jìn)行替換。A只有一個(gè)產(chǎn)生式Aba。以其右部替換A，得推導(dǎo)SaAbcababc得到語(yǔ)法樹(shù)，如圖2-7（b）所示。符號(hào)串a(chǎn)babc與待查符號(hào)串a(chǎn)bed的第2個(gè)符號(hào)相匹配，但與第3個(gè)符號(hào)不相匹配，匹配失敗。此時(shí)，需要退回到非終結(jié)符 A，重新選擇S另外的產(chǎn)生式，再做試探。這種選擇的過(guò)程稱之為回溯。選擇S的另外一條產(chǎn)生式的規(guī)則SaB，得到直接推導(dǎo)SaB，得到語(yǔ)法樹(shù)2-7（c），再選取其中的一條產(chǎn)生式BbeB，得到推導(dǎo)SaBa

45、beB，得到語(yǔ)法樹(shù)如圖（d），將Bd代入即可得到該字符串a(chǎn)bed。 3存在問(wèn)題自上而下分析方法是從文法的識(shí)別符號(hào)開(kāi)始，選擇相應(yīng)的產(chǎn)生式規(guī)則進(jìn)行推導(dǎo)。但在推導(dǎo)過(guò)程中會(huì)出現(xiàn)回溯現(xiàn)象。我們把出現(xiàn)回溯的分析稱為不確定的自頂上下分析方法。這種方法花費(fèi)時(shí)間多，效率低，編程實(shí)現(xiàn)時(shí)復(fù)雜，如果對(duì)文法加以限制，就可以避免回溯，這就出現(xiàn)了我們后面要提到的LL(1)分析方法2.4.2確定的自上而下的分析方法例2.31 設(shè)文法GSSaBc|bCdBeB|fCdC|c試檢查符號(hào)串a(chǎn)efc是不是該文法的句子。識(shí)別符S有兩條產(chǎn)生式，它們的右部首符號(hào)分別是終結(jié)符a和b。待檢查符號(hào)串a(chǎn)efc的首符號(hào)是a，所以從識(shí)別符S出發(fā)，只能

46、選擇其產(chǎn)生式SaBc得到直接推導(dǎo)SaBc得到語(yǔ)法樹(shù)如圖2-8（a）所示。其中，非終結(jié)符B有兩條產(chǎn)生式，它們右部首符號(hào)分別是終結(jié)符e與f，而待檢查的符號(hào)串a(chǎn)efc的第2個(gè)符號(hào)是終結(jié)符e，所以選擇B的產(chǎn)生式BeB得到推導(dǎo)SaBcaeBc，得到語(yǔ)法樹(shù)如圖2-8（b）所示。由于待檢查的符號(hào)串a(chǎn)efc的第3個(gè)符號(hào)是終結(jié)符f，因而對(duì)句型aeBc中的非終結(jié)符B選擇其產(chǎn)生式Bf的推導(dǎo)SaBcaeBcaefc得到語(yǔ)法樹(shù)如圖2-8（c）所示。如此推導(dǎo)出的符號(hào)串a(chǎn)efc，語(yǔ)法樹(shù)的葉子結(jié)點(diǎn)序列是aefc，與待檢查的符號(hào)串a(chǎn)efc相匹配。SaBcSaBceBSaBceBf圖2-8語(yǔ)法樹(shù)例2.32 若有文法GSSAp|B

47、qAaAcABbBdB當(dāng)輸入串W=ccap，那么試圖推出輸入串的推導(dǎo)過(guò)程為：SApcApccApccap很容易構(gòu)造相應(yīng)語(yǔ)法樹(shù)，如圖2-9所示。SApSApcASApcAcASApcAcAa圖2-9語(yǔ)法樹(shù)（a）（b）（c）（d）2.4.3自下而上的分析方法1基本思想自下而上的分析方法的基本思想是從待檢查的符號(hào)串出發(fā)，看最終是否能歸約到文法的識(shí)別符號(hào)。如果能歸約到文法的開(kāi)始的識(shí)別符號(hào)，則表明此待檢查的符號(hào)串是該文法的一個(gè)句型或句子，否則便不是。例2.33 若有文法GSScAdAabAa識(shí)別輸入串w=cabd是否是該文法的句子。首先從輸入串開(kāi)始，掃描cabd，從中尋找一個(gè)子串，該子串與某一產(chǎn)生式的右

48、端相匹配。子串a(chǎn)和子串a(chǎn)b都是合格的，假若我們選用了ab，用產(chǎn)生式的左端A去替代它，即把a(bǔ)b歸約到A，得到串cAd。構(gòu)造一個(gè)直接推導(dǎo)cAdcabd，即從cabd葉子開(kāi)始向上構(gòu)造語(yǔ)法樹(shù)，接下去在得到的串cAd中又找到了子串cAd與產(chǎn)生式的右端相匹配，則用S替代cAd，或稱將cAd歸約到S，得到了又一直接推導(dǎo)ScAd，形成了最終的語(yǔ)法樹(shù)。分析過(guò)程如圖2-10所示。圖2-10自下而上構(gòu)造語(yǔ)法樹(shù)cabdcabdAcabdAS2存在問(wèn)題在自上向下的分析中，假定要被代換的最左非終結(jié)符的符號(hào)是V，且有n條規(guī)則：V1|2|3|n，那么如何確定用哪個(gè)右部去替換V？有一種解決方法是從各種可能的選擇中挑選一種，并希

49、望它是正確的。如果發(fā)現(xiàn)它是錯(cuò)誤的，我們必須退回，再試著進(jìn)行另外的選擇，這種方式稱為回溯。在自下向上的分析方法中，在分析程序工作的每一步中，都從當(dāng)前串中選擇一個(gè)子串，將它歸約到某個(gè)非終結(jié)符號(hào)，我們暫且把這個(gè)子串稱為“可歸約串”。出現(xiàn)的問(wèn)題是如何確定這個(gè)“可歸約串”？比如在上例中，我們?cè)趯?duì)輸入串cabd 的分析中，如果不是選擇ab，用產(chǎn)生式，而是選擇a，用產(chǎn)生式將a歸約到A，那么最終就達(dá)不到S的結(jié)果，也就不知道cabd是一個(gè)句子。因此在歸約時(shí)，ab是“可歸約串”而不是a。如何求“可歸約串”成為自下而上進(jìn)行分析的關(guān)鍵。下面我們用“句柄”的概念來(lái)描述“可歸約3句柄的概念 （1）形式化定義定義2.21令

50、G是一文法，S是文法的開(kāi)始符號(hào)， 是文法的一個(gè)句型。如果有：SA且A則稱是句型相對(duì)于非終結(jié)符A的短語(yǔ)。特別地，如有A則稱是句型相對(duì)于規(guī)則A的直接短語(yǔ)。一個(gè)句型的最左直接短語(yǔ)稱為該句型的句柄。（2）求一個(gè)句型的句柄給定某個(gè)句型，要求出該句型的句柄，比較直觀的方法就是畫(huà)出該句型的語(yǔ)法樹(shù)。該語(yǔ)法樹(shù)的一棵子樹(shù)的葉子結(jié)點(diǎn)（從左到右）組成的符號(hào)串便是這個(gè)句型關(guān)于子樹(shù)根結(jié)點(diǎn)的一個(gè)短語(yǔ)。語(yǔ)法樹(shù)的一棵簡(jiǎn)單子樹(shù)（只有單層子樹(shù)）的葉子結(jié)點(diǎn)組成的符號(hào)串是這個(gè)句型關(guān)于簡(jiǎn)單子樹(shù)根結(jié)點(diǎn)的一個(gè)直接短語(yǔ)。語(yǔ)法樹(shù)的最左的簡(jiǎn)單子樹(shù)葉子結(jié)點(diǎn)組成的符號(hào)串就是這個(gè)句型的句柄。例2.34 已知文法GS：S(R)|a|RTTS,T|S句型=

51、(a,(T),(S,T)的語(yǔ)法樹(shù)如圖2-11所示?！窘獯稹坑^察該語(yǔ)法樹(shù)，共有10個(gè)非葉子結(jié)點(diǎn)，10棵子樹(shù)。因此有短語(yǔ)aT(T)S,T(S,T)(T), (S,T)a, (T), (S,T)(a, (T), (S,T)S(R)S，TaT，ST(R)TS(R)S，T圖2-11語(yǔ)法樹(shù)2.4.4文法的存儲(chǔ)一個(gè)文法的語(yǔ)法圖由該文法所有非終結(jié)符的定義圖組成。每個(gè)非終結(jié)符號(hào)的定義圖是一個(gè)結(jié)構(gòu)型數(shù)據(jù)。名字定義下一個(gè)候選式右部后繼寫(xiě)成高級(jí)語(yǔ)言的結(jié)構(gòu)型數(shù)據(jù)形式，則為：type struc=boxesboxes=recordname:array110 of char;def:struc;nextp:struc;ri

52、ghts:struc;end;其中，“名字”是用某種內(nèi)部形式表示的終結(jié)符號(hào)或非終結(jié)符號(hào)的名字。“定義”是一個(gè)指針，對(duì)于非終結(jié)符號(hào)，它指向其第一個(gè)侯選式結(jié)構(gòu)圖的開(kāi)始位置。對(duì)于終結(jié)符號(hào)，它為0；“下一個(gè)侯選式”是一個(gè)指針，指向相同左部的下一個(gè)侯選式的開(kāi)始位置。若無(wú)侯選式，則它為0；“右部后繼”是一個(gè)指針，指向同一個(gè)右部的下一個(gè)符號(hào)。另用一個(gè)一維數(shù)組記錄所有的非終結(jié)符號(hào)定義圖的開(kāi)始地址。也就是說(shuō)，這個(gè)數(shù)組的每個(gè)元素都是一個(gè)指針，分別指向相應(yīng)的非終結(jié)符號(hào)的第一個(gè)候選式的定義圖。例2.35文法EEAT|TTTMF|FF（E）|iA+|M*|/按照上面的存儲(chǔ)結(jié)構(gòu)，畫(huà)出文法的存儲(chǔ)結(jié)構(gòu)如圖2-12所示：EE+

53、TET文法圖2-15文法的鏈表結(jié)構(gòu)圖TT*FTFF(E)Fi小 結(jié)文法是形式語(yǔ)言的一個(gè)十分重要的基本概念。文法可定義為一個(gè)四元組，文法G=（VN，VT，P，S），其中，VN是一個(gè)非終結(jié)符集，VT是一個(gè)終結(jié)符集，P是一個(gè)產(chǎn)生式集，S是文法的開(kāi)始符號(hào)。Chomsky 將文法分為0 型，1型，2型和3型文法。程序設(shè)計(jì)語(yǔ)言的詞法規(guī)則屬于3型文法（正規(guī)文法），程序設(shè)計(jì)語(yǔ)言的語(yǔ)法和語(yǔ)義部分一般是采用2型文法來(lái)描述。對(duì)于一個(gè)文法，我們需要研究它的句型，句子和語(yǔ)言。要識(shí)別一個(gè)符號(hào)串是不是一個(gè)文法的句子，需要對(duì)它進(jìn)行語(yǔ)法分析。分析方法有兩類(lèi)，一類(lèi)是自上而下分析法，另一類(lèi)是自下而上的分析方法。為了進(jìn)行語(yǔ)法分析，需

54、要事先將產(chǎn)生式存儲(chǔ)在計(jì)算機(jī)中。可以為文法建立一個(gè)產(chǎn)生式表，把文法的所有的產(chǎn)生式都放在這個(gè)產(chǎn)生式表中。為了在分析過(guò)程中能迅速查找到相應(yīng)的產(chǎn)生式，還可以建立一個(gè)目錄表。習(xí) 題1設(shè)字母表A=a，符號(hào)串x=aaa，寫(xiě)出下列符號(hào)串及其長(zhǎng)度：x0，xx，x5以及A+和A*。2令=a,b,c，又令x=abc，y=b，z=aab，寫(xiě)出下列符號(hào)串及它們的長(zhǎng)度：xy，xyz，(xy)3。3設(shè)文法GS：SSS*|SS+|a，寫(xiě)出符號(hào)串a(chǎn)a+a*規(guī)范推導(dǎo)，并構(gòu)造語(yǔ)法樹(shù)。4已知文法SAB A|aA Bbc|bBc寫(xiě)出該文法描述的語(yǔ)言。5已知文法ET|E+T|E-TTF|T*F|T/FF(E)|i寫(xiě)出該文法的開(kāi)始符號(hào)、終

55、結(jié)符集合VT、非終結(jié)符集合VN。6對(duì)于文法ET|E+T|E-TTF|T*F|T/FF(E)|i寫(xiě)出句型T+T*F+i的短語(yǔ)、簡(jiǎn)單短語(yǔ)以及句柄。7設(shè)計(jì)出語(yǔ)言anbm|n,m1的文法。8文法G=(A，B，S，a,b,c,P,S)其中P為：SAc|AbAabBbc寫(xiě)出LGS）的全部元素。9已知文法ZaZb Zab 寫(xiě)出L（GZ）的全部元素。10為句子i+i*i構(gòu)造兩棵語(yǔ)法樹(shù)，從而證明下述文 法是二義性的。 i|()| +|*|/11寫(xiě)出生成下述語(yǔ)言的上下文無(wú)關(guān)文法。 （1）anbnambm|n,m0 (2) 1n0m1m0n|n,m012句型、句子和語(yǔ)言之間有什么關(guān)系？第三章 詞法分析本章學(xué)習(xí)目標(biāo)詞

56、法分析程序的主要任務(wù)是對(duì)源程序進(jìn)行掃描，從中識(shí)別出單詞。它是編譯程序的第一步，也是編譯過(guò)程中不可缺少的部分。本章的主要內(nèi)容是： 正則表達(dá)式和有限自動(dòng)機(jī)文法、正規(guī)表達(dá)式、正規(guī)集及自動(dòng)機(jī)的相互轉(zhuǎn)換詞法分析器的C語(yǔ)言實(shí)現(xiàn)詞法分析器的自動(dòng)生成3.1詞法分析器與單詞符號(hào)3.1.1 詞法分析詞法分析是編譯過(guò)程的第一個(gè)階段。這個(gè)階段的任務(wù)是從左到右一個(gè)字符一個(gè)字符地讀入源程序，對(duì)構(gòu)成源程序的字符流進(jìn)行掃描和分解，從而識(shí)別出一個(gè)一個(gè)的單詞。編譯程序中完成詞法分析任務(wù)的程序段，稱為詞法分析程序。詞法分析程序?qū)υ闯绦蜻M(jìn)行掃描，從中識(shí)別出一個(gè)個(gè)的單詞符號(hào)，因此，詞法分析程序又稱為詞法分析器，又稱掃描器。詞法分析器作

57、為編譯程序的一部分，它與語(yǔ)法分析程序之間接口方式有兩種。一種方式是詞法分析程序獨(dú)立工作，把字符流的源程序變?yōu)閱卧~序列，輸出在一個(gè)中間文件上，這個(gè)文件稱為語(yǔ)法分析程序的輸入而繼續(xù)編譯，如圖3-1所示就是將詞法分析單獨(dú)作為一遍的接口方式。源程序詞法分析程序單詞序列圖3-1詞法分析單獨(dú)作為一遍取符號(hào)源程序詞法分析程序語(yǔ)法分析程序圖3-2詞法分析作為語(yǔ)法分析子程序送符號(hào)另一種方法，也是常用的一種方法就是把詞法分析程序設(shè)計(jì)成一個(gè)子程序，每當(dāng)語(yǔ)法分析程序需要一個(gè)單詞時(shí)，就調(diào)用該程序。詞法分析程序每得到一次調(diào)用，就從源程序文件中讀入一個(gè)字符，直到識(shí)別出一個(gè)單詞為止。這種方法省去了中間文件。源程序詞法分析程序

58、單詞序列圖3-1詞法分析單獨(dú)作為一遍取符號(hào)源程序詞法分析程序語(yǔ)法分析程序圖3-2詞法分析作為語(yǔ)法分析子程序送符號(hào)3.1.2單詞符號(hào)單詞符號(hào)是程序設(shè)計(jì)語(yǔ)言的基本語(yǔ)法單位和最小語(yǔ)義單位。單詞符號(hào)一般分為五類(lèi)。（1）關(guān)鍵字（又稱保留字或基本字）如if，then ，else，while，do，begin和end。（2）標(biāo)識(shí)符，用于表示變量名、過(guò)程名等。（3）常數(shù)，如123，實(shí)數(shù)型45.67等。（4）運(yùn)算符，如+，-，*，/，A，且 =*，且# FOLLOW(A)。也可以定義為FOLLOW（A）=a|SAa，a VT若有S=A，則規(guī)定#FOLLOW（A）一般來(lái)講，我們用“#”作為輸入串的結(jié)束符，或稱為句

59、子的括號(hào)，如#輸入串#。4.1.2 LL(1)文法的定義根據(jù)上面的分析我們重新定義一個(gè)產(chǎn)生式被選擇時(shí)的集合SELECT如下。定義4.3 給定上下文無(wú)關(guān)文法的產(chǎn)生式A，AVN，V*，若不能推出，則SELECT(A)=FIRST()如果能夠推導(dǎo)出，則SELECT(A)=(FIRST()FOLLOW(A)。LL(1)文法定義：。定義4.4 一個(gè)上下文無(wú)關(guān)文法是LL（1）文法的充分必要條件是，對(duì)每個(gè)非終結(jié)符A的兩個(gè)不同的產(chǎn)生式，A，A 滿足SELECT（A）SELECT（A）=其中，和不同時(shí)推出。如果某個(gè)文法滿足上述條件，稱該文法為L(zhǎng)L(1)文法。如果一個(gè)文法是LL(1)文法，就可以采用確定的自頂向下

60、分析技術(shù)進(jìn)行語(yǔ)法分析。LL(1)文法的含義是：第一個(gè)L表明自頂向下分析是從左向右掃描輸入串，第二個(gè)L表明分析過(guò)程中將用最左推導(dǎo)，1表明只需向右看一個(gè)符號(hào)便可以決定如何推導(dǎo)即選擇哪個(gè)產(chǎn)生式規(guī)則進(jìn)行推導(dǎo)例4.4 有一文法，判斷該文法是否是LL(1)文法，寫(xiě)出判斷過(guò)程。 SpA | qBAcAd |a BdB |bSELECT(SpA)SELECT(SqB)=pq=SELECT(AcAS)SELECT(Aa)=ca=SELECT(BdB)SELECT(Bb)=db=所以是LL(1)文法，即可以采用確定的自頂向下的分析方法。例4.5 若有文法G4S：SaA | dAbAS| SELECT(SaA)SE