編譯原理簡明教程（第3版）-課件 第1-3章 概述、形式語言理論基礎(chǔ)、自動機(jī)原理

新工科建設(shè)·計(jì)算機(jī)類系列教材

免費(fèi)提供編譯原理1基本課程信息編譯原理計(jì)算機(jī)科學(xué)中發(fā)展最迅速、最成熟的分支之一編譯程序計(jì)算機(jī)系統(tǒng)中重要的系統(tǒng)軟件之一編譯技術(shù)計(jì)算機(jī)高級語言發(fā)展的支柱編譯原理計(jì)算機(jī)科學(xué)中語言處理的基石理論研究軟件開發(fā)編譯原理課程是計(jì)算機(jī)科學(xué)中理解語言處理內(nèi)在機(jī)制、提升軟件開發(fā)效率與質(zhì)量、培養(yǎng)系統(tǒng)級編程思維與創(chuàng)新能力的核心課程。學(xué)分：編譯原理簡明教程（第3版）馮秀芳

崔冬華

王會青

主編電子工業(yè)出版社

2024年出版課程教材學(xué)分：參考教材“編譯原理”是計(jì)算機(jī)類專業(yè)一門重要的專業(yè)課，其目的是系統(tǒng)地向?qū)W生講授編譯程序的基本結(jié)構(gòu)，闡述編譯原理的一般理論和常用的有效方法與編譯技術(shù)。

引言教學(xué)目的：學(xué)習(xí)本課后，使學(xué)生掌握編譯理論和方法方面的基本知識，具有設(shè)計(jì)、實(shí)現(xiàn)、分析和維護(hù)編譯程序等方面的初步能力。主要內(nèi)容：形式語言與自動機(jī)、詞法分析、語法分析、語義分析、中間語言代碼生成和優(yōu)化、目標(biāo)代碼生成、存儲組織與分配、程序的查錯(cuò)與處理等。56目錄第一章概述第二章形式語言理論基礎(chǔ)第三章自動機(jī)理論基礎(chǔ)第四章詞法分析第五章語法分析—自頂向下分析方法第六章語法分析—自底向上分析方法第七章語義分析及中間代碼的生成第八章代碼優(yōu)化第九章目標(biāo)代碼的生成第十章符號表和出錯(cuò)處理第十一章

面向?qū)ο笳Z言的編譯第十二章

并行編譯技術(shù)第十三章

軟件構(gòu)造62024/11/67學(xué)習(xí)目標(biāo)學(xué)習(xí)編譯程序的概念工作過程、體系結(jié)構(gòu)語言與編譯程序的關(guān)系了解開發(fā)技術(shù)1概述EINLEITUNG重點(diǎn)：編譯程序的概念、編譯程序的結(jié)構(gòu)難點(diǎn)：編譯程序的開發(fā)技術(shù)

目錄1.1程序設(shè)計(jì)語言與翻譯1.2編譯過程概述1.3編譯程序的開發(fā)1.4本章小結(jié)81.1程序設(shè)計(jì)語言與翻譯計(jì)算機(jī)系統(tǒng)：硬件軟件：應(yīng)用軟件、系統(tǒng)軟件（包括OS、編譯系統(tǒng)、診斷系統(tǒng)等）程序設(shè)計(jì)語言：機(jī)器、匯編、高級翻譯程序：指能把A語言程序翻譯成與之等價(jià)的B語言

程序的程序。B語言（目標(biāo)程序）A語言（源程序）翻譯程序91.1程序設(shè)計(jì)語言與翻譯計(jì)算機(jī)系統(tǒng)：硬件軟件：應(yīng)用軟件、系統(tǒng)軟件（包括OS、編譯系統(tǒng)、診斷系統(tǒng)等）程序設(shè)計(jì)語言：機(jī)器、匯編、高級翻譯程序：指能把A語言程序翻譯成與之等價(jià)的B語言

程序的程序。B語言（目標(biāo)程序）A語言（源程序）翻譯程序101.1.1程序設(shè)計(jì)語言機(jī)器語言高級語言11匯編語言機(jī)器語言即機(jī)器指令，能被計(jì)算機(jī)直接理解與執(zhí)行是符號化的機(jī)器語言FORTRAN、ALGOL、Pascal、C、JAVA、Ada、C++、Python等1.1.2編譯程序和解釋程序B（機(jī)器語言）A（高級語言）編譯程序12如何讓計(jì)算機(jī)認(rèn)識、理解、執(zhí)行高級語言程序？

匯編程序B（機(jī)器語言）A（匯編語言）匯編程序13

解釋程序純粹的解釋程序并不多見，通常做某種程序的結(jié)合。141.2編譯過程概述閱讀全文、識別單詞分析句子語法結(jié)構(gòu)根據(jù)句子含義初步分析修辭加工寫出譯文生成目標(biāo)代碼優(yōu)化語義分析語法分析掃描源程序、詞法分析分析綜合翻譯外文資料編譯程序15一、詞法分析

輸入源程序，對源程序構(gòu)成的字符串進(jìn)行掃描和分析，識別出一個(gè)個(gè)的單詞，如保留字(if、for、while等)、標(biāo)識符、常數(shù)、特殊符號(標(biāo)點(diǎn)符號、左右括號、運(yùn)算符等)。例如，對于C語言的循環(huán)語句：詞法分析：遵循詞法規(guī)則，描述詞法規(guī)則正規(guī)式和有限自動機(jī)for(i=1;i<=100;i++)

sum=sum+1;161.2.1編譯程序的工作過程編譯程序一般分五個(gè)部分二、語法分析

根據(jù)語言語法規(guī)則，把詞法分析后的單詞合成各類語法單位（語法范疇），如“短語”，“句子”，“程序段”，“程序”。例如賦值語句：Z=X+2*Y；

語法分析：遵循語法規(guī)則，采用上下文無關(guān)文法描述。17編譯程序一般分五個(gè)部分三、語義分析及中間代碼的生成

根據(jù)語法結(jié)構(gòu)，分析其含義，并進(jìn)行初步翻譯（生成中間代碼），或直接生成目標(biāo)代碼。對常用的一些語言來說，語義分析生成語法成分的含義和用途，以及應(yīng)進(jìn)行的運(yùn)算和操作，而且要進(jìn)行語義檢查等。例如：

