第2章(2)文法和語(yǔ)言的基本知識(shí)

1、2.4 2.4 短語(yǔ)、直接短語(yǔ)和句柄短語(yǔ)、直接短語(yǔ)和句柄短語(yǔ)短語(yǔ) 令令G是一個(gè)文法，是一個(gè)文法，S是文法的開(kāi)始符是文法的開(kāi)始符號(hào)，假定號(hào)，假定是文法是文法G的一個(gè)句型，如果的一個(gè)句型，如果有有 則稱(chēng)則稱(chēng) 是是相對(duì)于非終結(jié)符相對(duì)于非終結(jié)符A的的句型句型的的短語(yǔ)短語(yǔ)。SA*+且且 A 2.4 2.4 短語(yǔ)、直接短語(yǔ)和句柄短語(yǔ)、直接短語(yǔ)和句柄則稱(chēng)則稱(chēng)是是直接短語(yǔ)直接短語(yǔ)。 直接短語(yǔ)直接短語(yǔ) SA*且且 A 令令G是一個(gè)文法，是一個(gè)文法，S是文法的開(kāi)始符是文法的開(kāi)始符號(hào)，假定號(hào)，假定是文法是文法G的一個(gè)句型，如果的一個(gè)句型，如果有有 2.4 2.4 短語(yǔ)、直接短語(yǔ)和句柄短語(yǔ)、直接短語(yǔ)和句柄 注意：注意

2、：短語(yǔ)和直接短語(yǔ)的區(qū)別短語(yǔ)和直接短語(yǔ)的區(qū)別在于第二個(gè)條件在于第二個(gè)條件, 直接短語(yǔ)中的第直接短語(yǔ)中的第二個(gè)條件表示有文法規(guī)則二個(gè)條件表示有文法規(guī)則 A ，因此，每個(gè)直接短語(yǔ)都是因此，每個(gè)直接短語(yǔ)都是某規(guī)則右某規(guī)則右部部。 2.4 2.4 短語(yǔ)、直接短語(yǔ)和句柄短語(yǔ)、直接短語(yǔ)和句柄句柄句柄 一個(gè)句型的一個(gè)句型的最左直接短語(yǔ)最左直接短語(yǔ)稱(chēng)為該句稱(chēng)為該句型的句柄。型的句柄。句柄特征：句柄特征： (1) 它是它是直接短語(yǔ)直接短語(yǔ)，即某規(guī)則右部。，即某規(guī)則右部。 (2) 它具有它具有最左最左性。性。2.4 2.4 短語(yǔ)、直接短語(yǔ)和句柄短語(yǔ)、直接短語(yǔ)和句柄 注意注意: 短語(yǔ)、直接短語(yǔ)和句柄都短語(yǔ)、直接短語(yǔ)和

3、句柄都是針對(duì)某一句型的，都是指句型中是針對(duì)某一句型的，都是指句型中的哪些符號(hào)串能構(gòu)成短語(yǔ)和直接短的哪些符號(hào)串能構(gòu)成短語(yǔ)和直接短語(yǔ)語(yǔ)，離開(kāi)具體的句型離開(kāi)具體的句型來(lái)談短語(yǔ)、直來(lái)談短語(yǔ)、直接短語(yǔ)和句柄是無(wú)意義的接短語(yǔ)和句柄是無(wú)意義的。 2.4 2.4 短語(yǔ)、直接短語(yǔ)和句柄短語(yǔ)、直接短語(yǔ)和句柄 例如例如 設(shè)有文法設(shè)有文法GS=(S,A,B,a,b,P,S) 其中其中P為為： 求句型求句型 baSb的全部的全部短語(yǔ)短語(yǔ)、直接短語(yǔ)直接短語(yǔ)和和句柄句柄。 SABAAa | bBBa | Sb2.4 2.4 短語(yǔ)、直接短語(yǔ)和句柄短語(yǔ)、直接短語(yǔ)和句柄對(duì)文法，首先建立該句型的推導(dǎo)過(guò)程：對(duì)文法，首先建立該句型的推

4、導(dǎo)過(guò)程： 最左推導(dǎo)最左推導(dǎo):最右推導(dǎo)最右推導(dǎo):SABAAa | bBBa | SbSAB ASb bBSbbaSbSAB baBbaSbbBB 分析分析 根據(jù)短語(yǔ)定義，可以從句型根據(jù)短語(yǔ)定義，可以從句型的推導(dǎo)過(guò)程的推導(dǎo)過(guò)程 中找出其全部短語(yǔ)、直接短中找出其全部短語(yǔ)、直接短語(yǔ)和句柄。語(yǔ)和句柄。 句型句型 baSb2.4 2.4 短語(yǔ)、直接短語(yǔ)和句柄短語(yǔ)、直接短語(yǔ)和句柄句型句型baSb中的子串中的子串Sb，是是(相對(duì)相對(duì)于非終結(jié)符于非終結(jié)符B)句型句型baSb的短語(yǔ)，的短語(yǔ)，且為且為直接短語(yǔ)直接短語(yǔ)。 SAB bBBbaBbaSb(2) SbaB*B Sb (1) SS*S baSb +句型本身是

5、句型本身是(相對(duì)于非終結(jié)符相對(duì)于非終結(jié)符S)句型句型baSb的短語(yǔ)。的短語(yǔ)。 根據(jù)最左推導(dǎo)根據(jù)最左推導(dǎo):S A*+ A 2.4 2.4 短語(yǔ)、直接短語(yǔ)和句柄短語(yǔ)、直接短語(yǔ)和句柄句型句型baSb中的子串中的子串a(chǎn)，是是(相對(duì)相對(duì)于非終結(jié)符于非終結(jié)符B)句型句型baSb的短語(yǔ)，的短語(yǔ)，且為且為直接短語(yǔ)、句柄直接短語(yǔ)、句柄。 句型句型baSb中的子串中的子串ba，是是(相對(duì)相對(duì)于非終結(jié)符于非終結(jié)符A)句型句型baSb的短語(yǔ)。的短語(yǔ)。 B a(3) SbBSb*根據(jù)最右推導(dǎo)根據(jù)最右推導(dǎo):SAB ASb bBSbbaSb(4) SASb*A ba+S A*+ A 2.5 2.5 語(yǔ)法樹(shù)與文法的二義性語(yǔ)法

