《編譯原理》教案設計

《編譯原理》教案

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

第一章引論

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

教學目的、要求（分駕馭、熟識、了解三個層次）：

簡潔介紹學習此課程的目的和要求

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

熟識Compiler的基本概念

駕馭Compiler的結構和功能

教學重點和難點：編譯程序的基本結構和功能

授課類型（請打J）：理論課目探討課口試驗課口練習課口其他口

教學方式（請打J）：講授I3探討口示教口指導因其他口

教學資源（請打J）：多媒體因模型口實物口掛圖口音像口其他口

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

編譯程序的基本結構如何？各部分功能？

教學內容

0課程學習的要求及任務，學習方法介紹，成果考核標準。

第一章引論

1.1什么叫編譯程序？

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

言程序）轉換成另一種語言程序（稱為目標語言程序），而后者與前者在邏輯上是

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

樣的“高級語言”，而目標語言是諸如匯編語言或機器語言之類的“低級語言”，

這樣的一個翻譯程序就稱為編譯程序。

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

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

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

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

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

調試的編譯程序稱為診斷編譯程序（DiagnosticC。叩iler）,著重于提高目標代

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

同時供應了調試、優(yōu)化等多種功能，用戶可以通過“開關”進行選擇。運行編譯

程序的計算機稱宿主機，運行編譯程序所產生目標代碼的計算機稱目標機。

假如一個編譯程序產生不同于其宿主機的機器代碼，則稱它為交叉編譯程序

（CrOSSC。叩iler）。假如不需重寫編譯程序中與機器無關的部分就能變更目標

機，則稱該編譯程序為可變目標編譯程序（RetargetabIeCompiIer）o

1.2編譯過程概述

編譯程序過程：從輸入源程序起先到輸出目標程序為止的整個編譯過程可分為

以下五個階段：詞法分析，語法分析，語義分析，中間代碼產生，優(yōu)化和目標代碼生

成.

1.3編譯程序的結構

編譯程序的結構可以依據從輸入源程序起先到輸出目標程序為止的整個編譯過

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

標代碼生成。

1.3.1編譯程序總框

編譯程序的結構可以依據這五個階段的任務分模塊進行設計。下圖給出了編譯程

序的總框。

日癡2庫

1.3.2表格與表格管理

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

譯各階段的進展狀況。在編譯程序運用的表格中，最合理的是符號表。編譯程

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

的進展狀況。合理地設計和運用表格是編譯程序構造的一個重要問題。在編譯程

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

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

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

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

名字的運用性出現(xiàn)時，要對名字的屬性進行查證。

當掃描器識別出一個名字（標識符）后，它把該名字填人到符號表中。但這時不能

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

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

定。

由此可見，編譯各階段都涉及到構造、查找或更新有關的表格。

1.3.3出錯處理

遍:是對源程序或源程序的中間結果從頭到尾掃描一次，并作有關的加工處理，

生產新的中間結果或目標程序。一個編譯程序不僅應能對書寫正確的程序進行翻

譯，而且應能對出現(xiàn)在源程序中的錯誤進行處理。假如源程序有錯誤，編譯程序

應設法發(fā)覺錯誤，把有關錯誤信息報告給用戶。這部分工作是由特地的一組程序

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

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

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

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

那當然就更好了。但是，自動校正錯誤的代價是特別高的。

編譯過程的每一階段都可能檢測出錯誤，其中，絕大多數錯誤可以在編譯的前三

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

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

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

階段能夠檢測出諸如“括號不匹配”、“缺少；”之類的錯誤。語義錯誤是指源程

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

誤要在運行時才能檢測出來。語義錯誤通常包括：說明錯誤、作用域錯誤、類型

不一樣等等。

1.3.4遍

遍:是對源程序或源程序的中間結果從頭到尾掃描一次，并作有關的加工處理，

生產新的中間結果或目標程序。通常，每遍的工作由從外存上獲得的前一遍的中

間結果起先（對于第一遍而言，從外存上獲得源程序），完成它所含的有關工作之

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

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

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

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

現(xiàn)。

當一遍中包含若干階段時，各階段的工作是穿插進行的。例如，我們可以把詞法

