compiler_ch21

1、Ch2 形式語(yǔ)言自動(dòng)機(jī)理論基礎(chǔ)2.1 文法和語(yǔ)言2.1.1 語(yǔ)言的語(yǔ)法和語(yǔ)義本節(jié)展開(kāi)思路從文法和語(yǔ)言的直觀概念文法、語(yǔ)言的運(yùn)算和形式定義表示方法類型二義性問(wèn)題關(guān)于語(yǔ)言：自然語(yǔ)言 人與人交互的工具；程序設(shè)計(jì)語(yǔ)言 人機(jī)交互的工具。語(yǔ)言要素語(yǔ)法 （語(yǔ)言的描述規(guī)則）語(yǔ)義 （語(yǔ)言的含義）語(yǔ)法是一種媒介，語(yǔ)義以語(yǔ)法為媒介來(lái)予以說(shuō)明。語(yǔ)言是由單詞按一定規(guī)則（文法）組成句子來(lái)表達(dá)特定意思。故對(duì)語(yǔ)言的分析集中于對(duì)句子的分析。而句子的分析依據(jù)語(yǔ)言的文法規(guī)則。Ch2 形式語(yǔ)言自動(dòng)機(jī)理論基礎(chǔ)2.1 文法和語(yǔ)言2.1.1 語(yǔ)言的語(yǔ)法和語(yǔ)義動(dòng)詞 吃例2.1 : 設(shè)有語(yǔ)句 “小八哥吃大花生”。設(shè)有漢語(yǔ)語(yǔ)法規(guī)則的一個(gè)子集：句

2、子主語(yǔ)謂語(yǔ)主語(yǔ)形容詞名詞謂語(yǔ)動(dòng)詞賓語(yǔ)賓語(yǔ)形容詞名詞形容詞 小 | 大名詞 八哥 | 花生Ch2 形式語(yǔ)言自動(dòng)機(jī)理論基礎(chǔ)2.1 文法和語(yǔ)言2.1.1 語(yǔ)言的語(yǔ)法和語(yǔ)義8巴科斯諾爾（BackusNaur Form）范式表示法，簡(jiǎn)稱BNF。 ：表示語(yǔ)法成分。|：（通常也用 := ）表示“定義為”或“由組合成”的含義。：“或”的含義。表示具有相同左部的產(chǎn)生規(guī)則可用“|”分開(kāi)。元語(yǔ)言符號(hào)元語(yǔ)言: 描述另一個(gè)語(yǔ)言的語(yǔ)言。Ch2 形式語(yǔ)言自動(dòng)機(jī)理論基礎(chǔ)2.1 文法和語(yǔ)言2.1.1 語(yǔ)言的語(yǔ)法和語(yǔ)義語(yǔ)句“小八哥吃大花生”分析的語(yǔ)法樹(shù)上下句子主語(yǔ)謂語(yǔ)形容詞名詞 動(dòng)詞 賓語(yǔ)小八哥吃形容詞名詞大花生Ch2 形式語(yǔ)言

3、自動(dòng)機(jī)理論基礎(chǔ)2.1 文法和語(yǔ)言2.1.1 語(yǔ)言的語(yǔ)法和語(yǔ)義Ch2 形式語(yǔ)言自動(dòng)機(jī)理論基礎(chǔ)2.1 文法和語(yǔ)言2.1.1 語(yǔ)言的語(yǔ)法和語(yǔ)義句子的推導(dǎo) 小八哥吃 小八哥吃 小八哥吃大小八哥吃大花生句子句子的歸約謂語(yǔ)主語(yǔ)形容詞 名詞 動(dòng)詞賓語(yǔ)小八哥吃花生大下形容詞 名詞上Ch2 形式語(yǔ)言自動(dòng)機(jī)理論基礎(chǔ)2.1 文法和語(yǔ)言2.1.1 語(yǔ)言的語(yǔ)法和語(yǔ)義Ch2 形式語(yǔ)言自動(dòng)機(jī)理論基礎(chǔ)2.1 文法和語(yǔ)言2.1.2 文法和 語(yǔ)言的定義2.1.2 文法和語(yǔ)言的定義一.二.三.四.字符和字符串文法形式定義字符串運(yùn)算語(yǔ) 言Ch2 形式語(yǔ)言自動(dòng)機(jī)理論基礎(chǔ)2.1 文法和語(yǔ)言2.1.2 文法和 語(yǔ)言的定義一. 字符、字符串