6、樹(shù)與文法的二義性 推導(dǎo)和語(yǔ)法樹(shù)推導(dǎo)和語(yǔ)法樹(shù) 1. 語(yǔ)法樹(shù)語(yǔ)法樹(shù) 對(duì)句型的推導(dǎo)過(guò)程給出一種圖形對(duì)句型的推導(dǎo)過(guò)程給出一種圖形表示表示, 這種表示稱(chēng)為語(yǔ)法樹(shù)，也稱(chēng)推這種表示稱(chēng)為語(yǔ)法樹(shù)，也稱(chēng)推導(dǎo)樹(shù)。導(dǎo)樹(shù)。 2.5.1 2.5.1 推導(dǎo)和語(yǔ)法樹(shù)推導(dǎo)和語(yǔ)法樹(shù)例如例如 設(shè)有文法設(shè)有文法GE:構(gòu)造句型構(gòu)造句型i i* *i+ii+i的語(yǔ)法樹(shù)。的語(yǔ)法樹(shù)。首先給出句型的推導(dǎo)過(guò)程首先給出句型的推導(dǎo)過(guò)程 (最左推導(dǎo)最左推導(dǎo)) ：EE+T | ET | TTT* *F | T/F | FF(E) | iEE+TT+TT* *F+TF* *F+Ti* *F+T i* *i+Ti* *i+Fi* *i+i2.5.1 2.5

7、.1 推導(dǎo)和語(yǔ)法樹(shù)推導(dǎo)和語(yǔ)法樹(shù)根據(jù)推導(dǎo)過(guò)程構(gòu)造句型根據(jù)推導(dǎo)過(guò)程構(gòu)造句型i* *i+i的語(yǔ)法樹(shù)如下：的語(yǔ)法樹(shù)如下：EE+TEE+TT+TTT* *F+TT* *FF* *F+TFi* *F+T ii* *i+Tii* *i+FFi* *i+ii2.5.1 2.5.1 推導(dǎo)和語(yǔ)法樹(shù)推導(dǎo)和語(yǔ)法樹(shù) 由例可知，由例可知，語(yǔ)法樹(shù)的構(gòu)造過(guò)程是從語(yǔ)法樹(shù)的構(gòu)造過(guò)程是從文法的開(kāi)始符號(hào)出發(fā)，構(gòu)造一個(gè)推導(dǎo)的文法的開(kāi)始符號(hào)出發(fā)，構(gòu)造一個(gè)推導(dǎo)的過(guò)程。過(guò)程。 因?yàn)槲姆ǖ拿恳粋€(gè)句型因?yàn)槲姆ǖ拿恳粋€(gè)句型 (句子句子) 都都存在一存在一 個(gè)推導(dǎo)，所以文法的每個(gè)句型個(gè)推導(dǎo)，所以文法的每個(gè)句型(句子句子) 都存在一棵對(duì)應(yīng)的語(yǔ)法樹(shù)。都

8、存在一棵對(duì)應(yīng)的語(yǔ)法樹(shù)。EE+T E+F E+i T+i T* *F+i T* *i+i F* *i+i i* *i+i2.5.1 2.5.1 推導(dǎo)和語(yǔ)法樹(shù)推導(dǎo)和語(yǔ)法樹(shù) 對(duì)句型對(duì)句型i* *i+i，還可給出最右推導(dǎo)：還可給出最右推導(dǎo)： EE+TTT* *FFiiFi2.5.1 2.5.1 推導(dǎo)和語(yǔ)法樹(shù)推導(dǎo)和語(yǔ)法樹(shù) 這也就是說(shuō)，這也就是說(shuō)，一棵語(yǔ)法樹(shù)表示了一棵語(yǔ)法樹(shù)表示了 一個(gè)句型的種種可能的一個(gè)句型的種種可能的(但未必是所但未必是所 有的有的)不同推導(dǎo)過(guò)程不同推導(dǎo)過(guò)程, 包括最左包括最左(最右最右) 推導(dǎo)。推導(dǎo)。2 2.5.1 .5.1 推導(dǎo)和語(yǔ)法樹(shù)推導(dǎo)和語(yǔ)法樹(shù) 2. 子樹(shù)子樹(shù)語(yǔ)法樹(shù)的子語(yǔ)法樹(shù)的

9、子樹(shù)是由某一結(jié)點(diǎn)樹(shù)是由某一結(jié)點(diǎn)連同所有分枝組連同所有分枝組成的部分。成的部分。EE+TTT* *FFiiFi2 2.5.1 .5.1 推導(dǎo)和語(yǔ)法樹(shù)推導(dǎo)和語(yǔ)法樹(shù) 3. 簡(jiǎn)單子樹(shù)簡(jiǎn)單子樹(shù) 語(yǔ)法樹(shù)的語(yǔ)法樹(shù)的簡(jiǎn)單子樹(shù)是指簡(jiǎn)單子樹(shù)是指只有單層分枝只有單層分枝的子樹(shù)。的子樹(shù)。EE+TTT* *FFiiFi2.5.1 2.5.1 推導(dǎo)和語(yǔ)法樹(shù)推導(dǎo)和語(yǔ)法樹(shù) 句型的短語(yǔ)、直接短語(yǔ)和句柄的句型的短語(yǔ)、直接短語(yǔ)和句柄的直觀解釋直觀解釋是：是： 短語(yǔ)：短語(yǔ)：子樹(shù)子樹(shù)的末端結(jié)點(diǎn)形成的的末端結(jié)點(diǎn)形成的符號(hào)串符號(hào)串是是 相對(duì)于子樹(shù)根的短語(yǔ)。相對(duì)于子樹(shù)根的短語(yǔ)。 直接短語(yǔ)：直接短語(yǔ)：簡(jiǎn)單子樹(shù)簡(jiǎn)單子樹(shù)的末端結(jié)點(diǎn)形成的的末端結(jié)點(diǎn)