分析、語法分析及語義分析與中間代碼產生這三階段支配成一遍。這時，語法分

析器處于核心位置，當它在識別語法結構而須要下一單詞符號時，它就調用詞法

分析器，一旦識別出一個語法單位時，它就調用中間代碼產生器，完成相應的語

義分析并產生相應的中間代碼。

一個編譯程序原委應分成幾遍，如何劃分，是與源語言、設計要求、硬件設備等

諸因素有關的，因此難于統(tǒng)一劃定。遍數多一點有個好處，即整個編譯程序的邏

輯結構可能清晰一點。但遍數多勢必增加輸入/輸出所消耗的時間。因此，在主

存可能的前提下，一般還是遍數盡可能少一點為好。應當留意的是，并不是每種

語言都可以用單遍編譯程序實現(xiàn)。

1.3.5編譯前端與后端

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

有關但與目標機無關的那些部分組成。這些部分通常包括詞法分析、語法分析、

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

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

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

可以取編譯程序的前端，改寫其后端以生成不同目標機上的相同語言的編譯程

序。假如后端的設計是經過細心考慮的，那么后端的改寫將用不了太大工作量，

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

間語言，然后為不同的前端配上相同的后端，這樣就可為同一臺機器生成不同語

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

的成果還特別有限。

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

如.在聞名的Ada程序設計環(huán)境APSE中，運用的是一種稱為Diana的樹形結構

的中間語言一個Ada源程序通過前編譯轉換為Diana中間代碼，由編譯后端把

Diana中間代碼轉換為目標代碼。編譯前端與不同的編譯后端以Diana為界面，

實現(xiàn)編譯程序的目標機變更。

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

Java定義一種虛擬機代碼一Bytecode。只栗實際運用的操作平臺上實現(xiàn)了的

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

操作平臺無關性。

1.4編譯程序與程序設計環(huán)境

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

程序與這些程序設計工具一起構成所謂的程序設計環(huán)境。

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

缺乏對軟件開發(fā)全生命周期的支持。隨著軟件技術的不斷發(fā)展，現(xiàn)在人們越來越

傾向于構造集成化的程序設計環(huán)境。一個集成化的程序設計環(huán)境的特點是，它將

相互獨立的程序設計工具集成起來，以便為程序員供應完整的、一體化的支持，

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

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

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

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

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

1.5編譯程序的生成

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

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

具來構造編譯程序。但是，越來越多的人傾向于運用高級語言作為工具來構造編

譯程序。因為，這樣可以節(jié)約大量的程序設計時間，而且所構造出來的編譯程序

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

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

自動產生掃描器，有些可用于自動產生語法分析器，有些甚至可用來自動產生完

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

等，它們是依據對源語言和目標語言（或機器）的形式描述（作為輸入數據）而

自動產生編譯程序的。本課程將把自動產生器作為一個重要課題來探討。近些

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

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

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

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

的過程叫作自編譯過程。

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

另一機器上。著須要尋求某種適當的‘'中間語言但是，由于建立通用中間語

言事實上辦不到，因此，移植也只能在幾種語言和幾種機器之間進行。

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

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

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

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

教學目的、要求（分駕馭、熟識、了解三個層次）：

了解詞法分析器的構造方法

熟識詞法分析的任務和過程

駕馭正規(guī)式和有限自動機的基本概念

教學重點和難點：詞法分析器的設計、正規(guī)表達式和有限自動機、正規(guī)表達式和有限自動機

的等價性、正規(guī)文法和有限自動機間的轉換

授課類型（請打J）：理論課EI探討課口試驗課團練習課13其他口

教學方式（請打J）：講授因探討口示教口指導因其他口

教學資源（請打J）：多媒體因模型口實物口掛圖口音像口其他口

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

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

教學內容

其次章詞法分析

2.1對于詞法分析器的要求

首先探討詞法分析器輸出的單詞符號的一般形式，然后探討詞法分析器應如何和

語法分析器相連接。

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

詞法分析器的功能是輸入源程序，輸出單詞符號。單詞符號是一個程序語言的基

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

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

2標識符用來表示各種名字，如變量名、數組名和過程名等等；

