形式語(yǔ)言簡(jiǎn)介

1、第二章第二章 形式語(yǔ)言簡(jiǎn)介形式語(yǔ)言簡(jiǎn)介 形式語(yǔ)言和自動(dòng)機(jī)理論中的形式語(yǔ)言和自動(dòng)機(jī)理論中的語(yǔ)言語(yǔ)言是是一個(gè)廣泛的概念。一個(gè)廣泛的概念。 一個(gè)字母表上的一個(gè)字母表上的語(yǔ)言語(yǔ)言就是該就是該字母表字母表的某些的某些字符串字符串的的集合集合。 語(yǔ)言中的字符串稱為該語(yǔ)言的語(yǔ)言中的字符串稱為該語(yǔ)言的句子句子l語(yǔ)言的的定義可以從兩個(gè)方面進(jìn)行：語(yǔ)言的的定義可以從兩個(gè)方面進(jìn)行： ）從）從產(chǎn)生產(chǎn)生語(yǔ)言的角度；語(yǔ)言的角度； ）從）從接收接收(或或識(shí)別識(shí)別)語(yǔ)言的角度。語(yǔ)言的角度。l產(chǎn)生一個(gè)語(yǔ)言，目的就是根據(jù)語(yǔ)言中產(chǎn)生一個(gè)語(yǔ)言，目的就是根據(jù)語(yǔ)言中的的基本句子基本句子和句子的和句子的形成規(guī)則形成規(guī)則，得到，得到(產(chǎn)生產(chǎn)生

2、)該語(yǔ)言所包含的該語(yǔ)言所包含的所有句子所有句子。l這是這是形式語(yǔ)言形式語(yǔ)言所研究的問題。所研究的問題。l接收一個(gè)語(yǔ)言，目的就是使用某種接收一個(gè)語(yǔ)言，目的就是使用某種自自動(dòng)機(jī)模型動(dòng)機(jī)模型來(lái)來(lái)接收接收句子，該模型所接收句子，該模型所接收的所有句子，也形成一個(gè)語(yǔ)言。的所有句子，也形成一個(gè)語(yǔ)言。l這是這是自動(dòng)機(jī)自動(dòng)機(jī)所研究的問題。所研究的問題。 l本章介紹本章介紹形式語(yǔ)言形式語(yǔ)言的基本內(nèi)容。的基本內(nèi)容。語(yǔ)言的形式定義語(yǔ)言的形式定義l設(shè)設(shè) 是一個(gè)是一個(gè)字母表字母表， l l * *, , l l稱為稱為字母表字母表 上上的一個(gè)的一個(gè)語(yǔ)言語(yǔ)言, , w w l l, w, w稱為語(yǔ)言稱為語(yǔ)言l l的一個(gè)的

3、一個(gè)句子句子。2.1 例子語(yǔ)言例子語(yǔ)言l括號(hào)匹配串的語(yǔ)言。括號(hào)匹配串的語(yǔ)言。 該語(yǔ)言是指所有的左括號(hào)和右括號(hào)相該語(yǔ)言是指所有的左括號(hào)和右括號(hào)相匹配的串的集合；匹配的串的集合； ( )，( )，( )( )等等都是該語(yǔ)言的句子等等都是該語(yǔ)言的句子 )( ，( )等等不是該語(yǔ)言的句子。等等不是該語(yǔ)言的句子。 l如何如何產(chǎn)生產(chǎn)生這個(gè)語(yǔ)言呢？這個(gè)語(yǔ)言呢？ 即如何即如何產(chǎn)生產(chǎn)生該語(yǔ)言所有句子呢？該語(yǔ)言所有句子呢？l實(shí)際上，就是需要給出語(yǔ)言中句子的實(shí)際上，就是需要給出語(yǔ)言中句子的構(gòu)造（形成）規(guī)則構(gòu)造（形成）規(guī)則。l遞歸定義遞歸定義提供了語(yǔ)言的良好的定義方提供了語(yǔ)言的良好的定義方式，使得語(yǔ)言中的句子的構(gòu)造規(guī)

4、律較式，使得語(yǔ)言中的句子的構(gòu)造規(guī)律較明顯。明顯。l可以使用多種方法可以使用多種方法描述描述構(gòu)造規(guī)則。構(gòu)造規(guī)則。l自然語(yǔ)言自然語(yǔ)言的描述方式，采用如下的的描述方式，采用如下的 遞歸規(guī)則：遞歸規(guī)則：( )是該語(yǔ)言的最基本的句子；是該語(yǔ)言的最基本的句子；若若s是句子是句子,則則(s)是句子；是句子；若若s是句子是句子,則則ss是句子；是句子；l這些規(guī)則稱為這些規(guī)則稱為形成規(guī)則形成規(guī)則，根據(jù)這些規(guī)則，根據(jù)這些規(guī)則，可以可以 (1)產(chǎn)生該語(yǔ)言的任意的句子；產(chǎn)生該語(yǔ)言的任意的句子； (2)判斷某個(gè)判斷某個(gè)串串是否是該語(yǔ)言的句子。是否是該語(yǔ)言的句子。例如l可以產(chǎn)生句子可以產(chǎn)生句子（）（） 而推斷串而推斷串

5、（）（） 不是句子。不是句子。l規(guī)則規(guī)則(的個(gè)數(shù)的個(gè)數(shù))是有限的，但可以產(chǎn)生無(wú)是有限的，但可以產(chǎn)生無(wú)限個(gè)句子和長(zhǎng)度無(wú)限的句子；限個(gè)句子和長(zhǎng)度無(wú)限的句子；l因?yàn)橐?guī)則是因?yàn)橐?guī)則是遞歸遞歸的。的。bnf的描述方式的描述方式l巴科斯和諾爾采用的巴科斯和諾爾采用的巴科斯巴科斯-諾爾范式（諾爾范式（bnf-backus-naur form）描述規(guī)則描述規(guī)則：l:= ( )l:=()l:= l使用尖括號(hào)使用尖括號(hào)“”包括起來(lái)的部分，作包括起來(lái)的部分，作為一個(gè)整體來(lái)看待，表示某個(gè)語(yǔ)法成分為一個(gè)整體來(lái)看待，表示某個(gè)語(yǔ)法成分 需要使用字母表中的字母來(lái)定義其構(gòu)成需要使用字母表中的字母來(lái)定義其構(gòu)成l符號(hào)符號(hào)“:=”是

6、是bnf本身的符號(hào)（元符號(hào)），本身的符號(hào)（元符號(hào)），代表代表“定義為定義為”或或“是是”。l符號(hào)符號(hào)“( ”和和“ )”是字母表的元素。是字母表的元素。lchomsky采用的符號(hào)化采用的符號(hào)化(形式化形式化)的描述的描述方式，運(yùn)用如下的規(guī)則（這些規(guī)則被稱方式，運(yùn)用如下的規(guī)則（這些規(guī)則被稱為為產(chǎn)生式產(chǎn)生式）：）： s( ) s(s) sss “ “”代表代表“定義為定義為”或者或者“是是” ” ， 它的左邊和右邊分別稱為該產(chǎn)生式的它的左邊和右邊分別稱為該產(chǎn)生式的左邊左邊和和右邊右邊根據(jù)產(chǎn)生式 可以生成任意句子；可以生成任意句子； 可以判斷一個(gè)串是否為句子可以判斷一個(gè)串是否為句子(語(yǔ)法分析語(yǔ)法分析

7、)產(chǎn)生句子的過程 從從s開始，利用產(chǎn)生式的右邊開始，利用產(chǎn)生式的右邊代替代替產(chǎn)產(chǎn)生式的左邊（稱之為生式的左邊（稱之為推導(dǎo)過程推導(dǎo)過程） 進(jìn)行多次推導(dǎo)，可以得到括號(hào)匹配的進(jìn)行多次推導(dǎo)，可以得到括號(hào)匹配的的句子。的句子。例例:句子( )( )( ( )( )( )( ) )的推導(dǎo)過程的推導(dǎo)過程 s = =s ss s =( =(s s)s)s =( ) =( )s s =( )( =( )(s s) ) =( )( =( )(s ss)s) =( )( ) =( )( )s s) ) = ( )( )( ) = ( )( )( ) 產(chǎn)生式的個(gè)數(shù)是有限的，規(guī)則是遞歸產(chǎn)生式的個(gè)數(shù)是有限的，規(guī)則是遞歸的