3）在過程調(diào)用中，實(shí)參和形參是否在個(gè)數(shù)、次序、種屬一一對應(yīng)等。2）在表達(dá)式中，是否有類型不匹配的運(yùn)算對象；1）在說明語句中，是否有矛盾的類型說明；18編譯程序一般分五個(gè)部分“中間代碼”是一種含義明確、便于處理的記號系統(tǒng)。如：三元式、四元式、逆波蘭式。z=(x+3)*y/w;（+，x，3，T1）例：四元式（運(yùn)算符，第一運(yùn)算量，第二運(yùn)算量，結(jié)果）(/,T2,

w，z

)（*，T1,y,

T2）19編譯程序一般分五個(gè)部分四、代碼優(yōu)化

優(yōu)化的任務(wù)在于對前階段產(chǎn)生的中間代碼進(jìn)行加工變換，以期在最后階段產(chǎn)生出更為高效(節(jié)省時(shí)間和空間)的目標(biāo)代碼。優(yōu)化的主要方面有：公共子表達(dá)式的提取、循環(huán)優(yōu)化、刪除無用代碼等。有時(shí)，為了便于“并行運(yùn)算”，還可以對代碼進(jìn)行并行優(yōu)化處理。優(yōu)化所依循的原則是程序的等價(jià)變換規(guī)則。

20編譯程序一般分五個(gè)部分從與具體計(jì)算機(jī)的關(guān)系分與機(jī)器無關(guān)的與機(jī)器有關(guān)的從與源程序的關(guān)系分全局優(yōu)化局部優(yōu)化21五、目標(biāo)代碼生成

把中間代碼變成特定機(jī)器上的機(jī)器代碼。這部分涉及到硬件,如各種數(shù)據(jù)類型變量的存儲空間分配，寄存器的調(diào)度等。例：盡量使用執(zhí)行速度快的指令，充分利用計(jì)算機(jī)的寄存器，以節(jié)省訪問內(nèi)存所用時(shí)間等。22編譯程序一般分五個(gè)部分1.2.2編譯程序的結(jié)構(gòu)231.3編譯程序的開發(fā)

編譯程序是一個(gè)非常復(fù)雜的軟件系統(tǒng)，雖然編譯理論和技術(shù)不斷發(fā)展，開發(fā)周期縮短，但研制仍需大量時(shí)間。追求目標(biāo)過程自動化。1.3.1開發(fā)步驟1.認(rèn)真分析，合理分工

2.算法設(shè)計(jì)，方案確定

3.語言選擇，編制程序

4.調(diào)試程序，確保質(zhì)量

5.資料整理，文本形成

241.3.2開發(fā)技術(shù)一、系統(tǒng)程序設(shè)計(jì)語言

70年代以前，用機(jī)器語言、匯編語言，手工編寫工作量大、可靠性差、難以維護(hù)。

80年代以后，高級語言如PASCAL、ADA、C，工作量大大減少，縮短開發(fā)周期。系統(tǒng)程序程序設(shè)計(jì)語言：編寫編譯程序或其它系統(tǒng)軟件的高級語言。25二、開發(fā)技術(shù)自編譯：用某一高級語言編寫其自己的編譯程序。交叉編譯：A機(jī)器上的編譯程序能產(chǎn)生B機(jī)器上的目標(biāo)代碼。自展：首先確定一個(gè)非常簡單的核心語言L0，用機(jī)器的匯

編語言寫其編譯程序T0，擴(kuò)充L0到L1，用L0寫L1的T1, L1到L2……滾雪球一樣，直到所需編程序。移植：將A機(jī)器上的某高級語言編譯程序搬到B機(jī)器上運(yùn)行。261.3.2開發(fā)技術(shù)1.3.2開發(fā)技術(shù)三、編譯技術(shù)的發(fā)展面向?qū)ο蟮母呒壵Z言編譯技術(shù)

并行計(jì)算機(jī)和并行程序編譯技術(shù)27編譯技術(shù)的發(fā)展過程中，有多名計(jì)算機(jī)領(lǐng)域的專家因在編譯理論和技術(shù)相關(guān)研究方面的突出貢獻(xiàn)獲得了圖靈獎(jiǎng)，例如艾倫·佩利（AlanJ.Perlis）、高德納·克努斯（DonaldE.Knuth）、法蘭西斯·艾倫（FrancesE.Allen）、阿爾弗雷德·艾侯（AlfredVainoAho）和杰弗里·烏爾曼（JeffreyDavidUllman）如Unix下

LEX

詞法分析程序自動構(gòu)造軟件工具

YACC

語法分析程序自動構(gòu)造軟件工具

Llama

編譯程序生成軟件工具

Occs

源語言的定義機(jī)器語言的描述翻譯程序的自動生成軟件編譯程序281.3.3編譯程序的自動生成291.4本章小結(jié)1．程序設(shè)計(jì)語言：機(jī)器語言、匯編語言、高級語言2．編譯程序和解釋程序都是翻譯程序，但解釋程序不產(chǎn)生完整的目標(biāo)代碼程序3．編譯程序工作過程一般劃分為：詞法分析、語法分析、語義分析與中間代碼的產(chǎn)生、優(yōu)化、目標(biāo)代碼的生成五個(gè)階段4．編譯程序常用開發(fā)技術(shù)：自編譯、交叉編譯、自展和移植

30總結(jié)

本章我們學(xué)習(xí)了什么是編譯程序、高級語言的編譯過程、編譯程序的一般結(jié)構(gòu)、編譯程序的開發(fā)技術(shù)等內(nèi)容。

下一章將學(xué)習(xí)編譯的基本理論------形式語言理論。THANKS31THANKS新工科建設(shè)·計(jì)算機(jī)類系列教材

免費(fèi)提供編譯原理326目錄第一章概述第二章形式語言理論基礎(chǔ)第三章自動機(jī)理論基礎(chǔ)第四章詞法分析第五章語法分析—自頂向下分析方法第六章語法分析—自底向上分析方法第七章語義分析及中間代碼的生成第八章代碼優(yōu)化第九章目標(biāo)代碼的生成第十章符號表和出錯(cuò)處理第十一章

