第2章1文法和語(yǔ)言課件

第二章文法和語(yǔ)言一、文法的概念二、符號(hào)和符號(hào)串三、文法和語(yǔ)言的定義四、文法的類型五、上下文無(wú)關(guān)文法及其語(yǔ)法樹(shù)7/23/20231莆田學(xué)院許振和本章要求主要內(nèi)容：符號(hào)串，文法的概念及分類，語(yǔ)言的定義過(guò)程重點(diǎn)掌握：上下文無(wú)關(guān)文法、推導(dǎo)、句型、句子、語(yǔ)言，語(yǔ)法樹(shù)、二義性文法、文法的語(yǔ)言生成過(guò)程7/23/20232莆田學(xué)院許振和構(gòu)結(jié)識(shí)知文法和語(yǔ)言符號(hào)和符號(hào)串字母表和符號(hào)串符號(hào)串集合的運(yùn)算文法和語(yǔ)言的形式定義文法的形式定義語(yǔ)言的形式定義語(yǔ)法分析的基本術(shù)語(yǔ)規(guī)則文法推導(dǎo)和規(guī)約句型/句子/語(yǔ)言短語(yǔ)和句柄最左最右推導(dǎo)和規(guī)約語(yǔ)法樹(shù)和二義性語(yǔ)法樹(shù)的構(gòu)造語(yǔ)法樹(shù)與短語(yǔ)文法的二義性文法的實(shí)用限制7/23/20233莆田學(xué)院許振和語(yǔ)言是由單詞按一定規(guī)則（文法）組成句子來(lái)表達(dá)特定意思。故對(duì)語(yǔ)言的分析集中于對(duì)句子的分析。而句子的分析依據(jù)語(yǔ)言的文法規(guī)則。程序設(shè)計(jì)語(yǔ)言可以通過(guò)描述以下兩個(gè)要素來(lái)定義：

第一方面是程序模式，即語(yǔ)言的語(yǔ)法；第二方面是程序含義，即語(yǔ)言的語(yǔ)義。文法與語(yǔ)言語(yǔ)義分為兩類：

靜態(tài)語(yǔ)義動(dòng)態(tài)語(yǔ)義7/23/20234莆田學(xué)院許振和一、文法的概念所謂一個(gè)語(yǔ)言的語(yǔ)法是指一組規(guī)則，用它可以形成和產(chǎn)生一個(gè)合適的程序。由單詞符號(hào)按照一定的規(guī)則構(gòu)成各種類型的表達(dá)式、語(yǔ)句、分程序（程序），即不同的語(yǔ)法范疇。不同的語(yǔ)法范疇具有不同的構(gòu)成規(guī)律。單詞符號(hào)的構(gòu)成規(guī)則稱為詞法規(guī)則。各種語(yǔ)法范疇構(gòu)成規(guī)則稱為語(yǔ)法規(guī)則。描述詞法規(guī)則和語(yǔ)法規(guī)則的工具是文法。文法表示用語(yǔ)法圖(語(yǔ)法樹(shù))和EBNF(巴科斯-諾爾)描述。目前廣泛使用的手段是上下文無(wú)關(guān)文法，即用上下文無(wú)關(guān)文法作為程序設(shè)計(jì)語(yǔ)言語(yǔ)法的描述工具。7/23/20235莆田學(xué)院許振和語(yǔ)言語(yǔ)法：是一組規(guī)則,定義符號(hào)如何排列，排列與符號(hào)含義無(wú)關(guān)。即程序的結(jié)構(gòu)或形式語(yǔ)義：研究語(yǔ)言所代表的含義語(yǔ)用：語(yǔ)言的實(shí)際應(yīng)用語(yǔ)言的表示方法1、用識(shí)別的觀點(diǎn)表示語(yǔ)言，這種方法是給出一種算法由它判定一個(gè)句子是否在語(yǔ)言中。2、用產(chǎn)生的觀點(diǎn)表示語(yǔ)言7/23/20236莆田學(xué)院許振和〈句子〉∷=〈主語(yǔ)〉〈謂語(yǔ)〉〈主語(yǔ)〉∷=〈代詞〉|〈名詞〉〈代詞〉∷=我|你|他〈名詞〉∷=王明|大學(xué)生|工人|英語(yǔ)〈謂語(yǔ)〉∷=〈動(dòng)詞〉〈直接賓語(yǔ)〉〈動(dòng)詞〉∷=是|學(xué)習(xí)〈直接賓語(yǔ)〉∷=〈代詞〉|<名詞>先舉個(gè)例子：用EBNF表示7/23/20237莆田學(xué)院許振和推導(dǎo)：你是大學(xué)生

