第三章文法和語(yǔ)言

1、第三章第三章 文法和語(yǔ)言文法和語(yǔ)言學(xué)習(xí)目標(biāo)學(xué)習(xí)目標(biāo): : q掌握：自上而下與自下而上的分析方法掌握：自上而下與自下而上的分析方法q理解：文法的形式定義，推導(dǎo)，歸約，句理解：文法的形式定義，推導(dǎo)，歸約，句型，句子，語(yǔ)言，上下文無(wú)關(guān)文法，規(guī)范型，句子，語(yǔ)言，上下文無(wú)關(guān)文法，規(guī)范句型，語(yǔ)法樹(shù)，短語(yǔ)，直接短語(yǔ)，句柄句型，語(yǔ)法樹(shù)，短語(yǔ)，直接短語(yǔ)，句柄q了解：文法的類(lèi)型，文法使用中的限制，了解：文法的類(lèi)型，文法使用中的限制，文法的二義性文法的二義性3.1語(yǔ)言和文法的直觀概念語(yǔ)言和文法的直觀概念3.2符號(hào)和符號(hào)串符號(hào)和符號(hào)串3.3文法和語(yǔ)言的形式定義文法和語(yǔ)言的形式定義3.4文法的類(lèi)型文法的類(lèi)型3.5上下文

2、無(wú)關(guān)文法及其語(yǔ)法樹(shù)上下文無(wú)關(guān)文法及其語(yǔ)法樹(shù)3.6句型的分析句型的分析3.7有關(guān)文法實(shí)用中的一些說(shuō)明有關(guān)文法實(shí)用中的一些說(shuō)明3.1 3.1 語(yǔ)言和文法的直觀概念語(yǔ)言和文法的直觀概念1. 程序設(shè)計(jì)語(yǔ)言的定義程序設(shè)計(jì)語(yǔ)言的定義語(yǔ)言是一個(gè)記號(hào)系統(tǒng)。語(yǔ)言是一個(gè)記號(hào)系統(tǒng)。 漢語(yǔ)漢語(yǔ)-所有符合漢語(yǔ)語(yǔ)法的句子的全體所有符合漢語(yǔ)語(yǔ)法的句子的全體 英語(yǔ)英語(yǔ)-所有符合英語(yǔ)語(yǔ)法的句子的全體所有符合英語(yǔ)語(yǔ)法的句子的全體 程序設(shè)計(jì)語(yǔ)言程序設(shè)計(jì)語(yǔ)言-所有該語(yǔ)言的程序的全體所有該語(yǔ)言的程序的全體研究程序設(shè)計(jì)語(yǔ)言包括：研究程序設(shè)計(jì)語(yǔ)言包括： 每個(gè)程序構(gòu)成的規(guī)律每個(gè)程序構(gòu)成的規(guī)律 每個(gè)程序的含義每個(gè)程序的含義程序設(shè)計(jì)語(yǔ)言包括程序

3、設(shè)計(jì)語(yǔ)言包括:語(yǔ)法和語(yǔ)義語(yǔ)法和語(yǔ)義q語(yǔ)法語(yǔ)法(syntax)定義定義: 是一組規(guī)則，用它可以形成和產(chǎn)生是一組規(guī)則，用它可以形成和產(chǎn)生一個(gè)合適的程序一個(gè)合適的程序描述工具描述工具:文法文法作用作用: 定義什么樣的符號(hào)序列是合法的，定義什么樣的符號(hào)序列是合法的，與符號(hào)的含義無(wú)關(guān)。與符號(hào)的含義無(wú)關(guān)。q語(yǔ)義語(yǔ)義(semantics)分類(lèi)分類(lèi):靜態(tài)語(yǔ)義：一系列限定規(guī)則，確定哪些靜態(tài)語(yǔ)義：一系列限定規(guī)則，確定哪些合乎語(yǔ)法的程序是合適的合乎語(yǔ)法的程序是合適的動(dòng)態(tài)語(yǔ)義：表明程序要做什么動(dòng)態(tài)語(yǔ)義：表明程序要做什么描述工具描述工具: 指稱(chēng)語(yǔ)義指稱(chēng)語(yǔ)義,操作語(yǔ)義等操作語(yǔ)義等作用作用: 檢查類(lèi)型匹配，變量作用域等檢查

4、類(lèi)型匹配，變量作用域等2.2. 文法的直觀概念文法的直觀概念如何來(lái)描述一種語(yǔ)言？如何來(lái)描述一種語(yǔ)言？如果語(yǔ)言是有窮的（只含有有窮多個(gè)句子），可如果語(yǔ)言是有窮的（只含有有窮多個(gè)句子），可以將句子逐一列出來(lái)表示以將句子逐一列出來(lái)表示如果語(yǔ)言是無(wú)窮的，要找出語(yǔ)言的有窮表示。如果語(yǔ)言是無(wú)窮的，要找出語(yǔ)言的有窮表示。 有兩個(gè)途經(jīng)：有兩個(gè)途經(jīng)：1. 生成方式生成方式 （文法）：語(yǔ)言中的每個(gè)句子可以用嚴(yán)（文法）：語(yǔ)言中的每個(gè)句子可以用嚴(yán)格定義的規(guī)則來(lái)構(gòu)造格定義的規(guī)則來(lái)構(gòu)造2. 識(shí)別方式（自動(dòng)機(jī)）：用一個(gè)過(guò)程，當(dāng)輸入的一識(shí)別方式（自動(dòng)機(jī)）：用一個(gè)過(guò)程，當(dāng)輸入的一任意串屬于語(yǔ)言時(shí)，該過(guò)程經(jīng)有限次計(jì)算后就會(huì)任意串

