編譯原理第5版-課件匯 劉銘 第1-3章 編譯概述-詞法分析與有窮自動(dòng)機(jī)

第1章編譯概述

—編譯程序的基礎(chǔ)知識(shí)編譯原理（第5版）課程說(shuō)明教材:《編譯原理》（第5版），電子工業(yè)出版社，2024年其他參考書(shū):

[1]AlfredAhoect.，Compilers:Principles,Techniques,andTools，北京：人民郵電出版社，PearsonEducation出版集團(tuán)，2002.2.[2]許暢等.編譯原理實(shí)踐與指導(dǎo)教程.北京：機(jī)械工業(yè)出版社2學(xué)時(shí)參考內(nèi)容講課學(xué)時(shí)1編譯概述22文法和語(yǔ)言的基本知識(shí)63詞法分析與有窮自動(dòng)機(jī)74語(yǔ)法分析155語(yǔ)法制導(dǎo)翻譯技術(shù)和中間代碼生成7內(nèi)容講課學(xué)時(shí)6符號(hào)表的組織與管理17代碼優(yōu)化48運(yùn)行時(shí)的存儲(chǔ)組織與管理29目標(biāo)代碼生成210并行編譯技術(shù)基本常識(shí)23評(píng)分參考評(píng)分項(xiàng)目占比考試70%平時(shí)成績(jī)30%4第1章編譯概述編譯原理這門(mén)課程主要介紹設(shè)計(jì)和構(gòu)造編譯程序的基本原理和常用的技術(shù)和方法。本章重點(diǎn)介紹編譯程序的基本概念編譯的過(guò)程編譯程序的結(jié)構(gòu)5第1章編譯概述編譯器與解釋器6CompilersInterpretersProgram+DataInterpreterOutput第1章編譯概述1954IBM704Software>Hardwareprice如何提高軟件的產(chǎn)量？JohnBackus1924‐2007

Speedcoding1953(10-20slower,解釋執(zhí)行300bytes=30%memory)

FORTRAN1(FormulasTranslation)1954-1957195850%()FORTRAN1第一個(gè)編譯器意義重大誕生大量理論+實(shí)踐現(xiàn)代編譯器仍遵循781.1翻譯程序與編譯程序

翻譯程序：將一種語(yǔ)言所寫(xiě)的程序譯成等價(jià)的另一種語(yǔ)言的程序。

源語(yǔ)言源程序目標(biāo)語(yǔ)言目標(biāo)程序高級(jí)語(yǔ)言程序機(jī)器語(yǔ)言程序翻譯程序#include<stdio.h>intmain(void){printf(“hello,world！\n");

return0;}00001010…..91.1翻譯程序與編譯程序

編譯程序：是一種翻譯程序，它將高級(jí)語(yǔ)言所寫(xiě)的源程序翻譯成等價(jià)的機(jī)器語(yǔ)言或匯編語(yǔ)言的目標(biāo)程序。

源程序高級(jí)語(yǔ)言程序編譯程序目標(biāo)程序匯編語(yǔ)言或者機(jī)器語(yǔ)言程序1.1翻譯程序與編譯程序程序運(yùn)行階段第一種情況：源程序編譯程序機(jī)器語(yǔ)言目標(biāo)程序初始數(shù)據(jù)運(yùn)行系統(tǒng)結(jié)果編譯階段運(yùn)行階段高級(jí)語(yǔ)言程序101.1翻譯程序與編譯程序源程序編譯程序機(jī)器語(yǔ)言目標(biāo)程序初始數(shù)據(jù)運(yùn)行系統(tǒng)結(jié)果編譯階段運(yùn)行階段匯編程序匯編語(yǔ)言目標(biāo)程序匯編階段高級(jí)語(yǔ)言程序11程序運(yùn)行階段第二種情況：1.2編譯過(guò)程與編譯程序的基本結(jié)構(gòu)自然語(yǔ)言翻譯Thisisasentence.Isthisasentence12

詞法分析

語(yǔ)法分析

語(yǔ)義分析

修飾工作

翻譯成文

編譯過(guò)程編譯過(guò)程一般可劃分為五個(gè)階段：13

詞法分析

語(yǔ)法分析

語(yǔ)義分析和中間代碼生成

代碼優(yōu)化

目標(biāo)代碼生成編譯過(guò)程例如：程序片段14floatr,h,s；s=2*3.1416*r*(r＋h);或Ifx==ythenz=5;elsez=10;1）詞法分析詞法分析：是對(duì)構(gòu)成源程序的字符串從左到右進(jìn)行掃描和分解，根據(jù)語(yǔ)言的詞法規(guī)則，識(shí)別出具有獨(dú)立意義的單詞(也稱單詞符號(hào)、符號(hào)

)。15詞法規(guī)則詞法規(guī)則：是單詞符號(hào)的形成規(guī)則,它規(guī)定了字符串如何構(gòu)成一個(gè)單詞符號(hào)。16

例子：

floatr,h,s;

s=2*3.1416*r*(h＋r);基本字float 標(biāo)識(shí)符r、h、s常數(shù)3.1416、2 算符*、＋

界符（、）、;、,、=id1=2*3.1416*id2

*(id2

＋id3);2）語(yǔ)法分析語(yǔ)法分析：在詞法分析的基礎(chǔ)上,根據(jù)語(yǔ)言的語(yǔ)法規(guī)則從單詞符號(hào)串中識(shí)別出各種語(yǔ)法單位(如表達(dá)式、說(shuō)明、語(yǔ)句等),并進(jìn)行語(yǔ)法檢查,即檢查各種語(yǔ)法單位在語(yǔ)法結(jié)構(gòu)上的正確性；產(chǎn)生形成語(yǔ)法樹(shù)。17自然語(yǔ)言語(yǔ)法樹(shù)Thislineis

alongersentence18Articlenounverbaritcleadjectivenounsubjectobjectsentence語(yǔ)法樹(shù)ifX==ythen

Z=5;elseZ=10;19relationassignassignpredicateElse-stmtThen-stmtIf-then-elseX==yZ

5Z10語(yǔ)法規(guī)則語(yǔ)法規(guī)則：規(guī)定了如何從單詞符號(hào)形成語(yǔ)法單位。語(yǔ)法規(guī)則是語(yǔ)法單位的形成規(guī)則。例子：floatr，h，s；s=2*3.1416*r*(h＋r)；20“s”是<變量>；“2*3.1416*r*(h＋r)”組合成<表達(dá)式>；<變量>=<表達(dá)式>組合成<賦值語(yǔ)句>。213）語(yǔ)義分析和中間代碼生成語(yǔ)義分析：首先對(duì)每種語(yǔ)法單位進(jìn)行靜態(tài)的語(yǔ)義審查，然后分析其含義，并用另一種語(yǔ)言形式來(lái)描述這種語(yǔ)義。比源語(yǔ)言更接近于目標(biāo)語(yǔ)言

（中間代碼或直接用目標(biāo)語(yǔ)言）223）語(yǔ)義分析和中間代碼生成例子：將s=2*3.1416*r*(h＋r)翻譯成如下形式的四元式中間代碼：(1)(*,2,3.1416,T1)(2)(*,T1, r,T2)(3)(+,h, r,T3)(4)(*,T2,T3,T4)(5)(=,T4,__,s)例子：將s=2*3.1416*r*(h＋r)翻譯成如下形式的四元式中間代碼：233）語(yǔ)義分析和中間代碼生成T1=2*3.1416T2=T1*id1T3=id2+id3T4=T2*T3Id1=T4問(wèn)題作用域：{intJack=3;{intJack=4;cout<<Jack;}}二義性：JacksaidJerrylefthishomeworkathome244）代碼優(yōu)化