4、任何一種語(yǔ)言，都是由該語(yǔ)言的基本字符所組成的字符串的集合。例如，程序設(shè)計(jì)語(yǔ)言的基本字符集是由字母、數(shù)字、運(yùn)算符等其它符號(hào)組成，則任何程序都是由這些基本字符組成的序列。定義2.1 ( 字母表 )字母表是元素的非空有窮集合。字母表中的元素稱為符號(hào)，因此字母表也稱為符號(hào)集。Ch2 形式語(yǔ)言自動(dòng)機(jī)理論基礎(chǔ)2.1 文法和語(yǔ)言2.1.2 文法和 語(yǔ)言的定義例如:漢語(yǔ)的字母表中包括漢字、數(shù)字和標(biāo)點(diǎn)符號(hào)等。二進(jìn)制數(shù)語(yǔ)言的字母表是0,1。C語(yǔ)言的字母表可以認(rèn)為是一切可打印字符組成的集合。用希臘字母或大寫(xiě)英文字母等表示字母表，用集合元素表示形式枚舉字母表中的符號(hào)。例如，字母表 A=a,b,c,d與字母表 =0,1

5、等。定義2.2 (符號(hào)串)由字母表中的符號(hào)組成的任何有窮序列稱為符號(hào)串。例如:1) 001110是字母表= 0,1上的符號(hào)串；2) 字母表A= a,b,c上的一些符號(hào)串有：a, b, c, ab, ba, aaca等。通常使用小寫(xiě)字母表示符號(hào)串，如x =STR表示x是由符號(hào)S、T和R，并按此順序組成的符號(hào)串。Ch2 形式語(yǔ)言自動(dòng)機(jī)理論基礎(chǔ)2.1 文法和語(yǔ)言2.1.2 文法和 語(yǔ)言的定義字 句子 串Ch2 形式語(yǔ)言自動(dòng)機(jī)理論基礎(chǔ)2.1 文法和語(yǔ)言2.1.2 文法和 語(yǔ)言的定義從離散數(shù)學(xué)的角度定義符號(hào)串，則有：（1） 字母表上的字符是上的符號(hào)串；（2） 若x是上的符號(hào)串，且a,則xa或ax是上的符

6、號(hào)串；（3） y是上的符號(hào)串，當(dāng)且僅當(dāng)y可由(1)和(2)產(chǎn)生。符號(hào)串長(zhǎng)度如果某符號(hào)串x中有m個(gè)符號(hào)，則稱其長(zhǎng)度為m，記為 | x | = m。允許不包含任何符號(hào)的符號(hào)串，稱其為空符號(hào)串或空串。空串用表示，其長(zhǎng)度為0，記為 | | = 0。Ch2 形式語(yǔ)言自動(dòng)機(jī)理論基礎(chǔ)2.1 文法和語(yǔ)言2.1.2 文法和 語(yǔ)言的定義例如:1） 定義在字母表=0，1上的符號(hào)串| 001110 | = 62） 定義在字母表= x，y，z，=，0， ，1，+，; 上的符號(hào)串| x=y+; z=0; | = 11符號(hào)串的前綴、后綴和子符號(hào)串設(shè)x是一個(gè)符號(hào)串，把從x的尾部刪去0個(gè)或若干個(gè)符號(hào)之后剩余的部分稱為x的前綴。