3常數各種類型的常數，如125,0.718、TRUE等等；

4運算符如+、-、*、/等等；

5界符如逗號、括號、分號等等。

標識符一般統(tǒng)歸為一種。常數則宜按類型（整、實、復或布爾）分種?；咀挚?/p>

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

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

假如一個種別只含一個單詞符號，那么，對于這個單詞符號，種別編碼就完全代

表它自身了。若一個種別含有很多個單詞符號，那么對于它的每個單詞符號，除

了給出種別編碼之外，還應給出自身的值。

2.1.2詞法分析器作為一個獨立子程序

可以使整個編譯程序的結構更簡潔、清晰和條例化。

2.2詞法分析器的設計

我們將依據詞法分析的任務和作為一個獨立子程序的要求來考慮詞法分析器的

設計。

2.2.1輸入、預處理

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

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

個緩沖區(qū)中進行。但在很多狀況下，把輸入串預處理一下，對單詞符號的識別工

作將是比較便利的。

預處理的工作包括：剔除無用的空白、跳格、回車和換行符等編輯性字符；預

處理工作還可以包括源程序和出錯信息的列表打印。

2.2.2單詞符號的識別：超前搜尋

詞法分析器的結構如下圖所示：當詞法分析器調用預處理子程序處理出一串輸入

字符放進掃描緩沖區(qū)之后，掃描器就從今緩沖區(qū)中逐一識別單詞符號。當緩沖區(qū)

里的字符串被處理完之后，它又調用預處理程序裝入新串。

圖3.1詞法分析器

下面我們來介紹一下單詞符號識別的一個簡潔方法——超前搜尋。

基本字的識別有些語言的基本字的輸入表示有特殊標記，如加雙引號（如

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

FORTRAN這樣的語言，基本字不加特殊愛護，基本字和用戶自定義的標識符或

標號之間沒有特殊的界符作間隔，這就使得基本字的識別甚為麻煬。這里就須要

用到超前搜尋。

2.2.3狀態(tài)轉換圖

運用狀態(tài)轉換圖是設計詞法分析程序（掃描器）的一種好途徑。轉換圖是一張有限

方向圖。在狀態(tài)轉換圖中，結點代表狀態(tài)，用圓圈表示。狀態(tài)之間用箭弧連結。

箭弧上的標記（字符）代表在射出結（即箭弧始節(jié)）狀態(tài)下可能出現(xiàn)的輸入字符或

字符類。如下圖3.2（a）所示。

在狀態(tài)1下，若輸入字符X,則讀進X,并轉換到狀態(tài)2。若輸入字符Y,則讀

進Y,并轉換到狀態(tài)3o一張轉換圖只包含有限個狀態(tài)（即有限個結點），其中

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

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

一個狀態(tài)轉換圖可用于識別(或接受)肯定的字符。大多數程序語言的單詞符號

都可以用轉換圖予以識別。轉換圖特別易于用程序實現(xiàn)，最簡潔的方法是讓每個

狀態(tài)結點對應一小段程序。下面我們將引進一組全局變量和過程，把它們作為實

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

1.CHAR字符變量，存放最新讀進的源程序字符。

2.TOKEN字符數組，存放構成單詞符號的字符串。

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

移一字節(jié)位置。

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

直到CHAR中進入一個非空白符。

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

原來的值為‘AB',而CHAR中存放著'C',經調用CONCAT后，TOKEN的值就

變?yōu)锳BC。

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

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

7.RESERVE整型函數過程，對TOKEN中的字符串查找保留字表，若它是一個

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

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

置為空白。

2.3正規(guī)表達式與有限自動機

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(A|B)(A|B|0|l)*:2上的"標識符"的全體

(0|1)(0|1)*：￡上的"數"的全體

若兩個正規(guī)式所表示的正規(guī)集相同，則認為二者等價。兩個等價的正規(guī)式U和V

記為U=V。令U、V和W均為正規(guī)式，自不待言，下列關系普遍成立

1.V=V|U(交換律)

2.U|(V|W)=(u|v)|w(結合律)

3.U|(V|W)=(U|V)|W(結合律)

