第2章-1-文法的形式定義

第2章前后文無關(guān)文法和語言本章主要內(nèi)容2.1語言及文法概述2.2文法(Grammar)和語言的形式定義2.3句型分析2.4文法的分類2.5文法的構(gòu)造2.1語言概述什么是語言自然語言(NaturalLanguage)是人與人的通訊工具語義(Semantics):環(huán)境、背景知識、語氣、二義性——難以形式化計(jì)算機(jī)語言(ComputerLanguage)計(jì)算機(jī)系統(tǒng)間、人機(jī)間通訊工具嚴(yán)格的語法(Grammar)、語義(Semantics)——易于形式化：嚴(yán)格語言是用來交換信息的工具——功能性描述2.1語言概述語言的描述方法——現(xiàn)狀自然語言：自然、方便-非形式化數(shù)學(xué)語言（符號）：嚴(yán)格、準(zhǔn)確-形式化形式化描述高度的抽象，嚴(yán)格的理論基礎(chǔ)和方便的計(jì)算機(jī)表示。2.1語言概述語言——形式化的內(nèi)容提取單詞(Token)：滿足一定規(guī)則字符(Character)串句子(Sentence)：滿足一定規(guī)則單詞序列語言(Language)：滿足一定條件的句子集合語言是字和組合字的規(guī)則——結(jié)構(gòu)性描述例：一譯開天第課今始編節(jié)上今天開始上第一節(jié)編譯課2.1語言概述程序設(shè)計(jì)語言——形式化的內(nèi)容提取程序設(shè)計(jì)語言(ProgrammingLanguage)：組成程序的所有語句的集合程序(Program)：滿足語法規(guī)則的語句序列語句(Sentence)：滿足語法規(guī)則的單詞序列單詞(Token)：滿足詞法規(guī)則的字符串例變量=表達(dá)式if條件then語句while條件do語句call過程名(參數(shù)表)2.1語言概述描述形式——文法語法——語句語句的組成規(guī)則描述方法：BNF范式、語法(描述)圖詞法——單詞單詞的組成規(guī)則描述方法：BNF范式、正規(guī)式2.2文法和語言的基本定義

2.2.1基本概念和術(shù)語字母表（Alphabet）是一個(gè)非空有窮集合，字母表中的元素稱為該字母表的一個(gè)字母（Letter），也叫字符（Character）例以下是不同的字母表 ⑴{a，b，c，d} ⑵{a，b，c，……，z} ⑶{0，1}相當(dāng)于高級語言的字符集2.2.1基本概念和術(shù)語字母表上符號串(String)的定義

(1)ε是∑上的一個(gè)符號串，叫做空串。(2)若x是∑上的符號串，而a是∑的元素,

則xa是∑上的符號串。(3)y是∑上的符號串,當(dāng)且僅當(dāng)它由(1)和(2)導(dǎo)出。由字母表中的符號所組成的的任何有窮序列被稱之為該字母表上的符號串,也稱作“字”(Word)。2.2.1基本概念和術(shù)語定義1設(shè)∑1、∑2是兩個(gè)字母表，∑1與∑2