代碼優(yōu)化：對(duì)前階段產(chǎn)生的中間代碼進(jìn)行等價(jià)變換或改造，以期獲得更為高效即省時(shí)間和空間的目標(biāo)代碼。主要包括：局部?jī)?yōu)化和循環(huán)優(yōu)化等，例子：四元式經(jīng)局部?jī)?yōu)化后得：25(1)(*,6.28,

id2,T2)(2)(+,id3,id2,T3)(3)(*,T2,T3,T4)(4)(=,T4,__,id1)5）目標(biāo)代碼生成目標(biāo)代碼生成：將中間代碼變換成特定機(jī)器上的絕對(duì)指令代碼或可重定位的指令代碼或匯編指令代碼。26表格管理和錯(cuò)誤處理在編譯程序的各個(gè)階段中，都涉及表格管理和錯(cuò)誤處理。

表格：記錄源程序中所提供的、在編譯過(guò)程中產(chǎn)生的信息；表格管理：構(gòu)造、查找、修改或存取表格中的信息；錯(cuò)誤處理：編譯程序在編譯過(guò)程中，應(yīng)具有廣泛的程序查錯(cuò)能力，并能準(zhǔn)確地報(bào)告錯(cuò)誤的種類及出錯(cuò)位置，以便用戶查找和糾正。27編譯程序的結(jié)構(gòu)28

源程序語(yǔ)義分析和中間代碼生成程序語(yǔ)法分析程序詞法分析程序代碼優(yōu)化程序目標(biāo)代碼生成程序

目標(biāo)程序表格管理程序出錯(cuò)處理程序(字符串)1.3編譯程序的生成方法編譯程序是一個(gè)復(fù)雜的系統(tǒng)程序，需要考慮以下幾方面：29

對(duì)源語(yǔ)言和目標(biāo)語(yǔ)言認(rèn)真分析

設(shè)計(jì)編譯算法

選擇語(yǔ)言編制程序

調(diào)試編譯程序

提交相關(guān)文檔資料編譯程序的自動(dòng)生成隨著編譯技術(shù)和自動(dòng)機(jī)理論的發(fā)展,近年來(lái)已研制出了一些編譯程序的自動(dòng)生成系統(tǒng)：詞法分析程序的自動(dòng)生成系統(tǒng)：Flex/Lex;語(yǔ)法分析程序自動(dòng)生成系統(tǒng)：Bison/YACC等30編譯程序的自動(dòng)生成生成編譯程序的方法還常采用自編譯方式和移植方式。隨著并行技術(shù)和并行語(yǔ)言的發(fā)展，處理并行語(yǔ)言的并行編譯技術(shù)和將串行程序轉(zhuǎn)換成并行程序的自動(dòng)并行編譯技術(shù)正在深入研究之中。311.4編譯技術(shù)在軟件開(kāi)發(fā)中的應(yīng)用大部分系統(tǒng)軟件和應(yīng)用軟件的開(kāi)發(fā)，通常要用到編譯的原理和技術(shù)。例子：詞法分析器的串匹配技術(shù)用于正文編輯器、信息檢索系統(tǒng)和模式識(shí)別程序；上下文無(wú)關(guān)文法和語(yǔ)法制導(dǎo)定義用于排版、繪圖系統(tǒng)和語(yǔ)言結(jié)構(gòu)化編輯器中；代碼優(yōu)化技術(shù)用于程序驗(yàn)證器和從非結(jié)構(gòu)化的程序產(chǎn)生結(jié)構(gòu)化程序中。32本章小結(jié)什么是編譯程序編譯過(guò)程的五個(gè)階段編譯程序的結(jié)構(gòu)框圖33編譯程序是一種翻譯程序，它將高級(jí)語(yǔ)言所寫(xiě)的源程序翻譯成等價(jià)的機(jī)器語(yǔ)言或匯編語(yǔ)言的目標(biāo)程序。詞法分析、語(yǔ)法分析、語(yǔ)義分析和中間代碼生成、代碼優(yōu)化、目標(biāo)代碼生成本章小結(jié)34

源程序語(yǔ)義分析和中間代碼生成程序語(yǔ)法分析程序詞法分析程序代碼優(yōu)化程序目標(biāo)代碼生成程序

目標(biāo)程序表格管理程序出錯(cuò)處理程序(字符串)討論

351為什么有這么多編程語(yǔ)言？（科學(xué)計(jì)算浮點(diǎn)數(shù)組FORTRAN，商業(yè)應(yīng)用報(bào)表信息提取SQL，系統(tǒng)控制操縱資源C/C++)2為什么還有新語(yǔ)言？程序員培訓(xùn)成本廣泛使用的語(yǔ)言適應(yīng)新變化緩慢開(kāi)始新語(yǔ)言容易新應(yīng)用范圍新語(yǔ)言長(zhǎng)得像舊的（javavsC++）3什么是好編程語(yǔ)言？沒(méi)有統(tǒng)一的語(yǔ)言設(shè)計(jì)標(biāo)準(zhǔn)用戶越多就越好？第2章文法和語(yǔ)言的基本知識(shí)36研究語(yǔ)言的翻譯，首先要解決的問(wèn)題語(yǔ)言自身如何描述？第2章文法和語(yǔ)言的基本知識(shí)37形式語(yǔ)言理論是編譯的重要理論基礎(chǔ)。本章主要介紹編譯理論中用到的有關(guān)形式語(yǔ)言理論的最基本概念，重點(diǎn)介紹如何采用形式化的方法描述程序設(shè)計(jì)語(yǔ)言。第2章文法和語(yǔ)言的基本知識(shí)喬姆斯基（NoamChomsky,1928--）美國(guó)語(yǔ)言學(xué)家，轉(zhuǎn)換-生成語(yǔ)法的創(chuàng)始人。1955年完成博士論文《轉(zhuǎn)換分析》，獲得博士學(xué)位。曾任該校語(yǔ)言學(xué)與哲學(xué)系主任，并任該校認(rèn)知科學(xué)研究中心主任，為語(yǔ)言學(xué)界培養(yǎng)了一批有素養(yǎng)的學(xué)者。38第2章文法和語(yǔ)言的基本知識(shí)39字母表和符號(hào)串文法和語(yǔ)言的形式定義短語(yǔ)、直接短語(yǔ)和句柄語(yǔ)法樹(shù)和文法的二義性文法和語(yǔ)言的分類2.1概述例如語(yǔ)句s＝2*3.1416*r*(r+h)40語(yǔ)法：賦值語(yǔ)句由一個(gè)變量，后隨一個(gè)賦值號(hào)“＝”，其后面再跟一個(gè)表達(dá)式構(gòu)成。語(yǔ)義：首先計(jì)算語(yǔ)句右部表達(dá)式的值，然后把所得結(jié)果送給左部變量中。語(yǔ)用：賦值語(yǔ)句可用來(lái)計(jì)算和保存表達(dá)式的值。形式化的方法,是用一整套帶有嚴(yán)格規(guī)定的符號(hào)體系來(lái)描述問(wèn)題的方法形式語(yǔ)言(FormalLanguage)理論是編譯的重要理論基礎(chǔ)如何采用形式化的方法描述程序設(shè)計(jì)語(yǔ)言2.1概述412.2字母表和符號(hào)串1.字母表(Alphabet)元素的非空有窮集合。例如，∑={a,b,c}根據(jù)字母表的定義，Σ是字母表，它有a、b、c三個(gè)元素例如，∑'={0,1}組成?！啤亲帜副恚?、1兩個(gè)元素422.2字母表和符號(hào)串2.符號(hào)（字符）Symbol字母表中的元素稱為符號(hào)或稱為字符。43

2.2字母表和符號(hào)串3.符號(hào)串(Stringorword)（字）符號(hào)的有窮序列稱為符號(hào)串。設(shè)有字母表∑={a,b,c}符號(hào)串a(chǎn)，b，ab，ba，cba，

abc…

