《形式語言與自動(dòng)機(jī)》課件ch4.1

12023/5/21SchoolofComputerScience,BUPT第四章上下文無關(guān)文法與下推自動(dòng)機(jī)推導(dǎo)樹和文法的二義性上下文無關(guān)文法的變換

Chomsky范式 Greibach范式下推自動(dòng)機(jī)上下文無關(guān)語言的性質(zhì)22023/5/21SchoolofComputerScience,BUPT本章要點(diǎn)上下文無關(guān)文法（即2型文法）：

產(chǎn)生式形如A→α,A,∪Τ)*所描述的語言稱為上下文無關(guān)語言。用途：可定義程序設(shè)計(jì)語言、進(jìn)行語法分析、簡(jiǎn)化語言翻譯2型文法對(duì)應(yīng)的識(shí)別器——下推自動(dòng)機(jī)

PDA（PushDownAutomata)由輸入帶、有限控制器和下推棧構(gòu)成32023/5/21SchoolofComputerScience,BUPT回顧：在第一講中介紹過如下內(nèi)容設(shè)T=0,1，L=0n1nn1，如0011,000111,01

L,而10,1001,,010

L.

如下是一個(gè)可接受該語言的上下文無關(guān)文法

S01S0S1

但沒有任何有限自動(dòng)機(jī)能夠接受語言L.42023/5/21SchoolofComputerScience,BUPT歸約與推導(dǎo)的概念:推理字符串是否屬于文法所定義的語言一種是自下而上的方法，稱為遞歸推理(recursiveinference），遞歸推理的過程習(xí)稱為歸約；一種是自上而下的方法，稱為推導(dǎo)（derivation）.歸約過程將產(chǎn)生式的右部（body）替換為產(chǎn)生式的左部（head）.推導(dǎo)過程將產(chǎn)生式的左部（head）替換為產(chǎn)生式的右部（body）.4.1推導(dǎo)樹和二義性

52023/5/21SchoolofComputerScience,BUPT歸約與推導(dǎo)歸約過程舉例

對(duì)于CFG

Gexp=({E,O},

{(,),＋,,v,d},P

,E)，P為（1）EEOE

（2）E(E)

（3）Ev

（4）Ed

（5）O＋

（6）O

遞歸推理出字符串v(v＋d)

的一個(gè)歸約過程為v(v＋d)（4）v(v＋E)（6）vO(v＋E)（3）vO(E＋E)（5）vO(EOE)（1）vO(E)（2）vOE（3）EOE（1）E62023/5/21SchoolofComputerScience,BUPT歸約與推導(dǎo)推導(dǎo)過程舉例

對(duì)于CFG

Gexp=({E,O},

{(,),＋,,v,d},P

,E)，P為（1）EEOE

（2）E(E)

（3）Ev

（4）Ed

（5）O＋

（6）O

從開始符號(hào)到字符串v(v＋d)

的一個(gè)推導(dǎo)過程為v(v＋d)（4）v(v＋E)（6）E(E)（3）（1）v(EOE)（5）（3）EOE（1）EEE（2）v(E)v(E＋E)72023/5/21SchoolofComputerScience,BUPT歸約與推導(dǎo)EEOEE(E)EvEdO＋O最左推導(dǎo)(leftmostderivations)

若推導(dǎo)過程的每一步總是替換出現(xiàn)在最左邊的非終結(jié)符，則這樣的推導(dǎo)稱為最左推導(dǎo).為方便，最左推導(dǎo)關(guān)系用表示，其傳遞閉包用表示.

如對(duì)于文法Gexp，下面是關(guān)于v(v＋d)

的一個(gè)最左推導(dǎo)：lmlmv(v＋d)v(v＋E)v(EOE)EOEEv(E)vOEvEv(vOE)lmlmlmlmlmlmlmlm82023/5/21SchoolofComputerScience,BUPT歸約與推導(dǎo)EEOEE(E)EvEdO＋O最右推導(dǎo)(rightmostderivations)

若推導(dǎo)過程的每一步總是替換出現(xiàn)在最右邊的非終結(jié)符，則這樣的推導(dǎo)稱為最右推導(dǎo).為方便，最右推導(dǎo)關(guān)系用表示，其傳遞閉包用表示.

如對(duì)于文法Gexp，下面是關(guān)于

v(v＋d)

的一個(gè)最右推導(dǎo)：rmrmv(v＋d)E(v＋d)EO(E＋d)EOEEEO(EOd)EO(E)EO(EOE)EO(v＋d)rmrmrmrmrmrmrmrm92023/5/21SchoolofComputerScience,BUPT推導(dǎo)樹

用圖的方法表示一個(gè)句型的推導(dǎo)，這種圖稱為推導(dǎo)樹（也稱語法樹或語法分析樹）。有助于理解語法結(jié)構(gòu)的層次。定義方法：文法的起始符為根，樹的枝結(jié)點(diǎn)標(biāo)記是非終結(jié)符，葉結(jié)點(diǎn)標(biāo)記為終結(jié)符或。若枝結(jié)點(diǎn)有直接子孫x1,x2,…,xk，則文法中有生成式A→x1x2…xk102023/5/21SchoolofComputerScience,BUPT推導(dǎo)樹舉例例：（書P94例1） 文法S→S+S|S*S|(S)|a， 對(duì)句子(a*a+a)可有推導(dǎo)樹即：推導(dǎo)樹是對(duì)文法G中一個(gè)特定句子形式的派生過程所做的一種自然描述。

112023/5/21SchoolofComputerScience,BUPT邊緣葉子從左向右組成的字符串稱為推導(dǎo)樹的邊緣。如圖x1y1y2x3xmxm+1xn-1y3y4y5是樹的邊緣122023/5/21SchoolofComputerScience,BUPT(1)EEOE(2)E(E)(3)Ev(4)Ed(5)O＋(6)O歸約過程自下而上構(gòu)造了一棵樹

如對(duì)于文法Gexp，關(guān)于

v(v＋d)

的一個(gè)歸約過程可以認(rèn)為是構(gòu)造了如下一棵樹：v(v＋d)（4）v(v＋E)（6）vO(v＋E)（3）vO(E＋E)（5）vO(EOE)（1）vO(E)（2）vOE（3）EOE（1）EEEOEEOEEd＋v()v132023/5/21SchoolofComputerScience,BUPT(1)EEOE(2)E(E)(3)Ev(4)Ed(5)O＋(6)O推導(dǎo)過程自上而下構(gòu)造了一棵樹

如對(duì)于文法Gexp，關(guān)于

v(v＋d)

的一個(gè)推導(dǎo)過程可以認(rèn)為是構(gòu)造了如下一棵樹：Ed＋vvOEEE()EEOv(v＋d)（4）v(v＋E)（6）E(E)（3）（1）v(EOE)（5）（3）EOE（1）EEE（2）v(E)v(E＋E)142023/5/21SchoolofComputerScience,BUPT歸約、推導(dǎo)與分析樹之間關(guān)系三者之間的關(guān)系設(shè)

CFG

G=(N,

T,P

,S).以下命題是相互等價(jià)的：

(1)字符串

wT*可以歸約（遞歸推理）到非終結(jié)符A；

(2)

Aw；(3)

Aw；(4)

Aw；(5)

存在一棵根結(jié)點(diǎn)為A的分析樹，其邊緣為

w.lmrm152023/5/21SchoolofComputerScience,BUPT定理： 設(shè)2型文法G=（N，T，P，S），如果存在S=>+ω，當(dāng)且僅當(dāng)文法G中有一棵邊緣為ω的推導(dǎo)樹。證明：

需證明對(duì)任意枝結(jié)點(diǎn)B∈N，有B=>*ω當(dāng)且僅當(dāng)存在邊緣為ω的B樹（根為B的樹）子樹概念： 一棵派生樹的子樹，是樹中的某個(gè)頂點(diǎn)連同它的全部后裔，以及連接這些后裔的邊。歸約、推導(dǎo)與分析樹之間關(guān)系162023/5/21SchoolofComputerScience,BUPT證明步驟：1.證當(dāng)ω是B樹邊緣時(shí)，有B=>*ω 設(shè)B樹邊緣為ω，對(duì)樹中枝結(jié)點(diǎn)數(shù)目m作歸納證明。2.設(shè)有B=*ω，證明存在一棵邊緣為ω的B樹。 對(duì)推導(dǎo)步數(shù)作歸納172023/5/21SchoolofComputerScience,BUPT1.證當(dāng)ω是B樹邊緣時(shí)，有B=>*ω 設(shè)B樹邊緣為ω，對(duì)樹中枝結(jié)點(diǎn)數(shù)目m作歸納證明。wBX1X2X3w1w2w3……B基礎(chǔ)m為1.分析樹一定如右圖所示，必定有產(chǎn)生式Bw.因此，Bw.歸納m大于1的分析樹一定如右圖所示，必定有產(chǎn)生式BX1X2…Xk.存在

w1,w2,…,wk，wi

是Xi子樹的邊緣（1ik），且

w=w1w2…wk，由歸納假設(shè)，Xiwi（1ik）.

在此基礎(chǔ)上易證得Bw.182023/5/21SchoolofComputerScience,BUPT2.設(shè)有B=*ω，證明存在一棵邊緣為ω的B樹。 對(duì)推導(dǎo)步數(shù)作歸納基礎(chǔ)步數(shù)為1.一定有產(chǎn)生式Bw.w可以歸約到B.歸納設(shè)步數(shù)大于1，第一步使用了產(chǎn)生式BX1X2…Xk.

該推導(dǎo)如B