編譯原理教案

課程編碼：07153008

編譯原理及實現(xiàn)技術

課程教案

2011.?2012學年第1學期

任課教師：郭德貴、張紅、張睿

吉林大學計算機科學與技術學院

課程名稱：編譯原理

課程英文名稱：CompilerPrinciple

學時：64

學分：4

授課對象：計算機科學與技術專業(yè)2009級

教學目的：

編譯原理課程是計算機科學與技術專業(yè)學生的專業(yè)骨干課之一。通過學習這門課程，使學生掌握編譯

程序的基本原理、方法和實現(xiàn)技術，使學生更好的理解程序語言的內(nèi)部機制，培養(yǎng)學生初步掌握設計大型

系統(tǒng)軟件的方法、技術以及設計大型軟件的能力。

教學方式：板書多媒體系統(tǒng)演示

教材：

劉磊《編譯原理及實現(xiàn)技術》機械工業(yè)出版社2005

教學參考書：

1)陳火旺等《程序設計語言編譯原理》國防工業(yè)出版社2001

2)呂映芝，張素琴，蔣維杜《編譯原理》清華大學出版社1998

3)AlfredV.Aho,Ravi,Sethi,JeffreyD.Ullman.Compilers:Principles,Techniques,andTool.Addison

Wesley,1985.

4)CharlesN.Fischer,RichardJ.LcBlanc.CraftingaCompilerwithC.PearsonEducation,1991

授課題目第一章編譯引論

授課學時2授課時間

教學重點、難點：

本章從總體上概要介紹編譯相關的原理和技術以及典型編譯器的邏輯結構，使學生對編譯程序有一個

初步的認識。本章重點和難點為各基本概念的理解和對整個編譯程序各個階段所承擔任務的理解和掌握。

教學要點：本章需要學生掌握如下內(nèi)容：

1.實現(xiàn)高級語言的編譯方式和解釋方式及其區(qū)別。

編譯方式：對整個源程序進行分析，翻譯成等價的目標程序，翻譯的同時做語法檢查和語義檢查。然后

再運行目標程序。

解釋方式：一個語句一個語句的讀入源程序，邊翻譯邊執(zhí)行，在翻譯過程中不產(chǎn)生目標程序。

解釋方式特別適合于交互式語言；而且解釋方式允許程序執(zhí)行時改變自身，比如調(diào)試程序。這種情形

編譯程序不易勝任，因為它需要動態(tài)編譯，而解釋程序可以毫無困難的勝任；此外，解釋程序不依賴于目

標機，因為它不生成目標代碼，可移植性優(yōu)于編譯程序。但是和編譯程序相比，解釋程序開銷大，運行速

度慢得多。解釋方式和編譯方式的最根本區(qū)別在于：在解釋方式下，并不生成目標代碼程序，而是直接執(zhí)

行源程序本身。

2.典型編譯器的各個組成部分以及各個部分所承擔的任務。

a.詞法分析階段

詞法分析的任務是掃描源程序的ASCH碼序列，識別出一個個具有獨立意義的最小語法單位，即單詞.

b.語法分析階段

語法分析的任務是根據(jù)程序設計語言的語法規(guī)則，把詞法分析的結果分解成各種語法單位，同時檢查

程序中的語法錯誤。

c.語義分析階段

這一階段的任務是對語法分析所識別出的各類語法范疇，分析其含義，并進行靜態(tài)語義檢查。

d.中間代碼生成

在進行了上述的語法分析和語義分析階段的工作后，編譯程序?qū)⒃闯绦蜃兂梢环N內(nèi)部表示形式.

e.中間代碼優(yōu)化

此階段的任務是對前階段產(chǎn)生的中間代碼在不改變源程序語義的前提下進行加工變換，使生成的代碼

更為高效，縮短運行時間或節(jié)省存儲空間。

f.目標代碼生成

這一階段的任務是把中間代碼變換成特定機器上的機器指令代碼或匯編指令代碼。

g.表格管理

編譯程序在對源程序的分析過程中，需要創(chuàng)建和管理一系列的表格，以登記源程序的各類信息和編譯

各階段的進展情況。

3.遍具體實現(xiàn)上，受不同源語言、設計要求和計算機硬件條件的限制，往往將編譯程序組織成若干遍

（Pass）o所謂“遍”就是對源程序或源程序的中間表示形式從頭到尾掃描一次，并作加工處理，生成新的

中間結果或目標程序。既可以將編譯過程中的幾個不同階段合為一遍，也可以把?個階段的工作分為若干

遍。例如，詞法分析這一階段可以作為單獨的一遍，但更多的時候是把詞法分析程序作為語法分析程序的

子程序來加以調(diào)用，將詞法分析階段和語法分析階段合并為一遍。

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

與目標機無關的那些部分組成。編譯前端通常包括詞法分析、語法分析、語義分析、中間代碼生成，與目

標機無關的中間代碼優(yōu)化部分也可包含在前端，當然前端也包括相應部分的錯誤處理。

編譯后端包括與目標機有關的中間代碼優(yōu)化部分和目標代碼生成等。一般來說，這些部分與源語言無

