形式語言與自動機-第2章-語言與文法

1、1College of Computer Science & Technology, BUPT第二章第二章 語言及文法語言及文法n主要內(nèi)容主要內(nèi)容：n定義形式語言的術(shù)語定義形式語言的術(shù)語n給出文法的定義和文法的分類給出文法的定義和文法的分類n要求掌握：要求掌握：n語言和文法的形式定義語言和文法的形式定義nCHOMSKY文法體系的分類。文法體系的分類。College of Computer Science & Technology, BUPT引言n復(fù)習(xí)：復(fù)習(xí)：n什么是形式語言？什么是文法？什么是自動機？n形式語言的定義方式？n研究形式語言與自動機的意義？n問題的提出？本章關(guān)注問題

2、的提出？本章關(guān)注 語言與文法語言與文法n如何描述（產(chǎn)生）左右括號匹配的語言？n如何描述（產(chǎn)生）算術(shù)表達式？n知識點：知識點：n形式語言所研究的問題：產(chǎn)生語言，根據(jù)語言中的基本句子和其它句子的形成“規(guī)則”，得到（產(chǎn)生）語言所包含的所有句子。3College of Computer Science & Technology, BUPT第一節(jié)第一節(jié) 語言的定義與運算語言的定義與運算一、一、語言的一些術(shù)語：語言的一些術(shù)語：n 字母表：字母表： 字符的有限集合，記為字符的有限集合，記為T。 n字符串：字符串： 由字母表由字母表T中的字符構(gòu)成的序中的字符構(gòu)成的序列稱字母表列稱字母表T上的字符串（句

3、子）。上的字符串（句子）。n 常記為常記為u,v,w,x,y,z；n 常用常用a,b,c,d 標(biāo)識單個字符。標(biāo)識單個字符。4College of Computer Science & Technology, BUPT字字 母母 表表 （Alphabet） 概念概念 形式符號的集合形式符號的集合 記號記號 常用常用 T、 表示表示 舉例舉例- 英文字母表英文字母表 a, b, , z, A, B , , Z - 英文標(biāo)點符號表英文標(biāo)點符號表 , ; : . ? ! “ ” ( ) - 漢字表漢字表 , 自自, , 動動 , , 機機, - 化學(xué)元素表化學(xué)元素表 H, He, Li, ,

4、- T = a, n, y, 任任,意意 5College of Computer Science & Technology, BUPT字字 符符 串串 （string） 概念概念 字母表字母表 T 上的一個上的一個字符串字符串（簡稱（簡稱串串），或稱為），或稱為 字字（word），），為為 T 中字符構(gòu)成的一個有限序列。中字符構(gòu)成的一個有限序列。 空串空串（empty string）, 用用 表示，不包含任何字符。表示，不包含任何字符。 舉例舉例 設(shè)設(shè) T = a, b ，則則 , a, ba, bbaba 等都是串等都是串 字符串字符串 w 的的長度長度，記為，記為 w ，是包含在

5、是包含在 w 中字符的個中字符的個數(shù)數(shù) 舉例舉例 = 0， bbaba = 5 ai 表示含有表示含有i個個a的字符串的字符串6College of Computer Science & Technology, BUPT 連接（連接（concatenation） 設(shè)設(shè) x, y為串為串, 且且 x a1a2 am, y b1b2 bn, 則則 x 與與 y 的連接的連接 x y a1a2 am b1b2 bn 連接運算的性質(zhì)連接運算的性質(zhì) - ( x y ) z x（ y z ）- x x x - x y x + y 關(guān)關(guān) 于于 字字 符符 串串 的的 運運 算算7College of

6、 Computer Science & Technology, BUPT 其它其它 如如 取頭字符取頭字符，取尾部取尾部，子串匹配子串匹配 等等n 設(shè)設(shè)1, 2, 3是字母表是字母表T上的字符串，稱上的字符串，稱1是字符是字符串串12的前綴，的前綴，2是字符串是字符串12的后綴，且的后綴，且2是字符串是字符串123的子串。的子串。 n 空串是任何字符串的前綴，后綴及子串?？沾侨魏巫址那熬Y，后綴及子串。n 例例：abc的前綴的前綴 a ab abc . 后綴后綴 c bc abc . 子串子串 a b c ab bc abc , 即一個字符串可以看作是多個字符串的連接。即一個字符串

7、可以看作是多個字符串的連接。 關(guān)關(guān) 于于 字字 符符 串串 的的 運運 算算8College of Computer Science & Technology, BUPTn 字符串字符串的逆用的逆用 或或 T表示表示, 是是字符串字符串的倒置。的倒置。= b1b2bn = bnbn-1b2b1n 空串空串的逆還是的逆還是9College of Computer Science & Technology, BUPT字字 母母 表表 的的 冪冪 運運 算算 冪運算冪運算 設(shè)設(shè) T 為字母表，為字母表，n 為任意自然數(shù)，為任意自然數(shù)， 定義（定義（1） T0 = （2）設(shè)）設(shè) x T

