《編譯原理》教案

1、編 譯 原 理教案授課題目（教學(xué)章、節(jié)或主題）：第一章 引論課時(shí)安排2授課時(shí)間 第1周 第1、2節(jié) 教學(xué)目的、要求（分掌握、熟悉、了解三個(gè)層次）：簡(jiǎn)單介紹學(xué)習(xí)此課程的目的和要求初步了解編譯技術(shù)的基本原理和方法熟悉Compiler的基本概念掌握Compiler的結(jié)構(gòu)和功能教學(xué)重點(diǎn)和難點(diǎn)：編譯程序的基本結(jié)構(gòu)和功能授課類型（請(qǐng)打）：理論課þ 討論課 實(shí)驗(yàn)課 練習(xí)課 其他教學(xué)方式（請(qǐng)打）：講授þ 討論 示教 指導(dǎo)þ 其他教學(xué)資源（請(qǐng)打）：多媒體þ 模型 實(shí)物 掛圖 音像 其他討論、思考題、作業(yè)：編譯程序的基本結(jié)構(gòu)如何？各部分功能？教學(xué)內(nèi)容0 課程學(xué)習(xí)的要求及任務(wù)

2、，學(xué)習(xí)方法介紹，成績(jī)考核標(biāo)準(zhǔn)。第一章 引論1.1 什么叫編譯程序？ 通常所說(shuō)的翻譯程序是指這樣的一個(gè)程序，它能夠把某一種語(yǔ)言程序(稱為源語(yǔ)言程序)轉(zhuǎn)換成另一種語(yǔ)言程序(稱為目標(biāo)語(yǔ)言程序)，而后者與前者在邏輯上是等價(jià)的。如果 源語(yǔ)言是諸如FORTRAN、Pascal、C、Ada、Smalltalk或Java這樣的“高級(jí)語(yǔ)言”，而目標(biāo)語(yǔ)言是諸如匯編語(yǔ)言或機(jī)器語(yǔ)言之類的“低級(jí)語(yǔ)言”，這樣的一個(gè)翻譯程序就稱為編譯程序。 高級(jí)語(yǔ)言程序除了像上面所說(shuō)的先編譯后執(zhí)行外，有時(shí)也可“解釋”執(zhí)行。一個(gè)源語(yǔ)言的解釋程序是這樣的程序，它以該語(yǔ)言寫(xiě)的源程序作為輸入，但不產(chǎn)生目標(biāo)程序，而是 邊解釋邊執(zhí)行源程序本身。本書(shū)將

3、不對(duì)解釋程序作專門(mén)的討論。實(shí)際上，許多編譯程序的構(gòu)造與實(shí)現(xiàn)技術(shù)同樣適用于解釋程序。 根據(jù)不同的用途和側(cè)重，編譯程序還可進(jìn)一步分類。專門(mén)用于幫助程序開(kāi)發(fā)和調(diào)試 的編譯程序稱為診斷編譯程序(Diagnostic Compiler)，著重于提高目標(biāo)代碼效率的編譯程序叫優(yōu)化編譯程序(Optimizing Compiler)。現(xiàn)在很多編譯程序同時(shí)提供了調(diào)試、優(yōu)化等多種功能，用戶可以通過(guò)“開(kāi)關(guān)”進(jìn)行選擇。運(yùn)行編譯程序的計(jì)算機(jī)稱宿主機(jī)，運(yùn)行編譯程序所產(chǎn)生目標(biāo)代碼的計(jì)算機(jī)稱目標(biāo)機(jī)。 如果一個(gè)編譯程序產(chǎn)生不同于其宿主機(jī)的機(jī)器代碼， 則稱它為交叉編譯程序(CrOSS Compiler)。如果不需重寫(xiě)編譯程序中與機(jī)

4、器無(wú)關(guān)的部分就能改變目標(biāo)機(jī)，則稱該編譯程序?yàn)榭勺兡繕?biāo)編譯程序(Retargetable Compiler)。1.2 編譯過(guò)程概述編譯程序過(guò)程: 從輸入源程序開(kāi)始到輸出目標(biāo)程序?yàn)橹沟恼麄€(gè)編譯過(guò)程可分為以下五個(gè)階段：詞法分析,語(yǔ)法分析,語(yǔ)義分析,中間代碼產(chǎn)生,優(yōu)化和目標(biāo)代碼生成.1.3 編譯程序的結(jié)構(gòu) 編譯程序的結(jié)構(gòu)可以按照從輸入源程序開(kāi)始到輸出目標(biāo)程序?yàn)橹沟恼麄€(gè)編譯過(guò)程可分為以下五個(gè)階段：詞法分析,語(yǔ)法分析,語(yǔ)義分析,中間代碼產(chǎn)生,優(yōu)化和目標(biāo)代碼生成。 編譯程序總框 編譯程序的結(jié)構(gòu)可以按照這五個(gè)階段的任務(wù)分模塊進(jìn)行設(shè)計(jì)。下圖給出了編譯程序的總框。 表格與表格管理 編譯程序在工作過(guò)程中需要保持一系

5、列的表格，以登記源程序的各類信息和編譯各階段的進(jìn)展?fàn)顩r。在編譯程序使用的表格中，最合理的是符號(hào)表。 編譯程序在工作過(guò)程中需要保持一系列的表格，以登記源程序的各類信息和編譯各階段的進(jìn)展?fàn)顩r。合理地設(shè)計(jì)和使用表格是編譯程序構(gòu)造的一個(gè)重要問(wèn)題。在編譯程序使用的表格中，最重要的是符號(hào)表。它用來(lái)登記源程序中出現(xiàn)的每個(gè)名字以及名字的各種屬性。例如，一個(gè)名字是常量名、變量名，還是過(guò)程名等等；如果是變量名，它的類型是什么、所占內(nèi)存是多大、地址是什么等等。通常，編譯程序在處理到名字的定義性出現(xiàn)時(shí)，要把名字的各種屬性填人到符號(hào)表中；當(dāng)處理到名字的使用性出現(xiàn)時(shí)，要對(duì)名字的屬性進(jìn)行查證。 當(dāng)掃描器識(shí)別出一個(gè)名字(標(biāo)識(shí)

6、符)后，它把該名字填人到符號(hào)表中。但這時(shí)不能完全確定名字的屬性，它的各種屬性要在后續(xù)的各階段才能填人。例如，名字的類型等要在語(yǔ)義分析時(shí)才能確定，而名字的地址可能要到目標(biāo)代碼生成才能確定。 由此可見(jiàn)，編譯各階段都涉及到構(gòu)造、查找或更新有關(guān)的表格。 出錯(cuò)處理 遍:是對(duì)源程序或源程序的中間結(jié)果從頭到尾掃描一次，并作有關(guān)的加工處理，生產(chǎn)新的中間結(jié)果或目標(biāo)程序。一個(gè)編譯程序不僅應(yīng)能對(duì)書(shū)寫(xiě)正確的程序進(jìn)行翻譯，而且應(yīng)能對(duì)出現(xiàn)在源程序中的錯(cuò)誤進(jìn)行處理。如果源程序有錯(cuò)誤，編譯程序應(yīng)設(shè)法發(fā)現(xiàn)錯(cuò)誤，把有關(guān)錯(cuò)誤信息報(bào)告給用戶。這部分工作是由專門(mén)的一組程序(叫做出錯(cuò)處理程序)完成的。一個(gè)好的編譯程序應(yīng)能最大限度地發(fā)現(xiàn)源