5、屬于語(yǔ)言時(shí)，該過(guò)程經(jīng)有限次計(jì)算后就會(huì)停止并回答停止并回答“是是”，若不屬于，要么能停止并回，若不屬于，要么能停止并回答答“不是不是”，要么永遠(yuǎn)繼續(xù)下去。，要么永遠(yuǎn)繼續(xù)下去。q文法：是語(yǔ)言文法：是語(yǔ)言語(yǔ)法語(yǔ)法的描述工具，實(shí)現(xiàn)用的描述工具，實(shí)現(xiàn)用有窮的規(guī)則把語(yǔ)言的無(wú)窮句子集描述出有窮的規(guī)則把語(yǔ)言的無(wú)窮句子集描述出來(lái)。來(lái)。例例:“我是大學(xué)生我是大學(xué)生”是漢語(yǔ)的一個(gè)句子是漢語(yǔ)的一個(gè)句子用用EBNFEBNF來(lái)表示漢語(yǔ)句子的構(gòu)成規(guī)則：來(lái)表示漢語(yǔ)句子的構(gòu)成規(guī)則：句子句子=主語(yǔ)謂語(yǔ)主語(yǔ)謂語(yǔ)主語(yǔ)主語(yǔ)=代詞名詞代詞名詞代詞代詞= = 我你他我你他名詞名詞= = 王明大學(xué)生工人英語(yǔ)王明大學(xué)生工人英語(yǔ)謂語(yǔ)謂語(yǔ)=動(dòng)詞直

6、接賓語(yǔ)動(dòng)詞直接賓語(yǔ)動(dòng)詞動(dòng)詞= = 是學(xué)習(xí)是學(xué)習(xí)直接賓語(yǔ)直接賓語(yǔ)=代詞名詞代詞名詞q由規(guī)則推導(dǎo)句子由規(guī)則推導(dǎo)句子方法方法: 用一條規(guī)則用一條規(guī)則=的右端符號(hào)串代的右端符號(hào)串代替替:=:=的左端的左端. .表示表示: : 用用“ = = ”表示推導(dǎo)表示推導(dǎo), ,含義是含義是, ,使使用一條規(guī)則用一條規(guī)則, ,代替代替=左邊的某個(gè)符號(hào)左邊的某個(gè)符號(hào), ,產(chǎn)生產(chǎn)生=右端的符號(hào)串右端的符號(hào)串. .例如例如: :句子句子“我是大學(xué)生我是大學(xué)生”的推導(dǎo)過(guò)程如下：的推導(dǎo)過(guò)程如下：句子句子 主語(yǔ)主語(yǔ)謂語(yǔ)謂語(yǔ) 代詞代詞謂語(yǔ)謂語(yǔ) 我我謂語(yǔ)謂語(yǔ) 我我動(dòng)詞動(dòng)詞直接賓語(yǔ)直接賓語(yǔ) 我是我是直接賓語(yǔ)直接賓語(yǔ) 我是我是名詞名詞

7、 我是大學(xué)生我是大學(xué)生q文法的作用文法的作用嚴(yán)格定義句子的結(jié)構(gòu)，是判斷句子結(jié)構(gòu)嚴(yán)格定義句子的結(jié)構(gòu)，是判斷句子結(jié)構(gòu)合法與否的依據(jù)合法與否的依據(jù)用有窮的規(guī)則把無(wú)窮的句子集合描述出用有窮的規(guī)則把無(wú)窮的句子集合描述出來(lái)來(lái)3.2 3.2 符號(hào)和符號(hào)串符號(hào)和符號(hào)串1.1. 字母表字母表 定義定義: :元素的元素的非空非空有窮有窮集合集合 例：例：=01 =ab,c 元素也稱(chēng)為符號(hào)，字母表也稱(chēng)符號(hào)集。元素也稱(chēng)為符號(hào)，字母表也稱(chēng)符號(hào)集。 程序語(yǔ)言的字母表由字母數(shù)字和若干專(zhuān)程序語(yǔ)言的字母表由字母數(shù)字和若干專(zhuān)用符號(hào)組成。用符號(hào)組成。2.2. 符號(hào)串符號(hào)串 定義定義: :由字母表中的符號(hào)組成的任何有窮序列由字母表中

8、的符號(hào)組成的任何有窮序列例：例： 0,00,10是是字母表字母表=01上的符號(hào)串上的符號(hào)串 a,ab,aaca是是=ab,c上的符號(hào)串上的符號(hào)串在符號(hào)串中，符號(hào)是有順序的，順序不同在符號(hào)串中，符號(hào)是有順序的，順序不同,代代表不同的符號(hào)串，如表不同的符號(hào)串，如:ab和和ba不同不同不含任何符號(hào)的符號(hào)串稱(chēng)為空串，用不含任何符號(hào)的符號(hào)串稱(chēng)為空串，用表示表示注意注意: :并不等于空集合并不等于空集合 符號(hào)串長(zhǎng)度符號(hào)串長(zhǎng)度: 符號(hào)串中含有符號(hào)的個(gè)數(shù)符號(hào)串中含有符號(hào)的個(gè)數(shù)如如: |abc|=3| |=0 符號(hào)串的頭尾：如果符號(hào)串的頭尾：如果=xy，那么，那么x是是的頭，的頭，y是是的尾；如果的尾；如果x是

9、非空的，那么是非空的，那么y是是的固的固有尾，如果有尾，如果y是非空的，那么是非空的，那么x是是的固有頭的固有頭例：例： =abc 的頭包括：的頭包括： ，a,ab,abc 的固有頭包括：的固有頭包括： ，a,ab 的尾包括：的尾包括： ，c,bc,abc 的固有尾包括：的固有尾包括： ，c,bc3. 符號(hào)串的運(yùn)算符號(hào)串的運(yùn)算 符號(hào)串的連接符號(hào)串的連接：設(shè)設(shè)、是符號(hào)串是符號(hào)串,它們它們的連接是把的連接是把的符號(hào)寫(xiě)在的符號(hào)寫(xiě)在 的符號(hào)之后的符號(hào)之后得到的符號(hào)串得到的符號(hào)串例如例如 =ST，=abu ，則則 =STabu 顯然顯然 = = 符號(hào)串的方冪符號(hào)串的方冪：把：把符號(hào)串符號(hào)串自身連接自身連

