教學課件-編譯原理

編譯原理概述《編譯原理》第1講課程簡介-3-第1講概述

課程名稱編譯原理教材

《編譯方法》第2版機械工業(yè)出版社賀汛等編著教學內(nèi)容程序設計語言的編譯過程及方法（詳見目錄）

教學方式課堂講授

參考資料

《程序設計語言編譯原理》建議和要求-4-第1講概述課程有一定難度，做好心理準備。課前預習，帶著問題聽課，積極回答問題參與討論。認真聽講，以聽為主，務必聽懂。問題及時解決。作業(yè)認真、獨立、及時（盡快）。用好教材。內(nèi)容提要-5-第1講概述1.3編譯技術的應用1.2編譯程序1.1程序設計語言與程序1.1程序設計語言與程序-6-第1講概述1.1.2程序設計語言的分類

1.1.3程序及其結(jié)構

1.1.4高級語言程序的處理過程

1.1.1程序設計語言的定義1.1.1程序設計語言的定義-7-第1講概述程序設計語言語義語用語法說明程序的結(jié)構和形式的一組規(guī)則語法單位的實際含義程序與使用者的關系1.1.2程序設計語言的分類-8-第1講概述機器語言匯編語言高級語言特定應用語言邏輯約束語言1.1.3程序及其結(jié)構-9-第1講概述voidQ(){Q的局部數(shù)據(jù)定義

……R();……Q();……}main(){Main的局部數(shù)據(jù)定義

……}voidR(){R的局部數(shù)據(jù)定義

……}1.C語言

一個主函數(shù)main、若干（可以為0）個子函數(shù)。1.1.4高級語言程序的處理過程-10-第1講概述絕對機器代碼程序可再裝配的機器代碼程序匯編程序源程序需預處理的源程序預處理編譯匯編裝配／連接1.2編譯程序-11-第1講概述1.2.2編譯過程和編譯程序結(jié)構

1.2.3編譯程序的生成

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

1.2.1編譯與解釋1.2.1編譯與解釋-12-第1講概述

編譯程序

源程序目標程序錯誤信息高級語言程序的翻譯方式:解釋、編譯編譯

:將高級語言程序翻譯成另一種語言的等價程序。源程序、目標程序和編譯程序的關系：1.2.1編譯與解釋-13-第1講概述解釋：翻譯一句執(zhí)行一句，邊翻譯邊執(zhí)行，直到程序結(jié)束。與編譯的區(qū)別：不生成等價的目標代碼程序。

優(yōu)點：解釋方式便于程序的調(diào)試。（編譯方式只需翻譯一次，且目標程序的執(zhí)行速度快）1.2.2編譯過程和編譯程序結(jié)構-14-第1講概述詞法分析語義分析和中間代碼生成目標代碼生成目標程序代碼優(yōu)化語法分析源程序出錯處理表格管理1.編譯過程1.2.2編譯過程和編譯程序結(jié)構-15-第1講概述（1）詞法分析主要任務：

從左到右掃描源程序，逐一讀入構成源程序的字符流，

識別出其中的一個個單詞，識別出的單詞稱單詞符號，也簡稱符號。單詞是高級語言程序中有實際意義的最小語法單位。單詞構成規(guī)則——

詞法規(guī)則或構詞法

（單詞識別的依據(jù)）單詞內(nèi)碼形式——二元式（指出了單詞的類別和自身值）1.2.2編譯過程和編譯程序結(jié)構-16-第1講概述例：z=x+a%3*(int)(x+y)%2/7;（1）（標識符，z

）（2）（等號，=）（3）（標識符，x

）（4）（加號，+）（5）（標識符，a）（6）（取余號，%）（7）（整數(shù)，3）（8）（乘號，*）（9）（左括號，(）（10）（保留字，int

）（11）（右括號，)）（12）（左括號，(）（13）（標識符，x

）（14）（加號，+）（15）（標識符，

y

）（16）（右括號，)）（17）（取余號，%）（18）（整數(shù)，2）（19）（除號，/）（20）（整數(shù)7）（21）（分號;）1.2.2編譯過程和編譯程序結(jié)構-17-第1講概述（2）語法分析任務

“組詞成句”，根據(jù)單詞分析出組成源程序的各類語法單位，并指出其中的語法錯誤。語法單位——由源程序的單詞構成（如表達式、語句、……乃至整個程序。）語法單位的構成規(guī)則——語法規(guī)則。

一個語言的詞法規(guī)則和語法規(guī)則定義了一個程序的形式結(jié)構。語法單位的表示——語法樹1.2.2編譯過程和編譯程序結(jié)構-18-第1講概述＜賦值語句＞＜整數(shù)＞＝

x

z

＜變量＞＜表達式＞

y

%*

+

3

a＜表達式＞＜表達式＞＜表達式＞＜表達式＞＜表達式＞＜表達式＞＜變量＞＜變量＞＜變量＞例：z=x+a%3*y1.2.2編譯過程和編譯程序結(jié)構-19-第1講概述例：z=x+a%3*y

（1）（%a3t1）（2）（*t1y

t2）（3）（+x

t2t3）（4）（=t3_z