關而僅僅依賴于中間語言。很明顯編譯后端是面向目標語言的，而編譯前端則不是，它幾乎獨立于目標語

百。

5.編譯程序的實現(xiàn)

一般開發(fā)編譯程序有如下幾種可能途徑：

a.轉(zhuǎn)換法（預處理法）：

假如我們要實現(xiàn)L語言的編譯器，現(xiàn)在有L，語言的編譯器，那么可以把L語言程序轉(zhuǎn)換成L，語言的程

序，再利用L，語言的編譯器實現(xiàn)L語言，這種方法通常用于語言的擴充。如對于C++語言，可以把C++

程序轉(zhuǎn)換成C程序，再應用C語言的編譯器進行編譯，而不用重新設計和實現(xiàn)C++編譯器。常見的宏定

義和宏擴展都屬于這種情形。

b.移植法：

假設在A機器上已有L語言的編譯程序，想在B機器上開發(fā)一個L語言的編譯程序。這里有兩種實現(xiàn)

方法：

實現(xiàn)方法一：最直接的辦法就是將A機的代碼直接轉(zhuǎn)換成B機代碼。

實現(xiàn)方法二：假設A機和B機上都有高級程序設計語言W的編譯程序，并且A機上的L語

言編譯程序是用W語言寫的，我們可以修改L編譯程序的后端，即把從中間代碼生成A機目標代碼部分

改為生成B機的目標代碼。這種在A機上產(chǎn)生B機目標代碼的編譯程序稱為交叉編譯程序（Cross

Compiler）,

c.自展法：

實現(xiàn)思想：先用目標機的匯編語言或機器語言書寫源語言的一個子集的編譯程序，然后再用這個子集

作為書寫語言，實現(xiàn)源語言的編譯程序。通常這個過程會分成若干步，像滾雪球一樣直到生成預計源語言

的編譯程序為止。我們把這樣的實現(xiàn)方式稱為自展技術。使用自展技術開發(fā)編譯器要求這種高級語言必須

是能夠編譯自身的。

d.工具法：

70年代隨著諸多種類的高級程序設計語言的出現(xiàn)和軟件開發(fā)自動化技術的提高，編譯程序的構造工具

陸續(xù)誕生，如70年代Bell試驗室推出的LEX,YACC至今還在廣泛使用。其中LEX是詞法分析器的自動

生成工具，YACC是語法分析器的自動生成工具。然而，這些工具大都是用于編譯器的前端，即與目標機

有關的代碼生成和代碼優(yōu)化部分由于對語義和目標機形式化描述方面還存在困難，雖有不少生成工具被研

制，但還沒有廣泛應用。

e.自動生成法：

如果能根據(jù)對編譯程序的描述，由計算機自動生成編譯程序，是最理想的方法，但需要對語言的語法、

語義有較好的形式化描述工具，才能自動生成高質(zhì)量的編譯程序。目前，語法分析的自動生成工具比較成

熟，如前面提到的YACC等，但是整個編譯程序的自動生成技術還不是很成熟，雖然有基于屬性文法的編

譯程序自動生成器和基于指稱語義的編譯程序自動生成器，但產(chǎn)生目標程序的效率很低，離實用尚有一段

距離，因此，要想真正的實現(xiàn)自動化，必須建立形式化描述理論。

授課題目第二章語言和文法

授課學時1授課時間

教學重點、難點：

文法的定義和分類；

短語和句柄；

語法樹和文法二義性

教學要點：

1.基本概念：

定義1字母表

字母表(alphabet)是元素的非空有窮集合，字母表中的一個元素稱為該字母表的一個字母

(letter)，也可叫做符號(symbol)或者字符(character).

定義2符號串

由字母表中的符號組成的任何有窮序列稱為符號串。

定義3符號串的連接

設x和y均是字母表E上的符號串，它們的連接是把y的所有符號順序接在x的符號之后所得到

的符號串。

定義4符號串的方塞

設x是字母表E上的符號串，把x自身連接n次得到的符號串z,即z=xx…xx(n個x),稱作符號

串x的n次嘉，記作z=x,根據(jù)定義有：

x°=e

x'=x

x2=xx

X3=x2x=xx2=xxx

xn=xn'1x=xxnl=xx...xx(n個x)

23

例1：設x=001,則有x°=ex=001001,x=001001001a

定義5前綴和后綴

設x是某一字母表上的符號串，x=yz,則y是x的前綴，z是x的后綴，特別是當

時，y是x的真前綴；y^e時，z是x的真后綴。

例2設x=abc,則￡,a,ab,abc都是x的前綴，其中￡,a,ab為x的真前綴；而abc,be,c,￡都

是x的后綴，其中bc,c,€為x的真后綴。

定義6子字符串

一個非空字符串x,刪去它的前綴和后綴后所得到的字符串稱為x的子字符串，簡稱子串。如果

刪去的前綴和后綴不同時為e，則稱該子串為真子串。

定義7符號串集合

若集合A中的所有元素都是某字母表上的符號串，則稱A為該字母表上的符號串集合。

定義8符號串集合的乘積

設A、B是兩個符號串集合，AB表示A與B的乘積，則定義

AB={xy|(xeA)A(yGB)),運算結果仍然表示符號串的集合。