8、n-1，a T， 則則a x Tn （3） Tn 中的元素只能由（中的元素只能由（1）和）和（2）生成）生成 閉包閉包 T* = T0 T1 T2 閉包閉包 T+ = T1 T2 T3 T* = T+ ， T+ = T* - - 10College of Computer Science & Technology, BUPT閉包的物理意義閉包的物理意義 T的星閉包的星閉包T*：字母表T上的所有字符串和空串的集合。T的正閉包的正閉包T+：字母表T上的所有非空字符串構(gòu)成的集合T*= T+ 舉例舉例 設(shè)設(shè) T = 0，1 ，則則 T0 = ， T1 = 0，1 ， T2 = 00，01 ，1

9、0 ，11 ， T* = ，0，1，00，01 ，10 ，11， T+ = 0，1，00，01 ，10 ，11， 11College of Computer Science & Technology, BUPT語 言 （Languages） 概念概念 設(shè)設(shè) T 為字母表，則任何集合為字母表，則任何集合 L T* 是是字母字母表表T上的上的一個語言（一個語言（language） 舉例舉例 - 英文單詞集英文單詞集 , English, , words , - C 語言程序集語言程序集 字母表？字母表？- 漢語成語集漢語成語集 , 馬到成功馬到成功, - 化學(xué)分子式集化學(xué)分子式集 , H2

10、O, , NaCl , - any, 任意任意 12College of Computer Science & Technology, BUPT語 言 （Languages）舉例舉例：設(shè)：設(shè)T = a，b 則則 L1 = anbn | n1 L2 = bk | k 是質(zhì)數(shù)是質(zhì)數(shù) L3 = 只有一個空句子的語言只有一個空句子的語言 L4 = = 空語言空語言 均為字母表均為字母表T上的語言。上的語言。由語言的定義知語言是集合，對于集合的運算可應(yīng)由語言的定義知語言是集合，對于集合的運算可應(yīng)用于對于語言的計算。如并，交，補，差。用于對于語言的計算。如并，交，補，差。13College of

11、Computer Science & Technology, BUPT語言的基本運算 語言的積：語言的積：兩個語言L1 和L2的積L1 L2是由L1和L2中的字符串連接所構(gòu)成的字符串的集合。即L1中所有字符串分別與L2中的字符串連接得到的集合。設(shè)T=a, b， L1和 L2是T上的語言。 L1 =ab, ba L2 =aa, bb則 L1 L2 =abaa, abbb, baaa, babb L2 L1 =aaab, aaba, bbab, bbban L1 L2 L2 L1 語言的積不可交換。語言的積不可交換。14College of Computer Science & T

12、echnology, BUPT語言的基本運算 語言的冪：語言的冪：語言的冪可歸納定義如下語言的冪可歸納定義如下: L0 = Ln = L Ln-1 = Ln-1 L n 1上例中，上例中，L12 =abab, abba, baab, baba L22 =aaaa, aabb, bbaa, bbbb 15College of Computer Science & Technology, BUPT第二節(jié) 文法n定義：所謂文法是用來定義語言的一個數(shù)學(xué)模型：所謂文法是用來定義語言的一個數(shù)學(xué)模型n表示語言的方法：n若語言若語言L是有限集合，可用是有限集合，可用列舉法n若若L是無限集合（集合中的每

13、個元素有限長度），是無限集合（集合中的每個元素有限長度），用其他方法。用其他方法。n方法一：文法產(chǎn)生系統(tǒng)，由定義的文法規(guī)則產(chǎn)方法一：文法產(chǎn)生系統(tǒng)，由定義的文法規(guī)則產(chǎn)生出語言的每個句子生出語言的每個句子n方法二：機器識別系統(tǒng)：當(dāng)一個字符串能被一方法二：機器識別系統(tǒng)：當(dāng)一個字符串能被一個語言的識別系統(tǒng)接受，則這個字符串是該語個語言的識別系統(tǒng)接受，則這個字符串是該語言的一個句子，否則不屬于該語言。言的一個句子，否則不屬于該語言。16College of Computer Science & Technology, BUPT元語言元語言n定義定義：描述語言的語言描述語言的語言例如：各種各樣的程