8、，因而所有的小括號(hào)匹配的串，都可的，因而所有的小括號(hào)匹配的串，都可以由產(chǎn)生式產(chǎn)生；以由產(chǎn)生式產(chǎn)生； 它們組成的集合就稱為一個(gè)語(yǔ)言。它們組成的集合就稱為一個(gè)語(yǔ)言。ls稱為稱為非終結(jié)符非終結(jié)符，在推導(dǎo)過程中，可以被，在推導(dǎo)過程中，可以被代替的符號(hào)。代替的符號(hào)。l(和和)稱為稱為終結(jié)符終結(jié)符，在推導(dǎo)過程中，不可以，在推導(dǎo)過程中，不可以被代替的符號(hào)。被代替的符號(hào)。l 是產(chǎn)生式系統(tǒng)的是產(chǎn)生式系統(tǒng)的元符號(hào)元符號(hào)，不屬于非終，不屬于非終結(jié)符，也不屬于非終結(jié)符。結(jié)符，也不屬于非終結(jié)符。例例2-1：由偶數(shù)個(gè)：由偶數(shù)個(gè)0組成的串的語(yǔ)言。組成的串的語(yǔ)言。 規(guī)則的自然語(yǔ)言描述方式：規(guī)則的自然語(yǔ)言描述方式：00是該語(yǔ)言

9、的基本的句子；是該語(yǔ)言的基本的句子；若若s是句子是句子,則則00s是句子。是句子。 形式化的描述方式：形式化的描述方式： s00 s00s 問題：?jiǎn)栴}：將產(chǎn)生式將產(chǎn)生式sss換成換成s0s0或或ss00或或sss是否還產(chǎn)生相同的語(yǔ)言？是否還產(chǎn)生相同的語(yǔ)言？ 結(jié)論：結(jié)論： 一個(gè)語(yǔ)言，可以使用不同的產(chǎn)生式組一個(gè)語(yǔ)言，可以使用不同的產(chǎn)生式組合來(lái)產(chǎn)生。合來(lái)產(chǎn)生?？紤]由奇數(shù)個(gè)由奇數(shù)個(gè)1組成串的語(yǔ)言（產(chǎn)生規(guī)則）組成串的語(yǔ)言（產(chǎn)生規(guī)則）例2-2 高級(jí)程序設(shè)計(jì)語(yǔ)言中的算術(shù)表達(dá)式高級(jí)程序設(shè)計(jì)語(yǔ)言中的算術(shù)表達(dá)式(的的語(yǔ)言語(yǔ)言)的產(chǎn)生。的產(chǎn)生。 自然語(yǔ)言的描述方式自然語(yǔ)言的描述方式單個(gè)變量是最基本的單個(gè)變量是最基本

10、的句子句子；若若e是一個(gè)是一個(gè)句子句子，則，則eae是一個(gè)是一個(gè)句子句子（其中（其中a代表運(yùn)算符代表運(yùn)算符+、-、*、/）若若e是一個(gè)是一個(gè)句子句子，則，則(e)是是句子句子；形式語(yǔ)言的描述方式形式語(yǔ)言的描述方式 e i （i代表單個(gè)變量）代表單個(gè)變量） eeae e(e) a+ a- a* a/思考：思考：字母表為？字母表為？ 若以若以a開始推導(dǎo)，則產(chǎn)生？開始推導(dǎo)，則產(chǎn)生？其中其中 ： a+，a-，a*，a/ 四個(gè)產(chǎn)生式四個(gè)產(chǎn)生式的左邊是相同的符號(hào)，可以合并為的左邊是相同的符號(hào)，可以合并為 a+|-|*|/ +、-、*、/ 稱為稱為a的的侯選式侯選式。 e i eeae e(e)也可以記為：

11、也可以記為： e i|eae|(e)注意：注意： 這組產(chǎn)生式這組產(chǎn)生式?jīng)]有表示出運(yùn)算符的沒有表示出運(yùn)算符的優(yōu)先級(jí)優(yōu)先級(jí)。表示出運(yùn)算符的優(yōu)先級(jí)的產(chǎn)生式：表示出運(yùn)算符的優(yōu)先級(jí)的產(chǎn)生式： ee+t|e-t|t tt*f|t/f|f f(e)|il其中：其中：e e代表表達(dá)式，代表表達(dá)式，t t代表項(xiàng)，代表項(xiàng)，f f代表因子代表因子(e)(e)代表的是帶小括號(hào)的表達(dá)式。代表的是帶小括號(hào)的表達(dá)式。表示：先算因子，再表示：先算因子，再* *、/ /，最后，最后+ +、- -。 如果使用如果使用% %代表模運(yùn)算代表模運(yùn)算( (即取余數(shù)運(yùn)算即取余數(shù)運(yùn)算) )、使用使用 代表指數(shù)運(yùn)算，則有代表指數(shù)運(yùn)算，則有 e

12、e+t|e-t|tee+t|e-t|t tt tt* *f|t/f|t%f|af|t/f|t%f|a afa|fafa|f f(e)|i f(e)|i注意需要考慮需要考慮 運(yùn)算的運(yùn)算的結(jié)合性結(jié)合性： 是右結(jié)合的。是右結(jié)合的。例2-3 標(biāo)識(shí)符標(biāo)識(shí)符( (以字母開頭的字母、數(shù)字的以字母開頭的字母、數(shù)字的串串) )的產(chǎn)生的產(chǎn)生( (僅考慮小寫字母僅考慮小寫字母) )。 從標(biāo)識(shí)符的形成角度考慮從標(biāo)識(shí)符的形成角度考慮iliiliidla|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t u|v|w|x|y|zd0|1|2|3|4|5|6|7|8|9思考：上例是從標(biāo)識(shí)符的上例是從

13、標(biāo)識(shí)符的形成角度形成角度思考問題。思考問題。從標(biāo)識(shí)符的從標(biāo)識(shí)符的定義定義角度考慮，則？角度考慮，則？注意 d0|1|2|3|4|5|6|7|8|9不能簡(jiǎn)寫為不能簡(jiǎn)寫為 d0|9將i的定義加入到表達(dá)式中： ee+t|e-t|t tt*f |t/f|f f (e)|i il|il|id l d思考思考: 其他類型的表達(dá)式（如關(guān)系表達(dá)式等）其他類型的表達(dá)式（如關(guān)系表達(dá)式等）的定義：的定義：、=、= 標(biāo)識(shí)符標(biāo)識(shí)符(以以下劃線下劃線或字母開頭的字母、下或字母開頭的字母、下劃線和數(shù)字的串劃線和數(shù)字的串)的產(chǎn)生。的產(chǎn)生。例例2-42-4c c語(yǔ)言中簡(jiǎn)單變量的說(shuō)明語(yǔ)句的定義。語(yǔ)言中簡(jiǎn)單變量的說(shuō)明語(yǔ)句的定義。

14、c c語(yǔ)言中的說(shuō)明語(yǔ)句形式為：語(yǔ)言中的說(shuō)明語(yǔ)句形式為： type type 變量名表；變量名表； type type 變量名表；變量名表； type type 變量名表；變量名表；產(chǎn)生式為：產(chǎn)生式為： ssssss|p|p pt v pt v； tint|char|floattint|char|float v vv,vv,v|i |i il|il|id l d思考pascalpascal語(yǔ)言的簡(jiǎn)單變量的說(shuō)明語(yǔ)句的形成。語(yǔ)言的簡(jiǎn)單變量的說(shuō)明語(yǔ)句的形成。 var 變量名表變量名表: type; 變量名表變量名表: type ; 變量名表變量名表: type; 2.2 文法和語(yǔ)言的關(guān)系文法和語(yǔ)言的關(guān)

15、系語(yǔ)言的定義語(yǔ)言的定義文法的定義文法的定義文法與語(yǔ)言的關(guān)系文法與語(yǔ)言的關(guān)系再次強(qiáng)調(diào)：再次強(qiáng)調(diào)： 語(yǔ)言就是字母表上的字符串語(yǔ)言就是字母表上的字符串組成的一個(gè)集合。組成的一個(gè)集合。 語(yǔ)言中的字符串稱為語(yǔ)言中的字符串稱為句子句子。 文法的作用就是產(chǎn)生一個(gè)語(yǔ)言。文法的作用就是產(chǎn)生一個(gè)語(yǔ)言。 有窮語(yǔ)言的表示較容易。有窮語(yǔ)言的表示較容易。 即使語(yǔ)言中的句子的組成沒有什即使語(yǔ)言中的句子的組成沒有什么規(guī)律，也可以使用么規(guī)律，也可以使用枚舉枚舉的方式列的方式列出語(yǔ)言中的所有句子。出語(yǔ)言中的所有句子。 對(duì)于對(duì)于無(wú)窮語(yǔ)言無(wú)窮語(yǔ)言，需要使用有窮描述的，需要使用有窮描述的方式表達(dá)。方式表達(dá)。 需要從語(yǔ)言的句子的一般構(gòu)成

