編譯原理第03章 文法和語(yǔ)言

1、.1編譯原理編譯原理文法和語(yǔ)言文法和語(yǔ)言Tel:7046821 E-mail: .2第三章 文法和語(yǔ)言v本章目的本章目的 為語(yǔ)言的語(yǔ)法描述尋求工具為語(yǔ)言的語(yǔ)法描述尋求工具w工具要對(duì)程序設(shè)計(jì)語(yǔ)言給出精確無(wú)二義的語(yǔ)法描述。（嚴(yán)工具要對(duì)程序設(shè)計(jì)語(yǔ)言給出精確無(wú)二義的語(yǔ)法描述。（嚴(yán)謹(jǐn)、簡(jiǎn)潔、易讀）謹(jǐn)、簡(jiǎn)潔、易讀）v形式工具形式工具-形式語(yǔ)言抽象地定義為一個(gè)數(shù)學(xué)形式語(yǔ)言抽象地定義為一個(gè)數(shù)學(xué)系統(tǒng)。系統(tǒng)?！靶问叫问健笔侵高@樣的事實(shí)：語(yǔ)言的是指這樣的事實(shí)：語(yǔ)言的所有規(guī)則只以什麼符號(hào)串能出現(xiàn)的方式來(lái)所有規(guī)則只以什麼符號(hào)串能出現(xiàn)的方式來(lái)陳述。陳述。.3v3.1 文法的直觀概念v3.2 符號(hào)和符號(hào)串v3.3 文法和語(yǔ)

2、言的形式定義v3.4 文法的類(lèi)型v3.5 上下文無(wú)關(guān)文法及其語(yǔ)法樹(shù)v3.6 句型分析v3.7 實(shí)用說(shuō)明第三章第三章 文法和語(yǔ)言文法和語(yǔ)言.4文法的直觀概念文法的直觀概念v一個(gè)程序設(shè)計(jì)語(yǔ)言是一個(gè)記號(hào)系統(tǒng)，如同自然語(yǔ)言一樣，它的完整的定義應(yīng)包括語(yǔ)法和語(yǔ)義兩個(gè)方面。所謂一個(gè)語(yǔ)言的語(yǔ)法是指一組規(guī)則，用它可以形成和產(chǎn)生一個(gè)合適的程序。目前廣泛使用的手段是上下文無(wú)關(guān)文法，即用上下文無(wú)關(guān)文法作為程序設(shè)計(jì)語(yǔ)言語(yǔ)法的描述工具。語(yǔ)法只是定義什么樣的符號(hào)序列是合法的，與這些符號(hào)的含義毫無(wú)關(guān)系v闡明語(yǔ)法的一個(gè)工具是文法，這是形式語(yǔ)言理論的基本概念之一。v示例：漢語(yǔ)句子的描述v語(yǔ)言概述.5漢語(yǔ)句子的描述漢語(yǔ)句子的描述v

3、語(yǔ)法規(guī)則定義v字符串的判斷.6語(yǔ)法規(guī)則定義語(yǔ)法規(guī)則定義句子 =主語(yǔ)謂語(yǔ)主語(yǔ) =代詞名詞代詞 =我你他名詞 =王明大學(xué)生工人英語(yǔ)謂語(yǔ) =動(dòng)詞直接賓語(yǔ)動(dòng)詞 =是學(xué)習(xí)直接賓語(yǔ) =代詞名詞 .7字符串的判斷字符串的判斷v 有了一組規(guī)則以后，按照如下方式用它們導(dǎo)出句子：開(kāi)始去找 =左端的帶有句子的規(guī)則并把它由 =右端的符號(hào)串代替，這個(gè)動(dòng)作表示成：句子 主語(yǔ)謂語(yǔ)，v 然后在得到的串主語(yǔ)謂語(yǔ)中，選取主語(yǔ)或謂語(yǔ)，再用相應(yīng)規(guī)則的 =右端代替之。比如，選取了主語(yǔ)，并采用規(guī)則主語(yǔ) =代詞，v 那么得到：主語(yǔ)謂語(yǔ) 代詞謂語(yǔ)， 重復(fù)做下去。v 句子：“我是大學(xué)生”的全部動(dòng)作過(guò)程是：句子主語(yǔ)謂語(yǔ) 代詞謂語(yǔ)我謂語(yǔ)我動(dòng)詞直接

4、賓語(yǔ) 我是直接賓語(yǔ)我是名詞我是大學(xué)生.8字符串的判斷字符串的判斷v“我是大學(xué)生”的構(gòu)成符合上述規(guī)則，而“我大學(xué)生是”不符合上述規(guī)則，我們說(shuō)它不是句子。這些規(guī)則成為我們判別句子結(jié)構(gòu)合法與否的依據(jù)，換句話(huà)說(shuō)，這些規(guī)則看成是一種元語(yǔ)言，用它描述漢語(yǔ)。這里僅僅涉及漢語(yǔ)句子的結(jié)構(gòu)描述。其中一種描述元語(yǔ)言稱(chēng)為文法。.9符號(hào)和符號(hào)串v定義：符號(hào)：可以相互區(qū)別的記號(hào)（元素）。字母表（）：符號(hào)（元素）的非空有窮集合。符號(hào)串：由字母表中的符號(hào)組成的任何有窮序列稱(chēng)為該字母表上的符號(hào)串。1.空符號(hào)串(沒(méi)有符號(hào)的符號(hào)串)是上的符號(hào)串 2.若x是上的符號(hào)串,a是的元素,則xa是上的符號(hào)串 3. y是上的符號(hào)串,當(dāng)且僅當(dāng)它