例3設A={a,be},B={de,f}，則

AB={ade,af,bede,bef}

注意有{e}A=A{￡}=A,0A=a0=0,其中。為空集。符號串集合的乘積一般不滿足交換律。

定義9符號串集合的方鼎

設A是符號串集合，則稱A,是符號串集合A的方幕，其中i是非負整數(shù)。具體定義如下:

A°={E}

A'=A

A2=AA

An=AA...A(n個A)

定義10符號串集合的正閉包

設A是符號串集合，則稱A*為符號串集合A的正閉包。其具體定義如下：

A+=A'UA2UA3...

定義11符號串集合的星閉包：

設A是符號串集合，則稱A+為符號串集合A的星閉包。其具體定義如下：

A*=A°UA1UA2UA3...

星閉包又稱自反閉包或克林閉包。

由定義顯然有A+=AA*。

例4設A={ab,cd},則

A'={ab,cd,abab,abed,edab,eded,ababab,ababed,...}

A*={e,ab,cd,abab,abed,edab,eded,ababab,ababed,...}

定義12文法(grammar)

一個文法G是一個四元組G=(VN,VT,S,P)其中：

VT是一個非空的有限集合，它的每個元素稱為終極符號或終極符，一般用小寫字母表示。從語

法分析的角度看，終極符號是一個語言不可再分的基本符號。

VN是一個非空的有限集合，它的每個元素稱為非終極符號或非終極符，?般用大寫字母表示。

非終極符是一個語法范疇，表示一類具有某種性質(zhì)的符號，它不出現(xiàn)在句子中。

設V是文法G的符號集，則有V=VNUVT,VNOVT=0,即VN和VT的交集為空。

S是一個特殊的非終極符號，稱為文法的開始符號。SeVN?

P是產(chǎn)生式的有限集合。所謂的產(chǎn)生式，也稱為產(chǎn)生規(guī)則或簡稱為規(guī)則，是按照一定格式書寫的

定義語法范疇的文法規(guī)則。

2.文法分類

一個文法的核心是產(chǎn)生式集合，它決定了文法所產(chǎn)生的語言。根據(jù)產(chǎn)生式所受的限制不同，喬

姆斯基將文法分為四類，四類文法對應四種類型的語言，通常稱之為喬姆斯基體系。

a.O型文法(短語型文法)

如果對文法G中的任一產(chǎn)生式aTp不加任何限制，則稱G為0型文法或短語型文法。其中，a、

。是符號串。

b.1型文法(上下文相關文法)

如果對文法G中的任一產(chǎn)生式均限制為形如：

aAp-^ayP

其中AGVN,a,BG(VTUVN)*,YW(VTUVN)+，則稱文法G為1型文法或上下文相關文法。

c.2型文法(又稱上下文無關文法)

如果對文法G中的任一產(chǎn)生式均限制為形如：

Afa其中AGVN,aG(VTUVN)*則稱G為2型文法或上下文無關文法。

在2型文法中，用a取代非終極符A時，與A所在的上下文無關，所以稱之為上下文無關文

法。

例2.5文法G:STaSb|ab

容易驗證，G為2型文法，G產(chǎn)生的語言為：

L(G)={anbn|n>l)

例2.6文法G:S-aPd|abed

P-?bPc|be

容易驗證，G為2型文法，G產(chǎn)生的語言為：

