編譯原理課件

第一章編譯概述1.1

語言處理與編譯程序1.1.1程序設(shè)計(jì)語言的引入是解決人機(jī)對話鴻溝的一個(gè)里程碑語言處理程序自然語言數(shù)學(xué)概念與符號程序設(shè)計(jì)語言機(jī)器指令人類的“計(jì)算”思維形式表示方法計(jì)算機(jī)的“計(jì)算”方式**語言處理與編譯程序1.1.2程序設(shè)計(jì)語言分類程序設(shè)計(jì)語言是遵守一定規(guī)范的、描述“計(jì)算”（Computing）過程的形式語言。一般可以劃分：低級語言 低級語言是面向機(jī)器的語言，它是為特定的計(jì)算機(jī)系統(tǒng)設(shè)計(jì)的語言。如：機(jī)器指令、匯編語言是低級語言。高級語言 高級語言是與具體計(jì)算機(jī)無關(guān)的“通用”語言，它更接近于人類的自然語言和數(shù)學(xué)表示。如：FORTRAN、Pascal、C、JAVA等等高級語言。其他語言 如：控制命令語言、查詢語言、腳本語言等。**語言處理與編譯程序1.1.3語言處理程序翻譯程序(Translator)

翻譯程序是一種語言處理程序，它將輸入的用程序設(shè)計(jì)語言（源語言）書寫的程序（源程序）轉(zhuǎn)換為等價(jià)的用另一種語言書（目標(biāo)語言）寫的程序（目標(biāo)程序）。 若源語言是匯編語言，目標(biāo)語言是機(jī)器語言，稱這種翻譯程序?yàn)閰R編程序。 若源語言是高級語言，目標(biāo)語言是低級語言，稱這種翻譯程序?yàn)榫幾g程序。

若源語言是高級語言，目標(biāo)語言是另一種高級語言，稱這種翻譯程序?yàn)檗D(zhuǎn)換程序。**語言處理與編譯程序解釋程序（Interpreter） 解釋程序是一種語言處理程序，它對源程序逐個(gè)語句地進(jìn)行分析，并根據(jù)每個(gè)語句的含義執(zhí)行語句指定的功能。編譯程序（翻譯程序）與解釋程序主要的不同是：編譯程序?qū)⑾壬赡繕?biāo)程序，再執(zhí)行目標(biāo)程序，而解釋程序不生成目標(biāo)程序，邊翻譯、邊執(zhí)行。形象地說，這類似于自然語言中的“筆譯”與“口譯”。翻譯與解釋相結(jié)合的方法是一種不錯(cuò)的方法：即先將源程序翻譯為中間語言表示的代碼，然后再解釋執(zhí)行。例如，JAVA語言的源程序翻譯為一種稱為Bytecode的中間代碼，再通過JAVA虛擬機(jī)解釋執(zhí)行。

**語言處理與編譯程序編譯程序的一個(gè)實(shí)例FACOMM-340的C語言編譯器

程序名意義功能CV替換程序\、$等字符的替換CPP預(yù)處理程序#include、#define等的處理CSA詞法、語法、語義分析程序生成中間代碼CCG代碼生成程序生成匯編指令A(yù)SM匯編程序生成二進(jìn)制機(jī)器指令LINK連接裝配程序生成可執(zhí)行程序**語言處理與編譯程序相關(guān)說明CV、CPP與語言、機(jī)器相關(guān)，ASM、LINK與機(jī)器相關(guān)，而CSA、CSG組成了編譯程序的主體。稱CSA為編譯器的前端獨(dú)立于目標(biāo)語言，稱CSG為編譯器的后端面向目標(biāo)語言。遍 在編譯過程中，掃描一遍源程序（輸入文件），經(jīng)處理形成一個(gè)輸出文件，稱為一遍。 合理地決定“遍數(shù)”，可提高效率（時(shí)/空）LINK程序

linker：連接程序： 多個(gè)不同的目標(biāo)文件 一個(gè)可執(zhí)行文件

loader：裝配程序：相對地址 絕對地址**語言處理與編譯程序編譯器所在的集成環(huán)境 編輯器（Editor)

調(diào)試器（Debugger)

描述器（Profiler)

項(xiàng)目管理器（ProjectManager)等**編譯程序概貌1.2編譯過程和編譯程序的基本結(jié)構(gòu)

抽象地看：源程序（S）編譯程序（C）目標(biāo)程序（T）出錯(cuò)信息（E）**

這是一個(gè)邏輯模型

獨(dú)立于具體的語言和機(jī)器**以賦值語句pos:=init+rate*60為例來了解編譯的全過程詞法分析

(LexicalAnalysis)功能：a)掃描源程序的字符串，識別出意義獨(dú)立的最小的詞 法單位——單詞（Token）。b)刪除注解、空格、回車及與輸入介質(zhì)有關(guān)的符號。c)報(bào)告詞法錯(cuò)誤。 如上述賦值語句經(jīng)過詞法分析后輸出為如下單詞：

(ID,pos)(OP,:=)(ID,init)(OP,+)(ID,rate)(OP,*)(CONST,60)**語法分析

(SyntaxAnalysis)功能：對輸入的單詞串，按程序設(shè)計(jì)語言的語法規(guī)則，檢查源程序句法正確性。例如某語言關(guān)于賦值語句的語法規(guī)則是：賦值語句是：ID:=EXPID、CONST是EXP若EXP1和EXP2是EXP，則EXP1+EXP2、EXP1*EXP2、(EXP1)是EXP。 可以通過自頂向下或自底向上的句法分析方法，建立分析樹（又稱

句法樹、推導(dǎo)樹）進(jìn)行句法分析。

**對此例，分析樹為：**語義分析

(SemanticAnalysis)功能：檢查語義的正確性，完成語義解釋及必要的轉(zhuǎn)換。例如：此例中各變量的數(shù)據(jù)類型是float，由于rate與60的類型不同就應(yīng)該進(jìn)行轉(zhuǎn)換，即將60轉(zhuǎn)換為60.0。中間代碼生成

（IntermediateCodeGeneration）

功能：將單詞串轉(zhuǎn)換為等價(jià)的中間代碼串。 常見的中間代碼 有：四元組、三元組、 逆波蘭（后綴）表示等。上例中的賦值語句可翻譯為（四元組形式）：(float，，60，t1)(*，ID.rate，t1，t2)(+，ID.init，t2，t3)(:=,t3,,ID.pos)其中t1，t2，t3是臨時(shí)變量、ID.x是x在符號表中的位置。

**代碼優(yōu)化

(CodeOptimization)功能：以提高目標(biāo)代碼運(yùn)行的時(shí)/空間效率為目的 的對中間代碼進(jìn)行等價(jià)變換。常見的方法有：刪除無用賦值和多余運(yùn)算、常量合并、運(yùn)算強(qiáng)度削弱、代碼外提、復(fù)寫傳播等等。此例中的中間代碼通過優(yōu)化可為：(*，ID.rate，60.0，t1)(+，ID.init，t1，t2)(:=，t2，，ID.pos)代碼生成（CodeGeneration）功能：將中間代碼串轉(zhuǎn)換為匯編代碼或機(jī)器指令。**代碼生成此例中優(yōu)化后的中間代碼可生成如下的匯編代碼：LOADR0,drate(R3)LOADR1,d60.0(R3)MULTR0,R1LOADR0,dinit(R3)ADDR0,R1STORER1,dpos(R3)其中R3是基地址寄存器，dx是x的位移（相對于R3的內(nèi)容）。

**出錯(cuò)處理

(ErrorHandle)功能：顯示出錯(cuò)的位置、性質(zhì)，限制出錯(cuò)的影響，為盡可能多地發(fā)現(xiàn)錯(cuò)誤做些恢復(fù)工作。符號表管理

