編譯原理教案

課程編碼：07153008

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

課程教案

2011.?2012學(xué)年第1學(xué)期

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

吉林大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院

課程名稱(chēng)：編譯原理

課程英文名稱(chēng)：CompilerPrinciple

學(xué)時(shí)：64

學(xué)分：4

授課對(duì)象：計(jì)算機(jī)科學(xué)與技術(shù)專(zhuān)業(yè)2009級(jí)

教學(xué)目的：

編譯原理課程是計(jì)算機(jī)科學(xué)與技術(shù)專(zhuān)業(yè)學(xué)生的專(zhuān)業(yè)骨干課之一。通過(guò)學(xué)習(xí)這門(mén)課程，使學(xué)生掌握編譯

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

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

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

教材：

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

教學(xué)參考書(shū)：

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

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

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

Wesley,1985.

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

授課題目第一章編譯引論

授課學(xué)時(shí)2授課時(shí)間

教學(xué)重點(diǎn)、難點(diǎn)：

本章從總體上概要介紹編譯相關(guān)的原理和技術(shù)以及典型編譯器的邏輯結(jié)構(gòu)，使學(xué)生對(duì)編譯程序有一個(gè)

初步的認(rèn)識(shí)。本章重點(diǎn)和難點(diǎn)為各基本概念的理解和對(duì)整個(gè)編譯程序各個(gè)階段所承擔(dān)任務(wù)的理解和掌握。

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

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

編譯方式：對(duì)整個(gè)源程序進(jìn)行分析，翻譯成等價(jià)的目標(biāo)程序，翻譯的同時(shí)做語(yǔ)法檢查和語(yǔ)義檢查。然后

再運(yùn)行目標(biāo)程序。

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

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

編譯程序不易勝任，因?yàn)樗枰獎(jiǎng)討B(tài)編譯，而解釋程序可以毫無(wú)困難的勝任；此外，解釋程序不依賴(lài)于目

標(biāo)機(jī)，因?yàn)樗簧赡繕?biāo)代碼，可移植性?xún)?yōu)于編譯程序。但是和編譯程序相比，解釋程序開(kāi)銷(xiāo)大，運(yùn)行速

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

行源程序本身。

2.典型編譯器的各個(gè)組成部分以及各個(gè)部分所承擔(dān)的任務(wù)。

a.詞法分析階段

詞法分析的任務(wù)是掃描源程序的ASCH碼序列，識(shí)別出一個(gè)個(gè)具有獨(dú)立意義的最小語(yǔ)法單位，即單詞.

b.語(yǔ)法分析階段

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

程序中的語(yǔ)法錯(cuò)誤。

c.語(yǔ)義分析階段

這一階段的任務(wù)是對(duì)語(yǔ)法分析所識(shí)別出的各類(lèi)語(yǔ)法范疇，分析其含義，并進(jìn)行靜態(tài)語(yǔ)義檢查。

d.中間代碼生成

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

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

此階段的任務(wù)是對(duì)前階段產(chǎn)生的中間代碼在不改變?cè)闯绦蛘Z(yǔ)義的前提下進(jìn)行加工變換，使生成的代碼

更為高效，縮短運(yùn)行時(shí)間或節(jié)省存儲(chǔ)空間。

f.目標(biāo)代碼生成

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

g.表格管理

編譯程序在對(duì)源程序的分析過(guò)程中，需要?jiǎng)?chuàng)建和管理一系列的表格，以登記源程序的各類(lèi)信息和編譯

各階段的進(jìn)展情況。

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

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

中間結(jié)果或目標(biāo)程序。既可以將編譯過(guò)程中的幾個(gè)不同階段合為一遍，也可以把?個(gè)階段的工作分為若干

遍。例如，詞法分析這一階段可以作為單獨(dú)的一遍，但更多的時(shí)候是把詞法分析程序作為語(yǔ)法分析程序的

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

4.前端和后端概念上，我們有時(shí)把編譯程序劃分為編譯前端和編譯后端。前端主要由與源語(yǔ)言有關(guān)但

與目標(biāo)機(jī)無(wú)關(guān)的那些部分組成。編譯前端通常包括詞法分析、語(yǔ)法分析、語(yǔ)義分析、中間代碼生成，與目

