第三章文法和語言

第3章文法和語言3.1文法的直觀概念文法：描述語言的語法結(jié)構(gòu)的形式規(guī)則（即語法規(guī)則）。1）描述單詞單詞的組成規(guī)則 BNF范式、正規(guī)式2）描述語句 語句的組成規(guī)則BNF范式、語法圖3.1文法的直觀概念例如：判斷“我是大學(xué)生”是否為句子

文法如下：<句子>::=<主語><謂語><主語>::=<代詞>|<名詞><代詞>::=我|你|他<名詞>::=王明|大學(xué)生|工人|英語<謂語>::=<動(dòng)詞><直接賓語><動(dòng)詞>::=是|學(xué)習(xí)<直接賓語>::=<代詞>|<名詞>“我是大學(xué)生”的推導(dǎo)過程：<句子>-><主語><謂語>-><代詞><謂語>->我<謂語>->我<動(dòng)詞><直接賓語>->我是<直接賓語>我是<名詞>->

我是大學(xué)生

依次可以推導(dǎo)出句子“王明是大學(xué)生”、“我學(xué)習(xí)英語”等等文法作用（1）定義句子的結(jié)構(gòu)；（2）用適當(dāng)條數(shù)的規(guī)則把語言的全部句子描述出來，以有窮集合刻劃無窮集合。3.2符號(hào)和符號(hào)串一、基本概念1.字母表符號(hào)的非空有窮集合用符號(hào)Σ或V表示。例如：Σ={a，b，c}和V={0，1}都是字母表相當(dāng)于語言中的字符集2.符號(hào)語言中不可再分的基本單位3.符號(hào)串字母表中的符號(hào)組成的任何有窮序列。說明（1）符號(hào)的順序，如ab與ba不同；（2）符號(hào)串長度：符號(hào)串內(nèi)所含符號(hào)的個(gè)數(shù)其中不含任何符號(hào)的符號(hào)串稱為空符號(hào)串ε，長度|ε|＝03.2符號(hào)和符號(hào)串4.句子字母表上符合某種規(guī)則構(gòu)成的串包含單詞和語句5.語言句子的集合3.2符號(hào)和符號(hào)串二、符號(hào)串的計(jì)算1.符號(hào)串的連接設(shè)x和y是符號(hào)串，它們的連接xy是把y的符號(hào)寫在x的符號(hào)之后得到的符號(hào)串。例如：x=abc，y=def，則xy=abcdef2.符號(hào)串的方冪設(shè)x是符號(hào)串，把x自身連接n次得到的符號(hào)串z，即z=xx…xx，稱為符號(hào)串x的方冪，記作z=xn，即把符號(hào)串x重復(fù)地寫n次。例如：x0=ε，x1=x，x2=xx，x3=xxx…設(shè)x=ab則x3=ababab當(dāng)n>0時(shí)，xn＝xxn-1=xn-1x3.2符號(hào)和符號(hào)串三、符號(hào)串集合的運(yùn)算

連接（乘積）：設(shè)符號(hào)串集合A、B，則AB＝{xy|x∈A且y∈B}例如： A={a,b}，B={c,d}，則集合AB={ac,ad,bc,bd}{ε}A=A{ε}=A；一般而言，AB≠BA，但(AB)C=A(BC)注意：1)串集自身的連接稱為串集的方冪2）A0={ε}3）字母表A的n次方冪表示字母表A上長度為n的字符串集3.2符號(hào)和符號(hào)串四、字母表的閉包和正閉包1.字母表Σ的閉包

Σ*＝Σ0∪Σ1∪Σ2∪…∪Σn

即由Σ上所有符號(hào)串組成的符號(hào)串集（包含空串）2.字母表Σ的正閉包Σ+＝Σ1∪Σ2∪…∪Σn

即由Σ上所有符號(hào)串組成的符號(hào)串集（不包含空串）顯然有Σ*＝Σ0∪Σ+; Σ+=ΣΣ*=Σ*Σ對所有Σ，有ε∈Σ*。3.3文法和語言的形式定義規(guī)則，也稱為產(chǎn)生式或生成式如一個(gè)產(chǎn)生式的形式是α→β（或α::=β)，其中“→”讀為“是”或“定義為”；非終結(jié)符：在規(guī)則中用<>括起來非終結(jié)符用VN表示終結(jié)符語言中不可再分的字符串終結(jié)符用VT表示定義3.1文法G是一個(gè)四元式組G=(VT，VN，S，P)其中VT：終結(jié)符集合（非空、有窮）VN：非終結(jié)符集合（非空、有窮），且VT

