形式語言與文法

形式語言與文法第一頁，共九十三頁，編輯于2023年，星期六§1.符號串

符號串是形式語言中最基本的名詞.一,字母表與符號串

1,字母表∑

定義:元素的非空有窮集合例:∑={a,b,c}(a,b,c字母表)

∑={0,1}(二進(jìn)制數(shù)字字母表)

∑={漢字,數(shù)字,標(biāo)點(diǎn)符號,…}(漢字組成的字母表)

注:元素可是字母、數(shù)字或其他符號.

字母表中至少有一個元素.第二頁，共九十三頁，編輯于2023年，星期六2.符號(字符)

定義：字母表中的元素.

注:符號是字母表中不可再分解的最小單位.

3.符號串定義：字母表中的符號組成的有窮序列.

例:∑={a,b,c}

符號:a,b,c

符號串:a,b,c,ab,ac,aa,ba,ca,abc,…

例;設(shè)字母表A={0,1}A中的符號:0,1A中的符串:0,1,01,10,00,11,001,010,

…,01000,…第三頁，共九十三頁，編輯于2023年，星期六

顯然:字母表上的符號串可形成一個集合(可數(shù)無窮)注:1.符號串的組成與符號串組成的順序有關(guān).如01≠10,ab≠ba2.空符號串為不包含任何符號的符號串,記為:ε3.符號串的長度:符號串所含符號的個數(shù).設(shè)符號串為x,則x的長度為∣x∣。

例:∣a∣=1∣abc∣=3

特別：|ε|＝0即空符號串的長度為零．二．符號串的運(yùn)算１．連接運(yùn)算

定義：設(shè)x和y為符號串，則xy被稱為x與y的連接．設(shè)x＝abc，y＝10a則xy＝abc10a；yx＝10aabc第四頁，共九十三頁，編輯于2023年，星期六２．符號串的方冪設(shè)有符號串x，則x的n次連接稱為x的n次方冪，記為:x例：x＝ε

（注:x≠１）

x＝x

x＝xx

x＝xx＝xx＝xxx

……

x＝x

x＝xx＝xx…x

n次連接例:x＝abc則x＝ε

，x＝abc，x＝abcabc

即︱x︱＝０，︱x︱＝３，︱x︱＝６n0012322nn－1n－1011022第五頁，共九十三頁，編輯于2023年，星期六３．符號串集合的乘積

設(shè)AB＝｛xy︱x∈Ａ，y∈Ｂ｝即:AB是x∈Ａ,且y∈Ｂ的所有符號串xy構(gòu)成的集合．例:設(shè)A＝｛a，b｝，B＝｛c，d｝則AB＝｛ac，ad，bc，bd｝

注：{ε

}A=A{ε}=AA=A=A(其中為空集)={}

注:ε

不屬于，即空符號串并不屬于空集

第六頁，共九十三頁，編輯于2023年，星期六4.符號串集合的方冪

設(shè)A為符號串集合,則定義

A={ε}A=AA=AAA=AA=AA=AAA

……A=AA=AA=AA……A(n個)

例:設(shè)A={a,b}A={ε}A={a,b}A={aa,ab,ba,bb}(A共有2=4個長度為2的元素)

A=AA={aa,ab,ba,bb}{a,b}={aaa,aba,baa,bba,aab,abb,bab,bbb}

(A共有2=8個長度為3的元素)012322nn－1n－101232233第七頁，共九十三頁，編輯于2023年，星期六5.符號串集合的正閉包A和閉包A⑴.符號串集合的正閉包A

設(shè)A為符號串集合,則A定義為:

A=AUAUAU……UAU……

例設(shè)A={a,b}則

A={a,b}U{aa,ab,ba,bb}U……={a,b,aa,ab,ba,bb,aaa,…,bbb,……}={a,b}

即:A包括了由A上的元素a,b構(gòu)成的所有符號串.⑵.符號串集合A的閉包A.A=AUAUAU…UAU……(A=AUA)

即A={ε}UA=AU{ε}(A=A－{ε})＋＊＋＋＋123n＋＋＊＊012n＊0＋＊＋＋＋＊+第八頁，共九十三頁，編輯于2023年，星期六例設(shè)A={a,b}則

A={ε,a,b,aa,ab,ba,bb,aaa,…,bbb,……}={a,b}

顯然:對于所有的A,有ε

∈A＊＊＊第九頁，共九十三頁，編輯于2023年，星期六§2.文法和語言的形式定義一.文法與語言的關(guān)系

●語言:由定義在該語言字母表上,且按一定組成規(guī)則所構(gòu)成的句子的集合.

即:字母表{字符串(句子)}(語言)

●語言的描述

⑴.當(dāng)語言為有窮個句子的集合時,可用枚舉的方法表示語言.

⑵.當(dāng)語言為無窮個句子的集合時,則用有無窮的語法規(guī)則(文法)描述無窮的句子的結(jié)構(gòu).語法規(guī)則第十頁，共九十三頁，編輯于2023年，星期六例:漢語:人們無法列出全部的句子.但人們可以給出一些規(guī)則,用這些規(guī)則來說明(或定義)句子的組成結(jié)構(gòu).

如:漢語句子結(jié)構(gòu):<句子>=<主語>+<謂語><謂語>=<動詞>+<直接賓語><主語>=<代詞>︱<名詞>…………

用擴(kuò)充BNF來表示這種句子的結(jié)構(gòu):<句子>∷=<主語><謂語>(∷=表示“定義為”，“產(chǎn)生”，“生成”)<主語>∷=<代詞>︱<名詞>(︱表示“或者”)<代詞>∷=我︱你︱他(<>表示非終結(jié)符)<名詞>∷=王明︱大學(xué)生︱工人︱英語