10、接n n次次得到的符號(hào)串得到的符號(hào)串n n = = 例如例如 1 1= = 2 2= = 0 0=4.4. 符號(hào)串集合：符號(hào)串集合： 定義定義: : 若集合若集合A A中所有元素都是某字母表中所有元素都是某字母表 上上的符號(hào)串，則稱(chēng)的符號(hào)串，則稱(chēng)A A為字母表為字母表 上的符號(hào)串集合。上的符號(hào)串集合。 符號(hào)串集合的乘積符號(hào)串集合的乘積：符號(hào)串集合：符號(hào)串集合A和和B的乘積的乘積定義為定義為:AB = xy|xA且且yB ，即即AB是由是由A中的串中的串x和和B中的串中的串y連接而成的串連接而成的串xy組成的集合。組成的集合。若集合若集合A = ab,cdeab,cde B = 0,10,1 則

11、則 AB = abab0 0,ab,ab1 1,cde,cde0 0,cde,cde1 1 顯然顯然 A = A = A符號(hào)串集合的方冪符號(hào)串集合的方冪: : 設(shè)設(shè)A A是符號(hào)串的集合，則是符號(hào)串的集合，則稱(chēng)稱(chēng)A Ai i為符號(hào)串集為符號(hào)串集A A的方冪，其中的方冪，其中i i是非負(fù)整數(shù)。是非負(fù)整數(shù)。具體定義如下具體定義如下: :A A0 0 = = A A1 1 = A , A= A , A2 2 = A A= A AA AK K = AA.A(k = AA.A(k個(gè)個(gè)) )5. 集合的閉包集合的閉包 閉包閉包集合集合的閉包的閉包 *定義如下：定義如下： * = 0 1 2 3例：設(shè)有字母表

12、例：設(shè)有字母表=0，1則則*=012=,0,1,00,01,10,11,000,即即*表示表示上所有有窮長(zhǎng)的串的集合。上所有有窮長(zhǎng)的串的集合。正閉包正閉包+ = 123稱(chēng)為稱(chēng)為的正閉包。的正閉包。 + 表示字母表表示字母表 上的上的除除外外的所有用窮長(zhǎng)串的所有用窮長(zhǎng)串的集合的集合閉包和正閉包之間的運(yùn)算閉包和正閉包之間的運(yùn)算 * = 0+ = * = * 字母表字母表 上上的一個(gè)語(yǔ)言是的一個(gè)語(yǔ)言是 上的一些符號(hào)串的集合上的一些符號(hào)串的集合 即即是是 *的一個(gè)子集的一個(gè)子集例如：例如：=a,b =a,b * *=,a,b,aa,ab,ba,bb,aaa,aab,=,a,b,aa,ab,ba,bb,

13、aaa,aab, 1.集合集合 ab,aabb,aaabbb,ab,aabb,aaabbb,a,an nb bn n, , 或或 w|ww|w* *且且w=aw=an nb bn n,n1,n1為為字母表字母表 上上的一個(gè)語(yǔ)言。的一個(gè)語(yǔ)言。2.集合集合 a,aa,aaa,a,aa,aaa, 或或 w|ww|w* *且且w=aw=an n,n1,n1為為字母字母表表 上上的一個(gè)語(yǔ)言的一個(gè)語(yǔ)言3.3. 是一個(gè)語(yǔ)言是一個(gè)語(yǔ)言4. 即即 是一個(gè)語(yǔ)言。是一個(gè)語(yǔ)言。3.3 文法和語(yǔ)言的形式定義文法和語(yǔ)言的形式定義1文法的定義文法的定義2文法的簡(jiǎn)化表示法文法的簡(jiǎn)化表示法3推導(dǎo)與歸約推導(dǎo)與歸約4句型、句子、語(yǔ)

14、言的定義句型、句子、語(yǔ)言的定義5文法的等價(jià)文法的等價(jià)1文法的定義文法的定義q產(chǎn)生式（規(guī)則）產(chǎn)生式（規(guī)則）產(chǎn)生式是一個(gè)有序?qū)Ξa(chǎn)生式是一個(gè)有序?qū)?,)，通常寫(xiě)作，通常寫(xiě)作 （或或:= ） 定義為定義為q文法定義文法定義:文法文法G(Grammar)定義為四元組（定義為四元組（VN，VT，P，S）VN (Nonternimal)：非終結(jié)符集非終結(jié)符集VT (Terminal)：終結(jié)符集終結(jié)符集P (Production)： 產(chǎn)生式（規(guī)則）集合產(chǎn)生式（規(guī)則）集合S： 開(kāi)始符號(hào)或識(shí)別符號(hào)開(kāi)始符號(hào)或識(shí)別符號(hào)q 說(shuō)明說(shuō)明:V=VNVT，V稱(chēng)為文法稱(chēng)為文法G的字母表的字母表P中產(chǎn)生式形如：中產(chǎn)生式形如：,其中

15、其中V+且至少含一個(gè)非終結(jié)且至少含一個(gè)非終結(jié)符，符，V*VN,VT和和P是非空有窮集是非空有窮集VNVT=S是一個(gè)非終結(jié)符，且至少要在一條產(chǎn)生式的左部出現(xiàn)是一個(gè)非終結(jié)符，且至少要在一條產(chǎn)生式的左部出現(xiàn)非終結(jié)符一般代表一個(gè)語(yǔ)言中的語(yǔ)法成分，如非終結(jié)符一般代表一個(gè)語(yǔ)言中的語(yǔ)法成分，如，它是構(gòu)成程序的一個(gè)語(yǔ)法成分，這個(gè)符號(hào)，它是構(gòu)成程序的一個(gè)語(yǔ)法成分，這個(gè)符號(hào)本身不會(huì)在程序中出現(xiàn)，而終結(jié)符及其組成本身不會(huì)在程序中出現(xiàn)，而終結(jié)符及其組成的符號(hào)串是會(huì)在程序中出現(xiàn)的，如一個(gè)具體的賦值語(yǔ)的符號(hào)串是會(huì)在程序中出現(xiàn)的，如一個(gè)具體的賦值語(yǔ)句句“i:=x+1”例例1：文法文法G=(VN,VT,P,S)其中其中VN=