7、從x的首部刪去0個(gè)或若干個(gè)符號(hào)之后剩余的部分稱為x的后綴。若x的前綴(后綴)不是x自身，則將其稱為x的真前綴(真后綴)。Ch2 形式語(yǔ)言自動(dòng)機(jī)理論基礎(chǔ)2.1 文法和語(yǔ)言2.1.2 文法和 語(yǔ)言的定義Ch2 形式語(yǔ)言自動(dòng)機(jī)理論基礎(chǔ)2.1 文法和語(yǔ)言2.1.2 文法和 語(yǔ)言的定義例如: 設(shè)x = abc則,a,ab,abc都是x的前綴，且除abc外都為真前綴。,c,bc,abc都是x的后綴，且除abc外都為真后綴。abc是x的前綴或后綴，但既不是真前綴也不是真后綴。Ch2 形式語(yǔ)言自動(dòng)機(jī)理論基礎(chǔ)2.1 文法和語(yǔ)言2.1.2 文法和 語(yǔ)言的定義子符號(hào)串（子串）從一個(gè)符號(hào)串中刪去它的一個(gè)前綴或(和)一

8、個(gè)后綴之后剩余的部分稱為該符號(hào)串的子符號(hào)串或子串。例如:x = abcd則,a,b,c,ab,bc,cd,abc,bcd及abcd都是x的子字符串。而ac，ad，cb，bd，ba等都不是x的子字符串。Ch2 形式語(yǔ)言自動(dòng)機(jī)理論基礎(chǔ)2.1 文法和語(yǔ)言2.1.2 文法和 語(yǔ)言的定義2.1.2 文法和語(yǔ)言的定義一.二.三.四.字符和字符串文法形式定義字符串運(yùn)算語(yǔ) 言Ch2 形式語(yǔ)言自動(dòng)機(jī)理論基礎(chǔ)2.1 文法和語(yǔ)言2.1.2 文法和 語(yǔ)言的定義二. 文法定義2.3:一部文法G是一個(gè)四元組G =（ VN, VT, S, P）其中：VN：非空有限的非終結(jié)符號(hào)集(一般用大寫(xiě)字母表示)。VT：非空有限的終結(jié)符

9、號(hào)集（一般用小寫(xiě)字母表示）。設(shè)V是文法G的符號(hào)集，則有V= VT VN ，VT VN= 。S：文法的開(kāi)始符號(hào)或識(shí)別符號(hào)，亦稱公理，S VN。S代表語(yǔ)言最終要得到的語(yǔ)法范疇。Ch2 形式語(yǔ)言自動(dòng)機(jī)理論基礎(chǔ)2.1 文法和語(yǔ)言2.1.2 文法和語(yǔ)言的定義設(shè)有漢語(yǔ)語(yǔ)法規(guī)則的一個(gè)子集：句子主語(yǔ)謂語(yǔ)主語(yǔ)形容詞名詞謂語(yǔ)動(dòng)詞賓語(yǔ)賓語(yǔ)形容詞名詞形容詞 小 | 大名詞 八哥 | 花生動(dòng)詞 吃VNVTSCh2 形式語(yǔ)言自動(dòng)機(jī)理論基礎(chǔ)2.1 文法和語(yǔ)言2.1.2 文法和語(yǔ)言的定義P：有限產(chǎn)生式集。產(chǎn)生式就是按一定格式書(shū)寫(xiě)的定義語(yǔ)法范疇的文法規(guī)則，它是一部文法的實(shí)體。產(chǎn)生式的形式:P或P:=其中: P稱為產(chǎn)生式的左部，