標(biāo)機(jī)無(wú)關(guān)的中間代碼優(yōu)化部分也可包含在前端，當(dāng)然前端也包括相應(yīng)部分的錯(cuò)誤處理。

編譯后端包括與目標(biāo)機(jī)有關(guān)的中間代碼優(yōu)化部分和目標(biāo)代碼生成等。一般來(lái)說(shuō)，這些部分與源語(yǔ)言無(wú)

關(guān)而僅僅依賴(lài)于中間語(yǔ)言。很明顯編譯后端是面向目標(biāo)語(yǔ)言的，而編譯前端則不是，它幾乎獨(dú)立于目標(biāo)語(yǔ)

百。

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

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

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

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

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

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

義和宏擴(kuò)展都屬于這種情形。

b.移植法：

假設(shè)在A(yíng)機(jī)器上已有L語(yǔ)言的編譯程序，想在B機(jī)器上開(kāi)發(fā)一個(gè)L語(yǔ)言的編譯程序。這里有兩種實(shí)現(xiàn)

方法：

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

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

言編譯程序是用W語(yǔ)言寫(xiě)的，我們可以修改L編譯程序的后端，即把從中間代碼生成A機(jī)目標(biāo)代碼部分

改為生成B機(jī)的目標(biāo)代碼。這種在A(yíng)機(jī)上產(chǎn)生B機(jī)目標(biāo)代碼的編譯程序稱(chēng)為交叉編譯程序（Cross

Compiler）,

c.自展法：

實(shí)現(xiàn)思想：先用目標(biāo)機(jī)的匯編語(yǔ)言或機(jī)器語(yǔ)言書(shū)寫(xiě)源語(yǔ)言的一個(gè)子集的編譯程序，然后再用這個(gè)子集

作為書(shū)寫(xiě)語(yǔ)言，實(shí)現(xiàn)源語(yǔ)言的編譯程序。通常這個(gè)過(guò)程會(huì)分成若干步，像滾雪球一樣直到生成預(yù)計(jì)源語(yǔ)言

的編譯程序?yàn)橹?。我們把這樣的實(shí)現(xiàn)方式稱(chēng)為自展技術(shù)。使用自展技術(shù)開(kāi)發(fā)編譯器要求這種高級(jí)語(yǔ)言必須

是能夠編譯自身的。

d.工具法：

70年代隨著諸多種類(lèi)的高級(jí)程序設(shè)計(jì)語(yǔ)言的出現(xiàn)和軟件開(kāi)發(fā)自動(dòng)化技術(shù)的提高，編譯程序的構(gòu)造工具

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

生成工具，YACC是語(yǔ)法分析器的自動(dòng)生成工具。然而，這些工具大都是用于編譯器的前端，即與目標(biāo)機(jī)

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

制，但還沒(méi)有廣泛應(yīng)用。

e.自動(dòng)生成法：

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

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

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

譯程序自動(dòng)生成器和基于指稱(chēng)語(yǔ)義的編譯程序自動(dòng)生成器，但產(chǎn)生目標(biāo)程序的效率很低，離實(shí)用尚有一段

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

授課題目第二章語(yǔ)言和文法

授課學(xué)時(shí)1授課時(shí)間

教學(xué)重點(diǎn)、難點(diǎn)：

文法的定義和分類(lèi)；

短語(yǔ)和句柄；

語(yǔ)法樹(shù)和文法二義性

教學(xué)要點(diǎn)：

1.基本概念：

定義1字母表

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

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

定義2符號(hào)串

由字母表中的符號(hào)組成的任何有窮序列稱(chēng)為符號(hào)串。

定義3符號(hào)串的連接

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

的符號(hào)串。

定義4符號(hào)串的方塞

設(shè)x是字母表E上的符號(hào)串，把x自身連接n次得到的符號(hào)串z,即z=xx…xx(n個(gè)x),稱(chēng)作符號(hào)

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

x°=e

x'=x

x2=xx

X3=x2x=xx2=xxx

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

23

例1：設(shè)x=001,則有x°=ex=001001,x=001001001a

定義5前綴和后綴

設(shè)x是某一字母表上的符號(hào)串，x=yz,則y是x的前綴，z是x的后綴，特別是當(dāng)

時(shí)，y是x的真前綴；y^e時(shí)，z是x的真后綴。

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

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

定義6子字符串