16、S，VT=0，1，P=S0S1,S01開(kāi)始開(kāi)始符為符為S例例2：文法：文法G=(VN,VT,P,S)VN =標(biāo)識(shí)符，字母，數(shù)字標(biāo)識(shí)符，字母，數(shù)字，VT =a,b,c,x,y,z,0,1,9P=， ， a, z z， 0,0, ,99 ，S=2文法的簡(jiǎn)化表示法文法的簡(jiǎn)化表示法q簡(jiǎn)化簡(jiǎn)化:通常不用將文法的四元組表示出來(lái)，只寫(xiě)出產(chǎn)通常不用將文法的四元組表示出來(lái)，只寫(xiě)出產(chǎn)生式生式q約定：約定：第一條產(chǎn)生式的左部是開(kāi)始符號(hào)或用第一條產(chǎn)生式的左部是開(kāi)始符號(hào)或用GS表示表示S是開(kāi)始符號(hào)是開(kāi)始符號(hào)用大寫(xiě)字母（或用尖括號(hào)括起來(lái)）表示非終結(jié)符用大寫(xiě)字母（或用尖括號(hào)括起來(lái)）表示非終結(jié)符用小寫(xiě)字母表示終結(jié)符用小寫(xiě)字母

17、表示終結(jié)符左部相同的產(chǎn)生式左部相同的產(chǎn)生式A,A可以記為可以記為A|，其中其中“|”是是“或或”的意思，的意思，,分別稱(chēng)為候選式分別稱(chēng)為候選式q例如例如:文法文法GS： SA|SA|SDAa|b|zD0|1|93. 推導(dǎo)推導(dǎo)(Derivation)與歸約與歸約(Reduction)q直接推導(dǎo)和直接歸約：直接推導(dǎo)和直接歸約： 是文法是文法G G的產(chǎn)生式，若有的產(chǎn)生式，若有v v，w w滿(mǎn)足：滿(mǎn)足：v=v=,w= ,w= , , 其中其中,V,V* * 則稱(chēng)則稱(chēng)v v直接推導(dǎo)直接推導(dǎo)到到w,w,也稱(chēng)也稱(chēng)w w直接歸約直接歸約到到v,v,記記作作 v v w w直接推導(dǎo)直接推導(dǎo)就是用產(chǎn)生式的右部替換

18、產(chǎn)生式就是用產(chǎn)生式的右部替換產(chǎn)生式的左部的過(guò)程的左部的過(guò)程直接歸約直接歸約就是用產(chǎn)生式的左部替換產(chǎn)生式就是用產(chǎn)生式的左部替換產(chǎn)生式的右部的過(guò)程的右部的過(guò)程例例 文法文法G G： S0S1 S0S1，S01 S01 有直接推導(dǎo)：有直接推導(dǎo)： 0 0S S1 1 0 00S10S11 1（ S0S1S0S1 ） 0000S S11 11 00000S10S11111（ S0S1S0S1 ） 000000S S111 111 0000000101111111（ S01 S01 ） S S 0S10S1（ S0S1S0S1 ）q推導(dǎo)和歸約推導(dǎo)和歸約若存在若存在v=wv=w0 0 w w1 1 . .

19、w wn n=w ,(n0)=w ,(n0) 則稱(chēng)則稱(chēng)v v推導(dǎo)出推導(dǎo)出w w，或或w w歸約到歸約到v,v,記為記為v vw w若有若有v v w w，或或v=wv=w，則記作則記作v vw w+* *+例例 文法文法G G： S0S1 S0S1， S01 S01 S S 0 0S S1 1 0 00 0S S1 11 1 00000 0S S1 111 11 0000000101111 111 S S 0000111100001111S S 0000111100001111 S S S S +*4句型、句子、語(yǔ)言的定義句型、句子、語(yǔ)言的定義q句型和句子句型和句子設(shè)有文法設(shè)有文法GSGS，若

20、符號(hào)串若符號(hào)串x x是從開(kāi)始符推導(dǎo)出來(lái)的是從開(kāi)始符推導(dǎo)出來(lái)的, ,即即S S x x，則稱(chēng)則稱(chēng)x x是文法是文法G G的的句型句型。若。若x x僅由終結(jié)符僅由終結(jié)符組成組成, ,即即S S x x，且且xVxVT T* *，則稱(chēng)則稱(chēng)x x是文法是文法G G的的句子句子。例例 文法文法GSGS： S0S1 S0S1， S01 S01S S 0 0S S1 1 0 00 0S S1 11 1 00000 0S S1 111 11 0000000101111111S,S,0S1 ,00S11 ,000S111,000011110S1 ,00S11 ,000S111,00001111都是都是G G的句

21、型的句型0000111100001111是是G G的句子的句子*q語(yǔ)言的定義語(yǔ)言的定義由文法由文法G G生成的語(yǔ)言記為生成的語(yǔ)言記為L(zhǎng)(G),L(G),它是文法它是文法G G的一切句的一切句子的集合子的集合, ,即即 L(G)=x|S L(G)=x|S x x，其中其中S S為文法的開(kāi)始符號(hào)，為文法的開(kāi)始符號(hào)，且且x Vx VT T* * 例例 文法文法G G： S0S1 S0S1， S01 S01S0S1 00S11 03S13 0n-1S1n-1 0n1nL(G)=0L(G)=0n n1 1n n|n1|n1q文法和語(yǔ)言的關(guān)系：文法和語(yǔ)言的關(guān)系：文法文法G G生成的每個(gè)串都在生成的每個(gè)串都

22、在L(G)L(G)中中L(G)L(G)中的每個(gè)串確實(shí)能被中的每個(gè)串確實(shí)能被G G生成生成*根據(jù)文法，可以通過(guò)推導(dǎo)得到該文法相應(yīng)的語(yǔ)言；根據(jù)文法，可以通過(guò)推導(dǎo)得到該文法相應(yīng)的語(yǔ)言；例：例：GE E：EE+T|TEE+T|TTTTTF|FF|F F(E)|aF(E)|aE E E+T T+T F+T a+T a+TF a+FF a+aF a+aa表示一切能用符號(hào)表示一切能用符號(hào)a，+，(和和)構(gòu)成的算術(shù)表達(dá)式構(gòu)成的算術(shù)表達(dá)式有了語(yǔ)言的要求，也可以為該語(yǔ)言設(shè)計(jì)文法有了語(yǔ)言的要求，也可以為該語(yǔ)言設(shè)計(jì)文法例：若語(yǔ)言由例：若語(yǔ)言由0、1符號(hào)串組成，串中符號(hào)串組成，串中0和和1的個(gè)數(shù)相同，的個(gè)數(shù)相同，構(gòu)造其

