編譯原理第03章-文法和語言

1、2021/3/111 編譯原理編譯原理 文法和語言文法和語言 華東交通大學(xué)華東交通大學(xué) 軟件學(xué)院網(wǎng)絡(luò)工程教研室軟件學(xué)院網(wǎng)絡(luò)工程教研室 萬仲保萬仲保 Tel:7046821E-mail: 2021/3/112 第三章 文法和語言 v本章目的本章目的 為語言的語法描述尋求工具為語言的語法描述尋求工具 w工具要對程序設(shè)計語言給出精確無二義的語法描述。（嚴(yán)工具要對程序設(shè)計語言給出精確無二義的語法描述。（嚴(yán) 謹(jǐn)、簡潔、易讀）謹(jǐn)、簡潔、易讀） v形式工具形式工具-形式語言抽象地定義為一個數(shù)學(xué)形式語言抽象地定義為一個數(shù)學(xué) 系統(tǒng)。系統(tǒng)?！靶问叫问健笔侵高@樣的事實：語言的是指這樣的事實

2、：語言的 所有規(guī)則只以什麼符號串能出現(xiàn)的方式來所有規(guī)則只以什麼符號串能出現(xiàn)的方式來 陳述。陳述。 2021/3/113 v3.1 文法的直觀概念 v3.2 符號和符號串 v3.3 文法和語言的形式定義 v3.4 文法的類型 v3.5 上下文無關(guān)文法及其語法樹 v3.6 句型分析 v3.7 實用說明 第三章第三章 文法和語言文法和語言 2021/3/114 文法的直觀概念文法的直觀概念 v一個程序設(shè)計語言是一個記號系統(tǒng)，如同自然語言 一樣，它的完整的定義應(yīng)包括語法和語義兩個方面。 所謂一個語言的語法是指一組規(guī)則，用它可以形成 和產(chǎn)生一個合適的程序。目前廣泛使用的手段是上 下文無關(guān)文法，即用上下文

3、無關(guān)文法作為程序設(shè)計 語言語法的描述工具。語法只是定義什么樣的符號 序列是合法的，與這些符號的含義毫無關(guān)系 v闡明語法的一個工具是文法，這是形式語言理論的 基本概念之一。 v示例：漢語句子的描述 v語言概述 2021/3/115 漢語句子的描述漢語句子的描述 v語法規(guī)則定義 v字符串的判斷 2021/3/116 語法規(guī)則定義語法規(guī)則定義 句子 =主語謂語 主語 =代詞名詞 代詞 =我你他 名詞 =王明大學(xué)生工人英語 謂語 =動詞直接賓語 動詞 =是學(xué)習(xí) 直接賓語 =代詞名詞 2021/3/117 字符串的判斷字符串的判斷 v 有了一組規(guī)則以后，按照如下方式用它們導(dǎo)出句子：開始去找 = 左端的帶

4、有句子的規(guī)則并把它由 =右端的符號串代替，這個 動作表示成： 句子 主語謂語， v 然后在得到的串主語謂語中，選取主語或謂語， 再用相應(yīng)規(guī)則的 =右端代替之。比如，選取了主語，并采用 規(guī)則主語 =代詞， v 那么得到：主語謂語 代詞謂語， 重復(fù)做下去。 v 句子：“我是大學(xué)生”的全部動作過程是： 句子主語謂語 代詞謂語 我謂語我動詞直接賓語 我是直接賓語我是名詞我是大學(xué)生 2021/3/118 字符串的判斷字符串的判斷 v“我是大學(xué)生”的構(gòu)成符合上述規(guī)則，而“我大 學(xué)生是”不符合上述規(guī)則，我們說它不是句 子。這些規(guī)則成為我們判別句子結(jié)構(gòu)合法與 否的依據(jù)，換句話說，這些規(guī)則看成是一種 元語言，用