442.2字母表和符號(hào)串不包含任何符號(hào)的符號(hào)串,稱為空符號(hào)串，用ε表示。45空符號(hào)串由0個(gè)符號(hào)組成，其長(zhǎng)度|ε|=02.2字母表和符號(hào)串1.符號(hào)串的連結(jié)設(shè)x和y是符號(hào)串，則串xy稱為它們的連結(jié)。例如，設(shè)X＝ABC，Y＝10A則XY＝ABC10AYX＝

10AABC462.2字母表和符號(hào)串2.集合的乘積設(shè)A和B是符號(hào)串的集合,則A和B的乘積定義為：47AB={xy|x∈A,y∈B}2.2字母表和符號(hào)串例如：設(shè)A={a,b},B={c,d}48{

}A＝A{

}＝

A則AB={ac,ad,bc,bd}由于對(duì)任意的符號(hào)串x，總有

x=x

=x所以,對(duì)任意集合A,我們有:

是符號(hào)串{

}表示由空符號(hào)串

所組成的集合Φ表示空集合{}2.2字母表和符號(hào)串492.2字母表和符號(hào)串3.符號(hào)串的冪運(yùn)算50設(shè)x是符號(hào)串,x的冪運(yùn)算定義為：x0=

x1=xx2=xxx3=xxx

…xn=xx…x=xxn-1(n>0)n注意：x0≠12.2字母表和符號(hào)串例如,設(shè)x＝abc則51x0=__x1=__x2=xx=__

…2.2字母表和符號(hào)串4.集合的冪運(yùn)算設(shè)A是符號(hào)串的集合，則集合A的冪運(yùn)算定義為A0={}A1=AA2=AA…An=AA…A(n個(gè))=AAn-1(n>0)52例如，設(shè)A={a,b}，則A0=__A1=A={a,b}A2=AA=_______

…A3=AAA=A2A={aaa,aab,aba,abb,baa,bab,bba,bbb}2.2字母表和符號(hào)串532.2字母表和符號(hào)串5.集合A的正閉包A＋與閉包A*54設(shè)A是符號(hào)串的集合，則A的正閉包A＋和A的閉包A*的定義為:A+=A1∪A2∪…∪An…A*=A0∪A1∪A2∪…∪An…A*={ε}∪A+2.2字母表和符號(hào)串例如，設(shè)A={a,b},則：55A+={a,b,aa,ab,ba,bb,aaa,aab,…}A*={ε,a,b,aa,ab,ba,bb,aaa,aab,…}2.3.1形式語(yǔ)言(FormalLanguage)56每個(gè)形式語(yǔ)言都是某個(gè)字母表上按某種規(guī)則構(gòu)成的所有符號(hào)串的集合。序列的集合稱為形式語(yǔ)言。??NoteverystringofEnglishcharactersisanEnglishsentence??Note:ASCIIcharactersetisdifferentfromEnglishcharacterset57Alphabet=EnglishcharactersLanguage=EnglishsentencesAlphabet=ASCIILanguage=Cprograms2.3.1形式語(yǔ)言例如，設(shè)有字母表A={a,b,c}，則58

均表示字母表A上的一個(gè)形式語(yǔ)言。L1={a,b,c}L2={a,aa,ab,ac}L3={c,cc}2.3.1形式語(yǔ)言例如，設(shè)字母表∑={0,1},則59∑+=∑1∪∑2∪∑3∪…={0,1,00,10,11,01,000,100,…}當(dāng)語(yǔ)言為無(wú)窮集合時(shí)，如何能描述這個(gè)集合呢？A→0A→1A→A0A→A1∑+=∑1∪∑2∪∑3∪…∑+={0,1,00,10,11,01,000,100,…}A01001001112.3.1形式語(yǔ)言60從無(wú)窮到有窮2.3.1形式語(yǔ)言運(yùn)用類似于遞歸、數(shù)學(xué)歸納法的方法，解決無(wú)窮語(yǔ)言的問(wèn)題。61有窮規(guī)則無(wú)窮集合2.3.1形式語(yǔ)言Lindenmayer系統(tǒng)（L

System)是1968年由匈牙利生物學(xué)家林登麥伊爾提出的有關(guān)生長(zhǎng)發(fā)展中的細(xì)胞交互作用的數(shù)學(xué)模型，尤其被廣泛應(yīng)用于植物生長(zhǎng)過(guò)程的研究。622.3.1形式語(yǔ)言自動(dòng)機(jī)理論:形式語(yǔ)言和形式文法喬姆斯基層級(jí)文法語(yǔ)言極小自動(dòng)機(jī)類型0無(wú)限制遞歸可枚舉圖靈機(jī)n/a(無(wú)公用名)遞歸判定器類型1上下文有關(guān)上下文有關(guān)線性有界n/a附標(biāo)附標(biāo)嵌套堆棧n/a樹(shù)-鄰接適度上下文有關(guān)嵌入下推類型2上下文無(wú)關(guān)上下文無(wú)關(guān)非確定下推n/a確定上下文無(wú)關(guān)確定上下文無(wú)關(guān)確定下推類型3正則正則有限每個(gè)語(yǔ)言或文法范疇都是其直接上面的范疇的真子集。632.3.2文法的形式定義1.

規(guī)則

也稱產(chǎn)生式規(guī)則是一個(gè)符號(hào)與一個(gè)符號(hào)串的有序?qū)Γˋ,β），寫(xiě)作：64A→β（或A∷＝β)2.3.2文法的形式定義65例如，前述例中一組規(guī)則

A→0A→1A→A0A→A1∑+={0,1,00,10,11,01,000,100,…}2.3.2文法的形式定義2.文法規(guī)則的非空有窮集合，通常表示成四元組66

VN是規(guī)則中非終結(jié)符號(hào)的集合。VT是規(guī)則中終結(jié)符號(hào)的集合。P

是文法規(guī)則的集合。

G=(VN,VT,P,S)開(kāi)始符合關(guān)鍵縮寫(xiě)為：A→

1|

2|…

|

nA→

1A→

2A→

n

…

對(duì)左部相同的規(guī)則候選式2.3.2文法的形式定義672.3.2文法的形式定義前例中描述∑+的文法是:68G=(VN，VT，P，S)VN={A}VT={0，1}P={A→0|1|A0|A1}S=A∑+={0,1,00,10,11,01,000,100,…}2.3.2文法的形式定義例1

設(shè)字母表∑={a,b}，

設(shè)計(jì)一個(gè)文法描述語(yǔ)言L={a2n,b2n|n≥1}69當(dāng)n＝1L={____}……L={aa,bb,aaaa,bbbb,aaaaaa,bbbbbb,…}L={a2n,b2n|n≥1}當(dāng)n＝2L={_______}當(dāng)n＝3L={aaaaaa,bbbbbb}L是由偶數(shù)個(gè)a，偶數(shù)個(gè)b這樣的符號(hào)串組成的集合2.3.2文法的形式定義702.3.2文法的形式定義71因此，定義語(yǔ)言L的文法

G=(VN，VT，P，S)其中：

VN={A,B,D}VT={a,b}P={A→aaS=AB→aaD→bb|bbD}|bb|bbD注意:VT≠{aa,bb}|aaB|aaB2.3.2文法的形式定義72問(wèn)題:描述該語(yǔ)言的文法是否唯一？P':A→B|DB→aa|aBaD→bb|bDbG"是否是描述該語(yǔ)言的文法？2.3.2文法的形式定義73G"=({A},{a,b},P",A)其中P"={A→aa|bb|Aaa|Abb}2.3.2文法的形式定義例2試設(shè)計(jì)一個(gè)表示所有標(biāo)識(shí)符的文法74

2.3.2文法的形式定義75G=(VN，VT，P，S)其中：

VN={I,L,D}VT={a,b,c,…

x,y,z,0,1,2,…,9}P={I→LS=IL→a|b|c|…|x|y|zD→0|1|2|3|…|9}|IL|ID2.3.2文法的形式定義76將定義標(biāo)識(shí)符的文法設(shè)計(jì)成：