VN=S：文法的開始符號(hào)，SVNP：產(chǎn)生式集合(非空、有窮)，產(chǎn)生式的形式是α→β

α和β屬于(VT

VN)*開始符S至少必須在某個(gè)產(chǎn)生式的左部出現(xiàn)一次。3.3文法和語言的形式定義例：文法G=（VN，VT，P，S）VN＝{標(biāo)識(shí)符，字母，數(shù)字}，VT＝{a,b,c,…,x,y,z,0,1,…,8,9}

P={

<標(biāo)識(shí)符>→<字母>|<標(biāo)識(shí)符><字母>|<標(biāo)識(shí)符><數(shù)字><字母>→a|b|c|…|x|y|z<數(shù)字>→0|1|2|…|8|9

}S=<標(biāo)識(shí)符>注意：有時(shí)不用將文法G的四元組顯示的表示出來，而只寫產(chǎn)生式約定：第一個(gè)產(chǎn)生式的左部是開始符號(hào)可將G寫成G[S]，S為文法G的開始符號(hào)下面是一個(gè)文法的等價(jià)寫法1）G={{S,A},{a,b},P,S}其中P：S->aAbA->abA->aAbA->ε2）G:S->aAbA->abA->aAbA->ε3）G[S]:S->aAbA->abA->aAbA->ε4）G[S]:A->aAb|ab|εS->aAb

有關(guān)推導(dǎo)的定義1、直接推導(dǎo)若αAβ直接推導(dǎo)出αγβ，即αAβ=>αγβ，當(dāng)且僅當(dāng)A→γ是一個(gè)產(chǎn)生式，且α、β∈(VN∪VT)*<注>符號(hào)‘=>’指推導(dǎo)一步，即推導(dǎo)每前進(jìn)一步總是引用一條規(guī)則（產(chǎn)生式）2、長度為n（n≥1）的推導(dǎo)若存在直接推導(dǎo)序列a0a1…an，則稱a0可推導(dǎo)出an。a0an表示：從a0出發(fā)經(jīng)過一步或若干步，可推導(dǎo)出an。3、長度為n（n≥0）的推導(dǎo)a1an表示：從a1出發(fā)經(jīng)過0步（a1＝an）或若干步，可推導(dǎo)出an。例：文法G：<標(biāo)識(shí)符>→<字母>|<標(biāo)識(shí)符><字母>|<標(biāo)識(shí)符><數(shù)字><字母>→a|b|c|…|x|y|z<數(shù)字>→0|1|2|…|8|9句型、句子、語言例：證明終結(jié)符號(hào)串(i*i+i)是文法G：E→E+E|E*E|(E)|i的一個(gè)句子證明：∵E=>(E)=>(E+E)=>(E*E+E)=>(i*E+E)=>(i*i+E)=>(i*i+i)是從開始符號(hào)E到(i*i+i)的一個(gè)推導(dǎo)。其中E、(E)、(E+E)、(E*E+E)、(i*E+E)、(i*i+E)、(i*i+i)都是這個(gè)文法的一個(gè)句型1.句型：設(shè)G[S]是一個(gè)文法，S是它的開始符號(hào)，若Sα,則稱α是文法G[S]的句型。2.句子：僅含終結(jié)符的句型是一個(gè)句子，即Sα，α∈VT*,則α是句子。3.語言：文法G所產(chǎn)生的句子的全體是一個(gè)語言，記作L(G)L(G)={α|Sα,且α∈VT*}語言的例子例：文法G2：A→bA|cc，證明cc、bcc、bbcc、…屬于L(G2)。證明：VT={b,c}，VN={A}，S=AAcc，AbAbcc，AbAbbAbbcc……∴cc、bcc、bbcc、……是屬于L(G2)的例：文法G[S]為(1)S→0S1；(2)S→01,G[S]的語言是什么。解：通過對第一個(gè)產(chǎn)生式使用n-1次，然后使用第二個(gè)產(chǎn)生式一次，得到：S0S100S11……0n-1S1n-10n1n因此L(G)={0n1n|n≥1}

文法的等價(jià)若L(G1)=L(G2)，則稱文法G1和G2是等價(jià)的例如:文法G1=(VN,VT,P,S)，VN={S}，VT={0,1}，P由下列產(chǎn)生式組成：

(1)S→0S1；(2)S→01；

文法G2=(VN,VT,P,S)，VN={A,R}，VT={0,1}，P由下列產(chǎn)生式組成：(1)A→0R;(2)A→01;(3)R→A13.4文法的類型喬姆斯基建立的形式語言對計(jì)算機(jī)科學(xué)的發(fā)展具有深刻的意義。他把文法分成四種類型：0型、1型、2型和3型。它們的差別在于對產(chǎn)生式施加不同的限制。0型文法（或稱短語文法）