5、它描述漢語。這里僅僅涉及漢語 句子的結(jié)構(gòu)描述。其中一種描述元語言稱為 文法。 2021/3/119 符號和符號串 v定義： 符號：可以相互區(qū)別的記號（元素）。 字母表（）：符號（元素）的非空有窮集合。 符號串：由字母表中的符號組成的任何有窮序列稱為 該字母表上的符號串。 1.空符號串(沒有符號的符號串)是上的符號串 2.若x是上的符號串,a是的元素,則xa是上的符號串 3. y是上的符號串,當(dāng)且僅當(dāng)它可以由1和2導(dǎo)出。 例如： =a,b ,a,b,aa,ab,aabba都是上的符號串 v符號串的運算 2021/3/1110 符號串的運算符號串的運算 v既然將語言定義為一個集合，那么有關(guān)集合 的

6、運算也適合語言。即：設(shè)L是（上的）一 個語言,M是（上的）一個語言，則語言L 和M的并，交，差，補是一個語言。 符號串的頭、尾、子串 符號串的長度 符號串的連接 符號串的方冪 符號串的集合 2021/3/1111 符號串的頭、尾、子串符號串的頭、尾、子串 v符號串s的頭（前綴）：移走符號串s尾部的零個或多于零 個符號得到的符號串。 如： b是符號串banana的一個前綴. v符號串s的尾（后綴）：刪去符號串s頭部的零個或多于零 個符號得到的符號串。 如:nana是符號串banana的一個后綴. v符號串s的子串：從s中刪去一個前綴和一個后綴得到的符 號串。 如:ana是符號串banana的一個

7、子串. v對于每個符號串s， s和兩者都是符號串s的前綴，后綴和 子串。 v符號串s的真前綴，真后綴，真子串：任何非空符號串 x,相 應(yīng)地，是s的前綴，后綴或子串，并且 s x。 2021/3/1112 v符號串中符號的個數(shù)。符號串中符號的個數(shù)。 v符號串符號串s的長度記為的長度記為|s|。 v的長度為的長度為0 符號串的長度符號串的長度 2021/3/1113 符號串的連接符號串的連接 v設(shè)設(shè)x x、y y是符號串，則是符號串，則x x、y y的連接是把的連接是把y y的符的符 號寫在號寫在x x的符號之后得到的符號串的符號之后得到的符號串xyxy 如如 x=ab,y=cd x=ab,y=c

8、d 則則 xy=abcdxy=abcd 有有a = aa = a 2021/3/1114 符號串的方冪符號串的方冪 v方冪：設(shè)x是符號串，把x自身連接n次得到 的符號串z，即z=aaaa稱為符號串x的方冪。 寫作z=an v示例： a1=a, a2=aa a0= 2021/3/1115 符號串集合符號串集合 v 若集合A中所有元素都是某字母表上的符號串，則稱A為 字母表上的符號串集合。 v 兩個符號串集合A和B的乘積定義為： AB =xy|xA且yB 若 集合A=ab,cde B = 0,1，則 AB =ab1,ab0,cde0,cde1 v 使用 * 表示上的所有有窮長符號串（包括）組成的集

9、 合。*稱為的閉包。 v 上的除外的所有符號串組成的集合記為+ 。 +稱為 的正閉包。 * = 012 n + = 12 n * = + + =* = * 2021/3/1116 文法和語言的形式定義 v文法和語言的形式定義 文法的定義 推導(dǎo)的定義 句型（子）的定義 語言的定義 文法等價的定義 2021/3/1117 語言概述語言概述 v 語言是由句子組成的集合，是由一組符號所構(gòu)成的集合。語言是由句子組成的集合，是由一組符號所構(gòu)成的集合。 v 漢語漢語-所有符合漢語語法的句子的全體所有符合漢語語法的句子的全體 v 英語英語-所有符合英語語法的句子的全體所有符合英語語法的句子的全體 v 每個句子