10、形成的 符號(hào)串符號(hào)串是相對(duì)于簡(jiǎn)單子樹(shù)根的直接短語(yǔ)。是相對(duì)于簡(jiǎn)單子樹(shù)根的直接短語(yǔ)。 句柄：句柄：最左簡(jiǎn)單子樹(shù)最左簡(jiǎn)單子樹(shù)的末端結(jié)點(diǎn)形成的的末端結(jié)點(diǎn)形成的 符號(hào)串符號(hào)串是句柄。是句柄。2.5.1 2.5.1 推導(dǎo)和語(yǔ)法樹(shù)推導(dǎo)和語(yǔ)法樹(shù)EE+TTT* *FFiiFi短語(yǔ)短語(yǔ):ni i* *i+ii+ini i* *i in第一個(gè)第一個(gè)i in第二個(gè)第二個(gè)i in第三個(gè)第三個(gè)i in三個(gè)三個(gè)i i都是直接短語(yǔ)都是直接短語(yǔ)n第一個(gè)第一個(gè)i i是句柄是句柄注意注意: :i+ii+i不是句型的短語(yǔ)不是句型的短語(yǔ)句子句子 i* *i+i2.5.1 2.5.1 推導(dǎo)和語(yǔ)法樹(shù)推導(dǎo)和語(yǔ)法樹(shù) 前例前例 對(duì)文法對(duì)文法GS

11、=(S,A,B,a,b,P,S)其中其中P為：為： 可用語(yǔ)法樹(shù)非常直觀地求出句型可用語(yǔ)法樹(shù)非常直觀地求出句型baSb的全部短語(yǔ)，直接短語(yǔ)和句柄。的全部短語(yǔ)，直接短語(yǔ)和句柄。SABAAa | bBBa | Sb2.5.1 2.5.1 推導(dǎo)和語(yǔ)法樹(shù)推導(dǎo)和語(yǔ)法樹(shù) 分析分析 首先根據(jù)句型首先根據(jù)句型baSb的推導(dǎo)過(guò)程畫(huà)出對(duì)的推導(dǎo)過(guò)程畫(huà)出對(duì) 應(yīng)的語(yǔ)法樹(shù)如下：應(yīng)的語(yǔ)法樹(shù)如下： Sb 為句型的相對(duì)于為句型的相對(duì)于B的短語(yǔ)、的短語(yǔ)、直接短語(yǔ)直接短語(yǔ)baSb 為句型的相對(duì)于為句型的相對(duì)于S的短語(yǔ)的短語(yǔ)ba 為句型的相對(duì)于為句型的相對(duì)于A的短語(yǔ)的短語(yǔ)a 句型的相對(duì)于句型的相對(duì)于B的短語(yǔ)、的短語(yǔ)、直接短語(yǔ)直接短語(yǔ)和

12、和句柄句柄SABbBBbaBbaSbSABASbbBSbbaSbSABbB Sba由語(yǔ)法樹(shù)可知由語(yǔ)法樹(shù)可知2.5.2 2.5.2 文法的二義性文法的二義性從前面的討論可以看出，對(duì)于文法從前面的討論可以看出，對(duì)于文法G中中 任一句型的推導(dǎo)序列任一句型的推導(dǎo)序列, 我們總能為它構(gòu)造我們總能為它構(gòu)造 一棵語(yǔ)法樹(shù)，現(xiàn)在我們提出一個(gè)問(wèn)題：一棵語(yǔ)法樹(shù)，現(xiàn)在我們提出一個(gè)問(wèn)題： 文法的某個(gè)句型是否只對(duì)應(yīng)唯一的一棵文法的某個(gè)句型是否只對(duì)應(yīng)唯一的一棵語(yǔ)法樹(shù)呢？語(yǔ)法樹(shù)呢？也就是，它是否只有唯一的一也就是，它是否只有唯一的一個(gè)最左個(gè)最左( (最右最右) )推導(dǎo)呢？推導(dǎo)呢？ 2.5.2 2.5.2 文法的二義性文法的二

13、義性 例如例如 設(shè)有文法設(shè)有文法GE： 句子句子 i* *i+i 有兩個(gè)不同的最左推導(dǎo)，有兩個(gè)不同的最左推導(dǎo)，對(duì)應(yīng)兩棵不同的語(yǔ)法樹(shù)。對(duì)應(yīng)兩棵不同的語(yǔ)法樹(shù)。E E+E | E* *E | (E) | i2.5.2 2.5.2 文法的二義性文法的二義性 最左推導(dǎo)最左推導(dǎo)1 EE+EE* *E+E i* *E+Ei* *i+E i* *i+i 最左推導(dǎo)最左推導(dǎo)2 EE* *Ei* *E i* *E+Ei* *i+E i* *i+i EE* *EE+ +EiiiEE+EE* *Eiii2.5.2 2.5.2 文法的二義性文法的二義性 如果一個(gè)文法存在某個(gè)句子對(duì)應(yīng)如果一個(gè)文法存在某個(gè)句子對(duì)應(yīng)兩兩棵不同的

14、語(yǔ)法樹(shù)棵不同的語(yǔ)法樹(shù)，則說(shuō)這個(gè)文法則說(shuō)這個(gè)文法是是二義二義性的。性的。 或者說(shuō)，若一個(gè)文法中存在某個(gè)句或者說(shuō)，若一個(gè)文法中存在某個(gè)句子，它有子，它有兩個(gè)不同的最左兩個(gè)不同的最左 (最右最右) 推導(dǎo)，推導(dǎo)，則這個(gè)文法則這個(gè)文法是二義性的是二義性的。 E E+E | E* *E | (E) | i2.5.3 2.5.3 文法二義性的消除文法二義性的消除 1. 不改變文法中原有的語(yǔ)法規(guī)則不改變文法中原有的語(yǔ)法規(guī)則, 僅加僅加進(jìn)一些進(jìn)一些非形式的非形式的語(yǔ)法規(guī)定。語(yǔ)法規(guī)定。 EE+EE* *Eiii2.5.3 2.5.3 文法二義性的消除文法二義性的消除2. 構(gòu)造構(gòu)造一個(gè)等價(jià)的無(wú)二義性文法一個(gè)等價(jià)的無(wú)

