第2章(2)文法和語言的基本知識

1、2.4 2.4 短語、直接短語和句柄短語、直接短語和句柄短語短語 令令G是一個文法，是一個文法，S是文法的開始符是文法的開始符號，假定號，假定是文法是文法G的一個句型，如果的一個句型，如果有有 則稱則稱 是是相對于非終結(jié)符相對于非終結(jié)符A的的句型句型的的短語短語。SA*+且且 A 2.4 2.4 短語、直接短語和句柄短語、直接短語和句柄則稱則稱是是直接短語直接短語。 直接短語直接短語 SA*且且 A 令令G是一個文法，是一個文法，S是文法的開始符是文法的開始符號，假定號，假定是文法是文法G的一個句型，如果的一個句型，如果有有 2.4 2.4 短語、直接短語和句柄短語、直接短語和句柄 注意：注意

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

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

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

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

6、樹與文法的二義性 推導(dǎo)和語法樹推導(dǎo)和語法樹 1. 語法樹語法樹 對句型的推導(dǎo)過程給出一種圖形對句型的推導(dǎo)過程給出一種圖形表示表示, 這種表示稱為語法樹，也稱推這種表示稱為語法樹，也稱推導(dǎo)樹。導(dǎo)樹。 2.5.1 2.5.1 推導(dǎo)和語法樹推導(dǎo)和語法樹例如例如 設(shè)有文法設(shè)有文法GE:構(gòu)造句型構(gòu)造句型i i* *i+ii+i的語法樹。的語法樹。首先給出句型的推導(dǎo)過程首先給出句型的推導(dǎo)過程 (最左推導(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)和語法樹推導(dǎo)和語法樹根據(jù)推導(dǎo)過程構(gòu)造句型根據(jù)推導(dǎo)過程構(gòu)造句型i* *i+i的語法樹如下：的語法樹如下：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)和語法樹推導(dǎo)和語法樹 由例可知，由例可知，語法樹的構(gòu)造過程是從語法樹的構(gòu)造過程是從文法的開始符號出發(fā)，構(gòu)造一個推導(dǎo)的文法的開始符號出發(fā)，構(gòu)造一個推導(dǎo)的過程。過程。 因?yàn)槲姆ǖ拿恳粋€句型因?yàn)槲姆ǖ拿恳粋€句型 (句子句子) 都都存在一存在一 個推導(dǎo)，所以文法的每個句型個推導(dǎo)，所以文法的每個句型(句子句子) 都存在一棵對應(yīng)的語法樹。都

8、存在一棵對應(yīng)的語法樹。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)和語法樹推導(dǎo)和語法樹 對句型對句型i* *i+i，還可給出最右推導(dǎo)：還可給出最右推導(dǎo)： EE+TTT* *FFiiFi2.5.1 2.5.1 推導(dǎo)和語法樹推導(dǎo)和語法樹 這也就是說，這也就是說，一棵語法樹表示了一棵語法樹表示了 一個句型的種種可能的一個句型的種種可能的(但未必是所但未必是所 有的有的)不同推導(dǎo)過程不同推導(dǎo)過程, 包括最左包括最左(最右最右) 推導(dǎo)。推導(dǎo)。2 2.5.1 .5.1 推導(dǎo)和語法樹推導(dǎo)和語法樹 2. 子樹子樹語法樹的子語法樹的

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

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

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

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

13、義性 例如例如 設(shè)有文法設(shè)有文法GE： 句子句子 i* *i+i 有兩個不同的最左推導(dǎo)，有兩個不同的最左推導(dǎo)，對應(yīng)兩棵不同的語法樹。對應(yīng)兩棵不同的語法樹。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 文法的二義性文法的二義性 如果一個文法存在某個句子對應(yīng)如果一個文法存在某個句子對應(yīng)兩兩棵不同的

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

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