4.U|(VW)=UV|UW(安排律)(V[W)U=VU|WU

5.eU=Ue=U

2.3.2確定有限自動機(DFA)

設一個確定的有限自動機(DFA)M是一個五元式M=(S,*,f,S0,Z)其中

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

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

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

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

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

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

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

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

例如，有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

則對應的狀態(tài)轉換矩陣如下表3.2所示：

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

狀態(tài)ab

012

132

213

333

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

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

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

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

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

兩個a或相繼兩個b的字。

圖3.5狀態(tài)轉換圖

2.3.3非確定有限自動機(NFA)

設一個確定的有限自動機(DFA)M是一個五元式M=(S,Z,f,SO,Z)其中

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

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

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

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

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

2.3.4正規(guī)文法與有限自動機的等價性

對于正規(guī)文法G和有限自動機M,假如L(G)=L(M),則稱G和M是等價

的。關于正規(guī)文法和有限自動機的等價性，有以下結論：

(1)對每一個右線性正規(guī)文法G或左線性正規(guī)文法G,都存在一個有限自動機

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

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

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

2.3.5正規(guī)式與有限自動機的等價性

我們可以證明：

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

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

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

和非確定有限自動機在接收語言的實力上是相互等價的。

2.3.6確定有限自動機的化簡

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

2.4詞法分析器的自動產生

教學目的：運用狀態(tài)轉換圖構造詞法分析程序；上機實踐LEX的實現(xiàn)。

2.4.1語言LEX的一般描述

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

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

形式是Afa其中，箭頭(有時也用：：=)左邊的A是一個非終結符，稱為產生

式的左部符號；箭頭右邊的a是由終結符號或非終結符號組成的符號串，稱為產

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

用來定義語法范疇的。

例如，令i代表已定義的范疇“變量”，那么，產生式算術表達式fi意味著把

“算術表達式”這個范疇定義為“變量”。在有的書上，“一”也用“：：="表

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

2.4.2超前搜尋

在某些語言中，要識別一個單詞符號必需超前看若干字符。

2.4.3LEX的實現(xiàn)

LEX的編譯程序旨在將一個LEX源程序改造為一個詞法分析器L,這個詞法分

析器L將像有限自動機那樣工作。

相關介紹：人們已建立了多種編制部分編譯程序或整個編譯程序的有效工具。有

些能用于自動產生掃描器（如LEX）,有些可用于自動產生語法分析器（如YACC）,

有些甚至可用來自動產生完全的編譯程序。這些構造編譯程序的工具稱為編譯程

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

標語言（或機器）的形式描述（作為輸入數據）而自動產生編譯程序的。

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

課時支配6

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

授課時間

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

教學目的、要求（分駕馭、熟識、了解三個層次）：

理解和定義上下文無關文法，為學習和構造編譯程序打下良好基礎。

理解語言和文法的定義

駕馭文法的等價變換及語法描述方法

了解文法的分類

教學重點和難點：文法的直觀概念、文法和語言的形式定義、文法的類型、語法樹和二義性、

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

授課類型（請打J）:理論課團探討課口試驗課口練習課因其他口

教學方式（請打J）:講授囪探討口示教口指導因其他口

教學資源（請打J）:多媒體因模型口實物口掛圖口音像口其他口

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

P36：6,8,11

教學內容

3.1.1上下文無關文法

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

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

表達式）代表非終結符號，特殊是用小寫字母a、b、c…代表終結符，用a、8、

Y等代表由終結符和非終結符組成的符號串。為簡便起見，當引用具體的文法例

子時，僅列出產生式和指出起先符號。

例如，下面是一個上下文無關文法：

E—>i|EAE

A—>+1*

其中，E、A是非終結符，E是起先符號，而i、+和*是終結符。

一個上下文無關文法如何定義一個語言呢？其中心思想是，從文法的起先符號動

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

文法G：

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

其中，唯一的非終結符E可以看成是代表一類算術表達式。我們可以從E動身，

進行一系列的推導，推出種種不同的算術表達式來。例如，依據規(guī)則E-XE）

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

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

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

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

有

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

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

我們稱這樣的一串替換序列是從E推出（i+i）的一個推導。這個推導供應了一個

證明，證明（i+i）是文法（2.1）所定義的一個算術表達式。留意，推導每前進一步

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

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

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

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

法。其中，He,me,book,gave,a等，稱為終結符號；〈句子〉、〈主語〉、〈謂

語〉、〈動詞〉、〈代詞〉等，稱為非終結符號；這個文法最終是要定義＜句子》的語

法結構，所以〈句子＞在這里稱為起先符號；〈間接賓語〉冠詞X名詞》這種書

寫形式稱為產生式。

歸納起來，一個上下文無關文法C包括四個組成部分：一組終結符號，一組非終

結符號，一個起先符號，以及一組產生式。

所謂終結符號乃是組成語言的基本符號，在程序語言中就是以前屢次提到的

單詞符號，如基本字、標識符、常數、算符和界符等。從語法分析的角度來看，

終結符號是一個語言的不行再分的基本符號。

圖2.1語法樹

非終結符號（也稱語法變量）用來代表語法范疇。例如，“算術表達式”、“布爾表

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

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

符是一個類（或集合）記號，而不是一個個體記號。例如，“算術表達式”這個非

終結符乃代表肯定算術式組成的類。因而，也可以說，每個非終結符號表示肯定

符號串的集合（由終結符號和非終結符號組成的符號串）。

起先符號是一個特殊的非終結符號，它代表所定義的語言中我們最終感愛好的語

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

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

磚石O

3.1.2語法分析樹與二義性

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

或簡稱為語法樹。語法樹有助于理解一個句子語法結構的層次。語法樹通常表示

成一棵倒立的樹，根在上，枝葉在下。語法樹的根結由起先符號所標記。隨著推

導的綻開，當某個非終結符被它的某個候選式所替換時，這個非終結符的相應結

就產生出下一代新結，候選式中自左至右的每個符號對應一個新結，并用這些符

號標記其相應的新結。每個新結和其父結間都有一條連線。在一棵語法樹生長過

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

例如，對于文法（2.1）,關于（i*i+i）的推導（2.2）的語法樹如圖2.2所示。

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

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

是它們的代表。

假如我們堅持運用最左（最右）推導，那么，一棵語法樹就完全等價于一個最左（最

右）推導，這種等價性包括樹的步步成長和推導的步步綻開之間的完全一樣性。

但是，一個句型是否只對應唯一的一棵語法樹呢？也就是，它是否只有唯一的一

個最左（最右）推導呢？不盡然。

3.1.3形式語言俯視

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

型，1型強于2型，2型強于3型。這幾類文法的差別在于對產生式施加不同的

限制。

0型文法：也稱短語文法，其實力相當于圖靈機。任何0型語言都是遞歸可枚舉

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

1型文法：也稱上下文有關文法，對非終結符進行替換時務必聯(lián)系上下文，并且

一般不允許替換成空串。

2型文法：也稱上下文無關文法

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

下面兩種形式的產生式：ATBa或ATa。

3.2.1文法等價的概念：

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

例如：下列兩個文法是等價的

G1[A]:AORA01RA1

G2[A]:S0S1S01

因為L（G1）=L（G2）={0n1n|n21}

定義：對文法進行變換，使變換后的文法滿意某種要求并于原文法等價，這種變換成

為文法的等價變換。

3.2.2、增廣文法

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

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

例：[Z]:ZTabZA|aATb

經等價變換后可得到增廣文法GEA1]：