<謂語>∷=<動詞><直接賓語>(不加<>表示終結(jié)符)第十一頁，共九十三頁，編輯于2023年，星期六

<動詞>∷=是∣學(xué)習(xí)

<直接賓語>∷=<代詞>∣<名詞>利用以上規(guī)則(文法)推導(dǎo)句子:我是大學(xué)生.<句子><主語><謂詞><代詞><謂語>

我<謂語>

我<動詞><直接賓語>

我是<直接賓語>

我是<名詞>

我是大學(xué)生利用上列文法:可以產(chǎn)生的句子:我學(xué)習(xí)英語,他學(xué)習(xí),語,他是工人,….(很多句子)第十二頁，共九十三頁，編輯于2023年，星期六

利用上列文法不可產(chǎn)生“我大學(xué)生是”.它不符合以上規(guī)則.

文法的作用:不僅嚴(yán)格定義句子的結(jié)構(gòu),也是為了用有限的規(guī)則把語言的全部句子描述出來。它是用有窮的集合刻畫無窮集合的工具.

文法:語言的語法規(guī)則的有窮表示.(文法又稱元語言)注:1.有窮的文法通過推導(dǎo)的方法,可以推導(dǎo)出給定字母表上的所有句子.2.描述文法的所有字符構(gòu)成了語言的字母表.3.通過文法在推導(dǎo)合法句子過程中會有多個句型產(chǎn)生.4.合法的句型和句子是用字符串表示的.第十三頁，共九十三頁，編輯于2023年，星期六二.文法的形式定義1.規(guī)則(產(chǎn)生式,生成式,重寫規(guī)則)是一個符號與一個符號串的有序?qū)?A,β)

常寫成:A∷=β或A→β

其中:A是規(guī)則的左部.它是某個字母表∑的正閉包∑中的一個符號.即A∈∑.β是規(guī)則的右部.它是∑中一個符號串.(包括ε)2.文法的形式定義定義:文法G是一個四元組,它是規(guī)則的非空有窮集合.G=(V,V,P,S)

其中:V是文法規(guī)則式中的非終結(jié)符號集.V是文法規(guī)則式中的終結(jié)符號集.＋＋NTNT﹡第十四頁，共九十三頁，編輯于2023年，星期六

V∩V=Ф P是文法的規(guī)則式集。

S是文法的開始符號（識別符號）。S∈V非終結(jié)符號：出現(xiàn)在產(chǎn)生是左邊，能派生出符號和符號串的符號,常用大寫字母表示，即，每一個非終結(jié)符號表示一定的符號串。它至少要在產(chǎn)生式左邊出現(xiàn)一次。終結(jié)符號：不能派生出符號串的符號，它是組成語言不可再分的基本符號，一般用小寫字母表示。NTN第十五頁，共九十三頁，編輯于2023年，星期六例：文法G=(V,V,P,S)其中VN={S} VT={0,1} P={S→0S1,S→01}一般約定:1.只寫出文法的產(chǎn)生式

2.第一條產(chǎn)生式的左部是開始符號，且習(xí)慣用G（開始符號）表示。上例文法可寫成：

G[S]:S::=0S1 S::=01NT第十六頁，共九十三頁，編輯于2023年，星期六例：G[<標(biāo)識符>]:

<標(biāo)識符>::=<字母>|<標(biāo)識符><字母>|<標(biāo)識符><數(shù)字>

<字母>::=a|b|c|…|z

<數(shù)字>::=0|1|2|…|9

其中：VN={<標(biāo)識符>，<字母>，<數(shù)字>} S={<標(biāo)識符>} VT={a,b,c,…,z,0,1,2,…,9

}字母表：V=VN∪VT={<標(biāo)識符>,<字母>,<數(shù)字>,a,b,c,…,z,0,1,2,…,9

}第十七頁，共九十三頁，編輯于2023年，星期六3.推導(dǎo)有了文法，怎樣由文法推導(dǎo)出與該文法相應(yīng)的語言？為此引入了“推導(dǎo)”等概念。直接推導(dǎo)設(shè)x,y是V*中任意符號串，若用一次規(guī)則式可以從x推出y，則稱y是x的直接推導(dǎo)，記為：xy。（或稱符號串x直接產(chǎn)生了符號串y，或稱y直接歸約到x）第十八頁，共九十三頁，編輯于2023年，星期六例：設(shè)G[S]:S::=0S1|01

則有如下一些直接推導(dǎo)：S01（利用S::=01）S0S1（利用S::=0S1）0S10011（利用S::=01）0S100S11（利用S::=0S1）說明：每利用文法中的一條規(guī)則U::=u一次，均可得到一次直接推導(dǎo)：

Uu第十九頁，共九十三頁，編輯于2023年，星期六推導(dǎo)（＋推導(dǎo)） 若使用若干次規(guī)則式可以從x推出y，則稱y為x的推導(dǎo)，記為：x＋y（或稱x產(chǎn)生y，或稱y規(guī)約到x），或記為：xy例：上例：

0S100S11000S11100001111∴0S1+00001111

（推導(dǎo)長度為3）＋第二十頁，共九十三頁，編輯于2023年，星期六廣義推導(dǎo)（＊推導(dǎo)） 若x＋y或者x＝y(tǒng)（表示0步推導(dǎo)），則寫為x＊y（反之亦然，即：x＊y，當(dāng)且僅當(dāng)x＋y或者x＝y(tǒng)）例，上例中：0S1+00001111也可記為：0S1*00001111注：直接推導(dǎo)、推導(dǎo)、廣義推導(dǎo)的區(qū)別： 推導(dǎo)長度n不同： 直接推導(dǎo)：n＝1