一個(gè)非空字符串x,刪去它的前綴和后綴后所得到的字符串稱(chēng)為x的子字符串，簡(jiǎn)稱(chēng)子串。如果

刪去的前綴和后綴不同時(shí)為e，則稱(chēng)該子串為真子串。

定義7符號(hào)串集合

若集合A中的所有元素都是某字母表上的符號(hào)串，則稱(chēng)A為該字母表上的符號(hào)串集合。

定義8符號(hào)串集合的乘積

設(shè)A、B是兩個(gè)符號(hào)串集合，AB表示A與B的乘積，則定義

AB={xy|(xeA)A(yGB)),運(yùn)算結(jié)果仍然表示符號(hào)串的集合。

例3設(shè)A={a,be},B={de,f}，則

AB={ade,af,bede,bef}

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

定義9符號(hào)串集合的方鼎

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

A°={E}

A'=A

A2=AA

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

定義10符號(hào)串集合的正閉包

設(shè)A是符號(hào)串集合，則稱(chēng)A*為符號(hào)串集合A的正閉包。其具體定義如下：

A+=A'UA2UA3...

定義11符號(hào)串集合的星閉包：

設(shè)A是符號(hào)串集合，則稱(chēng)A+為符號(hào)串集合A的星閉包。其具體定義如下：

A*=A°UA1UA2UA3...

星閉包又稱(chēng)自反閉包或克林閉包。

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

例4設(shè)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是一個(gè)四元組G=(VN,VT,S,P)其中：

VT是一個(gè)非空的有限集合，它的每個(gè)元素稱(chēng)為終極符號(hào)或終極符，一般用小寫(xiě)字母表示。從語(yǔ)

法分析的角度看，終極符號(hào)是一個(gè)語(yǔ)言不可再分的基本符號(hào)。

VN是一個(gè)非空的有限集合，它的每個(gè)元素稱(chēng)為非終極符號(hào)或非終極符，?般用大寫(xiě)字母表示。

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

設(shè)V是文法G的符號(hào)集，則有V=VNUVT,VNOVT=0,即VN和VT的交集為空。

S是一個(gè)特殊的非終極符號(hào)，稱(chēng)為文法的開(kāi)始符號(hào)。SeVN?

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

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

2.文法分類(lèi)

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

姆斯基將文法分為四類(lèi)，四類(lèi)文法對(duì)應(yīng)四種類(lèi)型的語(yǔ)言，通常稱(chēng)之為喬姆斯基體系。

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

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

。是符號(hào)串。

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

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

aAp-^ayP

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

c.2型文法(又稱(chēng)上下文無(wú)關(guān)文法)

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

Afa其中AGVN,aG(VTUVN)*則稱(chēng)G為2型文法或上下文無(wú)關(guān)文法。

在2型文法中，用a取代非終極符A時(shí)，與A所在的上下文無(wú)關(guān)，所以稱(chēng)之為上下文無(wú)關(guān)文

法。

例2.5文法G:STaSb|ab

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

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

例2.6文法G:S-aPd|abed

P-?bPc|be

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

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

d.3型文法(又稱(chēng)線(xiàn)性文法、正則文法、正規(guī)文法)

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

A,BGVN,aWVT則稱(chēng)文法G為3型文法。

上述形式的3型文法也稱(chēng)為右線(xiàn)性文法，3型文法還有另一種形式，稱(chēng)為左線(xiàn)性文法。如果

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

A,BGVN,aSVq-

這樣的3型文法稱(chēng)為左線(xiàn)性文法。

例2.8文法G:S9S0|0

3.短語(yǔ)和句柄：

定義13短語(yǔ)

設(shè)G是一部文法，S是G的開(kāi)始符號(hào)，a便是文法G的一個(gè)句型，如果有：

S=>,aA8

并且

A=>+p

則稱(chēng)。是句型a位的相對(duì)于非終極符A的短語(yǔ)。

定義14直接短語(yǔ)(簡(jiǎn)單短語(yǔ))

設(shè)G是一部文法，S是G的開(kāi)始符號(hào)，是文法G的一個(gè)句型，如果有：

S=>,aA8

并且

A=>p

則稱(chēng)。是句型a05的相對(duì)于非終極符A的直接短語(yǔ)。直接短語(yǔ)也稱(chēng)為簡(jiǎn)單短語(yǔ)。

定義15句柄