）（3）語義分析和中間代碼生成任務：分析出語法單位具體的動作意義，進行初步翻譯，生成與源程序等價的中間代碼程序。語義:

定義一個程序所表示的意義,用語義規(guī)則描述。中間代碼：指令應結(jié)構簡單、含義明確，易于實現(xiàn)源程序——中間代碼

——目標代碼三者之間的轉(zhuǎn)換。中間代碼常用形式：逆波蘭式、三元式、四元式等。四元式：

（運算符，對象1，對象2，結(jié)果）1.2.2編譯過程和編譯程序結(jié)構-20-第1講概述（1）（%a3t1）（2）（*t1y

t2）（3）（+x

t2t3）（4）（=t3_z

）

（4）代碼優(yōu)化任務：

對中間代碼進行等價的加工變換，以便生成更有效更節(jié)省時間和空間的目標代碼。例：z=x+a%3*y

的四元式序列：代碼優(yōu)化的技術：

刪除公共子表達式、強度削弱、代碼外提、合并已知量....

注：此階段并非編譯程序所必需。（1）（%a3t1）（2）（*t1y

t2）（3）（+x

t2z

）1.2.2編譯過程和編譯程序結(jié)構-21-第1講概述（5）目標代碼生成任務：將中間代碼程序變換成目標代碼程序。

目標代碼：

特定機器上的絕對指令代碼可重定位的指令代碼

匯編指令代碼這一階段任務的實現(xiàn)與硬件系統(tǒng)的結(jié)構、目標指令的選擇、變量存儲空間的分配、寄存器的調(diào)度等均有關系。1.2.2編譯過程和編譯程序結(jié)構-22-第1講概述出錯處理：若編譯過程中發(fā)現(xiàn)源程序有錯誤，就應進行出錯處理。

（6）表格管理和出錯處理涉及編譯的每個階段！

遍布編譯的每個階段！表格管理

：為完成編譯而建立并使用一些表格，以記錄各種信息。信息登錄：編譯的各個階段（尤其是詞法語法、語義分析階段）。信息使用：各階段的分析和翻譯。1.2.2編譯過程和編譯程序結(jié)構-23-第1講概述

說明：以上為編譯過程的典型的處理模式。并非所有的編譯過程都有這些階段。（可以不生成中間代碼、不進行代碼優(yōu)化）常將編譯的這五個階段劃分成兩大部分：前三個階段——

分析部分后兩個階段——

綜合部分1.2.2編譯過程和編譯程序結(jié)構-24-第1講概述詞法分析程序語義分析和中間代碼生成程序目標代碼生成程序目標程序代碼優(yōu)化程序語法分析程序源程序出錯處理程序表格管理程序2.編譯程序結(jié)構1.2.2編譯過程和編譯程序結(jié)構-25-第1講概述后端程序：由與源語言無關，與中間代碼有關，主要依賴于目標機的工作組合而成。（與目標機有關的代碼優(yōu)化、目標代碼生成、相關的表格管理和出錯處理等。）前端程序：由那些主要依賴于源語言，而與目標機無關的工作組合而成。（詞法分析、語法分析、語義分析與中間代碼生成、某些目標機器無關的代碼優(yōu)化，以及此間的表格管理、和出錯處理等。)（1）“前后端”組合方式1.2.2編譯過程和編譯程序結(jié)構-26-第1講概述作用：

后端語言1前端語言2前端語言n前端語言1編譯語言2編譯語言n編譯………………

前端機器2后端機器2編譯機器1后端機器1編譯機器n后端機器n編譯…………1.2.2編譯過程和編譯程序結(jié)構-27-第1講概述（2）按“遍”組合方式“遍”：對源程序或等價的中間語言程序從頭到尾掃描，完成規(guī)定的任務，并生成新的中間結(jié)果或目標程序，稱一“遍”。

在一“遍”中可完成編譯的一個或多個階段的任務。

源語言的特征和機器的特征決定編譯程序究竟可以劃分成幾“遍”。1.2.2編譯過程和編譯程序結(jié)構-28-第1講概述第二遍第一遍第三遍中間代碼中間代碼C語言源程序目標代碼（匯編）詞法分析、語法分析、語義處理（生成中間代碼）

代碼優(yōu)化

目標代碼生成

1.2.3編譯程序的生成-29-第1講概述編譯程序的構造與三個方面有關源語言

結(jié)構、含義和用途等。是準確描述語言、構造編譯程序的出發(fā)點。

目標語言

結(jié)構、指令系統(tǒng)、存儲分配方式、外設管理方式、文件管理方法等。是編譯過程中應考慮的問題。

編譯方法

翻譯的具體方法。由源語言特性、目標語言特性、對編譯程序性能要求等決定。1.2.3編譯程序的生成-30-第1講概述

1．用機器語言編寫

復雜，不實用。

2．匯編語言編寫

對具體的硬件環(huán)境的依賴性較高，程序過長，也不常用。但有些編譯程序的核心部分常用匯編語言編寫。

3．其他高級語言編寫