推導(dǎo)：n≥1

廣義推導(dǎo)：n≥0(0步推導(dǎo)：如S＝s)＊包涵＋包涵第二十一頁，共九十三頁，編輯于2023年，星期六4.句型和句子設(shè)有文法G[S],若有S＊x,則稱符號串x為文法G[S]的句型。換句話說：凡是由識別符號推導(dǎo)出來的任意符號串稱為句型。句子：僅有終結(jié)符號組成的句型稱為句子。區(qū)別：符號串x∈(VN∪VT)*;x稱為句型，

符號串x∈VT*;x稱為句子。第二十二頁，共九十三頁，編輯于2023年，星期六例：G[S]:S::=01|0S1 S01S0S100S11000111可見：01,0S1,00S11,000111均為文法G[S]的句型。其中：01，000111為句子（說明句型包含了句子，句子是特殊的句型）但是：符號串000S11,0000111都不是文法G[S]的句型。第二十三頁，共九十三頁，編輯于2023年，星期六例：已知文法G[E]：E::=E+E|E*E|(E)|i (其中:VN={E} VT={+,*,i,(,)})試證明:符號串(i*i+i)是文法G[E]的一個句子。證明：只要證明(i*i+i)是文法G[E]的一個存在的推導(dǎo)）(需從開始符號出發(fā))

E=>(E) =>(E+E) =>(E*E+E) =>(i*E+E) =>(i*i+E) =>(i*i+i)即：E=>＊(i*i+i)所以,符號串(i*i+i)是文法G[E]的一個句子。第二十四頁，共九十三頁，編輯于2023年，星期六三、語言的形式定義：定義：由文法G[S]產(chǎn)生的所有句子的集合。即：

L(G[S])={x|S=>+x,且x∈V*}注：一旦文法給定，語言就確定。語言L(G)是V*的子集。（語言是字母表中終結(jié)符號串閉包的子集） 即：屬于L(G)的句子屬于V*

反之,屬于V*的符號串x不一定屬于L(G)。TTTT第二十五頁，共九十三頁，編輯于2023年，星期六例：已知文法G[S]：

S::=0S1|01求:L(G)=?解：分析：S=>0S1

=>00S11

=>000S111

…

=>0n-1S1n-1

=>0n1n

即：S=>＊0n1n ∴G描述的語言：L(G[S])={0n1n|n≥1}但：VT’＝{0,1,00,01,10,11,000,…,111,0000,…,0011,…,1111,…}，可見L(G)僅是VT‘的真子集。＋＋第二十六頁，共九十三頁，編輯于2023年，星期六例：已知文法：G[S]:S∷=0S|1S|ε,求L(G)=?解：L(G[S])={ε,0,1,01,11,00,10,…}

={x|x∈{0,1}*}第二十七頁，共九十三頁，編輯于2023年，星期六例：已知： S∷=aB|bA A∷=a|aS|bAA B∷=b|bS|aBB求：L＝？解： S=>aB=>ab S=>aB=>abS=>abaB=>abab S=>aB=>aaBB=>aabB=>aabb又∵S=>bA=>ba

S=>bA=>baS=>babA=>baba

S=>bA=>bbAA=>bbaA=>bbaa∴L(G[S])={x|x∈{a,b},且x中a，b個數(shù)相同}

反過來，給定語言L(G)后，若要寫出能正確描述此語言的文法，是有一定難度的。+第二十八頁，共九十三頁，編輯于2023年，星期六例：試對語言L(G)={(n)n|n=0,1,2,…}構(gòu)造相應(yīng)的文法G。解：（1）首先分析L是由怎樣的符號串x組成的。 當(dāng)n=0時，x=ε

當(dāng)n=1時，x=()

當(dāng)n=2時，x=(())

當(dāng)n=3時，x=((())) … ∴L(G)={ε,(),(()),((())),…}第二十九頁，共九十三頁，編輯于2023年，星期六(2)歸納集合L(G)的組成特點(diǎn)：L(G)中每個符號串呈對稱形式，即(和)成對出現(xiàn)。L(G)為無窮集合，因此描述出的規(guī)則中必然含有遞歸定義。L(G)中的終結(jié)符號只有兩個:(和)。(3)寫出規(guī)則：S∷=(S)|ε即，定義此語言L(G)的文法：

G:VT={(,)},VN={S},S為開始符號，產(chǎn)生式：

P：

S∷=(S)|ε第三十頁，共九十三頁，編輯于2023年，星期六例：給出語言L(G)＝{anbncm|n≥1,m≥0}的對應(yīng)文法解：分析：將anbn看成一個整體用一個非終結(jié)符號A來表示，cm看成另一個整體用非終結(jié)符B來表示。設(shè)S為G的識別符號，則有S∷=AB，而由A推出anbn，B推出cm。保證anbn成立，即a,b個數(shù)相等，且大于等于1。所以可以用產(chǎn)生式：A∷=aAb|ab

又因?yàn)閙可以為0,所以S::=AB改寫為S::=AB|A;

又由于A∷=aAb|ab，則對B容易看出B∷=cB|c ∴ S∷=AB|A S∷=AB A∷=aAb|ab 或者： A∷=aAb|ab B∷=cB|c B∷=cB|c|ε第三十一頁，共九十三頁，編輯于2023年，星期六例：設(shè)字母表∑＝{a,b},試設(shè)計一個文法，描述語言L＝{a,b|n≥1}解：分析語言由怎樣的符號串組成。 當(dāng)n=1時，L={aa,bb}

當(dāng)n=2時，L={aaaa,bbbb}