23、文法為：構(gòu)造其文法為：A 0B|1CB 1|1A|0BBC 0|0A|1CC5文法的等價(jià)文法的等價(jià)若若L L（G G1 1）=L=L（G G2 2），），則稱(chēng)文法則稱(chēng)文法G G1 1和和G G2 2是等價(jià)是等價(jià)的。的。例如例如 文法文法G G1 1AA：A0R A01 RA1A0R A01 RA1 G G2 2SS：S0S1 S01S0S1 S01所定義的語(yǔ)言都是所定義的語(yǔ)言都是0 0n n1 1n n兩文法等價(jià)兩文法等價(jià)3.4 3.4 文法的類(lèi)型文法的類(lèi)型通過(guò)對(duì)產(chǎn)生式施加不同的限制，通過(guò)對(duì)產(chǎn)生式施加不同的限制，ChomskyChomsky將將文法分為四種類(lèi)型：文法分為四種類(lèi)型：q0 0型文法

24、型文法( (短語(yǔ)文法短語(yǔ)文法) )：對(duì)任一產(chǎn)生式：對(duì)任一產(chǎn)生式，都有都有(V(VN NVVT T) )* *且至少含有一個(gè)非終結(jié)且至少含有一個(gè)非終結(jié)符符; (V; (VN NVVT T) )* *q1 1型文法型文法( (上下文有關(guān)上下文有關(guān)) )：它是：它是0型文法的特例，設(shè)型文法的特例，設(shè)文文法法G=(VN,VT,P,S)，對(duì)對(duì)P P中的任一產(chǎn)生式中的任一產(chǎn)生式，都都有有| |， 僅僅僅僅 SS除外除外例例 文法文法GSGS： SaSBE SaSBE SaBESaBEEBBEEBBEaBab aBab bBbb bBbb bEbe bEbe eEeeeEee1型文法產(chǎn)生式的一般形式是型文法

25、產(chǎn)生式的一般形式是 A ， , V V* * ，AVAVN N , , VV+ +( (不能是空串不能是空串) ) ，它表示當(dāng)，它表示當(dāng)A的上文為的上文為 且下文為且下文為 時(shí)可把時(shí)可把A替換成替換成 ，因此稱(chēng)，因此稱(chēng)1型文法為上下型文法為上下文有關(guān)文法。文有關(guān)文法。 q2 2型文法（上下文無(wú)關(guān)文法）型文法（上下文無(wú)關(guān)文法） ：它是：它是1型文型文法的特例，對(duì)任一產(chǎn)生式法的特例，對(duì)任一產(chǎn)生式，都有都有V VN N ， (V(VN NVVT T) )* *例例 文法文法GSGS： SABSABABS|0ABS|0BSA|1BSA|12型文法產(chǎn)生式的一般形式是型文法產(chǎn)生式的一般形式是:A ，它表示

26、它表示不管不管A的上下文如何即可把的上下文如何即可把A替換成替換成 ，因此被，因此被稱(chēng)為上下文無(wú)關(guān)文法。稱(chēng)為上下文無(wú)關(guān)文法。通常程序設(shè)計(jì)語(yǔ)言的文法，可用通常程序設(shè)計(jì)語(yǔ)言的文法，可用2型文法來(lái)型文法來(lái)描述，因此我們重點(diǎn)研究描述，因此我們重點(diǎn)研究2型文法。型文法。 q3 3型文法型文法( (正規(guī)文法正規(guī)文法) )：它是：它是2 2型文法的特例，型文法的特例，任一產(chǎn)生式任一產(chǎn)生式的形式都為的形式都為AaBAaB或或AaAa，其中其中A A ，BVBVN N ，aVaVT T例如例如 文法文法GSGS：S0A|1B|0S0A|1B|0A0A|1B|0SA0A|1B|0SB1B|1|0B1B|1|0在程

27、序設(shè)計(jì)語(yǔ)言中，在程序設(shè)計(jì)語(yǔ)言中，3型文法通常用來(lái)描述型文法通常用來(lái)描述單詞的結(jié)構(gòu)。單詞的結(jié)構(gòu)。文法類(lèi)別文法類(lèi)別產(chǎn)生式形式產(chǎn)生式形式產(chǎn)生的語(yǔ)言產(chǎn)生的語(yǔ)言 說(shuō)明說(shuō)明0型文法型文法(短語(yǔ)文法短語(yǔ)文法)VV+ + , ,且至少含一且至少含一個(gè)非終結(jié)符，個(gè)非終結(jié)符，VV* *0型語(yǔ)言型語(yǔ)言對(duì)產(chǎn)生式對(duì)產(chǎn)生式基本無(wú)限基本無(wú)限制制1型文法型文法(上下文有關(guān)文法上下文有關(guān)文法)，| |1|1或或 A , , V V* *AVAVN N , , VV1型語(yǔ)言型語(yǔ)言（上下文有（上下文有關(guān)語(yǔ)言）關(guān)語(yǔ)言）將將A替換替換成成 時(shí)，必時(shí)，必須考慮須考慮A的上下文的上下文 ， 2型文法型文法(上下文無(wú)關(guān)文法上下文無(wú)關(guān)文法)A