最方便、最常用。1.3編譯技術的應用1．語言的結(jié)構化編輯器2．查詢解釋器3．硅編譯器-31-第1講概述本講小結(jié)（1）編譯的功能；編譯與解釋的區(qū)別。（2）編譯階段的劃分；每個階段的任務；編譯程序的結(jié)構。（3）編譯程序的“前后臺”、按“遍”組合方式。-32-第1講概述課后1.看書2.思考題：P141～7參考資料：《編譯方法學習指導與實踐》預習題第2章的主題是什么？為什么要講這個主題？涉及哪幾個問題？-33-第1講概述編譯原理形式語言和文法的基本概念《編譯原理》第2講內(nèi)容提要-36-第2講形式語言和文法基本概念2.1形式語言2.5典型例題2.4文法的二義性2.3文法的分類和化簡2.2文法2.1形式語言-37-第2講形式語言和文法基本概念

2.1.1語言的概念

2.1.2語言的定義方式2.1.1語言的概念-38-第2講形式語言和文法基本概念語言：某字母表中的符號構成的符號串的集合。1.什么是語言符號串中符號的來源元素句子有一定構成規(guī)則語言的描述工具——文法2.1.1語言的概念-39-第2講形式語言和文法基本概念（1）有窮字母表

一個元素的非空有窮集合，其中的元素也稱符號。每個語言均有一固定的字母表。常用V、Σ或其他大寫字母表示例如V={0，1}，Σ={a，b，c，d，e}等1.符號串的相關概念2.1.1語言的概念-40-第2講形式語言和文法基本概念（2）符號串：字母表中的符號組成的任何有窮序列。長度：

符號串中符號的個數(shù)。

符號串x的長度表示為｜x｜，｜x｜=m≥0。1.符號串的相關概念【例2-1】Σ={a，b，c，……，z}，x=“l(fā)augh”，則|x|=5

Σ={I，you，he，am，is，are，a，student}，

y=“Iamastudent”，空格不計算長度，則|y|=4?？辗柎簾o任何符號的串，簡稱空串，用ε表示，|ε|=0

省略寫法：

z=x……

z=……x

z=……x……2.1.1語言的概念-41-第2講形式語言和文法基本概念（3）符號串的運算1.符號串的相關概念x1=x

，x2=xx

，x3=xxx

，……若n>0，則有：xn=xxn-1=xn-1xx*表示x的任意多次方冪（可以是0次）x+

表示x的任意非0次方冪?！纠?-3】

若x=“ab”

則x0=ε

x1=“ab”

x2=“abab”x3=“ababab”……方冪：符號串x的方冪就是n個x自身連接，表示為xn

。

規(guī)定x0=ε2.1.1語言的概念-42-第2講形式語言和文法基本概念（4）符號串的集合：若集合A中的所有元素都是某字母表上的符號串，則稱A為該字母表上的符號串集合。1.符號串的相關概念【例2-4】

若U={a，b}，V={c，d}

則UV={ac，ad，bc，bd}乘積：

兩符號串集U、V的乘積為

UV={αβ|α∈U∧β∈V

｝

成立的等式：{ε}U=U{ε}=U

Vn=VV……V

（n個V）規(guī)定：V0={ε}

V*=V

0∪V

1∪V

2∪……

V+=V

1∪V

2∪……2.1.1語言的概念-43-第2講形式語言和文法基本概念（4）符號串的集合：若集合A中的所有元素都是某字母表上的符號串，則稱A為該字母表上的符號串集合。1.符號串的相關概念閉包：若指定字母表Σ，則Σ*表示Σ上的所有有窮長的串的集合。

Σ*

=Σ0∪Σ1∪Σ2∪……∪Σn∪……

Σ*

稱為集合Σ的閉包。

Σ+=Σ1∪Σ2∪……∪Σn∪……

Σ+

稱為集合Σ的正閉包。2.1.2語言的定義方法-44-第2講形式語言和文法基本概念

語言的句子個數(shù)有限——枚舉語言的句子有很多甚至是無窮多個

——給出一些規(guī)則說明這個語言的句子的組成結(jié)構。

規(guī)則——文法規(guī)則

2.1.2語言的定義方法-45-第2講形式語言和文法基本概念【例2-5】文法規(guī)則：<句子>∷＝<主語><謂語><主語>∷＝<代詞>│<名詞><謂語>∷＝<動詞><賓語><賓語>∷＝<代詞>│<冠詞><名詞><名詞>∷＝student│English│computer<代詞>∷＝I│you│he

<動詞>∷＝am│is│are│have│study<冠詞>∷＝a│an│the

文法規(guī)則的作用：（1）嚴格定義了一個語言的句子的結(jié)構；（2）用適當條數(shù)的規(guī)則描述了一個語言的全部句子。2.2文法-46-第2講形式語言和文法基本概念

2.2.1文法的形式定義

2.2.2文法的表示方法

2.2.3相關概念2.2.1文法的形式定義-47-第2講形式語言和文法基本概念終結(jié)符是組成句子的最基本的單位。一個語言允許使用的所有終結(jié)符組成的集合稱為終結(jié)符集，用VT

表示非終結(jié)符

表示語言中的語法單位的符號，常用尖括號“<>”括起來。一個非終結(jié)符一般可以推導出終結(jié)符串。一個語言可使用的所有非終結(jié)符組成的集合稱為非終結(jié)符集，用VN

表示。2.2.1文法的形式定義-48-第2講形式語言和文法基本概念規(guī)則（重寫規(guī)則、產(chǎn)生式、生成式）

形如

α→β或

α∷＝β或（α，β）的有序?qū)?，其? α