當(dāng)n=3時，L={aaaaaa,bbbbbb} … L={aa,bb,aaaa,bbbb,aaaaaa,bbbbbb,…}即：語言由偶數(shù)個a和偶數(shù)個b的符號串組成。所以，描述語言的文法：G[A]: A∷=aa|aaB|bb|bbD B∷=aa|aaB D∷=bb|bbD2n2n第三十二頁，共九十三頁，編輯于2023年，星期六可以寫出另一個文法：G1[A]: A∷=B|D B∷=aa|aBa D∷=bb|bDb可見，對于給定語言，描述該語言的文法不是唯一的。注：①描述一個語言的文法不是唯一的 ②若不同的文法產(chǎn)生相同的語言，則稱這些文法是等價的。第三十三頁，共九十三頁，編輯于2023年，星期六例：設(shè)有文法G1={VN,VT,P,A}其中： VN={A} VT={a,b} P={A::=ab}顯然： L(G1)={ab}文法 G2={VN,VT,P,A}其中： VN={A,B} VT={a,b} P={A::=Bb,B::=a}顯然： L(G2,)={ab}即：L(G1)=L(G2)，且G1=G2③若語言在語法上等價，并不一定意味著語義上等價。第三十四頁，共九十三頁，編輯于2023年，星期六例：G3[S]和G4[S]它們的VN和VT相同：

VN={S,A},VT={a,b,c}而,G3[S]的P為：

S::=A|S-A A::=a|b|c G4[S]的P為：

S::=A|A-S A::=a|b|c顯然：G3[S]和G4[S]等價（語法），因?yàn)樗鼈兌籍a(chǎn)生相同的句子：

{a,b,c,a-b-c,a-b-b-c,…}但：句子的含義（語義）不一定相同：例如：由G3[S]推導(dǎo)出的句子：a-b-c其含義為(a-b)-c

由G4[S]推導(dǎo)出的句子：a-b-c其含義為a-(b-c)第三十五頁，共九十三頁，編輯于2023年，星期六④文法應(yīng)該能準(zhǔn)確地描述語言，不能擴(kuò)大或縮小。例：設(shè)計一個表示所有標(biāo)識符的文法。解：分析：標(biāo)識符：字母|字母開頭的字母數(shù)字串,用B表示標(biāo)識符；L-字母；D-數(shù)字：則G[B]的產(chǎn)生式P: B::=L|BL|BD L::=a|b|c|…|x|y|z D::=0|1|2|…|9 ……可以表示a1b2c3第三十六頁，共九十三頁，編輯于2023年，星期六若將產(chǎn)生式設(shè)計成P1：

B::=L|BD L::=a|b|c|…|x|y|z D::=0|1|2|…|9 表示：字母開頭，后面全是數(shù)字：abc1， 不能表示a1b2c3顯然：P1縮小了標(biāo)識符的表示，比P描述的范圍縮小了若將產(chǎn)生式設(shè)計成P2：

B::=L|BL|BD|D L::=a|b|c|…|x|y|z D::=0|1|2|…|9 顯然:P2也不能準(zhǔn)確地描述，擴(kuò)大了P的描述范圍第三十七頁，共九十三頁，編輯于2023年，星期六§3與語法分析有關(guān)的概念

一、短語、簡單短語與句柄短語：設(shè)有文法G[S]，W=αβδ是G的一個句型。若有識別符號S=>＊αAδ,且A=>+β,則稱β是相對非終結(jié)符A的句型w的短語。 特別，如果上式A=>+β為：

A=>β

則稱β為句型w的簡單短語（直接短語）第三十八頁，共九十三頁，編輯于2023年，星期六例：設(shè)有文法G=({S,A,B},{a,b},P,S)其中P為：1.S::=AB2.A::=Aa3.A::=bB4.B::=a5.B::=Sb試求句型baSb,bBABb和baabaab全部短語，簡單短語。解：先討論句型w=baSb,其中子串b,a,S,ba,aS,Sb,baS,aSb.是句型w的短語嗎？ 根據(jù)短語定義，可由句型的推導(dǎo)中找到全部短語及簡單短語。最左推導(dǎo)：第三十九頁，共九十三頁，編輯于2023年，星期六由此可見，下式成立：①∵S=>*S,且S=>+baSb∴baSb是短語(句型本身是短語)(注意:主要求異于句型本身的短語). ②又∵

S=>*AB,且B=>Sb∴句型baSb中子串Sb也該句型（相對于B）的短語,且是簡單短語。③又∵

S=>*bBSb,且B=>a∴句型baSb中子串a(chǎn)也該句型（相對于B）的短語,且是簡單短語。④又∵

S=>*ASb,且A=>+ba∴句型baSb中子串ba也該句型（相對于A）的短語.注:短語是句型中的子串,在推導(dǎo)中不是句型中的子串不能作短語。如:S=>*ASb,A=>bB;則由于bB不是句型baSb中子串,所以他不是該句型的短語.第四十頁，共九十三頁，編輯于2023年，星期六∴sb，a，ba是句型baSb異于自身的短語(句型本身是短語),其中Sb,a是簡單短語。最右推導(dǎo)：同樣可求出同上的該句型的短語,同學(xué)們可自求.

可用同樣的方法分析句型bBABb和baabaab的全部短語和簡單短語（略）同學(xué)們也可自求。句柄：句型的最左簡單短語特征：句柄至少是簡單短語（某規(guī)則的右部），且為最左簡單短語（具有最左性）。例如：上例中a是最左簡單短語――句柄。第四十一頁，共九十三頁，編輯于2023年，星期六注:短語、簡單短語與句柄的關(guān)系:

●它們都是針對某個句型而言的,離開了句型來談短語、簡單短語與句柄,是毫無意義的.