28、A，AVAVN N ， VV* *2型語(yǔ)言型語(yǔ)言（上下文無(wú)（上下文無(wú)關(guān)語(yǔ)言）關(guān)語(yǔ)言）無(wú)需考慮無(wú)需考慮A在上下在上下文中的出文中的出現(xiàn)情況現(xiàn)情況3型文法型文法(正規(guī)文法正規(guī)文法)AaBAaB或或AaAa，A,BVA,BVN N ，aVaVT T3型語(yǔ)言型語(yǔ)言(正規(guī)語(yǔ)言正規(guī)語(yǔ)言)產(chǎn)生式全產(chǎn)生式全部是規(guī)定部是規(guī)定的形式的形式四種文法之間的逐級(jí)四種文法之間的逐級(jí)“包含包含”關(guān)系關(guān)系2型文法型文法1型文法型文法3型文法型文法0型文法型文法3.5 上下文無(wú)關(guān)文法及其語(yǔ)法樹(shù)上下文無(wú)關(guān)文法及其語(yǔ)法樹(shù)1上下文無(wú)關(guān)文法上下文無(wú)關(guān)文法(Context-Free Grammar)上下文無(wú)關(guān)文法有足夠的能力描述現(xiàn)今程序

29、設(shè)計(jì)上下文無(wú)關(guān)文法有足夠的能力描述現(xiàn)今程序設(shè)計(jì)語(yǔ)言的語(yǔ)法結(jié)構(gòu)語(yǔ)言的語(yǔ)法結(jié)構(gòu)例：算術(shù)表達(dá)式：例：算術(shù)表達(dá)式：Ei|E+E|E*E|（E）i:=Eif then | if then else 所以我們只關(guān)心上下文無(wú)關(guān)文法形成的語(yǔ)言中所以我們只關(guān)心上下文無(wú)關(guān)文法形成的語(yǔ)言中的句子的分析的句子的分析2. 規(guī)范推導(dǎo)和規(guī)范句型規(guī)范推導(dǎo)和規(guī)范句型q如果在推導(dǎo)的任何一步如果在推導(dǎo)的任何一步，其中其中、是句型，都是對(duì)是句型，都是對(duì)中的最左（最右）非中的最左（最右）非終結(jié)符進(jìn)行替換終結(jié)符進(jìn)行替換, ,則稱(chēng)這種推導(dǎo)為則稱(chēng)這種推導(dǎo)為最左最左( (最最右右) )推導(dǎo)推導(dǎo)q最右推導(dǎo)被稱(chēng)為最右推導(dǎo)被稱(chēng)為規(guī)范推導(dǎo)規(guī)范推導(dǎo)q由

30、規(guī)范推導(dǎo)所得的句型稱(chēng)為由規(guī)范推導(dǎo)所得的句型稱(chēng)為規(guī)范句型規(guī)范句型q例例 文法文法G：EE+T|T TTF|F F（E）|i句子句子i+ii的推導(dǎo)過(guò)程如下：的推導(dǎo)過(guò)程如下：最左推導(dǎo)：最左推導(dǎo)：E=E+T=T+T=F+T=i+T=i+TF=i+FF =i+iF=i+ii最右推導(dǎo)：最右推導(dǎo)：E=E+T=E+TF=E+Ti=E+Fi=E+ii = T+ii=F+ii=i+ii3.語(yǔ)法樹(shù)語(yǔ)法樹(shù)(推導(dǎo)樹(shù)推導(dǎo)樹(shù)Parse Tree)q 作用作用:直觀地描述上下文無(wú)關(guān)文法的直觀地描述上下文無(wú)關(guān)文法的句型句型推導(dǎo)過(guò)程推導(dǎo)過(guò)程。給定文法給定文法G=(VG=(VN N,V,VT T,P,S),P,S)，對(duì)于對(duì)于G G

31、的任何句型都能構(gòu)造與之關(guān)聯(lián)的語(yǔ)法樹(shù)的任何句型都能構(gòu)造與之關(guān)聯(lián)的語(yǔ)法樹(shù)q例：文法例：文法G：EE+T|TTTF|F F（E）|i句型句型T+TF的推導(dǎo)過(guò)程與語(yǔ)法樹(shù)的推導(dǎo)過(guò)程與語(yǔ)法樹(shù)EET+TFTE=E+TEET+TFTE=E+T =E+TF=T+TF=T+T=T+TF從語(yǔ)法樹(shù)中看不出句型中的符號(hào)被替代的順序從語(yǔ)法樹(shù)中看不出句型中的符號(hào)被替代的順序從左到右讀出葉子結(jié)從左到右讀出葉子結(jié)點(diǎn)得到的符號(hào)點(diǎn)得到的符號(hào)串串，為，為文法文法的的句型。也把該句型。也把該語(yǔ)法樹(shù)稱(chēng)為該句型的語(yǔ)法樹(shù)稱(chēng)為該句型的語(yǔ)法樹(shù)。語(yǔ)法樹(shù)。q語(yǔ)法樹(shù)定義語(yǔ)法樹(shù)定義:給定文法給定文法G=( VG=( VN N,V,VT T,P,S),P

32、,S)，若一棵樹(shù)滿(mǎn)足下列若一棵樹(shù)滿(mǎn)足下列4 4個(gè)條個(gè)條件，則稱(chēng)此樹(shù)為件，則稱(chēng)此樹(shù)為G G的語(yǔ)法樹(shù)：的語(yǔ)法樹(shù)：1.1.每個(gè)結(jié)點(diǎn)都有一個(gè)標(biāo)記，此標(biāo)記是每個(gè)結(jié)點(diǎn)都有一個(gè)標(biāo)記，此標(biāo)記是V V的一個(gè)符號(hào)的一個(gè)符號(hào)2.2.根的標(biāo)記是根的標(biāo)記是S S（開(kāi)始符號(hào)）（開(kāi)始符號(hào)）3.3.若一結(jié)點(diǎn)若一結(jié)點(diǎn)n n至少有一個(gè)它自己除外的子孫，并且至少有一個(gè)它自己除外的子孫，并且有標(biāo)記有標(biāo)記A A，則肯定則肯定AVAVN N4.4.如果結(jié)點(diǎn)如果結(jié)點(diǎn)n n有標(biāo)記有標(biāo)記A,A,其直接子孫結(jié)點(diǎn)從左到右的其直接子孫結(jié)點(diǎn)從左到右的次序是次序是n n1 1，n n2 2，n nk k，其標(biāo)記分別為其標(biāo)記分別為A A1 1，A A2