16、規(guī)律去需要從語(yǔ)言的句子的一般構(gòu)成規(guī)律去考慮問題?？紤]問題。 從語(yǔ)言的從語(yǔ)言的有窮描述有窮描述來(lái)表達(dá)語(yǔ)言的方法來(lái)表達(dá)語(yǔ)言的方法對(duì)對(duì)大多數(shù)語(yǔ)言大多數(shù)語(yǔ)言是有效的。是有效的。 在（使用計(jì)算機(jī)）判斷一個(gè)字符在（使用計(jì)算機(jī)）判斷一個(gè)字符串是否是某個(gè)語(yǔ)言的句子時(shí)串是否是某個(gè)語(yǔ)言的句子時(shí)( (語(yǔ)法語(yǔ)法分析分析) ) 從句子和語(yǔ)言的從句子和語(yǔ)言的結(jié)構(gòu)特征結(jié)構(gòu)特征上著手上著手是非常重要的。是非常重要的。 對(duì)于語(yǔ)言，可以在字母表上，按照一對(duì)于語(yǔ)言，可以在字母表上，按照一定的構(gòu)成規(guī)則，根據(jù)語(yǔ)言的結(jié)構(gòu)特點(diǎn)，定的構(gòu)成規(guī)則，根據(jù)語(yǔ)言的結(jié)構(gòu)特點(diǎn)，可以定義一個(gè)產(chǎn)生該語(yǔ)言的可以定義一個(gè)產(chǎn)生該語(yǔ)言的文法文法。 使用使用文法文法作

17、為相應(yīng)語(yǔ)言的有窮描述，作為相應(yīng)語(yǔ)言的有窮描述，不僅可以描述出語(yǔ)言的不僅可以描述出語(yǔ)言的結(jié)構(gòu)特征結(jié)構(gòu)特征，而且，而且可以可以產(chǎn)生產(chǎn)生這個(gè)語(yǔ)言的這個(gè)語(yǔ)言的所有句子所有句子。定義定義2-1 短語(yǔ)結(jié)構(gòu)文法短語(yǔ)結(jié)構(gòu)文法(文法文法)的定義的定義文法文法g是一個(gè)四元式，是一個(gè)四元式， g=(，v，s，p) 是一個(gè)有限字符的集合是一個(gè)有限字符的集合(字母表字母表)，它的，它的元素稱為字母或者終結(jié)符；元素稱為字母或者終結(jié)符； v是一個(gè)有限字符的集合是一個(gè)有限字符的集合-非終結(jié)符集合，非終結(jié)符集合，它的元素稱為變量或者非終結(jié)符；它的元素稱為變量或者非終結(jié)符；短語(yǔ)結(jié)構(gòu)文法短語(yǔ)結(jié)構(gòu)文法(文法文法)的定義的定義 sv，

18、稱為文法的開始符號(hào)；，稱為文法的開始符號(hào)； p是有序偶對(duì)是有序偶對(duì)(，)的集合，其中的集合，其中是集是集合合(uv)上的字符串，但至少包含一個(gè)上的字符串，但至少包含一個(gè)非終結(jié)符；非終結(jié)符；是集合是集合(uv)*的元素。的元素。 一般，將有序偶對(duì)一般，將有序偶對(duì)(，)記為記為，稱，稱為產(chǎn)生式；為產(chǎn)生式； 如果有如果有，稱之為空串產(chǎn)生式或者，稱之為空串產(chǎn)生式或者產(chǎn)生式。產(chǎn)生式。 如果如果有有abab，稱之為單產(chǎn)生式。，稱之為單產(chǎn)生式。 一個(gè)產(chǎn)生式的左邊可能不只一個(gè)符號(hào)；一個(gè)產(chǎn)生式的左邊可能不只一個(gè)符號(hào)； 第一個(gè)產(chǎn)生式的左邊只能有一個(gè)符號(hào)，第一個(gè)產(chǎn)生式的左邊只能有一個(gè)符號(hào)，就是就是開始符號(hào)開始符號(hào)s

19、。文法文法的作用就是產(chǎn)生一個(gè)的作用就是產(chǎn)生一個(gè)語(yǔ)言語(yǔ)言。約定：如果沒有特別說(shuō)明約定：如果沒有特別說(shuō)明,則則 第一個(gè)產(chǎn)生式左邊的符號(hào)，就是開始符第一個(gè)產(chǎn)生式左邊的符號(hào)，就是開始符號(hào)，號(hào)，可以不為可以不為s； 大寫的英文字母代表非終結(jié)符；大寫的英文字母代表非終結(jié)符； 小寫的英文字母小寫的英文字母a，b，c，d，e和數(shù)字和數(shù)字代表終結(jié)符；代表終結(jié)符； 小寫的英文字母小寫的英文字母u，v，w，x，y，z代代表表 終結(jié)符串；終結(jié)符串； 小寫的希臘字母小寫的希臘字母，代表非終結(jié)符和代表非終結(jié)符和終結(jié)符串；終結(jié)符串； 推導(dǎo)（派生）的定義推導(dǎo)（派生）的定義2-2 文法文法g，和和是集合是集合(uv)上的串上的

20、串 = pvr ，=pur(p和和r可能同時(shí)為可能同時(shí)為) 而而vu是文法是文法g的一個(gè)產(chǎn)生式的一個(gè)產(chǎn)生式,則稱則稱可以可以直接推導(dǎo)出直接推導(dǎo)出 ， 記為記為= ，既，既 pvr =pur。推導(dǎo)的實(shí)質(zhì)推導(dǎo)的實(shí)質(zhì) 產(chǎn)生式的產(chǎn)生式的右邊右邊替換替換產(chǎn)生式的產(chǎn)生式的左邊左邊 非終結(jié)符非終結(jié)符代表在推導(dǎo)的過程中可以被代表在推導(dǎo)的過程中可以被替代的符號(hào)，替代的符號(hào)， 終結(jié)符終結(jié)符代表在推導(dǎo)的過程中不可以被代表在推導(dǎo)的過程中不可以被替代的符號(hào)。替代的符號(hào)。 推導(dǎo)推導(dǎo)的的逆逆過程稱為過程稱為歸約歸約。 與與pvr =pur對(duì)應(yīng)，稱串對(duì)應(yīng)，稱串pur可以直可以直接歸約成串接歸約成串pvr 記為記為pvr +z

21、 表示表示y可以經(jīng)過可以經(jīng)過多步多步推導(dǎo)出推導(dǎo)出z，即，即 存在串的序列存在串的序列 1， 2， 3 ， n ； 有有y= 1 ，z= n ， 且且 i= i+1；對(duì)所有；對(duì)所有ni1。任意步推導(dǎo)任意步推導(dǎo)(包括0步) y=*z 表示表示y可以經(jīng)過可以經(jīng)過任意步任意步推導(dǎo)出推導(dǎo)出z，即即 y=z；或者；或者 y=+z。思考：思考：對(duì)于任意文法對(duì)于任意文法g： s=*s s=+s 一定都成立嗎一定都成立嗎？最左推導(dǎo)和最右推導(dǎo)最左推導(dǎo)和最右推導(dǎo) 如果在推導(dǎo)的過程中，如果在推導(dǎo)的過程中，每一步每一步都都是將推導(dǎo)產(chǎn)生的串的是將推導(dǎo)產(chǎn)生的串的最左邊最左邊的非終的非終結(jié)符代替掉結(jié)符代替掉-最左推導(dǎo)最左推導(dǎo)