一個(gè)句型的最左直接短語(yǔ)稱(chēng)為句柄。

例9設(shè)有文法G:S9cAd

A->ab|a

對(duì)于符號(hào)串$=cabd,顯然存在推導(dǎo)SneAdneabd.則ab是句型cabd相對(duì)于A(yíng)的短語(yǔ)，也是相對(duì)

于A(yíng)的直接短語(yǔ)；同時(shí)ab也是句型cabd的句柄。

授課題目第二章語(yǔ)法樹(shù)和文法二義性

授課學(xué)時(shí)1授課時(shí)間

教學(xué)重點(diǎn)、難點(diǎn)：

1.用語(yǔ)法樹(shù)表示推導(dǎo)

2.文法二義性

教學(xué)要點(diǎn)：

1.語(yǔ)法樹(shù)與文法二義性

定義語(yǔ)法樹(shù)

設(shè)G是給定的文法，稱(chēng)滿(mǎn)足下列條件的樹(shù)為G的一棵語(yǔ)法樹(shù)。

a.每個(gè)節(jié)點(diǎn)都標(biāo)有G的一個(gè)文法符號(hào)，且根節(jié)點(diǎn)標(biāo)有初始符S,非葉節(jié)點(diǎn)標(biāo)有非終極符。

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

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

語(yǔ)法樹(shù)是推導(dǎo)過(guò)程的圖形表示，這種表示方式有助于理解一個(gè)句子語(yǔ)法結(jié)構(gòu)的層次。

在推導(dǎo)的過(guò)程中，當(dāng)某個(gè)非終極符被它的某個(gè)候選式所替代時(shí)，這個(gè)非終極符的相應(yīng)節(jié)點(diǎn)就產(chǎn)生

出下一代的節(jié)點(diǎn)，候選式中每個(gè)符號(hào)依次對(duì)應(yīng)地標(biāo)記了新產(chǎn)生的節(jié)點(diǎn)，每個(gè)新節(jié)點(diǎn)和父節(jié)點(diǎn)之間

都有線(xiàn)段相連接。在一棵語(yǔ)法樹(shù)生長(zhǎng)的任何時(shí)刻，所有那些葉節(jié)點(diǎn)上所標(biāo)記的符號(hào)按照從左到右

的次序排列起來(lái)就是這個(gè)文法的一個(gè)句型，樹(shù)的生長(zhǎng)過(guò)程就是這個(gè)句型的推導(dǎo)過(guò)程。

例如，對(duì)于表達(dá)式文法G:E-E+E|E*E|(E)|i,符號(hào)串i+i*i顯然是此文法的合法句型，這個(gè)句

型的最左推導(dǎo)過(guò)程是：

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

這是句型i+i*i的最左推導(dǎo)序列，這個(gè)推導(dǎo)過(guò)程的每一步均可用語(yǔ)法樹(shù)表示，如圖2.1所示。

(e)

句型i+i*i最左推導(dǎo)過(guò)程的語(yǔ)法樹(shù)表示

對(duì)于句型i+i*I,還可以使用最右推導(dǎo)或既非最左又非最右的推導(dǎo)，同樣可以給出其推導(dǎo)過(guò)程并用

語(yǔ)法樹(shù)表示。對(duì)比這些結(jié)果可以發(fā)現(xiàn)，如果推導(dǎo)方式不同，得到的推導(dǎo)序列就不同，語(yǔ)法樹(shù)的生

長(zhǎng)過(guò)程也不同。也就是說(shuō)，一棵語(yǔ)法樹(shù)包含了一個(gè)句型的多種可能的推導(dǎo)過(guò)程，包括最左和最右

推導(dǎo)，從語(yǔ)法樹(shù)本身看不出推導(dǎo)的次序。這樣的一棵語(yǔ)法樹(shù)是這些不同推導(dǎo)過(guò)程的共性抽象。

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

定唯一呢？也就是這個(gè)句型所對(duì)應(yīng)的語(yǔ)法樹(shù)是否只有唯一的一棵呢？

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

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

這個(gè)最左推導(dǎo)所對(duì)應(yīng)的語(yǔ)法樹(shù)如圖2.2所示。

(a)

2.文法二義性

定義文法二義性

對(duì)一個(gè)文法G,如果至少存在一個(gè)句子，有兩棵(或兩棵以上)不同的語(yǔ)法樹(shù)，則稱(chēng)該句子是二

