《編譯原理》教案設(shè)計(jì)

《編譯原理》教案

授課題目（教學(xué)章、節(jié)或主題）：課時(shí)支配2

第一章引論

授課時(shí)間第1周第1、2節(jié)

教學(xué)目的、要求（分駕馭、熟識(shí)、了解三個(gè)層次）：

簡(jiǎn)潔介紹學(xué)習(xí)此課程的目的和要求

初步了解編譯技術(shù)的基本原理和方法

熟識(shí)Compiler的基本概念

駕馭Compiler的結(jié)構(gòu)和功能

教學(xué)重點(diǎn)和難點(diǎn)：編譯程序的基本結(jié)構(gòu)和功能

授課類型（請(qǐng)打J）：理論課目探討課口試驗(yàn)課口練習(xí)課口其他口

教學(xué)方式（請(qǐng)打J）：講授I3探討口示教口指導(dǎo)因其他口

教學(xué)資源（請(qǐng)打J）：多媒體因模型口實(shí)物口掛圖口音像口其他口

探討、思索題、作業(yè)：

編譯程序的基本結(jié)構(gòu)如何？各部分功能？

教學(xué)內(nèi)容

0課程學(xué)習(xí)的要求及任務(wù)，學(xué)習(xí)方法介紹，成果考核標(biāo)準(zhǔn)。

第一章引論

1.1什么叫編譯程序？

通常所說的翻譯程序是指這樣的一個(gè)程序，它能夠把某一種語言程序（稱為源語

言程序）轉(zhuǎn)換成另一種語言程序（稱為目標(biāo)語言程序），而后者與前者在邏輯上是

等價(jià)的。假如源語言是諸如FORTRAN、Pascal.C、Ada、SmaIItaIk或Java這

樣的“高級(jí)語言”，而目標(biāo)語言是諸如匯編語言或機(jī)器語言之類的“低級(jí)語言”，

這樣的一個(gè)翻譯程序就稱為編譯程序。

高級(jí)語言程序除了像上面所說的先編譯后執(zhí)行外，有時(shí)也可“說明”執(zhí)行。一個(gè)

源語言的說明程序是這樣的程序，它以該語言寫的源程序作為輸入，但不產(chǎn)生目

標(biāo)程序，而是邊說明邊執(zhí)行源程序本身。本書將不對(duì)說明程序作特地的探討。

事實(shí)上，很多編譯程序的構(gòu)造與實(shí)現(xiàn)技術(shù)同樣適用于說明程序。

依據(jù)不同的用途和側(cè)重，編譯程序還可進(jìn)一步分類。特地用于幫助程序開發(fā)和

調(diào)試的編譯程序稱為診斷編譯程序（DiagnosticC。叩iler）,著重于提高目標(biāo)代

碼效率的編譯程序叫優(yōu)化編譯程序（OptimizingCompiIer）,,現(xiàn)在很多編譯程序

同時(shí)供應(yīng)了調(diào)試、優(yōu)化等多種功能，用戶可以通過“開關(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ī)器代碼，則稱它為交叉編譯程序

（CrOSSC。叩iler）。假如不需重寫編譯程序中與機(jī)器無關(guān)的部分就能變更目標(biāo)

機(jī)，則稱該編譯程序?yàn)榭勺兡繕?biāo)編譯程序（RetargetabIeCompiIer）o

1.2編譯過程概述

編譯程序過程：從輸入源程序起先到輸出目標(biāo)程序?yàn)橹沟恼麄€(gè)編譯過程可分為

以下五個(gè)階段：詞法分析，語法分析，語義分析，中間代碼產(chǎn)生，優(yōu)化和目標(biāo)代碼生

成.

1.3編譯程序的結(jié)構(gòu)

編譯程序的結(jié)構(gòu)可以依據(jù)從輸入源程序起先到輸出目標(biāo)程序?yàn)橹沟恼麄€(gè)編譯過

程可分為以下五個(gè)階段：詞法分析，語法分析，語義分析，中間代碼產(chǎn)生，優(yōu)化和目

標(biāo)代碼生成。

1.3.1編譯程序總框

編譯程序的結(jié)構(gòu)可以依據(jù)這五個(gè)階段的任務(wù)分模塊進(jìn)行設(shè)計(jì)。下圖給出了編譯程

序的總框。

日癡2庫(kù)

1.3.2表格與表格管理

編譯程序在工作過程中須要保持一系列的表格，以登記源程序的各類信息和編

譯各階段的進(jìn)展?fàn)顩r。在編譯程序運(yùn)用的表格中，最合理的是符號(hào)表。編譯程

序在工作過程中須要保持一系列的表格，以登記源程序的各類信息和編譯各階段

的進(jìn)展?fàn)顩r。合理地設(shè)計(jì)和運(yùn)用表格是編譯程序構(gòu)造的一個(gè)重要問題。在編譯程

序運(yùn)用的表格中，最重要的是符號(hào)表。它用來登記源程序中出現(xiàn)的每個(gè)名字以及

名字的各種屬性。例如，一個(gè)名字是常量名、變量名，還是過程名等等；假如是

變量名，它的類型是什么、所占內(nèi)存是多大、地址是什么等等。通常，編譯程序

在處理到名字的定義性出現(xiàn)時(shí)，要把名字的各種屬性填入到符號(hào)表中；當(dāng)處理到

名字的運(yùn)用性出現(xiàn)時(shí)，要對(duì)名字的屬性進(jìn)行查證。

當(dāng)掃描器識(shí)別出一個(gè)名字（標(biāo)識(shí)符）后，它把該名字填人到符號(hào)表中。但這時(shí)不能

完全確定名字的屬性，它的各種屬性要在后續(xù)的各階段才能填入。例如，名字的

類型等要在語義分析時(shí)才能確定，而名字的地址可能要到目標(biāo)代碼生成才能確

定。

由此可見，編譯各階段都涉及到構(gòu)造、查找或更新有關(guān)的表格。

1.3.3出錯(cuò)處理

遍:是對(duì)源程序或源程序的中間結(jié)果從頭到尾掃描一次，并作有關(guān)的加工處理，

生產(chǎn)新的中間結(jié)果或目標(biāo)程序。一個(gè)編譯程序不僅應(yīng)能對(duì)書寫正確的程序進(jìn)行翻

譯，而且應(yīng)能對(duì)出現(xiàn)在源程序中的錯(cuò)誤進(jìn)行處理。假如源程序有錯(cuò)誤，編譯程序

應(yīng)設(shè)法發(fā)覺錯(cuò)誤，把有關(guān)錯(cuò)誤信息報(bào)告給用戶。這部分工作是由特地的一組程序