22、 如果每一步都是將推導(dǎo)產(chǎn)生的串如果每一步都是將推導(dǎo)產(chǎn)生的串的最右邊的非終結(jié)符代替掉的最右邊的非終結(jié)符代替掉-最右最右推導(dǎo)推導(dǎo)(規(guī)范推導(dǎo)規(guī)范推導(dǎo))， 當(dāng)然，還有其它方式的推導(dǎo)過程當(dāng)然，還有其它方式的推導(dǎo)過程（例如混合）（例如混合） 而而最左推導(dǎo)最左推導(dǎo)和和最右推導(dǎo)最右推導(dǎo)是比較常用是比較常用的推導(dǎo)方式。的推導(dǎo)方式。句型和句子 對(duì)于文法對(duì)于文法g，如果，如果s=*，則稱，則稱是文法的一個(gè)是文法的一個(gè)句型句型， 若若 * *, , 稱為稱為句子句子。定義定義2-3 語(yǔ)言的定義語(yǔ)言的定義 給定文法給定文法g，有開始符號(hào)，有開始符號(hào)s，則把，則把s可可以推導(dǎo)出所有句子的集合，稱為由文法以推導(dǎo)出所有句子的

23、集合，稱為由文法產(chǎn)生的語(yǔ)言，記為產(chǎn)生的語(yǔ)言，記為l(g)，即，即 l(g)=|s=*，且且*例l文法文法 g=(,),s,s, s( ), s(s), sss ) 產(chǎn)生語(yǔ)言產(chǎn)生語(yǔ)言 l(g)=w|w是括號(hào)匹配的串是括號(hào)匹配的串注意注意:文法文法g產(chǎn)生語(yǔ)言產(chǎn)生語(yǔ)言l，必須：，必須：g推導(dǎo)產(chǎn)生的所有推導(dǎo)產(chǎn)生的所有句子句子都在都在l中中l(wèi)的任意一個(gè)的任意一個(gè)句子句子都可以由都可以由g產(chǎn)產(chǎn)生生對(duì)于文法對(duì)于文法g=(，v，s，p)約定：約定： 第一個(gè)產(chǎn)生式左邊的符號(hào)，就是開第一個(gè)產(chǎn)生式左邊的符號(hào)，就是開始符號(hào)（始符號(hào)（可以不是可以不是s）； 大寫的英文字母代表非終結(jié)符大寫的英文字母代表非終結(jié)符。 對(duì)于文

24、法（對(duì)于文法（g），只需給出該文法的），只需給出該文法的所有產(chǎn)生式即可。所有產(chǎn)生式即可。產(chǎn)生括號(hào)匹配語(yǔ)言的文法可以寫成產(chǎn)生括號(hào)匹配語(yǔ)言的文法可以寫成 s( ) s(s) sss 還可以再簡(jiǎn)單寫成還可以再簡(jiǎn)單寫成 s( )|(s)|ss 文法和語(yǔ)言的文法和語(yǔ)言的3類問題類問題 已知已知文法文法,得到該文法產(chǎn)生的得到該文法產(chǎn)生的語(yǔ)言語(yǔ)言 已知已知語(yǔ)言語(yǔ)言,構(gòu)造產(chǎn)生該語(yǔ)言的構(gòu)造產(chǎn)生該語(yǔ)言的某個(gè)某個(gè)文法文法 判斷判斷一個(gè)語(yǔ)言是否由某一個(gè)文法產(chǎn)生一個(gè)語(yǔ)言是否由某一個(gè)文法產(chǎn)生關(guān)系關(guān)系1： 文法文法 sasa|bsb|c| 產(chǎn)生的語(yǔ)言是什么？產(chǎn)生的語(yǔ)言是什么？ s能夠產(chǎn)生的所有句子，需要考能夠產(chǎn)生的所有句子

25、，需要考慮慮3個(gè)產(chǎn)生式個(gè)產(chǎn)生式所有可能使用情況所有可能使用情況 注意注意對(duì)稱性對(duì)稱性關(guān)系關(guān)系2：構(gòu)造產(chǎn)生語(yǔ)言構(gòu)造產(chǎn)生語(yǔ)言l的文法。的文法。 l= wwt|wa,b,c+其中：其中：wt是是w的逆（反序）的逆（反序）思考：思考：產(chǎn)生下列語(yǔ)言的文法：產(chǎn)生下列語(yǔ)言的文法： l1=anbn|n0 l2=anbn|n0關(guān)系關(guān)系3： 文法文法 s0b|1a a0|0s|1aa b1|1s|0bb是否產(chǎn)生的語(yǔ)言是否產(chǎn)生的語(yǔ)言l： l=|0,1+， 且且中有中有相同多相同多的的0和和1？注意： 一個(gè)語(yǔ)言一個(gè)語(yǔ)言可以可以由多個(gè)不同的文由多個(gè)不同的文法產(chǎn)生。法產(chǎn)生。 一個(gè)文法一個(gè)文法只能只能產(chǎn)生一個(gè)語(yǔ)言。產(chǎn)生一個(gè)

26、語(yǔ)言。例例2-5 g1：s0|1|00|11 g2：sa|b|aa|bb a0 b1l(g1)=l(g2)=0,1,00,11文法等價(jià)文法等價(jià) 如果文法如果文法g1和文法和文法g2產(chǎn)生同一產(chǎn)生同一個(gè)語(yǔ)言，則稱文法個(gè)語(yǔ)言，則稱文法g1和和g2是是等價(jià)等價(jià)的文法。的文法。 l(g1)= l(g2)注意區(qū)別：文法文法g1g1和和g2g2等價(jià)等價(jià)文法文法g1g1和和g2g2相同相同。 2.3chomsky對(duì)文法的分類對(duì)文法的分類 chomsky chomsky對(duì)文法進(jìn)行了分類；對(duì)文法進(jìn)行了分類； 對(duì)語(yǔ)言的分類，是根據(jù)產(chǎn)生語(yǔ)言的對(duì)語(yǔ)言的分類，是根據(jù)產(chǎn)生語(yǔ)言的文法的分類進(jìn)行的文法的分類進(jìn)行的0型文法 對(duì)于

27、一般的短語(yǔ)結(jié)構(gòu)文法對(duì)于一般的短語(yǔ)結(jié)構(gòu)文法(psg) g=(，v，s，p) g稱為稱為0型文法，對(duì)應(yīng)的型文法，對(duì)應(yīng)的l(g)稱為稱為0型語(yǔ)言或者短語(yǔ)結(jié)構(gòu)語(yǔ)言型語(yǔ)言或者短語(yǔ)結(jié)構(gòu)語(yǔ)言(psl)、遞歸可枚舉集遞歸可枚舉集。1型文法 如果對(duì)于任意如果對(duì)于任意p，均有，均有| | |成立，則稱成立，則稱g為為1型文法，或型文法，或上下文相關(guān)文法上下文相關(guān)文法(csg)。 對(duì)應(yīng)的對(duì)應(yīng)的l(g)稱為稱為1型語(yǔ)言或者上型語(yǔ)言或者上下文相關(guān)語(yǔ)言下文相關(guān)語(yǔ)言(csl)。1型文法1型文法產(chǎn)生式的標(biāo)準(zhǔn)形式為：型文法產(chǎn)生式的標(biāo)準(zhǔn)形式為： yazyz其中：其中：av； y,z(v)*， (v)+；1型文法 可以證明，任意的

28、可以證明，任意的1型文法，都型文法，都可以改造為可以改造為1型文法的標(biāo)準(zhǔn)形式。型文法的標(biāo)準(zhǔn)形式。2型文法 如果對(duì)于任意如果對(duì)于任意p，均有，均有| | |且且 v成立，則稱成立，則稱g為為2型型文法，或文法，或上下文無(wú)關(guān)文法上下文無(wú)關(guān)文法(cfg) 對(duì)應(yīng)的對(duì)應(yīng)的l(g)稱為稱為2型語(yǔ)言或者上下型語(yǔ)言或者上下文無(wú)關(guān)語(yǔ)言文無(wú)關(guān)語(yǔ)言(cfl)。3型文法 如果對(duì)于任意如果對(duì)于任意p，具有形式，具有形式 aw，awb其中，其中，a，bv，w+ 則稱則稱g為為3型文法，或右線性文法型文法，或右線性文法 rlg，也可稱為，也可稱為正則文法正則文法rg。 對(duì)應(yīng)的對(duì)應(yīng)的l(g)稱為稱為3型語(yǔ)言或型語(yǔ)言或 右線性