●句柄一定是簡單短語和短語,反之不成立.

●簡單短語和句柄一定是某個產(chǎn)生式的右部符號串,短語不是(他作為我們尋找和判斷句型的簡單短語的依據(jù));但文法中產(chǎn)生式的右部符號串不見得都是簡單短語或句柄.二、最右（左）推導(dǎo)，規(guī)范推導(dǎo)和規(guī)范規(guī)約，規(guī)范句型(1)最右（左）推導(dǎo)：在推導(dǎo)過程中，任何一步α=>β都是對α中最右（左）非終結(jié)符進(jìn)行替換。稱為最右（左）推導(dǎo)。特別：最右推導(dǎo)稱為規(guī)范推導(dǎo)。得到的句型稱為規(guī)范句型。第四十二頁，共九十三頁，編輯于2023年，星期六例：設(shè)有文法G的規(guī)則集P為：

S::=AB A::=Aa|bB B::=a|Sb給出babaab的最右（左）推導(dǎo)解：最右推導(dǎo)：

S=>AB=>ASb=>AABb=>AAab=>AbBab=>Abaab=>bBbaab=>babaab規(guī)范推導(dǎo)。最左推導(dǎo)：S=>AB=>bBB=>baB=>baSb=>baABb=>babBBb=>babaBb=>babaab忽左忽右推導(dǎo)：第四十三頁，共九十三頁，編輯于2023年，星期六歸約：將句型中某一個子串用一個非終結(jié)符替換的過程。 若有A::=α,則xAy=>xαy，有：

xαy=>xAy……規(guī)約(2)規(guī)范歸約（又稱最左規(guī)約）：規(guī)范推導(dǎo)（最右推導(dǎo)）的逆過程。例：G[N1]: N1::=N N::=ND|D D::=0|1|2

最右推導(dǎo)：N1=>N=>ND=>N2=>D2=>12

最左規(guī)約：

12=>D2=>N2=>ND=>N=>N1第四十四頁，共九十三頁，編輯于2023年，星期六三、文法的遞歸1．遞歸規(guī)則若文法中有形如規(guī)則:A::=A…，稱為規(guī)則左遞歸。若文法中有形如規(guī)則:A::=…A，稱為規(guī)則右遞歸 。若文法中有形如規(guī)則:A::=…A…，稱為規(guī)則遞歸。（規(guī)則遞歸稱為直接遞歸）２．文法的遞歸性如果有推導(dǎo)A=>+A…，稱文法左遞歸如果有推導(dǎo)A=>+…A，稱文法右遞歸 如果有推導(dǎo)A=>+…A…，稱文法遞歸（文法遞歸稱為間接遞歸）第四十五頁，共九十三頁，編輯于2023年，星期六例：G[N1]: N1::=N N::=ND（規(guī)則左遞歸：直接遞歸）例：G[U]: U::=Vx V::=Uy|a∵U=>Vx=>Uyx (左遞歸文法:間接遞歸)

G[U]的規(guī)則中無規(guī)則左遞歸，但在推導(dǎo)過程中存在左遞歸，所以G[U]是左遞歸文法。作用：用遞歸規(guī)則可以定義無窮集合的語言。例：G[A]:

A::=B

B::=D|DD|DDD…，

D::=0|1|2|…結(jié)論：若語言為無窮集合，描述語言的文法一定是遞歸的?？捎肁::=AD替代第四十六頁，共九十三頁，編輯于2023年，星期六四、語法樹與文法的二義性句型的語法樹(1)作用：直觀地求出一個句型的短語，簡單短語和句柄。直觀地表示一個句型（或句子）的推導(dǎo)或歸約過程，即它是語法分析的工具?？梢耘袛嘁粋€文法的二義性問題。第四十七頁，共九十三頁，編輯于2023年，星期六(2)句型推導(dǎo)的語法樹表示用樹型結(jié)構(gòu)直觀地表示一個句型的推導(dǎo)過程，稱為該句型的一棵語法樹（又稱推導(dǎo)樹）語法樹的構(gòu)成：樹的根為文法的識別符號；樹的中間結(jié)點(diǎn)是文法的非終結(jié)符；葉子結(jié)點(diǎn)為文法的終結(jié)符號或非終結(jié)符號。若一個標(biāo)記為U的結(jié)點(diǎn)，它有標(biāo)記依次為x1x2x3……xn的直接后繼結(jié)點(diǎn)，即U::=x1x2x3……xn必定是文法G的一條規(guī)則。一個句型的推導(dǎo)過程用語法樹表示：第四十八頁，共九十三頁，編輯于2023年，星期六例：設(shè)有文法G[E]：

E::=E+T|E-T|T T::=T*F|T/F|F F::=(E)|i根據(jù)推導(dǎo)，畫出句型（T+I)＊i-F的語法樹：最右推導(dǎo)：E=>E-T=>E-F=>T-F =>T*F-F=>T*i-F=>F*i-F=>(E)*i-F =>(E+T)*i-F =>(E+F)*i-F =>(E+i)*i-F =>(T+i)*i-F第四十九頁，共九十三頁，編輯于2023年，星期六第五十頁，共九十三頁，編輯于2023年，星期六最左推導(dǎo)：從左向右畫子樹。子樹：由某一結(jié)點(diǎn)連同所有分支組成的部分。簡單子樹：包括葉子在內(nèi)的單層子樹。(3)語法樹中的短語，簡單短語和句柄的概念短語：子樹的末端結(jié)點(diǎn)形成的符號串是相對子樹根的短語。簡單短語：簡單子樹末端結(jié)點(diǎn)形成的符號串是相對于簡單子樹根的簡單短語。句柄：最左簡單子樹的末端結(jié)點(diǎn)形成的符號串是句柄。第五十一頁，共九十三頁，編輯于2023年，星期六例：設(shè)有文法G[E]：