33、2，A Ak k，那么那么AAAA1 1A A2 2A Ak k一定是一定是P P中的一個(gè)中的一個(gè)產(chǎn)生式產(chǎn)生式文法文法G：EE+E|EE|（E）|i句子句子 ii+i 對(duì)應(yīng)的語(yǔ)法樹(shù)對(duì)應(yīng)的語(yǔ)法樹(shù)兩個(gè)不同的兩個(gè)不同的最左推導(dǎo)最左推導(dǎo)：推導(dǎo)推導(dǎo)1：E E+E EE+E iE+E ii+E ii+i推導(dǎo)推導(dǎo)2：E EE iE iE+E ii+E ii+iiEE+EEEiiEEEiEE+ii4.文法的二義性文法的二義性(Ambiguity)定義定義:如果一個(gè)文法存在某個(gè)句子對(duì)應(yīng)兩棵不同的語(yǔ)法樹(shù)，如果一個(gè)文法存在某個(gè)句子對(duì)應(yīng)兩棵不同的語(yǔ)法樹(shù)，則說(shuō)這個(gè)文法是二義的。則說(shuō)這個(gè)文法是二義的。二義性文法存在某個(gè)句

34、子二義性文法存在某個(gè)句子, ,它它有兩個(gè)不同的最左（右）推導(dǎo)有兩個(gè)不同的最左（右）推導(dǎo)對(duì)于一個(gè)程序設(shè)計(jì)語(yǔ)言來(lái)說(shuō)，希望它的文法是無(wú)二義對(duì)于一個(gè)程序設(shè)計(jì)語(yǔ)言來(lái)說(shuō)，希望它的文法是無(wú)二義的，因?yàn)橄Ｍ麑?duì)它的每個(gè)語(yǔ)句的分析是唯一的。的，因?yàn)橄Ｍ麑?duì)它的每個(gè)語(yǔ)句的分析是唯一的。文法文法G：E E+E| EE|（E）| i文法文法G：ET|E+TTF|TFF(E)| i等價(jià)的無(wú)等價(jià)的無(wú)二義文法二義文法3.6 句型的分析句型的分析q任務(wù)任務(wù): 句型分析就是識(shí)別一個(gè)符號(hào)串是否為句型分析就是識(shí)別一個(gè)符號(hào)串是否為某文法的句型，是某個(gè)推導(dǎo)的構(gòu)造過(guò)程。某文法的句型，是某個(gè)推導(dǎo)的構(gòu)造過(guò)程。對(duì)于程序設(shè)計(jì)語(yǔ)言來(lái)說(shuō)，句型分析就是一

35、對(duì)于程序設(shè)計(jì)語(yǔ)言來(lái)說(shuō)，句型分析就是一個(gè)識(shí)別輸入符號(hào)串是否為語(yǔ)法上正確的程個(gè)識(shí)別輸入符號(hào)串是否為語(yǔ)法上正確的程序的過(guò)程。序的過(guò)程。q從左到右的分析算法從左到右的分析算法，即總是從左到右地，即總是從左到右地識(shí)別輸入符號(hào)串識(shí)別輸入符號(hào)串.句型分析算法采用從左到句型分析算法采用從左到右的分析算法右的分析算法q句型的分析算法句型的分析算法分類(lèi)分類(lèi)自上而下分析法自上而下分析法 (Top-Down parsing)自下而上分析法自下而上分析法 (Bottom-Up parsing)3.6.1 自上而下的分析方法自上而下的分析方法q定義定義:從文法的開(kāi)始符號(hào)出發(fā)，反復(fù)使用文法的從文法的開(kāi)始符號(hào)出發(fā)，反復(fù)使用文

36、法的產(chǎn)生式，尋找與輸入符號(hào)串匹配的推導(dǎo)。產(chǎn)生式，尋找與輸入符號(hào)串匹配的推導(dǎo)。語(yǔ)法樹(shù)的構(gòu)造：將文法的開(kāi)始符號(hào)作為語(yǔ)語(yǔ)法樹(shù)的構(gòu)造：將文法的開(kāi)始符號(hào)作為語(yǔ)法樹(shù)的根，向下逐步建立語(yǔ)法樹(shù)，使語(yǔ)法法樹(shù)的根，向下逐步建立語(yǔ)法樹(shù)，使語(yǔ)法樹(shù)的末端結(jié)點(diǎn)符號(hào)串正好是輸入符號(hào)串。樹(shù)的末端結(jié)點(diǎn)符號(hào)串正好是輸入符號(hào)串。例例 文法文法G：S cAd A ab A a識(shí)別輸入串識(shí)別輸入串w=cabd是否為該文法的句子是否為該文法的句子S推導(dǎo)過(guò)程：推導(dǎo)過(guò)程：cAdab=cabdS =cAdq自上而下方法的主要問(wèn)題自上而下方法的主要問(wèn)題對(duì)輸入串對(duì)輸入串cabd自上而下構(gòu)造語(yǔ)法樹(shù)的另一過(guò)程自上而下構(gòu)造語(yǔ)法樹(shù)的另一過(guò)程不成功，不成功

37、，不成功的原因不成功的原因是選錯(cuò)產(chǎn)生式是選錯(cuò)產(chǎn)生式Aa自上而下分析的主要問(wèn)題是選擇產(chǎn)生式自上而下分析的主要問(wèn)題是選擇產(chǎn)生式 :假定要被代換的最左非終結(jié)符號(hào)是假定要被代換的最左非終結(jié)符號(hào)是B B，且有且有n n條規(guī)則：條規(guī)則：BABA1 1|A|A2 2| |A|An n，那么如何確定用那么如何確定用哪個(gè)右部去替代哪個(gè)右部去替代B B？ScA da3.6.2 自下而上的分析方法自下而上的分析方法q定義定義:從輸入符號(hào)串開(kāi)始，逐步進(jìn)行歸約，從輸入符號(hào)串開(kāi)始，逐步進(jìn)行歸約，直至歸約到文法的開(kāi)始符號(hào)。直至歸約到文法的開(kāi)始符號(hào)。語(yǔ)法樹(shù)的構(gòu)造：從輸入符號(hào)串開(kāi)始，以它語(yǔ)法樹(shù)的構(gòu)造：從輸入符號(hào)串開(kāi)始，以它作為