29、語(yǔ)右線性語(yǔ)言言rll或或 正則語(yǔ)言正則語(yǔ)言rl。 四類文法和對(duì)應(yīng)的四類四類文法和對(duì)應(yīng)的四類語(yǔ)言語(yǔ)言之間是之間是真包含真包含關(guān)系。關(guān)系。 思考思考 如果文法如果文法g有有產(chǎn)生式，則產(chǎn)生式，則g g是是 型文法型文法? ?文法分類判斷方法：文法分類判斷方法： 文法文法g=(，v，s，p)，則，則 1) g是短語(yǔ)結(jié)構(gòu)文法；是短語(yǔ)結(jié)構(gòu)文法； 2) 如果文法如果文法g的所有產(chǎn)生式的左的所有產(chǎn)生式的左邊邊長(zhǎng)度長(zhǎng)度小于等于右邊長(zhǎng)度部分，小于等于右邊長(zhǎng)度部分，那么那么g是是上下文相關(guān)文法上下文相關(guān)文法； 3) 如果上下文相關(guān)文法如果上下文相關(guān)文法g的所有產(chǎn)生的所有產(chǎn)生式的左邊都是式的左邊都是一個(gè)非終結(jié)符一個(gè)非

30、終結(jié)符，那么，那么g是是上下文無(wú)關(guān)文法上下文無(wú)關(guān)文法； 4) 如果如果上下文無(wú)關(guān)文法上下文無(wú)關(guān)文法g的所有產(chǎn)生式的所有產(chǎn)生式的右邊最多只有一個(gè)非終結(jié)符的右邊最多只有一個(gè)非終結(jié)符 且該非終結(jié)符號(hào)只能出現(xiàn)在最右邊，且該非終結(jié)符號(hào)只能出現(xiàn)在最右邊，那么那么g是是正則文法正則文法。文法文法g: s01|101s是是rg，cfg，csg和和psg文法文法g： saas|as aa|b|c|d是是cfg，csg和和psg，但不是，但不是rg。文法文法g sab abab是是csg和和psg，但不是，但不是cfg和和rg。文法文法g s ab abab aba是是psg，但不是，但不是cfg、rg和和csg

31、。 形如形如的產(chǎn)生式稱為空產(chǎn)生式，的產(chǎn)生式稱為空產(chǎn)生式，也可稱為也可稱為產(chǎn)生式產(chǎn)生式。 csg、cfg和和rg，都不能含有，都不能含有空產(chǎn)生式，所以任何空產(chǎn)生式，所以任何csl、cfl和和rl中都不包含中都不包含(空句子空句子)。 如果允許在如果允許在csg、cfg和和rg中中含有含有空產(chǎn)生式空產(chǎn)生式， 也就允許也就允許csl、cfl和和rl中包含中包含空句子空句子。 一般地，如果語(yǔ)言一般地，如果語(yǔ)言l沒有空句子，則沒有空句子，則 文法中增加產(chǎn)生式文法中增加產(chǎn)生式 s 就可以產(chǎn)生空句子。就可以產(chǎn)生空句子。文法文法擴(kuò)充分類擴(kuò)充分類： 設(shè)文法設(shè)文法g=(，v，s，p) 如果如果s不出現(xiàn)在任何產(chǎn)生式

32、的右不出現(xiàn)在任何產(chǎn)生式的右部部，則，則(1) 若若g是是csg g=(，v，s，ps)仍然仍然為為csg； l(g) 是是csl。(1) 若若g是是cfg g=(，v，s，ps)仍然仍然為為cfg；l(g) 是是cfl。 (1) 若若g是是rg g=(，v，s，ps) 仍然仍然為為rg； l(g) 是是rl。思考思考 為什么要有條件為什么要有條件 s不出現(xiàn)在任何產(chǎn)生式的右部？不出現(xiàn)在任何產(chǎn)生式的右部？設(shè)正則文法設(shè)正則文法rg：sab|as，則，則 l(g)=a+bg：sab|as|l(g)=a+b, , a+增加增加了空句子了空句子，但，但多多產(chǎn)生句子產(chǎn)生句子a+定理2-1 文法文法g=(，v

33、，s，p) ，存在與存在與g同類型的文法同類型的文法 g =(,v , s p ) ，使得，使得 l(g)=l(g )且且s 不出現(xiàn)不出現(xiàn)在在g 的任何產(chǎn)生式的任何產(chǎn)生式右部右部 證明： 先根據(jù)先根據(jù)g構(gòu)造構(gòu)造滿足條件的滿足條件的g ，然，然后證明兩者后證明兩者等價(jià)等價(jià)。 構(gòu)造構(gòu)造g =(，vs ,s ,p )其中其中p =ps|sp g 與與g有相同的類型。有相同的類型。g與g等價(jià) 即證明即證明l(g)=l(g ) 需要證明需要證明 l(g) l(g ) l(g ) l(g)特殊情況特殊情況 如果如果s不出現(xiàn)在不出現(xiàn)在p中任何產(chǎn)生式中任何產(chǎn)生式的右邊，則的右邊，則 g=g 思考 文法的文法的

34、s不出現(xiàn)在產(chǎn)生式的右部不出現(xiàn)在產(chǎn)生式的右部 那么，那么，s的的作用作用是什么？是什么？下列命題成立 有語(yǔ)言有語(yǔ)言l，設(shè)置，設(shè)置l = l (1)若若l是是csl，則，則l仍然是仍然是csl。 (2)若若l是是cfl，則，則l仍然是仍然是cfl。 (3)若若l是是rl，則，則l仍然是仍然是rl。證明： 證明第證明第(1)個(gè)命題，個(gè)命題， (2)(3)同理可證。同理可證。證明 設(shè)設(shè)l是是csl，則存在一個(gè)，則存在一個(gè) csg=(，v，s，p) 使得使得 l(g)=l。 設(shè)設(shè)s不出現(xiàn)在不出現(xiàn)在g的產(chǎn)生式右部。的產(chǎn)生式右部。構(gòu)造構(gòu)造 g =(,v,s,ps)g 也是也是csg。 s不出現(xiàn)在不出現(xiàn)在g中

35、產(chǎn)生式的右部中產(chǎn)生式的右部 增加的增加的s，不可能出現(xiàn)在非空不可能出現(xiàn)在非空句子的推導(dǎo)中，則句子的推導(dǎo)中，則 l(g )=l(g) l(g )是是csl。結(jié)論結(jié)論 增加空句子不影響語(yǔ)言的類型。增加空句子不影響語(yǔ)言的類型。同理刪除空句子也不影響語(yǔ)言的類型。刪除空句子也不影響語(yǔ)言的類型。下列命題成立有語(yǔ)言有語(yǔ)言l，l = l- (1)若若l是是csl，則，則l仍然是仍然是csl。 (2)若若l是是cfl，則，則l仍然是仍然是cfl。 (3)若若l是是rl，則，則l仍然是仍然是rl。證明： 證明第證明第(1)個(gè)命題，個(gè)命題， (2)(3)同理可證。同理可證。證明證明設(shè)設(shè)l是是csl，則存在一個(gè)，則存

36、在一個(gè) csg=(，v，s，p) 使得使得 l(g)=l。如果 l l-=l l- 是是csl。如果l 設(shè)設(shè)s不出現(xiàn)在不出現(xiàn)在g的產(chǎn)生式的右部。的產(chǎn)生式的右部。 構(gòu)造構(gòu)造 =(,v,s,p-s)， g 也是也是csg。 s不出現(xiàn)在不出現(xiàn)在g產(chǎn)生式的右部產(chǎn)生式的右部 去掉去掉s,則則不影響不影響任何非空任何非空句子句子的推導(dǎo)的推導(dǎo)， l(g )=l(g)-。 l(g )是是csl。 除了生成空句子除了生成空句子外，空產(chǎn)生式可外，空產(chǎn)生式可以不用于其他句子的推導(dǎo)中。以不用于其他句子的推導(dǎo)中。 空句子空句子在一個(gè)語(yǔ)言中的存在并不在一個(gè)語(yǔ)言中的存在并不影響該語(yǔ)言的有窮描述。影響該語(yǔ)言的有窮描述。 如果

37、如果允許允許csg,cfg,rg包含一般包含一般的的-產(chǎn)生式產(chǎn)生式 1)可能可能對(duì)問題的處理提供方便。對(duì)問題的處理提供方便。 2)編譯理論中編譯理論中(無(wú)回溯的無(wú)回溯的)自上而下自上而下分析法分析法需要需要一般的一般的-產(chǎn)生式。產(chǎn)生式。 l(g)=w|w0,1+,且且w以以0開始開始 g可以為：可以為：s0|0a a0|1|0a|1a 其中：其中： a產(chǎn)生產(chǎn)生0,1+或s？ a|0a|1a 其中：其中：a產(chǎn)生產(chǎn)生0,1* 2.4文法產(chǎn)生語(yǔ)言文法產(chǎn)生語(yǔ)言例例 文法文法 s0s s0產(chǎn)生語(yǔ)言產(chǎn)生語(yǔ)言l=0n|n0分析 如果開始使用第如果開始使用第2個(gè)產(chǎn)生式個(gè)產(chǎn)生式s0，則，則s=0，就不能再往下進(jìn)