10、構(gòu)成的規(guī)律每個句子構(gòu)成的規(guī)律 v 語言研究語言研究 每個句子的含義每個句子的含義 v 每個句子和使用者的關(guān)系每個句子和使用者的關(guān)系 每個程序構(gòu)成的規(guī)律每個程序構(gòu)成的規(guī)律 v 研究程序設(shè)計語言研究程序設(shè)計語言 每個程序的含義每個程序的含義 每個程序和使用者的關(guān)系每個程序和使用者的關(guān)系 語法語法 Syntax v 語言研究的三個方面語言研究的三個方面 語義語義 Semantics 語用語用 Pragmatics 2021/3/1118 程序設(shè)計語言程序設(shè)計語言 v研究程序設(shè)計語言研究程序設(shè)計語言 每個程序構(gòu)成的規(guī)律每個程序構(gòu)成的規(guī)律 每個程序的含義每個程序的含義 每個程序和使用者的關(guān)系每個程序和使

11、用者的關(guān)系 v語言研究的三個方面語言研究的三個方面 語法語法 Syntax 語義語義 Semantics 語用語用 Pragmatics 2021/3/1119 語言研究的三個方面 v 語法 - 表示構(gòu)成語言句子的各個記號之間的組合規(guī)律 v 語義 - 表示各個記號的特定含義。（各個記號和記號所表 示的對象之間的關(guān)系） v 語用 -表示在各個記號所出現(xiàn)的行為中，它們的來源、使 用和影響。 v 每種語言具有兩個可識別的特性，即語言的形式和該形式 相關(guān)聯(lián)的意義。 v 語言的實例若在語法上是正確的，其相關(guān)聯(lián)的意義可以從 兩個觀點來看，其一是該句子的創(chuàng)立者所想要表示的意義， 另一是接收者所檢驗到的意義。

12、這兩個意義并非總是一樣 的，前者稱為語言的語義，后者是其語用意義。幽默、雙 關(guān)語和謎語就是利用這兩方面意義間的差異。 2021/3/1120 文法的定義文法的定義 v 文法G定義為四元組(VN，VT，P，S )其中VN為非終結(jié)符號 (或語法實體，或變量)集；VT為終結(jié)符號集；P為產(chǎn)生式 (也稱規(guī)則)的集合；VN，VT和P是非空有窮集。S稱作識別 符號或開始符號，它是一個非終結(jié)符，至少要在一條產(chǎn)生 式中作為左部出現(xiàn)。 v VN和VT不含公共的元素，即VN VT = v 通常用V表示VN VT ，稱為文法G的字母表或字匯表。 v 規(guī)則規(guī)則，也稱重寫規(guī)則重寫規(guī)則、產(chǎn)生式產(chǎn)生式或生成式生成式，是形如或

13、 =的(，)有序?qū)?，其中是字母表V的正閉包V+中的 一個符號，是V*中的一個符號。稱為規(guī)則的左部，稱 作規(guī)則的右部。 v 示例： 例3.1 例3.2 2021/3/1121 例例3.1 v文法G=（VN，VT，P，S），VN = S , VT = 0, 1 ，P= S0S1, S01 。這里，非 終結(jié)符集中只含一個元素S；終結(jié)符集由兩 個元素0和1組成；有兩條產(chǎn)生式；開始符號 是S。 2021/3/1122 例例3.2 v 文法G=(VN，VT，P，S) v 其中VN=標(biāo)識符，字母，數(shù)字VT=a,b,c,，x,y,z,0,1,，9 v P =標(biāo)識符字母 標(biāo)識符標(biāo)識符字母 標(biāo)識符標(biāo)識符數(shù)字 字母

14、a 字母b 字母z 數(shù)字0 數(shù)字1 數(shù)字9 S =標(biāo)識符 這里，使用尖括號和括起非終結(jié)符。 2021/3/1123 推導(dǎo)的定義 v 直接推導(dǎo)“”： 如是文法G=(Vn，VT，P，S)的規(guī)則(或說是P中的一產(chǎn)生式)， 和是 V*中的任意符號，若有符號串v，w滿足：v= ，w= 則說v(應(yīng)用規(guī)則)直接產(chǎn)生w，或者說，w是v的直接推導(dǎo)直接推導(dǎo)，也可以說， w直接歸約直接歸約到v，記作v w。 v 如果存在直接推導(dǎo)的序列： v 示例： 直接推導(dǎo) 多步推導(dǎo) 2021/3/1124 直接推導(dǎo)的示例 v 對于例3.1的文法G，可以給出直接推導(dǎo)的一些例子如下： v=0S1,w=0011， 直接推導(dǎo)：0S100