的乘積(Product)∑1∑2={ab|a∈∑1，b∈∑2}例:∑1={0,1},∑2={a,b},∑1∑2={0a,0b,1a,1b}定義2設(shè)∑是一個(gè)字母表，∑的n次冪(Power)遞歸地定義為：⑴∑0={ε}⑵∑n=∑n-1∑ n≥1例：∑13={000,001,010,011,100,101,110,111}2.2.1基本概念和術(shù)語定義3設(shè)∑是一個(gè)字母表，∑的正閉包(PositiveClosure)：∑+=∑∪∑2∪∑3∪∑4∪……∑的克林閉包(KleeneClosure)：∑*=∑0∪∑+=∑0∪∑∪∑2∪∑3∪……2.2.1基本概念和術(shù)語例{0,1}+={0，1，00，01，11，000，001，010，011，100，……}{a，b，c，d}+={a，b，c，d，aa，ab，ac，ad，ba，bb，bc，bd，……，aaa，aab，aac，aad，aba，abb，abc……}2.2.1基本概念和術(shù)語例{0,1}*={ε，0，1，00，01，11，000，001，010，011，100，…}{a，b，c，d}*={ε，a，b，c，d，aa，ab，ac，ad，ba，bb，bc，bd，…，aaa，aab，aac，aad，aba，abb，abc，…}2.2.1基本概念和術(shù)語定義5設(shè)∑是一個(gè)字母表，L∑*，L稱為字母表∑上的一個(gè)語言（Language），x∈L，x叫做L的一個(gè)句子。例：字母表{0，1}上的語言{0，1}{00，11}{0，1，00，11}{0，1，00，11，01，10}{00，11}*{01，10}*2.2.1基本概念和術(shù)語設(shè)s是符號串：01290273前綴：移走s的尾部的零個(gè)或多于零個(gè)符號后綴：刪去s的頭部的零個(gè)或多于零個(gè)符號子串：從s中刪去一個(gè)前綴和一個(gè)后綴子序列:從s中刪去零個(gè)或多于零個(gè)符號(這些符號不要求是連續(xù)的）長度：是該符號串中的符號的數(shù)目。例如|aab|=3,|ε|=0。2.2.1基本概念和術(shù)語符號串的連接和冪1.連接：設(shè)x和y是符號串，它們的連接xy是把y的符號寫在x的符號之后得到的符號串。例如，x=ba,y=nana,xy=banana.2.冪：x0=;x1=x;x2=xx;……;xn=xn-1x;

例如,x=ba,x1=ba,x2=baba,x3=bababa,…...2.2.1基本概念和術(shù)語符號串集合的和與積設(shè)A，B為兩個(gè)符號串之集，定義

和 A+B（或A∪B）

={w|wA，或wB}

積 A?B（或AB）={xy|xA,yB} A+=+A=A；

A=A=；{}A=A{}=A符號串集合的方冪符號串集合A，定義A0={ε},A1=A,A2=AA,A3=A2A,…,An＝An-1A=AAn-1，n>0符號串集合的正閉包A+=A1∪A2∪…∪An…符號串集合的自反閉包A*={ε}∪A+2.2.2文法的形式化定義如何實(shí)現(xiàn)語言結(jié)構(gòu)的形式化描述？考慮一個(gè)句子——文法要素的提取分析：Thegraywolfwilleatthegoat〈謂語〉〈主語〉〈形容詞〉〈名詞〉〈動(dòng)詞〉〈直接賓語〉助動(dòng)詞〈句子〉動(dòng)原冠詞名詞Thegraywolfwilleatthegoat〈冠詞〉提取規(guī)則，寫在黑板上句子

→

主語

謂語主語

→

冠詞

形容詞

名詞謂語

→

動(dòng)詞

直接賓語動(dòng)詞

→

助動(dòng)詞

動(dòng)詞原形直接賓語

→

冠詞

名詞產(chǎn)生句子的規(guī)則——從產(chǎn)生語言的角度冠詞

→

the形容詞

→

gray助動(dòng)詞

→

will動(dòng)詞原形

→

eat名詞

→

wolf名詞

→

goat終結(jié)符號集VT={the，gray,wolf,will,eat,goat}非終結(jié)符號集VN={句子，主語，謂語，冠詞，形容詞，名詞，動(dòng)詞，直接賓語，助動(dòng)詞，動(dòng)詞原形

}語法規(guī)則集P={句子→主語謂語，……}開始符號S=句子句子的語法組成

——終結(jié)符號集，非終結(jié)符號集，語法規(guī)則，開始符號文法G的形式定義文法G為一個(gè)四元組:

Ｇ=(ＶT，ＶN，Ｐ，Ｓ)ＶT：終結(jié)符(Terminal)集ＶN：非終結(jié)符(Variable)集，ＶT∩ＶN=Φ語法范疇——某個(gè)語言結(jié)構(gòu)Ｓ：開始符號(StartSymbol)，S∈ＶN至少在產(chǎn)生式左側(cè)出現(xiàn)一次文法G的形式定義Ｐ：產(chǎn)生式(Product)集合α→β，被稱為產(chǎn)生式（定義式），讀作：α定義為β。其中α∈(ＶT∪ＶN)+，且α中至少有ＶN中元素的一個(gè)出現(xiàn)。β∈(ＶT∪ＶN)*。α稱為產(chǎn)生式α→β的左部(LeftPart)，β稱為產(chǎn)生式α→β的右部(RightPart)。

句子主語

謂語

冠詞

形容詞

名詞

謂語

the形容詞

名詞

謂語

thegray名詞

謂語

thegraywolf謂語

thegraywolf

動(dòng)詞

直接賓語

thegraywolf助動(dòng)詞

動(dòng)詞原形

直接賓語

thegraywolfwill動(dòng)詞原形

直接賓語

thegraywolfwilleat直接賓語

thegraywolfwilleat

冠詞

名詞

thegraywolfwilleatthe名詞

thegraywolfwilleatthegoat句子的派生（推導(dǎo)）___根據(jù)規(guī)則句子

thegraywolfwilleatthegoatthegraywolfwilleatthewolfthegraygoatwilleatthewolf符合語法且符合語義的句子僅是：

thegraywolfwilleatthegoat還可以“得出”其他的句子例

算術(shù)表達(dá)式的文法考慮簡單算術(shù)表達(dá)式組成的語言遞歸定義——中綴表示標(biāo)識符(id)（常數(shù)、變量）是表達(dá)式；表達(dá)式加一個(gè)表達(dá)式是表達(dá)式；表達(dá)式減一個(gè)表達(dá)式是表達(dá)式；表達(dá)式乘一個(gè)表達(dá)式是表達(dá)式；表達(dá)式除一個(gè)表達(dá)式是表達(dá)式；表達(dá)式加上括號后是表達(dá)式。例

算術(shù)表達(dá)式的文法考慮用式子表示這個(gè)定義標(biāo)識符(id)是表達(dá)式表達(dá)式加一個(gè)表達(dá)式是表達(dá)式E→idE→E+E表達(dá)式減一個(gè)表達(dá)式是表達(dá)式E→E-E表達(dá)式乘一個(gè)表達(dá)式是表達(dá)式E→E*E表達(dá)式除一個(gè)表達(dá)式是表達(dá)式E→E/E表達(dá)式加上括號后是表達(dá)式E→(E)例

算術(shù)表達(dá)式的文法P:E→E+EE→E-EE→E*EE→E/EE→(E)E→idG=（{id，+，-，*，/，(，)}，{E}，P，E）約定：只寫產(chǎn)生式簡寫E→E+E|E*E|E-E|E/E|(E)|id產(chǎn)生式的簡寫對一組有相同左部的產(chǎn)生式α→β1，α→β2…，α→βn簡單地記為：α→β1|β2|…|βn

讀作：α定義為或者β1，或者β2，…，或者βn。并且稱它們?yōu)棣廉a(chǎn)生式。β1，β2，…，βn稱為候選式(Candidate)文法如何實(shí)現(xiàn)對語言的刻畫？產(chǎn)生式很關(guān)鍵！產(chǎn)生式規(guī)定的一些變換E由第1個(gè)候選式可以變成E+EE+E中的第1個(gè)E由第2個(gè)候選式可以變成E*E，從而E+E變成E*E+E根據(jù)第4個(gè)候選式，E*E+E中的E都可以變成id:E*E+E變成id*E+Eid*E+E變成id*E+idid*E+id變成id*id+id也就是說，根據(jù)第4個(gè)候選式，E*E+E經(jīng)3步變換變成id*id+id1E→E+E2E→E*E3E→(E)4E→id5E→E-E6E→E/E表示依據(jù)文法進(jìn)行的變換EE+E （1）