G=(VN，VT，P，S)P={I→L|IDL→a|b|c|…|x|y|zD→0|1|2|3|…|9}2.3.2文法的形式定義77字母字母或數(shù)字串2.3.2文法的形式定義P:I→L|LTT→L|D|LT|DTL→a|b|c|…|x|y|zD→0|1|2|3|…|978字母字母或數(shù)字串2.3.2文法的形式定義例3已知自然語(yǔ)言描述的算數(shù)表達(dá)式如下，請(qǐng)用文法定義之。算術(shù)表達(dá)式定義用自然語(yǔ)言描述如下：變量i是一個(gè)表達(dá)式；若

E1和E2是算術(shù)表達(dá)式,則E1＋E2、E1*E2、(E1)也是算術(shù)表達(dá)式。79

G=({E},{i,+,*,(,)},P,E)其中P={E→i|E+E|E*E|(E)}{i,i+i,i*i,i+i*i,(i+i),…}2.3.2文法的形式定義802.3.2文法的形式定義例4設(shè)字母表Σ={a,b},

試設(shè)計(jì)一個(gè)文法，描述語(yǔ)言L={abna|n≥0}81請(qǐng)同學(xué)分析,該語(yǔ)言中串的結(jié)構(gòu)特征是?

2.3.2文法的形式定義例5設(shè)字母表∑={(,)},

試設(shè)計(jì)一個(gè)文法描述語(yǔ)言L={(n)n|n≥0}82請(qǐng)同學(xué)分析,該語(yǔ)言中串的結(jié)構(gòu)特征是?2.3.3語(yǔ)言的形式定義1.直接推導(dǎo)83令G是一文法，稱xAy直接推導(dǎo)出xαy，即xAy

xαy僅A→α是G的一條規(guī)則,且x,y

(VN∪VT)*。從符號(hào)串xAy直接推導(dǎo)出xαy僅使用一次規(guī)則2.3.3語(yǔ)言的形式定義例如，設(shè)有文法G[S]:84S

01使用規(guī)則S

01此時(shí)x＝

，y＝

P為：S→01|0S1

有如下直接推導(dǎo)：S

0S1使用規(guī)則S

0S1此時(shí)x＝

，y＝

0S1

0011使用規(guī)則S

01此時(shí)x＝0，y＝100S11

000S111使用規(guī)則S

0S1此時(shí)x＝00,y＝11000S111

00001111使用規(guī)則S

01此時(shí)x＝000y＝111S→01|0S12.3.3語(yǔ)言的形式定義852.3.3語(yǔ)言的形式定義2.推導(dǎo)86

如果存在一個(gè)直接推導(dǎo)序列：α0

α1

α2

…

αn從0出發(fā)，經(jīng)一步或若干步（使用若干次規(guī)則）可推導(dǎo)出n對(duì)i+i*i有如下直接推導(dǎo)序列:我們可記為

其中P為：E→E+T|TT→T*F|FF→(E)|iE

E+T

T+T

F+T

i+T

i+T*F

i+F*F

i+i*F

i+i*iEi+i*i+2.3.3語(yǔ)言的形式定義例設(shè)有文法G[E]=({E,T,F},{i,+,*,(,)},P,E)872.3.3語(yǔ)言的形式定義3．廣義推導(dǎo)88我們有：

0

n表示從

0出發(fā)，經(jīng)0步或若干步，可推導(dǎo)出n。*

0

n意味著0

n或者0=

n。*+EE*Ei+i*i*E→E+T|TT→T*F|FF→(E)|i2.3.3語(yǔ)言的形式定義4.句型和句子89設(shè)有文法G[S]（S是文法G的開(kāi)始符號(hào)）

如果S

x,x

∈(VN∪VT)*

則稱符號(hào)串x

為文法G[S]的句型。*

如果S

x,x

∈VT*

則稱符號(hào)串x為文法G[S]的句子。*我們有:

符號(hào)串01、0S1、00S11和000111都是文法G[S]的句型；01和000111又是文法G[S]的句子。S

01*S

0S1*S

00S11*S

000111*2.3.3語(yǔ)言的形式定義例1設(shè)有文法G[S]：S→01|0S190試證明符號(hào)串(i*i+i)是文法G[E]的一個(gè)句子。E→E+E|E*E|(E)|i2.3.3語(yǔ)言的形式定義例2設(shè)有文法G[E]：91E(E)(E+E)(E*E+E)(i*E+E)(i*i+E)(i*i+i)即有E(i*i+i),所以符號(hào)串(i+i*i)是文法G[E]的一個(gè)句子。*2.3.3語(yǔ)言的形式定義E→E+E|E*E|(E)|i922.3.3語(yǔ)言的形式定義5．語(yǔ)言

文法G[S]產(chǎn)生的所有句子的集合稱為文法G所定義的語(yǔ)言,記為L(zhǎng)(G[S])：

L(G[S])={x|Sx且x∈VT*}93*2.3.3語(yǔ)言的形式定義94例3設(shè)有文法G[S]：S→01|0S1求該文法所描述的語(yǔ)言是什么？2.3.3語(yǔ)言的形式定義95我們應(yīng)用第二個(gè)規(guī)則n－1次，然后再應(yīng)用第一個(gè)規(guī)則1次，有：S0S100S11…0n-1S1n-10n1n即S0n1n*可見(jiàn)，此文法定義的語(yǔ)言為L(zhǎng)(G[S])={0n1n|n≥1}S→01|0S12.3.3語(yǔ)言的形式定義96例4設(shè)有文法G[S]：S→0S|1S|ε該文法所定義的語(yǔ)言是什么？由該文法所確定的語(yǔ)言為L(zhǎng)(G[S])={ε,0,1,00,01,10,11,…}={x|x∈{0,1}*}例5設(shè)有文法G[A]：該文法所定義的語(yǔ)言是什么？

A→yBB→xB|x2.3.3語(yǔ)言的形式定義972.3.3語(yǔ)言的形式定義98形式語(yǔ)言理論可以證明如下兩點(diǎn)：(1)給定一種語(yǔ)言，能確定其文法，但這種文法不是唯一的，即：L→G1或G2或…(2)給定一個(gè)文法，就能從結(jié)構(gòu)上唯一確定其語(yǔ)言，即：G→L(G)；2.3.4規(guī)范推導(dǎo)和規(guī)范歸約99例如，設(shè)有文法G[N1]N1→NN→ND|DD→0|1|2①N1NNDN2D212②N1NNDDD1D12③N1NNDDDD212句子12有下列三種不同的推導(dǎo)序列:2.3.4規(guī)范推導(dǎo)和規(guī)范歸約100例設(shè)有文法G[S]:請(qǐng)給出句子101001的最右、最左推導(dǎo)。

S→ABA→A0|1BB→0|S12.3.4規(guī)范推導(dǎo)和規(guī)范歸約101S

AB

AS1

AAB1

AA01

A1B01

A1001

1B1001

101001句子101001的最右推導(dǎo)為:S→ABA→A0|1BB→0|S12.3.4規(guī)范推導(dǎo)和規(guī)范歸約最左推導(dǎo)：是指在推導(dǎo)過(guò)程中任何一步α

β(α和β是句型),都是對(duì)α的最左非終結(jié)符進(jìn)行替換。102句子101001的最左推導(dǎo)為：S→ABA→A0|1BB→0|S1S

AB

1BB

10B

10S1

10AB1

101BB1

1010B1

101001若用