5、可以由1和2導(dǎo)出。例如： =a,b,a,b,aa,ab,aabba都是上的符號(hào)串v符號(hào)串的運(yùn)算.10符號(hào)串的運(yùn)算符號(hào)串的運(yùn)算v既然將語(yǔ)言定義為一個(gè)集合，那么有關(guān)集合的運(yùn)算也適合語(yǔ)言。即：設(shè)L是（上的）一個(gè)語(yǔ)言,M是（上的）一個(gè)語(yǔ)言，則語(yǔ)言L和M的并，交，差，補(bǔ)是一個(gè)語(yǔ)言。符號(hào)串的頭、尾、子串符號(hào)串的長(zhǎng)度符號(hào)串的連接符號(hào)串的方冪符號(hào)串的集合.11符號(hào)串的頭、尾、子串符號(hào)串的頭、尾、子串v符號(hào)串s的頭（前綴）：移走符號(hào)串s尾部的零個(gè)或多于零個(gè)符號(hào)得到的符號(hào)串。如： b是符號(hào)串banana的一個(gè)前綴. v符號(hào)串s的尾（后綴）：刪去符號(hào)串s頭部的零個(gè)或多于零個(gè)符號(hào)得到的符號(hào)串。如:nana是符號(hào)串ba

6、nana的一個(gè)后綴.v符號(hào)串s的子串：從s中刪去一個(gè)前綴和一個(gè)后綴得到的符號(hào)串。如:ana是符號(hào)串banana的一個(gè)子串.v對(duì)于每個(gè)符號(hào)串s， s和兩者都是符號(hào)串s的前綴，后綴和子串。 v符號(hào)串s的真前綴，真后綴，真子串：任何非空符號(hào)串 x,相應(yīng)地，是s的前綴，后綴或子串，并且 s x。.12v符號(hào)串中符號(hào)的個(gè)數(shù)。符號(hào)串中符號(hào)的個(gè)數(shù)。v符號(hào)串符號(hào)串s的長(zhǎng)度記為的長(zhǎng)度記為|s|。v的長(zhǎng)度為的長(zhǎng)度為0符號(hào)串的長(zhǎng)度符號(hào)串的長(zhǎng)度.13符號(hào)串的連接符號(hào)串的連接v設(shè)設(shè)x x、y y是符號(hào)串，則是符號(hào)串，則x x、y y的連接是把的連接是把y y的符的符號(hào)寫(xiě)在號(hào)寫(xiě)在x x的符號(hào)之后得到的符號(hào)串的符號(hào)之后得到

7、的符號(hào)串xyxy如如 x=ab,y=cd x=ab,y=cd 則則 xy=abcdxy=abcd有有a = aa = a.14符號(hào)串的方冪符號(hào)串的方冪v方冪：設(shè)x是符號(hào)串，把x自身連接n次得到的符號(hào)串z，即z=aaaa稱(chēng)為符號(hào)串x的方冪。寫(xiě)作z=anv示例：a1=a, a2=aaa0=.15符號(hào)串集合符號(hào)串集合v 若集合A中所有元素都是某字母表上的符號(hào)串，則稱(chēng)A為字母表上的符號(hào)串集合。v 兩個(gè)符號(hào)串集合A和B的乘積定義為：AB =xy|xA且yB若 集合A=ab,cde B = 0,1，則 AB =ab1,ab0,cde0,cde1v 使用 * 表示上的所有有窮長(zhǎng)符號(hào)串（包括）組成的集合。*稱(chēng)

8、為的閉包。v 上的除外的所有符號(hào)串組成的集合記為+ 。 +稱(chēng)為的正閉包。* = 012 n + = 12 n * = + + =* = *.16文法和語(yǔ)言的形式定義v文法和語(yǔ)言的形式定義文法的定義推導(dǎo)的定義句型（子）的定義語(yǔ)言的定義文法等價(jià)的定義.17語(yǔ)言概述語(yǔ)言概述v 語(yǔ)言是由句子組成的集合，是由一組符號(hào)所構(gòu)成的集合。語(yǔ)言是由句子組成的集合，是由一組符號(hào)所構(gòu)成的集合。v 漢語(yǔ)漢語(yǔ)-所有符合漢語(yǔ)語(yǔ)法的句子的全體所有符合漢語(yǔ)語(yǔ)法的句子的全體v 英語(yǔ)英語(yǔ)-所有符合英語(yǔ)語(yǔ)法的句子的全體所有符合英語(yǔ)語(yǔ)法的句子的全體v 每個(gè)句子構(gòu)成的規(guī)律每個(gè)句子構(gòu)成的規(guī)律v 語(yǔ)言研究語(yǔ)言研究 每個(gè)句子的含義每個(gè)句子的含