Z'TZ

ZTabZA|a

ATb

3.2.3、提取左因子

定義：若文法中有產生式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、消退左遞歸

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

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

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

d,Y,5e(VNUVT)*O

干脆左遞歸的消退方法：

假設非終結符P存在產生式PnPa|。

刪除左遞歸產生式PnPa

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

PnBP，

P，naP，|E

間接左遞歸的消退方法：

將間接左遞歸轉化為干脆左遞歸；

消退干脆左遞歸；

化簡文法，刪除含有從起始符號無法到達的非終結符的產生式

最終，作為描述程序語言的上下文無關文法，我們對它有幾點限制。

(1)文法中不含任何下面形式的產生式：P-4P因為這種產生式除了產生二義性

外沒有任何用處。

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

就是，從起先符號動身，存在推導S=>*aPp.

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

永不終結的回路。

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

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

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

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

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

教學目的、要求(分駕馭、熟識、了解三個層次)：

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

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

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

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

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

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

授課類型(請打J)：理論課目探討課口試驗課因練習課囪其他口

教學方式(請打J)：講授團探討口示教口指導因其他口

教學資源(請打J)：多媒體因模型口實物口掛圖口音像口其他口

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

P81：1,2,4

教學內容

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

3.1語法分析器的功能

語法分析器：是這樣的一個程序，它將按文法的產生式，識別輸入符號串是否為

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

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

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