10、為產(chǎn)生式的右部或稱為P的侯選式，有PV+，V*。注意，公理S至少且必須在文法某個(gè)產(chǎn)生式的左部出現(xiàn)一次。Ch2 形式語(yǔ)言自動(dòng)機(jī)理論基礎(chǔ)2.1 文法和語(yǔ)言2.1.2 文法和語(yǔ)言的定義例2.2 : 數(shù)字文法定義為 0 | 1 | 2 | 3 | | 9其中: VN = NUMBER ，VT =0,1,2, ,9，S= VN，P為定義式本身。例如，簡(jiǎn)單的算術(shù)表達(dá)式文法G1定義為 E，i, +, *, (, )，E，E i | i+i | i *i | (E) 四元式形式Ch2 形式語(yǔ)言自動(dòng)機(jī)理論基礎(chǔ)2.1 文法和語(yǔ)言2.1.2 文法和語(yǔ)言的定義注意:E iE i+iE i *iE (E)E i | i

11、+i | i *i | (E)簡(jiǎn)寫(xiě)Ch2 形式語(yǔ)言自動(dòng)機(jī)理論基礎(chǔ)2.1 文法和語(yǔ)言2.1.2 文法和語(yǔ)言的定義三. 符號(hào)串運(yùn)算定義2.4 ( 符號(hào)串的連接 )設(shè)x和y是兩個(gè)符號(hào)串，如果將符號(hào)串y直接拼接在符號(hào)串x之后，則稱此操作為符號(hào)串x和y的連接，記作xy。例如， 設(shè)有字符串 j=abc，k=xyz則jk=abcxyz，kj=xyzabc。連接運(yùn)算是有序的。一般來(lái)說(shuō)xyyx，僅當(dāng)為空串，則有x=x=x。Ch2 形式語(yǔ)言自動(dòng)機(jī)理論基礎(chǔ)2.1 文法和語(yǔ)言2.1.2 文法和語(yǔ)言的定義2.1.2 文法和語(yǔ)言的定義一.二.三.四.字符和字符串文法形式定義字符串運(yùn)算語(yǔ) 言Ch2 形式語(yǔ)言自動(dòng)機(jī)理論基礎(chǔ)2

12、.1 文法和語(yǔ)言2.1.2 文法和語(yǔ)言的定義注意定義2.5 ( 符號(hào)串的方冪 )設(shè)x是某字母表上符號(hào)串，把x自身連接 n 次得到符號(hào)串z，即 z = xxx (n個(gè)x) ，稱z是符號(hào)串 x的n次冪，記作z=xn。設(shè)x是符號(hào)串，則有定義x0=x1=xx2=xxx3= x2x= xx2=xxxxn= xn-1x= xxn-1=xx xn個(gè)Ch2 形式語(yǔ)言自動(dòng)機(jī)理論基礎(chǔ)2.1 文法和語(yǔ)言2.1.2 文法和語(yǔ)言的定義例如， 設(shè)x=abc則 x2=abcabcx3=abcabcabc定義2.6 ( 符號(hào)串集合的乘積 )設(shè)A、B 是兩個(gè)符號(hào)串集合，AB表示A與B的乘積，則有定義AB=xy | (xA)(y

13、B) Ch2 形式語(yǔ)言自動(dòng)機(jī)理論基礎(chǔ)2.1 文法和語(yǔ)言2.1.2 文法和語(yǔ)言的定義例如，設(shè)A=ab,c, B=d,ef,則AB=abd, abef, cd, cef注意：有 A= A=A, A= A = ，其中 為空集。注意： = 。Ch2 形式語(yǔ)言自動(dòng)機(jī)理論基礎(chǔ)2.1 文法和語(yǔ)言2.1.2 文法和語(yǔ)言的定義定義2.7 ( 符號(hào)串集合的方冪 )設(shè)A是符號(hào)串集合，A自身的乘積可以用方冪表示。則有定義設(shè)P為字符串集：A0= A1=AA2=AAA3= A2A =AAAAn= An-1A =AAACh2 形式語(yǔ)言自動(dòng)機(jī)理論基礎(chǔ)2.1 文法和語(yǔ)言2.1.2 文法和語(yǔ)言的定義顯然有：Ai+j = Ai A