G=(VN,VT,P,S)是0型文法是指：若它的每個(gè)產(chǎn)生式α→β是這樣一種結(jié)構(gòu):

α∈(VN∪VT)*且至少含有一個(gè)非終結(jié)符，β∈(VN∪VT)*。0型文法又稱為短語文法。

0型文法的能力相當(dāng)于圖靈機(jī)（計(jì)算機(jī)的一種簡單的理論模型）。1型文法（或稱上下文有關(guān)文法）如果對0型文法分別加以以下的限制，則可得到1型文法。設(shè)G=(VN,VT,P,S)為一文法，若G的任何產(chǎn)生式α→β均滿足|α|≤|β|(指符號(hào)串的長度)，僅僅S→ε例外。上下文有關(guān)就是對非終結(jié)符進(jìn)行替換時(shí)必須考慮上下文例如：1型文法G的產(chǎn)生式也可寫成αAβ→αγβ，其中α、β、γ都在(VN∪VT)*中，且γ≠ε，A∈VN

，則說明了非終結(jié)符A必須在α、β這樣一個(gè)上下文環(huán)境中才可以替換。

2型文法（或稱上下文無關(guān)文法）設(shè)G=(VN,VT,P,S)為一文法，若G的任何產(chǎn)生式形似α→β，其中α∈VN，β∈(VN∪VT)*。例：G=({S,A,B},{a,b},P,S)，其中P由下列產(chǎn)生式組成S→aB|bAA→a|aS|bAAB→b|bS|Abb例：G=(VN,VT,P,S)，VN={S}，VT={0,1}，P由下列產(chǎn)生式組成：

(1)S→0S1；(2)S→01；

上下文無關(guān)文法的說明上下文無關(guān)，顧名思義就是非終結(jié)符的替換可以不必考慮上下文。由于這種文法對程序已基本可以描述，因此，上下文無關(guān)文法常簡稱為文法。

3型文法（或稱正規(guī)文法）設(shè)G=(VN,VT,P,S)為一文法，若G的任何產(chǎn)生式A→α或A→αB，其中A、B∈VN，α∈VT*。例：文法G=({S,A,B},{0,1},P,S)，其中P由下列產(chǎn)生式組成S→0A|1B|0A→0A|1B|0SB→1B|1|0例：設(shè)G=(VN,VT,P,S)，VN={S,B,E}，VT={a,b,e}，P由下列產(chǎn)生式組成：(1)S→aSBE；(2)S→aBE;(3)EB→BE;(4)aB→ab;(5)bB→bb;(6)bE→be;(7)eE→ee;判斷以下文法屬于哪類文法？3.5上下文無關(guān)文法及其語法樹一、語法樹（推導(dǎo)樹）直觀定義：用圖表示上下文無關(guān)文法句型推導(dǎo)的直觀方法。2.形式定義給定文法G=(VN,VT,P,S)，對于G的任何句型都能構(gòu)造與之相關(guān)聯(lián)的語法樹，這棵語法樹滿足以下4個(gè)條件：（1）根結(jié)點(diǎn)由開始符號(hào)S所標(biāo)記；（2）每個(gè)結(jié)點(diǎn)都有一個(gè)標(biāo)記，此標(biāo)記是V(即VN∪VT)的一個(gè)符號(hào)；（3）若結(jié)點(diǎn)n至少有一個(gè)除它自己以外的子孫結(jié)點(diǎn)，并且有標(biāo)記A，則A在VN中；（4）如果結(jié)點(diǎn)n的直接子孫，從左到右的次序是結(jié)點(diǎn)n1,…,nk，其標(biāo)記為A1,A2,…,Ak，那么A->A1A2…Ak一定是P中的一個(gè)產(chǎn)生式。從根結(jié)點(diǎn)S開始推導(dǎo)，當(dāng)非終結(jié)符被它的某個(gè)候選式所替換時(shí)，這個(gè)非終結(jié)符的相應(yīng)結(jié)點(diǎn)就產(chǎn)生出下一代新結(jié)點(diǎn)，候選式中自左向右的每個(gè)符號(hào)對應(yīng)一個(gè)新結(jié)點(diǎn)，并用這些符號(hào)標(biāo)記其相應(yīng)的新結(jié)點(diǎn)。每個(gè)新結(jié)點(diǎn)與其父結(jié)點(diǎn)間都有一條連線。在一棵語法樹生長過程中的任何時(shí)刻，所有那些沒有后代的末端結(jié)點(diǎn)自左向右排列起來就是一個(gè)句型。語法樹構(gòu)造的過程E(根)（E）E++EE*Eiii層次12345例1文法G=({E},{+,*,i,(,)},P,E)，其中P為：E→E+E|E*E|(E)|i對該文法關(guān)于(i*i+i)的推導(dǎo)的語法樹如下所示：例2：G=（{S，A}，{a,b},P,S),其中P為：(1)S→aAS(2)A→SbA(3)S→a(4)A→ba