(Symbol-TableManagement)功能：管理源程序中各種數(shù)據(jù)對象及其各種屬性，提供包括生成、查詢、更新等各種功能。

**編譯程序的生成方法1.3編譯程序的生成方法1.3.1手工生成 完全由人采用低級語言開發(fā)編譯程序，工作量很大。1.3.2自動(dòng)生成 利用自動(dòng)生成工具開發(fā)編譯程序。如：

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

YACC、LLgen語法分析程序的自動(dòng)生成程序

GAG、CGSS代碼生成程序的自動(dòng)生成程序**1.3.3其他編譯模式前面討論的編譯模式稱為“完全編譯”。其他編譯模式有：交互式編譯——允許通過交互方式處理源程序中的錯(cuò)誤，及時(shí)改錯(cuò)。允許部分或逐步測試。增量編譯——允許在修改了部分程序結(jié)構(gòu)后僅對該修改部分重新編譯，而不一定對整個(gè)程序進(jìn)行編譯。問題：如何實(shí)現(xiàn)？**第二章文法與語言的基本知識2.1概述程序設(shè)計(jì)語言是一種形式語言，與自然語言既有相似的性質(zhì)又有本質(zhì)的不同。最主要的區(qū)別是：形式語言的規(guī)則簡單、嚴(yán)格、無例外、無二義性。編譯程序的正確轉(zhuǎn)換建立在對程序設(shè)計(jì)語言的精確定義和描述基礎(chǔ)上。語法——文法是描述語言語法的形式規(guī)則語義——語言中各語句的含義語用——從使用者的角度對語言的描述本章將介紹形式語言和形式文法的基本概念，這是整個(gè)編譯原理的基礎(chǔ)。**基本概念2.2基本概念2.2.1符號與符號串用程序語言書寫的程序一般由一些基本符號組成。下面是一些常見的基本符號： 字母：a,b,c,…,x,y,z

數(shù)字：0,1,…,9

其他符號：+,-,*,/,=,:，等

在這些符號的基礎(chǔ)上，組成如if,then,else,for等關(guān)鍵字、程序的標(biāo)識符和常量，并進(jìn)一步組成用戶程序。

定義1符號的非空有限集合稱為字母表。常用V、

表示。

**符號與符號串例1：

1＝{0,1} 1是二進(jìn)制數(shù)的字母表

2＝{a,b…….z} 2是英文小寫字母

3＝{A….Z,0….9,+,-,*,/,.,(,),=,$,’,:}

3是FORTRAN4語言的字母表注意：符號可能是字符的組合如：

5＝{ASCII碼}則<=為一個(gè)符號再如：pascal語言的:＝C語言的&&等等**符號與符號串

定義2：字母表(符號的非空有限集合)V上的符號 串的遞歸定義如下：

①空串（一個(gè)不含任何元素的符號串）是字母表 V上的符號串?？沾孟ＥD字母

表示。

②字母表V中任何一個(gè)元素a，是字母表V上的符 號串。

③

若x，y是字母表V上的符號串，則它們的并置（將符號串y的符號依次寫在符號串x后面所得的符號串）也是字母表V上的符號串，記以xy。

注意：‘’與‘’的不同！

**2.2.2符號串的運(yùn)算符號串x中的元素的個(gè)數(shù)稱為符號串x的長度，記以|x|。設(shè)z＝xy是字母表V上的符號串，則x是符號串z的頭（或符號串z的前綴），而y是符號串z的尾（或符號串z的后綴）。若|x|＝1，則x是符號串z的頭符號。同樣，若|y|=1，則y是符號串z的尾符號。注意，空串

是任何一個(gè)符號串的頭和尾。當(dāng)y≠

稱x是z的真前綴。當(dāng)x≠

稱y是z的真后綴。并置（連接）是一種運(yùn)算，滿足結(jié)合律，但不滿足交換律。**例2：字母表

1＝{0,1}

，0，1，00，11，10，01，……是

1上的符號串如x=1001 y=010 則連接xy=1001010 yx=0101001 都是

1上的符號串|x|=4 |y|=3

，1，10，100，1001都是x的頭，1是x的頭符號

，1，01，001，1001都是x的尾，1是x的尾符號

，1，10，100，1001都是x的前綴，

，1，10，100是真前綴

1001，001，01，1，

都是x的后綴，001，01，1，

是真后綴**定義3：設(shè)A，B是二個(gè)符號串集合，定義：A∩B={a|a∈A且a∈B}A∪B={a|a∈A或者a∈B}A0＝{} An=AAn-1(n>0)A*=A0∪

A1∪A2∪…∪An

∪……

稱為A的閉包A＋=A1∪A2∪…∪An∪……

稱為A的正閉包

**由定義可知：A+=AA*=A*A例3：令A(yù)=

1＝{0,1}A*={，0，1，00，10，01，11…….}A+={0，1，00，10，01，11…….}令A(yù)=3

則任一FORTRAN4語言所編寫的程序P，有PA***2.3文法和語言2.3.1文法形式語言是字母表V上所有符號串的集合，當(dāng)該集合為有限集時(shí)可以枚舉其全部句子，如為無限集則需找出句子的規(guī)律，用文法來表示。定義4：上下文無關(guān)文法G是一個(gè)四元組：

G＝（VT，VN，P，<S>）其中，VT是非空有限集合，元素稱為終結(jié)符。

VN是非空有限集合，元素稱為非終結(jié)符。

P是由產(chǎn)生式組成的非空有限集合。

<S>

VN，是文法G的開始符號。常把文法G記為G[<S>]。**產(chǎn)生式（又稱復(fù)寫/產(chǎn)生規(guī)則）產(chǎn)生式是一有序?qū)ε迹║，x），一般記以 U→x（或U::=x)

其中：U稱為產(chǎn)生式左部，x稱為產(chǎn)生式的右部。符號‘→’（或‘::=’）稱為元符號含義為“由…..構(gòu)成”或“被定義為”記V＝VN∪VT

一般要求：VN∩VT＝φ

、UV，xV*，特別：

U

VN

xV

*

且<S>至少在某產(chǎn)生式左部 出現(xiàn)一次，稱文法G[<S>]為上下文無關(guān)文法。

**例4：簡單算術(shù)表達(dá)式文法G[<E>]定義為：

VT＝{+，*

，(，)，i} VN＝{<E>，<T>,<F>}P:<E>→<E>+<T> <E>→<T> <T>→<T>*<F> <T>→<F> <F>→(<E>) <F>→i

文法G是上下文無關(guān)文法**擴(kuò)展的BNF表示(見P59）擴(kuò)展的BNF（BackusNaurForm)表示引入一些元符號‘|’ 表示‘或’ 對<U>→x <U>→y: 可表示為：<U>→x|y|…..|z:<U>→z}**‘{’

‘}’表示重復(fù)出現(xiàn)n次。 如：{α}表示α連續(xù)出現(xiàn)i次，0<=i<=n {α}表示α可連續(xù)出現(xiàn)n次，i<=n<=j

例5：產(chǎn)生式<序列>→<語句> <序列>→<序列>；<語句>

與<序列>→<語句>{；<語句>}等價(jià)‘[’‘]’表示重復(fù)出現(xiàn)0次或1次。

‘(’‘)’表示提取公共符號后留下的 例6：<A>→+<T>|-<T>與<A>→(+|-)<T>等價(jià)**語言2.3.2語言定義5：設(shè)G是一個(gè)文法。如果v=x<U>y，w=xuy

其中：x，y

V*，且<U>→u

P， 則稱字符串v直接推導(dǎo)出字符串w。有時(shí)候也稱為w是v的一個(gè)直接推導(dǎo)，或者稱w直接歸約為v，記為v