38、行推導(dǎo)了。，就不能再往下進(jìn)行推導(dǎo)了。 產(chǎn)生產(chǎn)生基本句子基本句子0；若使用產(chǎn)生式若使用產(chǎn)生式s0s，n-1次后，則次后，則 s=0s=00s=000s=+0n-1s使用使用s0，則，則s=+0n 這對(duì)于任何這對(duì)于任何n1都是成立的；都是成立的； 總之，該文法產(chǎn)生語(yǔ)言總之，該文法產(chǎn)生語(yǔ)言l=0n|n0。定義定義2-7 遞歸文法遞歸文法 一個(gè)一個(gè)上下文無(wú)關(guān)文法上下文無(wú)關(guān)文法g，av 如果如果 a =+a ，則該文法稱為，則該文法稱為遞歸遞歸的文法；的文法；(a:遞歸遞歸非終結(jié)符非終結(jié)符) 遞歸分為遞歸分為直接直接和和間接間接遞歸。遞歸。 若若a =a 則稱為則稱為直接遞歸直接遞歸的非終結(jié)符。的非終結(jié)

39、符。 直接遞歸直接遞歸可以從可以從產(chǎn)生式產(chǎn)生式判斷。判斷。 間接遞歸間接遞歸需要根據(jù)需要根據(jù)推導(dǎo)推導(dǎo)過程才能進(jìn)行過程才能進(jìn)行判斷。判斷。思考思考 是否可以將間接遞歸是否可以將間接遞歸轉(zhuǎn)換轉(zhuǎn)換為直接為直接遞歸？遞歸？ 如何如何進(jìn)行進(jìn)行轉(zhuǎn)換？轉(zhuǎn)換？ 基本思路：基本思路： 將推導(dǎo)過程直接反映在產(chǎn)生式中將推導(dǎo)過程直接反映在產(chǎn)生式中 方法：方法： 代入法代入法 一個(gè)一個(gè)上下文無(wú)關(guān)上下文無(wú)關(guān)文法的產(chǎn)生式的文法的產(chǎn)生式的個(gè)數(shù)總是有限的。個(gè)數(shù)總是有限的。 如果該文法是如果該文法是遞歸文法遞歸文法，則該文，則該文法就能夠產(chǎn)生一個(gè)法就能夠產(chǎn)生一個(gè)無(wú)窮語(yǔ)言無(wú)窮語(yǔ)言。 若一個(gè)若一個(gè)上下文無(wú)關(guān)上下文無(wú)關(guān)文法文法不是遞歸

40、不是遞歸的文法，則的文法，則 該文法產(chǎn)生該文法產(chǎn)生有窮語(yǔ)言有窮語(yǔ)言。注意 特殊形式的產(chǎn)生式特殊形式的產(chǎn)生式 aa 是遞歸的，可以反復(fù)利用任意多次，是遞歸的，可以反復(fù)利用任意多次，但對(duì)于無(wú)窮語(yǔ)言的產(chǎn)生，沒有任何作用但對(duì)于無(wú)窮語(yǔ)言的產(chǎn)生，沒有任何作用定義定義2-8 空串產(chǎn)生式的定義空串產(chǎn)生式的定義 形如形如a的產(chǎn)生式，稱為的產(chǎn)生式，稱為上下文上下文無(wú)關(guān)無(wú)關(guān)文法的空串產(chǎn)生式，或文法的空串產(chǎn)生式，或產(chǎn)生產(chǎn)生式；式； 空串產(chǎn)生式的作用就是在推導(dǎo)的空串產(chǎn)生式的作用就是在推導(dǎo)的過程中，對(duì)于某個(gè)句型，省略掉能過程中，對(duì)于某個(gè)句型，省略掉能夠產(chǎn)生夠產(chǎn)生的非終結(jié)符號(hào)。的非終結(jié)符號(hào)。 若某個(gè)若某個(gè)上下文無(wú)關(guān)上下文無(wú)

41、關(guān)文法文法g g有有ss，則則 該該l(g)l(g)一定包含空句子一定包含空句子例文法文法 s0ss0s s s該文法產(chǎn)生語(yǔ)言該文法產(chǎn)生語(yǔ)言l=0l=0n n|n0|n0。思考：思考： 該文法是該文法是 ？型文法？型文法分析 如果開始使用第如果開始使用第2 2個(gè)產(chǎn)生式個(gè)產(chǎn)生式ss，則，則s=s=，就不能再往下進(jìn)行推導(dǎo)了，就不能再往下進(jìn)行推導(dǎo)了， 則產(chǎn)生空句子則產(chǎn)生空句子； 如果開始使用產(chǎn)生式如果開始使用產(chǎn)生式s0ss0s，n n次后，次后， s=0s=00s=000s=s=0s=00s=000s=+ +0 0n ns s 最后，使用最后，使用ss，則，則s=s=+ +0 0n n 這對(duì)于任何這

42、對(duì)于任何n1n1都是成立的；都是成立的；總之，該文法產(chǎn)生語(yǔ)言總之，該文法產(chǎn)生語(yǔ)言l=0l=0n n|n0|n0例 文法文法 sasb sab產(chǎn)生語(yǔ)言產(chǎn)生語(yǔ)言 l=anbn|n0例文法文法 sas sbs s產(chǎn)生語(yǔ)言產(chǎn)生語(yǔ)言 l=a，b*例 字母表字母表aa，bb上所有對(duì)稱的上所有對(duì)稱的非空串非空串組組成的語(yǔ)言成的語(yǔ)言( (沒有中心點(diǎn)沒有中心點(diǎn)) ) 構(gòu)造文法產(chǎn)生該語(yǔ)言構(gòu)造文法產(chǎn)生該語(yǔ)言分析 aa aa和和bbbb是最基本的句子。是最基本的句子。 如果如果s s是句子，則是句子，則asaasa和和bsbbsb是句子是句子得到文法：得到文法： saasaa sbb sbb sasa sasa sb

43、sb sbsb思考(1)(1)文法文法 sasasasa sbsb sbsb sa sa sb sb產(chǎn)生的語(yǔ)言是什么？產(chǎn)生的語(yǔ)言是什么？思考(2)(2)文法文法 sasasasa sbsb sbsb s s產(chǎn)生的語(yǔ)言是什么？產(chǎn)生的語(yǔ)言是什么？練習(xí)：構(gòu)造文法，產(chǎn)生(1)(1)字母表字母表aa，bb上所有對(duì)稱的上所有對(duì)稱的非空串非空串組成的語(yǔ)言。組成的語(yǔ)言。(2) l=wdw(2) l=wdwt t|wa,b,c|wa,b,c + + 。(3) l=a(3) l=an nb bn n|n|n=0=0。一般l對(duì) 任 意 的對(duì) 任 意 的 a a , , b b + +， 可 以 使 用， 可 以 使

44、 用aab|aabaab|aab來(lái)產(chǎn)生來(lái)產(chǎn)生 a an nb bn n|n|n00；l對(duì) 任 意 的對(duì) 任 意 的 a , ba , b + +， 可 以 使 用， 可 以 使 用aa|b|aa|baaa|b|aa|ba來(lái)產(chǎn)生來(lái)產(chǎn)生aa，bb+ +；l對(duì)任意的對(duì)任意的aa+ +，可以使用，可以使用aa|aaaa|aa來(lái)產(chǎn)生來(lái)產(chǎn)生aan n|n|n00；l對(duì)任意的對(duì)任意的a a，bb+ +，可以使用，可以使用 aaaa|babaaaa|bab來(lái)產(chǎn)生來(lái)產(chǎn)生 w wa aw wt t| |w wa,ba,b + + 注意：注意：l不能使用不能使用 aaaa2 2l代表代表 aaaaaal不能使用不能