15、11，使用的規(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 對于例3.2的文法G，直接推導(dǎo)的例子有： v v=標(biāo)識符，w=標(biāo)識符字母， 直接推導(dǎo)：標(biāo)識符 標(biāo)識符字母， 使用的規(guī)則：標(biāo)識符標(biāo)識符字母，這里 = v v=標(biāo)識符字母數(shù)字，w=字母字母數(shù)字， 直接推導(dǎo)：標(biāo)識符字母數(shù)字 字母字母數(shù)字， 使用的規(guī)則：標(biāo)識符字母。這里 =， 字母數(shù)字。 v v=abc數(shù)字，w=abc5， 直接推導(dǎo)：abc數(shù)字 abc5, 使用的規(guī)則：數(shù)字5，這

16、里 =abc,=。 2021/3/1125 多步推導(dǎo)的示例多步推導(dǎo)的示例 v對例3.1的文法，存在直接推導(dǎo)序列 v=0S100S11000S11100001111=w， 即0S1 00001111，也可記作0S1 00001111 v對例3.2的文法，存在直接推導(dǎo)序列 v=標(biāo)識符標(biāo)識符數(shù)字字母 數(shù)字x數(shù)字x1=w， 即 x1，也可記作 x1。 2021/3/1126 句型(子)的定義 v設(shè)GS 是一文法，如果符號串x是從識別符 號推導(dǎo)出來的，即有S x，則稱x是文法 GS的句型句型。若x僅由終結(jié)符號組成， 即S x，xVT*，則稱x為GS的句子句子。 v例： S，0S1，000111都是例3.

17、1的文法G的句型，其 中000111是G的句子。 標(biāo)識符字母，字母數(shù)字，a1等 都是例3.2文法G的句型，其中a1是G的句子。 2021/3/1127 語言的定義 v文法G所產(chǎn)生的語言定義為集合x|S x，其中S為 文法識別符號，且xVT*?？捎肔(G)表示該集合。 v從定義可以看出兩點： 第一，符號串x可從識別符號推出，也即x是句型。 第二，x僅由終結(jié)符號組成，即x是文法G的句子。也就 是說，文法描述的語言是該文法一切句子的集合。 v例： 例3.1 G： S0S1， S01 L(G)=0n1n|n1 例3.3 2021/3/1128 例例3.3 v設(shè)G=(VN，VT，P，S)， VN=S,B

18、,E， VT=a,b,e，P由下列產(chǎn)生式組成： (1) SaSBE (2) SaBE (3) EBBE (4) aBab (5) bBbb (6) bEbe (7) eEee v則L（G）= anbnen | n1 2021/3/1129 文法的等價 v若L（G1）=L（G2），則稱文法G1和G2是等 價的。 v示例：文法G1A：A0R A01 RA1與 G2S：S0S1 S01等價。 2021/3/1130 文法的類型 v喬姆斯基分類 v 示例： 例3.4 例3.5 v喬姆斯基分類文法之間關(guān)系 v對應(yīng)于喬姆斯基分類文法的語言 v文法和語言之間的關(guān)系 2021/3/1131 喬姆斯基對文法的分

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

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

21、,P,S)，其中P由下列 產(chǎn)生式組成： S0A A1B S1B B1B S0 B1 A0A B0 A0S 或?qū)改寫為： S0A|1B|0 A0S|1B|0A B1B|1|0 v則G是正規(guī)文法或3型文法。 2021/3/1134 喬姆斯基分類文法之間關(guān)系喬姆斯基分類文法之間關(guān)系 2型文法型文法 1型文法型文法 0型文法型文法 四種四種文法文法之間之間的的逐級逐級“包含包含”關(guān)系關(guān)系 3型文法型文法 2021/3/1135 對應(yīng)喬姆斯基分類文法的對應(yīng)喬姆斯基分類文法的語言 v0型文法產(chǎn)生的語言稱為0型語言。 v1型文法或上下文有關(guān)文法（ CSG ）產(chǎn)生的語言 稱為1型語言或上下文有關(guān)語言（CSL