面向?qū)ο笳Z言的編譯第十二章

并行編譯技術(shù)第十三章

軟件構(gòu)造33

學(xué)習(xí)形式語言基本理論和基礎(chǔ)知識掌握程序設(shè)計(jì)語言的語法描述方法需要著重掌握的內(nèi)容為：字母表、符號、符號串、符號串集合

規(guī)則（產(chǎn)生式）、文法推導(dǎo)、歸約、句型、句子、語言語法樹、二義性

文法的限制、文法的分類34學(xué)習(xí)目標(biāo)2形式語言理論基礎(chǔ)形式語言理論基礎(chǔ)程序設(shè)計(jì)語言語法程序的結(jié)構(gòu)形式語義語言所代表的含義語用語言的實(shí)際應(yīng)用35Theoreticalbasisofformallanguage形式語言理論基礎(chǔ)

例如：x:=a*b+c

以下非形式化的描述不夠清晰明確

變量：=表達(dá)式v:=e對e求值，再賦給變量計(jì)算和保存e的值語法語義語用36Theoreticalbasisofformallanguage形式語言理論基礎(chǔ)形式語言形式語言理論探討形式化方法發(fā)展過程用一套帶有嚴(yán)格規(guī)定的符號體系來描述問題的理論方法。是一種不考慮含義的符號語言（只談?wù)Z法不談?wù)Z義）。研究組成這組符號串的集合表示法、結(jié)構(gòu)及特性，只能用于程序語言的語法描述和語法分析。37Theoreticalbasisofformallanguage

目錄2.1形式語言的基本概念2.2文法和語言的形式定義2.3語法樹和二義性2.4文法的限制2.5文法和語言的Chomsky分類2.6本章小結(jié)382.1形式語言的基本概念

2.1.1符號和符號串形式語言和編譯技術(shù)中兩個(gè)主要概念任何一種語言都是由該語言的基本符號組成的基本符號串的集合。英文：26個(gè)字母、數(shù)字、標(biāo)點(diǎn)符號等

中文：漢字、數(shù)字、標(biāo)點(diǎn)符號等

C、JAVA、PASCAL：

字母、數(shù)字、關(guān)鍵字、專用符號等

392.1.1符號和符號串是一個(gè)非空的有限集合。用Σ表示。例：Σ={a，b，c}a,b,c均為字符或符號，是字母表中的元素字母表字母表上若干符號串/字符串組成的集合。用大寫字母表示。例：A={a，ab，bc}符號串集合/字符串集合符號/字符的有限序列。小寫希臘字母表示。如：ω，φ，λ，a，b，ab，abc等。ε表示空字符串，不包含任何符號的符號串。ε≠空格ab≠ba符號串/字符串402.1.1符號和符號串例：Σ={a}，L={a2k|k≥0}Σ={0，1}，L1={(01)n|n≥0}={ε，01，0101，……}L2={0n1n|n≥0}={ε，01，0011,……}

ф空集或者空語言，不含任何符號串的語言。ф≠{ε}

語言/形式語言412.1.2符號串的運(yùn)算符號串相等：同一字母表的兩個(gè)符號串所有

符號依次相等。如Σ={a，b，c}，ω=abc，ψ=abc，則ω=ψ；若ω=abc，ψ=cba，則ω≠ψ字符串的長度：符號串中包含的字符的個(gè)數(shù)。

記|ω|。例|abc|=3，|ε|=0,|aω|=|ωa|=1+|ω|，a∈Σ422.1.2符號串的運(yùn)算符號串的連接:

把符號串ψ的所有符號相繼寫在ω之后，記ωψ或ω·ψω=ab，ψ=bc，則ωψ=abbc符號串的逆：符號串ω的倒置，記ω-1如ω=abc則ω-1=cbaε-1=ε（ω-1）-1=ω（ωψ）-1=ψ-1ω-1432.1.2符號串的運(yùn)算前綴：ε，a，ab，abc后綴：ε，c,bc，abc子串：ε，a，b，c，ab，bc，abc例：abc符號串的前綴、后綴和子串：設(shè)ω，ψ，β是字母表Σ上的字符串，則ω為符號ωψ的前綴，ψ為字符串ωψ的后綴，ψ是字符串ωψβ的子串。前綴和后綴都是子串，但子串不一定是前綴或者后綴。

442.1.2符號串的運(yùn)算符號串的冪：一個(gè)符號串與它自己的n次連接。ω0=ε；ω1=ω；ω2=ωω；……；ωn=ωn-1ωω=abω0=εω1=abω2=abab……ωn=abab……ab452.1.3符號串集合的運(yùn)算符號串集合的乘積:A·B={ωψ|ω∈A，ψ∈B}例：A={ab,ba}B={bc,b}則AB={abbc,abb,babc,bab}特別：{ε}A=A{ε}=A46符號串集合的冪：A0={ε}；A1=A；……；An=An-1A=AAn-1

(n>0)例：A={ab,c}A0={ε}A1={ab,c}A2={abc,cab,abab,cc}……472.1.3符號串集合的運(yùn)算集合A的閉包和正閉包：星閉包A*=A0∪

A1∪

……A+=AA*=A*A正閉包A+=A1∪

A2∪

……A*=A0∪

A+

Σ字母表Σ*：Σ上所有符號串的集合

Σ+：Σ上所有非空符號串的集合A={0，1}則A1={0，1}A0={ε}A2={00，01，10，11}……A*={ε，0，1，00，01，10，11，000，……}A+={0，1，00，01，10，11，000，……}482.1.3符號串集合的運(yùn)算2.2文法和語言的形式定義語言L可抽象地看成是所有句子組成的集合（有限集：用枚舉；無限集：文法）句子可抽象地看成是某個(gè)有限字母表Σ上的符號串。例：英語Σ={26個(gè)字母，數(shù)字，標(biāo)點(diǎn)符號，……}文法在形式上用以描述和規(guī)定語言結(jié)構(gòu)的方法，是用有限的手段描述無限的句子集合的方法之一。492.2文法和語言的形式定義例：“Thebigcatateamouse.”

