形式語言與文法

形式語言與文法第一頁，共九十三頁，2022年，8月28日§1.符號(hào)串

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

1,字母表∑

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

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

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

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

字母表中至少有一個(gè)元素.第二頁，共九十三頁，2022年，8月28日2.符號(hào)(字符)

定義：字母表中的元素.

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

3.符號(hào)串定義：字母表中的符號(hào)組成的有窮序列.

例:∑={a,b,c}

符號(hào):a,b,c

符號(hào)串:a,b,c,ab,ac,aa,ba,ca,abc,…

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

…,01000,…第三頁，共九十三頁，2022年，8月28日

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

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

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

定義：設(shè)x和y為符號(hào)串，則xy被稱為x與y的連接．設(shè)x＝abc，y＝10a則xy＝abc10a；yx＝10aabc第四頁，共九十三頁，2022年，8月28日２．符號(hào)串的方冪設(shè)有符號(hào)串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第五頁，共九十三頁，2022年，8月28日３．符號(hào)串集合的乘積

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

注：{ε

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

注:ε

不屬于，即空符號(hào)串并不屬于空集

第六頁，共九十三頁，2022年，8月28日4.符號(hào)串集合的方冪

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

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

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

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

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

(A共有2=8個(gè)長度為3的元素)012322nn－1n－101232233第七頁，共九十三頁，2022年，8月28日5.符號(hào)串集合的正閉包A和閉包A⑴.符號(hào)串集合的正閉包A

設(shè)A為符號(hào)串集合,則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)成的所有符號(hào)串.⑵.符號(hào)串集合A的閉包A.A=AUAUAU…UAU……(A=AUA)

即A={ε}UA=AU{ε}(A=A－{ε})＋＊＋＋＋123n＋＋＊＊012n＊0＋＊＋＋＋＊+第八頁，共九十三頁，2022年，8月28日例設(shè)A={a,b}則

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

顯然:對(duì)于所有的A,有ε

∈A＊＊＊第九頁，共九十三頁，2022年，8月28日§2.文法和語言的形式定義一.文法與語言的關(guān)系

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

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

●語言的描述

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

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

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

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

<謂語>∷=<動(dòng)詞><直接賓語>(不加<>表示終結(jié)符)第十一頁，共九十三頁，2022年，8月28日

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

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

我<謂語>

我<動(dòng)詞><直接賓語>

我是<直接賓語>

我是<名詞>

我是大學(xué)生利用上列文法:可以產(chǎn)生的句子:我學(xué)習(xí)英語,他學(xué)習(xí),語,他是工人,….(很多句子)第十二頁，共九十三頁，2022年，8月28日

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

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

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

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

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

其中:V是文法規(guī)則式中的非終結(jié)符號(hào)集.V是文法規(guī)則式中的終結(jié)符號(hào)集.＋＋NTNT﹡第十四頁，共九十三頁，2022年，8月28日

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

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

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