〈句子〉〈主語(yǔ)〉〈謂語(yǔ)〉〈代詞〉〈謂語(yǔ)〉你〈謂語(yǔ)〉你〈動(dòng)詞〉〈直接賓語(yǔ)〉你是〈名詞〉你是大學(xué)生由上一組規(guī)則可以產(chǎn)生句子：你是大學(xué)生

這樣的語(yǔ)言描述稱為文法“=>”表示由某條規(guī)則的右部替換該規(guī)則的左部，把它稱之為推導(dǎo)。7/23/20238莆田學(xué)院許振和語(yǔ)句“小八哥吃大花生”分析的語(yǔ)法樹(shù)上下〈句子〉〈主語(yǔ)〉〈謂語(yǔ)〉〈形容詞〉〈名詞〉〈動(dòng)詞〉〈賓語(yǔ)〉小八哥吃〈形容詞〉〈名詞〉

大 花生7/23/20239莆田學(xué)院許振和句子的推導(dǎo)

<句子>?<主語(yǔ)><謂語(yǔ)>

?<形容詞><名詞><謂語(yǔ)>

?<小><名詞><謂語(yǔ)>

?<小><八哥><謂語(yǔ)>

?<小><八哥><動(dòng)><賓語(yǔ)>

?小八哥吃<賓語(yǔ)>

?小八哥吃<形容詞><名詞>

?小八哥吃大<名詞>

?小八哥吃大花生7/23/202310莆田學(xué)院許振和〈謂語(yǔ)〉〈主語(yǔ)〉〈形容詞〉〈名詞〉〈動(dòng)詞〉〈賓語(yǔ)〉小八哥吃花生大

下〈形容詞〉〈名詞〉上

〈句子〉句子的歸約7/23/202311莆田學(xué)院許振和二、符號(hào)和符號(hào)串

任何一種語(yǔ)言，都是由該語(yǔ)言的基本字符所組成的字符串的集合。1、語(yǔ)言可以看成在一個(gè)基本符號(hào)集上定義的，按一定規(guī)則構(gòu)成的一切基本符號(hào)串組成的集合。2、字母表(符號(hào)集)：是字母的有窮非空集合。用希臘字母∑或大寫英文字母等表示字母表。3、符號(hào)（字符）：字母表中的元素。因此字母表也稱為符號(hào)集。用集合元素表示形式枚舉字母表中的符號(hào)。符號(hào)是該語(yǔ)言能識(shí)別的符號(hào)，字母表是該語(yǔ)言能識(shí)別的所有符號(hào)的全體（字符集）

4、符號(hào)串(字符串)：字母表的符號(hào)組成任何有窮序列。例：∑={0，1}—符號(hào)集符號(hào)串有：0，1，00，01，10，117/23/202312莆田學(xué)院許振和例：∑={a，b，c}—符號(hào)集符號(hào)串有：a，b，c，ab，aaca

在符號(hào)串中，符號(hào)的順序是很重要的，符號(hào)串a(chǎn)b就不同于ba,abca和aabc也不同。

【注】不同排列順序表示不同的含義。5、符號(hào)串集合：字母表上若干個(gè)符號(hào)串組成的集合。6、符號(hào)串的長(zhǎng)度：符號(hào)串x有m個(gè)符號(hào)，則長(zhǎng)度就為m，表示|x|=m。

如：ababa

則長(zhǎng)度是5。定義在字母表Σ={x,，y，z，=，0，1，+，;}

上的符號(hào)串|x=y++；z=0;|=107、空符號(hào)串：用ε表示，長(zhǎng)度為0，||=0

若符號(hào)串x,則有εx=xε=x7/23/202313莆田學(xué)院許振和8、符號(hào)串的運(yùn)算：(1)符號(hào)串的頭(前綴)和尾(后綴)

若z=xy,則x是z的頭，y是z的尾。例：設(shè)z=abc,則z的頭是ε，a，ab，abc

則z的尾是ε，c，bc，abc（2）符號(hào)串的固有頭(真前綴)和固有尾(真后綴)

