形式語言03章無關(guān)文法與無關(guān)語言_第1頁
形式語言03章無關(guān)文法與無關(guān)語言_第2頁
形式語言03章無關(guān)文法與無關(guān)語言_第3頁
形式語言03章無關(guān)文法與無關(guān)語言_第4頁
形式語言03章無關(guān)文法與無關(guān)語言_第5頁
已閱讀5頁,還剩131頁未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

第三章

上下文無關(guān)文法后上下文無關(guān)語言

?上下文無關(guān)文法的重要性:

?擁有足夠強(qiáng)的表達(dá)力來表示大多數(shù)程序設(shè)計(jì)語

言的語法

?可以構(gòu)造有效的分析算法來檢驗(yàn)一個(gè)給定的字

符串是否是由某個(gè)上下文無關(guān)文法產(chǎn)生。

?上下文無關(guān)語言在實(shí)踐中有重要意義:

?1)定義程序設(shè)計(jì)語言:

?BNF(巴克斯?諾爾范式);

?2)描述文檔格式:

?XML,HTML;

?3)使語法分析概念形式化;

?4)簡(jiǎn)化程序設(shè)計(jì)語言的翻譯:

?語法分析器的設(shè)計(jì);

?給定文法G,如果對(duì)于G中的任意產(chǎn)生式v->3,

而v只是一個(gè)非終結(jié)符,即A-3,AeV,

we(^UV)*,則稱文法G為上下文無關(guān)文法(簡(jiǎn)

稱無關(guān)文法)。如果一個(gè)語言能由一個(gè)無關(guān)文法

產(chǎn)生,則稱這個(gè)語言是上下文無關(guān)語言(簡(jiǎn)稱無

關(guān)語言)。

定義3-1線性的無關(guān)文法

?若無關(guān)文法G=(2,V,S,P)的

所有產(chǎn)生式都是下列形式之一:

?A—uBv或A—w;

?其中:A,BeV;u,v^^+;w^E*。

?該文法稱為線性的無關(guān)文法。

?注意:u,V可以有一個(gè)為空串£。

?特別地,

如果U=£,稱為左線性的(無關(guān))文法;

如果V=£,稱為右線性的(無關(guān))文法。

?從定義可以看出,線性的無關(guān)文法是受

限制的無關(guān)文法;本身一定還是無關(guān)文

法。

化簡(jiǎn)的上下文無關(guān)文法

?左線性文法和右線性文法是線性文法中

特殊的兩類。

?定理3?2G=(3V,S,P)是一個(gè)上下文

無關(guān)文法,產(chǎn)生式的一般形式為A-w,其中:

WG(JUV)*,

?則存在另一個(gè)等價(jià)的線性的無關(guān)文法G1,而

G1中產(chǎn)生式的形式為;

?A-a或A^apbo

?其中:A£V;a,bGjU{£};pGV+o

?證明:

?讀者自己完成。

?定理3?3G=(3V,S,P)是一個(gè)上下文

無關(guān)文法,產(chǎn)生式的一般形式為A-w,其

中:we(ZUV)*,則存在另一個(gè)等價(jià)的無

關(guān)文法G1,而G1中產(chǎn)生式的形式為;

?A-a或A—>aB或A—>aBCo

?其中:A,B,CGV;。

?證明:讀者自己完成。

3.1消除無關(guān)文法中的無用非終結(jié)符號(hào)

?定義3-4文法中的無用符號(hào)

?一個(gè)無關(guān)文法G,符號(hào)YWV,如果不出

現(xiàn)在任何形如S=>*uYv=>*uwv的推導(dǎo)

之中,稱Y為文法G的無用非終結(jié)符。

?其中:U,W,V

?反之,一個(gè)無關(guān)文法G,符號(hào)Y£V,如

果能夠出現(xiàn)在某個(gè)形如

S=>*uYv=>*uwv的推導(dǎo)之中,稱丫為

文法G的有用非終結(jié)符。其中:u,

W,V。

?從定義可知:有用非終結(jié)符,必須同時(shí)滿

足兩個(gè)條件

?(1)從它開始推導(dǎo),能夠產(chǎn)生終結(jié)符號(hào)串;

?(2)它必須出現(xiàn)在某個(gè)句型中;

?判斷某個(gè)符號(hào)是有用非終結(jié)符,就應(yīng)該從

這兩方面同時(shí)進(jìn)行考慮。

?有用非終結(jié)符的判斷算法:

?略。

定義3-7無用的產(chǎn)生式

?如果一個(gè)產(chǎn)生式中(產(chǎn)生式的左邊或右邊)包含

有無用的非終結(jié)符,則該產(chǎn)生式就是無用的產(chǎn)生

式??梢詫o用的產(chǎn)生式從文法中刪除掉。

?問題3-8文法產(chǎn)生的語言是否為空?

?一個(gè)無關(guān)文法G,產(chǎn)生的語言為L(zhǎng)(G),而L(G)是

否為空(即空集①),是可以判定的。

?注意:

?一個(gè)語言包含有空串8或語言本身就是沱},它

們都不是空集①o

?判定方法:

?①首先使用空串定理,消除該無關(guān)文法中的所有

空串產(chǎn)生式,如果還有S-8,則該文法產(chǎn)生的

語言不為空;