45、使用 aaaan n(n1) (n1) 或或 aaaa + +l來(lái)代表來(lái)代表 a a可以產(chǎn)生任意多個(gè)可以產(chǎn)生任意多個(gè)a a。思考：字母表為思考：字母表為0，1語(yǔ)言的特性及產(chǎn)生語(yǔ)言的文法語(yǔ)言的特性及產(chǎn)生語(yǔ)言的文法 (1) x | x=xt , x (2) x| x=xt , x + (3) xxt | x + (4) xxt | x * (5) x0 xt | x + (6) xwxt | x, w + (7) xxtw | x, w + 構(gòu)造文法產(chǎn)生所有的產(chǎn)生所有的無(wú)符號(hào)整數(shù)無(wú)符號(hào)整數(shù)。 無(wú)符號(hào)整數(shù)是由無(wú)符號(hào)整數(shù)是由00，1,1,99中的中的1010個(gè)個(gè)數(shù)字符號(hào)組成的，但不允許以數(shù)字符號(hào)組成的

46、，但不允許以0 0開始。開始。 nam| nam|0 0 a1|2|3|4|5|6|7|8|9 a1|2|3|4|5|6|7|8|9 m|0m|1m|2m|3m|4m|5m|6m|7m|8m|9m m|0m|1m|2m|3m|4m|5m|6m|7m|8m|9m例2-11構(gòu)造文法構(gòu)造文法g g，產(chǎn)生語(yǔ)言，產(chǎn)生語(yǔ)言w|ww|w是實(shí)數(shù)是實(shí)數(shù) 略。略。例2-12 s0b|1a s0b|1a a0|0s|1aa a0|0s|1aa b1|1s|0bb b1|1s|0bb證明：證明：l(g)=|0l(g)=|0，11+ +，且，且中中有相同多的有相同多的0 0和和11。l證明提示：證明提示： 使用數(shù)學(xué)歸納

47、法（句子長(zhǎng)度）使用數(shù)學(xué)歸納法（句子長(zhǎng)度）l證明過程證明過程 略。略。根據(jù)下推自動(dòng)機(jī)根據(jù)下推自動(dòng)機(jī)00分析分析 所有產(chǎn)生式的的使用情況所有產(chǎn)生式的的使用情況: 順序和次數(shù)順序和次數(shù)思考：思考： 上下文相關(guān)上下文相關(guān)上述文法的后上述文法的后3 3個(gè)產(chǎn)生式個(gè)產(chǎn)生式 bbbbbbbb bcbc bcbc cccc cccc是否可以改為是否可以改為 bb ccbb cc上例還可以簡(jiǎn)化為：上例還可以簡(jiǎn)化為： sabc|asbsabc|asbc c cbbc cbbc bbbb bbbb 文法的產(chǎn)生式的左邊可以有多個(gè)符號(hào)文法的產(chǎn)生式的左邊可以有多個(gè)符號(hào)思考：思考：補(bǔ)充文法g使得使得l(g)= aan nb

48、bn nc cn n|n|n00 sab sabs sc c sabc sabc ba ba? 練習(xí)：練習(xí)：構(gòu)造文法g，使得 l(g)=anb2n|n=1 l(g)=am+1b2m+1|m=0 l(g)=anb2n-1|n=12.5 推導(dǎo)樹推導(dǎo)樹對(duì)于上下文無(wú)關(guān)文法，對(duì)于上下文無(wú)關(guān)文法， 利用推導(dǎo)樹也可以表示句型的產(chǎn)利用推導(dǎo)樹也可以表示句型的產(chǎn)生過程。生過程。例-16 s0b|1a a0|0s|1aa b1|1s|0bb對(duì)于串對(duì)于串0011的產(chǎn)生過程：的產(chǎn)生過程：推導(dǎo)過程推導(dǎo)過程最左推導(dǎo)：最左推導(dǎo)： s=0b=00bb=001b=0011 最右推導(dǎo)：最右推導(dǎo)： s=0b=00bb=00b1=00

49、11推導(dǎo)樹表示推導(dǎo)推導(dǎo)樹表示推導(dǎo) s s 0 b 0 b 0 b b 0 b b 1 1 1 1無(wú)用非終結(jié)符無(wú)用非終結(jié)符一個(gè)無(wú)關(guān)文法一個(gè)無(wú)關(guān)文法g,av 如果如果a不出現(xiàn)在任何形如不出現(xiàn)在任何形如 s=*uav=+uwv的推導(dǎo)之中的推導(dǎo)之中-a為為無(wú)用非終結(jié)符無(wú)用非終結(jié)符。其中：其中：u ，w ，v *。有用非終結(jié)符有用非終結(jié)符a，必須同時(shí)滿足，必須同時(shí)滿足:(1) a必須出現(xiàn)在某個(gè)句型中；必須出現(xiàn)在某個(gè)句型中；(2)從從a開始，能夠產(chǎn)生終結(jié)符號(hào)串開始，能夠產(chǎn)生終結(jié)符號(hào)串無(wú)用的產(chǎn)生式無(wú)用的產(chǎn)生式 如果一個(gè)產(chǎn)生式如果一個(gè)產(chǎn)生式( (產(chǎn)生式的左邊產(chǎn)生式的左邊或右邊或右邊) )包含有無(wú)用的非終結(jié)符，

50、包含有無(wú)用的非終結(jié)符，則該產(chǎn)生式就是則該產(chǎn)生式就是無(wú)用的產(chǎn)生式無(wú)用的產(chǎn)生式。 應(yīng)該將無(wú)用的產(chǎn)生式應(yīng)該將無(wú)用的產(chǎn)生式刪除刪除。思考思考如果文法如果文法g的開始符號(hào)的開始符號(hào)s是無(wú)用的非終是無(wú)用的非終結(jié)符號(hào)，則結(jié)符號(hào)，則l(g)=?思考判斷判斷a是有用的非終結(jié)符號(hào)的算法。是有用的非終結(jié)符號(hào)的算法。 請(qǐng)參見參考文獻(xiàn)請(qǐng)參見參考文獻(xiàn) 形式語(yǔ)言與自動(dòng)機(jī)理論形式語(yǔ)言與自動(dòng)機(jī)理論 （蔣宗禮蔣宗禮 姜守旭姜守旭 清華大學(xué)出版社）清華大學(xué)出版社）2.6 空串定理空串定理 上下文無(wú)關(guān)文法上下文無(wú)關(guān)文法g ，存在一般的空，存在一般的空串產(chǎn)生式串產(chǎn)生式a，則存在另一個(gè)上下文，則存在另一個(gè)上下文無(wú)關(guān)文法無(wú)關(guān)文法g1，使得

51、：，使得：l(g)=l(g1)；若若 l(g) ，則，則g1中沒有任何中沒有任何空串產(chǎn)空串產(chǎn)生式生式（s1就是就是s）；）； 若若l(g)，則，則g1中僅有一個(gè)空串中僅有一個(gè)空串產(chǎn)生式產(chǎn)生式s1，且，且s1不出現(xiàn)在不出現(xiàn)在g1的產(chǎn)的產(chǎn)生式的右邊。生式的右邊。證明（2） 因?yàn)橐驗(yàn)?l(g)，對(duì)于任意，對(duì)于任意cv，考慮它的任意產(chǎn)生式考慮它的任意產(chǎn)生式cw（w不為不為空串空串），），w中非終結(jié)符分為中非終結(jié)符分為a1，a2，ak，b1，b2，bj， 對(duì)于對(duì)于ai， 有有 ai 1ik 將將cw改造為改造為cw w是通過是通過0步，步，1步，步，k步步刪除刪除w中的中的ai而得到的，而得到的，w共有

52、共有2k個(gè)。個(gè)。 最后，去掉所有的空串產(chǎn)生式和最后，去掉所有的空串產(chǎn)生式和無(wú)用的產(chǎn)生式無(wú)用的產(chǎn)生式就得到就得到g1。 考慮考慮g產(chǎn)生句型產(chǎn)生句型的推導(dǎo)樹的推導(dǎo)樹t: 若若的推導(dǎo)中使用了空串產(chǎn)生式，則的推導(dǎo)中使用了空串產(chǎn)生式，則樹樹t中有以中有以為標(biāo)志的葉節(jié)點(diǎn)，為標(biāo)志的葉節(jié)點(diǎn)， 刪除刪除樹樹t中的所有產(chǎn)生中的所有產(chǎn)生的的子樹子樹，得到，得到樹樹t1，而它剛好是文法，而它剛好是文法g1產(chǎn)生串產(chǎn)生串的的推導(dǎo)樹，所以，推導(dǎo)樹，所以，l(g)=l(g1)。例文法：文法： 改造成等價(jià)的改造成等價(jià)的g：sabcd sacdcrs csb aaaa dddd sdr sd 證明（3） 假設(shè)假設(shè)l(g)，則要增