14、序設(shè)計語言例如：各種各樣的程序設(shè)計語言n當(dāng)人們要解釋或討論程序設(shè)計語言本身時，又需要當(dāng)人們要解釋或討論程序設(shè)計語言本身時，又需要一種語言，被討論的語言叫做對象語言，即某種程一種語言，被討論的語言叫做對象語言，即某種程序設(shè)計語言，討論對象語言的語言稱為元語言序設(shè)計語言，討論對象語言的語言稱為元語言。17College of Computer Science & Technology, BUPTBNF（巴科斯范式）巴科斯范式） BNF范式通常被作為討論某種程序設(shè)計語言語法的元語言n := 0|1|2|9 := “定義為”n := A|B|C|Z|a|b|z : = | | . n通過上述定

15、義可知，所有以字母開頭的，由字母和數(shù)字組成的字符串都是標(biāo)識符。nBNF定義了一種語言，其中標(biāo)識符如上定義。nBNF描述它所定義的語言，為元語言。18College of Computer Science & Technology, BUPTn例如：漢語語法中定義了句子的結(jié)構(gòu)由主語、謂語、賓語組成。這里主謂賓只是描述了句子的結(jié)構(gòu)，并不是句子。而按照這種結(jié)構(gòu)組成的建立在漢字上的字符串就是句子。如他是學(xué)生。n文法是一種元語言，一種方法，根據(jù)文法產(chǎn)文法是一種元語言，一種方法，根據(jù)文法產(chǎn)生出語言的句子。生出語言的句子。19例例1類類PASCAL語句語句定義定義20College of Compu

16、ter Science & Technology, BUPT三、Chomsky文法體系n例如：BNF := := := :=a|b|z|A|B|Z :=0|1|9將:= 改為表示可被代替用I, L, D分別表示標(biāo)識符、字母、數(shù)字;21College of Computer Science & Technology, BUPT則上述表達式可以表示為則上述表達式可以表示為 IL IIL IID La|b|.|z D0|1|.9這就是一個文法的生成式集合。這就是一個文法的生成式集合。22College of Computer Science & Technology, BUP

17、TnChomsky文法體系中，任何一種文法必須包含有兩個不同的有限符號的集合，即非終結(jié)符集合N和終結(jié)符集合T。一個形式規(guī)則的有限集合P（生成式集合），一個起始符S。nP中的生成式是用來產(chǎn)生語言句子的規(guī)則，而句子則是僅由終結(jié)符組成的字符串。這些字符串必須從一個起始符S開始，不斷使用P中的生成式而導(dǎo)出來。n可見文法的核心是生成式的集合，它決定了語言中句子的產(chǎn)生。23College of Computer Science & Technology, BUPT文法的形式定義n文法G是一個四元組G=(N，T，P，S)， 其中N 非終結(jié)符的有限集合T 終結(jié)符的有限集合 NT=P 形式為的生成式的有

18、限集合。 且(NT)* N+ (NT)* (NT)*S 起始符 且S N。24College of Computer Science & Technology, BUPTn將上例用文法表示G=(N，T，P，S)N = I, L, DT = a, b, c,z, 0, 1, 9P = I, La, , D0, , D9S = I n文法是語言的產(chǎn)生系統(tǒng)，研究怎樣構(gòu)造文法能產(chǎn)生出符合要求的句子。25College of Computer Science & Technology, BUPT四推導(dǎo)與句型1、直接推導(dǎo)設(shè)G =（N,T,P,S）是文法，若A是P中的生成式，和是（NT）*中

19、的字符串，則有A = 稱A直接推導(dǎo)出，或說是A的直接推導(dǎo)。26College of Computer Science & Technology, BUPTn設(shè)G = (N,T,P,S)是文法，、0、1n、都是（NT）*中的字符串，且=0、 =n，其中i直接推導(dǎo)出i+1 （0in）,則稱序列0=1=2=n是長度為n的推導(dǎo)序列，而=0是長度為0的推導(dǎo)序列。n對推導(dǎo)出記為 ，若推導(dǎo)序列長度大于0，則記為 。n推導(dǎo)序列的每一步，都產(chǎn)生一個字符串，這些字符串一般稱為句型。2、推導(dǎo)序列*G G 27College of Computer Science & Technology, BUPT

20、3、句型和句子n句型字符串字符串是文法是文法G的句型，當(dāng)且僅當(dāng)?shù)木湫停?dāng)且僅當(dāng)S ，且且（NT）* 。n 句子是是G的句子，當(dāng)且僅當(dāng)?shù)木渥?，?dāng)且僅當(dāng)S , 且且T*。（。（是是由終結(jié)符組成的字符串）由終結(jié)符組成的字符串）例：例：I =L =a I =IL =LL =zL =zbn句型包含句子*G *G 28College of Computer Science & Technology, BUPT4文法產(chǎn)生的語言由文法由文法G產(chǎn)生的語言記為產(chǎn)生的語言記為L(G)。 L(G) = |T*且且S 或：或：L(G)中的一個字符串，必是由終結(jié)符組成中的一個字符串，必是由終結(jié)符組成的，并且是從起