E::=E+T|E-T|T T::=T*F|T/F|F F::=(E)|i求(T+i)*i–F的短語，簡單短語和句柄。

(T+i)*i–F為句型的相對根E的短語。

(T+i)*i為句型的相對于以T為根的子樹的短語。

(T+i)為句型的相對于以F為根的子樹的短語。

T+i為句型的相對于以E為根的子樹的短語。

T為句型的相對于以E為根的子樹的短語，且為簡單短語。第一個i為句型的相對于以F為根的子樹的短語，且為簡單短語。第二個i為句型的相對于以F為根的子樹的短語，且為簡單短語。F為句型的相對于以T為根的子樹的短語，且為簡單短語。在四個簡單短語T，i，i，F(xiàn)中，T為句型的句柄第五十二頁，共九十三頁，編輯于2023年，星期六例：設(shè)有文法G[S]： S::=(T)|a|ε T::=T,S|S求句子（a,(a,a)）最右推導(dǎo)的逆過程（最左規(guī)約）每一步的句柄。——最右推導(dǎo)：S =>(T) 句柄:（T）

=>(T,S) 句柄:T,S =>(T,(T)) 句柄:(T) =>(T,(T,S))句柄:T,S =>(T,(T,a))句柄:第三個a =>(T,(S,a)) 句柄:S =>(T,(a,a)) 句柄:第二個a =>(S,(a,a)) 句柄:S =>(a,(a,a)) 句柄:第一個a第五十三頁，共九十三頁，編輯于2023年，星期六第五十四頁，共九十三頁，編輯于2023年，星期六文法的二義性所謂文法的二義性是指文法存在的某個句子對應(yīng)兩棵不同的語法樹（或說存在兩個不同的最左（右）推導(dǎo)）。例：文法G[E]：E::=E+E|E*E|(E)|i

句子i*i+i有兩個不同的語法樹（最左推導(dǎo)）

E=>E+E=>E*E+E =>i*E+E =>i*i+E =>i*i+i第五十五頁，共九十三頁，編輯于2023年，星期六E=>E*E=>i*E =>i*E+E =>i*i+E =>i*i+i∴G[E]具有二義性文法的二義性會導(dǎo)致對二義性文法的句子結(jié)構(gòu)產(chǎn)生多種不同的理解，造成語法分析和語義理解的不確定性。希望描述語言的文法是無二義性的。第五十六頁，共九十三頁，編輯于2023年，星期六文法二義性的消除(1)

不改變文法中原有的語法規(guī)則，僅加進(jìn)一些語法的非形式規(guī)定。例如，對于上例文法G[E],不改變已有的4條規(guī)則，僅加入運(yùn)算符的優(yōu)先順序和結(jié)合規(guī)則；即*優(yōu)先于+；+,*服從左結(jié)合。這樣，句子i*i+i只有唯一的一棵語法樹（如上例的第一個圖）。(2)

改寫文法。把排除二義性的規(guī)則合并到原文法中，構(gòu)造一個等價的無二義性的文法。第五十七頁，共九十三頁，編輯于2023年，星期六例如，對于上例文法G[E],將運(yùn)算符的優(yōu)先順序及結(jié)合規(guī)則（*優(yōu)先于+；+,*服從左結(jié)合）加到原文法中：

E::=E+T|T T::=T*F|F F::=(E)|i

則句子i*i+i只有唯一的語法樹可見：對于有二義性文法描述的語言，有時可以找到等價的無二義性文法來描述它。第五十八頁，共九十三頁，編輯于2023年，星期六例：某語言的條件語句的文法G為：

S::=ifbS|ifbSelseS|A(A為其它語句)證明G具有二義性，并消除之。分析：該文法的句子ifbifbAelseA對應(yīng)的兩棵不同的語法樹

第五十九頁，共九十三頁，編輯于2023年，星期六所以G是具有二義性的文法。消除二義性：

(1).不改變已有規(guī)則，僅加入一項(xiàng)非形式語法規(guī)定：else與前面最接近的if配對。這時句子ifbifbAelseA只唯一對應(yīng)語法樹(a).(2).改造文法G為G’:S::=S1|S2S1::=ifbS1elseS1|AS2::=ifbS|ifbS1elseS2

第六十頁，共九十三頁，編輯于2023年，星期六注：文法的二義性和語言的二義性是兩個不同的概念。通常只說文法的二義性，而且不說語言的二義性，因?yàn)槊枋稣Z言的文法不唯一，可能存在一個文法G有二義性，一個文法G’無二義性：使L(G)=L(G’)如果語言是二義性的，則它不存在無二義性的文法，這樣的語言稱為先天二義性語言。如：L={abc|i=j或j＝k,i,j,k≥1}便是這種語言。已證明，不存在一個算法，它能在有限步驟內(nèi)確切地判定任意給定一個上下文無關(guān)文法是否為二義性文法，或它是否會產(chǎn)生一個先天二義性的上下文無關(guān)語言。ijk第六十一頁，共九十三頁，編輯于2023年，星期六§4文法與語言的分類分類的依據(jù)：將文法中的規(guī)則施加不同的限制。文法被劃分為4類：0～3型文法一、0型文法（短語文法） 若文法G的規(guī)則式具有形式：α::=β(其中α∈(VN∪VT)+,β∈(VN∪VT)*)即α，β都是符號串對它們沒有作任何限制。（也可以|α|>|β|）由0型文法產(chǎn)生的語言稱為0型語言0型文法的能力相當(dāng)于圖靈機(jī)。第六十二頁，共九十三頁，編輯于2023年，星期六例：有產(chǎn)生式P：