14、j例如， P= ab, x, aby ，則P2 = PP=abab, abx,ababy, xab, xx, xaby,abyab, abyx, abyabyCh2 形式語(yǔ)言自動(dòng)機(jī)理論基礎(chǔ)2.1 文法和語(yǔ)言2.1.2 文法和語(yǔ)言的定義定義2.8 ( 符號(hào)串集合的并 )設(shè)P、Q為字符串集，集合P Q為P和Q 的并，它的元素是P或Q中的元素。例如，P=0, 1, 01Q=0, 10, 11, 00 ,則 P Q = 0, 1, 01, 10, 11, 00Ch2 形式語(yǔ)言自動(dòng)機(jī)理論基礎(chǔ)2.1 文法和語(yǔ)言2.1.2 文法和語(yǔ)言的定義定義2.9 ( 符號(hào)串集合的閉包 )設(shè)A為符號(hào)串集，A的正閉包記作A

15、+，則有A+= A1 A2 AnA的自反閉包記作A*，則有A*= A0 A+= A+= A+由定義知，A+= A A*A * = A0 A +Ch2 形式語(yǔ)言自動(dòng)機(jī)理論基礎(chǔ)2.1 文法和語(yǔ)言2.1.2 文法和語(yǔ)言的定義例如， 設(shè)有 A=01,10則A* = ，01，10，0110，1001，010101，100110，A+ = 01，10，0110，1001，010101，100110，Ch2 形式語(yǔ)言自動(dòng)機(jī)理論基礎(chǔ)2.1 文法和語(yǔ)言2.1.2 文法和語(yǔ)言的定義串集合運(yùn)算應(yīng)用：設(shè)有 L=A.Z, a.z D= 0,1,2, ,9 1) L D= 由字母和數(shù)字構(gòu)成的集合 2) LD= 所有一個(gè)字

16、母后跟隨一個(gè)數(shù)字組成的字符串的集合 3)L*= 由所有字母按任意順序組成的字符串（含 ）所構(gòu)成的集合 4) L( LD )*= 由所有一個(gè)字母開(kāi)頭后跟隨字母或數(shù)字組成的字符串或的集合 Ch2 形式語(yǔ)言自動(dòng)機(jī)理論基礎(chǔ)2.1 文法和語(yǔ)言2.1.2 文法和語(yǔ)言的定義2.1.2 文法和語(yǔ)言的定義一.二.三.四.字符和字符串文法形式定義字符串運(yùn)算語(yǔ) 言Ch2 形式語(yǔ)言自動(dòng)機(jī)理論基礎(chǔ)2.1 文法和語(yǔ)言2.1.2 文法和語(yǔ)言的定義四. 語(yǔ)言1. 語(yǔ)言的非形式化定義給定一部文法G, 從G的開(kāi)始符號(hào)S出發(fā)，反復(fù)使用產(chǎn)生式對(duì)非終結(jié)符進(jìn)行替換，最后所得到的終結(jié)符號(hào)串的全體，即為文法G所描述的語(yǔ)言L（G）。例2.3

17、: 設(shè)有文法GS P | aPbP ba | bQaQ ab則： L(G)=ba, abab, baba, abababCh2 形式語(yǔ)言自動(dòng)機(jī)理論基礎(chǔ)2.1 文法和語(yǔ)言2.1.2 文法和語(yǔ)言的定義S P baS aPb ababS P bQa babaS aPb abQab abababCh2 形式語(yǔ)言自動(dòng)機(jī)理論基礎(chǔ)2.1 文法和語(yǔ)言2.1.2 文法和語(yǔ)言的定義定義2.10 ( 直接推導(dǎo) “ = ” )有V=A=W(,(VNVT)*),當(dāng)且僅當(dāng)P中存在一條規(guī)則A，稱V直接推導(dǎo)出W （或W直接歸約到V），記作：V = W。定義2.11 ( 直接推導(dǎo)序列 )如果存在V= 0= 1, 1= 2, n