15、二義性文法。即。即 把排除二義性的規(guī)則合并到原有文法中把排除二義性的規(guī)則合并到原有文法中, , 改寫(xiě)原有的文法。改寫(xiě)原有的文法。例如，對(duì)于上例文法例如，對(duì)于上例文法GE，將運(yùn)算符的將運(yùn)算符的 優(yōu)先順序和結(jié)合規(guī)則：優(yōu)先順序和結(jié)合規(guī)則：* *優(yōu)先于優(yōu)先于; 、* * 左結(jié)合加到原有文法中左結(jié)合加到原有文法中, 可構(gòu)造出無(wú)二義可構(gòu)造出無(wú)二義 性文法如下性文法如下 ：2.5.3 2.5.3 文法二義性的消除文法二義性的消除則句子則句子i i* *i+ii+i只有只有唯一一棵語(yǔ)法樹(shù)：唯一一棵語(yǔ)法樹(shù)：EE+T | TTT* *F | FF(E) | iEE+TTT* *FFiiFi2.5.3 2.5.3

16、文法二義性的消除文法二義性的消除 例例2 定義某程序語(yǔ)言條件語(yǔ)句的文法定義某程序語(yǔ)言條件語(yǔ)句的文法G為為: 試證明該文法是二義性的并消除之試證明該文法是二義性的并消除之。 分析分析 該文法的句子該文法的句子 if b if b A else A 對(duì)應(yīng)下面兩棵不同的語(yǔ)法樹(shù)：對(duì)應(yīng)下面兩棵不同的語(yǔ)法樹(shù)： Sif b S | if b S else S | A (其它語(yǔ)句）其它語(yǔ)句）2.5.3 2.5.3 文法二義性的消除文法二義性的消除 所以該文法是二義的。所以該文法是二義的。 SifbSbSSifAelseASbSSifAelseAifbSSif b S | if b S else S | A句子

17、句子 if b if b A else A2.5.3 2.5.3 文法二義性的消除文法二義性的消除 消除文法的二義性可采用下面兩種方法：消除文法的二義性可采用下面兩種方法： 1. 不改變已有規(guī)則不改變已有規(guī)則，僅，僅加進(jìn)一非形式的語(yǔ)法規(guī)加進(jìn)一非形式的語(yǔ)法規(guī)定：定：else與前面最接近與前面最接近的不帶的不帶else的的 if 相對(duì)應(yīng)相對(duì)應(yīng)。SifbSbSSifAelseA文法文法G的句子的句子 if b if b A else只對(duì)應(yīng)唯一的一棵語(yǔ)法樹(shù)只對(duì)應(yīng)唯一的一棵語(yǔ)法樹(shù)，消除了二義性。消除了二義性。2.5.3 2.5.3 文法二義性的消除文法二義性的消除2. 改寫(xiě)文法改寫(xiě)文法G為為GS S1

18、| S2 S1 if b S1 else S1 | A S2 if b S | if b S1 else S2 G:Sif b S | if b S else S | A (其它語(yǔ)句）其它語(yǔ)句）G:2.5.3 2.5.3 文法二義性的消除文法二義性的消除 這是因?yàn)橥ㄟ^(guò)這是因?yàn)橥ㄟ^(guò)分析分析，得知引起二義，得知引起二義性的原因是性的原因是: : if if-else else 語(yǔ)句的語(yǔ)句的 if if 后可是后可是ifif型，型，因此改寫(xiě)文法時(shí)規(guī)定因此改寫(xiě)文法時(shí)規(guī)定: :ifif-elseelse之間只能是之間只能是ifif-elseelse語(yǔ)句或其他語(yǔ)句或其他語(yǔ)句語(yǔ)句。2.5.3 2.5.3 文

19、法二義性的消除文法二義性的消除S S1 | S2 S1 if b S1 else S1 | A S2 if b S | if b S1 else S2 ifbSbifAelseASS2S1S1S1對(duì)改寫(xiě)后的文法，句子對(duì)改寫(xiě)后的文法，句子 if b if b A else A 只對(duì)應(yīng)唯一的一棵語(yǔ)法只對(duì)應(yīng)唯一的一棵語(yǔ)法樹(shù)。樹(shù)。通常我們通常我們只說(shuō)文法的二義性只說(shuō)文法的二義性, 而不而不說(shuō)語(yǔ)言的二義性說(shuō)語(yǔ)言的二義性, 這是因?yàn)榭赡苡袃蓚€(gè)這是因?yàn)榭赡苡袃蓚€(gè)不同的文法不同的文法G和和G ，而且其中一個(gè)是而且其中一個(gè)是二二義性的義性的，另一個(gè)是另一個(gè)是無(wú)二義性的無(wú)二義性的, 但卻有但卻有L(G)=L(G)

20、, 即這兩個(gè)文法所產(chǎn)生的即這兩個(gè)文法所產(chǎn)生的語(yǔ)語(yǔ)言是相同的言是相同的。2.5.3 2.5.3 文法二義性的消除文法二義性的消除 應(yīng)該指出的是文法的二義性和語(yǔ)應(yīng)該指出的是文法的二義性和語(yǔ)言的二義性是言的二義性是兩個(gè)不同的概念兩個(gè)不同的概念。2.5.3 2.5.3 文法二義性的消除文法二義性的消除 將一個(gè)語(yǔ)言說(shuō)成是二義性的，將一個(gè)語(yǔ)言說(shuō)成是二義性的，是是指對(duì)它指對(duì)它不存在無(wú)二義性的文法，不存在無(wú)二義性的文法，這樣這樣的語(yǔ)言稱(chēng)為先天二義性的語(yǔ)言。的語(yǔ)言稱(chēng)為先天二義性的語(yǔ)言。 例如例如 L= ai bj ck | i=j 或或 j=k 且且 i, j, k1便是這種語(yǔ)言。便是這種語(yǔ)言。2.6 2.6