表示歸約，設(shè)A→α是文法G中的一個(gè)規(guī)則，則我們有：.xAyxαyxαyxAy.2.3.4規(guī)范推導(dǎo)和規(guī)范歸約歸約是與推導(dǎo)相對(duì)的概念103則有規(guī)范歸約：規(guī)范推導(dǎo)的逆過(guò)程，稱為最左歸約，也稱為規(guī)范歸約。N1NNDN2D21212D2.N2.ND.N.N1.2.3.4規(guī)范推導(dǎo)和規(guī)范歸約例如，例文法G[N1]中有規(guī)范推導(dǎo)：1042.3.5遞歸規(guī)則與文法的遞歸性遞歸規(guī)則105如果文法中有規(guī)則A→A…稱為規(guī)則左遞歸。如果文法中有規(guī)則A→…A稱為規(guī)則右遞歸。如果文法中有規(guī)則A→…A…稱為規(guī)則遞歸。2.3.5遞歸規(guī)則與文法的遞歸性文法的遞歸性106若文法中有推導(dǎo)AA…稱文法左遞歸。+若文法中有推導(dǎo)A

…

A稱文法右遞歸。+若文法中有推導(dǎo)A

…A…稱文法遞歸。+這三條規(guī)則都不是遞歸規(guī)則，但有

U→VxV→Uy|zU

VxUyx則該文法是左遞歸的。2.3.5遞歸規(guī)則與文法的遞歸性例如文法中有如下規(guī)則：107由于該文法無(wú)遞歸性，由它所描述的語(yǔ)言是有窮的。該文法描述的語(yǔ)言為:A→aB|bBB→a|bL(G[A])={}2.3.5遞歸規(guī)則與文法的遞歸性例2考慮文法G[A]：108aa,ab,ba,bb定義的語(yǔ)言為N1→NN→ND|DD→0|1|22.3.5遞歸規(guī)則與文法的遞歸性例3考慮文法G[N1]109{0,1,2}+課堂練習(xí)1設(shè)文法的規(guī)則如下：A→A1|A0|Aa|Ac|a|b|c，

該文法的句子是。A.bc10B.bbbbC.bcbcD.10012若一個(gè)不含多余規(guī)則的文法是遞歸的，則該文法生成語(yǔ)言的句子個(gè)數(shù)______。A.是有窮的B.是無(wú)窮的

C.對(duì)具體文法才可以確定D.無(wú)法確定1102.4短語(yǔ)、直接短語(yǔ)和句柄短語(yǔ)G[s]是一個(gè)文法,假定αβδ是文法G的一個(gè)句型，如果有則稱β是相對(duì)于非終結(jié)符A的,句型αβδ的短語(yǔ)。S

αAδ*+且A

β

2.4短語(yǔ)、直接短語(yǔ)和句柄直接短語(yǔ)則稱β是直接短語(yǔ)。S

αAδ*且A

β

令G是一個(gè)文法，S是文法的開(kāi)始符號(hào)，假定αβδ是文法G的一個(gè)句型，如果有2.4短語(yǔ)、直接短語(yǔ)和句柄句柄

一個(gè)句型的最左直接短語(yǔ)稱為該句型的句柄。句柄特征：(1)它是直接短語(yǔ)，即某規(guī)則右部。(2)它具有最左性。2.4短語(yǔ)、直接短語(yǔ)和句柄例如設(shè)有文法G[S]=({S,A,B},{a,b},P,S)

其中P為：求句型baSb的全部短語(yǔ)、直接短語(yǔ)和句柄。S

ABA

Aa|bBB

a|Sb2.5語(yǔ)法樹(shù)與文法的二義性推導(dǎo)和語(yǔ)法樹(shù)1.語(yǔ)法樹(shù)對(duì)句型的推導(dǎo)過(guò)程給出一種圖形表示,這種表示稱為語(yǔ)法樹(shù)，也稱推導(dǎo)樹(shù)。2.5.1推導(dǎo)和語(yǔ)法樹(shù)例如設(shè)有文法G[E]:構(gòu)造句型i*i+i的語(yǔ)法樹(shù)。E

E+T|E–T|TT

T*F|T/F|FF

(E)|i2.5.1推導(dǎo)和語(yǔ)法樹(shù)根據(jù)推導(dǎo)過(guò)程構(gòu)造句型i*i+i的語(yǔ)法樹(shù)如下：EE+TEE+TT+TTT*F+TT*FF*F+TFi*F+Tii*i+Tii*i+FFi*i+ii2.5.1推導(dǎo)和語(yǔ)法樹(shù)2.子樹(shù)語(yǔ)法樹(shù)的子樹(shù)是由某一結(jié)點(diǎn)連同所有分枝組成的部分。EE+TTT*FFiiFi2.5.1推導(dǎo)和語(yǔ)法樹(shù)句型的短語(yǔ)、直接短語(yǔ)和句柄的直觀解釋：短語(yǔ)：子樹(shù)的末端結(jié)點(diǎn)形成的符號(hào)串是相對(duì)于子樹(shù)根的短語(yǔ)。直接短語(yǔ)：簡(jiǎn)單子樹(shù)的末端結(jié)點(diǎn)形成的符號(hào)串是相對(duì)于簡(jiǎn)單子樹(shù)根的直接短語(yǔ)。句柄：最左簡(jiǎn)單子樹(shù)的末端結(jié)點(diǎn)形成的符號(hào)串是句柄。2.5.1推導(dǎo)和語(yǔ)法樹(shù)短語(yǔ):EE+TTT*FFiiFii*i+ii*i第一個(gè)i第二個(gè)i第三個(gè)i三個(gè)i都是直接短語(yǔ)第一個(gè)i是句柄句子i*i+i2.5.1推導(dǎo)和語(yǔ)法樹(shù)前例對(duì)文法G[S]=({S,A,B},{a,b},P,S)其中P為：S

ABA

Aa|bBB

a|Sb2.5.1推導(dǎo)和語(yǔ)法樹(shù)分析

首先根據(jù)句型baSb的推導(dǎo)過(guò)程畫(huà)出對(duì)應(yīng)的語(yǔ)法樹(shù)如下：

Sb

為句型的相對(duì)于B的短語(yǔ)、直接短語(yǔ)baSb

為句型的相對(duì)于S的短語(yǔ)ba

為句型的相對(duì)于A的短語(yǔ)a

句型的相對(duì)于B的短語(yǔ)、直接短語(yǔ)和句柄SABbBBbaBbaSbSABASbbBSbbaSbSABbBSba由語(yǔ)法樹(shù)可知文法的某個(gè)句型是否只對(duì)應(yīng)唯一的一棵語(yǔ)法樹(shù)呢？或者，它是否只有唯一的一個(gè)最左推導(dǎo)呢？它是否只有唯一的一個(gè)最右推導(dǎo)呢？2.5.2文法的二義性對(duì)于文法G中任一句型的推導(dǎo)序列,我們總能為它構(gòu)造一棵語(yǔ)法樹(shù)。問(wèn)題：2.5.2文法的二義性文法G[E]：

E

E+E|E*E|(E)|i2.5.2文法的二義性最左推導(dǎo)1EE+EE*E+Ei*E+Ei*i+Ei*i+i

EE*Ei*Ei*E+Ei*i+Ei*i+i

EE*EE+EiiiEE+EE*Eiii最左推導(dǎo)22.5.2文法的二義性如果一個(gè)文法存在某個(gè)句子，對(duì)應(yīng)兩棵不同的語(yǔ)法樹(shù)，則這個(gè)文法是二義性的。如果一個(gè)文法存在某個(gè)句子，有兩個(gè)不同的最左(最右)推導(dǎo)，則這個(gè)文法是二義性的。E

E+E|E*E|(E)|i2.5.3文法二義性的消除1.不改變文法中原有的語(yǔ)法規(guī)則,僅加進(jìn)一些非形式的語(yǔ)法規(guī)定。EE+EE*Eiii2.5.3文法二義性的消除2.構(gòu)造一個(gè)等價(jià)的無(wú)二義性文法。即將排除二義性的規(guī)則合并到原有文法中,改寫(xiě)原有的文法。 例如，對(duì)于上例文法G[E]，將運(yùn)算符的優(yōu)先順序和結(jié)合規(guī)則：*優(yōu)先于＋;＋、*