16、文法二義性的消除文法二義性的消除 例例2 定義某程序語言條件語句的文法定義某程序語言條件語句的文法G為為: 試證明該文法是二義性的并消除之試證明該文法是二義性的并消除之。 分析分析 該文法的句子該文法的句子 if b if b A else A 對應(yīng)下面兩棵不同的語法樹：對應(yīng)下面兩棵不同的語法樹： Sif b S | if b S else S | A (其它語句）其它語句）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)一非形式的語法規(guī)加進(jìn)一非形式的語法規(guī)定：定：else與前面最接近與前面最接近的不帶的不帶else的的 if 相對應(yīng)相對應(yīng)。SifbSbSSifAelseA文法文法G的句子的句子 if b if b A else只對應(yīng)唯一的一棵語法樹只對應(yīng)唯一的一棵語法樹，消除了二義性。消除了二義性。2.5.3 2.5.3 文法二義性的消除文法二義性的消除2. 改寫文法改寫文法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 (其它語句）其它語句）G:2.5.3 2.5.3 文法二義性的消除文法二義性的消除 這是因?yàn)橥ㄟ^這是因?yàn)橥ㄟ^分析分析，得知引起二義，得知引起二義性的原因是性的原因是: : if if-else else 語句的語句的 if if 后可是后可是ifif型，型，因此改寫文法時規(guī)定因此改寫文法時規(guī)定: :ifif-elseelse之間只能是之間只能是ifif-elseelse語句或其他語句或其他語句語句。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對改寫后的文法，句子對改寫后的文法，句子 if b if b A else A 只對應(yīng)唯一的一棵語法只對應(yīng)唯一的一棵語法樹。樹。通常我們通常我們只說文法的二義性只說文法的二義性, 而不而不說語言的二義性說語言的二義性, 這是因?yàn)榭赡苡袃蓚€這是因?yàn)榭赡苡袃蓚€不同的文法不同的文法G和和G ，而且其中一個是而且其中一個是二二義性的義性的，另一個是另一個是無二義性的無二義性的, 但卻有但卻有L(G)=L(G)

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

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

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

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

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