9、義 v 每個(gè)句子和使用者的關(guān)系每個(gè)句子和使用者的關(guān)系 每個(gè)程序構(gòu)成的規(guī)律每個(gè)程序構(gòu)成的規(guī)律v 研究程序設(shè)計(jì)語(yǔ)言研究程序設(shè)計(jì)語(yǔ)言 每個(gè)程序的含義每個(gè)程序的含義 每個(gè)程序和使用者的關(guān)系每個(gè)程序和使用者的關(guān)系 語(yǔ)法語(yǔ)法 Syntaxv 語(yǔ)言研究的三個(gè)方面語(yǔ)言研究的三個(gè)方面 語(yǔ)義語(yǔ)義 Semantics 語(yǔ)用語(yǔ)用 Pragmatics .18程序設(shè)計(jì)語(yǔ)言程序設(shè)計(jì)語(yǔ)言v研究程序設(shè)計(jì)語(yǔ)言研究程序設(shè)計(jì)語(yǔ)言 每個(gè)程序構(gòu)成的規(guī)律每個(gè)程序構(gòu)成的規(guī)律 每個(gè)程序的含義每個(gè)程序的含義 每個(gè)程序和使用者的關(guān)系每個(gè)程序和使用者的關(guān)系v語(yǔ)言研究的三個(gè)方面語(yǔ)言研究的三個(gè)方面 語(yǔ)法語(yǔ)法 Syntax 語(yǔ)義語(yǔ)義 Semantics

10、 語(yǔ)用語(yǔ)用 Pragmatics.19 語(yǔ)言研究的三個(gè)方面v 語(yǔ)法 - 表示構(gòu)成語(yǔ)言句子的各個(gè)記號(hào)之間的組合規(guī)律v 語(yǔ)義 - 表示各個(gè)記號(hào)的特定含義。（各個(gè)記號(hào)和記號(hào)所表示的對(duì)象之間的關(guān)系）v 語(yǔ)用 -表示在各個(gè)記號(hào)所出現(xiàn)的行為中，它們的來(lái)源、使用和影響。v 每種語(yǔ)言具有兩個(gè)可識(shí)別的特性，即語(yǔ)言的形式和該形式相關(guān)聯(lián)的意義。v 語(yǔ)言的實(shí)例若在語(yǔ)法上是正確的，其相關(guān)聯(lián)的意義可以從兩個(gè)觀點(diǎn)來(lái)看，其一是該句子的創(chuàng)立者所想要表示的意義，另一是接收者所檢驗(yàn)到的意義。這兩個(gè)意義并非總是一樣的，前者稱(chēng)為語(yǔ)言的語(yǔ)義，后者是其語(yǔ)用意義。幽默、雙關(guān)語(yǔ)和謎語(yǔ)就是利用這兩方面意義間的差異。.20文法的定義文法的定義v

11、文法G定義為四元組(VN，VT，P，S )其中VN為非終結(jié)符號(hào)(或語(yǔ)法實(shí)體，或變量)集；VT為終結(jié)符號(hào)集；P為產(chǎn)生式(也稱(chēng)規(guī)則)的集合；VN，VT和P是非空有窮集。S稱(chēng)作識(shí)別符號(hào)或開(kāi)始符號(hào)，它是一個(gè)非終結(jié)符，至少要在一條產(chǎn)生式中作為左部出現(xiàn)。v VN和VT不含公共的元素，即VN VT = v 通常用V表示VN VT ，稱(chēng)為文法G的字母表或字匯表。v 規(guī)則規(guī)則，也稱(chēng)重寫(xiě)規(guī)則重寫(xiě)規(guī)則、產(chǎn)生式產(chǎn)生式或生成式生成式，是形如或 =的(，)有序?qū)?，其中是字母表V的正閉包V+中的一個(gè)符號(hào)，是V*中的一個(gè)符號(hào)。稱(chēng)為規(guī)則的左部，稱(chēng)作規(guī)則的右部。v 示例：例3.1例3.2.21例例3.1v文法G=（VN，VT，P

12、，S），VN = S , VT = 0, 1 ，P= S0S1, S01 。這里，非終結(jié)符集中只含一個(gè)元素S；終結(jié)符集由兩個(gè)元素0和1組成；有兩條產(chǎn)生式；開(kāi)始符號(hào)是S。.22例例3.2v 文法G=(VN，VT，P，S) v 其中VN=標(biāo)識(shí)符，字母，數(shù)字VT=a,b,c,，x,y,z,0,1,，9v P =標(biāo)識(shí)符字母標(biāo)識(shí)符標(biāo)識(shí)符字母標(biāo)識(shí)符標(biāo)識(shí)符數(shù)字字母a字母b字母z數(shù)字0數(shù)字1數(shù)字9S =標(biāo)識(shí)符這里，使用尖括號(hào)和括起非終結(jié)符。.23推導(dǎo)的定義v 直接推導(dǎo)“”：如是文法G=(Vn，VT，P，S)的規(guī)則(或說(shuō)是P中的一產(chǎn)生式)， 和是V*中的任意符號(hào)，若有符號(hào)串v，w滿(mǎn)足：v= ，w= 則說(shuō)v(應(yīng)用

13、規(guī)則)直接產(chǎn)生w，或者說(shuō)，w是v的直接推導(dǎo)直接推導(dǎo)，也可以說(shuō)，w直接歸約直接歸約到v，記作v w。v 如果存在直接推導(dǎo)的序列：v 示例：直接推導(dǎo)多步推導(dǎo).24直接推導(dǎo)的示例v 對(duì)于例3.1的文法G，可以給出直接推導(dǎo)的一些例子如下：v=0S1,w=0011，直接推導(dǎo)：0S10011，使用的規(guī)則：S01，這里 =0，=1。v=S,w=0S1，直接推導(dǎo)：S0S1使用的規(guī)則：S0S1，這里 =，=v=0S1,w=00S11，直接推導(dǎo)：0S100S11，使用的規(guī)則：S0S1，這里 =0，=1。v 對(duì)于例3.2的文法G，直接推導(dǎo)的例子有：v v=標(biāo)識(shí)符，w=標(biāo)識(shí)符字母，直接推導(dǎo)：標(biāo)識(shí)符 標(biāo)識(shí)符字母，使用的