53、加新的開始，則要增加新的開始符號(hào)符號(hào)s和兩個(gè)產(chǎn)生式和兩個(gè)產(chǎn)生式 ss， s；再消除其余的空；再消除其余的空串產(chǎn)生式，即可。串產(chǎn)生式，即可。2.7 消除左遞歸消除左遞歸l在在某些情況某些情況下下,需要消除一個(gè)無(wú)關(guān)文法需要消除一個(gè)無(wú)關(guān)文法中的中的左遞歸左遞歸。l遞歸的作用是產(chǎn)生無(wú)窮的語(yǔ)言，消除遞歸的作用是產(chǎn)生無(wú)窮的語(yǔ)言，消除左遞歸，只是將左遞歸，只是將左遞歸左遞歸改造為改造為右遞歸右遞歸。l左遞歸包括左遞歸包括直接直接的和的和間接間接的左遞歸。的左遞歸。2.7.1 消除直接左遞歸消除直接左遞歸l直接左遞歸的產(chǎn)生式形式為直接左遞歸的產(chǎn)生式形式為 aav 其中：其中：av，v(uv)+。l遞歸的產(chǎn)生式

54、可以產(chǎn)生串遞歸的產(chǎn)生式可以產(chǎn)生串v的任意次的任意次連接。連接。 l假設(shè)文法假設(shè)文法g的產(chǎn)生式形式為：的產(chǎn)生式形式為： aav|wl其中其中: v,w(uv)+， 且且w不包含不包含al對(duì)于對(duì)于a，有，有 a=*wv*l增加增加b v，構(gòu)造無(wú)左遞歸文法：，構(gòu)造無(wú)左遞歸文法： awb|w bvb|v 右遞歸右遞歸則則 a=*wv*或 （編譯采用的文法） awb bvb|實(shí)際上，消除了實(shí)際上，消除了產(chǎn)生式，就得產(chǎn)生式，就得 awb|w bvb|vl一般地，產(chǎn)生式的形式為：一般地，產(chǎn)生式的形式為： aav1|av2|avn|w1|w2|wml對(duì)于對(duì)于a，有，有 a=*(w1|w2|wm)(v1|v2|

55、vn)*l增加一個(gè)新的非終結(jié)符增加一個(gè)新的非終結(jié)符b，構(gòu)造，構(gòu)造無(wú)左遞歸文法：無(wú)左遞歸文法：aw1b|w2b|wmb|w1|w2|wmbv1b|v2b|vnb|v2|v2|vnl某些文法可能沒有直接左遞歸，某些文法可能沒有直接左遞歸，但可能會(huì)有但可能會(huì)有間接左遞歸間接左遞歸。 saa asb|b2.7.2 消除間接左遞歸（消除間接左遞歸（自學(xué)自學(xué)）lg是一個(gè)上下文無(wú)關(guān)文法，首先是一個(gè)上下文無(wú)關(guān)文法，首先使用空串定理；然后將文法使用空串定理；然后將文法g中中的所有非終結(jié)符按的所有非終結(jié)符按任一順序排列任一順序排列為為a1，a2，an，根據(jù)下列，根據(jù)下列算算法法消除可能存在的間接左遞歸。消除可能存

56、在的間接左遞歸。lfor i：=1 to n do lbeginl for j：=1 to i-1 do l beginl 將將ai ajw的產(chǎn)生式的產(chǎn)生式改寫改寫為：為：l aiv1w|v2w|vkw ；l (v1，v2，vk是是aj的侯選式的侯選式)l endl 消除消除ai產(chǎn)生式的直接左遞歸；產(chǎn)生式的直接左遞歸； l endl最后，刪除最后，刪除無(wú)用無(wú)用的產(chǎn)生式，就可的產(chǎn)生式，就可以得到?jīng)]有間接左遞歸的文法。以得到?jīng)]有間接左遞歸的文法。l該算法思想是將推導(dǎo)過程中可能該算法思想是將推導(dǎo)過程中可能出現(xiàn)的左遞歸，在文法的產(chǎn)生式出現(xiàn)的左遞歸，在文法的產(chǎn)生式中就中就體現(xiàn)體現(xiàn)出來(lái)，產(chǎn)生式的改寫實(shí)出來(lái)

57、，產(chǎn)生式的改寫實(shí)際上是推導(dǎo)的體現(xiàn)際上是推導(dǎo)的體現(xiàn)-用用aj的侯選的侯選式將式將aj代替代替掉。掉。l為方便實(shí)現(xiàn)，將上述算法進(jìn)行改為方便實(shí)現(xiàn)，將上述算法進(jìn)行改寫。寫。lg是一個(gè)上下文無(wú)關(guān)文法，將是一個(gè)上下文無(wú)關(guān)文法，將文法文法g中的所有非終結(jié)符按任中的所有非終結(jié)符按任一給定的順序排列為一給定的順序排列為la1，a2，anl那么，文法的每個(gè)產(chǎn)生式是那么，文法的每個(gè)產(chǎn)生式是aiajw的形式（對(duì)于的形式（對(duì)于aiaw形形式的產(chǎn)生式，不用考慮，因?yàn)樗降漠a(chǎn)生式，不用考慮，因?yàn)樗粫?huì)導(dǎo)致左遞歸的出現(xiàn)）不會(huì)導(dǎo)致左遞歸的出現(xiàn)）.l而而i和和j的的大小關(guān)系大小關(guān)系只可能有只可能有3種情種情況：況：laiajwl

58、 ij 稱該產(chǎn)生式是稱該產(chǎn)生式是向下向下的；這類的；這類產(chǎn)生式需要產(chǎn)生式需要替代替代，用，用aj的侯選式的侯選式將將aj替掉，若出現(xiàn)了直接左遞歸，替掉，若出現(xiàn)了直接左遞歸，還需要將直接左遞歸還需要將直接左遞歸消除消除；l首先考慮非終結(jié)符首先考慮非終結(jié)符a1：la1ajwl 1j 產(chǎn)生式是向上的產(chǎn)生式是向上的l 1=j 該產(chǎn)生式是直接左遞歸的；該產(chǎn)生式是直接左遞歸的；消除直接左遞歸消除直接左遞歸l對(duì)于非終結(jié)符對(duì)于非終結(jié)符a2:la2ajw 2j 該產(chǎn)生式是向下的；這類產(chǎn)生該產(chǎn)生式是向下的；這類產(chǎn)生式需要替代，式需要替代，ll對(duì)于非終結(jié)符對(duì)于非終結(jié)符an：l anajw n=j 消除直接左遞歸；消

59、除直接左遞歸； nj 向下的；這類產(chǎn)生式需要需要替代，向下的；這類產(chǎn)生式需要需要替代，用用aj的侯選將的侯選將aj替換掉，若出現(xiàn)了直接左替換掉，若出現(xiàn)了直接左遞歸，還需要將直接左遞歸消除；遞歸，還需要將直接左遞歸消除；l最后，刪除多余的產(chǎn)生式，得到最后，刪除多余的產(chǎn)生式，得到的文法就的文法就沒有了左遞歸沒有了左遞歸，包括直，包括直接和間接的左遞歸。接和間接的左遞歸。2.8 上下文無(wú)關(guān)文法的另一種表示上下文無(wú)關(guān)文法的另一種表示l文法存在另外一種表示方法：文法存在另外一種表示方法： 使用使用表示表示* ； 使用使用表示表示的出現(xiàn)可有可無(wú)的出現(xiàn)可有可無(wú)(等等價(jià)于價(jià)于)l左遞歸的產(chǎn)生式左遞歸的產(chǎn)生式

60、aa|b|awl改寫成改寫成 a(a|b)wl右左遞歸的產(chǎn)生式右左遞歸的產(chǎn)生式 aa|b|wal改寫成：改寫成： aw(a|b)例2-18 標(biāo)識(shí)符可定義為 il iil iid la|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r| s|t|u|v|w|x|y|z d0|1|2|3|4|5|6|7|8|9改寫成ill|dla|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|zd0|1|2|3|4|5|6|7|8|92.9 語(yǔ)言之間的運(yùn)算及運(yùn)算封閉性語(yǔ)言之間的運(yùn)算及運(yùn)算封閉性 l對(duì)對(duì)簡(jiǎn)單語(yǔ)言簡(jiǎn)單語(yǔ)言進(jìn)行語(yǔ)言的進(jìn)行語(yǔ)言的運(yùn)算，運(yùn)算