G[S]:S::=0S1 S::=01NT第十六頁，共九十三頁，2022年，8月28日例：G[<標(biāo)識(shí)符>]:

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

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

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

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

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

}第十七頁，共九十三頁，2022年，8月28日3.推導(dǎo)有了文法，怎樣由文法推導(dǎo)出與該文法相應(yīng)的語言？為此引入了“推導(dǎo)”等概念。直接推導(dǎo)設(shè)x,y是V*中任意符號(hào)串，若用一次規(guī)則式可以從x推出y，則稱y是x的直接推導(dǎo)，記為：xy。（或稱符號(hào)串x直接產(chǎn)生了符號(hào)串y，或稱y直接歸約到x）第十八頁，共九十三頁，2022年，8月28日例：設(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第十九頁，共九十三頁，2022年，8月28日推導(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）＋第二十頁，共九十三頁，2022年，8月28日廣義推導(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)＊包涵＋包涵第二十一頁，共九十三頁，2022年，8月28日4.句型和句子設(shè)有文法G[S],若有S＊x,則稱符號(hào)串x為文法G[S]的句型。換句話說：凡是由識(shí)別符號(hào)推導(dǎo)出來的任意符號(hào)串稱為句型。句子：僅有終結(jié)符號(hào)組成的句型稱為句子。區(qū)別：符號(hào)串x∈(VN∪VT)*;x稱為句型，

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

E=>(E) =>(E+E) =>(E*E+E) =>(i*E+E) =>(i*i+E) =>(i*i+i)即：E=>＊(i*i+i)所以,符號(hào)串(i*i+i)是文法G[E]的一個(gè)句子。第二十四頁，共九十三頁，2022年，8月28日三、語言的形式定義：定義：由文法G[S]產(chǎn)生的所有句子的集合。即：

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

反之,屬于V*的符號(hào)串x不一定屬于L(G)。TTTT第二十五頁，共九十三頁，2022年，8月28日例：已知文法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‘的真子集。＋＋第二十六頁，共九十三頁，2022年，8月28日例：已知文法：G[S]:S∷=0S|1S|ε,求L(G)=?解：L(G[S])={ε,0,1,01,11,00,10,…}

={x|x∈{0,1}*}第二十七頁，共九十三頁，2022年，8月28日例：已知： 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個(gè)數(shù)相同}

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

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

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

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

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

P：

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

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

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

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

當(dāng)n=3時(shí)，L={aaaaaa,bbbbbb} … L={aa,bb,aaaa,bbbb,aaaaaa,bbbbbb,…}即：語言由偶數(shù)個(gè)a和偶數(shù)個(gè)b的符號(hào)串組成。所以，描述語言的文法：G[A]: A∷=aa|aaB|bb|bbD B∷=aa|aaB D∷=bb|bbD2n2n第三十二頁，共九十三頁，2022年，8月28日可以寫出另一個(gè)文法：G1[A]: A∷=B|D B∷=aa|aBa D∷=bb|bDb可見，對(duì)于給定語言，描述該語言的文法不是唯一的。注：①描述一個(gè)語言的文法不是唯一的 ②若不同的文法產(chǎn)生相同的語言，則稱這些文法是等價(jià)的。第三十三頁，共九十三頁，2022年，8月28日例：設(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③若語言在語法上等價(jià)，并不一定意味著語義上等價(jià)。第三十四頁，共九十三頁，2022年，8月28日例：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]等價(jià)（語法），因?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)第三十五頁，共九十三頁，2022年，8月28日④文法應(yīng)該能準(zhǔn)確地描述語言，不能擴(kuò)大或縮小。例：設(shè)計(jì)一個(gè)表示所有標(biāo)識(shí)符的文法。解：分析：標(biāo)識(shí)符：字母|字母開頭的字母數(shù)字串,用B表示標(biāo)識(shí)符；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第三十六頁，共九十三頁，2022年，8月28日若將產(chǎn)生式設(shè)計(jì)成P1：

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

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

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

A=>β

則稱β為句型w的簡單短語（直接短語）第三十八頁，共九十三頁，2022年，8月28日例：設(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)：第三十九頁，共九十三頁，2022年，8月28日由此可見，下式成立：①∵S=>*S,且S=>+baSb∴baSb是短語(句型本身是短語)(注意:主要求異于句型本身的短語). ②又∵

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

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

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

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

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

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