14、規(guī)則：標(biāo)識(shí)符標(biāo)識(shí)符字母，這里 =v v=標(biāo)識(shí)符字母數(shù)字，w=字母字母數(shù)字，直接推導(dǎo)：標(biāo)識(shí)符字母數(shù)字 字母字母數(shù)字，使用的規(guī)則：標(biāo)識(shí)符字母。這里 =， 字母數(shù)字。v v=abc數(shù)字，w=abc5，直接推導(dǎo)：abc數(shù)字 abc5, 使用的規(guī)則：數(shù)字5，這里 =abc,=。.25多步推導(dǎo)的示例多步推導(dǎo)的示例v對(duì)例3.1的文法，存在直接推導(dǎo)序列v=0S100S11000S11100001111=w，即0S1 00001111，也可記作0S1 00001111v對(duì)例3.2的文法，存在直接推導(dǎo)序列v=標(biāo)識(shí)符標(biāo)識(shí)符數(shù)字字母數(shù)字x數(shù)字x1=w，即 x1，也可記作 x1。.26句型(子)的定義v設(shè)GS 是一文法

15、，如果符號(hào)串x是從識(shí)別符號(hào)推導(dǎo)出來(lái)的，即有S x，則稱(chēng)x是文法GS的句型句型。若x僅由終結(jié)符號(hào)組成， 即S x，xVT*，則稱(chēng)x為GS的句子句子。v例：S，0S1，000111都是例3.1的文法G的句型，其中000111是G的句子。標(biāo)識(shí)符字母，字母數(shù)字，a1等都是例3.2文法G的句型，其中a1是G的句子。.27語(yǔ)言的定義v文法G所產(chǎn)生的語(yǔ)言定義為集合x(chóng)|S x，其中S為文法識(shí)別符號(hào)，且xVT*?？捎肔(G)表示該集合。v從定義可以看出兩點(diǎn)：第一，符號(hào)串x可從識(shí)別符號(hào)推出，也即x是句型。第二，x僅由終結(jié)符號(hào)組成，即x是文法G的句子。也就是說(shuō)，文法描述的語(yǔ)言是該文法一切句子的集合。v例：例3.1

16、G： S0S1， S01 L(G)=0n1n|n1例3.3.28例例3.3v設(shè)G=(VN，VT，P，S)， VN=S,B,E，VT=a,b,e，P由下列產(chǎn)生式組成：(1) SaSBE (2) SaBE (3) EBBE(4) aBab (5) bBbb (6) bEbe(7) eEeev則L（G）= anbnen | n1 .29文法的等價(jià)v若L（G1）=L（G2），則稱(chēng)文法G1和G2是等價(jià)的。v示例：文法G1A：A0R A01 RA1與G2S：S0S1 S01等價(jià)。 .30文法的類(lèi)型v喬姆斯基分類(lèi)v 示例：例3.4例3.5v喬姆斯基分類(lèi)文法之間關(guān)系v對(duì)應(yīng)于喬姆斯基分類(lèi)文法的語(yǔ)言v文法和語(yǔ)言之

17、間的關(guān)系.31喬姆斯基對(duì)文法的分類(lèi)喬姆斯基對(duì)文法的分類(lèi)v 通過(guò)對(duì)產(chǎn)生式施加不同的限制，Chomsky（喬姆斯基）將文法分為四種類(lèi)型：0型文法：對(duì)文法G=(VN，VT，P，S)的任一產(chǎn)生式，都有(VNVT)*且至少含有一個(gè)非終結(jié)符，(VNVT)*。1型文法（上下文有關(guān)文法）上下文有關(guān)文法） ：對(duì)文法G=(VN，VT，P，S)的任一產(chǎn)生式，都有|， 僅僅 S除外。2型文法（上下文無(wú)關(guān)文法）上下文無(wú)關(guān)文法）：對(duì)文法G=(VN，VT，P，S)的任一產(chǎn)生式，都有VN ， (VNVT)* 。3型文法（正規(guī)文法正規(guī)文法）：設(shè)G=(VN，VT，P，S)，若P中的每一個(gè)產(chǎn)生式的形式都是AaB或Aa，其中A和B都