L(G)={anbmcmd"|rn,n>1}

d.3型文法(又稱線性文法、正則文法、正規(guī)文法)

如果對文法G中的任一產(chǎn)生式均限制為形如：A9aB或Afa其中

A,BGVN,aWVT則稱文法G為3型文法。

上述形式的3型文法也稱為右線性文法，3型文法還有另一種形式，稱為左線性文法。如果

對文法G中的任一產(chǎn)生式均限制為形如：AfBa或A今a其中

A,BGVN,aSVq-

這樣的3型文法稱為左線性文法。

例2.8文法G:S9S0|0

3.短語和句柄：

定義13短語

設G是一部文法，S是G的開始符號，a便是文法G的一個句型，如果有：

S=>,aA8

并且

A=>+p

則稱。是句型a位的相對于非終極符A的短語。

定義14直接短語(簡單短語)

設G是一部文法，S是G的開始符號，是文法G的一個句型，如果有：

S=>,aA8

并且

A=>p

則稱。是句型a05的相對于非終極符A的直接短語。直接短語也稱為簡單短語。

定義15句柄

一個句型的最左直接短語稱為句柄。

例9設有文法G:S9cAd

A->ab|a

對于符號串$=cabd,顯然存在推導SneAdneabd.則ab是句型cabd相對于A的短語，也是相對

于A的直接短語；同時ab也是句型cabd的句柄。

授課題目第二章語法樹和文法二義性

授課學時1授課時間

教學重點、難點：

1.用語法樹表示推導

2.文法二義性

教學要點：

1.語法樹與文法二義性

定義語法樹

設G是給定的文法，稱滿足下列條件的樹為G的一棵語法樹。

a.每個節(jié)點都標有G的一個文法符號，且根節(jié)點標有初始符S,非葉節(jié)點標有非終極符。

b.如果一個非葉節(jié)點A有F個兒子節(jié)點B|,B2,…Bn(按從左到右順序)，則

A->B|B2...Bn一定是G的一個產(chǎn)生式。

語法樹是推導過程的圖形表示，這種表示方式有助于理解一個句子語法結構的層次。

在推導的過程中，當某個非終極符被它的某個候選式所替代時，這個非終極符的相應節(jié)點就產(chǎn)生

出下一代的節(jié)點，候選式中每個符號依次對應地標記了新產(chǎn)生的節(jié)點，每個新節(jié)點和父節(jié)點之間

都有線段相連接。在一棵語法樹生長的任何時刻，所有那些葉節(jié)點上所標記的符號按照從左到右

的次序排列起來就是這個文法的一個句型，樹的生長過程就是這個句型的推導過程。

例如，對于表達式文法G:E-E+E|E*E|(E)|i,符號串i+i*i顯然是此文法的合法句型，這個句

型的最左推導過程是：

E=>E+E=>i+E=>i+E*E=>i+i*E=>i+i*i

這是句型i+i*i的最左推導序列，這個推導過程的每一步均可用語法樹表示，如圖2.1所示。

(e)

句型i+i*i最左推導過程的語法樹表示

對于句型i+i*I,還可以使用最右推導或既非最左又非最右的推導，同樣可以給出其推導過程并用

語法樹表示。對比這些結果可以發(fā)現(xiàn)，如果推導方式不同，得到的推導序列就不同，語法樹的生

長過程也不同。也就是說，一棵語法樹包含了一個句型的多種可能的推導過程，包括最左和最右

推導，從語法樹本身看不出推導的次序。這樣的一棵語法樹是這些不同推導過程的共性抽象。

那么如果使用種確定的推導方式，比如最左推導（或最右推導），一個句型的最左推導是否一

定唯一呢？也就是這個句型所對應的語法樹是否只有唯一的一棵呢？

對于上面提到的表達式文法，它的句型i+i*i就存在另一種完全不同的最左推導：

E=>E*E=>E+E*E=>i+E*E=>i+i*E=>i+i*i

這個最左推導所對應的語法樹如圖2.2所示。

(a)

2.文法二義性

定義文法二義性

對一個文法G,如果至少存在一個句子，有兩棵(或兩棵以上)不同的語法樹，則稱該句子是二

義性的。包含有二義性句子的文法稱為二義性文法，否則，該文法是無二義性的。

根據(jù)定義2.20和上面的討論，句子i+i*i存在兩個不同的最左推導，顯然它是二義性的，因此表

達式文法G:E-E+E|E*E|(E)|i是二義性文法。

值得指出的是，文法的二義性和語言的二義性是兩個完全不同的概念。并非山于文法的二義性，

語言就有二義性?？梢杂袃蓚€文法G和G，,一個有二義性，另一個沒有二義性，但卻有

L(G尸L(G)即這兩個文法是等價的，它們所產(chǎn)生的語言相同。因此，我們在實際應用中，可以

對文法進行等價變換，以消除文法中的二義性。例如表達式文法G:E-E+E|E*E|(E)|i,可以通

過人為規(guī)定“*”的優(yōu)先級高于“+”的優(yōu)先級，并且都遵從左結合，就可以構造出與之等價的

無二義性文法G，：

授課題目第二章文法的等價變換

授課學時2授課時間

教學重點、難點：

1.直接左遞歸和間接左遞歸的消除；

2.空產(chǎn)生式消除：

教學要點

1.拓廣變換在LR類語法分析中，為了便于控制分析過程的結束，通常要求文法具有唯一

的開始符并且開始符不出現(xiàn)于產(chǎn)生式的右部。如果原文法不滿足該條件，需要

對原文法進行等價變換，因此，我們引入如下定理：

定理2.1對任一文法G1都可以構造文法G2，使得L(G】尸L(G2),且G2有這樣的特點，即

文法的開始符唯一并且不出現(xiàn)于任何產(chǎn)生式的右部。

證明：假設S是Gi的開始符，則只要在G1中擴充一條新產(chǎn)生式ZfS即可，其中Z是新

的開始符。另這樣擴充后的文法為G2,則它顯然滿足定理的要求。

2.去空產(chǎn)生式：

定理2.2對于任一文法Gi(sfSLXGO),可構造文法G2,使得L(GI尸L(G2),并且G2中無

空產(chǎn)生式。

證明：根據(jù)G”構造G2的方法如下：

(1)令。={A[A)",即。表示文法Gi中所有右部為￡的產(chǎn)生式的左部非終極符。

(2)遞歸擴充P直到收斂為止，即B=B5A|An+a,ae|T}。

(3)從G1中刪除所有空產(chǎn)生式。

(4)從Gi中刪除只能導出空串的非終極符。

(5)對于文法中任意產(chǎn)生式A^X1X2...Xi.|XiXi+1...Xn,Xi(i=l,2,...,n)有三種情況：

?若XCVT，不做動作；

?若XieV「。，不做動作；

?若Xiep,補充規(guī)則AfX1X2…Xi」Xi+i…Xn；

重復這個過程，直到不出現(xiàn)新的產(chǎn)生式為止。

例設有如下文法

A->aBcD

B^b|e

D-^BB|d

消除該文法中的空產(chǎn)生式。

解：P={B,D},根據(jù)算法中第3步可以增加下列產(chǎn)生式

A->acD

A->aBc

A->ac

AfB

去掉文法中的空產(chǎn)生式B9￡,得到新的文法如下

A->aBcD|acD|aBc|ac

B9b

DfBB|B|d

3.消除不可達產(chǎn)生式：

定理2.3對任一文法G1都可以構造文法G2，使得L(GD=L(G2),并且G2中的每個非終極

符必出現(xiàn)在它的某個句型中。

證明：根據(jù)G1,構造文法G2的方法如下：

(1)令片｛Z|Z是文法的開始符｝。

(2)遞歸擴充P直到收斂為止，即B=B3B|A9xByeG|,BeVN,Aep｝。

(3)若一個產(chǎn)生式左部非終極符As。，則刪除以A為左部的所有產(chǎn)生式。

4.去公共前綴：

公共前綴表示A的不同產(chǎn)生式的右部具有相同的前綴，這種情形不滿足自頂向下的語法分

析條件。這時可用提取左因子的方法消除產(chǎn)生式的公共前綴。假定關于A的規(guī)則是：

A^8p1|5p2|...|gpn|Yi|Y2|...|ym(其中每個Y不以6開頭)

那么，可以把這些規(guī)則寫成

>

A->5A|Y1|Y2|--lYm

A—陽㈤…叫

經(jīng)過反復提取左因子，就能夠把每個非終極符所有產(chǎn)生式的首符集變成兩兩不相交。

例2.7在Pascal語言中，語句和表達式的產(chǎn)生式都有公共前綴：

Stmfid:=Exp

Stmfid(ExpL)

ExpL->Exp

ExpL->Exp,ExpL

其中第二個產(chǎn)生式表示過程調(diào)用語句。這時可通過提取左因子法消除公共前綴得到下面產(chǎn)

生式：

Stm->idStm'

Stm'">:=Exp

Stm'今(ExpL)

ExpL->ExpExpL'

ExpL'玲，ExpExpL5

ExpL'~>￡

5.消除遞歸：

如果文法中的某個非終極符A有推導An'A…，則稱A左遞歸。左遞歸

情形，一定使得自頂向下的語法分析分析條件不成立。首先考慮直接的左遞歸，下

面是其中一例：

AfAa|A->p

消除產(chǎn)生式中的直接左遞歸是比較容易的。一般情形，假定有產(chǎn)生式：

A->Aai|Aa2|...|Aan|pi|p2|...|pn

其中，每個a都不等于3每個B都不以A開頭，那么有下面的產(chǎn)生式：

A-?A(a||a2|...|an)|(0岫|…|1)

若令a=ai|(X2I...Ian，P=Pi|P2|...|Pn?則可簡化成下面產(chǎn)生式

A->Aa|P

即有Afpaa…a(至少有一個a)。顯然它可以用下面產(chǎn)生式定義

A'faA'|E

再把a和。分別替換成ai|a2|…|%和-］同…|除，則可得下面的產(chǎn)生式

A^(p1|p2|...|pn)A,

,

A>(ai|a2|...|an)A,|e

使用這個辦法，我們?nèi)菀装盐姆ㄖ兴兄苯幼筮f歸都消除掉，但這并不意味著已經(jīng)

消除整個文法的左遞歸性。

例考慮下面文法：

STQc|c

QTRb|b

RTSa|a

雖不具有直接左遞歸，但S、Q、R都是左遞歸的，例如有

SnQcRbcSabc

如何消除一個文法的?切左遞歸呢？消除一般左遞歸的主要思想是切斷環(huán)路。以防

止左遞歸。如果一個文法不含回路（形如Pn*P的推導），也不含以人為右部的產(chǎn)

生式，那么，消除左遞歸的算法如下：

（1）把文法G的所有非終極符按任意一種順序排列成P|,P2...P,,；按此順序執(zhí)行；

（2）FORi:=lTOnDO

BEGIN

FORj:=lTOi-1DO

把形如PifRy的規(guī)則改寫成

PQ3IY|52yl..同，其中PjT-...一是關于Pj的所有規(guī)則;

消除關于P，規(guī)則的直接左遞歸；

END

（3）化簡由（2）所得的文法。即消除那些不可到達的非終極符的產(chǎn)生式規(guī)則。

例如，考慮例4.5的文法，令它的非終極符的排序為R、Q、So對于R,不存在直

接左遞歸。把R代入到Q的有關產(chǎn)生式后，我們把Q的規(guī)則變?yōu)?/p>

QTSab|ab|b

現(xiàn)在的Q同樣不含直接左遞歸，把它代入到S的有關產(chǎn)生式后，S變成

S->Sabc|abc|be|c

經(jīng)消除S的直接左遞歸后，我們得到整個文法為

S9abcS'|bcS'|cS'

S'fabcS'|￡

QTSab|ab|b

RlSa|a

顯然，其中關于Q和R的規(guī)則是多余的。經(jīng)化筒后所得的文法是：

S^abcS,|bcS,|cS,

S'fabcS'|￡

注意，由于對非終極符排列順序的不同，最后所得的文法在形式上可能不一樣。但不難證

明，它們都是等價的。例如，若對上面文法的非終極符排序為S、Q、R,那么，最后所得

的無左遞歸的文法是：

S9Qc|c

QTRb|b

R-^bcaR'|caR'|aR'

R'->bcaR'|e

顯然，兩個文法是等價的。

授課題目第二章有限自動機

授課學時2授課時間

教學重點、難點：

1確定有限自動機

2非確定有限自動機

3非確定有限自動機確定化

教學要點：

1.確定有限自動機(FA)

一個確定有限自動機M是一個五元組：M=(S,￡,f,So,Z),其中：

S：是一個有限集合，它的每個元素稱為一個狀態(tài)。

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

f：是狀態(tài)轉(zhuǎn)換函數(shù)，它是一個從SxX到S的單值全映射。F(S,a)=S,意味著：當

前狀態(tài)為S輸入字符為a時，自動機將轉(zhuǎn)換到下一狀態(tài)S\我們稱S，為S的一個后

繼狀態(tài)。

So：SoeS,是確定有限自動機唯?的初始狀態(tài)(也稱為開始狀態(tài))。

Z：ZcS,是終止狀態(tài)(也稱為接受狀態(tài))集合。

例設有DFAM=({0,1,2,3},{a,b,c}￡{0},{3})其中f定義為:

f(O,a)=1f(0,b)=4

f(l,a)=4fi[l,b)=2

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

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

出4,a)=4f(4,b)=4此DFA對應的狀態(tài)轉(zhuǎn)換圖如圖所示。

a,b

ab

014

142

234

3*33

444

2.非確定有限自動機:

定義非確定有限自動機

一個非確定有限自動機M是一個五元組M=(S,E,f,So,Z)，其中：

S：是一個有限集合，它的每個元素稱為一個狀態(tài)。

L：是一個有窮字母表，它的每個元素稱為一個輸入字符。

f：是狀態(tài)轉(zhuǎn)換函數(shù)，它是一個從SxX*到S的子集的映射，即SxE*f2s.注意這里的后繼狀態(tài)不

是單一的一個狀態(tài)，它是狀態(tài)集S的子集。

So：SocS,是非空初態(tài)集。

Z:ZcS，是終止狀態(tài)集。

對于非確定有限自動機，同樣也可以用狀態(tài)轉(zhuǎn)換圖和狀態(tài)轉(zhuǎn)換矩陣來表示。

例設有NFAM=({0,1,2},{a,b},f,{0},{2})

其中f定義為：

叫a尸{0,1}f(0,b)={0}

f(l,a)=0f(l,b尸{2}

解a尸{2}f(2,b尸{2}

此NFA對應的狀態(tài)轉(zhuǎn)換圖如圖2.6所示。

a,b

圖2.6NFAM的狀態(tài)轉(zhuǎn)換圖

此NFA對應的狀態(tài)轉(zhuǎn)換矩陣如圖所示。

aB

0{0,1}{0}

1*{2}

2*{2}{2}

NFAM的狀態(tài)轉(zhuǎn)換矩陣

3.非確定有限自動機和確定有限自動機的等價性。

對任何一個NFAM,都存在一個DFAM5,使得L(M，尸L(M)

首先定義兩個閉包：

1.設I是NFAM的狀態(tài)集的子集，定義I的￡閉包^CLOSURE⑴為：

a.若qWI,則qee_CLOSURE(I)

b.若qGI,那么從q出發(fā)經(jīng)任意條￡弧而能到達的任何狀態(tài)q'都屬于￡_CLOSURE(I)。

2.設I是NFAM的狀態(tài)集的子集，aeg,可以定義狀態(tài)子集L6S,對任一為6卻必有加日，使

得Si和Sj之間存在一條由Si指向Sj的有向弧，弧上的標記字符恰為a。

Ia=e_CLOSURE(J)

其中，J是那些可從I中的某一狀態(tài)節(jié)點出發(fā)經(jīng)過一條a弧而能到達的狀態(tài)節(jié)點的全體。

然后對給定的NFA按照如下的步驟進行確定化：

(1)構造一張表，共有|E|+1歹U，第一列為狀態(tài)子集I,然后對每個ad￡分別設一列加

(2)第一行第一列的狀態(tài)子集為I為jCLOSURE(so),其中s0為初始狀態(tài)；

(3)為第?列中的I和每個kG￡求k，并記入相應的Ik列。如果它和表格第一列中的所有狀態(tài)子集均

不相同，則此表生成一個新行，將它填入新行的第一列中。

(4)重復步驟(3),直到對每個I和kGE均已求得L且不再生成新的狀態(tài)子集為止。此過程在有限

步內(nèi)一定可以終止，因為如果|S|=n,則狀態(tài)子集最多只有2n個，上述表最多只有2n行；

(5)將第一列中的每個狀態(tài)子集重命名為新的狀態(tài)，則上述表格便成為新的狀態(tài)狀換矩陣。

例設有NFAM=({1,2,…9},{a,b},f,{l},{6,7,9})其中f如圖2.8所示.

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

對此NFA,我們首先構造一張表，表的每一行含有|L|+1列。將表的第二行的第一列處單元格的值

置為￡_CLOSURE(sO),這里為e_CLOSURE(1尸{1,2}?

然后我們開始計算表中其它單元格的值。一般而言，如果某一行的第一列中的狀態(tài)子集已經(jīng)確定，

記為I,那么對ke￡求［并記入這一行相應的Ik列。然后我們檢查這一行所有的狀態(tài)子集Ik，看它們是

否已經(jīng)在表的第一列中出現(xiàn)過，如果某一個股沒有出現(xiàn)過，則在此表的最下面生成?個新行，將它填入新

行的第一列中。

重復上述的過程，直至所有已生成的Ik均已在表的第列中出現(xiàn)過。這種NFA確定化的方法稱為子

集法。

按照子集法NFAM進行確定化構造出的狀態(tài)轉(zhuǎn)換矩陣表如圖所示。

I

Ialb

{1,2}{24,5,6,7}{3,8}

{245,6,7}{3,9,8}

{3,8}⑼4)

{3,9,8}{9}4)

{9}4)d>

對NFAM進行確定化構造出的狀態(tài)轉(zhuǎn)換矩陣表

對表格的狀態(tài)子集進行重命名,分別用1、2、3、4、5來代表{1,2}、{2,4,5,67}>{3,8}、{3,9,8}、{9}

這五個狀態(tài)子集，形成如圖2.10所示的狀態(tài)轉(zhuǎn)換矩陣，它即是和NFAM等價的DFAM，。

IAb

123

2*4

35

4*5

5*

和NFAM等價的DFAM，

授課題目第二章正則表達式

授課學時2授課時間

教學重點、難點：

1.正則表達式和正則集；

2.正則表達式和有限自動機相互轉(zhuǎn)化：

教學要點：

正則表達式和正則集

設E為有限字母表，在E上的正則表達式和正則集可遞歸定義如下：

(1)E和。是￡上的正則表達式，它們表示的正則集分別為｛e｝和0：

(2)對任何ad￡,a是Z上的正則表達式，它所表示的正則集為｛a｝;

(3)若r,s都是正則表達式，它們表示的正則集分別為R和S,則(r|s)、(r?s)、(r)*也是正則表達式,

它們分別表示的正則集是：RUS,RS和R*。

(4)有限次使用上述三條規(guī)則構成的表達式，稱為￡上的正則表達式，僅由這些正則表達式表示的集

合稱為正則集。

正則表達式的運算符“|”讀作“或”，“?”讀作“連接”，“*”讀作“閉包”(即任意有限次的自

重復連接)。在不至于引起混淆時，正則表達式中的括號可以省略不寫，連接符“?”一般也可

以省略不寫，但規(guī)定算符的優(yōu)先順序為：先“*”，次“?"，最后且規(guī)定它們的結合性為左

結合。

定理2.6

對E上的每一個正則表達r,存在一個X上的非確定有限自動機M,使得L(M)=L(r)。

證明：1.對于字母表￡上的任意一個正則表達式R,一定可以構造出一個非確定有限自動機M,使得

L(M)=L(R)o

首先構造此非確定有限自動機M的初始狀態(tài)轉(zhuǎn)換圖，其中只有開始狀態(tài)S和終止狀態(tài)Z,山S射出指

向Z的有向弧上標記正則表達式R,然后按照圖2.13所示的替換規(guī)則對正則表達式R依次進行分解，分解

過程中不斷加入新的狀態(tài)節(jié)點和有向弧，直至狀態(tài)轉(zhuǎn)換圖中所有有向弧上標記的符號都是字母表￡上的元

素或￡為止。

轉(zhuǎn)換規(guī)則1

例有正規(guī)表達式(a|b)*aa,為之構造等價的NFA。

構造過程如圖所示

由正則表達式構造等價NFA

2.同樣，對于字母表E上的非確定有限自動機M,也可以在Z上構造相應的正則表達式R,使得L(R)

=L(M)?

首先，對非確定有限自動機M的狀態(tài)轉(zhuǎn)換圖進行拓廣，即令每條弧可以用一個正則表達式標記。然

后在M的狀態(tài)轉(zhuǎn)換圖中加入兩個節(jié)點，一個是唯一的開始狀態(tài)節(jié)點S,另一個是唯一的終止狀態(tài)節(jié)點Z。

從S出發(fā)用標有e的有向弧連接到M的所有初始狀態(tài)節(jié)點上，從M的所有終止狀態(tài)節(jié)點用標有e的有

向弧連接到Z節(jié)點，形成一個與M等價的M，.接著，對M，按照圖2.15所示的替換規(guī)則進行替換，也就

是不斷消去原有的節(jié)點和有向弧，當狀態(tài)轉(zhuǎn)換圖中只剩下節(jié)點S和Z時，在S指向Z的有向弧上所標記

正則表達式就是所求的結果。

轉(zhuǎn)換規(guī)則2

例有如圖2.16所示的NFAM,試構造與之等價的正則表達式入

先對NFA的狀態(tài)轉(zhuǎn)換圖進行拓廣，然后按照圖所示的轉(zhuǎn)換規(guī)則，逐步消去自動機中的節(jié)點和弧，直

至狀態(tài)轉(zhuǎn)換圖中只剩下開始狀態(tài)S和接受狀態(tài)Z為止，此時S和Z之間弧上標記的正則表達式即為

所求。轉(zhuǎn)換過程如圖所示。

ba

a(ab|ba)a*b

(d)

a(abIba)a*b

(e)

作業(yè)安排：課后作業(yè)：4,6,8(1、3

授課題目第三章詞法分析程序的設計

授課學時1學時授課時間

教學重點、難點：

?詞法分析程序的兩種接口形式；

?單詞分類及其內(nèi)部表示形式：

?單詞的形式化描述；

?自動機的實現(xiàn)方法。

教學要點：

3.1詞法分析介紹

?功能讀源程序的字符序列，逐個拼出單詞，并構造相應的內(nèi)部表示TOKEN.同時檢查源程序中的詞

法錯誤.

?單詞所謂單詞是指語言中具有獨立含義的最小的語義單位。

?Token單詞的內(nèi)部表示。編譯程序總是用某種程序語言書寫的程序，語言的操作對象只能是該語

言規(guī)定的各種數(shù)據(jù)。而編譯程序的操作對象是程序中的各種語法單位，因此，必須把它們表示成

某種數(shù)據(jù)結構形式。

?詞法分析程序接口

3.2詞法分析程序的設計

?單詞分類一般常用程序設計語言的單詞可以分為以下幾類

1.保留字：保留字一般是由語言系統(tǒng)自身定義的，通常是由字母組成的字符串。

2.標識符：標識符一般是由字母開頭，字母、數(shù)字或其它符號的任意組合構成的。

3.常量：用來表示各種常量。主要包括整數(shù)常數(shù)、實數(shù)常數(shù)、字符串常量等。

4.特殊符號：包括運算符和界限符。運算符表示程序中算術運算、邏輯運算、字符運算、賦值運

算的確定的字符或字符串。

?單詞內(nèi)部表示

單詞的內(nèi)部表示TOKEN的結構一般由兩部分組成：單詞類別和語義信息。單詞類別用來區(qū)分單詞的

不同種類，通?？梢杂谜麛?shù)編碼來表示。單詞的語義信息也取決于今后處理上的方便。對于常量和標識符

還可以單獨構造常量表和標識符名字表，此時，單詞的語義信息的值就是指向常量表或標識符名字表中相

應位置的指針。

?單詞的形式化描述（正則表達式描述）

描述程序設計語言中單詞的工具主要有以下三種：正則表達式、自動機和正則文法。它們的功能彼此

相當。對于一個一般的程序設計語言，各類單詞的正則表達式可能如下：

1）標識符：L（L|D）*,其中L=[a-z,A-Z],D=[0-9]

2）整數(shù)：DID*,其中Dl=[l-9]

3）特殊符號：+|;|：|:=|<|<=|...

4）保留字：begin|end|while|...

單詞的形式化描述（有限自動機）

構造識別單詞的有限自動機的方法與步驟如下：

1.根據(jù)構成規(guī)則對程序語言的單詞按類構造出相應的狀態(tài)轉(zhuǎn)換圖。

2.合并各類單詞的狀態(tài)轉(zhuǎn)換圖，構成一個能識別語言所有單詞的狀態(tài)轉(zhuǎn)換圖。合并方法為：

（1）將各類單詞的狀態(tài)轉(zhuǎn)換圖的初始狀態(tài)合并為一個唯一的初始狀態(tài)；

（2）化簡調(diào)整狀態(tài)沖突和對沖突狀態(tài)重新編號；

（3）如果有必要，增加出錯狀態(tài)。

自動機的實現(xiàn)（狀態(tài)轉(zhuǎn)換矩陣法）

把自動機看作一種數(shù)據(jù)結構（狀態(tài)轉(zhuǎn)換矩陣），由控制程序控制字符在其上運行，從而完成詞法分析。

轉(zhuǎn)換矩陣法的優(yōu)點是程序短，但占存儲空間多。

State:=InitState;

Read(CurrentChar);

whileT(State,CurrentChar)^error&CurrentChar^Eofdo

beginState:=T(State,CurrentChar);

Read(CurrentChar);

end;

ifStateeFinalStatesthenAcceptelseError;

?自動機的實現(xiàn)(狀態(tài)轉(zhuǎn)換圖方法)

每個狀態(tài)對應一個帶標號的case語句；轉(zhuǎn)向邊對應goto語句。

L:caseCurrentCharof

a：gotoL;

b:gotoLk;

other:Error()

end

LjcaseCurrentCharof

Eof:Accept;

a：gotoL/

b：goto

other:Error()

end

授課題目第三章詞法分析程序的實現(xiàn)

授課學時1學時授課時間

教學重點、難點：

?詞法分析程序?qū)崿F(xiàn)算法；

?詞法分析程序的自動生成。

教學要點：

3.3手工實現(xiàn)詞法分析程序

?實現(xiàn)詞法分析程序應注意的問題

令保留字識別兩種方法

1）設置保留字表事先構造好所謂的保留字表，在進行詞法分析時，把保留字也當作一般標識符來

識別，然后查保留字表，若有，則把