●簡單短語和句柄一定是某個(gè)產(chǎn)生式的右部符號(hào)串,短語不是(他作為我們尋找和判斷句型的簡單短語的依據(jù));但文法中產(chǎn)生式的右部符號(hào)串不見得都是簡單短語或句柄.二、最右（左）推導(dǎo)，規(guī)范推導(dǎo)和規(guī)范規(guī)約，規(guī)范句型(1)最右（左）推導(dǎo)：在推導(dǎo)過程中，任何一步α=>β都是對(duì)α中最右（左）非終結(jié)符進(jìn)行替換。稱為最右（左）推導(dǎo)。特別：最右推導(dǎo)稱為規(guī)范推導(dǎo)。得到的句型稱為規(guī)范句型。第四十二頁，共九十三頁，2022年，8月28日例：設(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)：第四十三頁，共九十三頁，2022年，8月28日歸約：將句型中某一個(gè)子串用一個(gè)非終結(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第四十四頁，共九十三頁，2022年，8月28日三、文法的遞歸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…，稱文法遞歸（文法遞歸稱為間接遞歸）第四十五頁，共九十三頁，2022年，8月28日例：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替代第四十六頁，共九十三頁，2022年，8月28日四、語法樹與文法的二義性句型的語法樹(1)作用：直觀地求出一個(gè)句型的短語，簡單短語和句柄。直觀地表示一個(gè)句型（或句子）的推導(dǎo)或歸約過程，即它是語法分析的工具。可以判斷一個(gè)文法的二義性問題。第四十七頁，共九十三頁，2022年，8月28日(2)句型推導(dǎo)的語法樹表示用樹型結(jié)構(gòu)直觀地表示一個(gè)句型的推導(dǎo)過程，稱為該句型的一棵語法樹（又稱推導(dǎo)樹）語法樹的構(gòu)成：樹的根為文法的識(shí)別符號(hào)；樹的中間結(jié)點(diǎn)是文法的非終結(jié)符；葉子結(jié)點(diǎn)為文法的終結(jié)符號(hào)或非終結(jié)符號(hào)。若一個(gè)標(biāo)記為U的結(jié)點(diǎn)，它有標(biāo)記依次為x1x2x3……xn的直接后繼結(jié)點(diǎn)，即U::=x1x2x3……xn必定是文法G的一條規(guī)則。一個(gè)句型的推導(dǎo)過程用語法樹表示：第四十八頁，共九十三頁，2022年，8月28日例：設(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第四十九頁，共九十三頁，2022年，8月28日第五十頁，共九十三頁，2022年，8月28日最左推導(dǎo)：從左向右畫子樹。子樹：由某一結(jié)點(diǎn)連同所有分支組成的部分。簡單子樹：包括葉子在內(nèi)的單層子樹。(3)語法樹中的短語，簡單短語和句柄的概念短語：子樹的末端結(jié)點(diǎn)形成的符號(hào)串是相對(duì)子樹根的短語。簡單短語：簡單子樹末端結(jié)點(diǎn)形成的符號(hào)串是相對(duì)于簡單子樹根的簡單短語。句柄：最左簡單子樹的末端結(jié)點(diǎn)形成的符號(hào)串是句柄。第五十一頁，共九十三頁，2022年，8月28日例：設(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為句型的相對(duì)根E的短語。

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

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

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

T為句型的相對(duì)于以E為根的子樹的短語，且為簡單短語。第一個(gè)i為句型的相對(duì)于以F為根的子樹的短語，且為簡單短語。第二個(gè)i為句型的相對(duì)于以F為根的子樹的短語，且為簡單短語。F為句型的相對(duì)于以T為根的子樹的短語，且為簡單短語。在四個(gè)簡單短語T，i，i，F(xiàn)中，T為句型的句柄第五十二頁，共九十三頁，2022年，8月28日例：設(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))句柄:第三個(gè)a =>(T,(S,a)) 句柄:S =>(T,(a,a)) 句柄:第二個(gè)a =>(S,(a,a)) 句柄:S =>(a,(a,a)) 句柄:第一個(gè)a第五十三頁，共九十三頁，2022年，8月28日第五十四頁，共九十三頁，2022年，8月28日文法的二義性所謂文法的二義性是指文法存在的某個(gè)句子對(duì)應(yīng)兩棵不同的語法樹（或說存在兩個(gè)不同的最左（右）推導(dǎo)）。例：文法G[E]：E::=E+E|E*E|(E)|i

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

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

不改變文法中原有的語法規(guī)則，僅加進(jìn)一些語法的非形式規(guī)定。例如，對(duì)于上例文法G[E],不改變已有的4條規(guī)則，僅加入運(yùn)算符的優(yōu)先順序和結(jié)合規(guī)則；即*優(yōu)先于+；+,*服從左結(jié)合。這樣，句子i*i+i只有唯一的一棵語法樹（如上例的第一個(gè)圖）。(2)改寫文法。把排除二義性的規(guī)則合并到原文法中，構(gòu)造一個(gè)等價(jià)的無二義性的文法。第五十七頁，共九十三頁，2022年，8月28日例如，對(duì)于上例文法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只有唯一的語法樹可見：對(duì)于有二義性文法描述的語言，有時(shí)可以找到等價(jià)的無二義性文法來描述它。第五十八頁，共九十三頁，2022年，8月28日例：某語言的條件語句的文法G為：

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

第五十九頁，共九十三頁，2022年，8月28日所以G是具有二義性的文法。消除二義性：

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

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

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

αAβ::=αuβ其中：A∈VN，u∈(VN∪VT)+,α,β∈(VN∪VT)*則稱G為1型文法，所產(chǎn)生的語言為1型語言。 由于利用規(guī)則將A替換為u時(shí)，必須考慮A在上下文α…β中出現(xiàn)的情況，即與上下文有關(guān)，故又稱為下文有關(guān)文法。特點(diǎn)：每個(gè)規(guī)則式：|左邊|≤|右邊|；規(guī)則右部符號(hào)個(gè)數(shù)至少與左部符號(hào)個(gè)數(shù)一樣多。第六十四頁，共九十三頁，2022年，8月28日例：設(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這是一個(gè)1型文法，它描述了如下語言

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

A::=β

其中，A∈VN，β∈（VN∪VT）* 則稱G為2型文法，由它產(chǎn)生的語言稱2型語言。 由于利用規(guī)則將A替換成β時(shí)與其上下文無關(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)生式的左部是單個(gè)的非終結(jié)符，右部為終結(jié)符和非終結(jié)符組成的符號(hào)串。注：上下文無關(guān)文法可以描述當(dāng)今的程序語言第六十六頁，共九十三頁，2022年，8月28日四、3型文法（正規(guī)文法） 如果對(duì)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ī)語言。＊+第六十七頁，共九十三頁，2022年，8月28日例：設(shè)有G=(V,V,P,S) P: S::=A0|B1 A::=0|1 B::=0|1左線性文法注：①文法類型是由產(chǎn)生式的形式來劃分：NT第六十八頁，共九十三頁，2022年，8月28日即：G0G1G2G3表格：文法類型與產(chǎn)生式文法類型產(chǎn)生式限制0α::=β(|α|≠0,|α|>|β|)：無限制文法1α::=β(1≤|α|≤|β|):上下文有關(guān)文法2A::=δ(δ∈（VN∪VT)+):上下文無關(guān)文法3A::=aA::=aA::=aB或A::=Ba:正則（規(guī)）文法或左（右）線性文法第六十九頁，共九十三頁，2022年，8月28日②文法的分類對(duì)于程序設(shè)計(jì)語言的編譯程序有重要的意義。程序語言的詞法規(guī)則屬于正則文法編譯程序詞法掃描器采用正則文法識(shí)別技術(shù)。程序語言的語法和語義部分的規(guī)則屬于上下文有關(guān)文法。但考慮高功效而采用上下文無關(guān)文法定義語法編譯程序語法分析器采用上下文文法識(shí)別技術(shù)。程序語言的詞法由正則文法描述。第七十頁，共九十三頁，2022年，8月28日程序語言中與局部語法有關(guān)的規(guī)則屬于上下文無關(guān)文法。程序語言中全局的語法與語義有關(guān)的部分屬于上下文有關(guān)文法。（如標(biāo)識(shí)符類型匹配問題（說明部分與語句部分）。過程調(diào)用中實(shí)參與形參要求一致的問題等等）第七十一頁，共九十三頁，2022年，8月28日§5文法的實(shí)用限制

在實(shí)際使用中，對(duì)文法要作一些假定或限制。例如限制文法不含有有害規(guī)則或多余的規(guī)則。一、文法中不能含有有害規(guī)則U::=U這樣的規(guī)則顯然沒有必要，而且會(huì)引起二義性。例如，文法G[S]:S::=0S1|01是無二義性的，若將規(guī)則寫成：S::=0S1|01|S則文法G不再是無二義性的。就句子0011而言，可畫出多棵語法樹。第七十二頁，共九十三頁，2022年，8月28日二、文法中不能含有多余的規(guī)則文法的規(guī)則中不含有無用的非終結(jié)符和不可到達(dá)的符號(hào)。1.無用的非終結(jié)符號(hào)（不可終止符號(hào)） 如果從文法中某個(gè)非終結(jié)符推不出終結(jié)符號(hào)串，則稱該非終結(jié)符號(hào)為無用的非終結(jié)符2.不可到達(dá)的符號(hào) 如果文法規(guī)則中的一個(gè)非終結(jié)符（不是識(shí)別符號(hào)），不出現(xiàn)在文法的任何一條產(chǎn)生式的右部，則稱該非終結(jié)符為不可到達(dá)的符號(hào).第七十三頁，共九十三頁，2022年，8月28日例：已知文法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é)符號(hào)替換。∴C::=cf和B::=Ce多余應(yīng)該刪去。第七十四頁，共九十三頁，2022年，8月28日

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

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

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

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

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

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

試寫出產(chǎn)生該語言的文法。解：句子x中符號(hào)有多個(gè)，所以有遞歸產(chǎn)生式存在。又因?yàn)榫渥觴中符號(hào)是對(duì)稱的，保證對(duì)稱的推導(dǎo)出每個(gè)符號(hà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的個(gè)數(shù)有倍數(shù)關(guān)系于是：G[Z]:Z::=aaZb|ab|bb第八十二頁，共九十三頁，2022年，8月28日例：寫一文法，使其語言是偶整數(shù)的集合（不允許0開頭，且不考慮帶符號(hào)數(shù)）解：根據(jù)題意，將偶整數(shù)結(jié)構(gòu)劃分如圖所示的三個(gè)部分：最高位允許1～9，用非終結(jié)符B表示中間位允許任意多位數(shù)字0～9，每位用非終結(jié)符D表示最低位只允許出現(xiàn)0，2，4，6，8偶數(shù)，用A表示。第八十三頁，共九十三頁，2022年，8月28日 由于中間部分可以出現(xiàn)任意位，所以引入一個(gè)非終結(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類似問題：寫出帶符號(hào)