w。如果存在一個(gè)直接推導(dǎo)序列：v=u0

u1

u2

…

un=w，則稱v推導(dǎo)出字符串w，或者稱w歸約為v，記為v

+w。若v=w或v

+w，則為以v

*w。**直接推導(dǎo)與推導(dǎo)例7：設(shè)有文法G1[<S>]的產(chǎn)生式集P為：

<S>→<N><N>→<D>|<N><D><D>→0|1|2|…|9

對如下推導(dǎo)：<S>

<N>

<N><D>

<N><D><D>

<D><D><D>

0<D><D>

02<D>

028

稱這樣的推導(dǎo)為最左推導(dǎo)。2.<S>

<N>

<N><D>

<N>8

<N><D>8

<N>28

<D>28

028

稱這樣的推導(dǎo)為最右推導(dǎo)。**直接推導(dǎo)與推導(dǎo)最右推導(dǎo)又稱規(guī)范推導(dǎo)，記為

。規(guī)范推導(dǎo)的逆過程稱為規(guī)范歸約。R**句型、句子與語言定義6：設(shè)G[<S>]是一文法，若<S>

*w，w

(VN∪VT)*，則稱w為文法G[<S>]一個(gè)句型。特別：若w

VT*，稱w是文法G[<S>]一個(gè)句子。文法G[<S>]句子的全體所組成的集合稱為該文法所產(chǎn)生的語言，記以L（G[<S>]）。即L(G[<S>]）={w|<S>

*w，且w

VT*}。例8：對例7的G1[<S>]

<S>

、<N><D>、0<D><D>、028是文法的句型

028是G1的一個(gè)句子。語言L(G1[<S>])是什么？如何表示一個(gè)語言？**語言語言L(G1[<S>])是一個(gè)具有無限多句子的集合，稱為無限語言?？梢杂糜邢薜募系男问絹矶x一個(gè)無限多句子的語言。給定一個(gè)文法，就能唯一確定其語言。給定一種語言，能確定其對應(yīng)的文法，但文法不唯一。對給定的文法G及任意的符號串w，能否用有限的方法來判定w是否是G的一個(gè)句子（句型）？**語言語言L(G)有無限多個(gè)句子，這與G的產(chǎn)生式集合P中某些產(chǎn)生式的遞歸性有關(guān)：1.

若<U>→<U>……

P稱為直接左遞歸若<U>→……<U>……

P稱為直接遞歸若<U>→………<U>

P稱為直接右遞歸2.

若<U>

+<U>………

稱為左遞歸若<U>

+…<U>……

稱為遞歸若<U>

+………<U>

稱為右遞歸對文法G1、G2，如L(G1)=L(G2)

稱文法G1、G2等價(jià)**短語與句柄2.3.3短語與句柄定義7：設(shè)G[<S>]是一個(gè)文法，并設(shè)w=xuy是該文法的一個(gè)句型。若<S>

*x<U>y且<U>

+u，則稱u為句型w=xuy對非終結(jié)符<U>的一個(gè)短語。若<S>

*x<U>y且<U>

u，則稱u為句型w=xuy相對于非終結(jié)符<U>的一個(gè)簡單(直接）短語。任何一個(gè)句型的最左簡單短語稱為柄短語（句柄）。含有終結(jié)符的短語，并且不存在也具有這種性質(zhì)真子串的短語稱為素短語。**P30習(xí)題22.12.22.32.42.72.10補(bǔ)充題： 試為如下的語言構(gòu)造二個(gè)（或二個(gè)以上的）等價(jià)文法，它們接受相同的語言。

①L1={a2n

b|n≥1}②L2={aibjck|i,j,k≥1}習(xí)題**語法樹（推導(dǎo)樹）2.4語法樹與二義性2.4.1語法樹（又稱推導(dǎo)樹、分析樹）用特殊的樹的形式來表示推導(dǎo)一個(gè)推導(dǎo) 一棵推導(dǎo)樹注意：這是一種專為推導(dǎo)的表示而設(shè)計(jì)的特 殊的樹 **推導(dǎo)樹的構(gòu)造與表示方法：對文法G=（VT，VN，P，<S>）樹的每個(gè)結(jié)點(diǎn)對應(yīng)一個(gè)文法符號，vV∪{}根結(jié)點(diǎn)是文法開始符號<S>對<A>VN為標(biāo)記的結(jié)點(diǎn)，其所有的子結(jié)點(diǎn)（若有的話）則從左至右標(biāo)記為x1,x2,…xn,且<A>→x1,x2,…xn

P若某結(jié)點(diǎn)標(biāo)記為

，則必為葉結(jié)點(diǎn)，且為其 父結(jié)點(diǎn)的唯一子結(jié)點(diǎn)。**例1：表達(dá)式文法G[<E>]：

<E>→<E>+<T>|<T> <T>→<T>*<F>|<F> <F>→(<E>)|i對句型i*(<E>)的推導(dǎo)為：

<E>

<T><T>*<F><F>*<F>i*<F> i*(<E>)**對應(yīng)的推導(dǎo)樹為：

注意推導(dǎo)樹的特殊性**語法樹與短語使用推導(dǎo)樹計(jì)算句型（句子）的短語簡單、明了推導(dǎo)<S>

*x<U>y <U>

+u等價(jià)于： 等價(jià)于：

<S> <U> x<U>y u**因此稱u是句型xuy(對<U>)的一個(gè)短語等價(jià)于：

<S> x<U>y u以為子樹根的葉結(jié)點(diǎn)的全體<U>**若子樹高度為1，則u還是簡單短語，最左簡單短語為句柄。若u是含有終結(jié)符的最小的短語，則為素短語，句型最左邊的素短語稱為最左素短語（P72）。例2：例1的文法G[<E>]和句型i*(<E>)容易從推導(dǎo)樹中看出：短語：i,i*(<E>),(<E>)簡單短語：i，(<E>)句柄：i素短語：i，(<E>)**文法的二義性2.4.2文法的二義性定義8：若文法G的一個(gè)句子有兩棵（或兩棵以上）的分析樹，則稱該句子是二義性的。若文法含有二義性句子，稱該文法是二義性文法，否則稱該文法是無二義的。例3：文法G1[<E>] <E>→<E>+<E>|<E>*<E>|(<E>)|i

對句子i+i*i有兩棵不同的推導(dǎo)樹**文法的二義性<E><E><E>*<E><E>+iii表示先‘＋’后‘*’表示先‘*’后‘＋’<E><E><E>+<E><E>*iii**對文法的二義性討論一個(gè)句子有兩棵不同的推導(dǎo)樹，說明其含義（語義）是不唯一的，這給編譯帶來問題（不確定）。對某些二義性文法，如果確定其中一種含義（語義）而排除另一種（或多種）含義（稱為消除二義性規(guī)則），則可將其改造成等價(jià)的無二義性文法。例4：若規(guī)定先‘*’后‘＋’及‘＋’、‘*’都是左結(jié)合 的。則文法G1[<E>]可改造為算術(shù)表達(dá)式 文法G[<E>]。這樣句子i+i*i只能有一棵推 導(dǎo)樹。**對文法的二義性討論（續(xù)）對二義性文法所產(chǎn)生的語言，有的可找到等價(jià)的無二義性文法，因此只說文法的二義性，而不說語言的二義性。當(dāng)然存在這樣的語言，不存在它們的無二義性文法。例如：L={aibjck|i=j或j=k,i,j,k

1}。文法的二義性是不可判定的，即不存在一種算法能在有限步內(nèi)判定該文法是否是二義性的。通常的做法是：找出無二義性文法的一個(gè)充分條件，即滿足條件的一定是無二義性文法。**形式語言分類2.5形式語言分類1956年Chomsky將文法分成四類：0型、1型、2型和3型文法G＝（VT，VN，P，<S>）

VN∪VT＝

V

、

VN∩VT＝φ

P中產(chǎn)生式的一般形式是α→β，α

V+,α至少含有一個(gè)非終結(jié)符，β

V*，β可以是空串。 稱文法G為

0型文法（短語結(jié)構(gòu)文法）**形式語言分類在0型文法的基礎(chǔ)上，再規(guī)定：|α|<=|β|

∵

α中至少含有一個(gè)非終結(jié)符

β不能為

稱文法G為1型文法（上下文有關(guān)文法）等價(jià)定義：

wαz→wβzw,z

V*

α

VN，β

V＋

**形式語言分類在0型文法的基礎(chǔ)上，再規(guī)定：

<A>→α，其中<A>

VN，α

V*

稱文法是2型文法（上下文無關(guān)文法）任何含有<U>→ε的產(chǎn)生式（稱為ε產(chǎn)生式）的文法不是1型文法。但是含有ε產(chǎn)生式的2型文法可以轉(zhuǎn)化為不含ε產(chǎn)生式的2型文法，轉(zhuǎn)化前后的兩個(gè)文法所生成的語言至多相差一個(gè)ε。**例1：試將如下的含有

產(chǎn)生式的上下文無關(guān)文法 （2型文法）G[<S>]轉(zhuǎn)換成等價(jià)的不含

產(chǎn)生式的 上下文無關(guān)文法。

①<S>

a<A><S> ②<S>

b ③<A>

c<S> ④<A>

解：引入非終結(jié)符<AN>與<AY>,<AN>表示不可空， 而<AY>表示可空。隨后消除可空的產(chǎn)生式以及 在產(chǎn)生式的右部去除非終結(jié)符<AY>即可，因此 G[<S>]可等價(jià)表示為：①<S>

a<AN><S> ①’<S>

a<AY><S>②<S>

b ③<AN>

c<S>④<AY>

**最后得到等價(jià)的無

產(chǎn)生式的文法G1[<S>]為：①<S>

a<AN><S> ②<S>

a<S>③<S>

b ④<AN>

c<S>注意：兩文法不同，但等價(jià)！∵語言相同。問題：什么情況下轉(zhuǎn)換前后的二個(gè)文法的語言 會(huì) 相差

呢？**在2型文法的基礎(chǔ)上，再規(guī)定：

產(chǎn)生式形式是<A>→x，<A>→x<B>，

<A>,<B>

VN，x

VT*

則稱文法是右線性文法。 若規(guī)定：x

VT

即<A>→a，<A>→b<B>， <A>,<B>

VN，a,b

VT

則稱文法是3型文法（正則文法）。正則文法也可以是左線性文法的特例。適當(dāng)?shù)匾胄碌姆墙K結(jié)符可以把一個(gè)右線性文法轉(zhuǎn)換為等價(jià)的正則文法。**例2：試將如下文法G[<S>]轉(zhuǎn)換為等價(jià)的正則文法（3型文法）：

①<S>

a<A> ②<S>

<A> ③<A>

abb<S> ④A>

c<A> ⑤<A>

a解：按正則文法的定義，只需對產(chǎn)生式②、③進(jìn)行等價(jià)變換。對產(chǎn)生式③用<A>

a<bbS> <bbS>

b<bS><bS>

b<S>來替代。**對產(chǎn)生式②則用<S>

a<bbS><S>

c<A><S>

a來替代。 因此與G[<S>]等價(jià)的正則文法G1[<S>]為：

<S>

a<A>|a<bbS>|c<A>|a <A>

a<bbS>|c<A>|a <bbS>

b<bS> <bS>

b<S>

其中<bbS>,<bS>是新引入的非終結(jié)符。**實(shí)用限制文法的實(shí)用限制 從實(shí)用的角度一般規(guī)定：文法中不含任何如下形式的產(chǎn)生式：<U>→<U>。<U>是可達(dá)的，即從開始符號<S>出發(fā)，存在推導(dǎo)<S>

*α<U>β,α、β

V*<U>是有用的，即存在終結(jié)符號串γ

VT*，使得<U>

*γ。

**文法與模型文法與模型每一類文法都對應(yīng)數(shù)學(xué)模型（識別系統(tǒng)）——自動(dòng)機(jī)。 有限狀態(tài)自動(dòng)機(jī) 3型文法 下推自動(dòng)機(jī) 2型文法 線性界限圖靈機(jī) 1型文法 圖靈機(jī)（Turing） 0型文法編譯程序的詞法分析程序使用3型文法及其數(shù)學(xué)模型有限狀態(tài)自動(dòng)機(jī)。在句法分析中使用2型文法及其數(shù)學(xué)模型下推自動(dòng)機(jī)。**習(xí)題P30習(xí)題22.52.62.82.92.11補(bǔ)充題考察如下的文法G[<S>]：

<S>→abcd<A> <A>→a

試將其轉(zhuǎn)換成等價(jià)的正則文法。**考察如下的文法G[<S>]： <S>→<A>a<B>|a <A>→<A><B>|b|

<B>→b<B>|

試重寫G[<S>]，以便消去

產(chǎn)生式。**第三章詞法分析與有限狀態(tài)自動(dòng)機(jī)詞法分析程序的主要功能是識別單詞，這將涉及3型文法、正則表達(dá)式和有限狀態(tài)自動(dòng)機(jī)。本章將討論這三者間的關(guān)系。3.1有限狀態(tài)自動(dòng)機(jī)(Finite-stateAutomate machineFA)**有限狀態(tài)自動(dòng)機(jī)3.1.1基本概念FA的非形式描述有限狀態(tài)自動(dòng)機(jī)由3部分組成：

⑴一根輸入帶：輸入帶可以理解成由一系列帶塊組成，每個(gè)帶塊上只含有一個(gè)輸入符號（終結(jié)符號），其全體構(gòu)成集合VT，特殊符號“

”表示輸入符號串的結(jié)束，

VT。

⑵一個(gè)輸入頭：初始時(shí)，輸入頭指向第一個(gè)帶塊（即指向輸入帶最左端的帶塊），輸入頭每次將輸入頭下方帶塊上的輸入符號讀入，然后輸入頭向右移動(dòng)一個(gè)帶塊。**基本概念 ⑶

一個(gè)有限狀態(tài)控制器：有限狀態(tài)控制器所能處于的狀態(tài)的全體組成狀態(tài)集合Q，Q中有若干特殊狀態(tài)：一個(gè)初始狀態(tài)q0和若干最終狀態(tài)qf。開始時(shí)有限狀態(tài)控制器處于初始狀態(tài)，以后有限狀態(tài)控制器所處狀態(tài)由狀態(tài)轉(zhuǎn)換函數(shù)

決定。**基本概念例1令VT={0,1,2,3} Q={S,A,B}2030

S是初態(tài)用‘-’表示A是終態(tài)用‘+’表示有向弧表示轉(zhuǎn)換**FA的工作過程初始時(shí)，F(xiàn)A處于初態(tài)，輸入頭指向第一個(gè)輸入符，隨著帶上符號的讀入，F(xiàn)A從一個(gè)狀態(tài)轉(zhuǎn)向另一個(gè)狀態(tài)。若遇到如下情況，F(xiàn)A結(jié)束工作：輸入頭指向‘’、FA處于終態(tài)。稱輸入串被FA接受。（如2030）輸入頭指向‘’、FA不在終態(tài)。稱輸入串不被FA接受。（如203）FA無法轉(zhuǎn)換。稱輸入串不被FA接受。（如1031）**FA的形式描述定義1：有限狀態(tài)自動(dòng)機(jī)M是一個(gè)五元組：

M＝(VT,Q,

,q0,Qf)，其中：

VT：有限非空終結(jié)符集合

Q：有限非空狀態(tài)集合

：從Q×VT到Q的冪集2Q上的狀態(tài)轉(zhuǎn)換函數(shù)

q0：初始狀態(tài)，q0

Q Qf：最終狀態(tài)集，Qf

Q|Qf|≥1

**FA的形式描述對q,q1

Q aVT(q,a)={q1}的含義為：當(dāng)前狀態(tài)為q，若輸入頭所指符號為a，則轉(zhuǎn)向下一狀態(tài)q1，輸入頭右移?！?/p>

是Q×VT 2Q上的一個(gè)單射

一般地(q,a)={q1,q2,……qn}qiQi=1,2,…n

因此稱FAM為不確定的FA，記為NFA。若映射

是Q×VT Q，即對任何q

Q，ai

VT，

(q,ai)至多只有一個(gè)元素q’，稱FAM是確定性的FA，記為DFA。**FA的形式描述對FA的拓展Q0

Q|Q0|≥1即初態(tài)可以是一個(gè)集合

：從Q×VT*到2Q上的單值映射，即輸入符可以是一個(gè)串，包括

稱M為一個(gè)傳遞圖或轉(zhuǎn)換系統(tǒng)或NFA。例1：M1＝(VT,Q,

,q0,F)VT={a,b}, Q={q0,q1,q2} F={q2}:(q0,a)=q1 (q0,b)=q2(q1,a)=q1(q1,b)=q1 (q2,a)=q2 (q2,b)=q1M1是一個(gè)DFA。 **FA的表示3.1.2狀態(tài)轉(zhuǎn)換圖和狀態(tài)轉(zhuǎn)換表狀態(tài)轉(zhuǎn)換圖：q

Q若q，q’

Q，a

VT，且q’

(q,a)，初態(tài)用‘－’標(biāo)記、終態(tài)用‘+’標(biāo)記qqq’a**狀態(tài)轉(zhuǎn)換圖例2：例1的DFAM1可表示為：—＋q0q2q1abbaa,b**狀態(tài)轉(zhuǎn)換表狀態(tài)轉(zhuǎn)換表（矩陣）表的列對應(yīng)輸入符號及特殊符號‘’，行和M的狀態(tài)q相對應(yīng)。狀態(tài)轉(zhuǎn)換表的qi行aj列中填以

(qi,aj)中的狀態(tài)。表的第一行和M的初始狀態(tài)q0相對應(yīng)；‘’這一列和最終狀態(tài)qf行的元素標(biāo)以A，以表示該狀態(tài)是最終狀態(tài)。**狀態(tài)轉(zhuǎn)換表例3：例1的DFAM1可表示為：Mab

q0q1q2q1q1q1q2q2q1A**示例例4：設(shè)計(jì)一個(gè)接受以a為頭符號和尾符號，中間可出現(xiàn)任意多個(gè)a,b的符號串的FAM。解：令：VT={a,b} Q={q0,q1,q2}a—＋q0q2q1aaa,baM是NFA**FA識別的語言格局

FAM的一個(gè)格局是二元組（q,w)qQ，w