21、文法和語(yǔ)言的分類(lèi)文法和語(yǔ)言的分類(lèi) 著名的語(yǔ)言學(xué)家著名的語(yǔ)言學(xué)家喬姆斯基喬姆斯基(Chomsky) 將文法和語(yǔ)言分為四大類(lèi)，即將文法和語(yǔ)言分為四大類(lèi)，即0型、型、1型、型、 2型、型、3型。劃分的依據(jù)是對(duì)文法中的規(guī)型。劃分的依據(jù)是對(duì)文法中的規(guī) 則施加不同的限制。則施加不同的限制。 為了容易理解，我們講解時(shí)按照由簡(jiǎn)為了容易理解，我們講解時(shí)按照由簡(jiǎn)到難的次序，和教材稍有不同。到難的次序，和教材稍有不同。2.6 2.6 文法和語(yǔ)言的分類(lèi)文法和語(yǔ)言的分類(lèi) 3型文法（正規(guī)文法）型文法（正規(guī)文法） 右線性文法右線性文法和和左線性文法左線性文法都稱(chēng)為都稱(chēng)為3型文法。型文法。 若文法若文法G=(VN,VT, P

22、, S)中的每一條規(guī)則的形式中的每一條規(guī)則的形式 為為A B 或或 A , 其中：其中： A , B VN, VT*, 則稱(chēng)則稱(chēng)G是是右線性文法右線性文法。 若文法若文法G=(VN,VT, P, S)中的每一條規(guī)則的形式中的每一條規(guī)則的形式 為為A B 或或 A , 其中：其中： A , B VN , VT*, 則稱(chēng)則稱(chēng)G是是左線性文法左線性文法。3型文法描述的型文法描述的語(yǔ)言是語(yǔ)言是3型語(yǔ)言。型語(yǔ)言。3型語(yǔ)言由有型語(yǔ)言由有窮自動(dòng)機(jī)識(shí)別。窮自動(dòng)機(jī)識(shí)別。 3型文法也稱(chēng)型文法也稱(chēng)正規(guī)文法正規(guī)文法。正規(guī)文法產(chǎn)生的語(yǔ)言。正規(guī)文法產(chǎn)生的語(yǔ)言 稱(chēng)為稱(chēng)為正規(guī)語(yǔ)言正規(guī)語(yǔ)言。 例如，用左線性正規(guī)文法和右線性例如

23、，用左線性正規(guī)文法和右線性正規(guī)文法定義標(biāo)識(shí)符正規(guī)文法定義標(biāo)識(shí)符 2.6 2.6 文法和語(yǔ)言的分類(lèi)文法和語(yǔ)言的分類(lèi) 用用I代表標(biāo)識(shí)符代表標(biāo)識(shí)符; l代表任意一個(gè)字母代表任意一個(gè)字母; d代表任意一個(gè)數(shù)字代表任意一個(gè)數(shù)字; 則定義標(biāo)識(shí)符的文則定義標(biāo)識(shí)符的文法為：法為：左線性文法左線性文法: P: I l | Il | Id右線性文法右線性文法: P: I l | lT Tl | d | lT| dT 例如，用左線性正規(guī)文法和右線性例如，用左線性正規(guī)文法和右線性正規(guī)文法定義無(wú)符號(hào)整數(shù)正規(guī)文法定義無(wú)符號(hào)整數(shù)2.6 2.6 文法和語(yǔ)言的分類(lèi)文法和語(yǔ)言的分類(lèi) 用用N代表無(wú)符號(hào)整數(shù)代表無(wú)符號(hào)整數(shù); d代表任

24、意一個(gè)代表任意一個(gè)數(shù)字；則定義的無(wú)符號(hào)整數(shù)文法為：數(shù)字；則定義的無(wú)符號(hào)整數(shù)文法為：左線性文法左線性文法: P: N Nd | d右線性文法右線性文法: P: N dN | d2.6 2.6 文法和語(yǔ)言的分類(lèi)文法和語(yǔ)言的分類(lèi) 2型文法（上下文無(wú)關(guān)文法）型文法（上下文無(wú)關(guān)文法） 2型文法又稱(chēng)上下文無(wú)關(guān)文法，其產(chǎn)生的型文法又稱(chēng)上下文無(wú)關(guān)文法，其產(chǎn)生的 語(yǔ)言又稱(chēng)為語(yǔ)言又稱(chēng)為上下文無(wú)關(guān)的語(yǔ)言上下文無(wú)關(guān)的語(yǔ)言。 若文法若文法G=(VN,VT, P, S)中的每一條規(guī)則的中的每一條規(guī)則的 形式為形式為 A , 其中：其中： A VN , (VNVT)*則稱(chēng)則稱(chēng)G是是2型文法。型文法。2型文法描述的型文法描述

25、的語(yǔ)言是語(yǔ)言是2型語(yǔ)言。型語(yǔ)言。2型語(yǔ)言由下型語(yǔ)言由下推自動(dòng)機(jī)識(shí)別。推自動(dòng)機(jī)識(shí)別。例如前面描述算術(shù)表達(dá)式的文法例如前面描述算術(shù)表達(dá)式的文法GE:EE+E | E* *E | (E) | i2.6 2.6 文法和語(yǔ)言的分類(lèi)文法和語(yǔ)言的分類(lèi) 其描述的語(yǔ)言為其描述的語(yǔ)言為 L2(GS)=x | x a, b+ 且且x中中a和和b的個(gè)數(shù)相同的個(gè)數(shù)相同 例如，有例如，有2型文法型文法G=(VN,VT, P, S) 其中：其中：VN=S, A, B , VT=a, b P= S aB | bA A a | aS | bAA B b | bS | aBB 2.6 2.6 文法和語(yǔ)言的分類(lèi)文法和語(yǔ)言的分類(lèi) 2