（叫做出錯(cuò)處理程序）完成的。一個(gè)好的編譯程序應(yīng)能最大限度地發(fā)覺源程序中的

各種錯(cuò)誤，精確地指出錯(cuò)誤的性質(zhì)和發(fā)生錯(cuò)誤的地點(diǎn)，并且能將錯(cuò)誤所造成的影

響限制在盡可能小的范圍內(nèi)，使得源程序的其余部分能接著被編譯下去，以便進(jìn)

一步發(fā)覺其它可能的錯(cuò)誤。假如不僅能夠發(fā)覺錯(cuò)誤，而且還能自動(dòng)校正錯(cuò)、誤，

那當(dāng)然就更好了。但是，自動(dòng)校正錯(cuò)誤的代價(jià)是特別高的。

編譯過程的每一階段都可能檢測(cè)出錯(cuò)誤，其中，絕大多數(shù)錯(cuò)誤可以在編譯的前三

階段檢測(cè)出來。源程序中的錯(cuò)誤通常分為語法錯(cuò)誤和語義錯(cuò)誤兩大類。語法錯(cuò)誤

是指源程序中不符合語法（或詞法）規(guī)則的錯(cuò)誤，它們可在詞法分析或語法分析時(shí)

檢測(cè)出來。例如，詞法分析階段能夠檢測(cè)出“非法字符”之類的錯(cuò)誤；語法分析

階段能夠檢測(cè)出諸如“括號(hào)不匹配”、“缺少；”之類的錯(cuò)誤。語義錯(cuò)誤是指源程

序中不符合語義規(guī)則的錯(cuò)誤，這些錯(cuò)誤一般在語義分析時(shí)檢測(cè)出來，有的語義錯(cuò)

誤要在運(yùn)行時(shí)才能檢測(cè)出來。語義錯(cuò)誤通常包括：說明錯(cuò)誤、作用域錯(cuò)誤、類型

不一樣等等。

1.3.4遍

遍:是對(duì)源程序或源程序的中間結(jié)果從頭到尾掃描一次，并作有關(guān)的加工處理，

生產(chǎn)新的中間結(jié)果或目標(biāo)程序。通常，每遍的工作由從外存上獲得的前一遍的中

間結(jié)果起先（對(duì)于第一遍而言，從外存上獲得源程序），完成它所含的有關(guān)工作之

后，再把結(jié)果記錄于外存。既可以將幾個(gè)不同階段合為一遍，也可以把一個(gè)階段

的工作分為若干遍。例如，詞法分析這一階段可以單獨(dú)作為一遍，但更多的時(shí)候

是把它與語法分析合并為一遍；為了便于處理，語法分析和語義分析與中間代碼

產(chǎn)生又經(jīng)常合為一遍。在優(yōu)化要求很高時(shí)，往往還可把優(yōu)化階段分為若干遍來實(shí)

現(xiàn)。

當(dāng)一遍中包含若干階段時(shí)，各階段的工作是穿插進(jìn)行的。例如，我們可以把詞法

分析、語法分析及語義分析與中間代碼產(chǎn)生這三階段支配成一遍。這時(shí)，語法分

析器處于核心位置，當(dāng)它在識(shí)別語法結(jié)構(gòu)而須要下一單詞符號(hào)時(shí)，它就調(diào)用詞法

分析器，一旦識(shí)別出一個(gè)語法單位時(shí)，它就調(diào)用中間代碼產(chǎn)生器，完成相應(yīng)的語

義分析并產(chǎn)生相應(yīng)的中間代碼。

一個(gè)編譯程序原委應(yīng)分成幾遍，如何劃分，是與源語言、設(shè)計(jì)要求、硬件設(shè)備等

諸因素有關(guān)的，因此難于統(tǒng)一劃定。遍數(shù)多一點(diǎn)有個(gè)好處，即整個(gè)編譯程序的邏

輯結(jié)構(gòu)可能清晰一點(diǎn)。但遍數(shù)多勢(shì)必增加輸入/輸出所消耗的時(shí)間。因此，在主

存可能的前提下，一般還是遍數(shù)盡可能少一點(diǎn)為好。應(yīng)當(dāng)留意的是，并不是每種

語言都可以用單遍編譯程序?qū)崿F(xiàn)。

1.3.5編譯前端與后端

概念上，我們有時(shí)把編譯程序劃分為編譯前端和編譯后端。前端主要由與源語言

有關(guān)但與目標(biāo)機(jī)無關(guān)的那些部分組成。這些部分通常包括詞法分析、語法分析、

語義分析與中間代碼產(chǎn)生，有的代碼優(yōu)化工作也可包括在前端。后端包括編譯程

序中與目標(biāo)機(jī)有關(guān)的那些部分，如與目標(biāo)機(jī)有關(guān)的代碼優(yōu)化和目標(biāo)代碼生成等。

通常，后端不依靠于源語言而僅僅依靠于中間語言。

可以取編譯程序的前端，改寫其后端以生成不同目標(biāo)機(jī)上的相同語言的編譯程

序。假如后端的設(shè)計(jì)是經(jīng)過細(xì)心考慮的，那么后端的改寫將用不了太大工作量，

這樣就可實(shí)現(xiàn)編譯程序的目標(biāo)機(jī)變更。也可以設(shè)想將幾種源語言編譯成相同的中

間語言，然后為不同的前端配上相同的后端，這樣就可為同一臺(tái)機(jī)器生成不同語

言的編譯程序。然而，由于不同語言存在某些微妙的區(qū)分，因此在這方面所取得

的成果還特別有限。

為了實(shí)現(xiàn)編譯程序可變更目標(biāo)機(jī)，通常須要有一種定義良好的中間語言支持。例

如.在聞名的Ada程序設(shè)計(jì)環(huán)境APSE中，運(yùn)用的是一種稱為Diana的樹形結(jié)構(gòu)

的中間語言一個(gè)Ada源程序通過前編譯轉(zhuǎn)換為Diana中間代碼，由編譯后端把

Diana中間代碼轉(zhuǎn)換為目標(biāo)代碼。編譯前端與不同的編譯后端以Diana為界面，

實(shí)現(xiàn)編譯程序的目標(biāo)機(jī)變更。

又如，在Java語言環(huán)境中，為了使編譯后的程序從一個(gè)平臺(tái)移到另一個(gè)平臺(tái)，

Java定義一種虛擬機(jī)代碼一Bytecode。只栗實(shí)際運(yùn)用的操作平臺(tái)上實(shí)現(xiàn)了的

Java說明器，這個(gè)操作平臺(tái)就可以執(zhí)行各種Java程序。這就是所謂Java語言

操作平臺(tái)無關(guān)性。