左結(jié)合加到原有文法中,可構(gòu)造出無(wú)二義性文法如下：2.5.3文法二義性的消除則句子i*i+i只有唯一一棵語(yǔ)法樹(shù)：E

E+T|TT

T*F|FF(E)|iEE+TTT*FFiiFi2.5.3文法二義性的消除例2定義某程序語(yǔ)言條件語(yǔ)句的文法G為:試證明該文法是二義性的S

ifbS|ifbSelseS|A2.5.3文法二義性的消除S

ifbS|ifbSelseS|A所以該文法是二義的。SifbSbSSifAelseASbSSifAelseAifbS句子ifbifbAelseA2.5.3文法二義性的消除消除文法的二義性可采用下面兩種方法：不改變已有規(guī)則，僅加進(jìn)一非形式的語(yǔ)法規(guī)定：else與前面最接近的不帶else的if相對(duì)應(yīng)。SifbSbSSifAelseA2.5.3文法二義性的消除2.改寫(xiě)文法G為G'S

S1|S2

S1

ifbS1elseS1|AS2

ifbS

|

ifbS1elseS2

G':S

ifbS|ifbSelseS|A(其它語(yǔ)句）G:2.5.3文法二義性的消除S

S1|S2

S1

ifbS1elseS1|AS2

ifbS

|

ifbS1elseS2

ifbSbifAelseASS2S1S1S1對(duì)改寫(xiě)后的文法，句子ifbifbAelseA只對(duì)應(yīng)唯一的一棵語(yǔ)法樹(shù)。2.5.3文法二義性的消除可能有兩個(gè)不同的文法G和G’，而且其中一個(gè)是二義性的，另一個(gè)是無(wú)二義性的,但卻有L(G)=L(G’),即這兩個(gè)文法所產(chǎn)生的語(yǔ)言是相同的。2.5.3文法二義性的消除一個(gè)語(yǔ)言是二義性的，是指對(duì)它不存在無(wú)二義性的文法，這樣的語(yǔ)言稱為先天二義性的語(yǔ)言。L={aibjck|i=j或j=k且i,j,k≥1}2.6文法和語(yǔ)言的分類喬姆斯基將文法和語(yǔ)言分為四大類，即0型、1型、2型、3型。2.6文法和語(yǔ)言的分類3型文法（正規(guī)文法）右線性文法和左線性文法都稱為3型文法。

若文法G=(VN,VT,P,S)中的每一條規(guī)則的形式為A

aB或Aa,其中：A,BVN,a

VT*,則稱G是右線性文法。

若文法G=(VN,VT,P,S)中的每一條規(guī)則的形式為A

Ba或Aa,其中：A,BVN,a

VT*,則稱G是左線性文法。3型語(yǔ)言由

有窮自動(dòng)機(jī)識(shí)別。

3型文法也稱正規(guī)文法。正規(guī)文法產(chǎn)生的語(yǔ)言稱為正規(guī)語(yǔ)言。3型文法描述的語(yǔ)言是3型語(yǔ)言。2.6文法和語(yǔ)言的分類例如，用左線性正規(guī)文法和右線性正規(guī)文法定義標(biāo)識(shí)符 用I代表標(biāo)識(shí)符;l代表任意一個(gè)字母;d代表任意一個(gè)數(shù)字;則定義標(biāo)識(shí)符的文法為：左線性文法:P:I→l|Il|Id右線性文法:P:I→l|lT

T→l|d|lT|dT2.6文法和語(yǔ)言的分類例如，用左線性正規(guī)文法和右線性正規(guī)文法定義無(wú)符號(hào)整數(shù)用N代表無(wú)符號(hào)整數(shù);d代表任意一個(gè)數(shù)字；則定義的無(wú)符號(hào)整數(shù)文法為：左線性文法:P:N→Nd|d右線性文法:P:N→dN|d2.6文法和語(yǔ)言的分類2型文法（上下文無(wú)關(guān)文法）2型文法又稱上下文無(wú)關(guān)文法，其產(chǎn)生的語(yǔ)言又稱為上下文無(wú)關(guān)的語(yǔ)言。若文法G=(VN,VT,P,S)中的每一條規(guī)則的形式為A

β,其中：A

VN,β(VN∪VT)*則稱G是2型文法。其描述的語(yǔ)言為？L2(G[S])={}其中：VN={S,A,B},VT={a,b}P={S

aB|bAA

a|aS|bAAB

b|bS|aBB}2.6文法和語(yǔ)言的分類例如，有2型文法G=(VN,VT,P,S)

x|x{a,b}+且x中a和b的個(gè)數(shù)相同2.6文法和語(yǔ)言的分類1型文法（上下文有關(guān)文法）1型文法也稱為上下文有關(guān)文法，相應(yīng)的語(yǔ)言又稱為上下文有關(guān)語(yǔ)言。若文法G=(VN,VT,P,S)中的每一條規(guī)則的形式為αAβ

αμβ,其中：α,β(VN∪VT)*,A

VN,則稱G是1型文法。

μ(VN∪VT)+2.6文法和語(yǔ)言的分類例如，有1型文法G=(VN,VT,P,S)

其中：VN={S,A,B},VT={a,b,c}P:S

aSAB|abBBA

BA'BA'

AA'

AA'

ABbA

bbbB

bccB

cc其描述的1型語(yǔ)言為L(zhǎng)1(G[S])={

}anbncn|n≥12.6文法和語(yǔ)言的分類0型文法（無(wú)限制文法）若文法G=(VN,VT,P,S)中的每條規(guī)則αβ

是這樣一種結(jié)構(gòu)：而且α中至少含一個(gè)非終結(jié)符,則稱G是0型文法。α(VN∪VT)+,β

(VN∪VT)*0型文法沒(méi)有加任何限制條件，又稱為無(wú)限制性文法，相應(yīng)的語(yǔ)言稱為無(wú)限制性語(yǔ)言。2.6文法和語(yǔ)言的分類例如，有0型文法G=(VN,VT,P,S)

其中：VN={A,B,S},VT={0,1}其描述的0型語(yǔ)言為L(zhǎng)0(G[S])={

}P:S

0AB1B

0B

SA|01A1

SB1A0

S0B2.6文法和語(yǔ)言的分類L0

L1

L2

L32.7有關(guān)文法的實(shí)用限制和變換對(duì)文法的實(shí)用限制有以下兩點(diǎn)：1.文法中不能含有形如A→A的規(guī)則。這種規(guī)則我們稱之為有害規(guī)則。2.文法中不能有多余規(guī)則。所謂多余規(guī)則是指文法中出現(xiàn)以下兩種規(guī)則：2.7有關(guān)文法的實(shí)用限制和變換例如設(shè)有文法G[S]:P:S

BdA

Ad|dB

Cd|AeC

CeD

e刪除多余規(guī)則后的文法變換為:S->BdB-AeA->Ad|d本章小結(jié)本章重點(diǎn)介紹了語(yǔ)言的語(yǔ)法結(jié)構(gòu)的形式描述、語(yǔ)法樹(shù)以及文法的二義性,主要內(nèi)容有：1.設(shè)計(jì)一個(gè)文法定義一個(gè)已知的語(yǔ)言(1)文法是一個(gè)四元組G=(VN,VT,P,S)，文法四大要素中，關(guān)鍵是一組規(guī)則,它定義（或描述）了一個(gè)語(yǔ)言的結(jié)構(gòu)。從文法定義可知,文法對(duì)于程序設(shè)計(jì)者來(lái)說(shuō)，文法給出了語(yǔ)言的精確定義和描述。本章小結(jié)(2)分析已知語(yǔ)言句子的結(jié)構(gòu)特征,設(shè)計(jì)出相應(yīng)的一組規(guī)則，但不唯一。(3)設(shè)計(jì)的文法必須能定義已知的語(yǔ)言,不能超出或縮小所定義語(yǔ)言的范圍。(4)若語(yǔ)言是無(wú)窮集合,設(shè)計(jì)該語(yǔ)言的文法一定是遞歸的。分析根據(jù)語(yǔ)言句子的結(jié)構(gòu)特征，設(shè)計(jì)出相應(yīng)規(guī)則P2:S→ABL2={ab,abb,abbb,…aabb,aabbb,aabbbb,… aaabbb,aabbbb，…}A→aAb|abB→bB|ε本章小結(jié)例1.給出語(yǔ)言L2={anbm|m≥n≥1}的文法分析根據(jù)語(yǔ)言句子的結(jié)構(gòu)特征，設(shè)計(jì)出相應(yīng)規(guī)則P1':A→aB|aP1：A→aAa|a

或L1={a,aaa,aaaaa,aaaaaaa,aaaaaaaaa，…}B→aa|aBa本章小結(jié)例2.給出語(yǔ)言L1={a2n+1|n≥0}的文法本章小結(jié)例3.給出語(yǔ)言L3={anbmck|n,m,k≥0}的文法分析根據(jù)語(yǔ)言句子的結(jié)構(gòu)特征，設(shè)計(jì)出相應(yīng)規(guī)則P3:A→aA|bB|cC|εP3':A→aA|B或L3={ε,a,aa,aaa…,b,bb,bbb…,c,cc,ccc,…,ab,abb,…,bc,bcc，…}C→cC|εB→bB|cC|εC→cC|εB→bB|C本章小結(jié)例4.寫(xiě)一個(gè)文法,使其語(yǔ)言是正偶數(shù)的集合,每個(gè)偶數(shù)不以0開(kāi)頭。L4={2,4,6,8,10,12,14,16,18,20,22,24,26,…}P4:N→E′|AEN→2|4|6|8|BN'

或分析不以0開(kāi)頭的偶數(shù)集合中串的結(jié)構(gòu)特征:A→D|AD′E→0|2|4|6|8D→1|2|3|…|9D'→0|1|2|3|…|9B→1|2|3|…|9|B0P4':E'→2|4|6|8N'→BN'|0|2|4|6|8A→0A1|εP

:S→1S0|0A1|ε 分析根據(jù)語(yǔ)言句子的結(jié)構(gòu)特征,設(shè)計(jì)出相應(yīng)規(guī)則L={ε,01,0011,…,10,1100,…,1010,100110,110100,11001100…}本章小結(jié)例5.給出語(yǔ)言L={1n0m1m0n|n,m≥0}的文法。P

:S→a|0S0|1S1 分析根據(jù)語(yǔ)言句子的結(jié)構(gòu)特征，設(shè)計(jì)出相應(yīng)規(guī)則L={a,0a0,1a1,01a10,10a01,00a00,11a11,101a101,110a011,100a001,…}W={ε,0,1,01,10,00,11,101,110,100,111,…}本章小結(jié)例6.給出語(yǔ)言L={WaWt

|W∈{0|1}*}，其中Wt表示W(wǎng)的逆的文法。本章小結(jié)2.已知一個(gè)文法，確定該文法所定義的語(yǔ)言。(2)給定一個(gè)文法，可根據(jù)語(yǔ)言和推導(dǎo)定義推導(dǎo)出文法的句子，從而確定出該文法所定義的語(yǔ)言。(1)文法所定義的語(yǔ)言

L(G[S])={x|S

x且x∈VT*}*本章小結(jié)(3)語(yǔ)言可用①自然語(yǔ)言描述。例如,L={x|x∈{a,b}+且x中a,b個(gè)數(shù)相同}②式子描述。例如L={a2nbb|n≥0}。③正規(guī)式描述。本章小結(jié)例1文法G[A]=({A},{a,b},{A→bA|a},A)所生成的語(yǔ)言是什么？分析∵A

bA

bbA

bbbA

…

bnA

bna∴L(G[A])={bna|n≥0}N→ND|DD→0|1|2|3|4|5|6|7|8|9(1)G[N]所生成的語(yǔ)言是什么？(2)給出句子0127的最左、最右推導(dǎo)。本章小結(jié)例2文法G[N]為:本章小結(jié)N→ND|DD→0|1|2|3|4|5|6|7|8|9L(G[N])={α|α∈{0,1,2,…9}+}={α|α為可帶前導(dǎo)0的正整數(shù)}={α|α為數(shù)字串}最左推導(dǎo):N

ND

N7

ND7

N27

ND27

N127

D127

0127最右推導(dǎo):N

ND

NDD

NDDD

DDDD

0DDD

01DD

012D

0127本章小結(jié)例3.已知文法G[S]=({A,B},{a,b,c,d},P,S),其中P為:分析∵S

AB

aAbB

a2Ab2B

…

an-1Abn-1B

anbnB

anbncBd

anbnc2Bd2

…

anbncm-1Bdn-1

anbncmdm

∴L(G[S])={anbncmdm|n,m≥1}該文法所生成的語(yǔ)言是什么？A→aAb|abB→cBd|cdS→AB本章小結(jié)3.求句型的短語(yǔ)、直接短語(yǔ)和句柄(1)短語(yǔ)、直接短語(yǔ)和句柄是對(duì)某句型而言的。(2)短語(yǔ)總是句型的某個(gè)子串，它對(duì)應(yīng)子樹(shù)未端結(jié)點(diǎn)形成的符號(hào)串。(3)直接短語(yǔ)是某條規(guī)則右部，它對(duì)應(yīng)簡(jiǎn)單子樹(shù)未端結(jié)點(diǎn)形成的符號(hào)串。(4)最左邊的直接短語(yǔ)是句柄。證明E+T*F是它的一個(gè)句型,指出這個(gè)句型的短語(yǔ)﹑直接短語(yǔ)和句柄?！逧

E+T

E+T*F短語(yǔ):E+T*F、T*F∴E+T*F是它的一個(gè)句型。畫(huà)出該句型的語(yǔ)法樹(shù):句柄:T*F直接短語(yǔ):T*FETFT+E*E→E+T|E-T|TT→T*F|T/F|FF→(E)|i本章小結(jié)例1

已知文法G[E]：本章小結(jié)例2

已知文法G[S]：試找出符號(hào)串(a)和(A((SaA)(b)))的短語(yǔ)﹑直接短語(yǔ)和句柄(如果有的話)。S→(AS)|(b)A→(SaA)|(a)∴符號(hào)串(a))不是文法的句型，因此它沒(méi)有短語(yǔ)﹑直接短語(yǔ)和句柄。分析∵S