若z=xy符號(hào)串，x非空，則y固有尾；若y非空，則x是固有頭。例：設(shè)z=abc，則z的固有頭是ε，a，ab

則z的固有尾是ε，c，bc7/23/202314莆田學(xué)院許振和（3）子符號(hào)串（子串）

從一個(gè)符號(hào)串中刪去它的一個(gè)前綴或(和)一個(gè)后綴之后剩余的部分稱為該符號(hào)串的子符號(hào)串或子串。例如:x=abcd

則ε,a,b,c,ab,bc,cd,abc,bcd及abcd都是

x的子字符串。 而ac，ad，cb，bd，ba

等都不是x的子字符串。7/23/202315莆田學(xué)院許振和（4）符號(hào)串的連接：

設(shè)x，y是符號(hào)串，連接xy是y符號(hào)寫在x符號(hào)之后。記作xy。例如，設(shè)有字符串j=abc，k=xyz

則jk=abcxyz，kj=xyzabc。連接運(yùn)算是有序的。一般來(lái)說(shuō)xy≠yx，僅當(dāng)x=y 或其中之一為ε時(shí),有xy=yx。顯然：εx=xε=x(5)符號(hào)串的方冪：設(shè)x是符號(hào)串，則z=xx……xx，稱z為x的方冪,記z=xn。因此x0=ε,x1=x,x2=xx,x3=xxx

顯然n>0時(shí),有xn

=x·xn-1＝xn-1·xn個(gè)7/23/202316莆田學(xué)院許振和

(6)符號(hào)串的集合：

若集合A中的一切元素都是某字母表上的符號(hào)串，則稱A為該字母表上的符號(hào)串集合。兩個(gè)符號(hào)串集合A、B乘積定義：

AB={xy|x∈A且y∈B}

例：A={a,b}，B={c,d}

則AB={ac，ad，bc，bd}注意：有{ε}A=A{ε}=A,?A=A?=?

，其中?為空集。 ?≠{ε} ?={}≠{ε}

。7/23/202317莆田學(xué)院許振和

(7)閉包（∑*）字母表∑，用∑*表示∑上所有有窮長(zhǎng)的串集合，∑*稱為∑的閉包。例：字母表∑={0,1}

則∑*={ε,0,1,00,01,10,11,000,001,010……}=∑0∪∑1∪∑2∪.…∪∑n

(8)正閉包(∑+)∑+=∑1∪∑2∪.…∪∑n

∑+稱∑的正閉包。顯然：∑*＝∑0∪∑+∑+＝∑∑*＝∑*∑根據(jù)集合乘積的定義7/23/202318莆田學(xué)院許振和如何來(lái)描述一種語(yǔ)言？如果語(yǔ)言是有窮的（只含有有窮多個(gè)句子），可以將句子逐一列出來(lái)表示如果語(yǔ)言是無(wú)窮的，找出語(yǔ)言的有窮表示。語(yǔ)言的有窮表示有兩個(gè)途經(jīng)：

三、文法和語(yǔ)言的形式定義生成方式（文法）：語(yǔ)言中的每個(gè)句子可以用嚴(yán)格定義的規(guī)則來(lái)構(gòu)造。識(shí)別方式（自動(dòng)機(jī)）：用一個(gè)過(guò)程，當(dāng)輸入的一任意串屬于語(yǔ)言時(shí)，該過(guò)程經(jīng)有限次計(jì)算后就會(huì)停止并回答“是”，若不屬于，要麼能停止并回答“不是”，（要麼永遠(yuǎn)繼續(xù)下去。）7/23/202319莆田學(xué)院許振和

1、規(guī)則（產(chǎn)生式、生成式）

形如→β或

::=β是字母表V的正閉包V+的一個(gè)符號(hào)；

β是字母表V的閉包V*的一個(gè)符號(hào)；稱規(guī)則的左部，β稱規(guī)則的右部。2、文法的定義〈1〉文法G定義為四元組（VN，VT，P，S）文法中規(guī)則P的第一種表示法7/23/202320莆田學(xué)院許振和其中：VN——非終結(jié)符號(hào)集

VT——終結(jié)符號(hào)集

P——產(chǎn)生式（規(guī)則）

S——開(kāi)始符號(hào)或稱作識(shí)別符號(hào)，它是一個(gè)非終結(jié)符，至少要在一條規(guī)則中作為左部出現(xiàn)。規(guī)定：（1）VN，VT，P是有窮非空集合；（2）VN∩VT＝