<句子>→<主語><謂語><主語>→<冠詞><形容詞><名詞><冠詞>→the<名詞>→cat<形容詞>→big<謂語>→<動詞><直接賓語><動詞>→ate<直接賓語>→<冠詞><名詞><冠詞>→a<名詞>→mouse502.2文法和語言的形式定義例：我愛祖國。

從結(jié)構(gòu)上看符合中文文法，是中文句子。

又如：（1）〈無符號整數(shù)〉→〈數(shù)字串〉（2）〈數(shù)字串〉→〈數(shù)字串〉〈數(shù)字〉（3）〈數(shù)字串〉→〈數(shù)字〉（4）〈數(shù)字〉→2（5）〈數(shù)字〉→5（6）〈數(shù)字〉→6256是一個(gè)句子。51

文法G[A]：

A→B

B→BC|CC→2|5|6

2.2文法和語言的形式定義定義2.5：文法是一個(gè)四元組：G=（VN，VT，S，P）記為G[S]。V是字匯表，V=VT∪VN，S∈VN,VT∩VN=ΦU->X或U::=XVN大寫字母，一般出現(xiàn)在左部，不屬于字母表VT句子中的字母終結(jié)符號集非終結(jié)符號集文法規(guī)則集合52VN--非終結(jié)符集合，VT--終結(jié)符集合，S--開始符號，P--規(guī)則2.2文法和語言的形式定義例2-1

例2-2

VN={A}，VT={a，b，c}，S=A，P={A→aAb，A→c}。構(gòu)成文法G=（{A}，{a，b，c}，A，P）G=（{〈標(biāo)識符〉，〈字母〉，〈數(shù)字〉}，{0，1，2，…….9，a，b，c}，〈標(biāo)識符〉，P）532.2文法和語言的形式定義引進(jìn)BNF（巴科斯范式）

G[I]:I→L|IL|INL→a|b|cN→0|1|……|9定義2.6：句型

文法G[S]，G=（VN，VT，S，P）由S推出的符號串X∈(VT∪VN)*稱為句型。

542.2文法和語言的形式定義b.推導(dǎo)、歸約、推導(dǎo)長度(n≥1)

文法G，存在一直接推導(dǎo)序列，ω0

ω1

ω2……

ωn

(ω0ω1……ωn是句型)則稱ω0推導(dǎo)出ωn或ωn歸約到ω0記作ω0

ωn，ωn

ω0

++文法G，A→α是一條規(guī)則，ω1=φ1Aφ2ω2=φ1αφ2

（其中ω1，ω2，φ1，φ2∈(VT∪VN)*）

則稱ω1直接推導(dǎo)出ω2，記作

反之，ω2直接歸約到ω1，記作

ω1ω2ω2ω1

a.直接推導(dǎo)、直接歸約(長度=1)552.2文法和語言的形式定義c.若ω1

ω2或ω1=ω2

則稱ω1廣義推導(dǎo)ω2，記作ω1

ω2

ω2廣義歸約到ω1記作ω2

ω1

長度≥0

+**例：1.文法G[E]：E→E+T|TT→T*F|FE

i+i*i(n=8)F→(E)|i2.G[<無符號整數(shù)>]推出256+562.2文法和語言的形式定義例：1.文法G[E]：E→E+T|TT→T*F|FE

i+i*i(n=8)F→(E)|i2.G[<無符號整數(shù)>]推出256+57例：1.文法G[E]：E

E+T

E+T*F

E+T*iE+F*i

E+i*iT+i*iF+i*ii+i*i

2.G[<無符號整數(shù)>]ABBCBCCCCC2CC25C2562.2文法和語言的形式定義結(jié)論:給定一個(gè)文法,就能從結(jié)構(gòu)上唯一地確定其語言。

給定一個(gè)語言，能確定相應(yīng)文法,但不唯一。

定義2.7：語言、句子文法G=（VN，VT，S，P）所產(chǎn)生的語言L(G)

L(G)={ω|S

ω,ω∈VT*}其中ω稱為句子.空語言:由文法開始符號推不出任何句子.

+

d.規(guī)范推導(dǎo)（最右推導(dǎo)，也稱為最左歸約）

每次替換最右邊非終結(jié)符的直接推導(dǎo)。記作ω1

ω2

r+58例:G1:S→0S1S→01L(G1)={0n1n|n≥1}G2:S→1S→1AL(G2)={(10)n1|n≥0}A→0S

G3:S→1S→A1L(G3)={1(01)n|n≥0}A→S0

59L(G2)=L(G3),所以，G2和G3為等價(jià)文法2.2文法和語言的形式定義2.2文法和語言的形式定義又如：已知語言L(G[Z])={abna|n≥1}

則：G1：Z→aBaG2：Z→aBG3：Z→BaB→b|BbB→ba|bBB→ab|Bb例2-3G=（VN，VT，S，P）

VN={S，B，C}VT={a，b，c}P：（1）S→aSBC（5）bB→bb

（2）S→aBC（6）bC→bc

（3）CB→BC（7）cC→cc

（4）aB→ab602.2文法和語言的形式定義解：1)SaBCabCabc

（2）

（4）

（6）2）SaSBCaaBCBCaabCBCaabBCC(1)(2)(4)(3)aabbCCaabbcCaabbcc…………

所以,L(G)={anbncn|n=1，2，……}612.2文法和語言的形式定義例G=（VN，VT，S，P）

VN={A，B，S}VT={0，1}

P：S→0BS→1A

A→0B→1A→0SB→1S

A→1AAB→0BB

所以，L(G)由相同個(gè)數(shù)的0和1所組成的VT+中所有符號串的集合.

解：S

0B

01

S

1A

10

010B

0101S

0B

01S

011A

0110

S

0B

00BB

0011

……

62

2.3語法樹和二義性2.3.1語法樹和推導(dǎo)

1.語法樹的概念：定義2.8（用直觀方法描述句型或句子的語法結(jié)構(gòu)）已知文法G[S],滿足下列條件的樹稱為G的語法樹.a.結(jié)點(diǎn)：終結(jié)符or非終結(jié)符b.樹根:Sc.分枝:非終結(jié)符d.若結(jié)點(diǎn)A有B1B2…Bn分枝，則A→B1B2…Bn是G的一個(gè)規(guī)則。