1.4編譯程序與程序設(shè)計(jì)環(huán)境

開發(fā)通常還須要一些其它的工具；如編輯程序、連接程序，調(diào)試工具等等。編譯

程序與這些程序設(shè)計(jì)工具一起構(gòu)成所謂的程序設(shè)計(jì)環(huán)境。

在高級(jí)語言發(fā)展的早期，這些程序設(shè)計(jì)工具往往是獨(dú)立的，缺乏整體性，而且也

缺乏對(duì)軟件開發(fā)全生命周期的支持。隨著軟件技術(shù)的不斷發(fā)展，現(xiàn)在人們?cè)絹碓?/p>

傾向于構(gòu)造集成化的程序設(shè)計(jì)環(huán)境。一個(gè)集成化的程序設(shè)計(jì)環(huán)境的特點(diǎn)是，它將

相互獨(dú)立的程序設(shè)計(jì)工具集成起來，以便為程序員供應(yīng)完整的、一體化的支持，

從而進(jìn)一步提高程序開發(fā)效率，改善程序質(zhì)量。在一個(gè)好的集成化程序設(shè)計(jì)環(huán)境

中，不僅包含豐富的程序設(shè)計(jì)工具，而且還支持程序設(shè)計(jì)方法學(xué)，支持程序開發(fā)

的全生命周期。有代表性的集成化程序設(shè)計(jì)環(huán)境有Ada語言程序設(shè)計(jì)環(huán)境APSE、

LISP語言程序設(shè)計(jì)環(huán)境INTERLISP等。廣闊讀者所熟識(shí)的Pascal.TurboC、

VisuaIC++等語言環(huán)境也都可認(rèn)為是集成化的程序設(shè)計(jì)環(huán)境。

1.5編譯程序的生成

以前人們構(gòu)造編譯程序大多是用機(jī)器語言或匯編語言做工具的。為了發(fā)揮各種不

同硬件系統(tǒng)的效率，為了滿意各種不同的具體要求，現(xiàn)在很多人仍舊采納這種工

具來構(gòu)造編譯程序。但是，越來越多的人傾向于運(yùn)用高級(jí)語言作為工具來構(gòu)造編

譯程序。因?yàn)?，這樣可以節(jié)約大量的程序設(shè)計(jì)時(shí)間，而且所構(gòu)造出來的編譯程序

也易于閱讀、修改和移植。

人們已經(jīng)建立了多種編制部分編譯程序或整個(gè)編譯程序的有效工具。有些能用于

自動(dòng)產(chǎn)生掃描器，有些可用于自動(dòng)產(chǎn)生語法分析器，有些甚至可用來自動(dòng)產(chǎn)生完

全的編譯程序。如：編譯程序-編譯程序、編譯程序產(chǎn)生器、翻譯程序書寫系統(tǒng)

等，它們是依據(jù)對(duì)源語言和目標(biāo)語言（或機(jī)器）的形式描述（作為輸入數(shù)據(jù)）而

自動(dòng)產(chǎn)生編譯程序的。本課程將把自動(dòng)產(chǎn)生器作為一個(gè)重要課題來探討。近些

年來，有些人主見采納“自編譯方式”產(chǎn)生編譯程序。意思是，先對(duì)語言的核心

部分構(gòu)造一個(gè)小小的編譯程序（可用手編實(shí)現(xiàn)），再以它為工具構(gòu)造一個(gè)能夠編

譯更多語言成分的較大編譯程序。如此擴(kuò)展下去，就象滾雪球一樣，越滾越大，

最終形成人們所期望的整個(gè)編譯程序。這種通過一系列自展途徑而形成編譯程序

的過程叫作自編譯過程。

現(xiàn)在，有些編譯程序是通過“移植”得到的。即把某一機(jī)器上的編譯程序移植到

另一機(jī)器上。著須要尋求某種適當(dāng)?shù)摹?中間語言但是，由于建立通用中間語

言事實(shí)上辦不到，因此，移植也只能在幾種語言和幾種機(jī)器之間進(jìn)行。

授課題目（教學(xué)章、節(jié)或主題）：課時(shí)支配12

其次章詞法分析第1周第3-6節(jié)

授課時(shí)間第2周第1-6節(jié)

第3周第1、2節(jié)

教學(xué)目的、要求（分駕馭、熟識(shí)、了解三個(gè)層次）：

了解詞法分析器的構(gòu)造方法

熟識(shí)詞法分析的任務(wù)和過程

駕馭正規(guī)式和有限自動(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)打J）：理論課EI探討課口試驗(yàn)課團(tuán)練習(xí)課13其他口

教學(xué)方式（請(qǐng)打J）：講授因探討口示教口指導(dǎo)因其他口

教學(xué)資源（請(qǐng)打J）：多媒體因模型口實(shí)物口掛圖口音像口其他口

探討、思索題、作業(yè)：

P63：3,6,7,8,12,14

教學(xué)內(nèi)容

其次章詞法分析

2.1對(duì)于詞法分析器的要求

首先探討詞法分析器輸出的單詞符號(hào)的一般形式，然后探討詞法分析器應(yīng)如何和

語法分析器相連接。

2.1.1詞法分析器的功能和輸出形式

詞法分析器的功能是輸入源程序，輸出單詞符號(hào)。單詞符號(hào)是一個(gè)程序語言的基

本語法符號(hào)，程序語言的單詞符號(hào)一般可分為下列五種：

1基本字如FORTRAN中的DIMENSION、IF和DO等等；

2標(biāo)識(shí)符用來表示各種名字，如變量名、數(shù)組名和過程名等等；

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ù)或布爾）分種?；咀挚?/p>

將其全體視為一種，也可以一字一種。運(yùn)算符可采納一符一種的分法，但也可以

把具有肯定共性的算符（如全部關(guān)系符）視為一種。界符一般用一符一種的分法。

假如一個(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ì)

我們將依據(jù)詞法分析的任務(wù)和作為一個(gè)獨(dú)立子程序的要求來考慮詞法分析器的

設(shè)計(jì)。

2.2.1輸入、預(yù)處理

詞法分析器工作的第一步是輸入源程序文本。輸入串一般是放在一個(gè)緩沖區(qū)中，

這個(gè)緩沖區(qū)稱為輸入緩沖區(qū)。詞法分析的工作（單詞符號(hào)的識(shí)別）可以干脆在這

個(gè)緩沖區(qū)中進(jìn)行。但在很多狀況下，把輸入串預(yù)處理一下，對(duì)單詞符號(hào)的識(shí)別工

作將是比較便利的。