（不含公共元素）V=VN∪VT，稱為文法G的字母表（字匯表）7/23/202321莆田學(xué)院許振和例1文法G=（VN，VT，P，S），其中VN={S}，VT={0，1}，

P={S→0S1，S→01}。非終結(jié)符集中只含一個(gè)元素S；終結(jié)符集由兩個(gè)元素0和1組成；有兩條產(chǎn)生式；開(kāi)始符號(hào)是S。明顯求出：S＝{01，0011，000111，…}7/23/202322莆田學(xué)院許振和例2文法G=（VN，VT，P，S）其中VN={標(biāo)識(shí)符，字母，數(shù)字}VT={a,b,c,…,x,y,z,0,1,…,9}

P={<標(biāo)識(shí)符>→〈字母〉<標(biāo)識(shí)符>→<標(biāo)識(shí)符><字母〉<標(biāo)識(shí)符>→<標(biāo)識(shí)符><數(shù)字〉<字母>→a

<字母>→b…<字母>→z<數(shù)字>→1…<數(shù)字>→9｝S＝<標(biāo)識(shí)符>“<>”表示非終結(jié)符7/23/202323莆田學(xué)院許振和<2>文法中規(guī)則P的第二種表示法：上例1改為：G:S→0S1S→01<3>文法中規(guī)則P的第三種表示法：上例1改為：G[S]:S→0S1S→01一般約定，第一條產(chǎn)生式的左部是識(shí)別符號(hào)；用尖括號(hào)括起來(lái)的是非終結(jié)符號(hào)，不用尖括號(hào)括起來(lái)的是終結(jié)符號(hào)，或者用大寫字母表示非終結(jié)符號(hào)，小寫字母表示終結(jié)符號(hào)。7/23/202324莆田學(xué)院許振和<1>→

是文法G=（VN，VT，P，S）的規(guī)則，和是V*中的任意符號(hào)，若有符號(hào)V，W滿足：

V=

，W＝

則說(shuō)V是直接產(chǎn)生W

或W是V的直接推導(dǎo)或W直接規(guī)約到V記作VW3、直接推導(dǎo)“=>”

從識(shí)別符號(hào)開(kāi)始，不斷將當(dāng)前符號(hào)串中的非終結(jié)符號(hào)替換為該符號(hào)的某個(gè)規(guī)則的右部。直到當(dāng)前的符號(hào)串中所有的符號(hào)都是終結(jié)符號(hào)為止。7/23/202325莆田學(xué)院許振和若有VW，或V=W，則記作VW(0步或若干步)

例子：在例1中存在序列：V＝0S100S11000S11100001111＝W記作：0S1000011110S100001111+＋+*若存在直接推導(dǎo)的序列：

V=W0

W1W2…Wn

＝W(n>0)則稱V推導(dǎo)W(或W規(guī)約到V)，記VW(至少一步)

*一樣的7/23/202326莆田學(xué)院許振和4、句型的定義設(shè)G[S]是文法，如果符號(hào)串x是從識(shí)別符號(hào)（開(kāi)始符號(hào)）推導(dǎo)出來(lái)的（即Sx）則稱x是文法G[S]的句型。若x僅由終結(jié)符號(hào)組成（SxxVT*）則稱x為G[S]的句子。**例：S，0S1，000111都是文法G的句型，000111是G的句子?！冀Y(jié)論〗句子一定是句型，句型不一定是句子。7/23/202327莆田學(xué)院許振和5、語(yǔ)言的定義：

L(G)表示文法G產(chǎn)生的語(yǔ)言定義為：集合｛xSx，S為文法開(kāi)始符號(hào)，

xVT*

｝該集合為語(yǔ)言，用L(G)表示。從定義可知：x是句型且x是文法G的句子。注：語(yǔ)言是文法所產(chǎn)生的所有句子組成的集合。例：例1的句子表示為：

L(G)＝｛0n1n

n1｝因?yàn)镾0S100S11…0n1n重復(fù)利用規(guī)則S0S1*7/23/202328莆田學(xué)院許振和四、文法的類型：科學(xué)家Chomsky把文法分成以下四種類型：0型短語(yǔ)文法1型上下文有關(guān)文法2型上下文無(wú)關(guān)文法3型正規(guī)文法文法類型逐漸增加限制如果文法是正規(guī)文法一定也是上下文無(wú)關(guān)文法7/23/202329莆田學(xué)院許振和文法的類型2型文法1型文法0型文法四種文法之間的逐級(jí)“包含”關(guān)系3型文法7/23/202330莆田學(xué)院許振和設(shè)G=(VN,VT,P,S)，如果它的每一個(gè)產(chǎn)生式滿足：(VN∪VT)*且至少包含一個(gè)非終結(jié)符，(VN∪VT)*，則G是0型文法。