(AS)

((a)S)

(a)/本章小結(jié)S→(AS)|(b)A→(SaA)|(a)∵S

(AS)

(A(AS))

(A(A(b)))

(A((SaA)(b)))∴符號(hào)串(A((SaA)(b)))是文法的句型，畫(huà)出該句型的語(yǔ)法樹(shù)如下圖：本章小結(jié)從句型的語(yǔ)法樹(shù)求短語(yǔ):

(A((SaA)(b)))((SaA)(b))(SaA)(b)直接短語(yǔ)：(SaA)、(b)句柄：(SaA)SA(S)A(S)(SaA))b(S→(AS)|(b)A→(SaA)|(a)對(duì)于句型(A((SaA)(b)))本章小結(jié)4．文法二義性的判斷一個(gè)文法存在某個(gè)句子對(duì)應(yīng)兩棵不同的語(yǔ)法樹(shù)或?qū)?yīng)兩個(gè)不同的最左（最右）推導(dǎo)，則該文法是二義性的。

試證明文法G[S]有二義性。分析因?yàn)閷?duì)文法的句子iiiei有如下兩棵不同的語(yǔ)法樹(shù)與之對(duì)應(yīng)，所以該文法是二義的本章小結(jié)例1設(shè)有文法G[S]:S→iSeS|iS|i本章小結(jié)S→iSeS|iS|i句子iiiei對(duì)應(yīng)下面兩顆語(yǔ)法樹(shù)：SSieSiSiiSiSiSieSi本章小結(jié)例2設(shè)有文法G[N]:N→SE|ES→SD|DE→0|2|4|6|8|10D→0|1|2|3|4|5|6|7|8|91.