26、.6 2.6 文法和語(yǔ)言的分類(lèi)文法和語(yǔ)言的分類(lèi) 1型文法（上下文有關(guān)文法）型文法（上下文有關(guān)文法） 1型文法也稱(chēng)為上下文有關(guān)文法，型文法也稱(chēng)為上下文有關(guān)文法， 相應(yīng)相應(yīng) 的語(yǔ)言又稱(chēng)為的語(yǔ)言又稱(chēng)為上下文有關(guān)語(yǔ)言上下文有關(guān)語(yǔ)言。 若文法若文法G=(VN,VT, P, S)中的每一條規(guī)則的中的每一條規(guī)則的 形式為形式為 A , 其中：其中： , (VNVT)* ,A VN ,則稱(chēng)則稱(chēng)G是是1型文法型文法。1型文法描述的型文法描述的語(yǔ)言是語(yǔ)言是1型語(yǔ)言。型語(yǔ)言。1型語(yǔ)言由線性型語(yǔ)言由線性界限自動(dòng)機(jī)識(shí)別。界限自動(dòng)機(jī)識(shí)別。 (VNVT)+2.6 2.6 文法和語(yǔ)言的分類(lèi)文法和語(yǔ)言的分類(lèi) 例如，有例如，有1

27、型文法型文法G=(VN,VT, P, S) 其中：其中：VN=S,A,B , VT=a,b,c P: S aSAB | abB BA BA BA AA AA AB bA bb bB bc cB cc其描述的其描述的1型語(yǔ)言為型語(yǔ)言為L(zhǎng)1(GS)=anbncn | n1 2.6 2.6 文法和語(yǔ)言的分類(lèi)文法和語(yǔ)言的分類(lèi) 0型文法（無(wú)限制文法）型文法（無(wú)限制文法） 若文法若文法G=(VN,VT, P, S)中的每條規(guī)則中的每條規(guī)則 是這樣一種結(jié)構(gòu)：是這樣一種結(jié)構(gòu)： 而且而且中至少含一個(gè)非終結(jié)符中至少含一個(gè)非終結(jié)符, 則稱(chēng)則稱(chēng)G 是是0型文法型文法。 (VNVT)+ , (VNVT)*0型文法描述的

28、語(yǔ)言是型文法描述的語(yǔ)言是0型語(yǔ)言。型語(yǔ)言。0型文法沒(méi)有加任何限制條件，又稱(chēng)為型文法沒(méi)有加任何限制條件，又稱(chēng)為 無(wú)限制性文法，相應(yīng)的語(yǔ)言稱(chēng)為無(wú)限制性文法，相應(yīng)的語(yǔ)言稱(chēng)為無(wú)限制無(wú)限制 性語(yǔ)言性語(yǔ)言。0型語(yǔ)言由型語(yǔ)言由圖靈機(jī)識(shí)別。圖靈機(jī)識(shí)別。2.6 2.6 文法和語(yǔ)言的分類(lèi)文法和語(yǔ)言的分類(lèi) 例如，有例如，有0型文法型文法G=(VN,VT, P, S) 其中：其中：VN=A,B,S , VT=0,1 其描述的其描述的 0 型語(yǔ)言為型語(yǔ)言為 L0(GS)= P: S 0AB 1B 0 B SA | 01 A1 SB1 A0 S0B2.6 2.6 文法和語(yǔ)言的分類(lèi)文法和語(yǔ)言的分類(lèi) 由上述四類(lèi)文法的定義可知

29、由上述四類(lèi)文法的定義可知, 從從0型型文法到文法到3型文法型文法, 是逐漸增加對(duì)規(guī)則的限是逐漸增加對(duì)規(guī)則的限制條件而得到的，制條件而得到的，因此因此每一種正規(guī)文法每一種正規(guī)文法都是上下文無(wú)關(guān)的文法，都是上下文無(wú)關(guān)的文法，每一種上下文每一種上下文無(wú)關(guān)的文法都是上下文有關(guān)的文法，而無(wú)關(guān)的文法都是上下文有關(guān)的文法，而每一種上下文有關(guān)的文法都是每一種上下文有關(guān)的文法都是0型文法型文法, 而由它們所定義的語(yǔ)言類(lèi)是依次縮小的，而由它們所定義的語(yǔ)言類(lèi)是依次縮小的，有有 L0 L1 L2 L3 。 2.7 2.7 有關(guān)文法的實(shí)用限制和變換有關(guān)文法的實(shí)用限制和變換 文法是用來(lái)描述程序設(shè)計(jì)語(yǔ)言的，在文法是用來(lái)描述

30、程序設(shè)計(jì)語(yǔ)言的，在 實(shí)際應(yīng)用中需要對(duì)文法加一些限制條件。實(shí)際應(yīng)用中需要對(duì)文法加一些限制條件。 1. 文法中不能含有形如文法中不能含有形如A A 的規(guī)則。的規(guī)則。這種規(guī)則我們稱(chēng)之為這種規(guī)則我們稱(chēng)之為有害規(guī)則有害規(guī)則。對(duì)文法的實(shí)用限制有以下兩點(diǎn)：對(duì)文法的實(shí)用限制有以下兩點(diǎn)： 2.7 2.7 有關(guān)文法的實(shí)用限制和變換有關(guān)文法的實(shí)用限制和變換 2. 文法中不能有文法中不能有多余規(guī)則多余規(guī)則。所謂多余。所謂多余規(guī)則是指文法中出現(xiàn)以下兩種規(guī)則：規(guī)則是指文法中出現(xiàn)以下兩種規(guī)則： (1) 某條規(guī)則某條規(guī)則 A 的左部符號(hào)的左部符號(hào)A不在不在所屬文法的任何其他規(guī)則所屬文法的任何其他規(guī)則右部右部出現(xiàn)，即出現(xiàn)，即在

31、推導(dǎo)文法的所有句子中始終都不可能在推導(dǎo)文法的所有句子中始終都不可能用到的規(guī)則。用到的規(guī)則。 (2) 對(duì)文法中的某個(gè)非終結(jié)符對(duì)文法中的某個(gè)非終結(jié)符A，無(wú)法無(wú)法從它推出任何終結(jié)符號(hào)串來(lái)。從它推出任何終結(jié)符號(hào)串來(lái)。 2.7 2.7 有關(guān)文法的實(shí)用限制和變換有關(guān)文法的實(shí)用限制和變換 例如例如 設(shè)有文法設(shè)有文法GS: P: S Bd A Ad | dB Cd | AeC Ce D e 刪除多余規(guī)則后的刪除多余規(guī)則后的文法變換為文法變換為: P: S Bd A Ad | dB Ae 2.7 2.7 有關(guān)文法的實(shí)用限制和變換有關(guān)文法的實(shí)用限制和變換 若程序設(shè)計(jì)語(yǔ)言的若程序設(shè)計(jì)語(yǔ)言的文法含有多余規(guī)則文法含有多