0型文法又稱為無(wú)限制文法，有時(shí)也稱為短語(yǔ)文法。0型文法對(duì)應(yīng)的語(yǔ)言稱為0型語(yǔ)言或稱遞歸可枚舉集，它們的識(shí)別系統(tǒng)為圖靈機(jī)（Turing機(jī)）。設(shè)G=(VN,VT,P,S)，如果它的每一個(gè)產(chǎn)生式滿足：||≥||，僅僅S除外，則文法G是1型文法。7/23/202331莆田學(xué)院許振和下文只講上下文無(wú)關(guān)文法和正規(guī)文法

4個(gè)文法類的定義是逐漸增加限制的，因此，每一種正規(guī)文法都是上下文無(wú)關(guān)的，每一種上下文無(wú)關(guān)文法都是上下文有關(guān)的，而每一種上下文有關(guān)文法都是0型文法。1型文法相對(duì)應(yīng)的語(yǔ)言稱為1型語(yǔ)言或上下文有關(guān)語(yǔ)言，它的識(shí)別系統(tǒng)是線性界限自動(dòng)機(jī)。7/23/202332莆田學(xué)院許振和1、上下文無(wú)關(guān)文法：設(shè)G=（VN，VT，P，S），若P中的每一個(gè)產(chǎn)生式→滿足：

是一非終結(jié)符，(VN∪VT)*，則此文法稱為上下文無(wú)關(guān)文法(2型文法)。

2型文法相對(duì)應(yīng)的語(yǔ)言稱為2型語(yǔ)言或上下文無(wú)關(guān)語(yǔ)言，它的識(shí)別系統(tǒng)為下推自動(dòng)機(jī)(PDA)。例6：G＝({S,A,B},{a,b},P,S)，P的產(chǎn)生式如下：S→aB

S→bAA→bAA

A→aA→aSB→bB→bSB→aBB上下文無(wú)關(guān)文法7/23/202333莆田學(xué)院許振和該文法可以寫成：S→aB

|bAA→a

|aS|bAAB→b|Bs|aBB2、正規(guī)文法：設(shè)G=（VN，VT，P，S），若P中的每一個(gè)產(chǎn)生式都是A→aB或A→a，A,B都是非終結(jié)符，a是終結(jié)符，則G是正規(guī)文法（也稱右線性文法）。

3型文法對(duì)應(yīng)的語(yǔ)言稱為3型語(yǔ)言或正規(guī)語(yǔ)言（正則語(yǔ)言，或正則集）。7/23/202334莆田學(xué)院許振和例6：G＝({S,A,B},{0,1},P,S)，P的產(chǎn)生式如下：S→0AS→1BS→0A→0SA→0AA→1BB→1B→0B→1B正規(guī)文法該文法可以寫成：S→0|0A|1BA→0S|0A|1BB→0|1|1B7/23/202335莆田學(xué)院許振和

Chomsky語(yǔ)言層，對(duì)應(yīng)的文法、語(yǔ)言和自動(dòng)機(jī)關(guān)系如圖2-2所示。圖2-2Chomsky文法、語(yǔ)言及自動(dòng)機(jī)關(guān)系7/23/202336莆田學(xué)院許振和五、上下文無(wú)關(guān)文法及其語(yǔ)法樹(shù)1、語(yǔ)法樹(shù)（推導(dǎo)樹(shù)）的定義：給定文法G=（VN，VT，P，S），對(duì)于G的任何句型都能構(gòu)造與之關(guān)聯(lián)的語(yǔ)法樹(shù)，須滿足條件為：

每個(gè)結(jié)點(diǎn)都有一個(gè)標(biāo)記，此標(biāo)記是V的一個(gè)符號(hào)。

根的標(biāo)記是S。