38、語(yǔ)法樹(shù)的末端結(jié)點(diǎn)符號(hào)串，自底向上作為語(yǔ)法樹(shù)的末端結(jié)點(diǎn)符號(hào)串，自底向上的構(gòu)造語(yǔ)法樹(shù)的構(gòu)造語(yǔ)法樹(shù)例例 文法文法G：S cAd A ab A a識(shí)別輸入串識(shí)別輸入串w=cabd是否為該文法的句子是否為該文法的句子cabd歸約過(guò)程：歸約過(guò)程：用用“|-”表示歸表示歸約，下劃線(xiàn)部分約，下劃線(xiàn)部分為被歸約符號(hào)為被歸約符號(hào)cabd |-cAd |-SASq自下而上分析的主要問(wèn)題自下而上分析的主要問(wèn)題對(duì)輸入串對(duì)輸入串cabd的兩種歸約過(guò)程的兩種歸約過(guò)程（1）cabd|-cAd|-S 歸約到開(kāi)始符歸約到開(kāi)始符（2）cabd|-cAbd 不能歸約到開(kāi)始符不能歸約到開(kāi)始符在自下而上的分析方法中，每一步都是在自下而上

39、的分析方法中，每一步都是從當(dāng)前串中選擇一個(gè)子串加以歸約，該從當(dāng)前串中選擇一個(gè)子串加以歸約，該子串暫稱(chēng)子串暫稱(chēng)“可歸約串可歸約串”。如何確定如何確定“可歸約串可歸約串”是自下而上分析的是自下而上分析的主要問(wèn)題。主要問(wèn)題。為了刻劃為了刻劃“可歸約串可歸約串”,引入下面的概念引入下面的概念q短語(yǔ)，直接短語(yǔ)和句柄短語(yǔ)，直接短語(yǔ)和句柄定義定義:設(shè)設(shè)是文法是文法GS中的一個(gè)句型，如果中的一個(gè)句型，如果有有SA且且A，則稱(chēng)則稱(chēng)是句型是句型相相對(duì)于非終結(jié)符對(duì)于非終結(jié)符A的的短語(yǔ)短語(yǔ)特別的如有特別的如有A，則稱(chēng)則稱(chēng)是句型是句型相對(duì)相對(duì)于規(guī)則于規(guī)則A的的直接短語(yǔ)直接短語(yǔ)。一個(gè)句型的最左直接短語(yǔ)稱(chēng)為該句型的一個(gè)句型

40、的最左直接短語(yǔ)稱(chēng)為該句型的句柄句柄(Handle)。句柄就是句柄就是“可歸約串可歸約串”* *+ 對(duì)定義的分析：對(duì)定義的分析：在短語(yǔ)的定義中包括了三個(gè)條件：在短語(yǔ)的定義中包括了三個(gè)條件： 是文法的一個(gè)句型；是文法的一個(gè)句型； S A; A 。這三個(gè)條件都必須滿(mǎn)足。這三個(gè)條件都必須滿(mǎn)足。(1)(2)說(shuō)明說(shuō)明 、 A都必須是句型都必須是句型(2)(3)說(shuō)明，將說(shuō)明，將中的中的歸約歸約A后，得到的后，得到的A一定要是句型。假如符號(hào)串一定要是句型。假如符號(hào)串 ，將其歸約將其歸約成成A后得到的符號(hào)串不能由開(kāi)始符號(hào)推出，后得到的符號(hào)串不能由開(kāi)始符號(hào)推出，則則不是短語(yǔ)。不是短語(yǔ)。* *+例：文法例：文法GE

41、: EE+T|T TTF|F F（E）| i 的一個(gè)句型是的一個(gè)句型是 TF+i，相應(yīng)的語(yǔ)法樹(shù)見(jiàn)右圖：相應(yīng)的語(yǔ)法樹(shù)見(jiàn)右圖：EET+TTFFi1 因?yàn)橐驗(yàn)镋 T+i 且且 T TF，所所以以TF是句型相對(duì)于是句型相對(duì)于T的短語(yǔ)，且是的短語(yǔ)，且是相對(duì)于相對(duì)于TTF的直接短語(yǔ)的直接短語(yǔ)2 因?yàn)橐驗(yàn)镋 TF+F 且且 F i，所所以以i是句型相對(duì)于是句型相對(duì)于F的短語(yǔ)，且是相對(duì)的短語(yǔ)，且是相對(duì)于于Fi的直接短語(yǔ)的直接短語(yǔ)3 因?yàn)橐驗(yàn)镋 E 且且E TF+i，所以所以TF+i是句型相對(duì)于是句型相對(duì)于E的短語(yǔ)的短語(yǔ)4 TF是最左直接短語(yǔ)，即是最左直接短語(yǔ)，即句柄句柄 * * * *+ +文法文法GE:EE+T|TTTF|FF（E）|i的一個(gè)句型的一個(gè)句型 是是TF+iEET+TTFFi雖然雖然F+i是句型是句型TF+i的一部分，的一部分，但不是短語(yǔ)，因?yàn)楸M管有但不是短語(yǔ)，因?yàn)楸M管有E F+i，但是不存在從文法開(kāi)始符但是不存在從文法開(kāi)始符E TE的推導(dǎo)的推導(dǎo)+ +* *q短語(yǔ)與語(yǔ)法樹(shù)短語(yǔ)與語(yǔ)法樹(shù)從句型的語(yǔ)法樹(shù)上很容易找出句型的短語(yǔ)從句型的語(yǔ)法樹(shù)上很容易找出句型的短語(yǔ)語(yǔ)法樹(shù)中每棵子樹(shù)的末端結(jié)點(diǎn)構(gòu)成相對(duì)于子樹(shù)根語(yǔ)法樹(shù)中每棵子樹(shù)的末端結(jié)點(diǎn)構(gòu)成相對(duì)于子樹(shù)根的短語(yǔ)的短語(yǔ) 例：文法例：文法GE的句型的句型TF+i語(yǔ)法樹(shù)：語(yǔ)法樹(shù)：EET+TTFFi