預(yù)處理的工作包括：剔除無用的空白、跳格、回車和換行符等編輯性字符；預(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詞法分析器

下面我們來介紹一下單詞符號(hào)識(shí)別的一個(gè)簡(jiǎn)潔方法——超前搜尋。

基本字的識(shí)別有些語言的基本字的輸入表示有特殊標(biāo)記，如加雙引號(hào)（如

“BEGIN"），在這種狀況下，基本字的識(shí)別是很干脆的，不存在什么困難。象

FORTRAN這樣的語言，基本字不加特殊愛護(hù)，基本字和用戶自定義的標(biāo)識(shí)符或

標(biāo)號(hào)之間沒有特殊的界符作間隔，這就使得基本字的識(shí)別甚為麻煬。這里就須要

用到超前搜尋。

2.2.3狀態(tài)轉(zhuǎn)換圖

運(yù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)3o一張轉(zhuǎn)換圖只包含有限個(gè)狀態(tài)（即有限個(gè)結(jié)點(diǎn)），其中

有一個(gè)被認(rèn)為是初態(tài)，而且事實(shí)上至少要有一個(gè)終態(tài)（用雙圈表示）。

2.2.4狀態(tài)轉(zhuǎn)換圖的實(shí)現(xiàn)

一個(gè)狀態(tài)轉(zhuǎn)換圖可用于識(shí)別(或接受)肯定的字符。大多數(shù)程序語言的單詞符號(hào)

都可以用轉(zhuǎn)換圖予以識(shí)別。轉(zhuǎn)換圖特別易于用程序?qū)崿F(xiàn)，最簡(jiǎn)潔的方法是讓每個(gè)

狀態(tài)結(jié)點(diǎn)對(duì)應(yīng)一小段程序。下面我們將引進(jìn)一組全局變量和過程，把它們作為實(shí)

現(xiàn)轉(zhuǎn)換圖的基本成分。這些變量和過程是：

1.CHAR字符變量，存放最新讀進(jìn)的源程序字符。

2.TOKEN字符數(shù)組，存放構(gòu)成單詞符號(hào)的字符串。

3.GETCHAR子程序過程，把下一個(gè)輸入字符讀到CHAR中，把搜尋指示器前

移一字節(jié)位置。

4.GETBC子程序過程，檢查CHAR中的字符是否為空白.若是，則GETCHAR

直到CHAR中進(jìn)入一個(gè)非空白符。

5.CONCAT子程序過程，把CHAR中的字符連接TOKEN之后。例如，TOKEN

原來的值為‘AB',而CHAR中存放著'C',經(jīng)調(diào)用CONCAT后，TOKEN的值就

變?yōu)锳BC。

6.LETTER和DIGIT布爾函數(shù)過程，它們分別CHAR中的字符是否為字母和數(shù)

字，從爾給出真值TRUE或假值FALSEo

7.RESERVE整型函數(shù)過程，對(duì)TOKEN中的字符串查找保留字表，若它是一個(gè)

保留字則返回它的編碼，否則返回0值(假定0不是保留字的編碼)。

8.RETRACT子程序過程，把搜尋指示器回調(diào)一個(gè)字節(jié)位置，把CHAR中的字符

置為空白。

2.3正規(guī)表達(dá)式與有限自動(dòng)機(jī)

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

設(shè)2是一個(gè)有窮字母表，它的每個(gè)元素稱為一個(gè)字符。2上的一個(gè)字(也叫字符

串)是指由W中的字符所構(gòu)成的一個(gè)有窮序列。不包含任何字符的序列稱為空字，

記為E。用Z*表示2上的全部字的全體，空字￡也包括在其中。例如，若Z

={a,b},則￡*={￡1力聲2/1)方2,附/22}下面是正規(guī)式和正規(guī)集的遞歸定義：

1.和①都是上的正規(guī)式，它們所表示的正規(guī)集分別為{￡}和①；

2.任何a62,是Z上的一個(gè)正規(guī)式，它所表示的正規(guī)集為{a};

3.假定U和V都是上的正規(guī)式，它們所表示的正規(guī)集分別記為L(zhǎng)(U)和L(V),

那么，(UV)、(U|V)和(U)*也都是正規(guī)式，它們所表示的正規(guī)集分別為L(zhǎng)(U)

UL(V)、L(U).L(V)(連接積)和(L(U))*(閉包)。

僅由有限次運(yùn)用上述三步驟而定義的表達(dá)式才是2上的正規(guī)式，僅由這些正規(guī)式

所表示的字集才是E上的正規(guī)集。算符的優(yōu)先依次為：先“*”，次最終T。

例如，令W={a,b},下面是W上的正規(guī)式和相應(yīng)的正規(guī)集：

ba*:2上全部以b為首后跟隨意多個(gè)a的字

a(a|b)*:W上全部以a為首的字

(a|b)*(aa|bb)(a|b)*：2上全部含有兩個(gè)相繼的a或兩個(gè)相繼的b的字

又例如，令Z={A,B,0,1},則

(A|B)(A|B|0|l)*:2上的"標(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ī)式，自不待言，下列關(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.eU=Ue=U

2.3.2確定有限自動(dòng)機(jī)(DFA)

設(shè)一個(gè)確定的有限自動(dòng)機(jī)(DFA)M是一個(gè)五元式M=(S,*,f,S0,Z)其中

1.S是一個(gè)有限集，它的每個(gè)元素稱為一個(gè)狀態(tài)；

2.是一個(gè)有窮字母表2,它的每個(gè)元素稱為一個(gè)輸入字符；

3.f是一個(gè)從SXW至S的(單值)部分映照。f(s,a)=C意味著：當(dāng)現(xiàn)行狀態(tài)

為s,輸入字符a時(shí)，將轉(zhuǎn)換到下一狀態(tài)s'o我們把s，稱為s的一個(gè)后繼狀態(tài)；

4.SOeS,是唯一■的一■個(gè)初態(tài)；

5.ZcS,是一個(gè)終態(tài)集(可空)。

一本DFA可用一個(gè)矩陣表示，該矩陣的行表示狀態(tài)，列表示輸入字符，矩陣元

素表示f(s,a)的值，這個(gè)矩陣稱為狀態(tài)轉(zhuǎn)換矩陣。