S::=0AB 1B::=0 B::=SA|01 A1::=SB1 A0::=S0B|α|>|β|為0型文法該文法推不出任何句子：L={}第六十三頁，共九十三頁，編輯于2023年，星期六二、1型文法（上下文有關(guān)文法）若文法G中規(guī)則呈現(xiàn)下列的形式：

αAβ::=αuβ其中：A∈VN，u∈(VN∪VT)+,α,β∈(VN∪VT)*則稱G為1型文法，所產(chǎn)生的語言為1型語言。 由于利用規(guī)則將A替換為u時，必須考慮A在上下文α…β中出現(xiàn)的情況，即與上下文有關(guān)，故又稱為下文有關(guān)文法。特點(diǎn)：每個規(guī)則式：|左邊|≤|右邊|；規(guī)則右部符號個數(shù)至少與左部符號個數(shù)一樣多。第六十四頁，共九十三頁，編輯于2023年，星期六例：設(shè)有G=(VN

，VT

，P，S) VN={S,B,C} VT={a,b,c} P: S::=aSBC S::=aBC CB::=BC aB::=ab bB::=bb bC::=bc cC::=cc這是一個1型文法，它描述了如下語言

L(G)={anbncn|n≥1}第六十五頁，共九十三頁，編輯于2023年，星期六三、2型文法（上下文無關(guān)文法） 若文法G中規(guī)則呈現(xiàn)如下形式：

A::=β

其中，A∈VN，β∈（VN∪VT）* 則稱G為2型文法，由它產(chǎn)生的語言稱2型語言。 由于利用規(guī)則將A替換成β時與其上下文無關(guān)，即與A在上下文出現(xiàn)的情況無關(guān)，所以又稱這種文法為上下文無關(guān)文法。例：文法G的產(chǎn)生式P：

E::=E+E|E*E|(E)|i

屬于2型文法。特點(diǎn)：2型文法產(chǎn)生式的左部是單個的非終結(jié)符，右部為終結(jié)符和非終結(jié)符組成的符號串。注：上下文無關(guān)文法可以描述當(dāng)今的程序語言第六十六頁，共九十三頁，編輯于2023年，星期六四、3型文法（正規(guī)文法） 如果對2型文法的產(chǎn)生式作進(jìn)一步的限制，限制產(chǎn)生式的右部是單一終結(jié)符或單一終結(jié)符和單一非終結(jié)符組成。若文法G中的規(guī)則式，呈現(xiàn)如下形式： 右線性文法 A::=aB A::=a

或左線性文法 A::=Ba A::=a其中：A，B∈VN，a∈VT

稱G為3型文法?；蚍Q正規(guī)（正則）文法，由它產(chǎn)生的語言為3型語言或正規(guī)語言。＊+第六十七頁，共九十三頁，編輯于2023年，星期六例：設(shè)有G=(V,V,P,S) P: S::=A0|B1 A::=0|1 B::=0|1左線性文法注：①文法類型是由產(chǎn)生式的形式來劃分：NT第六十八頁，共九十三頁，編輯于2023年，星期六即：G0G1G2G3表格：文法類型與產(chǎn)生式文法類型產(chǎn)生式限制0α::=β(|α|≠0,|α|>|β|)：無限制文法1α::=β(1≤|α|≤|β|):上下文有關(guān)文法2A::=δ(δ∈（VN∪VT)+):上下文無關(guān)文法3A::=aA::=aA::=aB或A::=Ba:正則（規(guī)）文法或左（右）線性文法第六十九頁，共九十三頁，編輯于2023年，星期六②文法的分類對于程序設(shè)計語言的編譯程序有重要的意義。程序語言的詞法規(guī)則屬于正則文法編譯程序詞法掃描器采用正則文法識別技術(shù)。程序語言的語法和語義部分的規(guī)則屬于上下文有關(guān)文法。但考慮高功效而采用上下文無關(guān)文法定義語法編譯程序語法分析器采用上下文文法識別技術(shù)。程序語言的詞法由正則文法描述。第七十頁，共九十三頁，編輯于2023年，星期六程序語言中與局部語法有關(guān)的規(guī)則屬于上下文無關(guān)文法。程序語言中全局的語法與語義有關(guān)的部分屬于上下文有關(guān)文法。（如標(biāo)識符類型匹配問題（說明部分與語句部分）。過程調(diào)用中實(shí)參與形參要求一致的問題等等）第七十一頁，共九十三頁，編輯于2023年，星期六§5文法的實(shí)用限制

在實(shí)際使用中，對文法要作一些假定或限制。例如限制文法不含有有害規(guī)則或多余的規(guī)則。一、文法中不能含有有害規(guī)則U::=U這樣的規(guī)則顯然沒有必要，而且會引起二義性。例如，文法G[S]:S::=0S1|01是無二義性的，若將規(guī)則寫成：S::=0S1|01|S則文法G不再是無二義性的。就句子0011而言，可畫出多棵語法樹。第七十二頁，共九十三頁，編輯于2023年，星期六二、文法中不能含有多余的規(guī)則文法的規(guī)則中不含有無用的非終結(jié)符和不可到達(dá)的符號。1.無用的非終結(jié)符號（不可終止符號） 如果從文法中某個非終結(jié)符推不出終結(jié)符號串，則稱該非終結(jié)符號為無用的非終結(jié)符2.不可到達(dá)的符號 如果文法規(guī)則中的一個非終結(jié)符（不是識別符號），不出現(xiàn)在文法的任何一條產(chǎn)生式的右部，則稱該非終結(jié)符為不可到達(dá)的符號.第七十三頁，共九十三頁，編輯于2023年，星期六例：已知文法G=(VN，VT，P，Z)