：某字母表V的V+

中的一個符號串（左部）

β

：V*

中的一個符號串（右部）文法：是一個四元組G（VN

，VT，S

，

P）

VN

：非終結(jié)符集（非空）；

VT：終結(jié)符集（非空），VN∩VT＝?

；

S

：識別符號或開始符號，S∈VN，

且至少在一條規(guī)則中作為左部出現(xiàn)；

P

：規(guī)則（產(chǎn)生式）的集合。

用V表示VN∪VT

，稱G的字母表或詞匯表。2.2.1文法的形式定義-49-第2講形式語言和文法基本概念例：G：S→0S1或G[S]：S→0S1或G：S→0S1|01

S→01S→01

注意：左部相同的產(chǎn)生式可合并，用“|”表示“或”。簡化表示——只寫出規(guī)則（產(chǎn)生式），第一條規(guī)則的左部是開始符號，用“<>”括起的或大寫字母表示非終結(jié)符，不用“<>”括起的或小寫字母表示終結(jié)符。文法G也常寫成G[S]，方括號中的S為開始符號。

【例2-6】

文法G（VN

，VT

，S

，P）

其中:VN

={S},VT={0,1}

開始符號是S,P={S→0S1,S→01}2.2.1文法的形式定義-50-第2講形式語言和文法基本概念【例2-7】文法G=(VN，VT，S

，P)為：

VN={<句子>，<主語>，<謂語>，<賓語>，<名詞>，<代詞>，<動詞>，<冠詞>}

VT={student，computer，sister，English，I，you，he

，

am，is，are，have，study，a，an，the}

開始符是<句子>

P={<句子>∷＝<主語><謂語><主語>∷＝<代詞>│<名詞><謂語>∷＝<動詞><賓語><賓語>∷＝<代詞>│<冠詞><名詞><名詞>∷＝student│computer│sister│English

<代詞>∷＝I│you│he

<動詞>∷＝am│is│are│have│study<冠詞>∷＝a│an│the}2.2.2文法的表示方法-51-第2講形式語言和文法基本概念【例2-8】FORTRAN語言中對標識符的規(guī)定是字母開頭、長度小于等于8的字母數(shù)字串，則標識符的規(guī)則可以描述為：BNF表示法

巴科斯-諾爾范式（巴科斯范式）

采用四個元符號描述文法：“→”（或“∷＝”）、“<”、“>”，“|”

擴展的BNF表示法

增加三對元符號：

（1）“{}”:表示符號串t的多次重復，n為重復的最小次數(shù)，m為重復的最大次數(shù)，省略n、m表示t可以重復0到任意多次。2.2.2文法的表示方法-52-第2講形式語言和文法基本概念BNF表示法

巴科斯-諾爾范式（巴科斯范式）

采用四個元符號描述文法：“→”（或“∷＝”）、“<”、“>”，“|”

擴展的BNF表示法

增加三對元符號：

（2）“()”:用于提取產(chǎn)生式的公共因子，從而可以簡化產(chǎn)生式。若有文法規(guī)則

A→xα1|xα2|……|xαn表示為

A→x(α1|α2|……|αn)【例2-9】文法規(guī)則S→0S1|01簡化為S→0(S1|1)

或S→(0S|0)1

或S→0(S|ε)12.2.2文法的表示方法-53-第2講形式語言和文法基本概念BNF表示法

巴科斯-諾爾范式（巴科斯范式）

采用四個元符號描述文法：“→”（或“∷＝”）、“<”、“>”，“|”

擴展的BNF表示法

增加三對元符號：

（3）“[]”:

[t]表示符號串t可選（即可有可無）?！纠?-10】C程序設計語言的條件語句的文法規(guī)則

BNF表示：<條件語句>→if(<條件>)<語句>；|if(<條件>)<語句>；else<語句>；擴展BNF表示：<條件語句>→if(<條件>)<語句>；[else<語句>；]2.2.2文法的表示方法-54-第2講形式語言和文法基本概念語法圖表示法【例2-11】C語言條件語句的語法圖else語句if條件()語句終結(jié)符非終結(jié)符2.2.3文法的相關概念-55-第2講形式語言和文法基本概念1．推導和歸約定義：如α→β是文法G（VN

，VT

，S

，P）的一條規(guī)則，γ、δ∈V*

，若有符號串v、w滿足

v=γαδ，

w=γβδ

則稱v（應用規(guī)則α→β）直接產(chǎn)生w，或稱w是v的直接推導，反

過來稱w

直接歸約到v，記作

v?w?！纠?-13】

對文法G：S→0S1

S→01

有直接推導序列：S?0S1?00S11?0001112.2.3文法的相關概念-56-第2講形式語言和文法基本概念1．推導和歸約【例2-14】

S?0S1?00S11?000111