18、是非終結(jié)符，a是終結(jié)符。3型文法G=(VN，VT，P，S)的P中的規(guī)則有兩種形式：一種是前面定義的形式，即：AaB或Aa其中A，BVN ，aVT*，另一種形式是：ABa或Aa，前者稱(chēng)為右線性文法，后者稱(chēng)為左線性文法。正規(guī)文法所描述的是VT*上的正規(guī)集。.32例例3.43.4vG=(S,A,B,a,b,P,S)，其中P由下列產(chǎn)生式組成：SaB AbAA SbA BbAa BbS AaS BaBB或?qū)改寫(xiě)為：SaB|bA AbA|a Aa|AaS BbS|BaB|bv則G是正規(guī)文法或3型文法。.33例例3.53.5v文法G=(S,A,B,0,1,P,S)，其中P由下列產(chǎn)生式組成：S0A A1B

19、S1B B1BS0 B1 A0A B0 A0S或?qū)改寫(xiě)為：S0A|1B|0A0S|1B|0AB1B|1|0 v則G是正規(guī)文法或3型文法。.34喬姆斯基分類(lèi)文法之間關(guān)系喬姆斯基分類(lèi)文法之間關(guān)系2型文法型文法1型文法型文法0型文法型文法四種四種文法文法之間之間的的逐級(jí)逐級(jí)“包含包含”關(guān)系關(guān)系3型文法型文法.35對(duì)應(yīng)喬姆斯基分類(lèi)文法的對(duì)應(yīng)喬姆斯基分類(lèi)文法的語(yǔ)言v0型文法產(chǎn)生的語(yǔ)言稱(chēng)為0型語(yǔ)言。v1型文法或上下文有關(guān)文法（ CSG ）產(chǎn)生的語(yǔ)言稱(chēng)為1型語(yǔ)言或上下文有關(guān)語(yǔ)言（CSL）。v2型文法或上下文無(wú)關(guān)文法（ CFG ）產(chǎn)生的語(yǔ)言稱(chēng)為2型語(yǔ)言或上下文無(wú)關(guān)語(yǔ)言（ CF L ）。 v3型文法或正則（正

20、規(guī)）文法（ RG ）產(chǎn)生的語(yǔ)言稱(chēng)為3型語(yǔ)言正則（正規(guī)）語(yǔ)言（ RL ）。 .36文法和語(yǔ)言之間的關(guān)系文法和語(yǔ)言之間的關(guān)系v四種文法之間的關(guān)系是將產(chǎn)生式做進(jìn)一步限制而定義的。v語(yǔ)言之間的關(guān)系依次：有不是上下文有關(guān)語(yǔ)言的0型語(yǔ)言，有不是上下文無(wú)關(guān)語(yǔ)言的1型語(yǔ)言，有不是正則語(yǔ)言的上下文無(wú)關(guān)語(yǔ)言。.37上下文無(wú)關(guān)文法及其語(yǔ)法樹(shù)v語(yǔ)法樹(shù)句型能夠構(gòu)造關(guān)聯(lián)語(yǔ)法樹(shù)的條件示例：例3.7v最左（右）推導(dǎo)v二義性文法判斷依據(jù)示例：例3.8二義性文法與二義性語(yǔ)言的區(qū)別.38句型能夠構(gòu)造關(guān)聯(lián)語(yǔ)法樹(shù)的條件句型能夠構(gòu)造關(guān)聯(lián)語(yǔ)法樹(shù)的條件v給定文法G=(VN，VT，P，S)，對(duì)于G的任何句型都能構(gòu)造與之關(guān)聯(lián)的語(yǔ)法樹(shù)(推導(dǎo)樹(shù))。

21、這棵樹(shù)滿(mǎn)足下列4個(gè)條件： 每個(gè)結(jié)點(diǎn)都有一個(gè)標(biāo)記，此標(biāo)記是V的一個(gè)符號(hào)。 根的標(biāo)記是S。 若一結(jié)點(diǎn)n至少有一個(gè)它自己除外的子孫（子結(jié)點(diǎn)），并且有標(biāo)記A，則A肯定在VN中。 如果結(jié)點(diǎn)n的直接子孫，從左到右的次序是結(jié)點(diǎn)n1，n2，nk，其標(biāo)記分別為A1，A2，Ak，那么AA1A2Ak一定是P中的一個(gè)產(chǎn)生式。.39例例3.7G=(S,A,a,b,P,S)，其中P為： SaAS ASbA ASS Sa Aba右圖是G（aabbaa）的一棵推導(dǎo)樹(shù)。.40最左（右）推導(dǎo)最左（右）推導(dǎo)v如果在推導(dǎo)的任何一步，其中，是句型，都是對(duì)中的最左(最右)非終結(jié)符進(jìn)行替換，則稱(chēng)這種推導(dǎo)為最左(最右)推導(dǎo)。v在形式語(yǔ)言中，

22、最右推導(dǎo)常被稱(chēng)為規(guī)范推導(dǎo)。由規(guī)范推導(dǎo)所得的句型稱(chēng)為規(guī)范句型。v最左推導(dǎo)示例SaASaSbASaabASaabbaSaabbaav最右推導(dǎo)示例SaASaAaaSbAaaSbbaaaabbaa.41二義文法的判斷依據(jù)判斷依據(jù)v若一個(gè)文法存在某個(gè)句子對(duì)應(yīng)兩棵不同的語(yǔ)法樹(shù)，則稱(chēng)這個(gè)文法是二義的?；蛘?，若一個(gè)文法存在某個(gè)句子有兩個(gè)不同的最左（右）推導(dǎo)，則稱(chēng)這個(gè)文法是二義的。v如果產(chǎn)生上下文無(wú)關(guān)語(yǔ)言的每一個(gè)文法都是二義的，則說(shuō)此語(yǔ)言是先天二義的。v判定任給的一個(gè)上下文無(wú)關(guān)文法是否二義，或它是否產(chǎn)生一個(gè)先天二義的上下文無(wú)關(guān)語(yǔ)言，這兩個(gè)問(wèn)題是遞歸不可解的，即，不存在一個(gè)算法，它能在有限步驟內(nèi)，確切判定任給的一