VT*動(dòng)作 對q’

(q,a)則FAM的動(dòng)作記為：

(q,aw) (q’,w) a

VT w

VT*對w

VT*，q0是初態(tài)，稱w被FAM所接受，表示為：

(q0,w) (qf,) qfF***FA識別的語言定義2：設(shè)M是一個(gè)FA，w

VT*若：

(q0,w) (qf,) qfF q0是初態(tài) 稱w是M的一個(gè)句子。

M句子的全體稱為M的語言，記為：

L(M)={w|(q0,w) (qf,) ,w

VT*}

例5：對例4的NFAM，輸入串a(chǎn)bba

有：

(q0,abba) (q1,bba)(q1,ba) (q1,a) (q2,) ∵q2

FabbaL(M) L(M)=a|a(a|b)*a****FA的確定化定義3：對FAM與FAM’，若L(M)=L(M’)則稱M與M’等價(jià)。3.1.4FA的確定化定理3.1對任一給定的NFAM存在一個(gè)DFAM’使L(M)=L(M’)。分析： 由定理3.1L(DFA)L(NFA)

由FA的定義L(DFA)L(NFA)

得到 L(DFA)＝L(NFA)**FA的確定化證明：“構(gòu)造性證明” 對給定的NFAM＝(VT,Q,

,q0,F)