7、程序中的各種錯(cuò)誤，準(zhǔn)確地指出錯(cuò)誤的性質(zhì)和發(fā)生錯(cuò)誤的地點(diǎn)，并且能將錯(cuò)誤所造成的影響限制在盡可能小的范圍內(nèi)，使得源程序的其余部分能繼續(xù)被編譯下去，以便進(jìn)一步發(fā)現(xiàn)其它可能的錯(cuò)誤。如果不僅能夠發(fā)現(xiàn)錯(cuò)誤，而且還能自動(dòng)校正錯(cuò)、誤，那當(dāng)然就更好了。但是，自動(dòng)校正錯(cuò)誤的代價(jià)是非常高的。 編譯過(guò)程的每一階段都可能檢測(cè)出錯(cuò)誤，其中，絕大多數(shù)錯(cuò)誤可以在編譯的前三階段檢測(cè)出來(lái)。源程序中的錯(cuò)誤通常分為語(yǔ)法錯(cuò)誤和語(yǔ)義錯(cuò)誤兩大類。語(yǔ)法錯(cuò)誤是指源程序中不符合語(yǔ)法(或詞法)規(guī)則的錯(cuò)誤，它們可在詞法分析或語(yǔ)法分析時(shí)檢測(cè)出來(lái)。例如，詞法分析階段能夠檢測(cè)出“非法字符”之類的錯(cuò)誤；語(yǔ)法分析階段能夠檢測(cè)出諸如“括號(hào)不匹配”、“缺少；”之

8、類的錯(cuò)誤。語(yǔ)義錯(cuò)誤是指源程序中不符合語(yǔ)義規(guī)則的錯(cuò)誤，這些錯(cuò)誤一般在語(yǔ)義分析時(shí)檢測(cè)出來(lái)，有的語(yǔ)義錯(cuò)誤要在運(yùn)行時(shí)才能檢測(cè)出來(lái)。語(yǔ)義錯(cuò)誤通常包括：說(shuō)明錯(cuò)誤、作用域錯(cuò)誤、類型不一致等等。 遍 遍:是對(duì)源程序或源程序的中間結(jié)果從頭到尾掃描一次，并作有關(guān)的加工處理，生產(chǎn)新的中間結(jié)果或目標(biāo)程序。通常，每遍的工作由從外存上獲得的前一遍的中間結(jié)果開(kāi)始(對(duì)于第一遍而言，從外存上獲得源程序)，完成它所含的有關(guān)工作之后，再把結(jié)果記錄于外存。既可以將幾個(gè)不同階段合為一遍，也可以把一個(gè)階段的工作分為若干遍。例如，詞法分析這一階段可以單獨(dú)作為一遍，但更多的時(shí)候是把它與語(yǔ)法分析合并為一遍；為了便于處理，語(yǔ)法分析和語(yǔ)義分析與中

9、間代碼產(chǎn)生又常常合為一遍。在優(yōu)化要求很高時(shí)，往往還可把優(yōu)化階段分為若干遍來(lái)實(shí)現(xiàn)。 當(dāng)一遍中包含若干階段時(shí)，各階段的工作是穿插進(jìn)行的。例如，我們可以把詞法分析、語(yǔ)法分析及語(yǔ)義分析與中間代碼產(chǎn)生這三階段安排成一遍。這時(shí)，語(yǔ)法分析器處于核心位置，當(dāng)它在識(shí)別語(yǔ)法結(jié)構(gòu)而需要下一單詞符號(hào)時(shí)，它就調(diào)用詞法分析器，一旦識(shí)別出一個(gè)語(yǔ)法單位時(shí)，它就調(diào)用中間代碼產(chǎn)生器，完成相應(yīng)的語(yǔ)義分析并產(chǎn)生相應(yīng)的中間代碼。 一個(gè)編譯程序究竟應(yīng)分成幾遍，如何劃分，是與源語(yǔ)言、設(shè)計(jì)要求、硬件設(shè)備等諸因素有關(guān)的，因此難于統(tǒng)一劃定。遍數(shù)多一點(diǎn)有個(gè)好處，即整個(gè)編譯程序的邏輯結(jié)構(gòu)可能清晰一點(diǎn)。但遍數(shù)多勢(shì)必增加輸入輸出所消耗的時(shí)間。因此，在主

10、存可能的前提下，一般還是遍數(shù)盡可能少一點(diǎn)為好。應(yīng)當(dāng)注意的是，并不是每種語(yǔ)言都可以用單遍編譯程序?qū)崿F(xiàn)。 編譯前端與后端 概念上，我們有時(shí)把編譯程序劃分為編譯前端和編譯后端。前端主要由與源語(yǔ)言有關(guān)但與目標(biāo)機(jī)無(wú)關(guān)的那些部分組成。這些部分通常包括詞法分析、語(yǔ)法分析、語(yǔ)義分析與中間代碼產(chǎn)生，有的代碼優(yōu)化工作也可包括在前端。后端包括編譯程序中與目標(biāo)機(jī)有關(guān)的那些部分，如與目標(biāo)機(jī)有關(guān)的代碼優(yōu)化和目標(biāo)代碼生成等。通常，后端不依賴于源語(yǔ)言而僅僅依賴于中間語(yǔ)言。 可以取編譯程序的前端，改寫(xiě)其后端以生成不同目標(biāo)機(jī)上的相同語(yǔ)言的編譯程序。如果后端的設(shè)計(jì)是經(jīng)過(guò)精心考慮的，那么后端的改寫(xiě)將用不了太大工作量，這樣就可實(shí)現(xiàn)編譯

11、程序的目標(biāo)機(jī)改變。也可以設(shè)想將幾種源語(yǔ)言編譯成相同的中間語(yǔ)言，然后為不同的前端配上相同的后端，這樣就可為同一臺(tái)機(jī)器生成不同語(yǔ)言的編譯程序。然而，由于不同語(yǔ)言存在某些微妙的區(qū)別，因此在這方面所取得的成果還非常有限。 為了實(shí)現(xiàn)編譯程序可改變目標(biāo)機(jī)，通常需要有一種定義良好的中間語(yǔ)言支持。例如在著名的Ada程序設(shè)計(jì)環(huán)境APSE中，使用的是一種稱為Diana的樹(shù)形結(jié)構(gòu)的中間語(yǔ)言一個(gè)Ada源程序通過(guò)前編譯轉(zhuǎn)換為Diana中間代碼，由編譯后端把Diana中間代碼轉(zhuǎn)換為目標(biāo)代碼。編譯前端與不同的編譯后端以Diana為界面，實(shí)現(xiàn)編譯程序的目標(biāo)機(jī)改變。 又如，在Java語(yǔ)言環(huán)境中，為了使編譯后的程序從一個(gè)平臺(tái)移到

12、另一個(gè)平臺(tái)，Java定義一種虛擬機(jī)代碼-Bytecode。只要實(shí)際使用的操作平臺(tái)上實(shí)現(xiàn)了的Java解釋器，這個(gè)操作平臺(tái)就可以執(zhí)行各種Java程序。這就是所謂Java語(yǔ)言操作平臺(tái)無(wú)關(guān)性。1.4 編譯程序與程序設(shè)計(jì)環(huán)境 開(kāi)發(fā)通常還需要一些其它的工具；如編輯程序、連接程序，調(diào)試工具等等。編譯程序與這些程序設(shè)計(jì)工具一起構(gòu)成所謂的程序設(shè)計(jì)環(huán)境。 在高級(jí)語(yǔ)言發(fā)展的早期，這些程序設(shè)計(jì)工具往往是獨(dú)立的，缺乏整體性，而且也缺乏對(duì)軟件開(kāi)發(fā)全生命周期的支持。隨著軟件技術(shù)的不斷發(fā)展，現(xiàn)在人們?cè)絹?lái)越傾向于構(gòu)造集成化的程序設(shè)計(jì)環(huán)境。一個(gè)集成化的程序設(shè)計(jì)環(huán)境的特點(diǎn)是，它將相互獨(dú)立的程序設(shè)計(jì)工具集成起來(lái)，以便為程序員提供完整

13、的、一體化的支持，從而進(jìn)一步提高程序開(kāi)發(fā)效率，改善程序質(zhì)量。在一個(gè)好的集成化程序設(shè)計(jì)環(huán)境中，不僅包含豐富的程序設(shè)計(jì)工具，而且還支持程序設(shè)計(jì)方法學(xué)，支持程序開(kāi)發(fā)的全生命周期。有代表性的集成化程序設(shè)計(jì)環(huán)境有Ada語(yǔ)言程序設(shè)計(jì)環(huán)境APSE、LISP語(yǔ)言程序設(shè)計(jì)環(huán)境INTERLISP等。廣大讀者所熟悉的Pascal、TurboC、VisualC+等語(yǔ)言環(huán)境也都可認(rèn)為是集成化的程序設(shè)計(jì)環(huán)境。1.5 編譯程序的生成 以前人們構(gòu)造編譯程序大多是用機(jī)器語(yǔ)言或匯編語(yǔ)言做工具的。為了發(fā)揮各種不同硬件系統(tǒng)的效率，為了滿足各種不同的具體要求，現(xiàn)在許多人仍然采用這種工具來(lái)構(gòu)造編譯程序。但是，越來(lái)越多的人傾向于使用高級(jí)語(yǔ)