63例：G[S]：S→aABSSA→Ba|aaABaABB→bdBaBabdbd642.3.1語法樹和推導(dǎo)例：G[<無符號整數(shù)>]G[A]：A→BB→BC|CC→0|1|2……|9

推導(dǎo)：

A

BBCB6BC6B56C56256ABBCBCCCCC2CC25C256A

BBC

BC6C522.由推導(dǎo)生成語法樹:

句型or句子的推導(dǎo)用圖解表示→語法樹生成652.3.1語法樹和推導(dǎo)3.由語法樹構(gòu)造推導(dǎo)

上一步的逆過程.由分枝建立直接推導(dǎo),然后剪去分枝,直到無分枝可剪.A

BBCBCC

CCC

2CC

25C256或先進(jìn)行歸約,再倒過來.

662.3.1語法樹和推導(dǎo)4.子樹和短語定義:子樹----某個(gè)結(jié)點(diǎn)與它的分枝結(jié)點(diǎn).BB

CC5簡單子樹----單層分枝的子樹.BCC5672.3.1語法樹和推導(dǎo)設(shè)S

aBc,B

b,則S

aBc

abc

S則b稱為句型abc相對于B的短語.

a

B

c

b*+*+結(jié)論:(1)子樹的末端結(jié)點(diǎn)組成的符號串是相對于子樹根的短語.(2)簡單子樹的末端結(jié)點(diǎn)組成的符號串是相對于簡單子樹根的簡單短語.(3)最左簡單子樹的末端結(jié)點(diǎn)組成的符號串為句柄.

682.3.1語法樹和推導(dǎo)例：E句型：

短語：E

+

T

簡單短語：

句柄：T

F

iT+iT+i,T,iT,iT692.3.1語法樹和推導(dǎo)2.3.2文法的二義性

1.二義性的概念

定義:如果一個(gè)文法所定義的句子中,有某個(gè)句子存在兩棵不

同的語法樹,則稱文法是二義性的。

或:若文法所定義的某個(gè)句子,有兩種不同的最左(or最右)

推導(dǎo)?；?若文法所定義的某個(gè)句子,有兩種不同的最左(or最右)

歸約。70

例:G[E]：E→E+E|E*E|(E)|iEEE+EE*EiE*EE+Eiiiii

E

E+E

E+E*E

i+i*iE

E*EE+E*E

i+i*i++

文法的二義性產(chǎn)生句子語義上的不確定性712.3.2文法的二義性例：G[s]：S→ifBthenS|ifBthenSelseS|A

S：語句B：布爾表達(dá)式A：其它語句

句型：ifBthenifBthenSelseSS

ifBthenS

ifBthenifBthenSelseSS

ifBthenSelseS

ifBthenifBthenSelseS722.3.2文法的二義性

S

SifB

then

Sif

Bthen

S

elseS

if

Bthen

S

else

S

ifB

then

S

732.3.2文法的二義性

例:G[E]：E→E+E|E*E|(E)|i在編譯方法中規(guī)定運(yùn)算之間的優(yōu)先級。

如:①*,/高于+,-

②同級先左后右2.二義性解決方法（1）修改編譯算法742.3.2文法的二義性（2）修改文法

G[E]：E→E+T|E-T|TT→T*F|T/F|FF→(E)|iG[S]：S→C|UC:完全語句U:不完全語句C→ifBthenCelseS|AU→ifBthenS

752.3.2文法的二義性

注：規(guī)則左部的符號在右部同時(shí)出現(xiàn)兩次or兩次以上，導(dǎo)致二義性。先天二義性文法：不存在等價(jià)的非二義性文法。二義性問題是不可判定的，即不存在一種算法在有限步內(nèi)判斷二義性762.3.2文法的二義性2.4文法的限制文法的實(shí)用限制主要是限制文法中不能存在有害規(guī)則和多余規(guī)則，這兩種規(guī)則如果出現(xiàn)會導(dǎo)致文法的二義性和錯(cuò)誤。77定義2.14:如果文法G[S]中所有規(guī)則均滿足下列實(shí)用限制條件：①沒有有害規(guī)則；②沒有多余規(guī)則。則稱該文法G[S]是壓縮或化簡過的。2.4.1文法的實(shí)用限制2.4.1文法的實(shí)用限制定義2.15:文法中形如A→A的規(guī)則，稱為有害規(guī)則。

N

例:N→NNNN→ND|DNND→0|1|……|9

N

DN

D78定義2.17:

對于文法G，在某句型中出現(xiàn)的符號稱為可推出符號。例:G[E]：{E,T,F,+,-,*,/,(,),i}

例:S→aAB|aA→aAb|b{S,A,B,a,b,d}B→dC→aBf定義2.16:G[S],若A∈VN，存在α,β∈V*有S

*

αAβ，則稱A為活的非終結(jié)符。792.4.1文法的實(shí)用限制定義2.18

多余規(guī)則：左部符號為A的規(guī)則,若不滿足條件

①A為可推出符號

②從A能推出句子

例:G[S]:S→Be①D不是可推出符號A→Ae|e∴D→f多余B→Ce|Af②B→CeC→Cf

C→Cf多余D→f在程序設(shè)計(jì)語言中若包含多余規(guī)則，必定有錯(cuò)誤句子。802.4.1文法的實(shí)用限制a.A為可推出符號：即S

αAβ;α,β∈V*；

b.必須能從A推出句子，即：A

ω,ω∈VT+

*+定理1:如果一個(gè)文法G[S]中所有規(guī)則均滿足下列兩個(gè)條件，則該文法不包含多余規(guī)則（設(shè)：A為任一規(guī)則的左部符號）。812.4.1文法的實(shí)用限制

G[S]:S→Be多余規(guī)則①D→fA→Ae|e②B→CeB→Ce|AfC→CfC→CfD→f822.4.1文法的實(shí)用限制

832.4.1文法的實(shí)用限制

842.4.1文法的實(shí)用限制算法2.2:使文法的每個(gè)非終結(jié)符均出現(xiàn)在某個(gè)句型中

*852.4.2文法的實(shí)用限制2.4.2文法的等價(jià)變換