22、）。 v2型文法或上下文無關(guān)文法（ CFG ）產(chǎn)生的語言 稱為2型語言或上下文無關(guān)語言（ CF L ）。 v3型文法或正則（正規(guī)）文法（ RG ）產(chǎn)生的語言 稱為3型語言正則（正規(guī)）語言（ RL ）。 2021/3/1136 文法和語言之間的關(guān)系文法和語言之間的關(guān)系 v四種文法之間的關(guān)系是將產(chǎn)生式做進(jìn)一步限 制而定義的。 v語言之間的關(guān)系依次：有不是上下文有關(guān)語 言的0型語言，有不是上下文無關(guān)語言的1型 語言，有不是正則語言的上下文無關(guān)語言。 2021/3/1137 上下文無關(guān)文法及其語法樹 v語法樹 句型能夠構(gòu)造關(guān)聯(lián)語法樹的條件 示例：例3.7 v最左（右）推導(dǎo) v二義性文法 判斷依據(jù) 示例

23、：例3.8 二義性文法與二義性語言的區(qū)別 2021/3/1138 句型能夠構(gòu)造關(guān)聯(lián)語法樹的條件句型能夠構(gòu)造關(guān)聯(lián)語法樹的條件 v給定文法G=(VN，VT，P，S)，對于G的任何句型 都能構(gòu)造與之關(guān)聯(lián)的語法樹(推導(dǎo)樹)。這棵樹滿足 下列4個條件： 每個結(jié)點都有一個標(biāo)記，此標(biāo)記是V的一個符號。 根的標(biāo)記是S。 若一結(jié)點n至少有一個它自己除外的子孫（子結(jié)點）， 并且有標(biāo)記A，則A肯定在VN中。 如果結(jié)點n的直接子孫，從左到右的次序是結(jié)點n1， n2，nk，其標(biāo)記分別為A1，A2，Ak，那么 AA1A2Ak一定是P中的一個產(chǎn)生式。 2021/3/1139 例例3.7 G=(S,A,a,b,P,S)，其中

24、P為： SaAS ASbA ASS Sa Aba 右圖是G（aabbaa）的一棵推導(dǎo)樹。 2021/3/1140 最左（右）推導(dǎo)最左（右）推導(dǎo) v如果在推導(dǎo)的任何一步，其中，是句型， 都是對中的最左(最右)非終結(jié)符進(jìn)行替換，則稱 這種推導(dǎo)為最左(最右)推導(dǎo)。 v在形式語言中，最右推導(dǎo)常被稱為規(guī)范推導(dǎo)。由 規(guī)范推導(dǎo)所得的句型稱為規(guī)范句型。 v最左推導(dǎo)示例 SaASaSbASaabASaabbaSaabbaa v最右推導(dǎo)示例 SaASaAaaSbAaaSbbaaaabbaa 2021/3/1141 二義文法的判斷依據(jù)判斷依據(jù) v若一個文法存在某個句子對應(yīng)兩棵不同的語法樹， 則稱這個文法是二義的。

25、或者，若一個文法存在某個句子有兩個不同的最左 （右）推導(dǎo)，則稱這個文法是二義的。 v如果產(chǎn)生上下文無關(guān)語言的每一個文法都是二義的， 則說此語言是先天二義的。 v判定任給的一個上下文無關(guān)文法是否二義，或它是 否產(chǎn)生一個先天二義的上下文無關(guān)語言，這兩個問 題是遞歸不可解的，即，不存在一個算法，它能在 有限步驟內(nèi)，確切判定任給的一個文法是否為二義 的。我們所能做的事是為無二義性尋找一組充分條 件(當(dāng)然它們未必都是必要的)。 2021/3/1142 例例3.8 v文法G=(E,+,*,i,(,),P,E)其中P= EiEE+EEE*EE(E) 是二義性的， 假若規(guī)定了運算符“+”與“*”的優(yōu)先順序和結(jié)

