編譯原理第5版-課件 第2章 文法和語言的基本知識

第2章文法和語言的基本知識1研究語言的翻譯，首先要解決的問題語言自身如何描述？第2章文法和語言的基本知識2形式語言理論是編譯的重要理論基礎(chǔ)。本章主要介紹編譯理論中用到的有關(guān)形式語言理論的最基本概念，重點(diǎn)介紹如何采用形式化的方法描述程序設(shè)計(jì)語言。第2章文法和語言的基本知識喬姆斯基（NoamChomsky,1928--）美國語言學(xué)家，轉(zhuǎn)換-生成語法的創(chuàng)始人。1955年完成博士論文《轉(zhuǎn)換分析》，獲得博士學(xué)位。曾任該校語言學(xué)與哲學(xué)系主任，并任該校認(rèn)知科學(xué)研究中心主任，為語言學(xué)界培養(yǎng)了一批有素養(yǎng)的學(xué)者。3第2章文法和語言的基本知識4字母表和符號串文法和語言的形式定義短語、直接短語和句柄語法樹和文法的二義性文法和語言的分類2.1概述例如語句s＝2*3.1416*r*(r+h)5語法：賦值語句由一個(gè)變量，后隨一個(gè)賦值號“＝”，其后面再跟一個(gè)表達(dá)式構(gòu)成。語義：首先計(jì)算語句右部表達(dá)式的值，然后把所得結(jié)果送給左部變量中。語用：賦值語句可用來計(jì)算和保存表達(dá)式的值。形式化的方法,是用一整套帶有嚴(yán)格規(guī)定的符號體系來描述問題的方法形式語言(FormalLanguage)理論是編譯的重要理論基礎(chǔ)如何采用形式化的方法描述程序設(shè)計(jì)語言2.1概述61.字母表(Alphabet)元素的非空有窮集合。例如，∑={a,b,c}根據(jù)字母表的定義，Σ是字母表，它有a、b、c三個(gè)元素例如，∑'={0,1}組成?！啤亲帜副恚?、1兩個(gè)元素2.2字母表和符號串72.符號（字符）Symbol字母表中的元素稱為符號或稱為字符。

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

abc…

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

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

}A＝A{

}＝

A則AB={ac,ad,bc,bd}由于對任意的符號串x，總有

x=x

=x所以,對任意集合A,我們有:2.2字母表和符號串13

是符號串{

}表示由空符號串

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

x1=xx2=xxx3=xxx

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

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

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

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

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

規(guī)則

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

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

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

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

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

1|

2|…

|

nA→

1A→

2A→

n

…

對左部相同的規(guī)則候選式2.3.2文法的形式定義322.3.2文法的形式定義前例中描述∑+的文法是:33G=(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è)文法描述語言L={a2n,b2n|n≥1}34當(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這樣的符號串組成的集合2.3.2文法的形式定義352.3.2文法的形式定義36因此，定義語言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文法的形式定義37問題:描述該語言的文法是否唯一？P':A→B|DB→aa|aBaD→bb|bDbG"是否是描述該語言的文法？2.3.2文法的形式定義38G"=({A},{a,b},P",A)其中P"={A→aa|bb|Aaa|Abb}2.3.2文法的形式定義例2試設(shè)計(jì)一個(gè)表示所有標(biāo)識符的文法39

2.3.2文法的形式定義40G=(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文法的形式定義41將定義標(biāo)識符的文法設(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文法的形式定義42字母字母或數(shù)字串2.3.2文法的形式定義P:I→L|LTT→L|D|LT|DTL→a|b|c|…|x|y|zD→0|1|2|3|…|943字母字母或數(shù)字串2.3.2文法的形式定義例3已知自然語言描述的算數(shù)表達(dá)式如下，請用文法定義之。算術(shù)表達(dá)式定義用自然語言描述如下：變量i是一個(gè)表達(dá)式；若

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

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文法的形式定義452.3.2文法的形式定義例4設(shè)字母表Σ={a,b},

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

例5設(shè)字母表∑={(,)},

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

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

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

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語言的形式定義502.推導(dǎo)

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

α1

α2

…

αn從0出發(fā)，經(jīng)一步或若干步（使用若干次規(guī)則）可推導(dǎo)出n2.3.3語言的形式定義51對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語言的形式定義例設(shè)有文法G[E]=({E,T,F},{i,+,*,(,)},P,E)522.3.3語言的形式定義3．廣義推導(dǎo)53我們有：

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)|i4.句型和句子設(shè)有文法G[S]（S是文法G的開始符號）

如果S

x,x

∈(VN∪VT)*

則稱符號串x

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

如果S

x,x

∈VT*

則稱符號串x為文法G[S]的句子。*2.3.3語言的形式定義54我們有:

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

01*S

0S1*S

00S11*S

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

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

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

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

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

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)過程中任何一步α

β(α和β是句型),都是對α的最左非終結(jié)符進(jìn)行替換。67句子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)相對的概念68則有規(guī)范歸約：規(guī)范推導(dǎo)的逆過程，稱為最左歸約，也稱為規(guī)范歸約。N1NNDN2D21212D2.N2.ND.N.N1.2.3.4規(guī)范推導(dǎo)和規(guī)范歸約例如，例文法G[N1]中有規(guī)范推導(dǎo)：692.3.5遞歸規(guī)則與文法的遞歸性遞歸規(guī)則70如果文法中有規(guī)則A→A…稱為規(guī)則左遞歸。如果文法中有規(guī)則A→…A稱為規(guī)則右遞歸。如果文法中有規(guī)則A→…A…稱為規(guī)則遞歸。2.3.5遞歸規(guī)則與文法的遞歸性文法的遞歸性71若文法中有推導(dǎo)AA…稱文法左遞歸。+若文法中有推導(dǎo)A