在語法分析中,各種分析方法都有一定的局限性，對文法進(jìn)行種種限制,為了使某一語言能用某一種分析方法,常常根據(jù)限制條件對文法進(jìn)行變換.

86

872.4.2文法的等價(jià)變換2.4.3擴(kuò)充的BNF表示法在BNF上發(fā)展起來,相同表達(dá)效力,結(jié)構(gòu)上更簡單，清晰.一.專用符號{t}--t可重復(fù)任意次[t]--t可出現(xiàn)0次或1次

()--提因子例:G[N]:N

→ND|DN→D{D}D→0|1|…|9D→0|1|…|9例:G[E]:E→T|T+EE→T[+E]T→F|F*TT→F[*T]F→i|(E)F→i|(E)例:A→αβ1|αβ2|…|αβnA→α(β1|β2|…|βn)88二.擴(kuò)充BNF表示法的用途.

消除左遞歸,使文法在自頂向下分析過程中，能進(jìn)行分析處理.

例:G[E]:E→T{+T}T→F{*F}F→i|(E)892.4.3擴(kuò)充的BNF表示法2.5文法和語言的Chomsky分類如果對某文法G[S]，P中的每個(gè)規(guī)則具有下列形式：α→β,α∈V+,β∈V*,V=(VN∪VT)則稱該文法G為Chomsky0型文法或無限制性文法或短語結(jié)構(gòu)文法(Phrase

StructureGrammar)，記為PSG。0型文法產(chǎn)生的相應(yīng)語言稱為0型語言(無限制性語言或短語結(jié)構(gòu)語言)，記為L0(G)。四類文法對應(yīng)四類語言.2.5.10型文法與0型語言(圖靈機(jī))

定義2.19:90例[2-13]:P={S→ACaB,Ca→aaC,CB→DBCB→E,aD→Da,AD→AC,aE→Ea,AE→ε}SACaBAaaCBAaaEAaEaAEaaaa,SaaaaL0(G)={a2n|n>0}+

盡管0型文法不足以描述自然語言，但對程序設(shè)計(jì)語言的描述而言又太一般化,所以須對規(guī)則的形式加以限制.912.5.10型文法與0型語言(圖靈機(jī))2.5.21型文法與1型語言（線性界限自動機(jī)）

在自然語言中，一個(gè)句子或一個(gè)單詞的語法性質(zhì)往往和它所處的上下文有密切的關(guān)系，所以描述自然語言的文法一定是上下文有關(guān)文法。定義2.20：文法G[S]中每個(gè)規(guī)則即為：

αWβ→αωβ,W∈VN，α，β∈V*,ω∈V+

則稱G為1型文法（或上下文有關(guān)文法)→CSG產(chǎn)生的語言稱為1型語言L1（G）（或上下文有關(guān)語言，前后文有關(guān)語言）。92例：G[S]：S→aSBC|aBCG[S]是1型文法CB→DBDB→DCDC→BCaB→abbB→bbbC→bccC→ccS?aBC?abC?abcS?aSBC?aaBCBC?aabCBC?aabDBC?aabDCC?aabBCC?aabbcC?aabbcc……L1(G)={anbncn|n≥1}932.5.21型文法與1型語言（線性界限自動機(jī)）2.5.32型文法和2型語言（下推自動機(jī)）例：G[S]：S→aSbL2(G)={anbn|n≥1}S→abG[S]:S→Ac|ScL2(G)={anbncm|n,m≥1}A→ab|aAb

定義2.21:

文法G[S]中每一個(gè)規(guī)則形如：A→α，A∈VN，α∈V+,V=(VN∪VT)則稱G為2型文法，產(chǎn)生的語言稱為2型語言(CFG)，或上下文無關(guān)語言、前后文無關(guān)語言

L2（G）。注:

有些書中α∈V*，即允許出現(xiàn)A→ε的規(guī)則。大部分程序設(shè)計(jì)語言的文法近似于2型文法，所以是我們主要研究對象942.5.43型文法和3型語言（有限自動機(jī)）注:1.左線性文法A→Ba或A→a

右線性文法A→aB或A→a2.一般形式a∈VT*,定義中的是簡單形式，可以替換3.對于每一個(gè)左(右)線性文法，都存在一個(gè)與某等價(jià)

的右(左)線性文法.

定義2.22:文法G[S]中每個(gè)規(guī)則形如:A→Ba(A→aB)或A→aA，B∈VN，a∈VT

則稱G為3型文法(或正則文法)→RG產(chǎn)生的語言為3型語言(或正則語言)L3(G)95例:G[S]:S→Bc|ScB→Ab|Bb左線性A→Aa|aL3(G)={ambnck|m,n,k≥1}G[S]:S→aS|aAA→bA|bB右線性B→c|cB

962.5.43型文法和3型語言（有限自動機(jī)）

例:<標(biāo)識符>→<字母>|<標(biāo)識符><字母>|<標(biāo)識符><數(shù)字><無符號整數(shù)>→<數(shù)字>|<無符號整數(shù)><數(shù)字>

在程序設(shè)計(jì)語言中，與詞法有關(guān)的文法(單詞的語法規(guī)則）一般屬于3型文法.972.5.43型文法和3型語言（有限自動機(jī)）2.5.5四類文法的關(guān)系1.0型→3型,限制逐漸增加,描述語言的能力逐漸減弱。L0?L1?L2?L3

注:1型不允許A→ε,但2,3型允許.

文法文法名稱語言自動機(jī)0短語結(jié)構(gòu)文法短語結(jié)構(gòu)圖靈機(jī)(TM)1上下文有關(guān)文法上下文有關(guān)線性界限自動機(jī)(LBA)2上下文無關(guān)文法上下文無關(guān)下推自動機(jī)(PDA)3正則文法正則語言有限自動機(jī)(FA)2.四種語言可分別被四種自動機(jī)所接收.98992.6本章小結(jié)

1．形式語言是編譯技術(shù)的重要理論基礎(chǔ)，文法是形式語言最重要的概念之一2．文法是在形式上用以描述和規(guī)定語言結(jié)構(gòu)的方法，是用有限的手段描述無限的句子集合的方法之一3．二義性文法，產(chǎn)生句子語義上的不確定性，通過句子的不同語法樹可以判斷二義性問題4．文法的限制有兩方面，文法的實(shí)用限制、文法的等價(jià)變換5．Chomsky將文法分為四類(0型、1型、2型、3型)，四類文法對應(yīng)四類語言，與四類自動機(jī)相對應(yīng)。100總結(jié)

本章我們學(xué)習(xí)了形式語言的基本概念、文法和形式語言的定義、語法樹和二義性、文法的實(shí)用限制、文法和語言的Chomsky分類等內(nèi)容。下一章將學(xué)習(xí)編譯的另一個(gè)基本理論----自動機(jī)理論基礎(chǔ)。THANKS101THANKS新工科建設(shè)·計(jì)算機(jī)類系列教材

免費(fèi)提供編譯原理1026目錄第一章引言第二章形式語言理論基礎(chǔ)第三章自動機(jī)理論基礎(chǔ)第四章詞法分析第五章語法分析—自頂向下分析方法第六章語法分析—自底向上分析方法第七章語義分析及中間代碼的生成第八章代碼優(yōu)化第九章目標(biāo)代碼的生成第十章符號表和出錯(cuò)處理第十一章

面向?qū)ο笳Z言的編譯第十二章