義性的。包含有二義性句子的文法稱(chēng)為二義性文法，否則，該文法是無(wú)二義性的。

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

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

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

語(yǔ)言就有二義性?？梢杂袃蓚€(gè)文法G和G，,一個(gè)有二義性，另一個(gè)沒(méi)有二義性，但卻有

L(G尸L(G)即這兩個(gè)文法是等價(jià)的，它們所產(chǎn)生的語(yǔ)言相同。因此，我們?cè)趯?shí)際應(yīng)用中，可以

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

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

無(wú)二義性文法G，：

授課題目第二章文法的等價(jià)變換

授課學(xué)時(shí)2授課時(shí)間

教學(xué)重點(diǎn)、難點(diǎn)：

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

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

教學(xué)要點(diǎn)

1.拓廣變換在LR類(lèi)語(yǔ)法分析中，為了便于控制分析過(guò)程的結(jié)束，通常要求文法具有唯一

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

對(duì)原文法進(jìn)行等價(jià)變換，因此，我們引入如下定理：

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

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

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

的開(kāi)始符。另這樣擴(kuò)充后的文法為G2,則它顯然滿(mǎn)足定理的要求。

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

定理2.2對(duì)于任一文法Gi(sfSLXGO),可構(gòu)造文法G2,使得L(GI尸L(G2),并且G2中無(wú)

空產(chǎn)生式。

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

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

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

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

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

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

?若XCVT，不做動(dòng)作；

?若XieV「。，不做動(dòng)作；

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

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

例設(shè)有如下文法

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.消除不可達(dá)產(chǎn)生式：

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

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

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

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

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

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

4.去公共前綴：

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

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

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

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

>

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

A—陽(yáng)㈤…叫

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

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

Stmfid:=Exp

Stmfid(ExpL)

ExpL->Exp

ExpL->Exp,ExpL

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

生式：

Stm->idStm'

Stm'">:=Exp

Stm'今(ExpL)

ExpL->ExpExpL'

ExpL'玲，ExpExpL5

ExpL'~>￡

5.消除遞歸：

如果文法中的某個(gè)非終極符A有推導(dǎo)An'A…，則稱(chēng)A左遞歸。左遞歸

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

面是其中一例：

AfAa|A->p

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

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

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

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

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

A->Aa|P

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

A'faA'|E

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

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

,

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

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

消除整個(gè)文法的左遞歸性。

例考慮下面文法：

STQc|c

QTRb|b

RTSa|a

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

SnQcRbcSabc

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

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

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

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

（2）FORi:=lTOnDO

BEGIN

FORj:=lTOi-1DO

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

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

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

END

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

例如，考慮例4.5的文法，令它的非終極符的排序?yàn)镽、Q、So對(duì)于R,不存在直

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

QTSab|ab|b

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

S->Sabc|abc|be|c

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

S9abcS'|bcS'|cS'

S'fabcS'|￡

QTSab|ab|b

RlSa|a

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

S^abcS,|bcS,|cS,

S'fabcS'|￡

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

明，它們都是等價(jià)的。例如，若對(duì)上面文法的非終極符排序?yàn)镾、Q、R,那么，最后所得

的無(wú)左遞歸的文法是：

S9Qc|c

QTRb|b

R-^bcaR'|caR'|aR'

R'->bcaR'|e

顯然，兩個(gè)文法是等價(jià)的。

授課題目第二章有限自動(dòng)機(jī)

授課學(xué)時(shí)2授課時(shí)間

教學(xué)重點(diǎn)、難點(diǎn)：

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

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

3非確定有限自動(dòng)機(jī)確定化

教學(xué)要點(diǎn)：

1.確定有限自動(dòng)機(jī)(FA)

一個(gè)確定有限自動(dòng)機(jī)M是一個(gè)五元組：M=(S,￡,f,So,Z),其中：

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

匚是一個(gè)有窮字母表，它的每個(gè)元素稱(chēng)為一個(gè)輸入字符。

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

前狀態(tài)為S輸入字符為a時(shí)，自動(dòng)機(jī)將轉(zhuǎn)換到下一狀態(tài)S\我們稱(chēng)S，為S的一個(gè)后

繼狀態(tài)。

So：SoeS,是確定有限自動(dòng)機(jī)唯?的初始狀態(tài)(也稱(chēng)為開(kāi)始狀態(tài))。