例如，有DFAM=({0,l,2,3,{a,b,f,0,{3}其中f為：

f(0,a)=lf(0,b)=2

f(l,a)=3f(4,b)=2

f(2,a)=lf(2,b)=3

f(3,a)=3f(3,b)=3

則對(duì)應(yīng)的狀態(tài)轉(zhuǎn)換矩陣如下表3.2所示：

表3.2狀態(tài)轉(zhuǎn)換矩陣

狀態(tài)ab

012

132

213

333

一個(gè)DFA也可以表示成一張(確定的)狀態(tài)轉(zhuǎn)換圖。

對(duì)于2*中的任何字a,若存在一條從初態(tài)結(jié)到某一條終態(tài)結(jié)的道路，且這條路上

全部弧的標(biāo)記符連接成的字等于a,則稱a可為DFAM所識(shí)別(讀出或接受)。

若M的初態(tài)結(jié)同時(shí)又是終態(tài)結(jié)，則空字E可為M所識(shí)別(或接受)。

上例所定義的DFAM相應(yīng)的狀態(tài)轉(zhuǎn)換圖如下所示：它能識(shí)別2上全部含有相繼

兩個(gè)a或相繼兩個(gè)b的字。

圖3.5狀態(tài)轉(zhuǎn)換圖

2.3.3非確定有限自動(dòng)機(jī)(NFA)

設(shè)一個(gè)確定的有限自動(dòng)機(jī)(DFA)M是一個(gè)五元式M=(S,Z,f,SO,Z)其中

1.S是一個(gè)有限集，它的每個(gè)元素稱為一個(gè)狀態(tài)；

2.2是一個(gè)有窮字母表，它的每個(gè)元素稱為一個(gè)輸入字符；

3.f是一個(gè)從SX2*到S的子集的映照，即f:SX2*f2S

4.SOcS,是非空初態(tài)集；

5.ZcS,是一個(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ī)

(FA)M,使得L(M)=L(G)o

(2)對(duì)每一個(gè)FAM,都存在一個(gè)右線性正規(guī)文法GR或左線性正規(guī)文法GL,

使得L(M)=L(GR)=L(GL)

2.3.5正規(guī)式與有限自動(dòng)機(jī)的等價(jià)性

我們可以證明：

(1)對(duì)任何FAM,都存在一個(gè)正規(guī)式r,使得L(r)=L(M)。

(2)對(duì)任何的正規(guī)式r,都存在一個(gè)FAM,使得L(M)=L(r)。

上述結(jié)論加上前面章節(jié)所證明的結(jié)論，說明正規(guī)文法、正規(guī)式、確定有限自動(dòng)機(jī)

和非確定有限自動(dòng)機(jī)在接收語言的實(shí)力上是相互等價(jià)的。

2.3.6確定有限自動(dòng)機(jī)的化簡(jiǎn)

等價(jià)狀態(tài)；最少化。

2.4詞法分析器的自動(dòng)產(chǎn)生

教學(xué)目的：運(yùn)用狀態(tài)轉(zhuǎn)換圖構(gòu)造詞法分析程序；上機(jī)實(shí)踐LEX的實(shí)現(xiàn)。

2.4.1語言LEX的一般描述

一個(gè)LEX源程序主要包括兩部分。一部分是正規(guī)定義式，另一個(gè)是識(shí)別規(guī)則。產(chǎn)

生式(也稱產(chǎn)生規(guī)則或簡(jiǎn)稱規(guī)則)是定義語法范疇的一種書寫規(guī)則。一個(gè)產(chǎn)生式的

形式是Afa其中，箭頭(有時(shí)也用：：=)左邊的A是一個(gè)非終結(jié)符，稱為產(chǎn)生

式的左部符號(hào)；箭頭右邊的a是由終結(jié)符號(hào)或非終結(jié)符號(hào)組成的符號(hào)串，稱為產(chǎn)

生式的右部。我們有時(shí)也說，產(chǎn)生式Afa是關(guān)于A的一條產(chǎn)生規(guī)則。產(chǎn)生式是

用來定義語法范疇的。

例如，令i代表已定義的范疇“變量”，那么，產(chǎn)生式算術(shù)表達(dá)式fi意味著把

“算術(shù)表達(dá)式”這個(gè)范疇定義為“變量”。在有的書上，“一”也用“：：="表

示：這種表示方法也稱巴科斯范式。

2.4.2超前搜尋

在某些語言中，要識(shí)別一個(gè)單詞符號(hào)必需超前看若干字符。

2.4.3LEX的實(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)生語法分析器（如YACC）,

有些甚至可用來自動(dòng)產(chǎn)生完全的編譯程序。這些構(gòu)造編譯程序的工具稱為編譯程

序——編譯程序、編譯程序產(chǎn)生器或翻譯程序書寫系統(tǒng)，它們是按對(duì)源程序和目

標(biāo)語言（或機(jī)器）的形式描述（作為輸入數(shù)據(jù)）而自動(dòng)產(chǎn)生編譯程序的。

授課題目（教學(xué)章、節(jié)或主題）：

課時(shí)支配6

第三章語法分析-上下文無關(guān)文法、形式語言和文法第3周第3-6節(jié)

授課時(shí)間

第4周第1、2節(jié)

教學(xué)目的、要求（分駕馭、熟識(shí)、了解三個(gè)層次）：

理解和定義上下文無關(guān)文法，為學(xué)習(xí)和構(gòu)造編譯程序打下良好基礎(chǔ)。

理解語言和文法的定義

駕馭文法的等價(jià)變換及語法描述方法

了解文法的分類

教學(xué)重點(diǎn)和難點(diǎn)：文法的直觀概念、文法和語言的形式定義、文法的類型、語法樹和二義性、

文法中的好用限制、句型的分析

授課類型（請(qǐng)打J）:理論課團(tuán)探討課口試驗(yàn)課口練習(xí)課因其他口

教學(xué)方式（請(qǐng)打J）:講授囪探討口示教口指導(dǎo)因其他口

教學(xué)資源（請(qǐng)打J）:多媒體因模型口實(shí)物口掛圖口音像口其他口

探討、思索題、作業(yè)：

P36：6,8,11

教學(xué)內(nèi)容

3.1.1上下文無關(guān)文法

箭頭'一>'讀為“定義為"，直豎'|'讀為"或”，它們是元語言符號(hào)。在后面

的探討中，依據(jù)不同狀況，我們將用大寫字母A、B、C…或漢語詞組（如，算術(shù)

表達(dá)式）代表非終結(jié)符號(hào)，特殊是用小寫字母a、b、c…代表終結(jié)符，用a、8、

Y等代表由終結(jié)符和非終結(jié)符組成的符號(hào)串。為簡(jiǎn)便起見，當(dāng)引用具體的文法例

子時(shí)，僅列出產(chǎn)生式和指出起先符號(hào)。

例如，下面是一個(gè)上下文無關(guān)文法：

E—>i|EAE

A—>+1*

其中，E、A是非終結(jié)符，E是起先符號(hào)，而i、+和*是終結(jié)符。

一個(gè)上下文無關(guān)文法如何定義一個(gè)語言呢？其中心思想是，從文法的起先符號(hào)動(dòng)

身，反復(fù)連續(xù)運(yùn)用產(chǎn)生式，對(duì)非終結(jié)符施行替換和綻開。例如，我們考慮下面的

文法G：

E—>E十E|E*E|（E）|i

其中，唯一的非終結(jié)符E可以看成是代表一類算術(shù)表達(dá)式。我們可以從E動(dòng)身，

進(jìn)行一系列的推導(dǎo)，推出種種不同的算術(shù)表達(dá)式來。例如，依據(jù)規(guī)則E-XE）

我們可以說：從'E'可干脆（一步地）推出'（E）'。與前面一樣，我們用'=>'

表示“干脆推出”，這樣，這句話就可表示為：En（E）。若對(duì)'（E）'中的E運(yùn)用

規(guī)則E—>E+E,就有

（E）=>（E+E）o即，從'（E）'可干脆推出'（E+E）'。把上述這兩步合并起來，就

有

En（E）n（E+E）。再對(duì)'（E+E）'中的E相繼兩次運(yùn)用規(guī)則E—>i之后，我們就有

（E）=>（E+E）=>（i+E）=>（i+i）o

我們稱這樣的一串替換序列是從E推出（i+i）的一個(gè)推導(dǎo)。這個(gè)推導(dǎo)供應(yīng)了一個(gè)

證明，證明（i+i）是文法（2.1）所定義的一個(gè)算術(shù)表達(dá)式。留意，推導(dǎo)每前進(jìn)一步

總是引用一條規(guī)則（產(chǎn)生式），而符號(hào)指僅推導(dǎo)一步的意思。

我們可以用一種圖示化的方法來表示這種推導(dǎo)，如下圖2.1,說明Hegavemea

book是一個(gè)語法正確的句子。這種圖形表示稱為語法分析樹。

定義"hegavemeabook”這個(gè)英文句子的規(guī)則可以說就是一個(gè)上下文無關(guān)文

法。其中，He,me,book,gave,a等，稱為終結(jié)符號(hào)；〈句子〉、〈主語〉、〈謂

語〉、〈動(dòng)詞〉、〈代詞〉等，稱為非終結(jié)符號(hào)；這個(gè)文法最終是要定義＜句子》的語

法結(jié)構(gòu)，所以〈句子＞在這里稱為起先符號(hào)；〈間接賓語〉冠詞X名詞》這種書

寫形式稱為產(chǎn)生式。

歸納起來，一個(gè)上下文無關(guān)文法C包括四個(gè)組成部分：一組終結(jié)符號(hào)，一組非終

結(jié)符號(hào)，一個(gè)起先符號(hào)，以及一組產(chǎn)生式。

所謂終結(jié)符號(hào)乃是組成語言的基本符號(hào)，在程序語言中就是以前屢次提到的

單詞符號(hào)，如基本字、標(biāo)識(shí)符、常數(shù)、算符和界符等。從語法分析的角度來看，

終結(jié)符號(hào)是一個(gè)語言的不行再分的基本符號(hào)。

圖2.1語法樹

非終結(jié)符號(hào)（也稱語法變量）用來代表語法范疇。例如，“算術(shù)表達(dá)式”、“布爾表

達(dá)式”、“賦值句”、“分程序”、“過程”等，它們都是現(xiàn)今程序語言常見的語法范

疇。我們也可以說，一個(gè)非終結(jié)符代表一個(gè)肯定的語法概念。因此，一個(gè)非終結(jié)

符是一個(gè)類（或集合）記號(hào)，而不是一個(gè)個(gè)體記號(hào)。例如，“算術(shù)表達(dá)式”這個(gè)非

終結(jié)符乃代表肯定算術(shù)式組成的類。因而，也可以說，每個(gè)非終結(jié)符號(hào)表示肯定

符號(hào)串的集合（由終結(jié)符號(hào)和非終結(jié)符號(hào)組成的符號(hào)串）。

起先符號(hào)是一個(gè)特殊的非終結(jié)符號(hào)，它代表所定義的語言中我們最終感愛好的語

法范疇，這個(gè)語法范疇通常稱為“句子”。但在程序語言中，我們最終感愛好的

是“程序”這個(gè)語法范疇，而其它的語法范疇都只不過是構(gòu)造“程序”的一塊塊

磚石O

3.1.2語法分析樹與二義性

前面我們提到過可以用一張圖表示一個(gè)句型的推導(dǎo)，這種表示稱為語法分析樹，

或簡(jiǎn)稱為語法樹。語法樹有助于理解一個(gè)句子語法結(jié)構(gòu)的層次。語法樹通常表示

成一棵倒立的樹，根在上，枝葉在下。語法樹的根結(jié)由起先符號(hào)所標(biāo)記。隨著推

導(dǎo)的綻開，當(dāng)某個(gè)非終結(jié)符被它的某個(gè)候選式所替換時(shí)，這個(gè)非終結(jié)符的相應(yīng)結(jié)

就產(chǎn)生出下一代新結(jié)，候選式中自左至右的每個(gè)符號(hào)對(duì)應(yīng)一個(gè)新結(jié)，并用這些符

號(hào)標(biāo)記其相應(yīng)的新結(jié)。每個(gè)新結(jié)和其父結(jié)間都有一條連線。在一棵語法樹生長(zhǎng)過

程中的任何時(shí)刻，全部那些沒有后代的端末結(jié)自左至右排列起來就是一個(gè)句型。

例如，對(duì)于文法（2.1）,關(guān)于（i*i+i）的推導(dǎo)（2.2）的語法樹如圖2.2所示。

這就是說，一棵語法樹表示了一個(gè)句型種種可能的（但未必是全部的）不同推導(dǎo)過

程，包括最左（最右）推導(dǎo)。這樣的一棵語法樹是這些不同推導(dǎo)過程的共性抽象，

是它們的代表。

假如我們堅(jiān)持運(yùn)用最左（最右）推導(dǎo)，那么，一棵語法樹就完全等價(jià)于一個(gè)最左（最

右）推導(dǎo)，這種等價(jià)性包括樹的步步成長(zhǎng)和推導(dǎo)的步步綻開之間的完全一樣性。

但是，一個(gè)句型是否只對(duì)應(yīng)唯一的一棵語法樹呢？也就是，它是否只有唯一的一

個(gè)最左（最右）推導(dǎo)呢？不盡然。

3.1.3形式語言俯視

前面喬姆斯基把文法分成四種類型，即0型，1型，2型，和3型。0型強(qiáng)于1

型，1型強(qiáng)于2型，2型強(qiáng)于3型。這幾類文法的差別在于對(duì)產(chǎn)生式施加不同的

限制。

0型文法：也稱短語文法，其實(shí)力相當(dāng)于圖靈機(jī)。任何0型語言都是遞歸可枚舉

的，反之，遞歸可枚舉集必定是一個(gè)0型語言。

1型文法：也稱上下文有關(guān)文法，對(duì)非終結(jié)符進(jìn)行替換時(shí)務(wù)必聯(lián)系上下文，并且

一般不允許替換成空串。

2型文法：也稱上下文無關(guān)文法

3型文法：也稱右線性文法，這類文法等價(jià)于正規(guī)式，所以也稱正規(guī)文法。只有

下面兩種形式的產(chǎn)生式：ATBa或ATa。

3.2.1文法等價(jià)的概念：

若L（G1）=L（G2）,則稱文法G1和G2是等價(jià)的

例如：下列兩個(gè)文法是等價(jià)的

G1[A]:AORA01RA1

G2[A]:S0S1S01

因?yàn)長(zhǎng)（G1）=L（G2）={0n1n|n21}

定義：對(duì)文法進(jìn)行變換，使變換后的文法滿意某種要求并于原文法等價(jià)，這種變換成

為文法的等價(jià)變換。

3.2.2、增廣文法

定義：設(shè)文法G[S]={VN,VT,P,S},構(gòu)造文法G，[S']=(VNU{S'},VT,P\S'),其中，P5={A

a|Aa6P}USS},明顯L(G)=L(G'),稱G'為文法G的增廣文法。

例：[Z]:ZTabZA|aATb

經(jīng)等價(jià)變換后可得到增廣文法GEA1]：