構(gòu)造一個(gè)DFAM’＝(VT’,Q’,’,q0’,F’)令VT＝

VT’Q’＝2Q 即Q’的元素是Q的子集，Q’也是有限集，|Q|=2|Q| 對aVT若({qi1,….qin},a)={qj1,…qjm}令’([qi1,….qin],a)=[qj1,…qjm]Q’M’的初態(tài)q0’=[q0]QF’中的元素由Q’中那些至少含有F中一個(gè)元素的狀態(tài)組成，即[qj1,…qjm]F’則qjkF1kn

M’是DFA**FA的確定化再證：L(M’)=L(M)，即要證xVT*

’(q0,x) [qi1,…qik,…qim]F’

(q0,x) {qi1,…qik,…qim}qikF

證明：對x的長度|x|作歸納法

1.當(dāng)|x|=0時(shí)，結(jié)論成立

2.假定|x|<n，結(jié)論成立

3.當(dāng)|x|=n, 由’的定義，結(jié)論成立****FA的確定化例6：例4的M是NFA可用表的形式表示為：Mab

q0{q1,q2}q1{q1,q2}{q1}q2{q2}AM’ab

[q0][q1,q2][q1,q2][q1,q2][q1]A[q1][q1,q2][q1]確定化**FA的最小化3.1.3FA的最小化一般地說，對給定的一個(gè)FAM，可以找到任意多個(gè)不同的FAM’，有L(M)=L(M’)，因此得到最小的FA是有意義的。定義4：若FA的二個(gè)狀態(tài)q與q’，對任意一個(gè)長度為k或小于k的符號串w，q接受w當(dāng)且僅當(dāng)q’接受w，稱q與q’是k等價(jià)的，否則稱q與q’是k可區(qū)分的。q與q’等價(jià)的充要條件是對k0，q與q’是k等價(jià)的。**FA的最小化狀態(tài)分離法基本思想：對DFA的狀態(tài)集Q進(jìn)行k等價(jià)類劃分，即將Q劃分成Qk1,….Qkn的n個(gè)子集，子集中的狀態(tài)是k等價(jià)的。然后進(jìn)行k+1的等價(jià)類劃分……直至無法進(jìn)一步劃分為止。 則得到的等價(jià)子集中各狀態(tài)等價(jià)，可合并為一個(gè)狀態(tài)。**狀態(tài)分離法具體做法：0等價(jià)類劃分：將Q劃分成F與Q-F二個(gè)0等價(jià)類。若已經(jīng)進(jìn)行了k等價(jià)類劃分，Q已經(jīng)被劃分成Q1，…，Qn（n2)n個(gè)子集，進(jìn)行k+1等價(jià)類劃分。對Qi(i=1…n)q,q’Qi，若有aVT，

（q，a）Qj和

（q’，a）Ql，j≠l或

（q，a）存在而

（q’，a）不存在或反之。則將Qi劃分為二個(gè)子集Qi1，Qi2，使qQi1，q’Qi2

。重復(fù)2直至無法進(jìn)一步劃分為止。**狀態(tài)分離法對每一個(gè)子集Qi(i=1…n)，任選一個(gè)代表qi，并修改

，修改方法為： 轉(zhuǎn)向Qi中任何一個(gè)狀態(tài)改成轉(zhuǎn)向qi