求文法G的句型aabbaa的推導(dǎo)樹。最左推導(dǎo)/最右推導(dǎo)/規(guī)范句型最左推導(dǎo)是指：任何一步α=>β都是對α中的最左非終結(jié)符進(jìn)行替換。同樣，可定義最右推導(dǎo)（又稱規(guī)范推導(dǎo)）：任何一步α=>β都是對α中的最右非終結(jié)符進(jìn)行替換。由規(guī)范推導(dǎo)所得到的句型稱為規(guī)范句型。注意：從一個(gè)句型到另一個(gè)句型的推導(dǎo)過程往往是不唯一的。例如E+Ei+i（a）E+E=>E+i=>i+i——最右推導(dǎo)（b）E+E=>i+E=>i+i——最左推導(dǎo)一個(gè)句型是否只對應(yīng)唯一的一棵語法樹？例如對于文法G[E]：E→E+E|E*E|(E)|i，對于句子(i*i+i)存在語法樹：E(根)（E）E++EE*EiiiE(根)（E）E*EE+Eiii定義：一個(gè)文法的某個(gè)句子對應(yīng)兩棵不同的語法樹，則這個(gè)文法是二義的?；蛞粋€(gè)文法的某個(gè)句子有兩個(gè)不同的最左（右）推導(dǎo)，則這個(gè)文法是二義的。二義性

二義性其它問題人們已證明，二義性問題是不可判定的，即不存在一個(gè)算法，它能在有限步驟內(nèi)，確切地判斷一個(gè)文法是否是二義的。我們所能做的就是為無二義性尋找一些充分條件例如對文法G[E]：E→E+E|E*E|(E)|i修改，規(guī)定運(yùn)算符“+”與“*”的優(yōu)先關(guān)系和結(jié)合規(guī)則，設(shè)“*”的優(yōu)先性高于“+”，且服從左結(jié)合。G’:E→T|E+TT→F|T*FF→(E)|i3.6句型的分析句型分析的任務(wù)就是按文法的產(chǎn)生式，識(shí)別輸入的符號(hào)是否是該文法的句型。我們把完成句型分析的程序稱為分析程序或識(shí)別程序，分析算法又稱識(shí)別算法。分析算法又分為：從左到右分析算法；從右到左分析算法；自上而下的分析法自下而上的分析法3.6.1自上而下的分析法基本思想：從文法的開始符號(hào)出發(fā)，反復(fù)使用各種產(chǎn)生式，尋找“匹配”輸入符號(hào)串的推導(dǎo)。即對任何輸入符號(hào)串，從文法的開始符號(hào)（根結(jié)）出發(fā)，自上而下地為輸入串建立一棵語法樹，直到語法樹結(jié)果正好是輸入的符號(hào)串為止。例如：文法G[S]:S→xAyA→**|*，識(shí)別輸入串x*y是否是該文法的一個(gè)句子。解：SSSSxAy(2)SSSxAy(3)*(1)缺陷關(guān)鍵：回溯問題；（∵其分析過程是一種試探過程）回溯問題是從各種可能的候選式中任選一個(gè)，進(jìn)行推導(dǎo)后發(fā)現(xiàn)該候選式是錯(cuò)誤的，則退回去重新選擇候選式的方式。例如上例中的(3)。SSSxAy(3)—選用第1個(gè)候選式*回溯的產(chǎn)生使算法代價(jià)極高，效率很低。*3.6.2自下而上的分析法基本思想：從輸入串開始，逐步進(jìn)行“歸約”，直至歸約到文法的開始符號(hào)。即從語法樹的末端開始，步步向上“歸約”，直到根結(jié)。歸約：若V=γαδ，W=γβδ，α→β是文法的產(chǎn)生式，如有V=>W，則W直接歸約到V。例：文法G[S]：(1)S→aAcBe(2)A→b(3)A→Ab(4)B→d識(shí)別abbcde是否為文法S的一個(gè)句子。解題思想：掃描abbcde，從中找出一個(gè)子串，該子串與某一產(chǎn)生式的右部相匹配。解：abbcde(1)abbcdeAA(2)abbcdeAA(3)abbcdeAA(4)BabbcdeAA(5)BAS例：文法G[S]：(1)S→aAcBe(2)A→b(3)A→Ab(4)B→d自下而上分析法存在的問題可歸約串的問題；該分析的每一步就是從當(dāng)前串中找一個(gè)子串（稱“可歸約串”），將它歸約到某個(gè)非終結(jié)符號(hào)