14、言作為工具來(lái)構(gòu)造編譯程序。因?yàn)椋@樣可以節(jié)省大量的程序設(shè)計(jì)時(shí)間，而且所構(gòu)造出來(lái)的編譯程序也易于閱讀、修改和移植。 人們已經(jīng)建立了多種編制部分編譯程序或整個(gè)編譯程序的有效工具。有些能用于自動(dòng)產(chǎn)生掃描器，有些可用于自動(dòng)產(chǎn)生語(yǔ)法分析器，有些甚至可用來(lái)自動(dòng)產(chǎn)生整個(gè)的編譯程序。如：編譯程序-編譯程序、編譯程序產(chǎn)生器、翻譯程序書(shū)寫(xiě)系統(tǒng)等，它們是按照對(duì)源語(yǔ)言和目標(biāo)語(yǔ)言（或機(jī)器）的形式描述（作為輸入數(shù)據(jù)）而自動(dòng)產(chǎn)生編譯程序的。本課程將把自動(dòng)產(chǎn)生器作為一個(gè)重要課題來(lái)討論。 近些年來(lái)，有些人主張采用“自編譯方式”產(chǎn)生編譯程序。意思是，先對(duì)語(yǔ)言的核心部分構(gòu)造一個(gè)小小的編譯程序（可用手編實(shí)現(xiàn)），再以它為工具構(gòu)造一個(gè)能

15、夠編譯更多語(yǔ)言成分的較大編譯程序。如此擴(kuò)展下去，就象滾雪球一樣，越滾越大，最后形成人們所期望的整個(gè)編譯程序。這種通過(guò)一系列自展途徑而形成編譯程序的過(guò)程叫作自編譯過(guò)程。 現(xiàn)在，有些編譯程序是通過(guò)“移植”得到的。即把某一機(jī)器上的編譯程序移植到另一機(jī)器上。著需要尋求某種適當(dāng)?shù)摹爸虚g語(yǔ)言”。但是，由于建立通用中間語(yǔ)言實(shí)際上辦不到，因此，移植也只能在幾種語(yǔ)言和幾種機(jī)器之間進(jìn)行。授課題目（教學(xué)章、節(jié)或主題）：第二章 詞法分析課時(shí)安排12授課時(shí)間第1周 第3-6節(jié) 第2周 第1-6節(jié)第3周 第1、2節(jié) 教學(xué)目的、要求（分掌握、熟悉、了解三個(gè)層次）：了解詞法分析器的構(gòu)造方法熟悉詞法分析的任務(wù)和過(guò)程掌握正規(guī)式和

16、有限自動(dòng)機(jī)的基本概念教學(xué)重點(diǎn)和難點(diǎn)：詞法分析器的設(shè)計(jì)、正規(guī)表達(dá)式和有限自動(dòng)機(jī)、正規(guī)表達(dá)式和有限自動(dòng)機(jī)的等價(jià)性、正規(guī)文法和有限自動(dòng)機(jī)間的轉(zhuǎn)換授課類型（請(qǐng)打）：理論課þ 討論課 實(shí)驗(yàn)課þ 練習(xí)課þ 其他教學(xué)方式（請(qǐng)打）：講授þ 討論 示教 指導(dǎo)þ 其他教學(xué)資源（請(qǐng)打）：多媒體þ 模型 實(shí)物 掛圖 音像 其他討論、思考題、作業(yè)：P63：3，6，7，8，12，14教學(xué)內(nèi)容第二章 詞法分析2.1 對(duì)于詞法分析器的要求 首先討論詞法分析器輸出的單詞符號(hào)的一般形式，然后研究詞法分析器應(yīng)如何和語(yǔ)法分析器相銜接。2.1.1 詞法分析器的功能和輸出形式

17、詞法分析器的功能是輸入源程序，輸出單詞符號(hào)。單詞符號(hào)是一個(gè)程序語(yǔ)言的基本語(yǔ)法符號(hào)，程序語(yǔ)言的單詞符號(hào)一般可分為下列五種：1 基本字 如FORTRAN中的DIMENSION、IF和DO 等等；2 標(biāo)識(shí)符 用來(lái)表示各種名字，如變量名、數(shù)組名和過(guò)程名等等；3 常 數(shù) 各種類型的常數(shù)，如125，0.718、TRUE等等； 4 運(yùn)算符 如+、-、*、/等等； 5 界 符 如逗號(hào)、括號(hào)、分號(hào)等等。 標(biāo)識(shí)符一般統(tǒng)歸為一種。常數(shù)則宜按類型（整、實(shí)、復(fù)或布爾）分種?；咀挚蓪⑵淙w視為一種，也可以一字一種。運(yùn)算符可采用一符一種的分法，但也可以把具有一定共性的算符（如所有關(guān)系符）視為一種。界符一般用一符一種的分法

18、。 如果一個(gè)種別只含一個(gè)單詞符號(hào)，那么，對(duì)于這個(gè)單詞符號(hào)，種別編碼就完全代表它自身了。若一個(gè)種別含有許多個(gè)單詞符號(hào)，那么對(duì)于它的每個(gè)單詞符號(hào)，除了給出種別編碼之外，還應(yīng)給出自身的值。2.1.2 詞法分析器作為一個(gè)獨(dú)立子程序 可以使整個(gè)編譯程序的結(jié)構(gòu)更簡(jiǎn)潔、清晰和條例化。2.2 詞法分析器的設(shè)計(jì) 我們將按照詞法分析的任務(wù)和作為一個(gè)獨(dú)立子程序的要求來(lái)考慮詞法分析器的設(shè)計(jì)。2.2.1 輸入、預(yù)處理 詞法分析器工作的第一步是輸入源程序文本。輸入串一般是放在一個(gè)緩沖區(qū)中，這個(gè)緩沖區(qū)稱為輸入緩沖區(qū)。詞法分析的工作（單詞符號(hào)的識(shí)別）可以直接在這個(gè)緩沖區(qū)中進(jìn)行。但在許多情況下，把輸入串預(yù)處理一下，對(duì)單詞符號(hào)的

19、識(shí)別工作將是比較方便的。 預(yù)處理的工作包括：剔除無(wú)用的空白、跳格、回車和換行符等編輯性字符；預(yù)處理工作還可以包括源程序和出錯(cuò)信息的列表打印。2.2.2 單詞符號(hào)的識(shí)別：超前搜索詞法分析器的結(jié)構(gòu)如下圖所示：當(dāng)詞法分析器調(diào)用預(yù)處理子程序處理出一串輸入字符放進(jìn)掃描緩沖區(qū)之后，掃描器就從此緩沖區(qū)中逐一識(shí)別單詞符號(hào)。當(dāng)緩沖區(qū)里的字符串被處理完之后，它又調(diào)用預(yù)處理程序裝入新串。圖3.1 詞法分析器下面我們來(lái)介紹一下單詞符號(hào)識(shí)別的一個(gè)簡(jiǎn)單方法超前搜索。 基本字的識(shí)別 有些語(yǔ)言的基本字的輸入表示有特殊標(biāo)志，如加雙引號(hào)（如“BEGIN”），在這種情況下，基本字的識(shí)別是很直接的，不存在什么困難。 象FORTRAN