S

推導出“000111”，推導長度3

“000111”歸約到S

表示成S?000111++*+定義：如果存在直接推導序列：

v=w0?w1?w2?……?wn=w

則稱v

推導（產(chǎn)生）出w，推導長度為n

，反過來稱w

歸約到v，記作

v?w。

如果有v?w

，或v=w

，則記作v?w。2.2.3文法的相關概念-57-第2講形式語言和文法基本概念2．句型和句子*定義：

文法G（VN，VT，S

，P），若符號串x可由開始符號S推導出（S?x），則稱x是G

的一個句型，

若x僅由終結(jié)符組成，則稱x為G

的一個句子。注意：句型和句子都必須由開始符號S推出！

【例2-15】

推導S?0S1?00S11?000111句型句子2.2.3文法的相關概念-58-第2講形式語言和文法基本概念3．形式語言定義：文法描述的語言是該文法的所有句子的集合，記作L(G)。集合形式表示：

L(G)={α|S?α∧α∈VT*}+【例2-16】文法G：S→0S1

S→01

描述的語言：L(G)={0n1n|n≥1}2.2.3文法的相關概念-59-第2講形式語言和文法基本概念4．文法的等價性定義：若有文法G1、G2，它們描述的語言相同，即

L(G1

)=L(G2

)

則稱兩文法G1

和G2

等價。+【例2-17】有文法G[A]：A→0R

A→01

R→A1描述的語言L(G)={0n1n|n≥1}。2.2.3文法的相關概念-60-第2講形式語言和文法基本概念5．遞歸規(guī)則和遞歸文法遞歸規(guī)則：形如P→α1Pα2的規(guī)則稱遞歸規(guī)則。若α1=ε則稱左遞歸規(guī)則;若α2=ε則稱右遞歸規(guī)則。遞歸文法：含有遞歸規(guī)則的文法稱遞歸文法。P?α1Pα2的遞歸稱間接遞歸，含間接遞歸的文法也是遞歸文法本講小結(jié)-61-內(nèi)容：

語言：固有的有窮字母表上的句子（終結(jié)符串）的集合，文法：（VN，VT，S，P）

BNF表示、擴展的BNF、語法圖（直接）推導、（直接）歸約、句型、句子語言和文法：語言由文法描述，文法定義語言語言文法的不唯一性（文法的等價性）要求：弄懂概念，會寫文法第2講形式語言和文法基本概念課后-62-思考

習題1，2預習題文法按什么標準進行分類？分成哪幾類？

文法的二義性是什么意思？文法有二義性是好事還是壞事？第2講形式語言和文法基本概念編譯原理文法分類和正規(guī)式《編譯原理》第3講回顧-65-第3講文法分類和正規(guī)式語言：有窮字母表上的句子（終結(jié)符串）的集合，文法：（VN，VT，S，P）

BNF表示、擴展的BNF、語法圖（直接）推導、（直接）歸約、句型、句子語言和文法：語言由文法描述，文法定義語言語言文法的不唯一性（文法的等價性）內(nèi)容提要-66-2.1形式語言2.4文法的二義性2.3文法的分類和化簡2.2文法第3講文法分類和正規(guī)式2.3.1文法的分類-67-1.0型文法（無限制文法或短語文法）定義2-7設G=(VN，VT，P，S)，如果它的每個產(chǎn)生式α→β滿足α、

β∈(VN∪VT)*，且α至少含有一個非終結(jié)符，則G是一個0型文法。第3講文法分類和正規(guī)式2.3.1文法的分類-68-2.1型文法（上下文有關文法）定義2-8設G=(VN，VT，P，S)，如果它的每個產(chǎn)生式α→β滿足|β|≥|α|（僅S→ε除外），則G是一個1型文法。

另一種描述：文法的產(chǎn)生式形如

α1Aα2

→α1βα2

其中A∈VN，α、β∈(VN∪VT)*且β≠ε

【例2-18】1型文法G[S]：

S→xSYZ|xYZ

yZ→yz

xY→xy

ZY→YZ

yY→yy

zZ→zz第3講文法分類和正規(guī)式2.3.1文法的分類-69-3.2型文法（上下文無關文法）定義2-9設G=(VN，VT，P，S)，如果它的每個產(chǎn)生式α→β中的α

是一個非終結(jié)符，則G是一個2型文法或上下文無關文法。【例2-19】2型文法G[S]：

S→E

T→P|T﹡P

F→i|(E)

E→T|E＋T

P→F|F↑P

第3講文法分類和正規(guī)式2.3.1文法的分類-70-4.3型文法（正規(guī)文法或正則文法）定義2-10設G=(VN，VT，P，S)，如果它的每個產(chǎn)生式均形如

A→aB或A→a其中A、B∈VN，a∈VT?！纠?-20】

3型文法G[S]：

S→aA

A→aA

A→a

S→a

A→dA

A→d

第3講文法分類和正規(guī)式2.3.1文法的分類-71-0型文法1型文法2型文法3型文法0型語言1型語言上下文有關3型語言正規(guī)2型語言上下文無關描述句法描述詞法|β|≥|α|α∈VNβ