23、個(gè)文法是否為二義的。我們所能做的事是為無(wú)二義性尋找一組充分條件(當(dāng)然它們未必都是必要的)。 .42例例3.8v文法G=(E,+,*,i,(,),P,E)其中P=EiEE+EEE*EE(E) 是二義性的，假若規(guī)定了運(yùn)算符“+”與“*”的優(yōu)先順序和結(jié)合規(guī)則，即按慣例，讓“*”的優(yōu)先性高于“+”，且它們都服從左結(jié)合，那么就可以構(gòu)造出一個(gè)無(wú)二義文法。v定義表達(dá)式的無(wú)二義文法GE：ET|E+TTF|T*FF(E)|i它和上述文法產(chǎn)生的語(yǔ)言是相同的。即它們是等價(jià)的。.43二義性文法與二義性語(yǔ)言的區(qū)別二義性文法與二義性語(yǔ)言的區(qū)別v文法的二義性和語(yǔ)言的二義性是兩個(gè)不同的概念。因?yàn)榭赡苡袃蓚€(gè)不同的文法G和G，其

24、中G是二義的，但是卻有L(G)=L(G)，也就是說(shuō)，這兩個(gè)文法所產(chǎn)生的語(yǔ)言是相同的。.44句型的分析v 句型分析句型分析是識(shí)別一個(gè)輸入符號(hào)串是否為語(yǔ)法上正確的程序的過(guò)程。在語(yǔ)言的編譯實(shí)現(xiàn)中，把完成句型分析的程序稱(chēng)為分析程序分析程序或識(shí)別程序識(shí)別程序，分析算法又稱(chēng)識(shí)別算法。v 從左到右的分析算法，即總是從左到右地識(shí)別輸入符號(hào)串，首先識(shí)別符號(hào)串中的最左符號(hào)，進(jìn)而依次識(shí)別右邊的一個(gè)符號(hào)，直到分析結(jié)束。v 句型的分析算法分類(lèi)v 句型的分析算法反映語(yǔ)法樹(shù)的構(gòu)造過(guò)程v 句型分析的有關(guān)定義v 句型分析的有關(guān)問(wèn)題.45句型的分析算法分類(lèi)v自上而下分析法：是從文法的開(kāi)始符號(hào)出發(fā)，反復(fù)使用各種產(chǎn)生式，尋找“匹配”

25、于輸入符號(hào)串的推導(dǎo)。示例：例3.9v自下而上分析法：從輸入符號(hào)串開(kāi)始，逐步進(jìn)行“歸約”，直至歸約到文法的開(kāi)始符號(hào)。示例 .46兩種方法反映語(yǔ)法樹(shù)的構(gòu)造過(guò)程v自上而下方法：自上而下方法是從文法符號(hào)開(kāi)始，將它做為語(yǔ)法樹(shù)的根，向下逐步建立語(yǔ)法樹(shù)，使語(yǔ)法樹(shù)的末端結(jié)點(diǎn)符號(hào)串正好是輸入符號(hào)串。v自下而上方法：自下而上方法是從輸入符號(hào)串開(kāi)始，以它做為語(yǔ)法樹(shù)的末端結(jié)點(diǎn)符號(hào)串，自底向上地構(gòu)造語(yǔ)法樹(shù)。.47例例3.9：自上而下分析：自上而下分析例：考慮文法GS； ScAd Aab Aa識(shí)別輸入串w=cabd是否該文法的句子。推導(dǎo)過(guò)程：推導(dǎo)過(guò)程：ScAd cabd.48示例：自下而上分析示例：自下而上分析例：例：考

26、慮文法GS； ScAd Aab Aa識(shí)別輸入串w=cabd是否該文法的句子。SAA c a b d c a b d c a b d 規(guī)約規(guī)約過(guò)程構(gòu)造的推導(dǎo)：過(guò)程構(gòu)造的推導(dǎo)： cAd cabd S cAd.49句型分析的有關(guān)定義句型分析的有關(guān)定義v令G是一文法，S是文法的開(kāi)始符號(hào)，是文法G的一個(gè)句型。如果有：S A且A 則稱(chēng)是句型相對(duì)于非終結(jié)符A的短語(yǔ)短語(yǔ)。特別，如有A 則稱(chēng)是句型相對(duì)于規(guī)則A的直接短語(yǔ)直接短語(yǔ)(也稱(chēng)簡(jiǎn)單短語(yǔ)簡(jiǎn)單短語(yǔ))。一個(gè)句型的最左直接短語(yǔ)稱(chēng)為該句型的句柄句柄。v示例v從句型的推導(dǎo)樹(shù)中查找方法.50示例示例v 文法GE的一個(gè)句型i*i+i。為了敘述方便，將句型改寫(xiě)為i1*i2+