試證明文法G[N]有二義性。2.

此文法所描述的語(yǔ)言是什么？

3.試寫(xiě)出另一文法G'使L(G')=L(G)且G'是無(wú)二義性的。本章小結(jié)分析因?yàn)閷?duì)文法的句子10有兩棵不同的語(yǔ)法樹(shù)與之對(duì)應(yīng)，所以該文法是二義的NES0D1NE01N→SE|ES→SD|DE→0|2|4|6|8|10D→0|1|2|3|4|5|6|7|8|9本章小結(jié)N→SE|ES→SD|DE→0|2|4|6|8|10D→0|1|2|3|4|5|6|7|8|9該文法所描述的語(yǔ)言是所有無(wú)符號(hào)偶數(shù)的集合(可以0開(kāi)頭)。改寫(xiě)后的文法G‘[S]為:

N→SE|ES→SD|DE→0|2|4|6|8D→0|1|2|3|4|5|6|7|8|9第3章詞法分析與有窮自動(dòng)機(jī)

詞法分析程序功能

單詞符號(hào)及輸出單詞的形式

語(yǔ)言單詞符號(hào)的兩種定義方式

正規(guī)式與有窮自動(dòng)機(jī)

正規(guī)文法與有窮自動(dòng)機(jī)

詞法分析程序的編寫(xiě)方法175intfib(intn){if(n<=1)returnn;returnfib(n-1)+fib(n-2);}chara[100]="Enteraninteger:";intmain(){print_string(a);intmax=read_int();intn=1;do{print_int(fib(n++));print_string("\n");}while(n<=max);return0;}關(guān)鍵字

if，while,do標(biāo)識(shí)符

各種名字，如變量名、常量名、數(shù)組名、函數(shù)名等。常數(shù)整型常數(shù)125、實(shí)型常數(shù)0.718、布爾型常數(shù)TRUE等。運(yùn)算符＋、－、*、/、＜等。分界符，、；、（、）、：等。1763.1詞法分析程序的功能語(yǔ)言的單詞符號(hào)是指語(yǔ)言中具有獨(dú)立意義的最小語(yǔ)法單位。1773.1詞法分析程序的功能3.1詞法分析程序的功能1783.1詞法分析程序的功能179

字符串表示的源程序詞法分析器字符單詞符號(hào)取下一個(gè)單詞符號(hào)語(yǔ)法分析器輸入:if(a＞1)b=100；3.2單詞符號(hào)及輸出單詞的形式詞法分析程序輸出單詞的形式詞法分析程序所輸出的單詞符號(hào)通常表示成如下的二元式：180

（單詞種別，單詞自身的值）3.2單詞符號(hào)及輸出單詞的形式例子:if(a＞1)b=100；181標(biāo)識(shí)符的種別編碼整數(shù)10；常數(shù)的種別編碼整數(shù)11；基本字if種別編碼2；賦值號(hào)的種別編碼17；大于號(hào)的種別編碼23；分號(hào)的種別編碼26；左括號(hào)的種別編碼29；右括號(hào)的種別編碼30；3.2單詞符號(hào)及輸出單詞的形式if(a＞1)b=100；182（2,）基本字if（29,）左括號(hào)(（10,‘a(chǎn)’）標(biāo)識(shí)符a（23,）大于號(hào)＞（11,1）常數(shù)1（30，）右括號(hào))（10，‘b’）標(biāo)識(shí)符b（17，）賦值號(hào)=（11，100）常數(shù)100（26,）分號(hào)；問(wèn)題：下面的內(nèi)容表達(dá)什么？\A(?:[a-z0-9!#$%&'*+/=?^_‘{|}~-]+(?:\.[a-z0-9!#$%&'*+/=?^_‘{|}~-]+)*|"(?:[\x01-\x08\x0b\x0c\x0e-\x1f\x21\x23-\x5b\x5d-\x7f]|\\[\x01-\x09\x0b\x0c\x0e-\x7f])*")@(?:(?:[a-z0-9](?:[a-z0-9-]*[a-z0-9])?\.)+[a-z0-9](?:[a-z0-9-]*[a-z0-9])?|\[(?:(?:25[0-5]|2[0-4][0-9]|[01]?[0-9][0-9]?)\.){3}(?:25[0-5]|2[0-4][0-9]|[01]?[0-9][0-9]?|[a-z0-9-]*[a-z0-9]:(?:[\x01-\x08\x0b\x0c\x0e-\x1f\x21-\x5a\x53-\x7f]|\\[\x01-\x09\x0b\x0c\x0e-\x7f])+)\])\z1833.3單詞符號(hào)的兩種定義方式正規(guī)式例子：l(l|d)*對(duì)應(yīng)的正規(guī)文法：I→l|Il|Id或：I→l|lTT→l|d|lT|dT/quickstart.html184

3.3.1正規(guī)式和正規(guī)集設(shè)有字母表Σ={a1,a2,…,an}，在字母表Σ上的正規(guī)式和它所表示的正規(guī)集可用如下規(guī)則來(lái)定義：1.Φ是Σ上的正規(guī)式，它所表示的正規(guī)集是Φ，即空集{}。2.ε是Σ上的正規(guī)式，它所表示的正規(guī)集僅含一空符號(hào)串，即{ε}。3.ai是∑上的一個(gè)正規(guī)式，它所表示的正規(guī)集是由單個(gè)符號(hào)ai所組成，即{ai}。1853.3.1正規(guī)式和正規(guī)集4.如果e1和e2

是∑上的正規(guī)式，它們所表示的正規(guī)集分別為L(zhǎng)(e1)和L(e2)，則：(1)e1|e2是∑上的一個(gè)正規(guī)式，它所表示的正規(guī)集為L(zhǎng)(e1|e2)=L(e1)∪L(e2)(2)e1e2也是∑上的一個(gè)正規(guī)式，它所表示的正規(guī)集為L(zhǎng)(e1e2)=L(e1)L(e2)(3)(e1)*也是∑上的一個(gè)正規(guī)式，它所表示的正規(guī)集為L(zhǎng)((e1)*)=(L(e1))*1863.3.1正規(guī)式和正規(guī)集例1設(shè)有字母表Σ={a,b}，根據(jù)正規(guī)式與正規(guī)集的定義有：1.a和b是正規(guī)式，正規(guī)集為L(zhǎng)(a)={a},L(b)=2.a|b是正規(guī)式，正規(guī)集為L(zhǎng)(a|b)=L(a)∪L(b)={a,b}3.ab是正規(guī)式，正規(guī)集為L(zhǎng)(ab)=L(a)L(b)={a}={ab}1873.3.1正規(guī)式和正規(guī)集4.(a|b)*是正規(guī)式，相應(yīng)正規(guī)集為L(zhǎng)((a|b)*)=(L(a|b))*

={a,b}*={ε,a,b,aa,ab,ba,bb,…}問(wèn)題：{a,b}*的子集{anbn|n≥1}是正規(guī)集嗎？1883.3.1正規(guī)式和正規(guī)集5.ba*是正規(guī)式，正規(guī)集為L(zhǎng)(ba*)=L(b)L(a*)={b,ba,baa,baaa,…}6.(a|b)*(aa|bb)(a|b)*是正規(guī)式，正規(guī)集為L(zhǎng)((a|b)*(aa|bb)(a|b)*)=L((a|b)*)L(aa|bb)L((a|b)*)＝{a,b}*{aa,bb}{a,b}*1893.3.1正規(guī)式和正規(guī)集例2設(shè)Σ={a,b,c},則aa*bb*cc*是∑上的一個(gè)正規(guī)式,它所表示的正規(guī)集：L={abc,aabc,abbc,abcc,aaabc,