21、始符的，并且是從起始符S推導(dǎo)出來的。推導(dǎo)出來的。*G College of Computer Science & Technology, BUPT例：文法產(chǎn)生語言例例1：括號匹配的語言及產(chǎn)生：括號匹配的語言及產(chǎn)生遞歸定義遞歸定義提供了集合的定義方式。構(gòu)造規(guī)律。n基礎(chǔ)：定義該集合的最基本的元素，“（）”n遞歸：若S是合法串，則：（S）是合法串； SS 是合法串；文法產(chǎn)生式集合：S（）S（S）S SSCollege of Computer Science & Technology, BUPT例 文法產(chǎn)生語言例例2：程序設(shè)計語言中算術(shù)表達式的文法：程序設(shè)計語言中算術(shù)表達式的文法運算符

22、運算符A ：+、- -、* *、/ /利用利用遞歸定義遞歸定義方式。重點是構(gòu)造規(guī)律。n基礎(chǔ)：單個變量是最基本的串，i,n遞歸：若S是合法串，則：SAS 是合法串； （ S）是合法串產(chǎn)生式集合：Si ; SSAS; S(S);A+; A; A*; A/; 31College of Computer Science & Technology, BUPT第三節(jié) Chomsky文法體系分類n文法文法 G = (N,T,P,S)； P: 其中其中 (NT)* N+ (NT)* (NT)* 屬于屬于Chomsky文法體系文法體系n該體系對該體系對生成式（產(chǎn)生式）生成式（產(chǎn)生式）的形式做了一的形式做

23、了一些規(guī)定，分為四類，即些規(guī)定，分為四類，即0型、型、1型、型、2型、型、3型文法型文法n0型文法：無限制文法型文法：無限制文法對應(yīng)的語言：遞歸可枚舉語言，與圖靈機等價。32College of Computer Science & Technology, BUPT1型文法n也稱上下文有關(guān)文法（也稱上下文有關(guān)文法（CSG：Context-sensitive Grammar)生成式的形式為生成式的形式為，其中其中 | | ，(NT)+， (NT)* N+ (NT)*n對應(yīng)的語言：上下文有關(guān)語言（對應(yīng)的語言：上下文有關(guān)語言（CSL：Context-sensitive Language)n若

24、不考慮若不考慮，與線性有界自動機（與線性有界自動機（LBA, Linear Bounded Automaton）等價。等價。College of Computer Science & Technology, BUPT1型文法語言限定約束：n左部的長度小于右部左部的長度小于右部n不含不含A-A-n實際程序語言中上下文有關(guān)的部分：n過程調(diào)用時形參與實參的一致性檢查等。過程調(diào)用時形參與實參的一致性檢查等。34College of Computer Science & Technology, BUPT2型文法n也稱上下文無關(guān)文法（也稱上下文無關(guān)文法（CFG：Context-free G

25、rammar) A , AN, 且且 (NT)*n對應(yīng)的語言：上下文無關(guān)語言對應(yīng)的語言：上下文無關(guān)語言 （CFL： Context-free Language)。n對 應(yīng) 的 自 動 機 ： 下 推 自 動 機 （對 應(yīng) 的 自 動 機 ： 下 推 自 動 機 （ P D A ： Pushdown Automaton)。College of Computer Science & Technology, BUPTn語言限定約束：語言限定約束： 左部是單個非終結(jié)符。nCFL對實際語言結(jié)構(gòu)的抽象：對實際語言結(jié)構(gòu)的抽象：n表示句子的語法結(jié)構(gòu)，如：表達式，嵌套結(jié)構(gòu)。n目前的程序設(shè)計語言主要采用C

26、FL描述語法結(jié)構(gòu)。36College of Computer Science & Technology, BUPT3型文法也稱正則文法也稱正則文法n右線性文法（右線性文法（Right-linear Grammar） AB 或或 A A、BN, T*。n左線性文法（左線性文法（Left-linear Grammar）：）：AB 或或 AA、BN, T*。n對應(yīng)的語言：正則語言對應(yīng)的語言：正則語言n對應(yīng)的自動機：有限自動機對應(yīng)的自動機：有限自動機(Finite Automaton)。37College of Computer Science & Technology, BUPT例例1：G = (A,B,C, a,b,d, P, A) P: AAB；ABCAAB；Ad；Ba；Cb 是是1型文法。型文法。 A=dA=AB =dB =daA=AB =ABB =dBB =daB =daaA=AB =CAAB =bAAB =bdAB =bdCAAB =bdbAAB =bdbdAB=bdbddB =bdbdda38College of Computer Science &