Z'TZ

ZTabZA|a

ATb

3.2.3、提取左因子

定義：若文法中有產(chǎn)生式PT501|502|...|6Bn,則稱該文發(fā)含有左因子5。其中

PeVN,01,02...BnW(VNUVT)*。

例：文法[S]:S->iEtS|iEtSeS|aE->b

提取左因子該文法變?yōu)椋?/p>

G[S]：STiEtSS'|a

S5TeS|￡

ETb

3.2.4、消退左遞歸

定義：若文法中存在推導(dǎo)：Pn+Pa,則稱該文法含有左遞歸。若存在產(chǎn)生式PnP

a,則稱該文法含有干脆左遞歸。若存在產(chǎn)生式PnP1a,P1nP2B,……,Pn-1

=>PnY,PnnP5,則稱該文法含有間接左遞歸。其中P,P1,…，PnGVN,a,

d,Y,5e(VNUVT)*O

干脆左遞歸的消退方法：

假設(shè)非終結(jié)符P存在產(chǎn)生式PnPa|。

刪除左遞歸產(chǎn)生式PnPa

引入新的非終結(jié)符P，消退文法中的左遞歸，得：

PnBP，

P，naP，|E

間接左遞歸的消退方法：

將間接左遞歸轉(zhuǎn)化為干脆左遞歸；