若一結(jié)點(diǎn)n至少有一個(gè)它自己除外的子孫，并且有標(biāo)記A，則A肯定在VN中。

如果結(jié)點(diǎn)n的直接子孫，從左到右的次序是結(jié)點(diǎn)n1,n2,…,nK，其標(biāo)記分別為A1,A2,…,AK

，那么AA1A2…AK一定是P中的一個(gè)產(chǎn)生式。描述上下文無(wú)關(guān)文法的句型推導(dǎo)的直觀方法。7/23/202337莆田學(xué)院許振和例8：G=({S,A},{a,b},P,S)，其中P為：SaASASbAASSSaAba語(yǔ)法樹(shù)：SaASaSbAaab說(shuō)明語(yǔ)法樹(shù)滿足：樹(shù)根是S。每個(gè)節(jié)點(diǎn)的標(biāo)記都是V的一個(gè)符號(hào)。A有自己的子孫(S,b,A)，AVN中。SbA是A

SbA的產(chǎn)生式，aAS是S

aAS的產(chǎn)生式。7/23/202338莆田學(xué)院許振和結(jié)點(diǎn)：每個(gè)樹(shù)的結(jié)點(diǎn)對(duì)應(yīng)于一個(gè)符號(hào)。結(jié)點(diǎn)的名字就是該符號(hào)。邊：兩個(gè)結(jié)點(diǎn)之間的連線。根結(jié)點(diǎn)：沒(méi)有邊進(jìn)入的結(jié)點(diǎn)。分支：某個(gè)結(jié)點(diǎn)向下射出的邊和其結(jié)點(diǎn)稱為分支。（父子結(jié)點(diǎn)，兄弟結(jié)點(diǎn)）子樹(shù)：語(yǔ)法樹(shù)的某個(gè)結(jié)點(diǎn)和它向下射出的部分。末端結(jié)點(diǎn)：沒(méi)有向下射出的邊的結(jié)點(diǎn)成為末端結(jié)點(diǎn)。在相對(duì)于句型的語(yǔ)法樹(shù)中，末端結(jié)點(diǎn)可能是非終結(jié)符號(hào)語(yǔ)法樹(shù)的相關(guān)概念7/23/202339莆田學(xué)院許振和葉子結(jié)點(diǎn)：樹(shù)中沒(méi)有子孫的結(jié)點(diǎn)。

從左到右讀出推導(dǎo)樹(shù)的葉子標(biāo)記連接成的文法符號(hào)串，為G[S]的句型。也把該推導(dǎo)樹(shù)稱為該句型的語(yǔ)法樹(shù)。語(yǔ)法樹(shù)的結(jié)果：從左到右讀出葉子的標(biāo)記而構(gòu)成的行謂之句子7/23/202340莆田學(xué)院許振和語(yǔ)法樹(shù)的理解：語(yǔ)法樹(shù)表示了在推導(dǎo)過(guò)程中用到什么樣的產(chǎn)生式和用到哪些非終結(jié)符，并沒(méi)有表明采用的順序。例9：上式推導(dǎo)樹(shù)是aabbaa句型的語(yǔ)法樹(shù)。推導(dǎo)如下：

SaASaAaaSbAaaSbbaaaabbaa

SaASaSbASaSbAaaabAaaabbaa

SaASaSbASaabASaabbaSaabbaa都是同一個(gè)語(yǔ)法樹(shù)7/23/202341莆田學(xué)院許振和2、最左推導(dǎo)（或最右推導(dǎo)）：若β（任何一條），、β是句型，都是對(duì)中的最左（最右）非終結(jié)符進(jìn)行替換，則稱為最左（最右）推導(dǎo)。在形式語(yǔ)言中，最右推導(dǎo)常被稱為規(guī)范推導(dǎo)。由規(guī)范推導(dǎo)所得的句型稱為規(guī)范句型。