27、i3。因?yàn)橛校篍 F* i2+i3 且Fi1則稱(chēng)i1是句型i1*i2+i3的相對(duì)于非終結(jié)符F的短語(yǔ)，也是相對(duì)于規(guī)則Fi的直接短語(yǔ)。又有：E i1*F+i3 且Fi2則i2是句型i1*i2+i3的相對(duì)于F的短語(yǔ)，也是相對(duì)于規(guī)則Fi的直接短語(yǔ)，還有：E i1*i2+F 且Fi3則i3也是句型i1*i2+i3的相對(duì)于F的短語(yǔ)，也是相對(duì)于規(guī)則Fi的直接短語(yǔ)。E T*i2+i3，且T i1則i1是句型i*i2+i3的相對(duì)于T的短語(yǔ)。E i1*i2+T 且T i3則i3是句型i1*i2+i3的相對(duì)于T的短語(yǔ)。E E+i3 且E i1*i2則i1*i2是句型i1*i2+i3的相對(duì)于E的短語(yǔ)。E E 且E i

28、1*i2+i3則i1*i2+i3是句型i1*i2+i3相對(duì)于E的短語(yǔ)。即i1，i2，i3，i1*i2和i1*i2+i3都是句型i1*i2+i3的短語(yǔ)，而且i1，i2，i3均為直接短語(yǔ)，其中i1是最左直接短語(yǔ)，即句柄。v 雖然i2+i3是句型i1*i2+i3的一部分，并不是它的短語(yǔ)，因?yàn)楸M管有E i2+i3，但不存在從文法開(kāi)始符號(hào)E到i1*E的推導(dǎo)。.51從句型的推導(dǎo)樹(shù)中查找方法從句型的推導(dǎo)樹(shù)中查找方法v從句型的推導(dǎo)樹(shù)上很容易找出句型的短語(yǔ)和直接短語(yǔ)。v設(shè)A是句型的某一子樹(shù)的根，其中是形成此子樹(shù)的末端結(jié)點(diǎn)的符號(hào)串，則其中是句型的相對(duì)于A的短語(yǔ)。若這個(gè)子樹(shù)只有一層分支，則是句型的直接短語(yǔ)。v示例.

29、52示例：推導(dǎo)樹(shù)中找短語(yǔ)示例：推導(dǎo)樹(shù)中找短語(yǔ).53句型分析的有關(guān)問(wèn)題v在自上而下的分析方法中如何選擇使用哪個(gè)產(chǎn)生式進(jìn)行推導(dǎo)？假定要被代換的最左非終結(jié)符號(hào)是B，且有n條規(guī)則：BA1|A2|An，那么如何確定用哪個(gè)右部去替代B？v在自下而上的分析方法中如何識(shí)別可歸約的串？在分析程序工作的每一步，都是從當(dāng)前串中選擇一個(gè)子串，將它歸約到某個(gè)非終結(jié)符號(hào)，該子串稱(chēng)為“可歸約串”。v存在確定和不確定分析。.54實(shí)用說(shuō)明實(shí)用說(shuō)明 v有關(guān)文法的實(shí)用限制有關(guān)文法的實(shí)用限制 v上下文無(wú)關(guān)文法中的上下文無(wú)關(guān)文法中的規(guī)則規(guī)則v無(wú)用符號(hào)和無(wú)用產(chǎn)生式的消除無(wú)用符號(hào)和無(wú)用產(chǎn)生式的消除v -產(chǎn)生式的消除產(chǎn)生式的消除v單產(chǎn)生式的

30、消除單產(chǎn)生式的消除.55有關(guān)文法的實(shí)用限制v 在實(shí)用中，我們將限制文法中不得含有有害規(guī)則和多余規(guī)則：有害規(guī)則，是指形為UU的產(chǎn)生式。它對(duì)描述語(yǔ)言顯然是沒(méi)有必要的。說(shuō)它有害，是說(shuō)它只會(huì)引起文法的二義性。多余規(guī)則，是指文法中那些連一個(gè)句子的推導(dǎo)都用不到的規(guī)則，這類(lèi)規(guī)則在文法中以?xún)煞N形式出現(xiàn)。一種是文法中某些非終結(jié)符不在任何規(guī)則的右部出現(xiàn)，所以任何句子的推導(dǎo)中不可能用到它。v 對(duì)文法G=(VN，VT，P，S)來(lái)說(shuō)，為了保證其任一非終結(jié)符A在句子推導(dǎo)中出現(xiàn)，必須滿(mǎn)足如下兩個(gè)條件： A必須在某句型中出現(xiàn)。即有S A，其中，屬于(VTVN)* 。 必須能夠從A推出終結(jié)符號(hào)串t來(lái)。即A t，其中tVT 。v