并行編譯技術(shù)第十三章

軟件構(gòu)造1033自動機(jī)理論基礎(chǔ)本章主要介紹狀態(tài)轉(zhuǎn)換圖定義、有限自動機(jī)的理論及下推自動機(jī)的的理論。著重需要掌握以下內(nèi)容：確定的有限自動機(jī)DFA非確定的有限自動機(jī)NFANFA到DFA的轉(zhuǎn)換DFA的最小化下推自動機(jī)PDA104學(xué)習(xí)目標(biāo)

目錄3.1有限自動機(jī)的基本概念3.2確定有限自動機(jī)DFA的化簡3.3正則表達(dá)式形式定義3.4下推自動機(jī)PDA3.5本章小結(jié)1053.1有限自動機(jī)的基礎(chǔ)106定義3.1：有限自動機(jī)定義為一個(gè)五元組：D=(K,Σ,δ,S,F)。K是有窮的非空狀態(tài)集合；Σ是有窮的輸入字母表；δ是從K×Σ到K的映射，表示狀態(tài)的轉(zhuǎn)換（狀態(tài)轉(zhuǎn)換函數(shù)）；S是初始狀態(tài)；F是終止?fàn)顟B(tài)。確定有限自動機(jī)

(DFA)：每次轉(zhuǎn)換的后繼狀態(tài)都是唯一的不確定有限自動機(jī)(NFA)：轉(zhuǎn)換的后繼狀態(tài)不是唯一的3.1.1有限自動機(jī)的定義和表達(dá)式1.狀態(tài)轉(zhuǎn)換圖的引進(jìn)和構(gòu)造定義3.2：狀態(tài)轉(zhuǎn)換圖是定義在字母表上的有向圖，滿足以下三個(gè)條件：

至少存在一個(gè)初始結(jié)點(diǎn)

存在一些終止?fàn)顟B(tài)結(jié)點(diǎn)（也可為空）

每條邊上標(biāo)有字母表∑上的符號（也可為空串ε）107例：TG接收（or識別）的符號串：從某一初始結(jié)點(diǎn)到某一終止結(jié)

點(diǎn)的序列。TG所接收的符號串集合：L（TG）={ab，bab，abbb，……}狀態(tài)轉(zhuǎn)換圖：結(jié)點(diǎn)------狀態(tài)------文法的非終結(jié)符

初始結(jié)點(diǎn)--初始狀態(tài)

終止結(jié)點(diǎn)--終止?fàn)顟B(tài)--開始符號

邊--------轉(zhuǎn)換關(guān)系--終結(jié)符號∑={a，b}1080S1S2Sbbbba算法3.1

正則文法構(gòu)造狀態(tài)轉(zhuǎn)換圖算法

將S設(shè)為初始狀態(tài)（假定文法的字母表中不含符號S）以每一個(gè)非終結(jié)符號作為其它狀態(tài)對于形如A→b

的每個(gè)規(guī)則，引一條從初始狀態(tài)S到狀態(tài)A的邊，其標(biāo)記為b；

而對于形如A→Bc

的規(guī)則，引一條從狀態(tài)B到A的邊，其標(biāo)

記為c（其中A、B為非終結(jié)符號，b、c為終結(jié)符號）。④以文法開始符號作為終止?fàn)顟B(tài)。

特別地，一個(gè)狀態(tài)轉(zhuǎn)換圖可以不止一個(gè)初始狀態(tài)，也可以有不止一個(gè)終止?fàn)顟B(tài)。109

例3.1：文法G[Z]，其中，VN=｛Z,A,B｝，VT=｛a,b｝。Z→Za|Aa|BbA→Ba|aB→Ab|b1102.應(yīng)用狀態(tài)轉(zhuǎn)換圖識別句子識別句子：從開始狀態(tài)到終止?fàn)顟B(tài)經(jīng)過的邊上的符號序列。識別句子（α）的步驟：111定理3.1當(dāng)識別一個(gè)符號串α?xí)r，如果能從轉(zhuǎn)換圖的初始狀態(tài)出發(fā)行進(jìn)達(dá)到α的右端，那么，α為句子的充要條件是：最后的當(dāng)前狀態(tài)為終止?fàn)顟B(tài)。用狀態(tài)轉(zhuǎn)換圖識別句子的過程，稱為運(yùn)行狀態(tài)轉(zhuǎn)換圖。1121從開始狀態(tài)出發(fā)，以它作為當(dāng)前狀態(tài)，并從α的最左字符開始，重復(fù)第二步到達(dá)α的最右端為止2掃描α的下一個(gè)字符（當(dāng)前字符），在當(dāng)前狀態(tài)射出的各條邊中找出標(biāo)有該字符的邊并沿此邊前進(jìn)，以所達(dá)到的狀態(tài)作為下一個(gè)當(dāng)前狀態(tài)。例3.2：對句子ababaaa進(jìn)行分析并生成語法樹

當(dāng)前狀態(tài)輸入串的其余部分語法樹SababaaaAbabaaaBabaaaAbaaaBaaaAaaZaZ