一棵語(yǔ)法樹(shù)表示了一個(gè)句型的種種可能的(但未必是所有的)不同推導(dǎo)過(guò)程，包括最左(最右)推導(dǎo)。但是，一個(gè)句型是否只對(duì)應(yīng)唯一的一棵語(yǔ)法樹(shù)呢?一個(gè)句型是否只有唯一的一個(gè)最左(最右)推導(dǎo)呢?7/23/202342莆田學(xué)院許振和3、文法的二義性的定義：如果一個(gè)文法存在某個(gè)句子對(duì)應(yīng)兩棵不同的語(yǔ)法樹(shù)，則說(shuō)這個(gè)文法是二義的。若一個(gè)文法中存在某個(gè)句子，它有兩個(gè)不同的最左（最右）推導(dǎo)，則這個(gè)文法是二義的。一個(gè)句型是否只對(duì)應(yīng)唯一的一棵語(yǔ)法樹(shù)？一個(gè)句型是否只有唯一的一個(gè)最左（最右）推導(dǎo)？不是7/23/202343莆田學(xué)院許振和例10：文法G＝({E},{+，×，i，(，)}，P，E)，其中P為：EiEE+EEE×EE(E)則句型i×i+i的推導(dǎo)：推導(dǎo)1：EE+EE×E+Ei×E+Ei×i＋Ei×i＋i推導(dǎo)2：EE×Ei×Ei×E＋Ei×i＋Ei×i＋i產(chǎn)生兩個(gè)不同的語(yǔ)法樹(shù)：7/23/202344莆田學(xué)院許振和iEEE×iEE＋iEE＋EEE×iii該文法為二義性7/23/202345莆田學(xué)院許振和[例]句子abaabb的兩棵語(yǔ)法樹(shù)

為什么？

對(duì)于一個(gè)文法G而言，如果L(G)中存在一個(gè)句子對(duì)應(yīng)兩棵或兩棵以上的語(yǔ)法樹(shù)，那么該文法就稱為二義性的。

7/23/202346莆田學(xué)院許振和二義文法改造為無(wú)二義文法如果規(guī)定“×”和“＋”的優(yōu)先性，并服從左結(jié)合，上式就可以構(gòu)出無(wú)二義性。例如：文法G[E]:ET|E+TTF|T×FF(E)|i注意，文法的二義性和語(yǔ)言的二義性是兩個(gè)不同的概念。因?yàn)榭赡苡袃蓚€(gè)不同的文法G和G`，其中G是二義的，但是卻有L(G)=L(G`)。

產(chǎn)生某上下文無(wú)關(guān)語(yǔ)言的每一個(gè)文法都是二義的，則稱此語(yǔ)言是先天二義的。判定任給的一個(gè)上下文無(wú)關(guān)文法是否二義，或它是否產(chǎn)生一個(gè)先天二義的上下文無(wú)關(guān)語(yǔ)言，這兩個(gè)問(wèn)題是遞歸不可解的。但可以為無(wú)二義性尋找一組充分條件。7/23/202347莆田學(xué)院許振和本章重點(diǎn)：1、符號(hào)、符號(hào)串、句型、句子、語(yǔ)言2、理解有關(guān)文法、閉包、正閉包、規(guī)則、推導(dǎo)3、文法的類型7/23/202348莆田學(xué)院許振和課堂習(xí)題與練習(xí)：1、假設(shè)G是一個(gè)文法，S是文法的開(kāi)始符號(hào)，如果Sx，則稱x是__________。*句型2、文法G產(chǎn)生的_________的全體是該文法描述的語(yǔ)言。句子3、喬姆斯基定義的四種形式語(yǔ)言文法分別為:(1)文法(又"稱

(2)文法)、

(3)文法(又稱

(4)文法)、

(5)文法(又稱

(6)文法)、

(7)文法(又稱

(8)文法)。答案：(1)0型(2)短語(yǔ)結(jié)構(gòu)(3)1型(4)上下文有關(guān)

(5)2型(6)上下文無(wú)關(guān)(7)3型(8)正規(guī)7/23/202349莆田學(xué)院許振和4、如果一個(gè)文法滿足

，則稱該文法是二義文法。①文法的某一個(gè)句子存在兩棵（包括兩棵）以上的語(yǔ)法樹(shù)②文法中存在某個(gè)句子，它有兩個(gè)（包括兩個(gè)）以上的最右（最左）推導(dǎo)③文法中存在某個(gè)句子，它有兩個(gè)（包括兩個(gè)）以上的最右（最左）歸約④在進(jìn)行歸約時(shí)，文法的某些規(guī)范句型的句柄不惟一可選項(xiàng)有：a.①b.②c.③d.④e.②③f.①②③g.①②③④答案：gg7/23/202350莆田學(xué)院許振和5、一個(gè)語(yǔ)言的文法是【

】。

a.唯一