形式語言03章無關(guān)文法與無關(guā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的