=aB|a第3講文法分類和正規(guī)式2.4文法的二義性-72-

i*i＋i

的語法樹【例2-22】對（算術表達式）文法G：

E→i

E→E+E

E→E*E

E→(E)E*+iEEEEii“i*i＋i”的推導過程可以是：

(1)

E?E+E?E*E+E?i*E+E?i*i+E?i*i+i(2)

E?E+E?E+i?E*E+i?E*i+i?i*i+i(3)

E?E+E?E+i?E*E+i?i*E+i?i*i+iE+*iEEEEii第3講文法分類和正規(guī)式2.4文法的二義性-73-最左推導：在推導的任何一步α?β（α、β是句型）都是對α中的最左非終結(jié)符進行替換。最右推導：在推導的任何一步α?β（α、β是句型）都是對α中的最右非終結(jié)符進行替換。也稱規(guī)范推導，推出的句型稱規(guī)范句型。例如最左推導：E?E*E?i*E?i*E+E?i*i+E?i*i+i

最右推導：E?E*E?E*E+E?E*E+i?E*i+i?i*i+i顯然，一棵語法樹表示的最左（右）推導是唯一的！可見：（1）一棵語法樹表示了一個句型的多種可能的不同推導過程，但未必是所有的。（2）一個句型未必只有一棵語法樹。第3講文法分類和正規(guī)式2.4文法的二義性-74-

i*i＋i

的語法樹：

若產(chǎn)生某一上下文無關語言的每個文法均是二義的，則說該語言先天二義。【例2-23】與例2-22等價的非二義文法

G′：E→T|E+T

T→F|T*F

F→(E)|iE*+FT

TEFTiFii愿望：文法非二義！定義：若一個文法存在某個句子，它對應兩棵（或以上）不同的語法樹，或

它有兩個不同的最左（右）推導，則該文法是二義的（具有二義性）。第3講文法分類和正規(guī)式3.1正規(guī)式與正規(guī)集-75-

3.1.1概念

3.1.2正規(guī)文法和正規(guī)式的等價性第3講文法分類和正規(guī)式3.1.1概念-76-

1.正規(guī)式和正規(guī)集的定義

定義3-1：設有字母表Σ，則（1）ε和?都是Σ上的正規(guī)式，所表示的正規(guī)集是{ε}和?；（2）若a∈Σ，則a是Σ上的正規(guī)式，所表示的正規(guī)集是{a}；（3）若U、V都是Σ上的正規(guī)式，它們所表示的正規(guī)集分別記為L(U)和L(V)，則U|V（或）、U·V（連接，也可寫UV）和U*（閉包）也都是正規(guī)式，它們所表示的正規(guī)集分別為L(U)∪L(V)、L(U)L(V)（乘積）和(L(U))*；（4）僅由有限次使用上述三步驟得到的表達式才是Σ上的正規(guī)式，僅由這些正規(guī)式所表示的集合才是Σ上的正規(guī)集。優(yōu)先級從高到低為“*”（閉包）、“·”（連接）、“|”（或），括號優(yōu)先。第3講文法分類和正規(guī)式3.1.1概念-77-【例3-1】Σ={a,b,x,y,0,1}

正規(guī)式對應的正規(guī)集(a|b)(a|b){aa，ab，ba，bb}xy*

x開頭后跟任意多個y的串的集合(0|1)*11(0|1)*含有連續(xù)兩個1的0、1串的集合(0|1)*1以1結(jié)尾的0、1串的集合

第3講文法分類和正規(guī)式3.1.1概念-78-2.正規(guī)式服從的代數(shù)規(guī)律定義3-2：若兩個正規(guī)式e1、e2所描述的正規(guī)集相同，則兩正規(guī)式等價。

即對任意兩正規(guī)式e1和e2，e1=e2

當且僅當L(e1)=L(e2)

。

定理3-1：設r，s，t都是字母表Σ上的正規(guī)式，則有：（1）

r|s=s|r

交換律（2）

r|(s|t)=(r|s)|t

結(jié)合律

(rs)t=r(st)（3）

r(s|t)=rs|rt

(s|t)r=sr|tr

分配律（4）εr=rε=r

“連接”的恒等元素ε（5）(a|b)*=(a*b*)*第3講文法分類和正規(guī)式3.1.2正規(guī)式和正規(guī)文法的等價性-79-1.正規(guī)式

正規(guī)文法【例3-3】

構造與R=a(a|d)*等價的正規(guī)文法A→aA

，A→dA

A→(a|d)A

，A→ε

S→a(a|d)*

A

xy

A

xB，B

y

A

x*y

A

xA，A

y

A

x|y

A

x，A

yS→aA

，A→(a|d)*分解規(guī)則：第3講文法分類和正規(guī)式3.1.2正規(guī)式和正規(guī)文法的等價性-80-2.正規(guī)文法正規(guī)式

反用分解規(guī)則，合并產(chǎn)生式，直到最后形成一個開始符號定義的產(chǎn)生式，且其右部不含非終結(jié)符。A

xB，B

y

A

xy

A

xA，A

y

A

x*y

A

x，A

y

A