。若一個(gè)狀態(tài)子集中某一狀態(tài)是原來的開始狀態(tài)，則該狀態(tài)子集的代表就是新的有限狀態(tài)自動(dòng)機(jī)的開始狀態(tài)。同理，若一個(gè)狀態(tài)子集中的狀態(tài)均是最終狀態(tài)，則該狀態(tài)子集的代表就是新的有限狀態(tài)自動(dòng)機(jī)的最終狀態(tài)。抹去可能存在的無用狀態(tài)與不可及狀態(tài)。則DFAM是最小的（或簡化的）。**狀態(tài)分離法例7：試將下圖中所示的有限狀態(tài)自動(dòng)機(jī)M最 小化。**例7續(xù)一解：最小化的過程為：初始時(shí)的劃分由2個(gè)子集組成，即：（{A,B,C},{D,E,F,G}）集合{D,E,F,G}不需要進(jìn)一步劃分，考察子集{A,B,C}。由于

（B,a）=D

{D,E,F,G}，而

（A,a）＝

（C,a）＝B

{A,BC}，因此Q可進(jìn)一步劃分為：（{A,C},{B},{D,E,F,G}）。由于

（A,b）＝C

{A,C}， 而

（C，b）＝E

{D,E,F,G}。因此Q可進(jìn)一步劃分為：（{A},{C},{B},{D,E,F,G}）**例7續(xù)二這時(shí)不能再劃分了，得到的最小化的有限狀態(tài)自動(dòng)機(jī)如下表所示：

Mab

ABCCBDBDCDDDF**習(xí)題P55習(xí)題31.3.22.3.33.補(bǔ)充題將如下所示的非確定有限狀態(tài)自動(dòng)機(jī)M確定化和最小化。

**試給出下述每個(gè)有限狀態(tài)自動(dòng)機(jī)所識別的語言

a)b)**c)**正則表達(dá)式（REX)3.2正則表達(dá)式（RegularExpression）、有限狀態(tài)自動(dòng)機(jī)、3型文法及其相互間的關(guān)系正則表達(dá)式又稱正規(guī)式有限狀態(tài)自動(dòng)機(jī)(FA)是正則文法（3型文法）的數(shù)學(xué)模型，正則表達(dá)式（REX）所表示的值，即為FA所能接收的語言的全體，因此這三者的關(guān)系可用下圖表示：FA3型文法REX**正則表達(dá)式通常稱有限狀態(tài)自動(dòng)機(jī)和三型文法所接受的語言為正則語言。REX在詞法分析中有很重要的作用，它可以精確地表示單詞符號的組成，定義單詞符號集。3.2.1正規(guī)式與正規(guī)集如程序設(shè)計(jì)語言中的標(biāo)識符（ID）可以用REX表示為：Let(let|Dig)*

其中Let是字母、Dig是數(shù)字**正則表達(dá)式定義1：設(shè)

是字母表。

上的REX及其值——REX所表示的符號串集合（正規(guī)集）遞歸定義如下：

⑴ф、ε是正則表達(dá)式，其值表示空集和{ε}；⑵對

中每一字母ai

，ai是正則表達(dá)式，其值表 示集合{ai}；

⑶若p,q是REX，值分別為L(p)和L(q)， 則p|q，p·q和p*也是

上的REX， 其值分別是：L(p)∪L(q)，L(p)·

L(q)，

L(p)*。

⑷有限次使用上述規(guī)則得到的仍是

上的REX。**正則表達(dá)式規(guī)則：優(yōu)先級由高到低為：*，·,|?？捎谩ā?，‘）’改變優(yōu)先級。記R*R為R+

值L(R+)=L(R*)L(R)。性質(zhì)交換律 R|S=S|R結(jié)合律 R|(S|T)=(R|S)|TR(ST)=(RS)T分配律 R(S|T)=RS|RT (R|S)T=RT|ST同一律 εR=Rε=R**正則表達(dá)式例1．試寫出

＝{0，1}上下述集合的REX：

⑴所有以1開始和結(jié)束的符號串。

⑵恰含有3個(gè)1的所有符號所組成的集合。

⑶集合{01，1}。

⑷所有以111結(jié)束的符號串。 解答：

⑴1(0|1)*1|1 ⑵0*10*10*10* ⑶01|1 ⑷(0|1)*111**正則表達(dá)式與有限狀態(tài)自動(dòng)機(jī)3.2.2REX和FA定理3.2（Kleene)設(shè)R是

上的一個(gè)REX，則存在一個(gè)FAM，有L(M)=L(R)。反之亦然。證：1.對給定的REX到FA從REX構(gòu)造FA可以分兩步進(jìn)行。從REXR到傳遞圖T

XYR－＋**Kleene定理

反復(fù)應(yīng)用下述替代規(guī)則，直至所有有向弧都以

中的符號或標(biāo)記

為止。

A|B

**Kleene定理②消除應(yīng)用①所得到的傳遞圖中的ε弧，可以分為兩步：首先消除ε環(huán)路，其次消除其他ε弧。a)ε環(huán)路的消除方法：

i．將ε環(huán)路的諸項(xiàng)合并為一個(gè)頂點(diǎn)。

ii．修改各個(gè)相關(guān)的有向弧。

iii．若ε環(huán)路中某一狀態(tài)是最終（或初始）狀 態(tài)，則新頂點(diǎn)是最終（或初始）狀態(tài)。b）其它ε弧的消除有兩種方法：1）子集法：即計(jì)算ε-Closure（T），其表示從狀態(tài)集T中任何一狀態(tài)沿ε弧可以到達(dá)的狀態(tài)全體。

**Kleene定理

其要點(diǎn)是：從初始狀態(tài)q0的X=ε-Closure（q0）開始，按如下方法構(gòu)造狀態(tài)集：i．令Set＝{X}；ii．若Set中還有未考察過的狀態(tài)子集Xi，則對于每一輸入符號a

VT，計(jì)算：

T=ε-Closure（move（Xi,a）），Set=Set∪{T}（其中move(Xi,a)={q|q

δ(p,a),p

Xi}）。重復(fù)執(zhí)行（ii），直至不存在這樣的Xi。這樣得到的Set即為消除ε弧后的DFA。DFA的初始狀態(tài)就是ε-Closure（q0），最終狀態(tài)由那些至少含有一個(gè)最終狀態(tài)的狀態(tài)子集組成。**Kleene定理2）逐步消除法： 其要點(diǎn)是找到類似于下圖所示，但從B再無ε弧引出的ε弧。 刪除狀態(tài)A到狀態(tài)B的ε弧，對每一條從狀態(tài)B到狀態(tài)C標(biāo)記為ai的弧，增加1條從狀態(tài)A到狀態(tài)C標(biāo)記為ai的弧。若B是最終狀態(tài)，則讓A為最終狀態(tài)。重復(fù)上述過程直至消除全部的ε弧，這樣得到的一般是NFA。

**Kleene定理例2：試給出與下圖所示的傳遞圖等價(jià)的、確定的、最小的有限狀態(tài)自動(dòng)機(jī)。

**例2（續(xù)一）解法一子集法：

M的初始狀態(tài)為D，而ε–Closure(D)={D，E，G}

令A(yù)={D，E，G}，B={D，E，F(xiàn)，G} ∵VT={0，1} ∴ε–Closure(move(A，1))={D，E，F(xiàn)，G} ε–Closure(move(A，0))={F} ε–Closure(move(F，1))={G} ε–Closure(move(G，1))={D，E，G} ε–Closure(move(B，1))={D，E，F(xiàn)，G} ε–Closure(move(B，0))={F}**例2（續(xù)二）所以，DFAM如下表所示： 其中A={D,E,F,G}、B={D,E,G}。

注意：狀態(tài)F與表示該狀態(tài)是最終狀態(tài)的標(biāo)記F的不同。