32、余規(guī)則， 其中其中必定必定有錯(cuò)誤存在有錯(cuò)誤存在，因此檢查文法中是，因此檢查文法中是否含有多余規(guī)則對(duì)我們來(lái)說(shuō)是很重要的。否含有多余規(guī)則對(duì)我們來(lái)說(shuō)是很重要的。 本章重點(diǎn)介紹了語(yǔ)言的語(yǔ)法結(jié)構(gòu)的形式描述、本章重點(diǎn)介紹了語(yǔ)言的語(yǔ)法結(jié)構(gòu)的形式描述、語(yǔ)法樹(shù)以及文法的二義性語(yǔ)法樹(shù)以及文法的二義性, 主要內(nèi)容有：主要內(nèi)容有： 1. 設(shè)計(jì)一個(gè)文法定義一個(gè)已知的語(yǔ)言設(shè)計(jì)一個(gè)文法定義一個(gè)已知的語(yǔ)言 (1) 文法是一個(gè)四元組文法是一個(gè)四元組 G=(VN,VT, P, S)， 文法四大要素中，關(guān)鍵是一組規(guī)則文法四大要素中，關(guān)鍵是一組規(guī)則, 它定義它定義（或描述）了一個(gè)語(yǔ)言的結(jié)構(gòu)。（或描述）了一個(gè)語(yǔ)言的結(jié)構(gòu)。 從文法定義可

33、知從文法定義可知, 文法對(duì)于程序設(shè)計(jì)者來(lái)文法對(duì)于程序設(shè)計(jì)者來(lái) 說(shuō)，文法給出了語(yǔ)言的精確定義和描述。說(shuō)，文法給出了語(yǔ)言的精確定義和描述。 本章小結(jié)本章小結(jié) (2) 分析已知語(yǔ)言分析已知語(yǔ)言句子的結(jié)構(gòu)特征句子的結(jié)構(gòu)特征, 設(shè)計(jì)設(shè)計(jì) 出相應(yīng)的一組規(guī)則，但不唯一。出相應(yīng)的一組規(guī)則，但不唯一。 (4) 若語(yǔ)言是若語(yǔ)言是無(wú)窮集合無(wú)窮集合, 設(shè)計(jì)該語(yǔ)言的文設(shè)計(jì)該語(yǔ)言的文 法一定是法一定是遞歸的遞歸的。本章小結(jié)本章小結(jié)(3) 設(shè)計(jì)的文法必須能定義已知的語(yǔ)言設(shè)計(jì)的文法必須能定義已知的語(yǔ)言, 不能超出或縮小所定義語(yǔ)言的范圍。不能超出或縮小所定義語(yǔ)言的范圍。 分析分析 根據(jù)語(yǔ)言句子的結(jié)構(gòu)特征，設(shè)計(jì)出相根據(jù)語(yǔ)言句子的

34、結(jié)構(gòu)特征，設(shè)計(jì)出相 應(yīng)規(guī)則應(yīng)規(guī)則例例1. 給出語(yǔ)言給出語(yǔ)言 L2=an bm| mn1 的文法的文法P2: SABL2=ab,abb,abbb, aabb,aabbb,aabbbb, aaabbb, aabbbb，AaAb | ab BbB |本章小結(jié)本章小結(jié) 分析分析 根據(jù)語(yǔ)言句子的結(jié)構(gòu)特征，設(shè)計(jì)出相根據(jù)語(yǔ)言句子的結(jié)構(gòu)特征，設(shè)計(jì)出相 應(yīng)規(guī)則應(yīng)規(guī)則 例例2. 給出語(yǔ)言給出語(yǔ)言 L1=a2n+1|n0 的文法的文法P1: AaB | aP1：AaAa | a 或或L1=a, aaa, aaaaa, aaaaaaa, aaaaaaaaa，Baa | aBa本章小結(jié)本章小結(jié)本章小結(jié)本章小結(jié) 分析分析

35、 根據(jù)語(yǔ)言句子的根據(jù)語(yǔ)言句子的結(jié)構(gòu)特征結(jié)構(gòu)特征，設(shè)計(jì)出相，設(shè)計(jì)出相應(yīng)規(guī)則應(yīng)規(guī)則 例例3. 給出語(yǔ)言給出語(yǔ)言L3=anbmck| n,m,k0的文法的文法P3: AaA | bB | cC |P3: AaA | B或或L3=,a,aa,aaa,b,bb,bbb,c,cc,ccc, , ab,abb, ,bc,bcc，CcC |BbB | cC | CcC |BbB | C本章小結(jié)本章小結(jié)L4=2,4,6,8,10,12,14,16,18,20,22,24,26, 例例4. 寫(xiě)一個(gè)寫(xiě)一個(gè) 文法文法, ,使其語(yǔ)言是正偶數(shù)的集合使其語(yǔ)言是正偶數(shù)的集合, ,每每個(gè)偶數(shù)不以個(gè)偶數(shù)不以0 0開(kāi)頭。開(kāi)頭。P4

36、: NE | AE N2 | 4 | 6 | 8 | BN 或或分析分析 不以不以0開(kāi)頭的偶數(shù)集合中串的結(jié)構(gòu)特征開(kāi)頭的偶數(shù)集合中串的結(jié)構(gòu)特征:AD | AD E0 | 2 | 4 | 6 | 8 D1 | 2 | 3 | | 9 D0 | 1 | 2 | 3 | 9 B1 | 2 | 3 | | 9 |B0P4:E2 | 4 | 6 | 8 N BN | 0| 2 | 4 | 6 | 8本章小結(jié)本章小結(jié)A 0A1 | P : S 1S0 | 0A1 | 例例5. 給出語(yǔ)言給出語(yǔ)言L=1n0m1m0n | n,m0的的文法。文法。分析分析 根據(jù)語(yǔ)言句子的結(jié)構(gòu)特征根據(jù)語(yǔ)言句子的結(jié)構(gòu)特征, 設(shè)計(jì)設(shè)計(jì)