26、合 規(guī)則，即按慣例，讓“*”的優(yōu)先性高于“+”，且 它們都服從左結(jié)合，那么就可以構(gòu)造出一個無二義 文法。 v定義表達(dá)式的無二義文法GE： ET|E+T TF|T*F F(E)|i 它和上述文法產(chǎn)生的語言是相同的。即它們是等價 的。 2021/3/1143 二義性文法與二義性語言的區(qū)別二義性文法與二義性語言的區(qū)別 v文法的二義性和語言的二義性是兩個 不同的概念。因為可能有兩個不同的文 法G和G，其中G是二義的，但是卻有 L(G)=L(G)，也就是說，這兩個文法 所產(chǎn)生的語言是相同的。 2021/3/1144 句型的分析 v 句型分析句型分析是識別一個輸入符號串是否為語法上正確的程序 的過程。在語

27、言的編譯實現(xiàn)中，把完成句型分析的程序稱 為分析程序分析程序或識別程序識別程序，分析算法又稱識別算法。 v 從左到右的分析算法，即總是從左到右地識別輸入符號串， 首先識別符號串中的最左符號，進(jìn)而依次識別右邊的一個 符號，直到分析結(jié)束。 v 句型的分析算法分類 v 句型的分析算法反映語法樹的構(gòu)造過程 v 句型分析的有關(guān)定義 v 句型分析的有關(guān)問題 2021/3/1145 句型的分析算法分類 v自上而下分析法： 是從文法的開始符號出發(fā)，反復(fù)使用各種產(chǎn)生 式，尋找“匹配”于輸入符號串的推導(dǎo)。 示例：例3.9 v自下而上分析法： 從輸入符號串開始，逐步進(jìn)行“歸約”，直至 歸約到文法的開始符號。 示例 2

28、021/3/1146 兩種方法反映語法樹的構(gòu)造過程 v自上而下方法： 自上而下方法是從文法符號開始，將它做為語 法樹的根，向下逐步建立語法樹，使語法樹的 末端結(jié)點符號串正好是輸入符號串。 v自下而上方法： 自下而上方法是從輸入符號串開始，以它做為 語法樹的末端結(jié)點符號串，自底向上地構(gòu)造語 法樹。 2021/3/1147 例例3.9：自上而下分析：自上而下分析 例：考慮文法GS； ScAd Aab Aa 識別輸入串w=cabd是否該文法的句子。 推導(dǎo)過程：推導(dǎo)過程：ScAd cabd 2021/3/1148 示例：自下而上分析示例：自下而上分析 例：例：考慮文法GS； ScAd Aab Aa 識

29、別輸入串w=cabd是否該文法的句子。 S AA c a b d c a b d c a b d 規(guī)約規(guī)約過程構(gòu)造的推導(dǎo)：過程構(gòu)造的推導(dǎo)： cAd cabd S cAd 2021/3/1149 句型分析的有關(guān)定義句型分析的有關(guān)定義 v令G是一文法，S是文法的開始符號，是 文法G的一個句型。如果有： S A且A 則稱是句型相對于非終結(jié)符 A的短語短語。特別，如有A 則稱是句型相 對于規(guī)則A的直接短語直接短語(也稱簡單短語簡單短語)。一個 句型的最左直接短語稱為該句型的句柄句柄。 v示例 v從句型的推導(dǎo)樹中查找方法 2021/3/1150 示例示例 v 文法GE的一個句型i*i+i。為了敘述方便，

30、將句型改寫為i1*i2+i3。因為 有： E F* i2+i3 且Fi1則稱i1是句型i1*i2+i3的相對于非終結(jié)符F的短語，也是相 對于規(guī)則Fi的直接短語。又有： E i1*F+i3 且Fi2則i2是句型i1*i2+i3的相對于F的短語，也是相對于規(guī)則 Fi的直接短語，還有： E i1*i2+F 且Fi3則i3也是句型i1*i2+i3的相對于F的短語，也是相對于規(guī)則 Fi的直接短語。 E T*i2+i3，且T i1則i1是句型i*i2+i3的相對于T的短語。 E i1*i2+T 且T i3則i3是句型i1*i2+i3的相對于T的短語。 E E+i3 且E i1*i2則i1*i2是句型i1*