消退干脆左遞歸；

化簡(jiǎn)文法，刪除含有從起始符號(hào)無法到達(dá)的非終結(jié)符的產(chǎn)生式

最終，作為描述程序語言的上下文無關(guān)文法，我們對(duì)它有幾點(diǎn)限制。

(1)文法中不含任何下面形式的產(chǎn)生式：P-4P因?yàn)檫@種產(chǎn)生式除了產(chǎn)生二義性

外沒有任何用處。

(2)每個(gè)非終結(jié)符P必需有用處。這一方面意味著，必需存在含P的句型；也

就是，從起先符號(hào)動(dòng)身，存在推導(dǎo)S=>*aPp.

另一方面意味著，必需存在終結(jié)符串yeVT*,使得Pn+y；也就是，對(duì)于P不存在

永不終結(jié)的回路。

我們以后所探討的文法均假定滿意上述兩條件。

授課題目(教學(xué)章、節(jié)或主題)：課時(shí)支配12

第三章語法分析——自上而下分析第4周第3-6節(jié)

授課時(shí)間第6周第1-6節(jié)

第7周第1-2節(jié)

教學(xué)目的、要求(分駕馭、熟識(shí)、了解三個(gè)層次)：

了解確定的自頂向下分析思想

熟識(shí)某些非LL(1)文法到LL(1)文法的等價(jià)變換

駕馭LL(1)文法的判別、確定的自頂向下分析方法

教學(xué)重點(diǎn)和難點(diǎn)：語法分析器的功能、確定的自頂向下分析思想、LL(1)文法的判別、某

些非LL(1)文法到LL(1)文法的等價(jià)變換、不確定的自頂向下分析思

想、確定的自頂向下分析方法

授課類型(請(qǐng)打J)：理論課目探討課口試驗(yàn)課因練習(xí)課囪其他口

教學(xué)方式(請(qǐng)打J)：講授團(tuán)探討口示教口指導(dǎo)因其他口

教學(xué)資源(請(qǐng)打J)：多媒體因模型口實(shí)物口掛圖口音像口其他口

探討、思索題、作業(yè)：

P81：1,2,4

教學(xué)內(nèi)容

第三章語法分析——自上而下分析

3.1語法分析器的功能

語法分析器：是這樣的一個(gè)程序，它將按文法的產(chǎn)生式，識(shí)別輸入符號(hào)串是否為

一個(gè)句子。輸入串是指由單詞符號(hào)(文法的終結(jié)符)組成的有限序列。

語法分析的方法：可大致分為兩類，一類是自下而上分析法，另一類是自上而下

分析法。所謂自下而上分析法就是從輸入串起先，逐步進(jìn)行''歸約"，直至歸約

到文法的起先符號(hào)。自上而下分析過程恰好與此相反，它從文法的起先符號(hào)動(dòng)身，

反復(fù)運(yùn)用各種產(chǎn)生式，找尋“匹配”于輸入串的推導(dǎo)。

3.2自上而下分析面臨的問題

本節(jié)主要是通過例子使我們相識(shí)到，作自上而下分析所遇到的主要困難是語法的

左遞歸性使分析陷入無限循環(huán)；回溯的不確定性，要求我們將已經(jīng)完成工作推倒

重來，為解決這些問題我們要消退左遞歸和消退回溯。

3.3LL(1)分析法

自上而下分析方法不允許文法含有任何左遞歸。為構(gòu)造不帶回溯的自上而下分析

算法，首先要消退文法的左遞歸性，并找出克服回溯的充分必要條件。

3.3.1左遞歸的消退

假定關(guān)于非終結(jié)符P的規(guī)則為：P—>P|a0

其中，每個(gè)都不以P開頭，那么我們可以把P的規(guī)則改寫成如下的非干脆左遞

歸形式：

p—PP'

p'—ap'|E(E為空字)