?(2)構(gòu)造能產(chǎn)生終結(jié)符串的非終結(jié)符集合N,如果

SeN,則該文法產(chǎn)生的語言不為空。否則,該

文法產(chǎn)生的語言為空。

?定理3-11已知產(chǎn)生一個(gè)非空語言的上下文無關(guān)

文法G,則對(duì)于某個(gè)AeV,總有A二〉*w,且

weE*o

?證明:

?讀者自行完成。

?定理3-12一個(gè)無關(guān)文法G二(£,V,S,P),產(chǎn)生的語言為

L(G)O如果L(G)不為空,則至少存在一個(gè)非終結(jié)符A,而

它的產(chǎn)生式右邊僅僅只包含終結(jié)符號(hào)或空串£o

?證明提示:

?考慮產(chǎn)生串的推導(dǎo)過程中最后使用的產(chǎn)生式的特點(diǎn)。

?證明:

?讀者自行完成。

?定理3-13已知產(chǎn)生一個(gè)非空語言的上下文無關(guān)

文法G二(£,V,S,P),則能夠構(gòu)造一個(gè)等價(jià)

的無關(guān)文法G1,對(duì)于任意AeV,總有一個(gè)推

導(dǎo):S=〉*W]Aw3=〉*WF2W3,且嗎,w2,w3£E*0

?證明:

?讀者自行完成。

?定理3-14已知產(chǎn)生一個(gè)非空語言的上下文無關(guān)

文法G=(£,V,S,P),則文法中的每個(gè)非終結(jié)符都

是有用的;即:若A£V,則S=〉*uAv=〉*uwv

?其中:u,w,v£E*o

?證明:

?讀者自行完成。

?問題3-15上下文無關(guān)語言CFL是否有窮是否可

以判定?

?上下文無關(guān)文法CFG生成無窮個(gè)句子的原理是利

用遞歸的產(chǎn)生式,即

?S二〉*uAy=〉*uvAxy=〉*...二〉*uviAxiy=〉*uviwxiy

?根據(jù)著一原理可以判定上下文無關(guān)語言是否有窮。

?定義3-16可派生性圖的定義

?上下文無關(guān)文法G二(£,V,S,P),文法G的可

派生性圖是滿足下列條件的有向圖:

?(1)對(duì)于終結(jié)符或非終結(jié)符X,圖中有且僅有一個(gè)

標(biāo)記為X的頂點(diǎn)。

?(2)如果A—〉XlX2...Xn,則圖中存在從標(biāo)記為A的

頂點(diǎn)分別到標(biāo)記為XI,X2,Xn的頂點(diǎn)的弧。

?(3)圖中只有滿足條件(1)和(2)的弧。

?可派生性圖表示了G中變量間的派生關(guān)系:從A到

B有一條有向路表示B出現(xiàn)在A派生出的某個(gè)符號(hào)

串中。

?3.2推廣的化簡(jiǎn)上下文無關(guān)文法

?上下文無關(guān)文法化簡(jiǎn)的目的:

限制產(chǎn)生式的格式而不降低文法生成句子的能力,

從而降低文法分析算法的復(fù)雜度。

?上下文無關(guān)文法化簡(jiǎn)的基本手段:

刪除無用符號(hào)

刪除單一產(chǎn)生式組

?對(duì)于一個(gè)上下文無關(guān)文法G,如果:

?①?zèng)]有A-A形式的產(chǎn)生式;

?②每個(gè)非終結(jié)符A都是有用的,即:

?有S=〉*QAp=〉*QWp;

?其中:Q,w,B££*;

?則該文法是化簡(jiǎn)的上下文無關(guān)文法。

?對(duì)于任意的無關(guān)文法,進(jìn)行

?(1)直接刪除沒有A-A形式的產(chǎn)生式

?對(duì)于A-A形式的產(chǎn)生式,該類產(chǎn)生式是遞歸的,可以反

復(fù)利用任意多次,但對(duì)于無窮語言的產(chǎn)生,沒有任何作

用??梢灾苯觿h除即可。

?(2)消除無關(guān)文法中的無用非終結(jié)符號(hào)

?消除無關(guān)文法中的無用非終結(jié)符號(hào)后,無關(guān)文法中的所

有非終結(jié)符號(hào)都是有用的。

?得到的文法是化簡(jiǎn)的上下文無關(guān)文法。

?定義3-21推廣的簡(jiǎn)化上下文無關(guān)文法:

?對(duì)于一個(gè)上下文無關(guān)文法G,如果該文法中不存

在形如A-B的產(chǎn)生式(A,B£V),

?則該文法是推廣的化簡(jiǎn)上下文無關(guān)文法。

?定理3-22對(duì)于一個(gè)上下文無關(guān)文法G,能夠找

到一個(gè)等價(jià)的無關(guān)文法G1,而G1中不存在形如A

一B的單產(chǎn)生式(A,B£V)。

?證明思路:

?對(duì)于某個(gè)推導(dǎo)過程:

S=>*oA|3=>aBp=>awz|3=>...

?可簡(jiǎn)化為:S=>*aAp=>awF=>...

?即省略掉A=>B的推導(dǎo)。

?因此,需要將A-B的產(chǎn)生式使用下面產(chǎn)生式進(jìn)行