31、i2+i3的相對于E的短語。 E E 且E i1*i2+i3則i1*i2+i3是句型i1*i2+i3相對于E的短語。 即i1，i2，i3，i1*i2和i1*i2+i3都是句型i1*i2+i3的短語，而且i1，i2，i3均為直接 短語，其中i1是最左直接短語，即句柄。 v 雖然i2+i3是句型i1*i2+i3的一部分，并不是它的短語，因為盡管有E i2+i3，但不存在從文法開始符號E到i1*E的推導(dǎo)。 2021/3/1151 從句型的推導(dǎo)樹中查找方法從句型的推導(dǎo)樹中查找方法 v從句型的推導(dǎo)樹上很容易找出句型的短語和直接 短語。 v設(shè)A是句型的某一子樹的根，其中是形成此 子樹的末端結(jié)點的符號串，則

32、其中是句型的 相對于A的短語。若這個子樹只有一層分支，則 是句型的直接短語。 v示例 2021/3/1152 示例：推導(dǎo)樹中找短語示例：推導(dǎo)樹中找短語 2021/3/1153 句型分析的有關(guān)問題 v在自上而下的分析方法中如何選擇使用哪個產(chǎn)生 式進(jìn)行推導(dǎo)？ 假定要被代換的最左非終結(jié)符號是B，且有n條規(guī)則： BA1|A2|An，那么如何確定用哪個右部去替代B？ v在自下而上的分析方法中如何識別可歸約的串？ 在分析程序工作的每一步，都是從當(dāng)前串中選擇一個 子串，將它歸約到某個非終結(jié)符號，該子串稱為“可 歸約串”。 v存在確定和不確定分析。 2021/3/1154 實用說明實用說明 v有關(guān)文法的實用限

33、制有關(guān)文法的實用限制 v上下文無關(guān)文法中的上下文無關(guān)文法中的規(guī)則規(guī)則 v無用符號和無用產(chǎn)生式的消除無用符號和無用產(chǎn)生式的消除 v -產(chǎn)生式的消除產(chǎn)生式的消除 v單產(chǎn)生式的消除單產(chǎn)生式的消除 2021/3/1155 有關(guān)文法的實用限制 v 在實用中，我們將限制文法中不得含有有害規(guī)則和多余規(guī) 則： 有害規(guī)則，是指形為UU的產(chǎn)生式。它對描述語言顯然是沒有必 要的。說它有害，是說它只會引起文法的二義性。 多余規(guī)則，是指文法中那些連一個句子的推導(dǎo)都用不到的規(guī)則，這 類規(guī)則在文法中以兩種形式出現(xiàn)。一種是文法中某些非終結(jié)符不在 任何規(guī)則的右部出現(xiàn)，所以任何句子的推導(dǎo)中不可能用到它。 v 對文法G=(VN，V

34、T，P，S)來說，為了保證其任一非終結(jié)符 A在句子推導(dǎo)中出現(xiàn)，必須滿足如下兩個條件： A必須在某句型中出現(xiàn)。即有S A，其中，屬于(VTVN)* 。 必須能夠從A推出終結(jié)符號串t來。即A t，其中tVT 。 v 若程序設(shè)計語言的文法包含有多余規(guī)則時，其中必定有錯 誤存在，因此檢查文法是否包含多余規(guī)則是很有必要的。 2021/3/1156 上下文無關(guān)文法中的規(guī)則 v上下文無關(guān)文法中某些規(guī)則可具有形式 A，稱這種規(guī)則為規(guī)則。 v規(guī)則會使得有關(guān)文法的一些討論和證明變 得復(fù)雜,有時會限制這種規(guī)則的出現(xiàn)。 v上下文無關(guān)文法的相關(guān)定理 定理3.1 定理3.2 2021/3/1157 定理3.1 v若L是由