20、這樣的語(yǔ)言，基本字不加特殊保護(hù)，基本字和用戶自定義的標(biāo)識(shí)符或標(biāo)號(hào)之間沒(méi)有特殊的界符作間隔，這就使得基本字的識(shí)別甚為麻煩。這里就需要用到超前搜索。2.2.3 狀態(tài)轉(zhuǎn)換圖 使用狀態(tài)轉(zhuǎn)換圖是設(shè)計(jì)詞法分析程序(掃描器)的一種好途徑。轉(zhuǎn)換圖是一張有限方向圖。在狀態(tài)轉(zhuǎn)換圖中，結(jié)點(diǎn)代表狀態(tài)，用圓圈表示。狀態(tài)之間用箭弧連結(jié)。箭弧上的標(biāo)記（字符）代表在射出結(jié)(即箭弧始節(jié))狀態(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)

21、（用雙圈表示）。圖3.2（a）狀態(tài)轉(zhuǎn)換圖示例2.2.4 狀態(tài)轉(zhuǎn)換圖的實(shí)現(xiàn) 一個(gè)狀態(tài)轉(zhuǎn)換圖可用于識(shí)別（或接受）一定的字符。大多數(shù)程序語(yǔ)言的單詞符號(hào)都可以用轉(zhuǎn)換圖予以識(shí)別。轉(zhuǎn)換圖非常易于用程序?qū)崿F(xiàn)，最簡(jiǎn)單的辦法是讓每個(gè)狀態(tài)結(jié)點(diǎn)對(duì)應(yīng)一小段程序。下面我們將引進(jìn)一組全局變量和過(guò)程，把它們作為實(shí)現(xiàn)轉(zhuǎn)換圖的基本成分。這些變量和過(guò)程是：1. CHAR 字符變量，存放最新讀進(jìn)的源程序字符。2. TOKEN 字符數(shù)組，存放構(gòu)成單詞符號(hào)的字符串。3. GETCHAR 子程序過(guò)程，把下一個(gè)輸入字符讀到CHAR中，把搜索指示器前移一字節(jié)位置。4. GETBC 子程序過(guò)程，檢查CHAR中的字符是否為空白.若是，則GETC

22、HAR直到CHAR中進(jìn)入一個(gè)非空白符。5. CONCAT 子程序過(guò)程，把CHAR中的字符連接TOKEN之后。例如，TOKEN原來(lái)的值為AB'，而CHAR中存放著'C'，經(jīng)調(diào)用CONCAT后，TOKEN的值就變?yōu)?#39;ABC'。6. LETTER和DIGIT布爾函數(shù)過(guò)程，它們分別CHAR中的字符是否為字母和數(shù)字，從爾給出真值TRUE或假值FALSE。 7. RESERVE 整型函數(shù)過(guò)程，對(duì)TOKEN中的字符串查找保留字表，若它是一個(gè)保留字則返回它的編碼，否則返回0值(假定0不是保留字的編碼)。8. RETRACT 子程序過(guò)程，把搜索指示器回調(diào)一個(gè)字節(jié)位置，把C

23、HAR中的字符置為空白。2.3 正規(guī)表達(dá)式與有限自動(dòng)機(jī)2.3.1 正規(guī)式與正規(guī)集 設(shè)是一個(gè)有窮字母表，它的每個(gè)元素稱為一個(gè)字符。上的一個(gè)字（也叫字符串）是指由中的字符所構(gòu)成的一個(gè)有窮序列。不包含任何字符的序列稱為空字，記為。用* 表示上的所有字的全體 ，空字也包括在其中。 例如，若=a，b，則*=,a,b,aa,ab,ba,bb,aaa下面是正規(guī)式和正規(guī)集的遞歸定義：1.和 都是 上的正規(guī)式，它們所表示 的正規(guī)集分別為 和 ；2.任何，是上的一個(gè)正規(guī)式，它所表示的正規(guī)集為;3.假定U和V都是 上的正規(guī)式，它們所表示的正規(guī)集分別記為L(zhǎng)（U）和L（V），那么，（U V）、（U|V）和（U）*也都是

24、正規(guī)式，它們所表示的正規(guī)集分別為L(zhǎng)（U）ÈL（V）、L（U）.L（V）（連接積）和 （L（U）*（閉包）。僅由有限次使用上述三步驟而定義的表達(dá)式才是上的正規(guī)式，僅由這些正規(guī)式所表示的字集才是上的正規(guī)集。算符的優(yōu)先順序?yàn)椋合?quot;*"，次"."，最后"|"。例如，令 =a，b ，下面是 上的正規(guī)式和相應(yīng)的正規(guī)集：ba*： 上所有以b為首后跟任意多個(gè)a的字a(a| b)* ： 上所有以a為首的字(a| b)* (aa| bb)(a|b)*： 上所有含有兩個(gè)相繼的a或兩個(gè)相繼的b的字 又例如，令=A，B，0，1 ，則 (A|B)(A|

25、B|0|1)* ： 上的"標(biāo)識(shí)符"的全體 (0|1)(0|1)* ： 上的"數(shù)"的全體 若兩個(gè)正規(guī)式所表示的正規(guī)集相同，則認(rèn)為二者等價(jià)。兩個(gè)等價(jià)的正規(guī)式U和V記為U=V。 令U、V和W 均為正規(guī)式，顯而易見(jiàn)，下列關(guān)系普遍成立 1. V=V|U （交換律） 2. U|(V|W)=(u|v)|w（結(jié)合律） 3. U|(V|W)=(U|V)|W（結(jié)合律） 4. U|(VW)=UV|UW（分配律） (V|W)U=VU|WU 5.U=U =U 2.3.2 確定有限自動(dòng)機(jī)（DFA） 設(shè)一個(gè)確定的有限自動(dòng)機(jī)（DFA）M是一個(gè)五元式M=(S, ,f,S0, Z)其中1.

26、 S是一個(gè)有限集，它的每個(gè)元素稱為一個(gè)狀態(tài)；2. 是一個(gè)有窮字母表，它的每個(gè)元素稱為一個(gè)輸入字符；3. f是一個(gè)從S×至S的（單值）部分映照。f（s，a）=s'意味著：當(dāng)現(xiàn)行狀態(tài)為s，輸入字符a時(shí)，將轉(zhuǎn)換到下一狀態(tài)s'。我們把s'稱為s的一個(gè)后繼狀態(tài)；4. S0ÎS，是唯一的一個(gè)初態(tài)；5. ZÍS，是一個(gè)終態(tài)集（可空）。 一個(gè)DFA可用一個(gè)矩陣表示，該矩陣的行表示狀態(tài)，列表示輸入字符，矩陣元素表示f（s，a）的值，這個(gè)矩陣稱為狀態(tài)轉(zhuǎn)換矩陣。 例如，有DFA M=(0,1,2,3 ,a,b ,f,0,3 其中f為： f(0,a)=1 f(0,

27、b)=2f(1,a)=3 f(4,b)=2f(2,a)=1 f(2,b)=3f(3,a)=3 f(3,b)=3則對(duì)應(yīng)的狀態(tài)轉(zhuǎn)換矩陣如下表3.2所示：表3.2 狀態(tài)轉(zhuǎn)換矩陣狀態(tài)ab012132213333一個(gè)DFA也可以表示成一張（確定的）狀態(tài)轉(zhuǎn)換圖。對(duì)于*中的任何字a，若存在一條從初態(tài)結(jié)到某一條終態(tài)結(jié)的道路，且這條路上所有弧的標(biāo)記符連接成的字等于a，則稱a可為DFA M 所識(shí)別（讀出或接受）。若 M的初態(tài)結(jié)同時(shí)又是終態(tài)結(jié)， 則空字可為M所識(shí)別（或接受）。上例所定義的DFA M相應(yīng)的狀態(tài)轉(zhuǎn)換圖如下所示：它能識(shí)別上所有含有相繼兩個(gè)a或相繼兩個(gè)b的字。圖3.5 狀態(tài)轉(zhuǎn)換圖2.3.3 非確定有限自動(dòng)機(jī)