1133.應(yīng)用狀態(tài)轉(zhuǎn)換圖為正則語言構(gòu)造正則文法狀態(tài)轉(zhuǎn)換正則文法正則語言

ε

a

ab

a|b

114b115正則文法：

A→CbC→Bb|bB→AbA→Ba|a例3.3正則語言{|n≥0}1163.1.2有限自動機(jī)的機(jī)器模型

有限自動機(jī)（FA，F(xiàn)initeAutomata）可看作一個(gè)機(jī)器模型，由一個(gè)帶讀頭的有限控制器和一條字符輸入帶組成。工作原理：讀頭從左到右掃描輸入帶，讀到一個(gè)字符，狀態(tài)改變，同時(shí)讀頭右移一個(gè)字符，…，直到讀頭讀到“#”，狀態(tài)進(jìn)入終止?fàn)顟B(tài)?？刂破髦邪ㄓ邢迋€(gè)狀態(tài)，讀入一個(gè)字符形成狀態(tài)轉(zhuǎn)換。

后繼狀態(tài)為自身狀態(tài)轉(zhuǎn)換后繼狀態(tài)為一個(gè)DFA后繼狀態(tài)為多個(gè)NFA

輸入帶ababa…#控制器1173.1.3

確定有限自動機(jī)（DFA）

定義3.3：DFA是一個(gè)五元組

D=(Κ,Σ,,?,F)

其中：Κ是狀態(tài)的非空有限集

Σ有窮的輸入字母表

是從ΚXΣ到Κ的映射，且為單值，即如果有轉(zhuǎn)換函數(shù)(,a)=,、∈Κ表示當(dāng)前狀態(tài)為，輸入符號為a時(shí)，轉(zhuǎn)換到

?初始狀態(tài)?∈Κ

F非空的終止?fàn)顟B(tài)集FΚDFA----DeterministicFiniteAotomaton118例3.4：由例3.1的狀態(tài)轉(zhuǎn)換圖構(gòu)造DFA如下

D1=

({S,Z,A,B},{a,b},,S,{Z})

其中：(S,a)=A,(S,b)=B

(A,a)=Z,(A,b)=B

(B,a)=A,(B,b)=Z

(Z,a)=Z

同理，由例3.3中的狀態(tài)轉(zhuǎn)換圖構(gòu)造確定有限自動機(jī)如下：D2=({S,A,B

,C,Z},{a,b},,S,{Z})

119(S,a)=A

(S,a)=C(A,b)=

(B,a)=

(B,b)=C(C,b)=

120定義3.5

由有限自動機(jī)接受的符號串集合稱為正則集，記為L（D）。121定義3.4對于某個(gè)DFAD=(K,Σ,δ,S,F)，如果δ(S,α)=P，P∈F，則稱字符串α可被該DFAD所接受(識別)。3.1.4有限自動機(jī)在計(jì)算機(jī)內(nèi)的表示

1、矩陣表示

例3.6

或

或

注：

S0表示初始狀態(tài)，0表示無后繼狀態(tài)

輸入狀態(tài)abS0=SAB

S1=AZB

S2=BAZ

S3=ZZ0ABZZZAB0122上例：

輸入狀態(tài)abc1232.表結(jié)構(gòu)表示狀態(tài)名射出邊數(shù)標(biāo)記1指向下一狀態(tài)……標(biāo)記k指向下一狀態(tài)k1243.1.5不確定有限自動機(jī)（NFA）定義3.6

NFA是一個(gè)五元組，=(Κ,Σ,,?,F)其中：Κ是狀態(tài)的非空有限集Σ有窮的輸入字母表是從ΚXΣ到Κ的子集的映射?開始狀態(tài)?ΚF終止?fàn)顟B(tài)FΚ125例：=(Κ,Σ,,?,F)其中

Κ={,,

}Σ={a,b}?={,}F={}(,a)={}(,b)={,}(,a)=Φ(,b)={}(,a)=Φ(,b)={}126

得出：

輸入狀態(tài)ab

127例3.7由正則文法G[Z]=(VN,VT,S,P)構(gòu)造NFA其中VN={Z,A,B}VT={a,b}P集為Z→Za|Aa|BbA→Ba|Za|aB→Ab|Ba|b128步驟當(dāng)前狀態(tài)輸入串余留部分可能的后繼狀態(tài)選擇狀態(tài)

1SbabbabbBB2BabbabbA,BA3AbbabbBB4BbabbZZ5ZabbA,ZA6AbbBB7BbZZ8.

例3.8對于輸入符號串babbabb運(yùn)行過程:129

由此可見，在NFA中由于某些狀態(tài)的轉(zhuǎn)換需從若干個(gè)可能的后繼狀態(tài)中進(jìn)行選擇，這種不確定性給識別過程帶來反復(fù)，影響了工作效率。

解決這一問題的一個(gè)方法就是下面將介紹的使NFA轉(zhuǎn)換成等價(jià)的DFA。1303.1.6NFA到DFA的等價(jià)轉(zhuǎn)換定理3.3：設(shè)L是一個(gè)為某NFA所接受的符號串集合，則存在一個(gè)接受L的DFA，即L(D)=L(N)。

算法3.2:NFAN=

(Κ,Σ,,?,F)DFAN’=(,,,,)

1、若NFA中全部初始狀態(tài)為,,…,

則令DFA的初始狀態(tài)=[,,…,]

[]表示由若干狀態(tài)構(gòu)成的某一狀態(tài)1312、設(shè)Q=[,,…,]是DFA的一個(gè)狀態(tài)

在NFA中，({,,…,},a)={,,…,}

則令([,,…,],a)=[,,…,]。3、重復(fù)第2步，直到不出現(xiàn)新的狀態(tài)為止。4、上面得到DFA的狀態(tài)集，映射,Σ不變。5、在DFA中，含有NFA終止?fàn)顟B(tài)的狀態(tài)均為DFA的終止?fàn)顟B(tài)。132例3.9=(Κ,Σ,,?,F)其中S={,}K={,,}Σ={a,b}F={}133

轉(zhuǎn)換：①=[,]②({,},a)={}({,},b)={,}∴([,],a)=[]([,],b)=[,]③({