這種形式和原來的形式是等價(jià)的，也就是說，從P推出的符號(hào)串是相同的。

3.3.2消退回溯、提左因子

我們首先來看一下在不得回溯的狀況下對(duì)于文法有什么要求。前面已經(jīng)說過，欲

實(shí)行自上而下的分析，文法不得含左遞歸。令G是一個(gè)不含左遞歸的文法，對(duì)G

的全部的非終結(jié)符號(hào)的每個(gè)候選a定義它的終結(jié)首符集FIRST(a)為：

FIRST(a)={a|a=>*a...,aeVT)

特殊是，若a=*E,則規(guī)定￡sFIRST(a)o換句話說FIRST(a)是a的全部可能推

導(dǎo)的開頭終結(jié)符或可能的so假如非終結(jié)符A的全部候選首符集兩兩不相交，即

A的任何兩個(gè)不同的候選ai和aj

FIRST(ai)cFIRST(aj)那么，當(dāng)要求A匹配輸入串時(shí)，A就能依據(jù)它所面臨

的第一個(gè)輸入符號(hào)a,精確地指派某個(gè)候選前去執(zhí)行任務(wù)。這個(gè)候選就是那個(gè)終

結(jié)首符集含a的a。

如何把一個(gè)文法改造成任何終結(jié)首符集的全部候選首符集兩兩不相交呢？其方

法是提取公共左因子。例如，假定關(guān)于A的規(guī)則是

A^8pl|5p2|...|8PnlyllY2|...lym(其中每個(gè)丫不以3開頭)

刃卜么，可以把這些規(guī)則改寫成：A.3A'|yl|丫2|…lym

A^|pl|p2l...lpn

3.3.3LL(1)分析條件

假定S是文法G的起先符號(hào)，對(duì)于任何非終結(jié)符A我們定義：

FOLLOW(A)={a|S=*...Aa...,a/}

特殊是，若Sn*...A,則規(guī)定#eFOLLOW(A).也就是說，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)nFIRST(aj)=(|)(iwj)

(3)對(duì)文法中每一個(gè)終結(jié)符A,若它存在某個(gè)候選首符集包含￡,則

FIRST(A)nFLLOW(A)=(|)一個(gè)文法若滿意以上條件，

則稱該文法G為L(zhǎng)L⑴文法

3.4遞歸下降分析程序構(gòu)造

在不含左遞歸和每個(gè)非終結(jié)符的全部候選終結(jié)首符集都兩兩不相交的條件下，可

能(僅是可能)構(gòu)造一個(gè)不帶回溯的自上而下分析程序.

文法如下：

E—>TE5E—+TEVE

T—>FTT—*FTVE

F—>(E)/i

當(dāng)一個(gè)文法滿意LL(1)條件時(shí)，我們就可以為它構(gòu)造一個(gè)不帶回溯的自上而下分

析程序，這個(gè)分析程序是由一組遞歸過程組成的，每個(gè)過程對(duì)應(yīng)文法的一個(gè)非終

結(jié)符。這樣的一個(gè)分析程序稱為遞歸下降分析器。

3.5預(yù)料分析程序

用高級(jí)語言的遞歸過程描述遞歸下降分析器只有當(dāng)具有實(shí)現(xiàn)這種過程的編譯系

統(tǒng)剛才有實(shí)際意義。實(shí)現(xiàn)LL(1)分析的另一種有效方法是運(yùn)用一張分析表和一個(gè)

棧進(jìn)行聯(lián)合限制。我們現(xiàn)在要介紹的預(yù)料分析程序就是屬于這種類型的LL(1)分

析器

3.5.1預(yù)料分析程序工作過程

預(yù)料分析程序的總控程序在任何時(shí)候都是按STACK棧頂符號(hào)X和當(dāng)前的輸入符號(hào)

a行事的。

3.5.2預(yù)料分析表的構(gòu)造

為了構(gòu)造預(yù)料分析表M,我們須要先構(gòu)造與文法G有關(guān)的集合FIRST和FOLLOW.

消退左遞歸和提取左因子將有助于獲得無多重定義的分析表Mo

可以證明，一個(gè)文法G的預(yù)料分析表M不含多重定義入口，當(dāng)且僅當(dāng)該文法為L(zhǎng)L(1)

的。

3.6LL(1)分析中的錯(cuò)誤處理

我們以預(yù)料分析為例。在預(yù)料分析過程中，出現(xiàn)了下列兩種狀況，則說明遇到了

語法錯(cuò)誤。

(1)棧頂?shù)慕K結(jié)符與當(dāng)前的輸入符號(hào)不匹配。

(2)非終結(jié)符A處于棧頂，面臨的輸入符號(hào)為a,但分析表M中的MIA,a］為空。

發(fā)覺錯(cuò)誤后，要盡快地從錯(cuò)誤中復(fù)原過來，使分析能接著進(jìn)行下去?；镜淖龇?/p>

就是跳過輸入串中的一些符號(hào)直至遇到“同步符號(hào)”為止。這種做法的效果有賴

于同步符號(hào)集的選擇。我們可以從以下幾個(gè)方面考慮同步符號(hào)集的選擇。

(1)把FOLLOW(A)中的全部符號(hào)放人非終結(jié)符A的同步符號(hào)集。假如我們跳讀一些

輸入符號(hào)直到出現(xiàn)FOLLOWS)中的符號(hào)，把A從棧中彈出，這樣就可能使分析接

著下去。

(2)對(duì)于非終結(jié)符A來說，只用FOLLOWS)作為它的同步符號(hào)集是不夠的。例如，

假如分號(hào)作為語句的結(jié)束符(C語言中就是這樣的)，那么作為語句開頭的關(guān)鍵字

就可能不在產(chǎn)生表達(dá)式的非終結(jié)符的FOLIDW集中。這樣，在一個(gè)賦值語句后少

一個(gè)分號(hào)就可能導(dǎo)致作為下一語句開頭的關(guān)鍵字被跳過。

(3)假如把FIRSTS)中的符號(hào)加入非終結(jié)符A的同步符號(hào)集，那么，當(dāng)FIRSTS)

中的一個(gè)符號(hào)在輸入中出現(xiàn)時(shí)，可以依據(jù)A復(fù)原語法分析。

(4)假如一個(gè)非終結(jié)符產(chǎn)生空串，那么，推導(dǎo)6的產(chǎn)生式可以作為缺省的狀況，

這樣做可以推遲某些錯(cuò)誤檢查，但不能導(dǎo)致放棄一個(gè)錯(cuò)誤。這種方法削減在錯(cuò)誤

復(fù)原期間必需考慮的非終結(jié)符數(shù)。

⑸假如不能匹配棧頂?shù)慕K