28、(NFA) 設(shè)一個(gè)確定的有限自動(dòng)機(jī)（DFA）M是一個(gè)五元式M=(S,f,S0, Z)其中1. S是一個(gè)有限集，它的每個(gè)元素稱為一個(gè)狀態(tài)；2.是一個(gè)有窮字母表，它的每個(gè)元素稱為一個(gè)輸入字符；3. f是一個(gè)從S×*到S的子集的映照，即 f：S×*® 2S4. S0ÍS，是非空初態(tài)集；5. Z ÍS，是一個(gè)終態(tài)集（可空）。2.3.4 正規(guī)文法與有限自動(dòng)機(jī)的等價(jià)性 對(duì)于正規(guī)文法G和有限自動(dòng)機(jī)M，如果L（G）L（M），則稱G和M是等價(jià)的。關(guān)于正規(guī)文法和有限自動(dòng)機(jī)的等價(jià)性，有以下結(jié)論：（1） 對(duì)每一個(gè)右線性正規(guī)文法G或左線性正規(guī)文法G，都存在一個(gè)有限自動(dòng)機(jī)

29、（FA）M，使得L（M）L（G）。（2） 對(duì)每一個(gè)FA M，都存在一個(gè)右線性正規(guī)文法GR或左線性正規(guī)文法GL，使得L（M）L（GR）L（GL）2.3.5 正規(guī)式與有限自動(dòng)機(jī)的等價(jià)性 我們可以證明：（1） 對(duì)任何FA M，都存在一個(gè)正規(guī)式r，使得L（r）L（M）。（2） 對(duì)任何的正規(guī)式r，都存在一個(gè)FA M，使得L（M）L（r）。上述結(jié)論加上前面章節(jié)所證明的結(jié)論，說(shuō)明正規(guī)文法、正規(guī)式、確定有限自動(dòng)機(jī)和非確定有限自動(dòng)機(jī)在接收語(yǔ)言的能力上是互相等價(jià)的。2.3.6 確定有限自動(dòng)機(jī)的化簡(jiǎn) 等價(jià)狀態(tài)；最少化。2.4 詞法分析器的自動(dòng)產(chǎn)生 教學(xué)目的：使用狀態(tài)轉(zhuǎn)換圖構(gòu)造詞法分析程序；上機(jī)實(shí)踐LEX的實(shí)現(xiàn)。2.

30、4.1 語(yǔ)言LEX的一般描述 一個(gè)LEX源程序主要包括兩部分。一部分是正規(guī)定義式，另一個(gè)是識(shí)別規(guī)則。 產(chǎn)生式(也稱產(chǎn)生規(guī)則或簡(jiǎn)稱規(guī)則)是定義語(yǔ)法范疇的一種書(shū)寫(xiě)規(guī)則。一個(gè)產(chǎn)生式的 形式是 A®a 其中，箭頭(有時(shí)也用：)左邊的A是一個(gè)非終結(jié)符，稱為產(chǎn)生式的左部符號(hào)；箭頭右邊的a是由終結(jié)符號(hào)或非終結(jié)符號(hào)組成的符號(hào)串，稱為產(chǎn)生式的右部。我們有時(shí)也說(shuō)，產(chǎn)生式A®a是關(guān)于A的一條產(chǎn)生規(guī)則。產(chǎn)生式是用來(lái)定義語(yǔ)法范疇的。例如，令i 代表已定義的范疇“變量”，那么，產(chǎn)生式 算術(shù)表達(dá)式®i 意味著把“算術(shù)表達(dá)式”這個(gè)范疇定義為“變量”。在有的書(shū)上，“®”也用“：”表示：這

31、種表示方法也稱巴科斯范式。2.4.2 超前搜索 在某些語(yǔ)言中，要識(shí)別一個(gè)單詞符號(hào)必須超前看若干字符。2.4.3 LEX的實(shí)現(xiàn) LEX的編譯程序旨在將一個(gè)LEX源程序改造為一個(gè)詞法分析器L，這個(gè)詞法分析器L將像有限自動(dòng)機(jī)那樣工作。相關(guān)介紹：人們已建立了多種編制部分編譯程序或整個(gè)編譯程序的有效工具。有些能用于自動(dòng)產(chǎn)生掃描器(如LEX)，有些可用于自動(dòng)產(chǎn)生語(yǔ)法分析器(如YACC)，有些甚至可用來(lái)自動(dòng)產(chǎn)生整個(gè)的編譯程序。這些構(gòu)造編譯程序的工具稱為編譯程序編譯程序、編譯程序產(chǎn)生器或翻譯程序書(shū)寫(xiě)系統(tǒng)，它們是按對(duì)源程序和目標(biāo)語(yǔ)言(或機(jī)器)的形式描述(作為輸入數(shù)據(jù))而自動(dòng)產(chǎn)生編譯程序的。授課題目（教學(xué)章、節(jié)或

32、主題）：第三章 語(yǔ)法分析-上下文無(wú)關(guān)文法、形式語(yǔ)言和文法課時(shí)安排6授課時(shí)間 第3周 第3-6節(jié) 第4周 第1、2節(jié) 教學(xué)目的、要求（分掌握、熟悉、了解三個(gè)層次）：理解和定義上下文無(wú)關(guān)文法，為學(xué)習(xí)和構(gòu)造編譯程序打下良好基礎(chǔ)。理解語(yǔ)言和文法的定義掌握文法的等價(jià)變換及語(yǔ)法描述方法了解文法的分類教學(xué)重點(diǎn)和難點(diǎn)：文法的直觀概念、文法和語(yǔ)言的形式定義、文法的類型、語(yǔ)法樹(shù)和二義性、文法中的實(shí)用限制、句型的分析授課類型（請(qǐng)打）：理論課þ 討論課 實(shí)驗(yàn)課 練習(xí)課þ 其他教學(xué)方式（請(qǐng)打）：講授þ 討論 示教 指導(dǎo)þ 其他教學(xué)資源（請(qǐng)打）：多媒體þ 模型 實(shí)物 掛圖

33、 音像 其他討論、思考題、作業(yè)：P36：6，8，11教學(xué)內(nèi)容 上下文無(wú)關(guān)文法 箭頭->讀為“定義為”，直豎|讀為“或”，它們是元語(yǔ)言符號(hào)。在后面的討論中，根據(jù)不同情況，我們將用大寫(xiě)字母A、B、C或漢語(yǔ)詞組(如，算術(shù)表達(dá)式)代表非終結(jié)符號(hào)，特別是用小寫(xiě)字母a、b、c代表終結(jié)符，用、等代表由終結(jié)符和非終結(jié)符組成的符號(hào)串。為簡(jiǎn)便起見(jiàn)，當(dāng)引用具體的文法例子時(shí)，僅列出產(chǎn)生式和指出開(kāi)始符號(hào)。 例如，下面是一個(gè)上下文無(wú)關(guān)文法：E->i|EAEA->+|*其中，E、A是非終結(jié)符，E是開(kāi)始符號(hào)，而i、+和*是終結(jié)符。一個(gè)上下文無(wú)關(guān)文法如何定義一個(gè)語(yǔ)言呢?其中心思想是，從文法的開(kāi)始符號(hào)出發(fā)，反復(fù)

34、連續(xù)使用產(chǎn)生式，對(duì)非終結(jié)符施行替換和展開(kāi)。例如，我們考慮下面的文法G: E->E十E | E*E | (E) |i 其中，唯一的非終結(jié)符E可以看成是代表一類算術(shù)表達(dá)式。我們可以從E出發(fā)，進(jìn)行一系列的推導(dǎo)，推出種種不同的算術(shù)表達(dá)式來(lái)。例如，根據(jù)規(guī)則E一>(E)我們可以說(shuō)：從E可直接(一步地)推出(E)。與前面一樣，我們用Þ表示“直接推出”，這樣，這句話就可表示為:EÞ(E)。若對(duì)(E)中的E使用規(guī)則E->E+E，就有(E)Þ(E+E)。即，從(E)可直接推出(E+E)。把上述這兩步合并起來(lái)，就有EÞ(E)Þ(E+E)。再對(duì)(E+

35、E)中的E相繼兩次使用規(guī)則E->i之后，我們就有(E) Þ(E+E)Þ(i+E)Þ(i+i)。我們稱這樣的一串替換序列是從E推出(i+i)的一個(gè)推導(dǎo)。這個(gè)推導(dǎo)提供了一個(gè)證明，證明(i+i)是文法(2.1)所定義的一個(gè)算術(shù)表達(dá)式。注意，推導(dǎo)每前進(jìn)一步總是引用一條規(guī)則(產(chǎn)生式),而符號(hào)Þ指僅推導(dǎo)一步的意思。我們可以用一種圖示化的方法來(lái)表示這種推導(dǎo)，如下圖2.1，說(shuō)明He gave me a book是一個(gè)語(yǔ)法正確的句子。這種圖形表示稱為語(yǔ)法分析樹(shù)。定義 “he gave me a book”這個(gè)英文句子的規(guī)則可以說(shuō)就是一個(gè)上下文無(wú)關(guān)文法。其中，He，m