**例2（續(xù)三）解法二逐步消除法：

a)消除狀態(tài)E到G的ε弧：

**例2（續(xù)四）b)消除狀態(tài)D到E的ε?。?/p>

**例2（續(xù)五）消除所有ε弧后得到的狀態(tài)表

**例2（續(xù)六）c)確定化的DFA如下表所示：

**Kleene定理從傳遞圖T到REX設(shè)傳遞圖T為：逐步消除個(gè)狀態(tài)或弧得到只剩狀態(tài)X、Y，消除方法為：略。得到：—εSabc…………dfεεf1f2XY+—RXY＋**正則表達(dá)式與有限狀態(tài)自動(dòng)機(jī)例3：設(shè)V={a,b},V上的正則表達(dá)式R={ba|a}+

：試設(shè)計(jì)接收R所表示的符號串集合的確定的，最小的有限狀態(tài)自動(dòng)機(jī)M。

解：正則表達(dá)式R可等價(jià)地改寫為：R=(ba|a)*(ba|a)或R=(ba|a)(ba|a)*。有限狀態(tài)自動(dòng)機(jī)M=(V,Q,δ,q0,Qf)，其中V={a,b},Q={S,A,B}，q0=S，Qf={B}，

δ如下圖所示,顯然M是確定的和最小的。

****3.2.3有限狀態(tài)自動(dòng)機(jī)與3型文法定理3.3對任一正則文法G，存在有限自動(dòng)機(jī)M，使得L(M)=L(G)。反之亦然。 證：1.設(shè)G[<S>]=（VN，VT，p，<S>），令與其對應(yīng)的M＝（VT，Q，

，<S>，Qf)其中：

①VT，<S>相同，即<S>作為M的開始狀態(tài)。

②令Q＝VN∪{F}，F(xiàn)

VN ③若<A>→a<B>

P，讓

（<A>,a）中含有<B>

若<A>→a

P，讓

（<A>,a）中含有F

a

VT，令

（F，a）＝φ ④

令Qf＝{F}

容易證明L(M)=L(G)。(例見P47）**設(shè)M是DFAM＝（VT，Q，

，<S>，Qf），令與其對應(yīng)的G[<S>]=（VN，VT，p，<S>），其中：

①VT，<S>相同，VN＝Q ②若

（<B>,a）＝C，<B>

Q，C

Qf， 讓<B>→a<C>

P

若

（<B>,a）＝C，<B>

Q，C

Qf，讓 <B>→a

P或<B>→a<C>

P

容易證明L(M)=L(G)。 （例見P49）**3.2.4正則表達(dá)式與正則文法定理3.4對任一正則文法G，存在REXR，使得L(R)=L(G)。反之亦然。 證：一、從正則文法G到REXR 1.將G中每個(gè)非終結(jié)符表示為關(guān)于它的正則式方程，得到一個(gè)聯(lián)立方程組。 即對<A>→a<B>|b為：<A>＝a<B>＋b2.如<A>＝a<A>＋b則解為：<A>＝a*＋b3.利用REX的分配律、結(jié)合率和交換律求正則式方程組的解R。容易證明L(R)=L(G)。 （例見P36）**二、從REXR到正則文法G對V上的REXR及正則文法G=（VN，VT

，p，<S>）VT=

V。

R讓<S>→R。如a，b是REX，則對形如<A>→ab的產(chǎn)生式轉(zhuǎn)換為<A>→a<B>及<B>→b，<B>

VN

。對形如<A>→a*b轉(zhuǎn)換為<A>→a<A>|b。重復(fù)使用規(guī)則3.和4.，直至每個(gè)產(chǎn)生式至多含有一個(gè)非終結(jié)符。容易證明L(R)=L(G)。（例見P37）**例4：對例3的REXR=(ba|a)*(ba|a)，試設(shè)計(jì)接收R所表示的符號串集合的正則文法G。

解：正則文法G={VT,VN,P,<S>}，其中 VT={a,b}，VN={<S>,<A>,<B>}先讓<S>

(ba|a)(ba|a)*并轉(zhuǎn)換為：<S>

(ba|a)<A><S>

ba<A>|a<A><A>

(ba|a)*<A>

ba<A>|a<A>|ε<S>

ba<A>| <S>

b<B> <B>a<A><A>

ba<A>| <A>

b<C> <C>a<A>注意：<C>可以改為<B>以及消除ε的方法，得：**P為：

<S>

a<A>|b<B>|a<A>

a<A>|b<B>|a <B>

a<A>|a

**習(xí)題P55習(xí)題33.13.43.53.63.73.83.93.103.11**§3.3詞法分析程序的設(shè)計(jì)和實(shí)現(xiàn)詞法分析程序從輸入串中識別單詞。單詞的構(gòu)詞規(guī)則可由狀態(tài)轉(zhuǎn)換圖（FA）或REX表示。將FA確定化、最小化即得到識別單詞的FA。編程實(shí)現(xiàn)FA，即得到詞法分析程序。**1.詞法分析程序的任務(wù)及環(huán)境詞法分析程序的任務(wù)是：a)識別源程序組成的輸入符號中語義獨(dú)立的最小的詞法單位—單詞（token）。b)刪除注解和其他與輸入介質(zhì)相關(guān)的符號（如空格、回車等）。c)報(bào)告各種不符合程序設(shè)計(jì)語言規(guī)定的詞法錯(cuò)誤。d)符號表的維護(hù)（插入、查找…)**單詞符號的種類單詞是程序語言最基本的語法單位,通常有五種:(1) 基本字：有的稱關(guān)鍵字或保留字,如if、while、for、do、goto等(2) 標(biāo)識符：用戶定義各種變量、數(shù)組、函數(shù)、過程等的名字，以字母打頭后接若干個(gè)字母、數(shù)字。如X2、Len、getword……(3) 常數(shù)：如216、31.4……(4) 運(yùn)算符：如+、=、*、/等；(5) 界限符：如;、:、(、)及雙字符界符:=、/*、*/及空白符等。（1）、（4）、（5）?？珊蠟橐?，分為單、雙字符界限符。**單詞的編碼 詞法分析程序輸出的是統(tǒng)一格式的單詞，形式為：(type,value,lineNo,columnNo)

一般可分為三類：標(biāo)識符：表示為（ID,addr)，addr是標(biāo)識符在符號表的位置。常數(shù)：表示為（N,addr）addr是常數(shù)在常數(shù)表的位置。界限符：表示為（DEL,code)，將關(guān)鍵字、運(yùn)算符、單（雙）界限符統(tǒng)一預(yù)先編號，則code為界限符的內(nèi)部碼。 **詞法分析程序的實(shí)現(xiàn)可以有兩種方案：把詞法分析程序視為語法分析部分的一個(gè)子程序，每調(diào)用一次詞法分析程序就掃描一個(gè)單詞。把詞法分析程序視為編譯程序的一個(gè)獨(dú)立模塊，詞法分析程序一次掃描全部的輸入符號。常用的方法是a），優(yōu)點(diǎn)是不用形成中間文件，直接生成符號表。**2. 詞法分析程序的設(shè)計(jì)識別單詞的FA的設(shè)計(jì)：0137空白字母|數(shù)字字母非字母與數(shù)字＋＋數(shù)字?jǐn)?shù)字非數(shù)字界限符非法字符

2456＋＋＋**狀態(tài)2的處理流程：

查保留字得內(nèi)部碼，輸出（DEL，code） 查或送符號表 得到addr,輸出（ID,addr)狀態(tài)4的處理流程： 檢查前一單詞，決定正負(fù)號 轉(zhuǎn)換相應(yīng)的常數(shù)表示（二、八、十六進(jìn)制） 查或送常數(shù)表得到addr，輸出（N,addr)YN**狀態(tài)5的處理流程：