…

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

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

U→VxV→Uy|zU

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

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

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

αAδ*+且A

β

2.4短語、直接短語和句柄直接短語則稱β是直接短語。S

αAδ*且A

β

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

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

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

ABA

Aa|bBB

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

E+T|E–T|TT

T*F|T/F|FF

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

ABA

Aa|bBB

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

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

Sb

為句型的相對于B的短語、直接短語baSb

為句型的相對于S的短語ba

為句型的相對于A的短語a

句型的相對于B的短語、直接短語和句柄SABbBBbaBbaSbSABASbbBSbbaSbSABbBSba由語法樹可知文法的某個(gè)句型是否只對應(yīng)唯一的一棵語法樹呢？或者，它是否只有唯一的一個(gè)最左推導(dǎo)呢？它是否只有唯一的一個(gè)最右推導(dǎo)呢？2.5.2文法的二義性對于文法G中任一句型的推導(dǎo)序列,我們總能為它構(gòu)造一棵語法樹。問題：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è)句子，對應(yīng)兩棵不同的語法樹，則這個(gè)文法是二義性的。如果一個(gè)文法存在某個(gè)句子，有兩個(gè)不同的最左(最右)推導(dǎo)，則這個(gè)文法是二義性的。E

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

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

E+T|TT

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

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

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

S1|S2

S1

ifbS1elseS1|AS2

ifbS

|

ifbS1elseS2

G':S

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

S1|S2

S1

ifbS1elseS1|AS2

ifbS

|

ifbS1elseS2

ifbSbifAelseASS2S1S1S1對改寫后的文法，句子ifbifbAelseA只對應(yīng)唯一的一棵語法樹。2.5.3文法二義性的消除可能有兩個(gè)不同的文法G和G’，而且其中一個(gè)是二義性的，另一個(gè)是無二義性的,但卻有L(G)=L(G’),即這兩個(gè)文法所產(chǎn)生的語言是相同的。2.5.3文法二義性的消除一個(gè)語言是二義性的，是指對它不存在無二義性的文法，這樣的語言稱為先天二義性的語言。L={aibjck|i=j或j=k且i,j,k≥1}2.6文法和語言的分類喬姆斯基將文法和語言分為四大類，即0型、1型、2型、3型。2.6文法和語言的分類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型語言由

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

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

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

β,其中：A

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

aB|bAA

a|aS|bAAB

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

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

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

VN,則稱G是1型文法。

μ(VN∪VT)+2.6文法和語言的分類例如，有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型語言為L1(G[S])={

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

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

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

其中：VN={A,B,S},VT={0,1}其描述的0型語言為L0(G[S])={

}P:S

0AB1B

0B

SA|01A1

SB1A0

S0B2.6文法和語言的分類L0

L1

L2

L32.7有關(guān)文法的實(shí)用限制和變換對文法的實(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本章重點(diǎn)介紹了語言的語法結(jié)構(gòu)的形式描述、語法樹以及文法的二義性,主要內(nèi)容有：1.設(shè)計(jì)一個(gè)文法定義一個(gè)已知的語言(1)文法是一個(gè)四元組G=(VN,VT,P,S)，文法四大要素中，關(guān)鍵是一組規(guī)則,它定義（或描述）了一個(gè)語言的結(jié)構(gòu)。從文法定義可知,文法對于程序設(shè)計(jì)者來說，文法給出了語言的精確定義和描述。本章小結(jié)(2)分析已知語言句子的結(jié)構(gòu)特征,設(shè)計(jì)出相應(yīng)的一組規(guī)則，但不唯一。(3)設(shè)計(jì)的文法必須能定義已知的語言,不能超出或縮小所定義語言的范圍。(4)若語言是無窮集合,設(shè)計(jì)該語言的文法一定是遞歸的。本章小結(jié)分析根據(jù)語言句子的結(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.給出語言L2={anbm|m≥n≥1}的文法分析根據(jù)語言句子的結(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.給出語言L1={a2n+1|n≥0}的文法本章小結(jié)例3.給出語言L3={anbmck|n,m,k≥0}的文法分析根據(jù)語言句子的結(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.寫一個(gè)文法,使其語言是正偶數(shù)的集合,每個(gè)偶數(shù)不以0開頭。L4={2,4,6,8,10,12,14,16,18,20,22,24,26,…}P4:N→E′|AEN→2|4|6|8|BN'

或分析不以0開頭的偶數(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ù)語言句子的結(jié)構(gòu)特征,設(shè)計(jì)出相應(yīng)規(guī)則L={ε,01,0011,…,10,1100,…,1010,100110,110100,11001100…}本章小結(jié)例5.給出語言L={1n0m1m0n|n,m≥0}的文法。P

:S→a|0S0|1S1 分析根據(jù)語言句子的結(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.給出語言L={WaWt

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

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

x且x∈VT*}*本章小結(jié)(3)語言可用①自然語言描述。例如,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)所生成的語言是什么？分析∵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]所生成的語言是什么？(2)給出句子0127的最左、最右推導(dǎo)。本章小結(jié)例2文法G[N]為: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é)本章小結(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

anbncm