Z：ZcS,是終止?fàn)顟B(tài)(也稱(chēng)為接受狀態(tài))集合。

例設(shè)有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對(duì)應(yīng)的狀態(tài)轉(zhuǎn)換圖如圖所示。

a,b

ab

014

142

234

3*33

444

2.非確定有限自動(dòng)機(jī):

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

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

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

L：是一個(gè)有窮字母表，它的每個(gè)元素稱(chēng)為一個(gè)輸入字符。

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

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

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

Z:ZcS，是終止?fàn)顟B(tài)集。

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

例設(shè)有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對(duì)應(yīng)的狀態(tài)轉(zhuǎn)換圖如圖2.6所示。

a,b

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

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

aB

0{0,1}{0}

1*{2}

2*{2}{2}

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

3.非確定有限自動(dòng)機(jī)和確定有限自動(dòng)機(jī)的等價(jià)性。

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

首先定義兩個(gè)閉包：

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

a.若qWI,則qee_CLOSURE(I)

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

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

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

Ia=e_CLOSURE(J)

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

然后對(duì)給定的NFA按照如下的步驟進(jìn)行確定化：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

行的第一列中。

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

集法。

按照子集法NFAM進(jìn)行確定化構(gòu)造出的狀態(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>

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

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

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

IAb

123

2*4

35

4*5

5*

和NFAM等價(jià)的DFAM，

授課題目第二章正則表達(dá)式

授課學(xué)時(shí)2授課時(shí)間

教學(xué)重點(diǎn)、難點(diǎn)：

1.正則表達(dá)式和正則集；

2.正則表達(dá)式和有限自動(dòng)機(jī)相互轉(zhuǎn)化：

教學(xué)要點(diǎn)：

正則表達(dá)式和正則集

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

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

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

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

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

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

合稱(chēng)為正則集。

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

重復(fù)連接)。在不至于引起混淆時(shí)，正則表達(dá)式中的括號(hào)可以省略不寫(xiě)，連接符“?”一般也可

以省略不寫(xiě)，但規(guī)定算符的優(yōu)先順序?yàn)椋合取?”，次“?"，最后且規(guī)定它們的結(jié)合性為左

結(jié)合。

定理2.6

對(duì)E上的每一個(gè)正則表達(dá)r,存在一個(gè)X上的非確定有限自動(dòng)機(jī)M,使得L(M)=L(r)。

證明：1.對(duì)于字母表￡上的任意一個(gè)正則表達(dá)式R,一定可以構(gòu)造出一個(gè)非確定有限自動(dòng)機(jī)M,使得

L(M)=L(R)o

首先構(gòu)造此非確定有限自動(dòng)機(jī)M的初始狀態(tài)轉(zhuǎn)換圖，其中只有開(kāi)始狀態(tài)S和終止?fàn)顟B(tài)Z,山S射出指

向Z的有向弧上標(biāo)記正則表達(dá)式R,然后按照?qǐng)D2.13所示的替換規(guī)則對(duì)正則表達(dá)式R依次進(jìn)行分解，分解

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

素或￡為止。

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

例有正規(guī)表達(dá)式(a|b)*aa,為之構(gòu)造等價(jià)的NFA。

構(gòu)造過(guò)程如圖所示

由正則表達(dá)式構(gòu)造等價(jià)NFA

2.同樣，對(duì)于字母表E上的非確定有限自動(dòng)機(jī)M,也可以在Z上構(gòu)造相應(yīng)的正則表達(dá)式R,使得L(R)

=L(M)?

首先，對(duì)非確定有限自動(dòng)機(jī)M的狀態(tài)轉(zhuǎn)換圖進(jìn)行拓廣，即令每條弧可以用一個(gè)正則表達(dá)式標(biāo)記。然

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

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

向弧連接到Z節(jié)點(diǎn)，形成一個(gè)與M等價(jià)的M，.接著，對(duì)M，按照?qǐng)D2.15所示的替換規(guī)則進(jìn)行替換，也就

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

正則表達(dá)式就是所求的結(jié)果。

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

例有如圖2.16所示的NFAM,試構(gòu)造與之等價(jià)的正則表達(dá)式入

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

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

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

ba

a(ab|ba)a*b

(d)

a(abIba)a*b

(e)

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