25、的語言是語言是2型語言。型語言。2型語言由下型語言由下推自動機(jī)識別。推自動機(jī)識別。例如前面描述算術(shù)表達(dá)式的文法例如前面描述算術(shù)表達(dá)式的文法GE:EE+E | E* *E | (E) | i2.6 2.6 文法和語言的分類文法和語言的分類 其描述的語言為其描述的語言為 L2(GS)=x | x a, b+ 且且x中中a和和b的個數(shù)相同的個數(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 文法和語言的分類文法和語言的分類 2

26、.6 2.6 文法和語言的分類文法和語言的分類 1型文法（上下文有關(guān)文法）型文法（上下文有關(guān)文法） 1型文法也稱為上下文有關(guān)文法，型文法也稱為上下文有關(guān)文法， 相應(yīng)相應(yīng) 的語言又稱為的語言又稱為上下文有關(guān)語言上下文有關(guān)語言。 若文法若文法G=(VN,VT, P, S)中的每一條規(guī)則的中的每一條規(guī)則的 形式為形式為 A , 其中：其中： , (VNVT)* ,A VN ,則稱則稱G是是1型文法型文法。1型文法描述的型文法描述的語言是語言是1型語言。型語言。1型語言由線性型語言由線性界限自動機(jī)識別。界限自動機(jī)識別。 (VNVT)+2.6 2.6 文法和語言的分類文法和語言的分類 例如，有例如，有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型語言為型語言為L1(GS)=anbncn | n1 2.6 2.6 文法和語言的分類文法和語言的分類 0型文法（無限制文法）型文法（無限制文法） 若文法若文法G=(VN,VT, P, S)中的每條規(guī)則中的每條規(guī)則 是這樣一種結(jié)構(gòu)：是這樣一種結(jié)構(gòu)： 而且而且中至少含一個非終結(jié)符中至少含一個非終結(jié)符, 則稱則稱G 是是0型文法型文法。 (VNVT)+ , (VNVT)*0型文法描述的

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

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

30、程序設(shè)計語言的，在 實(shí)際應(yīng)用中需要對文法加一些限制條件。實(shí)際應(yīng)用中需要對文法加一些限制條件。 1. 文法中不能含有形如文法中不能含有形如A A 的規(guī)則。的規(guī)則。這種規(guī)則我們稱之為這種規(guī)則我們稱之為有害規(guī)則有害規(guī)則。對文法的實(shí)用限制有以下兩點(diǎn)：對文法的實(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 的左部符號的左部符號A不在不在所屬文法的任何其他規(guī)則所屬文法的任何其他規(guī)則右部右部出現(xiàn)，即出現(xiàn)，即在

31、推導(dǎo)文法的所有句子中始終都不可能在推導(dǎo)文法的所有句子中始終都不可能用到的規(guī)則。用到的規(guī)則。 (2) 對文法中的某個非終結(jié)符對文法中的某個非終結(jié)符A，無法無法從它推出任何終結(jié)符號串來。從它推出任何終結(jié)符號串來。 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è)計語言的若程序設(shè)計語言的文法含有多余規(guī)則文法含有多

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

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

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

35、 根據(jù)語言句子的根據(jù)語言句子的結(jié)構(gòu)特征結(jié)構(gòu)特征，設(shè)計出相，設(shè)計出相應(yīng)規(guī)則應(yīng)規(guī)則 例例3. 給出語言給出語言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. 寫一個寫一個 文法文法, ,使其語言是正偶數(shù)的集合使其語言是正偶數(shù)的集合, ,每每個偶數(shù)不以個偶數(shù)不以0 0開頭。開頭。P4

36、: NE | AE N2 | 4 | 6 | 8 | BN 或或分析分析 不以不以0開頭的偶數(shù)集合中串的結(jié)構(gòu)特征開頭的偶數(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. 給出語言給出語言L=1n0m1m0n | n,m0的的文法。文法。分析分析 根據(jù)語言句子的結(jié)構(gòu)特征根據(jù)語言句子的結(jié)構(gòu)特征, 設(shè)計設(shè)計

37、 出相應(yīng)規(guī)則出相應(yīng)規(guī)則 L=,01,0011,10,1100,1010,100110, 110100,11001100本章小結(jié)本章小結(jié)P : S a | 0S0 | 1S1例例6. 給出語言給出語言L= WaWt | W0|1* * ， 其中其中 W Wt t表示表示W(wǎng) W的逆的文法的逆的文法。分析分析 根據(jù)語言句子的結(jié)構(gòu)特征，設(shè)計根據(jù)語言句子的結(jié)構(gòu)特征，設(shè)計 出相應(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. 已知一個文法，確定該文法所定義的已知一個文法，確定該文法所定義的 語言。語言。 (2) 給定一個文法，可根據(jù)語言和推導(dǎo)定給定一個文法，可根據(jù)語言和推導(dǎo)定 義推導(dǎo)出文法的句子，從而確定出該文法義推導(dǎo)出文法的句子，從而確定出該文法 所定義的語言。所定義的語言。 (1) 文法所定義的語言文法所定義的語言 L(GS)=x|S x且且xVT*本章小結(jié)本章小結(jié) 自然語言描述。自然語言描述。 例如例如, L=x|xa,b+且且x中中a,b個數(shù)相同個數(shù)相同式子描述。例如式子描述。例如 L=a2nbb | n0。正規(guī)式描述。正規(guī)式描述。 (3) 語言可用語言可用本章小結(jié)本章

39、小結(jié) 例例1 文法文法GA=(A,a,b,AbA | a, A) 所生成的語言是什么？所生成的語言是什么？ 分析分析 AbAbbAbbbAbnAbna L(GA)= bna | n0 本章小結(jié)本章小結(jié)例例2 文法文法GN為為:N ND | DD 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9(1) GN所生成的語言是什么？所生成的語言是什么？ (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 該文法該文法 所生成的語言是什么？所生成的語言是什么？ A aAb | ab

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