18、-1= n= W或 1= 2= 3= = n-1= n，+則V經(jīng)過(guò)n步(n0)可以推導(dǎo)出 W，記作: V = W 。當(dāng)+ *V = W或V = W，記作：V = W。Ch2 形式語(yǔ)言自動(dòng)機(jī)理論基礎(chǔ)2.1 文法和語(yǔ)言2.1.2 文法和 語(yǔ)言的定義定義2.12 (最左(右)推導(dǎo))在推導(dǎo)過(guò)程中，總是對(duì)句型中的最左(右)邊的非終結(jié)符進(jìn)行替換，稱為最左(右)推導(dǎo)。定義2.13 ( 句型 )*為GS的句型 。定義2.14 ( 句子 )*GS的句子。Ch2 形式語(yǔ)言自動(dòng)機(jī)理論基礎(chǔ)2.1 文法和語(yǔ)言2.1.2 文法和 語(yǔ)言的定義定義2.15 (規(guī)范推導(dǎo)/規(guī)范句型/ 規(guī)范歸約)最右推導(dǎo)也稱為規(guī)范推導(dǎo) 。僅用規(guī)范

19、推導(dǎo)得到的句型稱為規(guī)范句型 。規(guī)范推導(dǎo)的逆序?yàn)橐?guī)范歸約。注意：對(duì)給定的一個(gè)句子或句型其最左和最右推導(dǎo)的惟一性。Ch2 形式語(yǔ)言自動(dòng)機(jī)理論基礎(chǔ)2.1 文法和語(yǔ)言2.1.2 文法和 語(yǔ)言的定義例2.4: 設(shè)有文法GE：E E *E | E+E | (E) | i設(shè)有句子$1: i*i+i= =L L L LE = E *E = E *E+E = E *E+i = E *i+i = i*i+iR R R R R最左推導(dǎo)最右推導(dǎo)/規(guī)范推導(dǎo)規(guī)范句型句子句型Ch2 形式語(yǔ)言自動(dòng)機(jī)理論基礎(chǔ)2.1 文法和語(yǔ)言2.1.2 文法和 語(yǔ)言的定義定義2.16 ( 文法的遞歸 )設(shè)有文法G，A 是G的產(chǎn)生式，若具有A+

20、若= ，則G為左遞歸文法。若= ，則G為右遞歸文法。直接遞歸遞歸文法間接遞歸左（右）遞歸Ch2 形式語(yǔ)言自動(dòng)機(jī)理論基礎(chǔ)2.1 文法和語(yǔ)言2.1.2 文法和 語(yǔ)言的定義例2.5： 設(shè)有文法G1： E E+E | E*E | (E) | i有E = E 則文法G1是直接遞歸文法。例2.6： 設(shè)有文法G2：T Qc | cQ Rb | bR Ta | a+有T=Qc =Rbc =Tabc，即 T= Tabc，則文法G2是間接遞歸文法。L(G) = | VTS = ，S是文法Ch2 形式語(yǔ)言自動(dòng)機(jī)理論基礎(chǔ)2.1 文法和語(yǔ)言2.1.2 文法和 語(yǔ)言的定義2. 語(yǔ)言的形式定義定義2.17 ( 語(yǔ)言 )文法

21、 G所產(chǎn)生的語(yǔ)言L(G)：*+的開(kāi)始符號(hào) 例2.7: 設(shè)有語(yǔ)言 L(G1)= abna | n=0 , 求G1？G1 ： S aa | aRaR b | RbCh2 形式語(yǔ)言自動(dòng)機(jī)理論基礎(chǔ)2.1 文法和語(yǔ)言2.1.2 文法和 語(yǔ)言的定義S S0 | 0求L (G) ？L (G) = 0n | n=1 例2.8: 設(shè)有文法 G：S 0S1 | 01求L(G)？L（G）= 0n1n | n=1 例2.9: 設(shè)有文法 G：G:S 0S | 0L(G) = L(G)Ch2 形式語(yǔ)言自動(dòng)機(jī)理論基礎(chǔ)2.1 文法和語(yǔ)言2.1.2 文法和 語(yǔ)言的定義定義2.18 ( 文法等價(jià) )若 L(G1)= L(G2)，