其中， VN={Z,A,B,C,D},VT={e,f} P:Z::=Be A::=Ae|e B::=Ce|Af C::=Cf D::=f C為無用的非終結(jié)符，因?yàn)镃在推導(dǎo)中沒有終結(jié)符號替換。∴C::=cf和B::=Ce多余應(yīng)該刪去。第七十四頁，共九十三頁，編輯于2023年，星期六

D為不可到達(dá)的符號，即D::=f在推導(dǎo)中不起作用，應(yīng)該刪去。刪除多余的規(guī)則后的文法為：

Z::=Be A::=Ae|e B::=Af第七十五頁，共九十三頁，編輯于2023年，星期六文法中不含多余規(guī)則的充要條件：U(U∈VN)必須出現(xiàn)在某個推導(dǎo)的句型中，即：Z=>＊x∪y。（U為文法的非終結(jié)符）能從U推出終結(jié)符號串，即：U=>+t(t∈VT)

滿足上述條件的文法稱為壓縮過的或化簡了的。對文法的限制還有：文法中不含有左遞歸規(guī)則U::=U…。（消除左遞歸在后面會講到）對于上下文無關(guān)文法，限制U::=ε，即不含有空規(guī)則。（可以變換消除）等等第七十六頁，共九十三頁，編輯于2023年，星期六§6小結(jié)本章主要解決的問題：已知文法，確定該文法描述的語言已知語言，設(shè)計描述該語言的文法求句型的短語，簡單短語及句柄文法二義性的判斷第七十七頁，共九十三頁，編輯于2023年，星期六一、已知文法，確定該文法描述的語言1.語言的定義：文法G產(chǎn)生句子的全體。即L(G[S])={x|S=>+x,且x∈VT*}2.語言的描述：用自然語言：L={x|x∈{a,b}+,且x中a，b個數(shù)相同}用式子：L={a2nbb|n≥0}用正規(guī)式：L={bna|n≥0}，可用：L=b*a來描述。3.求法：根據(jù)給定文法，從文法的識別符號開始，推導(dǎo)出所有的句子，然后歸納寫出語言描述的三種形式之一。第七十八頁，共九十三頁，編輯于2023年，星期六例：有如下文法G[S]：

S::=AB A::=aAb|ab B::=BC|ε求：L(G[S])=?解：S=>AB=>abB=>ab S=>AB=>abB=>abBc=>abc S=>AB=>aAbB=>aabbB=>aabb S=>AB=>aAbB=>aabbB=>aabbBC=>aabbc ……∴L(G[S])={anbnc|n≥1,m≥0}m第七十九頁，共九十三頁，編輯于2023年，星期六例：已知文法G[S]為：

S::=dAB A::=aA|a B::=Bb|εG[S]產(chǎn)生的語言是什么？G[S]能否改寫為等價的正規(guī)文法？解：首先分析G[S]產(chǎn)生的語言：語言的句子都是d開頭，后跟a或b，且a，b個數(shù)不等。

L(G[S])={danbm|n≥1,m≥0}

根據(jù)語言的特點(diǎn)：a,b的個數(shù)n與m沒有相互制約的關(guān)系，所以將an與bm分別構(gòu)造，得到正規(guī)文法：G[S]：S::=dA A::=aA|aB|a B::=bB|b第八十頁，共九十三頁，編輯于2023年，星期六二、已知語言，設(shè)計描述該語言的文法文法的形式定義：四元組G[S]=(VN,VT,P,S)，主要求產(chǎn)生式P。分析已知語言句子的結(jié)構(gòu)特征，設(shè)計相應(yīng)的產(chǎn)生式，但求出的文法不唯一。設(shè)計出的文法必須能準(zhǔn)確地定義已知的語言，不能超出或縮小所定義的語言范圍。若語言是句子的無窮集合，則設(shè)計的文法一定是遞歸的。第八十一頁，共九十三頁，編輯于2023年，星期六例：已知L={x|x∈{a,b,c}*,且x中符號的排列是對稱的。（例如：aabcbaa或aabbaa等）}

試寫出產(chǎn)生該語言的文法。解：句子x中符號有多個，所以有遞歸產(chǎn)生式存在。又因?yàn)榫渥觴中符號是對稱的，保證對稱的推導(dǎo)出每個符號就可以了。

G[Z]:Z::=aZa|bZb|cZc|a|b|c|ε例：給出描述：L={a2m+1bm+1|m≥0}∪{a2mbm+2|m≥0}的文法。解：將句子的描述變形：

a2mabbm和a2mbbbm發(fā)現(xiàn)句子中前后的a和b的個數(shù)有倍數(shù)關(guān)系于是：G[Z]:Z::=aaZb|ab|bb第八十二頁，共九十三頁，編輯于2023年，星期六例：寫一文法，使其語言是偶整數(shù)的集合（不允許0開頭，且不考慮帶符號數(shù)）解：根據(jù)題意，將偶整數(shù)結(jié)構(gòu)劃分如圖所示的三個部分：最高位允許1～9，用非終結(jié)符B表示中間位允許任意多位數(shù)字0～9，每位用非終結(jié)符D表示最低位只允許出現(xiàn)0，2，4，6，8偶數(shù)，用A表示。第八十三頁，共九十三頁，編輯于2023年，星期六 由于中間部分可以出現(xiàn)任意位，所以引入一個非終結(jié)符M，它包括最高位和中間位。所求文法G[N]:N::=A|MA M::=B|MD A::=0|2|4|6|8 B::=1|2||3|4|5|6|7|8|9 D::=0|B類似問題：寫出帶符號