31、 若程序設(shè)計(jì)語(yǔ)言的文法包含有多余規(guī)則時(shí)，其中必定有錯(cuò)誤存在，因此檢查文法是否包含多余規(guī)則是很有必要的。.56上下文無(wú)關(guān)文法中的規(guī)則v上下文無(wú)關(guān)文法中某些規(guī)則可具有形式A，稱(chēng)這種規(guī)則為規(guī)則。v規(guī)則會(huì)使得有關(guān)文法的一些討論和證明變得復(fù)雜,有時(shí)會(huì)限制這種規(guī)則的出現(xiàn)。v上下文無(wú)關(guān)文法的相關(guān)定理定理3.1定理3.2.57定理3.1v若L是由文法G=(VN，VT，P，S)產(chǎn)生的語(yǔ)言，P中的每一個(gè)產(chǎn)生式的形式均為A，其中AVN，(VN VT)*(即可能為)，則L能由這樣一種文法產(chǎn)生：每一個(gè)產(chǎn)生式或者為A形式，其中AVN， (VN VT)+(即)，或者 S且 S不出現(xiàn)在任何產(chǎn)生式右邊。.58定理3.2v如果如

32、果G=G=(VN，VT，P，S)是一個(gè)上下文有關(guān)文法，是一個(gè)上下文有關(guān)文法，則存在另一個(gè)上下文有關(guān)文法則存在另一個(gè)上下文有關(guān)文法G G1 1，它所產(chǎn)生，它所產(chǎn)生的語(yǔ)言與的語(yǔ)言與G G產(chǎn)生的相同，即產(chǎn)生的相同，即L(G)=L(GL(G)=L(G1 1) )，其，其中中G G1 1的開(kāi)始符號(hào)不出現(xiàn)在的開(kāi)始符號(hào)不出現(xiàn)在G G1 1的任何產(chǎn)生式的的任何產(chǎn)生式的右邊。右邊。v若若G G為上下文無(wú)關(guān)文法或正規(guī)文法，類(lèi)似結(jié)為上下文無(wú)關(guān)文法或正規(guī)文法，類(lèi)似結(jié)論成立。論成立。.59無(wú)用符號(hào)和無(wú)用產(chǎn)生式的消除無(wú)用符號(hào)和無(wú)用產(chǎn)生式的消除v定義：設(shè)G=(VN，VT，P，S)是一文法，我們說(shuō)G中的一個(gè)符號(hào)x(VNVT)

33、是有用的指x至少出現(xiàn)在一個(gè)句子的推導(dǎo)過(guò)程中。即x必須同時(shí)滿(mǎn)足以下兩個(gè)條件：存在、V*，有S*x存在wVT*,x*w否則就說(shuō)x是無(wú)用的。如果一個(gè)產(chǎn)生式的左部或右部含有無(wú)用符號(hào)，則此產(chǎn)生式稱(chēng)之為無(wú)用產(chǎn)生式。v消除算法算法1算法2v示例.60算法算法1v1、分別置VN(1)和P(1) 為；v2、對(duì)于P中的每一產(chǎn)生式A ，若 VT* ，則將A置于VN(1) 中；v3、對(duì)于P中的每一產(chǎn)生式A x1x2xm若每個(gè)xi都屬于VN(1) 或VT ，則將A置于VN(1) ；v4、重復(fù)步驟3，直到VN(1)不再增大為止；v5、對(duì)于P中的每一產(chǎn)生式B y1y2yn ，若B及每一個(gè)yi都屬于VN(1) VT ，則將此

34、產(chǎn)生 式B y1y2yn置于P (1)。.61算法算法2v1、分別置VN 、VT和P 為；v2、將文法的開(kāi)始符號(hào)S置入VN中； v3、對(duì)于G (1)中任何形如A x1|x2 | | xm的產(chǎn)生式，若A VN ，則將符號(hào)串x1，x2 ， ， xm中的全部非終結(jié)符號(hào)置于VN中，而將其中的全部終結(jié)符號(hào)置于VT中；v4、重復(fù)步驟3，直到VN和VT都不再增大為止；v5、將P中左右部?jī)H含VN VT中符號(hào)的所有產(chǎn)生式置P 。.62示例示例v文法的定義已知文法G=（S,U,V,W，a,b,c，P，S），產(chǎn)生式P的組成如下：SaS SW SU UaVbV Vac WaWv執(zhí)行算法1v執(zhí)行算法2.63執(zhí)行算法執(zhí)行

35、算法1v第一步，由于產(chǎn)生式Ua、 Vac的右部均為終結(jié)符號(hào)串，故置VN(1) =U，V；v第二步，對(duì)于產(chǎn)生式SU ，由于U VN(1) ，故將S置于中，所以VN(1) =S，U，V；v于是得到以下文法G1：vG1=（S,U,V,a,b,c,P (1),S），其中P (1)由如下產(chǎn)生式組成：SaS SU UaVbV Vac.64執(zhí)行算法執(zhí)行算法2v第一步，置VN =S；v第二步，因?yàn)镚1中含有產(chǎn)生式SU、Ua ，故應(yīng)將U、a分別置于，即VN =S，U VT =a;v因此得到等價(jià)的且不含無(wú)用符號(hào)和無(wú)用產(chǎn)生式的文法為G2=（S，U，a，P，S），其中，P由如下產(chǎn)生式組成：SaS SU Ua.65-產(chǎn)生式的消除v算法3v算法4（ 不屬于文法所產(chǎn)生的語(yǔ)言）v算法5 （屬于文法所產(chǎn)生的語(yǔ)言）v示例：不屬于文法所產(chǎn)生的語(yǔ)言屬于文法所產(chǎn)生的語(yǔ)言.66算法算法3v1、作集合 W