37、 出相應(yīng)規(guī)則出相應(yīng)規(guī)則 L=,01,0011,10,1100,1010,100110, 110100,11001100本章小結(jié)本章小結(jié)P : S a | 0S0 | 1S1例例6. 給出語(yǔ)言給出語(yǔ)言L= WaWt | W0|1* * ， 其中其中 W Wt t表示表示W(wǎng) W的逆的文法的逆的文法。分析分析 根據(jù)語(yǔ)言句子的結(jié)構(gòu)特征，設(shè)計(jì)根據(jù)語(yǔ)言句子的結(jié)構(gòu)特征，設(shè)計(jì) 出相應(yīng)規(guī)則出相應(yīng)規(guī)則 L=a, 0a0, 1a1, 01a10, 10a01, 00a00, 11a11, 101a101, 110a011, 100a001, W=,0, 1 ,01, 10, 00, 11, 101, 110, 10

38、0, 111, 本章小結(jié)本章小結(jié)2. 已知一個(gè)文法，確定該文法所定義的已知一個(gè)文法，確定該文法所定義的 語(yǔ)言。語(yǔ)言。 (2) 給定一個(gè)文法，可根據(jù)語(yǔ)言和推導(dǎo)定給定一個(gè)文法，可根據(jù)語(yǔ)言和推導(dǎo)定 義推導(dǎo)出文法的句子，從而確定出該文法義推導(dǎo)出文法的句子，從而確定出該文法 所定義的語(yǔ)言。所定義的語(yǔ)言。 (1) 文法所定義的語(yǔ)言文法所定義的語(yǔ)言 L(GS)=x|S x且且xVT*本章小結(jié)本章小結(jié) 自然語(yǔ)言描述。自然語(yǔ)言描述。 例如例如, L=x|xa,b+且且x中中a,b個(gè)數(shù)相同個(gè)數(shù)相同式子描述。例如式子描述。例如 L=a2nbb | n0。正規(guī)式描述。正規(guī)式描述。 (3) 語(yǔ)言可用語(yǔ)言可用本章小結(jié)本章

39、小結(jié) 例例1 文法文法GA=(A,a,b,AbA | a, A) 所生成的語(yǔ)言是什么？所生成的語(yǔ)言是什么？ 分析分析 AbAbbAbbbAbnAbna L(GA)= bna | n0 本章小結(jié)本章小結(jié)例例2 文法文法GN為為:N ND | DD 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9(1) GN所生成的語(yǔ)言是什么？所生成的語(yǔ)言是什么？ (2) 給出句子給出句子0127的最左的最左、最右推導(dǎo)最右推導(dǎo)。 本章小結(jié)本章小結(jié)L(GN)= | 0,1,2, 9+= | 為可帶前導(dǎo)為可帶前導(dǎo)0的正整數(shù)的正整數(shù)= | 為數(shù)字串為數(shù)字串最左推導(dǎo)最左推導(dǎo):NNDN7ND7N2

40、7ND27 N127D1270127最右推導(dǎo)最右推導(dǎo):NNDNDDNDDDDDDD 0DDD01DD012D0127N ND | DD 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9本章小結(jié)本章小結(jié) 例例3. 已知文法已知文法GS=( A,B,a,b,c,d, P, S ) , 其中其中 P 為為:分析分析 SABaAbBa2Ab2B an-1Abn-1BanbnBanbncBd anbnc2Bd2 anbncm-1Bdn-1anbncmdm L(GS)=anbncmdm | n ,m1 該文法該文法 所生成的語(yǔ)言是什么？所生成的語(yǔ)言是什么？ A aAb | ab

41、B cBd | cd S AB本章小結(jié)本章小結(jié)3. 求句型的短語(yǔ)、直接短語(yǔ)和句柄求句型的短語(yǔ)、直接短語(yǔ)和句柄 (1) 短語(yǔ)、直接短語(yǔ)和句柄是對(duì)某句短語(yǔ)、直接短語(yǔ)和句柄是對(duì)某句 型而言的。型而言的。 (2) 短語(yǔ)總是句型的某個(gè)子串，它對(duì)應(yīng)短語(yǔ)總是句型的某個(gè)子串，它對(duì)應(yīng) 子樹(shù)未端結(jié)點(diǎn)形成的符號(hào)串。子樹(shù)未端結(jié)點(diǎn)形成的符號(hào)串。 (3) 直接短語(yǔ)是某條規(guī)則右部，它對(duì)應(yīng)直接短語(yǔ)是某條規(guī)則右部，它對(duì)應(yīng) 簡(jiǎn)單子樹(shù)未端結(jié)點(diǎn)形成的符號(hào)串。簡(jiǎn)單子樹(shù)未端結(jié)點(diǎn)形成的符號(hào)串。(4) 最左邊的直接短語(yǔ)是句柄。最左邊的直接短語(yǔ)是句柄。 本章小結(jié)本章小結(jié)例例1 已知文已知文法法GE： 證明證明 E+T* *F是它的一個(gè)句型是它的一個(gè)句型, ,指出這個(gè)句指出這個(gè)句型的短語(yǔ)直接短語(yǔ)和句柄。型的短語(yǔ)直接短語(yǔ)和句柄。 EE+TE+T* *F 短語(yǔ)短語(yǔ): E+T* *F、T* *F E+T* *F是它的一個(gè)句型是它的一個(gè)句型。畫(huà)出該句型的語(yǔ)畫(huà)出該句型的語(yǔ)法樹(shù)法樹(shù):句柄句柄: T* *F直接短語(yǔ)直接短語(yǔ): T* *FETFT+E* *EE+T | E- -T | TTT* *F | T/F | FF(E) | i本章小結(jié)本章小結(jié) 例例2 已知文法已知文法GS： 試