E*E+E （2）

id*E+E （4）

id*E+id （4）

id*id+id （4）4E→id5E→E-E6E→E/EE可以變成E+EE+E中的第一個(gè)E變成E*EE*E+E變成id*E+Eid*E+E變成id*E+idid*E+id變成id*id+idE經(jīng)5步變換變成id*id+id：E5id*id+id1E→E+E2E→E*E3E→(E)實(shí)質(zhì)是從E開始依據(jù)產(chǎn)生式對所得串中的特定部分進(jìn)行變換，不斷獲得新的串，最終得到目標(biāo)變換的分析實(shí)質(zhì)是從E開始依據(jù)產(chǎn)生式對所得串中的特定部分進(jìn)行變換，不斷獲得新的串，最終得到目標(biāo)

E*E

依據(jù)產(chǎn)生式E→E+EE*E+EαAβ依據(jù)產(chǎn)生式A→γαγβ直接推導(dǎo)與歸約根據(jù)產(chǎn)生式對符號串進(jìn)行變換的過程Ａ→γ是文法Ｇ的一個(gè)產(chǎn)生式，且α、β∈（ＶT∪ＶN）*，稱αＡβ的直接推導(dǎo)/派生(Derive)出αγβ，也稱αγβ直接歸約(Reduce)為αＡβ。記為αＡβαγβ例：id+Eid+E*E（多步）推導(dǎo)/歸約α0α1α2…αn記為α0nαn

(恰用n步)α0+αn

（至少一步）

α0*αn

（若干步:零步或多步）E5id*id+id推導(dǎo)/歸約回顧EE+E （1）串中含有變量

id+E （4）串中含有變量

id+E*E （2）串中含有變量

id+id*E （4）串中含有變量

id+id*id （4）串中沒有變量到此串中已經(jīng)沒有（語法）變量了，不能再推了——得到句子1E→E+E2E→E*E3E→(E)4E→id句型與句子EE+EE+E*EE4id+id*E定義:如果S*α，α∈(ＶT∪ＶN)*則稱α是G產(chǎn)生的一個(gè)句型(SententialForm)E5id+id*id定義:如果S*x，且x∈ＶT*，則稱x是G產(chǎn)生的一個(gè)句子(Sentence)文法G產(chǎn)生的語言定義： L(G)={x|S*xandx∈VT*}文法E→E+E|E*E|(E)|id可以派生出多少個(gè)句子？文法G的作用——語言的有窮描述以有限的規(guī)則描述無限的語言現(xiàn)象有限:產(chǎn)生式集合、終結(jié)符集合、非終結(jié)符集合無限：可以導(dǎo)出無窮多個(gè)句子（注：L也可是有窮）當(dāng)語言是無限集時(shí)，能否用有限的規(guī)則來描述呢？回答是肯定的,只需使用文法的遞歸定義即可。例如，文法G1[<標(biāo)識符>]：<標(biāo)識符><字母>|<標(biāo)識符><字母>|<標(biāo)識符><數(shù)字><字母>A|B|…|Z<數(shù)字>0|1|2|…|9遞歸文法文法G2[E]：

E→E+E|E*E|E-E|E/E|(E)|id顯然，G1，G2都是遞歸定義的。所謂遞歸定義，指在定義一個(gè)語法成分時(shí)，直接或間接地使用了語法成分自身。遞歸文法文法等價(jià)若L(G1)=L(G2)，則稱文法