35、文法G=(VN，VT，P，S)產(chǎn)生的語言，P 中的每一個產(chǎn)生式的形式均為A，其中 AVN，(VN VT)*(即可能為)， 則L能由這樣一種文法產(chǎn)生：每一個產(chǎn)生式 或者為A形式，其中AVN， (VN VT)+(即)，或者 S且 S不出現(xiàn) 在任何產(chǎn)生式右邊。 2021/3/1158 定理3.2 v如果如果G=G=(VN，VT，P，S)是一個上下文有關(guān)文法，是一個上下文有關(guān)文法， 則存在另一個上下文有關(guān)文法則存在另一個上下文有關(guān)文法G G1 1，它所產(chǎn)生，它所產(chǎn)生 的語言與的語言與G G產(chǎn)生的相同，即產(chǎn)生的相同，即L(G)=L(GL(G)=L(G1 1) )，其，其 中中G G1 1的開始符號不出現(xiàn)

36、在的開始符號不出現(xiàn)在G G1 1的任何產(chǎn)生式的的任何產(chǎn)生式的 右邊。右邊。 v若若G G為上下文無關(guān)文法或正規(guī)文法，類似結(jié)為上下文無關(guān)文法或正規(guī)文法，類似結(jié) 論成立。論成立。 2021/3/1159 無用符號和無用產(chǎn)生式的消除無用符號和無用產(chǎn)生式的消除 v定義：設(shè)G=(VN，VT，P，S)是一文法，我們說G 中的一個符號x(VNVT)是有用的指x至少出現(xiàn)在 一個句子的推導(dǎo)過程中。即x必須同時滿足以下兩 個條件： 存在、V*，有S*x 存在wVT*,x*w 否則就說x是無用的。如果一個產(chǎn)生式的左部或右部含 有無用符號，則此產(chǎn)生式稱之為無用產(chǎn)生式。 v消除算法 算法1 算法2 v示例 2021/3

37、/1160 算法算法1 v1、分別置VN(1)和P(1) 為； v2、對于P中的每一產(chǎn)生式A ，若 VT* ，則將 A置于VN(1) 中； v3、對于P中的每一產(chǎn)生式A x1x2xm若每個xi都屬 于VN(1) 或VT ，則將A置于VN(1) ； v4、重復(fù)步驟3，直到VN(1)不再增大為止； v5、對于P中的每一產(chǎn)生式B y1y2yn ，若B及每一 個yi都屬于VN(1) VT ，則將此產(chǎn)生 式B y1y2yn 置于P (1)。 2021/3/1161 算法算法2 v1、分別置VN 、VT和P 為； v2、將文法的開始符號S置入VN中； v3、對于G (1)中任何形如A x1|x2 | |

38、xm的產(chǎn)生式， 若A VN ，則將符號串x1，x2 ， ， xm中的全部 非終結(jié)符號置于VN中，而將其中的全部終結(jié)符號 置于VT中； v4、重復(fù)步驟3，直到VN和VT都不再增大為止； v5、將P中左右部僅含VN VT中符號的所有產(chǎn)生式 置P 。 2021/3/1162 示例示例 v文法的定義 已知文法G=（S,U,V,W，a,b,c，P，S），產(chǎn) 生式P的組成如下： SaS SW SU Ua VbV Vac WaW v執(zhí)行算法1 v執(zhí)行算法2 2021/3/1163 執(zhí)行算法執(zhí)行算法1 v第一步，由于產(chǎn)生式Ua、 Vac的右部均 為終結(jié)符號串，故置VN(1) =U，V； v第二步，對于產(chǎn)生式S

39、U ，由于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 Ua VbV Vac 2021/3/1164 執(zhí)行算法執(zhí)行算法2 v第一步，置VN =S； v第二步，因為G1中含有產(chǎn)生式SU、Ua ， 故應(yīng)將U、a分別置于，即VN =S，U VT =a; v因此得到等價的且不含無用符號和無用產(chǎn)生 式的文法為G2=（S，U，a，P，S）， 其中，P由如下產(chǎn)生式組成： SaS SU Ua 2021/3/1165 -產(chǎn)生式的消除 v算法3 v算法4（ 不屬于文法所產(chǎn)生的語言） v算法5 （屬于文法所產(chǎn)生的語言） v示例： 不屬于文法