36、e，book，gave，a等，稱為終結(jié)符號(hào)；<句子>、<主語(yǔ)>、<謂語(yǔ)>、<動(dòng)詞>、<代詞>等，稱為非終結(jié)符號(hào)；這個(gè)文法最終是要定義<句子>的語(yǔ)法結(jié)構(gòu)，所以<句子>在這里稱為開(kāi)始符號(hào)；<間接賓語(yǔ)>-><冠詞><名詞>這種書(shū)寫(xiě)形式稱為產(chǎn)生式。歸納起來(lái)，一個(gè)上下文無(wú)關(guān)文法C包括四個(gè)組成部分：一組終結(jié)符號(hào)，一組非終結(jié)符號(hào)，一個(gè)開(kāi)始符號(hào)，以及一組產(chǎn)生式。 所謂終結(jié)符號(hào)乃是組成語(yǔ)言的基本符號(hào)，在程序語(yǔ)言中就是以前屢次提到的單詞符號(hào)，如基本字、標(biāo)識(shí)符、常數(shù)、算符和界符等。從語(yǔ)法分析

37、的角度來(lái)看，終結(jié)符號(hào)是一個(gè)語(yǔ)言的不可再分的基本符號(hào)。<句子><主語(yǔ)><謂語(yǔ)><形容詞><名詞><動(dòng)詞><賓語(yǔ)><形容詞><名詞> hegavemeabook圖2.1語(yǔ)法樹(shù)非終結(jié)符號(hào)(也稱語(yǔ)法變量)用來(lái)代表語(yǔ)法范疇。例如，“算術(shù)表達(dá)式”、“布爾表達(dá)式”、“賦值句”、“分程序”、“過(guò)程”等，它們都是現(xiàn)今程序語(yǔ)言常見(jiàn)的語(yǔ)法范疇。我們也可以說(shuō)，一個(gè)非終結(jié)符代表一個(gè)一定的語(yǔ)法概念。因此，一個(gè)非終結(jié)符是一個(gè)類(或集合)記號(hào)，而不是一個(gè)個(gè)體記號(hào)。例如，“算術(shù)表達(dá)式”這個(gè)非終結(jié)符乃代表一定算術(shù)式組成的類

38、。因而，也可以說(shuō)，每個(gè)非終結(jié)符號(hào)表示一定符號(hào)串的集合(由終結(jié)符號(hào)和非終結(jié)符號(hào)組成的符號(hào)串)。開(kāi)始符號(hào)是一個(gè)特殊的非終結(jié)符號(hào)，它代表所定義的語(yǔ)言中我們最終感興趣的語(yǔ)法范疇，這個(gè)語(yǔ)法范疇通常稱為“句子”。但在程序語(yǔ)言中，我們最終感興趣的是“程序”這個(gè)語(yǔ)法范疇，而其它的語(yǔ)法范疇都只不過(guò)是構(gòu)造“程序”的一塊塊磚石。 語(yǔ)法分析樹(shù)與二義性 前面我們提到過(guò)可以用一張圖表示一個(gè)句型的推導(dǎo)，這種表示稱為語(yǔ)法分析樹(shù)，或簡(jiǎn)稱為語(yǔ)法樹(shù)。語(yǔ)法樹(shù)有助于理解一個(gè)句子語(yǔ)法結(jié)構(gòu)的層次。語(yǔ)法樹(shù)通常表示成一棵倒立的樹(shù)，根在上，枝葉在下。語(yǔ)法樹(shù)的根結(jié)由開(kāi)始符號(hào)所標(biāo)記。隨著推導(dǎo)的展開(kāi)，當(dāng)某個(gè)非終結(jié)符被它的某個(gè)候選式所替換時(shí)，這個(gè)非終結(jié)

39、符的相應(yīng)結(jié)就產(chǎn)生出下一代新結(jié)，候選式中自左至右的每個(gè)符號(hào)對(duì)應(yīng)一個(gè)新結(jié)，并用這些符號(hào)標(biāo)記其相應(yīng)的新結(jié)。每個(gè)新結(jié)和其父結(jié)間都有一條連線。在一棵語(yǔ)法樹(shù)生長(zhǎng)過(guò)程中的任何時(shí)刻，所有那些沒(méi)有后代的端末結(jié)自左至右排列起來(lái)就是一個(gè)句型。例如，對(duì)于文法(2.1)，關(guān)于(i*i+i)的推導(dǎo)(2.2)的語(yǔ)法樹(shù)如圖2.2所示。圖2.2 語(yǔ)法樹(shù)這就是說(shuō)，一棵語(yǔ)法樹(shù)表示了一個(gè)句型種種可能的(但未必是所有的)不同推導(dǎo)過(guò)程，包括最左(最右)推導(dǎo)。這樣的一棵語(yǔ)法樹(shù)是這些不同推導(dǎo)過(guò)程的共性抽象，是它們的代表。如果我們堅(jiān)持使用最左(最右)推導(dǎo)，那么，一棵語(yǔ)法樹(shù)就完全等價(jià)于一個(gè)最左(最右)推導(dǎo)，這種等價(jià)性包括樹(shù)的步步成長(zhǎng)和推導(dǎo)的步步

40、展開(kāi)之間的完全一致性。但是，一個(gè)句型是否只對(duì)應(yīng)唯一的一棵語(yǔ)法樹(shù)呢?也就是，它是否只有唯一的一個(gè)最左(最右)推導(dǎo)呢?不盡然。 形式語(yǔ)言鳥(niǎo)瞰 前面喬姆斯基把文法分成四種類型，即0型，1型，2型，和3型。0型強(qiáng)于1型，1型強(qiáng)于2型，2型強(qiáng)于3型。這幾類文法的差別在于對(duì)產(chǎn)生式施加不同的限制。 0型文法：也稱短語(yǔ)文法，其能力相當(dāng)于圖靈機(jī)。任何0型語(yǔ)言都是遞歸可枚舉的，反之，遞歸可枚舉集必定是一個(gè)0型語(yǔ)言。 1型文法：也稱上下文有關(guān)文法，對(duì)非終結(jié)符進(jìn)行替換時(shí)務(wù)必聯(lián)系上下文，并且一般不允許替換成空串。 2型文法：也稱上下文無(wú)關(guān)文法 3型文法：也稱右線性文法，這類文法等價(jià)于正規(guī)式，所以也稱正規(guī)文法。只有下面兩

41、種形式的產(chǎn)生式：ABa 或Aa。文法等價(jià)的概念： 若L(G1)=L(G2),則稱文法G1和G2是等價(jià)的例如：下列兩個(gè)文法是等價(jià)的G1A: A 0R A 01 R A1G2A：S 0S1 S 01因?yàn)長(zhǎng)(G1)=L(G2)=0n1n|n 1定義：對(duì)文法進(jìn)行變換，使變換后的文法滿足某種要求并于原文法等價(jià)，這種變換成為文法的等價(jià)變換。、增廣文法定義：設(shè)文法GS=VN,VT,P,S，構(gòu)造文法GS=(VNS,VT,P,S),其中，P=A |A PS S,顯然L(G)= L(G)，稱G為文法G的增廣文法。例：Z:Z abZA|a Ab經(jīng)等價(jià)變換后可得到增廣文法GA: Z Z Z abZA|a Ab、提取左