授課題目第三章詞法分析程序的設(shè)計(jì)

授課學(xué)時(shí)1學(xué)時(shí)授課時(shí)間

教學(xué)重點(diǎn)、難點(diǎn)：

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

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

?單詞的形式化描述；

?自動(dòng)機(jī)的實(shí)現(xiàn)方法。

教學(xué)要點(diǎn)：

3.1詞法分析介紹

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

法錯(cuò)誤.

?單詞所謂單詞是指語(yǔ)言中具有獨(dú)立含義的最小的語(yǔ)義單位。

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

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

某種數(shù)據(jù)結(jié)構(gòu)形式。

?詞法分析程序接口

3.2詞法分析程序的設(shè)計(jì)

?單詞分類(lèi)一般常用程序設(shè)計(jì)語(yǔ)言的單詞可以分為以下幾類(lèi)

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

2.標(biāo)識(shí)符：標(biāo)識(shí)符一般是由字母開(kāi)頭，字母、數(shù)字或其它符號(hào)的任意組合構(gòu)成的。

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

4.特殊符號(hào)：包括運(yùn)算符和界限符。運(yùn)算符表示程序中算術(shù)運(yùn)算、邏輯運(yùn)算、字符運(yùn)算、賦值運(yùn)

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

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

單詞的內(nèi)部表示TOKEN的結(jié)構(gòu)一般由兩部分組成：?jiǎn)卧~類(lèi)別和語(yǔ)義信息。單詞類(lèi)別用來(lái)區(qū)分單詞的

不同種類(lèi)，通?？梢杂谜麛?shù)編碼來(lái)表示。單詞的語(yǔ)義信息也取決于今后處理上的方便。對(duì)于常量和標(biāo)識(shí)符

還可以單獨(dú)構(gòu)造常量表和標(biāo)識(shí)符名字表，此時(shí)，單詞的語(yǔ)義信息的值就是指向常量表或標(biāo)識(shí)符名字表中相

應(yīng)位置的指針。

?單詞的形式化描述（正則表達(dá)式描述）

描述程序設(shè)計(jì)語(yǔ)言中單詞的工具主要有以下三種：正則表達(dá)式、自動(dòng)機(jī)和正則文法。它們的功能彼此

相當(dāng)。對(duì)于一個(gè)一般的程序設(shè)計(jì)語(yǔ)言，各類(lèi)單詞的正則表達(dá)式可能如下：

1）標(biāo)識(shí)符：L（L|D）*,其中L=[a-z,A-Z],D=[0-9]

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

3）特殊符號(hào)：+|;|：|:=|<|<=|...

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

單詞的形式化描述（有限自動(dòng)機(jī)）

構(gòu)造識(shí)別單詞的有限自動(dòng)機(jī)的方法與步驟如下：

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

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

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

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

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

自動(dòng)機(jī)的實(shí)現(xiàn)（狀態(tài)轉(zhuǎn)換矩陣法）

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

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

State:=InitState;

Read(CurrentChar);

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

beginState:=T(State,CurrentChar);

Read(CurrentChar);

end;

ifStateeFinalStatesthenAcceptelseError;

?自動(dòng)機(jī)的實(shí)現(xiàn)(狀態(tài)轉(zhuǎn)換圖方法)

每個(gè)狀態(tài)對(duì)應(yīng)一個(gè)帶標(biāo)號(hào)的case語(yǔ)句；轉(zhuǎn)向邊對(duì)應(yīng)goto語(yǔ)句。

L:caseCurrentCharof

a：gotoL;

b:gotoLk;

other:Error()

end

LjcaseCurrentCharof

Eof:Accept;

a：gotoL/

b：goto

other:Error()

end

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

授課學(xué)時(shí)1學(xué)時(shí)授課時(shí)間

教學(xué)重點(diǎn)、難點(diǎn)：

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

?詞法分析程序的自動(dòng)生成。

教學(xué)要點(diǎn)：

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

?實(shí)現(xiàn)詞法分析程序應(yīng)注意的問(wèn)題

令保留字識(shí)別兩種方法

1）設(shè)置保留字表事先構(gòu)造好所謂的保留字表，在進(jìn)行詞法分析時(shí)，把保留字也當(dāng)作一般標(biāo)識(shí)符來(lái)

識(shí)別，然后查保留字表，若有，則把