替換:

?AfW]|W2|W3|??.|WR

?而B-wtIw21w31...Iw是文法G中關(guān)于B的所有

產(chǎn)生式。

?實(shí)際上,就是將推導(dǎo)過程在產(chǎn)

生式中就體現(xiàn)出來。

?注意,對(duì)于關(guān)于B的產(chǎn)生式,

BIw21w31...|wn

需要保留,不能刪除。因?yàn)榭赡艽嬖?/p>

?S=>axBpi=〉。]W[|31=>...

?的推導(dǎo),即該推導(dǎo)過程沒有使用產(chǎn)生式A-Bo

思考:_________________________

?能否將文法中的產(chǎn)生式右邊的A直接替換為B,

然后將

?ATB1IB2IB3I??邛mIB

?替換為

?B->31|32|p3|...|3m

?這是不行的;因?yàn)榭赡墚a(chǎn)生多余的串。

?A->a,而B-B,如果B->Q,它將B的功能

擴(kuò)大了(能夠定義為。和B)。

?例如:

?S->ABS->BB

?A—>B|aB—a

?B-bB->b

?L為:{ab,bb}L為:{aa,ab,bb,ba}

3.3推導(dǎo)樹

?對(duì)于無關(guān)文法G,如果串3能由該文

法產(chǎn)生,則3的產(chǎn)生過程可以用推導(dǎo)

的辦法表示,即用符號(hào)“二〉”表示,

也可以用推導(dǎo)樹的辦法表示。

定義3-23推導(dǎo)樹(語法分析樹)

?推導(dǎo)樹是一棵有向無循環(huán)的圖。

?樹的節(jié)點(diǎn)是文法中的非終結(jié)符或者終結(jié)符,如果

有空串產(chǎn)生式,貝帕也可以是樹的節(jié)點(diǎn),樹的根

節(jié)點(diǎn)是文法的開始符號(hào)s;如果推導(dǎo)使用了產(chǎn)生

式A-/a2a3…其中A是非終結(jié)符,%是非終

結(jié)符或者是終結(jié)符;則a1,a2,a3,4都是A

的直接后繼節(jié)點(diǎn)(A稱為父節(jié)點(diǎn),a2,a3,

a。稱為子節(jié)點(diǎn));

?一個(gè)節(jié)點(diǎn)和它的直接后繼節(jié)點(diǎn)之間用有向邊連接

起來;

?如果節(jié)點(diǎn)是終結(jié)符,該節(jié)點(diǎn)稱為葉子節(jié)點(diǎn);

?如果節(jié)點(diǎn)是非終結(jié)符,該節(jié)點(diǎn)稱為非葉子節(jié)點(diǎn)

(或稱為分枝節(jié)點(diǎn));

?端末節(jié)點(diǎn)(僅有入口,沒有出口的節(jié)點(diǎn))從左到右

的連接,是該推導(dǎo)樹產(chǎn)生的邊緣。

?注意:推導(dǎo)樹是向下生長(zhǎng)的。

?定理3?24設(shè)文法G為無關(guān)文法,那么