若為‘.’ 按小數(shù)點(diǎn)處理，轉(zhuǎn)狀態(tài)4

取下一字符 是否為雙字符界限符 查表得到內(nèi)部碼， 輸出（DEL，code)

回送，查表得到內(nèi)部碼，輸出（DEL，code)狀態(tài)6的處理流程：報(bào)錯(cuò)Y

Y

N

N

**說明上述的FA只是一個(gè)粗框架，具體實(shí)現(xiàn)時(shí)應(yīng)根據(jù)不同語言的詞法規(guī)則，作必要的改進(jìn)和相應(yīng)的處理。特定要求的處理：如true、false表示真、假常數(shù)：NOT、IN等是運(yùn)算符；.EQ.表示邏輯相等；允許0x1f、35L等作常數(shù)等等。無符號數(shù)的識別： 如無符號數(shù)用REX表示為：

(D+E|D+.D+E|E|.D+E)((+|-)D|D)D*|D+|D*.D+

其中D表示數(shù)字0，1，……，9，則相應(yīng)的最小的DFA為：**0213456－EE+DD－DD.D.E+D+＋D**超前搜索 在FORTRAN語言中，關(guān)鍵字不是保留字，空格不是分隔符。因此：對語句

100DO110I=1，10

（循環(huán)語句，DO是關(guān)鍵字）

100DO110I=1.10

（賦值語句，DO110I是標(biāo)識符）拼字與緩沖區(qū)的組織P22的左、右兩區(qū)的緩沖區(qū)組織形式。用getline();讀入一行，如:char*fgets(char*S,intn,FILE*fp)

這樣拼字時(shí)只需移動(dòng)緩沖區(qū)指針即可。

while(*chp==‘’)chp++; **3.詞法分析程序的實(shí)現(xiàn)FA的狀態(tài)轉(zhuǎn)換圖可以視為一個(gè)程序的粗框圖：

FA 程序 狀態(tài) 子程序（程序段） 狀態(tài)轉(zhuǎn)換 程序的控制流

**§3.4詞法分析程序的自動(dòng)生成

見P181附錄A**第四章語法分析§4.1概述§4.1.1語法分析方法 語法（句法）分析的任務(wù)是根據(jù)程序設(shè)計(jì)語言的語法規(guī)定，對輸入的單詞流進(jìn)行分析，判定是否構(gòu)成了合法的句子，并盡可能多的找出語法錯(cuò)誤。句法分析方法可分兩大類：**句法分析方法分類自頂向下（Top-Down)分析方法 以文法的開始符號為分析樹的根，向下逐步構(gòu)造分析樹，每次以樹中最左非終結(jié)符為子樹的根向下形成新的子樹（最左推導(dǎo)），直至分析樹的葉結(jié)點(diǎn)形成輸入串。此時(shí)稱輸入串是合法的句子，否則輸入串非法（報(bào)錯(cuò)）。自底向上（Bottom-Up)分析方法 從輸入串出發(fā)，向上逐步構(gòu)造分析樹，每次尋找當(dāng)前句型的句柄（或最左素短語）進(jìn)行歸約（最右推導(dǎo)的逆），直至歸約出文法的開始符號。此時(shí)稱輸入串是合法的句子，否則輸入串非法（報(bào)錯(cuò)）。**下推自動(dòng)機(jī)（PDA）與2型文法§4.1.2下推自動(dòng)機(jī)(Push-DownAutomation)與2型文法3型文法及其數(shù)學(xué)模型FA由于其本身的局限性不能勝任句法分析。例如：判定表達(dá)式中的括號配對問題：L={anbn|n0}引入2型文法和PDA <A>→ (VN∪VT)*

在FA中增加一個(gè)下推棧并要求控制器能控制棧的操作，這就是PDA。 **下推自動(dòng)機(jī)定義1：非確定的PDAM是一個(gè)七元組： M＝（VT，Q，

，

，q0，Z0，QF），其中，VT是有限的輸入字母表； Q是有限的狀態(tài)集合；

是有限的棧字母表； q0是初始狀態(tài)，q0

Q； Z0

，是棧底符號；

是一個(gè)從Q×

×（VT∪{

}） 到Q×

*的冪集上的映射； QF是最終狀態(tài)集，QF

Q。

**下推自動(dòng)機(jī)下推自動(dòng)機(jī)有兩類動(dòng)作。 第一類動(dòng)作每一步?jīng)Q定于三個(gè)信息：

⑴有限控制器所處的狀態(tài)qi，qi

Q；

⑵下推棧的棧頂符號A，A

；

⑶當(dāng)前輸入符號a，a

VT。這類動(dòng)作表示成：

（qi，a，A）={(qi1,α1),…,(qik,αk)}， 它表示：當(dāng)下推自動(dòng)機(jī)處于狀態(tài)qi、 當(dāng)前輸入符號為a、 下推棧棧頂符號是A時(shí)， 下推自動(dòng)機(jī)可以進(jìn)入狀態(tài)qij，且αj代替棧頂符號是A（j＝1，2，…,k），然后輸入頭向右移動(dòng)一個(gè)帶塊。**下推自動(dòng)機(jī)第二類動(dòng)作為：

（qi，

，A）={(qi1,α1),…,(qik,αk)}， 稱為

動(dòng)作。表示：PDA處于狀態(tài)qi，不論當(dāng)前輸入符是什么，只要棧頂符號為A，則下一狀態(tài)可以是qij中的任意一個(gè)，且用αj替代A，輸入頭不動(dòng)。注意：由αj

*而αj可以為

這表示讓A出棧。問題：1.為什么不定義

（qi，a，

）？

2.若不讓A出棧，而只讓αj進(jìn)棧，如何表 示？

**確定的下推自動(dòng)機(jī)PDAM是確定性的，當(dāng)且僅當(dāng)：

⑴對于任何q

Q，a

VT∪{

}及A

，

（q，a，A）只含有一個(gè)元素。

⑵

對于q

Q，A

，當(dāng)

（q，

，A）非空， 則對于任何一個(gè)a

VT，

（q，a，A）為空。**下推自動(dòng)機(jī)的格局下推自動(dòng)機(jī)的當(dāng)前格局是一個(gè)三元組 （q，w，α），q

Q、w

VT*、α

*。格局變換記為： （q，aw，XαZ0） （qi，w，αiαZ0）

（q，a，X）＝{（q1，α1），…，（qm，αm）}q,qi

Q、a

VT、w

VT*、x,Z0

、α,αi

***下推自動(dòng)機(jī)接受的語言PDAM接收輸入字符串w可以采用兩種方式：i）空棧接收：（q0，w，Z0）（q，

，Z0）ii）最終狀態(tài)接收：（q0，w，Z0）（qf，

，α），qf

Qf，α

*。一般采用空棧方法來定義輸入串w為下推自動(dòng)機(jī)M所接收。即先下推一個(gè)棧底符號Z0，一旦輸入頭所遇到的符號是輸入串的結(jié)束符號‘

’，棧頂符號是‘Z0’，則表示輸入串w為下推自動(dòng)機(jī)所接收?？梢宰C明（Chomsky)空棧接收與最終狀態(tài)接收是等價(jià)的。（接受的語言集合相同）****下推自動(dòng)機(jī)在確定的句法分析中（無論是自頂向下還是自底向上），由于采用的是單狀態(tài)的下推自動(dòng)機(jī)，因此狀態(tài)變換可省略，下推自動(dòng)機(jī)的控制器可簡化為圖或表的形式，主要描述入棧和出棧的控制。(見P66圖4.3）例1：試設(shè)計(jì)能檢查左右括號是否配對的PDA。

L={anbn|n>=0}<A>

a