x|y合并規(guī)則：第3講文法分類和正規(guī)式3.1.2正規(guī)式和正規(guī)文法的等價性-81-（2）A→aA

（3）A→aB（5）C→cB（6）C→c規(guī)則②：A→a*a(bc)*(bc)【例3-4】

文法G：(1)S→aA(2)A→aA(3)A→aB

(4)B→bC(5)C→cB(6)C→cA→aA|aBC→cB|cB→bcB|bc代入S→aA：S→aa*a(bc)*(bc)

等價的正規(guī)式:aa*a(bc)*(bc)

或

aa+(bc)+

規(guī)則②：B→(bc)*(bc)代入

A→aA|aB

：A→aA|a(bc)*(bc)代入B→bC

B→b(cB|c)第3講文法分類和正規(guī)式本講小結(jié)-82-（1）文法的分類：四類文法的定義類間的關系——?，要求逐步增加。（2）語法樹的作用：描述語法單位文法二義性的定義和判別：一個句型有多棵語法樹或有多個最左／最右推導語言的二義性。（3）正規(guī)文法與正規(guī)式第3講文法分類和正規(guī)式課后-83-思考習題3，4作業(yè)習題5（1～4）,6,8，9，10預習題有窮自動機的作用是什么？它以何種形式表示？編譯原理有窮自動機《編譯原理》第4講復習-86-第4講有窮自動機文法的分類

哪幾類？分別如何定義？

那類用于詞法分析？那類用于語法分析？詞法分析相關概念

什么是正規(guī)式、正規(guī)集？與正規(guī)文法是什么關系？內(nèi)容提要-87-3.4正規(guī)文法和FA的等價性

3.3正規(guī)式和FA的等價性3.2有窮自動機第4講有窮自動機3.2有窮自動機-88-有窮自動機確定的有窮自動機DFA（DeterministicFiniteAutomata）不確定的有窮自動機NFA（NondeterministicFiniteAutomata）正規(guī)集的識別裝置——第4講有窮自動機3.2.2確定的有窮自動機DFA-89-每個元素稱一個狀態(tài)每個符號稱為一個輸入符號Q×Σ→Q的單值映射，δ(q1，a)=q2：在q1狀態(tài)下遇a轉(zhuǎn)到q2狀態(tài)，q2為q1的后繼

q0∈Q

Z?Q有窮狀態(tài)集有窮字母表狀態(tài)轉(zhuǎn)換函數(shù)終態(tài)集初態(tài)1．DFA的形式定義（DeterministicFiniteAutomata）定義：五元組M=（Q，Σ，δ，q0，Z）第4講有窮自動機3.2.2確定的有窮自動機DFA-90-

0123abbaab?（2）狀態(tài)轉(zhuǎn)換圖（1）狀態(tài)轉(zhuǎn)換矩陣2.DFA的表示

【例3-5】DFA

M=（Q,Σ,δ,q0

,Z）

Q={0，1，2，3}δ函數(shù)：Σ={a，b}δ(0，a)=1δ(1，b)=2

q0=0，δ(2，a)=2δ(2，b)=3

Z={3}δ(3，a)=2δ(3，b)=1a02131b22321?字符狀態(tài)第4講有窮自動機3.2.2確定的有窮自動機DFA-91-DFA的意義：對于Σ*中的任何字符串t，若存在一條從初態(tài)到終態(tài)的路徑（該路徑上的字符串為t），則t可為DFA所接受（或說t是該DFA可識別的）。

若初態(tài)結(jié)也是終態(tài)結(jié)，則空字可接受。

DFAM

所能接受的字符串的全體稱為該自動機識別的語言，記為L(M)。

結(jié)論：

Σ上的一個字符串集U是正規(guī)的，當且僅當存在一個Σ上的確定的有窮自動機DFAM，使U=L(M)。第4講有窮自動機3.2.3不確定的有窮自動機NFA-92-1．NFA的形式定義（NondeterministicFiniteAutomata）定義：五元組M=（Q，Σ，δ，Q0，Z）每個元素稱一個狀態(tài)每個符號稱為一個輸入符號Q×Σ→2Q的映射函數(shù)，2Q是Q的冪集

Q0

?

Q

Z?Q有窮狀態(tài)集有窮字母表狀態(tài)轉(zhuǎn)換函數(shù)終態(tài)集非空初態(tài)集第4講有窮自動機3.2.3不確定的有窮自動機NFA-93-2.NFA的表示狀態(tài)轉(zhuǎn)換圖012010,1?

與DFA的異同點：

在某狀態(tài)下遇某輸入符到達的后繼狀態(tài)是不唯一的;

NFA的初態(tài)也可以不唯一;

NFA的意義與DFA一樣。字符狀態(tài)?0011，11221狀態(tài)轉(zhuǎn)換矩陣第4講有窮自動機3.2.4NFA與DFA的等價性-94-1.FA的等價定理定理3-2對于每一個NFAM，必存在一個DFAM

，使它們識別的語言L(M

)=L(M)。若兩個有窮自動機M和M

所識別的語言L(M)=L(M

)，則說M和M

等價。第4講有窮自動機3.2.4NFA與DFA的等價性-95-

NFA的確定化過程