自下而上分析法的關(guān)鍵就是找哪個(gè)子串是“可歸約串”，哪個(gè)不是“可歸約串”。例：上例中的(3)abbcdeAA(3)—用產(chǎn)生式(2)而非(3)，則不能歸約到S因此必須精確定義“可歸約串”

3.6.3句型分析的有關(guān)問題在自上而下的分析方法中，存在的缺陷是“回溯”，如何確定用哪個(gè)右部代替左部？在自下而上的分析方法中，解決的關(guān)鍵問題是“可歸約串”。短語、直接短語、句柄1、短語：令文法G，開始符號(hào)為S，αβδ是G的句型（即Sαβδ），如果SαAδ且Aβ，則稱β是句型αβδ相對于非終結(jié)符A的短語。如果有A=>β，則稱β是句型相對于規(guī)則A→β的直接短語。3、句柄一個(gè)句型的最左直接短語稱為該句型的句柄。解題方法例：文法G[E]:E→T|E+TT→F|T*FF→(E)|i證明i+i*i是G的一個(gè)句型，并指出這個(gè)句型的所有短語、直接短語、句柄。證明：EE+TE+T*FE+T*iE+F*iE+i*iT+i*iF+i*ii+i*i接上例語法樹：EE+TTT*FFFi3i1i2第1層i1+i2*i3—相對于E第2層i1—相對于E;i2*i3—相對于T第3層i1,i2—相對于T;i3—相對于F第4層i1,i2—相對于F(F→i直接短語)第5層i+i*i是G的一個(gè)句型，其中i1,i2,i3,i2*i3,i1+i2*i3都是句型i1+i2*i3的短語，且i1,i2,i3為直接短語，i1為句柄分析說明(2)作為“短語”的兩個(gè)條件是不可缺少的，僅僅有Aβ，未必意味著β就是句型αβδ的一個(gè)短語，因?yàn)檫€需要有SαAδ這個(gè)條件。例如：上例中有Ei1+i2，但i1+i2并不是該句型的一個(gè)短語，因?yàn)椴淮嬖趶腅（開始符號(hào)）到E*i3的推導(dǎo)。(1)短語、直接短語、句柄是針對某一句型（Sα）而言的;3.7有關(guān)文法實(shí)用中的一些說明在實(shí)際應(yīng)用中對文法提出一些限制對文法進(jìn)行擴(kuò)充3.7.1有關(guān)文法實(shí)用限制在實(shí)用中，主要是在文法中不得含有有害規(guī)則和多余規(guī)則。1、不含有害規(guī)則有害規(guī)則是指形如P→P的產(chǎn)生式，因?yàn)檫@樣的產(chǎn)生式除了引起二義外，沒有任何用處。2、不含多余規(guī)則(1)不可到達(dá)的即文法中的某些非終結(jié)符不在任何規(guī)則的右部出現(xiàn)，則任何句子推導(dǎo)不可能用到它。也就是說對非終結(jié)符P，不存在SαPβ，α,β∈

(VN∪VT)*

3.7.1有關(guān)文法實(shí)用限制(2)不可終止的即文法中的某些非終結(jié)符不能夠從它推出終結(jié)符串。也就是說對非終結(jié)符P，不存在Pt，t∈

VT*

若文法均滿足以上兩個(gè)條件，則稱這個(gè)文法為簡化了的文法。文法G[S]：

(1)S→Be

(2)B→Ce

(3)B→Af

(4)A→Ae

(5)A→e

(6)C→Cf

(7)D→f（7）、（6）、（2）多余規(guī)則3.7.2上下文無關(guān)文法的ε規(guī)則自學(xué)例1：證明文法G[E]是二義的:(1)E→EOE|(E)|v|d(2)O→+|*

3.8典型例題例1：證明文法G[E]是二義的:(1)E→EOE|(E)|v|d(2)O→+3.8典型例題3.8典型例題例2：考慮以下語言L1={anb2ncm|n,m>0}L2={anbmc2m|n,m>0}通過分別給出上述語言的文法來證明這些語言都是上下文無關(guān)