S=>*o(,當(dāng)且僅當(dāng)存在一棵以Q為邊

緣的推導(dǎo)樹。即文法和推導(dǎo)樹都可以

產(chǎn)生甫Q。

?證明:

?略。

?結(jié)論:端末節(jié)點(diǎn)從左到右的連接,就

是該推導(dǎo)樹產(chǎn)生的句型。

?豐,:

?推營(yíng)樹不僅可以表示句子的產(chǎn)生,也

可以表示向型的產(chǎn)生。

?思考:

?端末節(jié)點(diǎn)一定為終結(jié)符嗎?

?定義3?24直接子孫和子孫的定義:

?在一個(gè)有向無循環(huán)的圖(樹)中,稱滿足下

列條件的節(jié)點(diǎn)n為節(jié)點(diǎn)m的直接子孫:有一

條看向邊從節(jié)點(diǎn)m由發(fā)送X節(jié)點(diǎn)n。

?如果有節(jié)點(diǎn)的序列:nn...n,使

得m二n1,n=iv,以及對(duì)v于每一3個(gè)i,k是

山的一不直接字孫,則節(jié)點(diǎn)n稱為節(jié)點(diǎn)m的子

孫。

?約定:

?每一個(gè)節(jié)點(diǎn)都是自己的子孫。

?一棵推導(dǎo)樹T中的每個(gè)節(jié)點(diǎn)

都是根節(jié)點(diǎn)S的一個(gè)子孫。

?定義3?25推導(dǎo)樹的另一個(gè)

定義

?無關(guān)文法G=(£V,S,P),若

一棵樹滿足下列條件,則稱

之為文法的推導(dǎo)樹:

?每個(gè)節(jié)點(diǎn)都有一個(gè)標(biāo)記(是

guv的一個(gè)符號(hào)或者是£);

?根的標(biāo)記為s;

?若一個(gè)節(jié)點(diǎn)有多于1個(gè)的子孫,

該節(jié)點(diǎn)標(biāo)記的符號(hào)為非終結(jié)符

號(hào);

?如果節(jié)點(diǎn)A的所有直接子孫,

從左到右的次序是標(biāo)記為A[,

A2,A3,…,Ak的節(jié)點(diǎn),貝力

?A一A〔A2A3…Ak為文法G的一

個(gè)產(chǎn)生式。

?實(shí)際上,存在產(chǎn)生句子的(完

整的)推導(dǎo)樹,也存在產(chǎn)生句

型的(不完整的)推導(dǎo)樹。

?一棵推導(dǎo)樹中,僅有一個(gè)子孫

的節(jié)點(diǎn)稱為端末節(jié)點(diǎn)(該子孫

就是自己)。

?定義3?26最左推導(dǎo)和最左推導(dǎo)的定

?無關(guān)文法G,有產(chǎn)生式A-B,對(duì)于一

步直接推導(dǎo)。/出二>。平。2:

?若5£工*,則稱之為一步最左推導(dǎo);

?若出£2*,則稱之為一步最右推導(dǎo);

?對(duì)于文法G和句型w:

?如果產(chǎn)生w的每一步推導(dǎo)都是最左推

導(dǎo),則稱產(chǎn)生w的推導(dǎo)為最左推導(dǎo);

?如果產(chǎn)生w的每一步推導(dǎo)都是最右推

導(dǎo),則稱產(chǎn)生w的推導(dǎo)為最右推導(dǎo)。

?最右推導(dǎo)還稱為規(guī)范推導(dǎo)。

?一般,常使用

最左推導(dǎo)。

?例3?27文法S—0B|1A

?A->0|0S|1AA

?對(duì)于串0011的產(chǎn)生過程:

?最左推導(dǎo):

S=>0B=>00BB=>001B=>0011

?最右推導(dǎo):

S=>0B=>00BB=>00B1=>0011

?推導(dǎo)也可以用推導(dǎo)樹表示為:

?實(shí)際上,一棵推導(dǎo)樹代表了一個(gè)句型(或者句子)

的最左推導(dǎo)和最右推導(dǎo)過程以及其他所有的以任

意順序進(jìn)行推導(dǎo)的過程。

?在推導(dǎo)樹中,從根節(jié)點(diǎn)到一個(gè)葉節(jié)點(diǎn)(或者端末

節(jié)點(diǎn))叫一條路徑,一條路徑上的非終結(jié)符的個(gè)

數(shù),叫做該路徑的長(zhǎng)度。最大的路徑長(zhǎng)度叫做該

推導(dǎo)樹的高度。

?定義3?28推導(dǎo)樹的子樹的定義:

?在一棵推導(dǎo)樹T中,以任意一個(gè)非終結(jié)符A為根,連同它

的所有后繼節(jié)點(diǎn)(直接的節(jié)點(diǎn)和非直接的節(jié)點(diǎn),即它的

所有子孫,并且子孫的個(gè)數(shù)>1),構(gòu)成一棵子樹,稱之

為推導(dǎo)樹T的A-子樹。

?推導(dǎo)樹本身就是樹T最大的一棵子樹;即S-子樹。

?注意:

?一個(gè)非終結(jié)符本身不是一棵子樹。

對(duì)于推導(dǎo)樹:

S

/\

0B

0/B\B

11

?共有4棵子樹:除它自身外,還有

?3.4空串定理

?定理3?29消除空串產(chǎn)生式

?G是一個(gè)上下文無關(guān)文法,存在一般的空

串產(chǎn)生式A-w,若W!£L(G),則存在另一

個(gè)上下文無關(guān)文法G1,?W:

?(1)L(G)=L(G1);

?⑵G1中沒有任何空串產(chǎn)生式;

?證明:

?因?yàn)椤?£L(G),對(duì)于C£V,考慮它的

所有產(chǎn)生上C—w(w不為空串£),

如果w中有非終結(jié)符AAA2,…Ak,

B1,B2,…Bj,對(duì)于Ai,

?1—iVk有Ai一£;

?首先,將C—w改造為C-w"其中w,

是通過0步,1步,...k步刪除w申的Ai

而得到的,w,共有2k個(gè)。

?最后,去掉所有的空串產(chǎn)生式(包括

在改造w的過程中引入的空串產(chǎn)生式,

如CTA1,則改造為C—A1|w;引入

了C-£),去掉無用的非終結(jié)符就得

到G1。

?再考慮G產(chǎn)生串艮的推導(dǎo)樹T,如

果B而推導(dǎo)中使用了空串產(chǎn)生式,

則樹T中有以£為標(biāo)志的葉節(jié)點(diǎn),

刪除樹T中的所有產(chǎn)生£的子樹,

得到樹T1,而它剛好是文法G1產(chǎn)

生串B的推導(dǎo)樹,所以,

L(G)=L(G1)0證畢。

?例如:

?文法:改造成G\

?S—ABCDS—ACD

?C-RSC—S

?B78A—>a

?A—>aD->d

?D—dS-d

?R—>8

?S-d

?它們產(chǎn)生相同的語言L。

定理3-30空串定理

?G是一個(gè)無關(guān)文法,存在一般的空串產(chǎn)生式A—。

則存在另一個(gè)無關(guān)文法G,使得:

?(1)L(G尸L(G');

?(2)若包£9),則G,中沒有任何空串產(chǎn)生式;

?⑶若g£L(G),則G,中有一個(gè)空串產(chǎn)生式,S,一8,

且S,不出現(xiàn)在G,的其它任何產(chǎn)生式的右邊;(S,

是G,開始符號(hào))。

?證明:

?如果w!£L(G\,先消除文法G中的所有空

串產(chǎn)生式,得到GL

?假設(shè)g£L(G),則要增加新的開始符號(hào)S,

和兩個(gè)產(chǎn)生式

?S,一S,S,一2;再按上述方法得到GL

?證畢。

?根據(jù)文法的定義,G,是一個(gè)無

關(guān)文法。也是一個(gè)相關(guān)文法,所

以,任意一個(gè)無關(guān)語言也是一個(gè)

相關(guān)語言。

?文法間關(guān)系:交叉

?語言間關(guān)系:包含

?3.5無關(guān)語言的泵浦(pumping)定理

?推導(dǎo)樹有一個(gè)性質(zhì):

推導(dǎo)樹的性質(zhì)______________

?假設(shè)推導(dǎo)樹T是終結(jié)符串z的推導(dǎo)樹,

并且假設(shè)在樹T的某個(gè)路徑上非終結(jié)

符A出現(xiàn)了兩次;

?(該文法是遞歸的文法)

?例如:

推導(dǎo)樹的性質(zhì)一

W

推導(dǎo)樹的性質(zhì)一

?該推導(dǎo)樹產(chǎn)生串z=uvwxy,由

于文法是上下文無關(guān)的文法,

在推導(dǎo)時(shí)可以用下面的A代替

上面的A,則得到另一棵推導(dǎo)

樹:

推導(dǎo)樹的性質(zhì)一

U

W

推導(dǎo)樹的性質(zhì)一

?它推導(dǎo)出$uwy=uv°wx°y;

?同樣,在推導(dǎo)時(shí)可以用上面

的A代替下面的A,并做任意

多次后,則得到另一棵推導(dǎo)

樹:

推導(dǎo)樹的性質(zhì)一

A

Vx

推導(dǎo)樹的性質(zhì)一

A

Aw

?它推導(dǎo)出串uvnwxny。

推導(dǎo)樹的性質(zhì)二

?定理3?13給定上下文無關(guān)文法G,假設(shè)文法中

的產(chǎn)生式的右邊最多有m個(gè)符號(hào),令T是串

w£L(G)的一棵推導(dǎo)樹,如果T中的沒有路徑的

長(zhǎng)度大手j,則|w|wmj。

?證明:

?使用歸納法證明:若對(duì)于以任意非終結(jié)符為根,

高度W的推導(dǎo)樹T,結(jié)論成立。

?基礎(chǔ):當(dāng)j=1時(shí),T代表單個(gè)產(chǎn)生式的使用,所以

串的長(zhǎng)度小于等于m。

?假設(shè):對(duì)于以任意非終結(jié)符為根,高度w的推導(dǎo)樹T,結(jié)

論成立;

?歸納:令T是以非終結(jié)符A為根,高度為j+1的樹,假定

樹根使用的產(chǎn)生式是A-v,而v中的每個(gè)符號(hào)至多產(chǎn)生

一個(gè)高度為j的樹,根據(jù)假設(shè),每個(gè)子樹至多產(chǎn)生一個(gè)長(zhǎng)

度為mJ的串(即v中的每個(gè)符號(hào)都是非終結(jié)符,且它們

都使用最長(zhǎng)的產(chǎn)生式進(jìn)行推導(dǎo)),由于所以,樹

T產(chǎn)生的串的長(zhǎng)度

?<mj+mJ+mJ...+mJ(共|v|個(gè))<m*mJ=mj+1。

?利用推導(dǎo)樹的上述兩個(gè)性質(zhì),可以得

到泵浦引理。

?定理3?14泵浦(pumping)引理(或uvwxy定理)。

?給定上下文無關(guān)語言L,則存在兩個(gè)僅依賴于語言L的常

藪p和q;使得:

?如果z是語言L中的串,且憶|>P;則z可以寫成uvwxy的形

式,并且滿足:

?(D|vwx|<q;

?⑵V和X至多有一個(gè)為空;

?⑶對(duì)所有的泛0,串uviwxiy者B屬于L。

?泵浦引理也可以直接稱為泵引理。

?若G是產(chǎn)生語言L的上下文無關(guān)文法,m是G中最長(zhǎng)

產(chǎn)生式右邊的符號(hào)個(gè)數(shù),k是文法G中非終結(jié)符的

個(gè)數(shù);令L粒,如果z是語言L中的串,且

Iz|>p,根據(jù)定理5,在z的推導(dǎo)樹T中,一定有某

個(gè)路徑的長(zhǎng)度大于或等于k+1,而文法G僅有k個(gè)

非終結(jié)符,則在這條路徑上至少有一個(gè)非終結(jié)符

出現(xiàn)兩次。令A(yù)是樹T中最低的重復(fù)的非終結(jié)符,

則A的下面不再包含重復(fù)的非終結(jié)符。

?故以上面的A為根的樹的高度至多為k+1;這個(gè)子

樹產(chǎn)生串vwx,根據(jù)定理3-13,|vwx|Wmk+i,令

q=mk+1,貝[||vwx|Wq;

?用下面的A代替上面的A,得至U串vwx二uv^wx^y的

推導(dǎo),用上面的A代替下面的A(進(jìn)行i次),

得到串uviwxiy的推導(dǎo),所以,對(duì)所有的iNO,

串uviwxiy屬于L。

?下面證明V和X至多有一個(gè)為空,即不能同時(shí)為空。

因?yàn)槿鬡=x=8,由下面的A彳弋替上面的A,仍得到

串z的推導(dǎo),但路徑的長(zhǎng)度縮短了。如果每個(gè)有

重復(fù)非終結(jié)符的路徑都如此,那么推導(dǎo)出串z的

樹的高度可能小于k+1;這與假設(shè)是矛盾的。所

以,v和x不能同時(shí)為空。證畢。

?利用泵浦引理,可以證明某些語言不是上下文無

關(guān)的語言,即用反證法證明語言不滿足泵浦引理。

?例3?33語言{anbncn|n>0}不是上下文無關(guān)的語言。

?證明:

?假設(shè)該語言是上下文無關(guān)的語言,則存在兩個(gè)常數(shù)p和q;

使得泵浦引理成立。考慮串a(chǎn)rbrcr,r>p,且r>q;貝U

|arbrcr|=3r>p;根據(jù)泵浦引理,串a(chǎn)rbrcr可以寫成uvwxy,

>|vwx|<q;由于r>q;所以串vwx只能在

?①a串中或者b串中或者c串中,即vwx只能包含字母a或

者b成舍c;

?②a,b串中或者b,c串中,即vwx只能包含字母a和b或

者b和c;

?否則,|vwx|>r>q。

?也就是說,串vwx中最多包含兩個(gè)字母,所以串

uviwxiy(i>1)中只有最多兩個(gè)終結(jié)符的數(shù)目在

增加,而不能使a,b和c的數(shù)目相等,所以串

uviwxiy(i>1)不在語言{anbncn|n>0}中,與

泵浦引理矛盾,所以假設(shè)不成立。語言{anbncn

|n>0}不是上下文無關(guān)語言。證畢。

?3.6短語

?定義3?12短語的定義

?如果耶丫是上下文無關(guān)文法G的一個(gè)句型,若有

S=>*QAY,并且有A=>+0,則稱0是句型Q0Y關(guān)于

非終結(jié)符A的一個(gè)短語(或者簡(jiǎn)稱B是句型。即的

一個(gè)短語;特別地,若A=>B,則B是句型印丫的

一個(gè)直接短語。句型最左邊的直接短語,就是句

柄。(注意:一個(gè)句型或者句子的短語是該句型

或者句子的一個(gè)子串)。

?根據(jù)定義,句型印丫本身就是印丫關(guān)于開始符號(hào)S

的一個(gè)短語。

?利用子樹的概念,可以方便地理解短語的概念。

在句型印丫的推導(dǎo)樹中,若B是A-子樹產(chǎn)生的串,

則B就是句型印丫關(guān)于非終結(jié)符A的短語,如果子

樹只有父子兩代,則B就是直接短語。最左邊的

僅有父子兩代的子樹產(chǎn)生的直接短語就是句柄。

?對(duì)于文法G的一個(gè)給定的句型(或者句子),可

以有多個(gè)短語,多個(gè)直接短語,只有一個(gè)句柄。

在指明短語(直接短語,句柄)時(shí),一定要指明

它是哪一個(gè)句型(或句子)的短語(直接短語,

句柄)。

?定義3?13素短語的定義

?素短語是一個(gè)短語,至少包含一個(gè)終

結(jié)符,并且除它自身以外,不再含有

任何更小的素短語。最左素短語是指

句型(或句子)最左邊的素短語。

?例3?41文法

?E-E+T

?E-T

?T—T*F

?T—F

?F一(E)

?F―2

?對(duì)于句型F+2*F,

?短語:F,2,2*F,F+2*F

?直接短語:F,2

?句柄:F

?素短語:2

?最左素短語:2

?3.7形式語言與高級(jí)計(jì)算機(jī)程序設(shè)計(jì)語言

?對(duì)于某種高級(jí)計(jì)算機(jī)程序設(shè)計(jì)語言的學(xué)習(xí),

首先要了解該語言的字母表,各類單詞符

號(hào)的形成規(guī)定(即詞法規(guī)則)。

?程序設(shè)計(jì)語言的單詞符號(hào)一般分為5類:

?保留字,標(biāo)識(shí)符,運(yùn)算符,常量,(分)界符。

?標(biāo)識(shí)符和常量可以有任意多個(gè)。

?保留字,運(yùn)算符和(分)界符的個(gè)數(shù)是

規(guī)定好的(對(duì)一個(gè)具體的高級(jí)程序設(shè)

計(jì)語言),是有限的。

?標(biāo)識(shí)符的形成可以使用文法:(字母開

始的字母、數(shù)字串)

?I—L

?I—IL|ID

?L-^a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|

S|t|ll|v|w|xMz

?D—0|1|2|3|4|5||6||7|8||9

?正整型常量的形成可使用文法:

?C->D|EA

?A->AD|D

?E-1|2|3|4|5||6||7|8||9

?D->0|E

?對(duì)于某種高級(jí)計(jì)算機(jī)程序設(shè)計(jì)語言的

學(xué)習(xí)和介紹,還必須了解該語言的語

法區(qū)位(如:表達(dá)式,語句,子程序,

程岸)的組成規(guī)定(即語法規(guī)則)。

?語法規(guī)則對(duì)于高級(jí)程序設(shè)計(jì)語言的設(shè)計(jì)者,

實(shí)現(xiàn)者和使用者都是十分有用途

?語法規(guī)則表達(dá)了語言設(shè)計(jì)者的意圖和設(shè)計(jì)

目標(biāo);

?指導(dǎo)語言的使用者寫出正確的程序;

?指導(dǎo)語言的實(shí)現(xiàn)者(編譯程序的設(shè)計(jì)者)編

寫一個(gè)語法檢查程序來識(shí)別所有合法的程

序。

?語法規(guī)則可以用自然語言描述(如漢語,

英語等);也可以用通用的形式化的方式-

一文法來進(jìn)行語法描述(特別是上下文無

關(guān)的文法)。而程序中的各個(gè)語法單位就

是文法所產(chǎn)生的句子。

?定義3?43二義性文法的定義

?一個(gè)文法G是二義性的,如果L(G)中的某個(gè)串x

有兩棵不同的推導(dǎo)樹,即串x有兩種不同的最左

推導(dǎo)或兩種不同的最右推導(dǎo);否則,文法G是非

二義的文注。

?定義3?44二義性語言的定義

?對(duì)于一個(gè)語言L,如果產(chǎn)生該語言的所有文法都

是二義性的文法,則L是二義性的語言。

?實(shí)際上,語言的二義性是不可判定的。二

義性的語言也是沒有什么實(shí)際意義的。

?絕大多數(shù)的程序設(shè)計(jì)語言的語法規(guī)定可以

用上下文無關(guān)文法進(jìn)行描述。

?例基本PASCAL的語法結(jié)構(gòu):

?G=(E,V,C,P);

?其中:

?E={begin,end,pred,succ,:

while,do,;,(,),0,x,y)

?V二cS,SPS2,A,W,U,T)

?c是開始符號(hào)

?P={C—beginend

S]-SS'

JL乙

?

0s2—'0s1E

S-AWC

?A->V:=T

?T-*pred(V)|succ(V)|0

?W^whileVOVdoS

?V-xy

C-beginS】end

S1-S|S;Si

SfA|W|C

A->V:=T

T-pred(V)|succ(V)|0

WfwhileVOVdoS

Vfxy

?該文法產(chǎn)生的一個(gè)基本語法單位為:

?begin

?y:=0;

?whilexOydo

?y:=succ(y)

?end

?(文法中沒有考慮回車和換行)

?3.8形式語言與自然語言

?無關(guān)文法也可以用來描述自然語言(例如對(duì)英

語)O

?使用、列符號(hào):

?S代表語句;NP代表名詞短語;VP代表動(dòng)詞短語

?Adj代表形容詞;Det代表冠詞;N代表名詞

?V代表動(dòng)詞;Prep代表介詞;

?A代表形容詞短語;PP代表介詞短語

?可以有下列文法:

?S—NPVP

?NP—DetN|DetAN

?A->AdjA|Adj

?VP—VbePP

?PP—PrepNP

?Vbe—>am|is|are

?Det->a|an|the

?Prep—>on|in|for|......

?V—play|go|……

?N>boy|girl|...........

?Adj—>small|big|high|

?對(duì)于語句:

?Thebigredballisonthetable

?推導(dǎo)樹P52圖3-13。

3.9基本的語法分析方法

?對(duì)給定的上下文無關(guān)文法G=(名,V,S,

P)及符號(hào)串w£g*,語法分析就是判斷

串w是否是文法G能產(chǎn)生的合法的句子。

即是否S=>*w成立?

?對(duì)于計(jì)算機(jī)程序設(shè)計(jì)語言和使用

該語言編寫的程序而言,語法分

析的任務(wù)就是要判斷程序中的各

個(gè)語句是否是合法的語句,進(jìn)而

判斷整個(gè)程序是否合法。這也是

形式語言中要研究的一個(gè)重要方

面。

?基本的語法分析方法有兩種:

?⑴自上(頂)而下法

?從文法的開始符號(hào)(頂)出發(fā),能否找到一個(gè)最左推導(dǎo)

序列推導(dǎo)出w(下),即S=>+w;或者從根節(jié)點(diǎn)S開始,

是否能向下構(gòu)造一棵推導(dǎo)樹,能產(chǎn)生串w;

?⑵自下(底)而上法:

?與自上而下分析法的推導(dǎo)序列相反,從符號(hào)串w(底)出發(fā)

尋找一個(gè)歸約序列,逐步對(duì)可歸約串向上進(jìn)行歸約,直

到文法的開始符號(hào)S(頂)。

?例3?46對(duì)于算術(shù)表達(dá)式的文法(E是開始

符號(hào),文法表示出了運(yùn)算符的優(yōu)先級(jí))

?E—E+T|T

?T—T*F|F

?F-(E)|2

?串2+2*2是否是文法的合法的句子呢?

?自上而下法:

?最左推導(dǎo):

E=>E+T=>T+T=>F+T=>2+T=>2+T*F=>2

+F*F=>2+2*F=>2+2*2

?最右推導(dǎo):

?E=>E+T=>E+T*F=>E+T*2=>E+F*2=>E+

2*2=>T+2*2=>F+2*2=>2+2*2

?對(duì)于自下而上的分析法,遇到的最大問題是可歸約串的

定義。若每次歸約的是句柄,就是LR分析法,該過程也

稱之為最左歸約或規(guī)范歸約,實(shí)質(zhì)上是最右推導(dǎo)的逆過

程(因此,最右推導(dǎo)也被稱為規(guī)范推導(dǎo))。若每次歸約

的是最左素短語,就是算符優(yōu)先分析法。

?自下而上法:

?LR分析法:(畫下劃線的是該句型的句柄)

?2+2*2<=F+2*2<=T+2*2<=E+2*2<=E+F*2<=E+T*2<=E

+T*F<=E+T<=E

?算符優(yōu)先分析法:(畫下劃線的是該句型的最左素短語)

?2+2*2<=F+2*2<=F+F*2<=F+FT<=F+I<=E

?奇以看出,餐符優(yōu)先分布法比LR分析法要簡(jiǎn)明,原因是

它省略了單個(gè)符號(hào)的產(chǎn)生式(形如A-B的產(chǎn)生式)的歸

約。其中,A,BeVo

?實(shí)際上,算符優(yōu)先分析法省略了產(chǎn)生式右邊全是非終結(jié)

符的的產(chǎn)生凝(形加A-W的產(chǎn)生式)的歸約。其中:

Aev,Wev+o

?因?yàn)榉墙K結(jié)符串不可能是素短語。

?3.10消除左遞歸

?在某些情況下,需要消除一個(gè)無關(guān)文法

中的左遞歸。

?遞歸的好處是產(chǎn)生無窮的語言,消除

左遞歸,只是將左遞歸改造為右遞歸。

?左遞歸包括直接的和間接的。

?3.10.1消除直接左遞歸

?直接左遞歸的產(chǎn)生式形式為

?A—>Av

?其中:A£V,ve(^UV)+o

?遞歸的產(chǎn)生式可以產(chǎn)生串的任意次連

接,可以將左遞歸轉(zhuǎn)換為右遞歸。

?假設(shè)文法G的產(chǎn)生式形式為:

?A一Av|w,

?其中:A£V,v,w£(2UV)*,

?且w不以A開頭,

?對(duì)于A,有A=>*wv*

?增加一個(gè)新的非終結(jié)符B,構(gòu)造無左

遞歸文法:

?A->wB|w

?B—>vB|v

?它產(chǎn)生的串也為wv*的形式;

?或者A—wB

?B—VB|£

?實(shí)際上,消除了£產(chǎn)生式,就得

?A—>wB|w

?B-vB|v

?一般,產(chǎn)生式的形式為:

?A^Avl|Av2|...|Avn|w1|w2|...|wm

?對(duì)于A,有

?A=>*(w1|w2|...|wm)(v1|v2|...|vn)*

?增加一個(gè)新的非終結(jié)符B,構(gòu)造無左遞歸

文法:

?A-w1B|w2B|…|wmB|w1|w2|...|wm

?B一v1B|v2B|??.|vnB|v1|v2|??.|vn

?它產(chǎn)生的串也為

?(w1+w2+...wm)(v1+v2+...vn)*的形式;

?某些文法可能沒有直接左遞歸,但可能會(huì)

有間接左遞歸,

?例如:文法S—Aa

?A—Sb|b

?雖然它的每個(gè)產(chǎn)生式都沒有直接左遞歸,

但推導(dǎo)S=>Aa=>Sba導(dǎo)致了左遞歸的出現(xiàn),

這種左遞歸就稱為間接左遞歸。

?3.10.2消除間接左遞歸

?G是一個(gè)上下文無關(guān)文法,首先使用

空串定理;然后將文法G中的所有非

終結(jié)符按任一順序排列為A1,

A2,…An,根據(jù)下列算法消除可能

存在的間接左遞歸。

?fori:=1tondo

?begin

?forj:=1toi-1do

?begin

?將形如Ai-Ajw的產(chǎn)生式改寫為:

?Ai^v1w|v2w|...|vkw;

?(其中:vrv2,Vk是Aj的侯選式)

?end

?消除Ai產(chǎn)生式的直接左遞歸;

?end

?最后,刪除多余(無用)的產(chǎn)生式,

即在從文法開始符號(hào)S開始的任何推

導(dǎo)中都不會(huì)使用的非終結(jié)符(即無用

非終結(jié)符)對(duì)應(yīng)的產(chǎn)生式;就可以得

到?jīng)]有間接左遞歸的文法。

?該算法思想是將推導(dǎo)過程中可能出現(xiàn)

的左遞歸,在文法的產(chǎn)生式中就體現(xiàn)

出來,產(chǎn)生式的改寫實(shí)際上是推導(dǎo)的

體現(xiàn)一用Aj的侯選式將Aj代替掉。

?為方便實(shí)現(xiàn),將上述算法進(jìn)行改寫。

?G是一個(gè)上下文無關(guān)文法,將文法G

中的所有非終結(jié)符按任一給定的順序

排列為A1,A2,…An,那么,文法

的每個(gè)產(chǎn)生式是Ai—Ajw的

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

評(píng)論

0/150

提交評(píng)論