與NFA等價的DFAbX1234aY5εεabbb?bbbbaabX14Yaa2ba3?

?

b{2,3}{1,2,3}{X}{2,3,4}{2,3,5}{2,3,4,Y}aaababbabb例：（無a轉(zhuǎn)換）第4講有窮自動機3.2.5DFA的化簡-96-410000311151?000311151?b)最簡！a)

DFA中沒有多余的狀態(tài)，沒有等價的狀態(tài)。

1.最簡DFA

（1）多余狀態(tài):

從開始狀態(tài)出發(fā)，任何輸入串都無法到達的狀態(tài)。

消除：將該狀態(tài)及其射出的弧刪除。第4講有窮自動機3.2.5DFA的化簡-97-DFA中沒有多余的狀態(tài)，沒有等價的狀態(tài)。

1.最簡DFA

（2）等價狀態(tài)

①一致性條件

——或同為可接受狀態(tài)（終態(tài)），或同為不可接受狀態(tài)（非終態(tài)）；

②蔓延性條件——對所有輸入符號，都必須轉(zhuǎn)到等價的狀態(tài)?；蛘哒f，若兩個狀態(tài)s、t

等價，則首先，s、t

同為終態(tài)或非終態(tài);

其次，若從s

出發(fā)能識別出字符串w

而停于終態(tài)，則從t出發(fā)也能識別出字符串w而停于終態(tài)，反之亦然。第4講有窮自動機3.2.5DFA的化簡-98-基本思想：將DFA的狀態(tài)分割成若干個不相交的子集，

使不同子集中的狀態(tài)不等價，同一子集中

的狀態(tài)等價。2．化簡算法——分割法第4講有窮自動機3.2.5DFA的化簡-99-1111001X15Y002103?111001X15Y0103?【例3-10】DFA:最簡DFA:第4講有窮自動機3.3正規(guī)式和FA的等價性-100-

3.3.1構造與FA等價的正規(guī)式

3.3.2構造與正規(guī)式等價的FA

第4講有窮自動機3.3.1構造與FA等價的正規(guī)式-101-算法：FA=(Q,Σ,δ,q0,Z)轉(zhuǎn)換成正規(guī)式{在FA上增加兩個新結(jié)點X和Y;

置X為FA的新初態(tài)結(jié)點、Y置為FA的新終態(tài)結(jié)點；用ε弧將X連向FA的所有原初態(tài)結(jié)點;

將FA的所有原終態(tài)結(jié)點用ε弧連向Y;

while(FA中有除X、Y外的其它結(jié)點||X到Y(jié)的弧不止一條)

用消除規(guī)則逐步消除除Ｘ、Ｙ外的結(jié)點和弧;}ijkr1r2ikr1r2r1jr2iijr1|r2ik

r1r2*r3r2ijkr1r3消除規(guī)則：第4講有窮自動機3.3.1構造與FA等價的正規(guī)式-102-3ba,b021?aa4a,bba,bb3a,b021aa4

a,bba,bX?εYεεbba|b02aa4a|ba|bX?Yεεε0a|bX?Yεaa(a|b)*bb(a|b)*0a|bX?Yε(aa|bb)(a|b)*X?Y(a|b)*(aa|bb)(a|b)*【例3-11】第4講有窮自動機3.3.1構造與FA等價的正規(guī)式-103-C101ABD00101X?εYεX?Y(0|10*1)(00*1|110*1|10)*

00BD1

C01BD110ABD1

C10*100*1AB010*1|01X?εεY10*100*1AB0110*1|10X?εYε

【例3-12】第4講有窮自動機3.3.2構造與正規(guī)式等價的FA-104-算法：正規(guī)式r轉(zhuǎn)換成FA=(Q,Σ,δ,q0,Z)ijkr1r2ijkεεr2ikr1r2ijr1|r2ikr2*r1jr2i分解規(guī)則：

{設置兩個狀態(tài)X、Y，并將X置為FA的初態(tài)，Y置為終態(tài);

構造

while(有標記多于一個終結(jié)符的弧)

用分解規(guī)則引入新的狀態(tài)和弧來分解弧上的標記；

}rXY

第4講有窮自動機3.3.2構造與正規(guī)式等價的FA-105-【例3-13】將正規(guī)式

r=10|(0|11)0*1

轉(zhuǎn)換成等價的FA。10|(0|11)0*1Y?XY?(0|11)0*110X1Y?(0|11)0*1X10Y?X123100*11100*11Y3101?X20411X1?0415εε

0Y103121Y?X3100|110*12第4講有窮自動機3.4正規(guī)文法和FA的等價性-106-

3.4.1構造與正規(guī)文法等價的FA

3.4.2構造與FA等價的正規(guī)文法第4講有窮自動機3.4.1構造與正規(guī)文法等價的FA-107-

【例3-14】G[S]：ZSABaabbab?S→aB→bAA→aBB→aSB→bS→bBA→bAbaS→aA轉(zhuǎn)換函數(shù)的構造：A→aBδ(A,a)=BA→aδ(A,a)=Z第4講有窮自動機3.4.2構造與FA等價的正規(guī)文法-108-?C101ABD01