22、則稱文法G1和G2是等價(jià)的 。例2.11:設(shè)有語(yǔ)言L(G) :L(G)= a(bn)a | n=0 = a()a, a(b)a, a(bb)a, G: S a(B)aG: S a()a | a(B)aB Bb | b | B Bb | bCh2 形式語(yǔ)言自動(dòng)機(jī)理論基礎(chǔ)2.1 文法和語(yǔ)言2.1.3 文法的表示1. BNF表示法元語(yǔ)言符號(hào)集： , , | 2. 擴(kuò)充BNF表示法 （EBNF）1) 引入花括號(hào) t 表示字符串t 的多次獲任意次出現(xiàn)，其中下角標(biāo)n 表示串t重復(fù)的最小次數(shù)，上角標(biāo)m表示字符串 t 重復(fù)的最大次數(shù)。mnCh2 形式語(yǔ)言自動(dòng)機(jī)理論基礎(chǔ)2.1 文法和語(yǔ)言2.1.3 文法的表示例

23、2.12: FORTRAN語(yǔ)言中標(biāo)識(shí)符的定義。假設(shè)標(biāo)識(shí)符是長(zhǎng)度8的字母開(kāi)頭后跟字母或數(shù)字的字符串，則有： | 70Ch2 形式語(yǔ)言自動(dòng)機(jī)理論基礎(chǔ)2.1 文法和語(yǔ)言2.1.3 文法的表示2) 引入圓括號(hào) “(” “)”提取產(chǎn)生式中的公共因子，簡(jiǎn)化產(chǎn)生式的表示。例2.13: 有文法規(guī)則U xa | xb | | xz引入圓括號(hào)提取公共字符串x后有：U x（a | b | | z）Ch2 形式語(yǔ)言自動(dòng)機(jī)理論基礎(chǔ)2.1 文法和語(yǔ)言2.1.3 文法的表示3) 引入方括號(hào) t 表示字符串 t 可有可無(wú)。例2.14:設(shè)有條件語(yǔ)句的文法 |else IF THEN引入方括號(hào)后，可簡(jiǎn)化為： else IF TH

24、ENCh2 形式語(yǔ)言自動(dòng)機(jī)理論基礎(chǔ)2.1 文法和語(yǔ)言2.1.3 文法的表示3. 語(yǔ)法圖例2.15: PASCAL語(yǔ)言中標(biāo)識(shí)符的定義如下圖。Ch2 形式語(yǔ)言自動(dòng)機(jī)理論基礎(chǔ)2.1 文法和語(yǔ)言2.1.4 語(yǔ)法樹(shù)與二義性一 . 語(yǔ)法樹(shù)與二義性語(yǔ)法樹(shù)是句子結(jié)構(gòu)的圖形表示，它代表了句子的推導(dǎo)結(jié)果，有利于理解句子語(yǔ)法結(jié)構(gòu)的層次。表示：語(yǔ)法樹(shù)的根結(jié)點(diǎn)語(yǔ)法樹(shù)的中間結(jié)點(diǎn)語(yǔ)法樹(shù)的葉結(jié)點(diǎn)結(jié)點(diǎn)間關(guān)系G的SG的VNG的VTG的產(chǎn)生式規(guī)則Ch2 形式語(yǔ)言自動(dòng)機(jī)理論基礎(chǔ)2.1 文法和語(yǔ)言2.1.4 語(yǔ)法樹(shù)與二義性例2.16 ： 設(shè)有無(wú)符號(hào)整數(shù)的文法 | 0 | 1 | 2 | | 9對(duì)句子25的最左推導(dǎo)過(guò)程是： = = =