42、因子定義：若文法中有產(chǎn)生式P1|2|n,則稱該文發(fā)含有左因子。其中P VN ，1，2 n (VN VT)*。例：文法S: S iEtS|iEtSeS|a E b提取左因子該文法變?yōu)椋?GS: S iEtSS|a S eS| E b、消除左遞歸定義：若文法中存在推導(dǎo)：P Þ+ P,則稱該文法含有左遞歸。若存在產(chǎn)生式P Þ P,則稱該文法含有直接左遞歸。若存在產(chǎn)生式P Þ P1，P1 ÞP2, ,Pn-1 ÞPn，Pn Þ P,則稱該文法含有間接左遞歸。其中P,P1, ,Pn VN, , , , (VN VT)*。直接左遞歸的消除方法：假

43、設(shè)非終結(jié)符P存在產(chǎn)生式P ÞP|刪除左遞歸產(chǎn)生式P ÞP引入新的非終結(jié)符P消除文法中的左遞歸，得： P ÞP P ÞP|間接左遞歸的消除方法：將間接左遞歸轉(zhuǎn)化為直接左遞歸；消除直接左遞歸；化簡(jiǎn)文法，刪除含有從起始符號(hào)無(wú)法到達(dá)的非終結(jié)符的產(chǎn)生式最后，作為描述程序語(yǔ)言的上下文無(wú)關(guān)文法，我們對(duì)它有幾點(diǎn)限制。 （1）文法中不含任何下面形式的產(chǎn)生式： PP因?yàn)檫@種產(chǎn)生式除了產(chǎn)生二義性外沒(méi)有任何用處。（2）每個(gè)非終結(jié)符P必須有用處。這一方面意味著，必須存在含P的句型；也就是，從開(kāi)始符號(hào)出發(fā)，存在推導(dǎo) SÞ*aPb. 另一方面意味著，必須存在終結(jié)符串g

44、06;VT*,使得PÞ+g；也就是，對(duì)于P不存在永不終結(jié)的回路。 我們以后所討論的文法均假定滿足上述兩條件。授課題目（教學(xué)章、節(jié)或主題）：第三章 語(yǔ)法分析自上而下分析課時(shí)安排12授課時(shí)間 第4周 第3-6節(jié) 第6周 第1-6節(jié) 第7周 第1-2節(jié) 教學(xué)目的、要求（分掌握、熟悉、了解三個(gè)層次）：了解確定的自頂向下分析思想熟悉某些非LL（1）文法到LL（1）文法的等價(jià)變換掌握LL（1）文法的判別、確定的自頂向下分析方法教學(xué)重點(diǎn)和難點(diǎn)：語(yǔ)法分析器的功能、確定的自頂向下分析思想、LL（1）文法的判別、某些非LL（1）文法到LL（1）文法的等價(jià)變換、不確定的自頂向下分析思想、確定的自頂向下分析

45、方法授課類型（請(qǐng)打）：理論課þ 討論課 實(shí)驗(yàn)課þ 練習(xí)課þ 其他教學(xué)方式（請(qǐng)打）：講授þ 討論 示教 指導(dǎo)þ 其他教學(xué)資源（請(qǐng)打）：多媒體þ 模型 實(shí)物 掛圖 音像 其他討論、思考題、作業(yè)：P81：1，2，4教學(xué)內(nèi)容第三章 語(yǔ)法分析自上而下分析3.1 語(yǔ)法分析器的功能 語(yǔ)法分析器：是這樣的一個(gè)程序，它將按文法的產(chǎn)生式，識(shí)別輸入符號(hào)串是否為一個(gè)句子。輸入串是指由單詞符號(hào)（文法的終結(jié)符）組成的有限序列。語(yǔ)法分析的方法：可大致分為兩類，一類是自下而上分析法，另一類是自上而下分析法。所謂自下而上分析法就是從輸入串開(kāi)始，逐步進(jìn)行“歸約”，直至歸

46、約到文法的開(kāi)始符號(hào)。自上而下分析過(guò)程恰好與此相反，它從文法的開(kāi)始符號(hào)出發(fā)，反復(fù)使用各種產(chǎn)生式，尋找“匹配”于輸入串的推導(dǎo)。3.2 自上而下分析面臨的問(wèn)題 本節(jié)主要是通過(guò)例子使我們認(rèn)識(shí)到，作自上而下分析所遇到的主要困難是語(yǔ)法的左遞歸性使分析陷入無(wú)限循環(huán)；回溯的不確定性，要求我們將已經(jīng)完成工作推倒重來(lái)，為解決這些問(wèn)題我們要消除左遞歸和消除回溯。3.3 LL(1)分析法 自上而下分析方法不允許文法含有任何左遞歸。為構(gòu)造不帶回溯的自上而下分析算法，首先要消除文法的左遞歸性，并找出克服回溯的充分必要條件。3.3.1 左遞歸的消除 假定關(guān)于非終結(jié)符P的規(guī)則為 :P-> P| 其中，每個(gè) 都不以P開(kāi)頭

47、，那么我們可以把P的規(guī)則改寫(xiě)成如下的非直接左遞歸形式：p -p'p'- p'|( 為空字)這種形式和原來(lái)的形式是等價(jià)的，也就是說(shuō)，從P推出的符號(hào)串是相同的。3.3.2 消除回溯、提左因子 我們首先來(lái)看一下在不得回溯的情況下對(duì)于文法有什么要求。前面已經(jīng)說(shuō)過(guò)，欲實(shí)行自上而下的分析，文法不得含左遞歸。令G是一個(gè)不含左遞歸的文法，對(duì)G 的所有的非終結(jié)符號(hào)的每個(gè)候選a定義它的終結(jié)首符集FIRST(a)為： FIRST(a)=a|aÞ*a,aÎVT特別是，若aÞ*，則規(guī)定ÎFIRST(a)。換句話說(shuō)FIRST(a)是a的所有可能推導(dǎo)的開(kāi)頭終結(jié)

48、符或可能的。如果非終結(jié)符A的所有候選首符集兩兩不相交，即A的任何兩個(gè)不同的候選ai和aj FIRST(ai)ÇFIRST(aj) = f那么，當(dāng)要求A匹配輸入串時(shí)，A 就能根據(jù)它所面臨的第一個(gè)輸入符號(hào)a，準(zhǔn)確地指派某個(gè)候選前去執(zhí)行任務(wù)。這個(gè)候選就是那個(gè)終結(jié)首符集含a的a。如何把一個(gè)文法改造成任何終結(jié)首符集的所有候選首符集兩兩不相交呢？其辦法是提取公共左因子。例如，假定關(guān)于A 的規(guī)則是 A®db1|db2|dbn|g1|g2| |gm （其中每個(gè)g不以d開(kāi)頭）那么，可以把這些規(guī)則改寫(xiě)成：A®dA|g1|g2| |gmA®|b1|b2|bn 3.3.3 LL

49、(1)分析條件 假定S是文法G的開(kāi)始符號(hào)，對(duì)于任何非終結(jié)符A我們定義： FOLLOW(A) = a | SÞ*Aa,aÎVT特別是，若SÞ*A， 則規(guī)定#ÎFOLLOW(A). 也就是說(shuō)，F(xiàn)OLLOW(A)是所有句型中出現(xiàn)在緊接A之后的終結(jié)符或者#。判斷某給定文法是否為L(zhǎng)L(1)文法其條件為： （1）文法不含左遞歸。 （2）對(duì)于文法中每個(gè)非終結(jié)符A的各個(gè)產(chǎn)生式的候選首符集兩兩不相交。即，若 A®a1 | a2 | an 則： FIRST(ai)ÇFIRST(aj) = f（i¹j ） (3) 對(duì)文法中每一個(gè)終結(jié)符A，若它存在

50、某個(gè)候選首符集包含，則 FIRST(A) ÇFLLOW(A)= f一個(gè)文法若滿足以上條件，則稱該文法G為L(zhǎng)L(1)文法3.4 遞歸下降分析程序構(gòu)造 在不含左遞歸和每個(gè)非終結(jié)符的所有候選終結(jié)首符集都兩兩不相交的條件下，可能（僅是可能）構(gòu)造一個(gè)不帶回溯的自上而下分析程序. 文法如下：E-> TE E-> +TE/T-> FT T-> *FT/F-> （E）/i 當(dāng)一個(gè)文法滿足LL(1)條件時(shí)，我們就可以為它構(gòu)造一個(gè)不帶回溯的自上而下分析程序，這個(gè)分析程序是由一組遞歸過(guò)程組成的，每個(gè)過(guò)程對(duì)應(yīng)文法的一個(gè)非終結(jié)符。這樣的一個(gè)分析程序稱為遞歸下降分析器。3.5 預(yù)測(cè)