到文法的起先符號。自上而下分析過程恰好與此相反，它從文法的起先符號動身，

反復運用各種產生式，找尋“匹配”于輸入串的推導。

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

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

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

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

3.3LL(1)分析法

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

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

3.3.1左遞歸的消退

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

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

歸形式：

p—PP'

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

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

3.3.2消退回溯、提左因子

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

實行自上而下的分析，文法不得含左遞歸。令G是一個不含左遞歸的文法，對G

的全部的非終結符號的每個候選a定義它的終結首符集FIRST(a)為：

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

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

導的開頭終結符或可能的so假如非終結符A的全部候選首符集兩兩不相交，即

A的任何兩個不同的候選ai和aj

FIRST(ai)cFIRST(aj)那么，當要求A匹配輸入串時，A就能依據它所面臨

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

結首符集含a的a。

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

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

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

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

A^|pl|p2l...lpn

3.3.3LL(1)分析條件

假定S是文法G的起先符號，對于任何非終結符A我們定義：

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

特殊是，若Sn*...A,則規(guī)定#eFOLLOW(A).也就是說，F(xiàn)OLLOW(A)是全部句型

中出現(xiàn)在緊接A之后的終結符或者中，。推斷某給定文法是否為LL(1)文法其條件

為：

(1)文法不含左遞歸。

(2)對于文法中每個非終結符A的各個產生式的候選首符集兩兩不相交。

即，若

A―^a1|a2|...|an則：

FIRST(ai)nFIRST(aj)=(|)(iwj)

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

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

則稱該文法G為LL⑴文法

3.4遞歸下降分析程序構造

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

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

文法如下：

E—>TE5E—+TEVE

T—>FTT—*FTVE

F—>(E)/i

當一個文法滿意LL(1)條件時，我們就可以為它構造一個不帶回溯的自上而下分

析程序，這個分析程序是由一組遞歸過程組成的，每個過程對應文法的一個非終

結符。這樣的一個分析程序稱為遞歸下降分析器。

3.5預料分析程序

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

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

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

析器

3.5.1預料分析程序工作過程

預料分析程序的總控程序在任何時候都是按STACK棧頂符號X和當前的輸入符號

a行事的。

3.5.2預料分析表的構造

為了構造預料分析表M,我們須要先構造與文法G有關的集合FIRST和FOLLOW.

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

可以證明，一個文法G的預料分析表M不含多重定義入口，當且僅當該文法為LL(1)

的。

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

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

語法錯誤。

(1)棧頂的終結符與當前的輸入符號不匹配。

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

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

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

于同步符號集的選擇。我們可以從以下幾個方面考慮同步符號集的選擇。

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

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

著下去。

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

假如分號作為語句的結束符(C語言中就是這樣的)，那么作為語句開頭的關鍵字

就可能不在產生表達式的非終結符的FOLIDW集中。這樣，在一個賦值語句后少

一個分號就可能導致作為下一語句開頭的關鍵字被跳過。

(3)假如把FIRSTS)中的符號加入非終結符A的同步符號集，那么，當FIRSTS)

中的一個符號在輸入中出現(xiàn)時，可以依據A復原語法分析。

(4)假如一個非終結符產生空串，那么，推導6的產生式可以作為缺省的狀況，

這樣做可以推遲某些錯誤檢查，但不能導致放棄一個錯誤。這種方法削減在錯誤

復原期間必需考慮的非終結符數。

⑸假如不能匹配棧頂的終