25、= 2 = 25對(duì)句子25的最右推導(dǎo)過(guò)程是： = = =5 = 5 = 25Ch2 形式語(yǔ)言自動(dòng)機(jī)理論基礎(chǔ)2.1 文法和語(yǔ)言2.1.4 語(yǔ)法樹(shù)與二義性無(wú)符號(hào)整數(shù)數(shù)字串?dāng)?shù)字串?dāng)?shù)字?jǐn)?shù)字5注意：一棵語(yǔ)法樹(shù)包括了一個(gè)句型的所有可能的推導(dǎo)過(guò)程。一個(gè)句型是否只對(duì)應(yīng)一棵語(yǔ)法樹(shù)？是否只有惟一的最左（右）推導(dǎo)？2文法二義性問(wèn)題Ch2 形式語(yǔ)言自動(dòng)機(jī)理論基礎(chǔ)2.1 文法和語(yǔ)言2.1.4 語(yǔ)法樹(shù)與二義性定義2.19 ( 二義文法 )對(duì)一部文法G，如果至少存在一個(gè)句子,有兩棵( 或兩棵以上 )不同的語(yǔ)法樹(shù)，則稱該句子是二義性的。包含有二義性句子的文法稱為二義文法。否則，該文法是無(wú)二義性的。定義提供了對(duì)給定文法在某一范

26、圍內(nèi)判定是否是二義性文法的充分條件。Ch2 形式語(yǔ)言自動(dòng)機(jī)理論基礎(chǔ)2.1 文法和語(yǔ)言2.1.4 語(yǔ)法樹(shù)與二義性例2.17： 設(shè)有文法G1：E E+E | E*E | (E) | i=L L L LE=E +E =E *E+E = i *E+E = i *i+E =i*i+iL L L L LEE * EiE + EiiEE + EE * EiiiCh2 形式語(yǔ)言自動(dòng)機(jī)理論基礎(chǔ)2.1 文法和語(yǔ)言2.1.4 語(yǔ)法樹(shù)與二義性二. 文法二義性的消除例如， 對(duì)有文法G1： E E+E | E*E | (E) | i1） 分析二義性原因a) 運(yùn)算符 “+”和“*”未體現(xiàn)優(yōu)先級(jí)；b) “+”和“*”自身結(jié)合

27、規(guī)則不明確；2） 構(gòu)造G1 ，使L( G1）=L( G1)G1:E T | E+TT F | T*FF (E) | iCh2 形式語(yǔ)言自動(dòng)機(jī)理論基礎(chǔ)2.1 文法和語(yǔ)言2.1.5 文法和語(yǔ)言的類型N.Chomsky 分類 ：1. 0型文法（ 短語(yǔ)文法 ）定義2.20：如果對(duì)文法G中的規(guī)則不加任何限制，則稱G為0型文法或短語(yǔ)文法。其中，,(VTVN) *且。0型文法相應(yīng)的語(yǔ)言為0型語(yǔ)言L0，0型語(yǔ)言可由圖靈機(jī)（Turing）來(lái)識(shí)別。Ch2 形式語(yǔ)言自動(dòng)機(jī)理論基礎(chǔ)2.1 文法和語(yǔ)言2.1.5 文法和語(yǔ)言的類型例2.18: 設(shè)有文法GS aQbaQb caRbcaRb caba顯然，G是0型文法。Ch2 形式語(yǔ)言自動(dòng)機(jī)理論基礎(chǔ)2.1 文法和語(yǔ)言2.1.5 文法和語(yǔ)言的類型21型文法（ 上下文有關(guān)文法 ）定義2.21：設(shè)文法G=(VN,VT,S,P)，對(duì)P中的每個(gè)產(chǎn)生式限制為形如：A其中，AVN，,(VTVN)，(VTVN)+，則稱文法G為1型文法或上下文有關(guān)文法。1型文法相應(yīng)的語(yǔ)言為1型語(yǔ)言L1，1型語(yǔ)言可由線性有界自動(dòng)機(jī)來(lái)識(shí)別