51、分析程序 用高級(jí)語(yǔ)言的遞歸過(guò)程描述遞歸下降分析器只有當(dāng)具有實(shí)現(xiàn)這種過(guò)程的編譯系統(tǒng)剛才有實(shí)際意義。實(shí)現(xiàn)LL(1)分析的另一種有效方法是使用一張分析表和一個(gè)棧進(jìn)行聯(lián)合控制。我們現(xiàn)在要介紹的預(yù)測(cè)分析程序就是屬于這種類型的LL(1)分析器3.5.1 預(yù)測(cè)分析程序工作過(guò)程 預(yù)測(cè)分析程序的總控程序在任何時(shí)候都是按STACK棧頂符號(hào)X和當(dāng)前的輸入符號(hào)a行事的。3.5.2 預(yù)測(cè)分析表的構(gòu)造 為了構(gòu)造預(yù)測(cè)分析表M，我們需要先構(gòu)造與文法G有關(guān)的集合FIRST和FOLLOW. 消除左遞歸和提取左因子將有助于獲得無(wú)多重定義的分析表M。 可以證明，一個(gè)文法G的預(yù)測(cè)分析表M不含多重定義入口，當(dāng)且僅當(dāng)該文法為L(zhǎng)L(1)的。

52、3.6 LL(1)分析中的錯(cuò)誤處理 我們以預(yù)測(cè)分析為例。在預(yù)測(cè)分析過(guò)程中，出現(xiàn)了下列兩種情況，則說(shuō)明遇到了語(yǔ)法錯(cuò)誤。(1)棧頂?shù)慕K結(jié)符與當(dāng)前的輸入符號(hào)不匹配。(2)非終結(jié)符A處于棧頂，面臨的輸入符號(hào)為a，但分析表M中的MIA，a為空。發(fā)現(xiàn)錯(cuò)誤后，要盡快地從錯(cuò)誤中恢復(fù)過(guò)來(lái)，使分析能繼續(xù)進(jìn)行下去。基本的做法就是跳過(guò)輸入串中的一些符號(hào)直至遇到“同步符號(hào)”為止。這種做法的效果有賴于同步符號(hào)集的選擇。我們可以從以下幾個(gè)方面考慮同步符號(hào)集的選擇。(1)把FOLLOW(A)中的所有符號(hào)放人非終結(jié)符A的同步符號(hào)集。如果我們跳讀一些輸入符號(hào)直到出現(xiàn)FOLLOW(A)中的符號(hào)，把A從棧中彈出，這樣就可能使分析繼續(xù)

53、下去。(2)對(duì)于非終結(jié)符A來(lái)說(shuō)，只用FOLLOW(A)作為它的同步符號(hào)集是不夠的。例如，如果分號(hào)作為語(yǔ)句的結(jié)束符(C語(yǔ)言中就是這樣的)，那么作為語(yǔ)句開(kāi)頭的關(guān)鍵字就可能不在產(chǎn)生表達(dá)式的非終結(jié)符的FOLIDW集中。這樣，在一個(gè)賦值語(yǔ)句后少一個(gè)分號(hào)就可能導(dǎo)致作為下一語(yǔ)句開(kāi)頭的關(guān)鍵字被跳過(guò)。(3)如果把FIRST(A)中的符號(hào)加入非終結(jié)符A的同步符號(hào)集，那么，當(dāng)FIRST(A)中的一個(gè)符號(hào)在輸人中出現(xiàn)時(shí)，可以根據(jù)A恢復(fù)語(yǔ)法分析。(4)如果一個(gè)非終結(jié)符產(chǎn)生空串，那么，推導(dǎo)6的產(chǎn)生式可以作為缺省的情況，這樣做可以推遲某些錯(cuò)誤檢查，但不能導(dǎo)致放棄一個(gè)錯(cuò)誤。這種方法減少在錯(cuò)誤恢復(fù)期間必須考慮的非終結(jié)符數(shù)。(5

54、)如果不能匹配棧頂?shù)慕K結(jié)符號(hào)，一種簡(jiǎn)單的想法是彈出棧頂?shù)倪@個(gè)終結(jié)符號(hào)，并發(fā)出一條信息，說(shuō)明已經(jīng)插入這個(gè)終結(jié)符，繼續(xù)進(jìn)行語(yǔ)法分析。結(jié)果，這種方法使一個(gè)單詞符號(hào)的同步符號(hào)集包含所有其它單詞符號(hào)。授課題目（教學(xué)章、節(jié)或主題）：第三章 語(yǔ)法分析自下而上分析課時(shí)安排16授課時(shí)間 第7周 第3-4節(jié)第8周 第1-4節(jié) 第9周 第1-4節(jié)第10周 第1-4節(jié)第11周 第1-2節(jié)教學(xué)目的、要求（分掌握、熟悉、了解三個(gè)層次）：熟悉自下而上分析思想了解算符優(yōu)先分析法掌握LR分析法教學(xué)重點(diǎn)和難點(diǎn)：自下而上分析思想、算符優(yōu)先分析法、LR分析法授課類型（請(qǐng)打）：理論課þ 討論課 實(shí)驗(yàn)課þ 練習(xí)課&#

55、254; 其他教學(xué)方式（請(qǐng)打）：講授þ 討論 示教 指導(dǎo)þ 其他教學(xué)資源（請(qǐng)打）：多媒體þ 模型 實(shí)物 掛圖 音像 其他討論、思考題、作業(yè)：P133：1，2，3，5教學(xué)內(nèi)容第三章 語(yǔ)法分析程序-自下而上分析所謂自下而上分析法就是從輸入串開(kāi)始，逐步進(jìn)行“歸約”，直至歸約到文法的開(kāi)始符號(hào)；或者說(shuō)從語(yǔ)法樹(shù)的末端開(kāi)始，步步向上“歸約”，直到根結(jié)。5.1 自下而上分析基本問(wèn)題 我們首先討論自下而上分析法的基本思想和基本概念 3.1.1 歸約 “移進(jìn)-歸約”：用一個(gè)寄存符號(hào)的先進(jìn)后出棧，把輸入符號(hào)一個(gè)一個(gè)地移進(jìn)到棧里，當(dāng)棧頂形成某個(gè)產(chǎn)生式的一個(gè)候選式時(shí)，即把棧頂?shù)倪@一部分替換

56、（歸約為）該產(chǎn)生式的左部符號(hào)。我們可用句柄來(lái)刻畫(huà)移進(jìn)歸約過(guò)程的“可歸約串”。3.1.2 規(guī)范歸約簡(jiǎn)述 規(guī)范規(guī)約是關(guān)于的一個(gè)最右推導(dǎo)的逆過(guò)程。因此，規(guī)范規(guī)約也稱最左規(guī)約。最右推導(dǎo)常被稱為規(guī)范推導(dǎo)。由規(guī)范推導(dǎo)所得的句型稱為規(guī)范句型。如果文法G是無(wú)二義的，那么規(guī)范推導(dǎo)的逆過(guò)程必是規(guī)范規(guī)約。 句柄：令G是一個(gè)文法，S是文法的開(kāi)始符號(hào)，假定是文法G的一個(gè)句型，如果有SÞ*A且AÞ則稱是句型相對(duì)于非終結(jié)符A的短語(yǔ)。特別是，如果有AÞ則稱是句型相對(duì)于規(guī)則A®b的直接短語(yǔ)。一個(gè)句型的最左直接短語(yǔ)稱為該句型的句柄。3.1.3 符號(hào)棧的使用與語(yǔ)法樹(shù)的表示 在形式語(yǔ)言中，最右推導(dǎo)常被稱為規(guī)范推導(dǎo)。由規(guī)范推導(dǎo)所得的句型稱為規(guī)范句型。如果文法G是無(wú)二義的，那么，規(guī)范推導(dǎo)(最右推導(dǎo))的逆過(guò)程必是規(guī)范歸約