編譯原理及其習(xí)題解答武漢大學(xué)出版社課件.ppt
《編譯原理及其習(xí)題解答武漢大學(xué)出版社課件.ppt》由會(huì)員分享,可在線閱讀,更多相關(guān)《編譯原理及其習(xí)題解答武漢大學(xué)出版社課件.ppt(84頁(yè)珍藏版)》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。
1,第二章 文法和語(yǔ)言,要點(diǎn)(本章是基礎(chǔ)) 1、概念:文法,推導(dǎo),直接推導(dǎo),最左(右)推導(dǎo),產(chǎn)生式,句型,短語(yǔ),直接短語(yǔ),句柄,語(yǔ)法樹,規(guī)范推導(dǎo),二義文法等 2、4種文法的定義、文法的構(gòu)造和文法的推導(dǎo) 3、語(yǔ)法樹的構(gòu)造和最左(右)推導(dǎo); 4、二義文法、二義性的證明; 5、句型分析;,2,詞法規(guī)則:自動(dòng)機(jī) 語(yǔ)法規(guī)則:上下文無(wú)關(guān)文法,3,引言,語(yǔ)言包括語(yǔ)法和語(yǔ)義兩方面。 語(yǔ)法是一組規(guī)則,用以判斷什么樣的符號(hào)序列是合法的; 語(yǔ)義指含義,如變量的類型、作用域是否符合正確的語(yǔ)法。常把程序設(shè)計(jì)語(yǔ)言的語(yǔ)義分為二類:靜態(tài)語(yǔ)義和動(dòng)態(tài)語(yǔ)義。靜態(tài)語(yǔ)義是一系列限定規(guī)則,并確定哪些合乎語(yǔ)法的程序是合適的;動(dòng)態(tài)語(yǔ)義(或稱運(yùn)行語(yǔ)義、執(zhí)行語(yǔ)義),表明程序要做些什么,要計(jì)算什么。 闡明語(yǔ)法的一個(gè)工具是文法,常采用上下文無(wú)關(guān)文法作為程序設(shè)計(jì)語(yǔ)言語(yǔ)法的描述工具。,4,補(bǔ)充: 文法的直觀概念(1/5),描述一種語(yǔ)言,無(wú)非是說(shuō)明這種語(yǔ)言的句子。如果該語(yǔ)言所含的句子是有限的,那么只要一一列舉出即可;若是無(wú)限的,則存在如何給出有窮表示的問(wèn)題。但無(wú)論如何,某語(yǔ)言的句子總是存在著一種組成結(jié)構(gòu),即所謂的規(guī)則(或稱文法)。 文法:描述語(yǔ)言的語(yǔ)法結(jié)構(gòu)的形式規(guī)則(即語(yǔ)法規(guī)則)。,5,直觀文法舉例(2/5),例如:簡(jiǎn)單的漢語(yǔ)句子的構(gòu)成規(guī)則 ::= ::= | ::= 我 | 你 | 他 ::=王明| 大學(xué)生|工人|英語(yǔ) ::= ::=是 |學(xué)習(xí) ::= | 則 “我是大學(xué)生”是句子,6,“我是大學(xué)生”的推導(dǎo)過(guò)程: 我 我 我是 我是 我是大學(xué)生 依次可以推導(dǎo)出句子“王明是大學(xué)生”、“我學(xué)習(xí)英語(yǔ)”等等,推導(dǎo)過(guò)程(3/5),7,程序設(shè)計(jì)語(yǔ)言對(duì)文法的要求(4/5),這些規(guī)則必須是準(zhǔn)確的,易于理解的,且應(yīng)當(dāng)有相當(dāng)強(qiáng)的描述能力,足以描述各種不同的結(jié)構(gòu)。,8,文法作用(5/5),(1)定義句子的結(jié)構(gòu); (2)用適當(dāng)條數(shù)的規(guī)則把語(yǔ)言的全部句子描述出來(lái),以有窮集合刻劃無(wú)窮集合。,9,2 符號(hào)串及其運(yùn)算 (1)符號(hào)串:由字母表中的符號(hào)組成的任何有窮序列。 說(shuō)明: 字母間的順序 不同順序組成的符號(hào)串是不同的; (2)符號(hào)串長(zhǎng)度 符號(hào)串內(nèi)所含符號(hào)的個(gè)數(shù),若x=string,則|x|=6; 其中不含任何符號(hào)的符號(hào)串稱為空符號(hào)串ε,長(zhǎng)度| ε |=0,2.1 語(yǔ)言成分,1 字母表(符號(hào)表)與符號(hào) 元素(或稱符號(hào))的非空有窮集合,用符號(hào)Σ表示。 不同語(yǔ)言有不同的字母表。如漢語(yǔ)包括漢字、數(shù)字、標(biāo)點(diǎn)符號(hào)等;C語(yǔ)言包括字母、數(shù)字和保留字等等。,10,符號(hào)串的運(yùn)算(1/3),符號(hào)串的頭尾,固有頭和固有尾: 設(shè) z=xy 是一個(gè)符號(hào)串,則x是z的頭,y是z的尾。如果x是非空的,那么y是是固有尾;如果y是非空的,那么x是固有頭。,例:z=abc,則 z的頭:ε、a、ab、abc; 固有頭: ε、a、ab; z的尾:ε、c、bc、abc; 固有尾: ε、c、bc;,當(dāng)我們對(duì)符號(hào)z=xy 的頭感興趣而對(duì)其余部分不感興趣時(shí),我們可以采用省略寫法:z=x…。如果只是為了強(qiáng)調(diào)x在符號(hào)串中的某處出現(xiàn),則可表示為:z=…x…;符號(hào)t是符號(hào)串z的第一個(gè)符號(hào),則表示為:z=t…。,11,(3)符號(hào)串的連接,設(shè)x和y是符號(hào)串,它們的連接xy是把y的符號(hào)寫在x的符號(hào)之后得到的符號(hào)串。 例如:x=abc,y=DEF,則xy=abcDEF;,若| x | = n,| y |=m,則| xy | = n+m,對(duì)任意的符號(hào)串x,有ε x = x ε = x,12,(4) 符號(hào)串集合的乘積,設(shè)A、B是兩個(gè)符號(hào)串的集合,則AB表示A與B的乘積,定義為: AB={xy|x∈A,y∈B} 如:若A={ab,c}, B={d,efg},則AB={abd,abefg,cd,cefg} 特別地,有:{ε}A=A{ε}=A 空集φ 表示不含任何元素的空集{}。 有: φA=A φ= φ 請(qǐng)區(qū)別: ε,{},{ε}三種表示方法的含義,13,(5) 符號(hào)串的方冪,同一符號(hào)串的連接可以寫成方冪的形式。 設(shè)x是符號(hào)串,把x自身連接n次得到的符號(hào)串z,即z=xx…xx,稱為符號(hào)串x的方冪,記作z=xn,有: x0=ε x1= x x2= xx x3= xxx … 當(dāng)n0時(shí), xn =x xn-1 = xn-1 x,14,(6)符號(hào)串集合的方冪,同一符號(hào)串集合的連接也可以寫成方冪的形式。 設(shè)符號(hào)串集合為A,則有: A0={ε} A1= A A2= AA A3= AAA … 當(dāng)n0時(shí), An =A An-1 = An-1 A 例如:A={ab,c},則AA={ ……} AAA={ ……},15,(7)符號(hào)串集合的正閉包,設(shè)符號(hào)串集合為A,則A的正閉包記為A+ ,定義為: A+ = A1 ∪ A2∪… ∪ An 表示A上所有有窮長(zhǎng)串的集合 例如:A={ab,c},AA={ }, AAA={ },(8)符號(hào)串集合的自反閉包,設(shè)符號(hào)串集合為A,則A的自反閉包記為A* ,定義為: A* = A0 ∪ A1 ∪ A2∪… ∪ An 即A* = A0 ∪ A+ = {ε} ∪ A+ 例如: A= {a,b},則 A*={ε, a, b, aa, ab, ba, bb, aaa, …… },A+ = A* A = AA*,16,2.2 產(chǎn)生式文法和語(yǔ)言,2.2.1 文法的形式定義——是一個(gè)四元組 G =(VN,VT,P,S) VN —— 非終結(jié)符號(hào)集,非終結(jié)符號(hào)代表的是語(yǔ)法范疇,也就是它是一類(或集合)的記號(hào),而不是一個(gè)個(gè)體記號(hào)。如“表達(dá)式”、“語(yǔ)句”、“分程序”等等,都是表達(dá)一定的語(yǔ)法概念。因此,每個(gè)非終結(jié)符表示一定符號(hào)串的集合(由終結(jié)符和非終結(jié)符 組成);(如簡(jiǎn)單漢語(yǔ)句子中。。。),VT —— 終結(jié)符號(hào)集合,終結(jié)符是構(gòu)成語(yǔ)言的基本符號(hào),也就是說(shuō),它是一個(gè)語(yǔ)言的不可再分的基本符號(hào);,P ——產(chǎn)生式(或稱規(guī)則,重寫規(guī)則,生成式)集合。所謂產(chǎn)生式是定義語(yǔ)法范疇的一種書寫規(guī)則。一個(gè)產(chǎn)生式的形式是α→β (或α::= β ),其中 “→”讀為“是”或“定義為”; 產(chǎn)生式的左部 α∈ (VN∪VT )*且至少含有一個(gè)非終結(jié)符號(hào),右部β∈(VN∪VT)* ,即由終結(jié)符或(與)非終結(jié)符組成的一符號(hào)串,β允許是空字ε,17,2.2 產(chǎn)生式文法和語(yǔ)言,例如:簡(jiǎn)單的漢語(yǔ)句子的構(gòu)成規(guī)則 ::= ::= | ::= 我 | 你 | 他 ::=王明| 大學(xué)生|工人|英語(yǔ) ::= ::=是 |學(xué)習(xí) ::= | 則 “我是大學(xué)生”是句子,18,文法的形式定義,S ——開(kāi)始符號(hào),即文法的第一個(gè)非終結(jié)符。 開(kāi)始符號(hào)代表了所定義的語(yǔ)言中我們最感興趣的語(yǔ)法范疇,如在程序語(yǔ)言中,我們感興趣的是“程序”,注意: 1、 VN ∩ VT=φ 即不含公共元素 ; 2 、產(chǎn)生式是有限的; 3、開(kāi)始符號(hào)S至少必須在某個(gè)產(chǎn)生式的左部出現(xiàn)一次; 4、為書寫方便,若干個(gè)左部相同的產(chǎn)生式如: P→α1, P→α2,…,P→αn 合并成: P→α1|α2|…|αn 其中αi稱為P的一個(gè)候選式。,19,文法定義舉例1,例2.1 表示算術(shù)表達(dá)式的文法描述:G1 =(VN,VT,P,S) 其中VN={E} VT ={i , +,*, ( , ) } P={E→ i , E→ E + E , E→ E * E , E→ ( E ) } S=E 或者直接寫為: G1 =({E}, {i , +,*, ( , ) }, {E→ i , E→ E + E , E→ E * E , E→ ( E ) }, E ),20,文法定義舉例2,例2 文法G =(VN,VT,P,S) 其中VN={標(biāo)識(shí)符,字母,數(shù)字}, VT ={a, b, c, … , x, y, z, 0,1, …, 8, 9} P={ → | | , → a|b|c|…|x|y|z, → 0|1|2|…|8|9 } S = ,21,用文法定義語(yǔ)言的中心思想是:從文法的開(kāi)始符號(hào)出發(fā),反復(fù)連續(xù)使用產(chǎn)生式,對(duì)非終結(jié)符施行替換和展開(kāi)。 例如文法G:E→ E+E | E*E | ( E ) | i,其中唯一非終結(jié)符E可以看成是代表一類算術(shù)表達(dá)式。 從E出發(fā),進(jìn)行一系列的推導(dǎo),推出種種不同的算術(shù)表達(dá)式。如根據(jù)上述規(guī)則可推出 ( i+i ): E = ( E )= ( E+E )= ( i+E )= ( i+i) 我們稱這樣的一串替換是從E推出( i+i )的一個(gè)推導(dǎo),這個(gè)推導(dǎo)提供了一個(gè)證明,證明( i+i )是文法G所定義的一個(gè)算術(shù)表達(dá)式。,2.2.2 文法的推導(dǎo),22,有關(guān)推導(dǎo)的定義,,,,,定義2.3 直接推導(dǎo) = 若αAβ直接推導(dǎo)出 αγβ,即 αAβ=αγβ,當(dāng)且僅當(dāng)A-γ是一個(gè)產(chǎn)生式,且α、β∈(VN∪VT)* 符號(hào)‘ =’指推導(dǎo)一步,即推導(dǎo)每前進(jìn)一步總是引用一條規(guī)則(產(chǎn)生式),定義2.4 長(zhǎng)度為n(n≥1)的推導(dǎo) 若存在直接推導(dǎo)序列a1= a2= … =an,則稱a1可推導(dǎo)出an。 a1 an 表示:從a1出發(fā)經(jīng)過(guò)一步或若干步,可推導(dǎo)出an 。,,定義2.5 長(zhǎng)度為n(n≥0)的推導(dǎo) a1 an 表示:從a1出發(fā)經(jīng)過(guò)0步( a1 =an )或若干步,可推導(dǎo)出an 。,,,,23,2.2.3 句型、句子、語(yǔ)言,,,例1:證明終結(jié)符號(hào)串( i*i+i )是文法G:E→ E+E | E*E | (E)| i的一個(gè)句子 證明:∵ E =( E ) =(E+E)=(E*E+E) =(i*E+E) =(i*i+E)=(i*i+i) 是從開(kāi)始符號(hào)E到( i*i+i )的一個(gè)推導(dǎo)。 其中E、(E)、(E+E)、(E*E+E)、 (i*E+E) 、 (i*i+E) 、 (i*i+i)都是這個(gè)文法的一個(gè)句型,,1.句型:設(shè)G[S]是一個(gè)文法,S是它的開(kāi)始符號(hào),若S α ,則稱α是文法G[S]的句型。 2.句子:僅含終結(jié)符的句型是一個(gè)句子,即S α,α∈VT*, 則α是句子。 3.語(yǔ)言:文法G所產(chǎn)生的句子的全體是一個(gè)語(yǔ)言,記作L(G) L(G)={α|S α,且α∈VT*},24,語(yǔ)言的例子,例2:文法G2 [A ]:A→ bA | cc,證明cc、bcc、bbcc屬于L(G2)。 證明: A=cc, A= Ba=bcc, A =bA =bbA = bbcc ∴ cc、bcc、bbcc、……是屬于L(G2)的,,例3:文法G[S]: (1) S→0S1;(2) S→01。G[S]的語(yǔ)言是什么? 解:對(duì)第一個(gè)產(chǎn)生式使用n-1次,然后使用第二個(gè)產(chǎn)生式一次,得到: S = 0S1 = 00S11= …… = 0n-1S1n-1 = 0n1n 因此L(G)={0n1n|n ≥1},例4:下列文法的語(yǔ)言是什么? G[S]=({S}, {ε }, { S - ε }, S ) G[A]=({A}, {ε }, { },A ),25,2.2.4 文法的等價(jià),若L(G1) = L(G2),則稱文法G1和G2是等價(jià)的 例1:G1=(VN, VT, P, S), VN ={S}, VT ={0, 1},P由下列產(chǎn)生式組成: (1) S→0S1; (2) S→01; G2=(VN, VT, P, A), VN ={A, R}, VT ={0, 1},P由下列產(chǎn)生式組成: (1) A→ 0R ; (2) A→ 01; (3) R→ A1,26,什么是遞歸文法?,1.遞歸規(guī)則:規(guī)則右部有與左部相同的符號(hào) 對(duì)于 U - xUy 若x=ε,即U - Uy,左遞歸; 若y=ε,即U - xU,右遞歸;,2.遞歸文法:文法G,存在U ∈VN 若 U==…U…, 則G為遞歸文法; 若 U==U…, 則G為左遞歸文法; 若 U==…U, 則G為右遞歸文法;,27,4. 遞歸文法的優(yōu)點(diǎn):可用有窮條規(guī)則,定義無(wú)窮語(yǔ)言,例:對(duì)于前面給出的標(biāo)識(shí)符的文法是有遞歸文法,用y有限條規(guī)則就可以定義出所有的標(biāo)識(shí)符。若不用遞歸文法,那將要用多少條規(guī)則呢?,!,3. 左遞歸文法的缺點(diǎn):不能用自頂向下的方法來(lái)進(jìn)行語(yǔ) 分析,會(huì)造成死循環(huán),28,2.3 文法的分類,2.3.1 文法分類 喬姆斯基(Chomsky)建立的形式語(yǔ)言對(duì)計(jì)算機(jī)科學(xué)的發(fā)展具有深刻的意義。他把文法分成四種類型:0型、1型、2型和3型。0型強(qiáng)于1型,1型強(qiáng)于2型,2型強(qiáng)于3型,它們的差別在于對(duì)產(chǎn)生式施加不同的限制。,,29,定義 0型文法(或稱短語(yǔ)文法, phrase structure grammar,PSG),G=( VN, VT, P, S)是0型文法是指: 若它的每個(gè)產(chǎn)生式α→β是這樣一種結(jié)構(gòu): α∈(VN∪VT)+且至少含有一個(gè)非終結(jié)符, β∈(VN∪VT)*。 任何0型文法都是遞歸可枚舉的。 0型文法的能力相當(dāng)于圖靈機(jī)(計(jì)算機(jī)的一種簡(jiǎn)單的理論模型)。 稱L為遞歸可枚舉的:若存在一個(gè)產(chǎn)生L的過(guò)程。 稱L為遞歸的:若存在一個(gè)識(shí)別L的算法。,30,定義 1型文法(或稱上下文有關(guān)文法,CSG Context Sensitive Grammar),如果對(duì)0型文法加以以下的限制,則可得到1型文法。 設(shè)G=( VN, VT, P, S)為一文法,若G的任何產(chǎn)生式α→ β均滿足|α| ≤ |β| (指符號(hào)串的長(zhǎng)度),僅僅S→ ε例外。 課本P24例2.2。,例:設(shè)G=(VN, VT, P, S), VN ={S, B, E}, VT ={a, b, e},P由下列產(chǎn)生式組成: (1) S→ aSBE ; (2) S→ aBE ; (3) EB→ BE ; (4) aB→ ab ; (5) bB→ bb ; (6) bE→ be ; (7) eE→ ee ; 求 G[S]的語(yǔ)言是什么。,31,接上頁(yè)例子,,,分析:7條產(chǎn)生式中只有第1條具有遞歸性,其它的產(chǎn)生式最終都向終結(jié)符靠攏。 注意: S→ aSBE 與S→0S1的相似性,都可用同一模板來(lái)表示S→ □S□ ① 使用產(chǎn)生式(1) n-1次,得推導(dǎo)序列:S an-1S(BE)n-1; ②使用產(chǎn)生式(2) 一次,得到: S an(BE)n; ③使用產(chǎn)生式(3)的右部替換EB,使最終得到的串中,所有的B都先于所有的E,即S anBnEn;,32,接上例,④使用產(chǎn)生式(4)一次,得到S an bBn-1En; ⑤使用產(chǎn)生式(5) n-1次,得到S an bnEn; ⑥使用產(chǎn)生式(6) 一次,得到S an bn eEn-1; ⑦使用產(chǎn)生式(7) n-1次,得到S an bn en; 因此,L(G)={an bn en | n≥ 1},,說(shuō)明:上述分析中,步驟③是關(guān)鍵一步,否則不能推導(dǎo)出終結(jié)符號(hào)串。例如假設(shè)n=3,S aaaBEBEBE aaaBBEEBE aaabBEEBE aaabbEEBE aaabbeEBE aaabbeeBE,33,上下文有關(guān),顧名思義就是對(duì)非終結(jié)符進(jìn)行替換時(shí)必須考慮上下文。例如,1型文法G的產(chǎn)生式也可寫成αAβ→ αγβ,其中α、β、γ都在(VN∪VT)*中,且γ≠ ε,A∈ VN ,則說(shuō)明了非終結(jié)符A必須在α、β這樣一個(gè)上下文環(huán)境中才可以替換。 上下文有關(guān)文法能生成anbncn類特征的語(yǔ)言。但它不能描述L={αcα|α∈(a|b)*}類語(yǔ)言。,對(duì)上下文有關(guān)文法的說(shuō)明,34,定義 2型文法(或稱上下文無(wú)關(guān)文法,CFG Context Free Grammar),設(shè)G=( VN, VT, P, S)為一文法,若G的任何產(chǎn)生式形似A→ β,其中A ∈ VN, β ∈ (VN∪VT)+ 。,例:G=({S,A,B},{a,b},P,S),其中P由下列產(chǎn)生式組成 S→aB|bA A→a|aS|bAA B→b|bS|aBB 例:G=(VN, VT, P, S), VN ={S}, VT ={0, 1},P由下列產(chǎn)生式組成: (1) S→0S1; (2) S→01;,35,上下文無(wú)關(guān)文法的說(shuō)明,上下文無(wú)關(guān),顧名思義就是非終結(jié)符的替換可以不必考慮上下文。由于這種文法對(duì)程序已基本可以描述,因此,上下文無(wú)關(guān)文法常簡(jiǎn)稱為文法。 上下文無(wú)關(guān)文法最多能生成anbn類特征的語(yǔ)言,不能生成anbncn類特征的語(yǔ)言。,36,設(shè)G=( VN, VT, P, S)為一文法,若G的任何產(chǎn)生式A→ α或A→ α B ,其中A、B ∈ VN ,α ∈ VT* 。 對(duì)任何正規(guī)文法G,都可以設(shè)計(jì)一個(gè)不確定的有窮自動(dòng)機(jī)NFA,它能夠而且只能夠識(shí)別G的語(yǔ)言。,定義 3型文法(或稱正規(guī)文法,RG Regular Grammar),例:文法G=({S,A,B},{0,1},P,S),其中P由下列產(chǎn)生式組成 S →0A|1B|0 A →0A|1B|0S B →1B|1|0,37,左線性文法,設(shè)G=( VN, VT, P, S)為一文法,若G的任何產(chǎn)生式A→α或A→ Bα ,其中A、B ∈ VN ,α∈ VT* 。,左線性文法=右線性文法(非嚴(yán)格的轉(zhuǎn)換) 設(shè)左線性文法為G=( VN, VT, P, S),右線性文法為G’=( VN’, VT, P’, S’),其中 VN’= VN+{S’},P’轉(zhuǎn)化方式為:,38,2.3.2 文法分類的意義,自動(dòng)機(jī) 具有有窮描述的某種機(jī)器,對(duì)于給定文法,可接收某個(gè)終結(jié)符號(hào)串,并確定是否能從該文法推導(dǎo)出來(lái)。 分析器 判定(分析)一個(gè)終結(jié)符號(hào)串是否是某個(gè)文法的句子,給出給定串的推導(dǎo)序列,完成此工作的自動(dòng)機(jī),稱為分析器。 正規(guī)文法與自動(dòng)機(jī) 自動(dòng)機(jī)由一個(gè)有窮狀態(tài)集和一個(gè)狀態(tài)對(duì)偶之間的轉(zhuǎn)換集組成。 CFG與自動(dòng)機(jī) CFG可以由下推自動(dòng)機(jī)來(lái)識(shí)別。,,,,,39,文法分類的意義,文法的分類,對(duì)于實(shí)現(xiàn)程序設(shè)計(jì)語(yǔ)言的編譯程序, 具有重要意義。 語(yǔ)言的詞法規(guī)則:用正規(guī)文法(RG)描述。 語(yǔ)言的語(yǔ)法規(guī)則:局部語(yǔ)法用CFG描述; 全局語(yǔ)法用CSG描述。 語(yǔ)言的語(yǔ)義描述:CSG(實(shí)際定義采用CFG)。 編譯程序在實(shí)現(xiàn)時(shí),一般采用CFG識(shí)別技術(shù)(易實(shí)現(xiàn),高效)。,,,40,2.3.3 文法舉例,例2.6 1型文法G6 = ( VN, VT, P, S),其中 VN= { S,X,Y,Z} VT ={x, y, z } P= {S-xSYZ|xYZ, xY-xy, yY-yy, yZ-yz, ZY-YZ, zZ - zz} L(G6)為?,例2.7 2型文法G7 = ( VN, VT, P, S),其中 VN= { S,T} VT ={a, b, c, d } P= {S-aTd, T-bT | cT | b | c},L(G6) = {xnynzn | n0 },L(G7) = {aαd | α ∈ { b, c}+ },41,2.3.3 文法舉例(2),例2.8 2型文法G8 = ( VN, VT, P, B),其中 VN= { B} VT ={ ( , ) } P= { B - ( B ) | BB | ( ) },例2.9 2型文法G9 = ( VN, VT, P, S),其中 VN= { S } VT ={0 , 1 } P= {S-0S1 , S - 01},L(G8) = {(n )n (m )m… (k )k | n0, m=0, k=0 },L(G9) = {0n 1n | n0 },42,2.3.3 文法舉例(3),例2.10 所有以0開(kāi)頭,以零個(gè)或多個(gè)10組成的符號(hào)串的語(yǔ)言。 (1)右線性文法 G10 [S]:S - 0A A -10A | ε (2)左線性文法 G11 [S]:S - S10 | 0 (3)正規(guī)文法 G12 [S]:S - 0B | 0 B -1S,43,2.3.4 文法的構(gòu)造(補(bǔ)充),以{an}、{anbn}、{anbncn}、{ωωr|ω∈{0|1}*}的構(gòu)造為基礎(chǔ),以它們?yōu)橐罁?jù)來(lái)構(gòu)造其它文法。 給出下面語(yǔ)言相應(yīng)的文法 1、L1={abna | n≥ 0}; 2、L2={an bn+mcm | m,n≥ 1}; 3、L3={anbnci | n≥ 1,i ≥ 0}; 4、L4={aibncn | n≥ 1,i ≥ 0}; 5、L5={anbncn|n ≥ 1 },對(duì)文法的構(gòu)造的求解要多做練習(xí)。,44,文法的構(gòu)造的分析(補(bǔ)充),類型:①A →□A或A →A□對(duì)應(yīng)于{an| n≥ 1}類 ② A →□A◇對(duì)應(yīng)于{anbcn| n≥ 1}類 ③ 分步:先用A →□A◇對(duì)應(yīng)于{an(BC)n| n≥ 1},然后再通過(guò)改變排列順序,最終實(shí)現(xiàn) {anbncn| n≥ 1}類,45,文法構(gòu)造的方法(補(bǔ)充),①分析所用文法的類型 ②對(duì)照典型的幾種文法構(gòu)造方法,來(lái)指導(dǎo)構(gòu)造新的文法 ③利用模塊化設(shè)計(jì)思想來(lái)指導(dǎo)構(gòu)造過(guò)程 ④注意邊界問(wèn)題,46,文法的構(gòu)造舉例(1/3),1、L1={abna | n≥ 0}; 對(duì)應(yīng)模板: A →□A或A →A□ 劃分模塊:bn 2、L2={an bn+mcm | m,n≥ 1}; 對(duì)應(yīng)模板: A →□A ◇ 劃分模塊: □ ◇ ; □ 對(duì)應(yīng)an bn, ◇對(duì)應(yīng) bmcm,47,文法的構(gòu)造舉例(2/3),3、L3={anbnci | n≥ 1,i ≥ 0}; 對(duì)應(yīng)模板: A →□A或A →A□ A →□A ◇ 劃分模塊: □ ◇ ; □ 對(duì)應(yīng)an bn, ◇對(duì)應(yīng) ci 4、L4={aibncn | n≥ 1,i ≥ 0}; 同3,48,文法的構(gòu)造舉例(3/3),5、L5={anbncn|n ≥ 1 } 對(duì)應(yīng)模板: A →□A ◇ 劃分模塊: □ ◇ ; □ 對(duì)應(yīng)an bn, ◇對(duì)應(yīng) cn或 對(duì)應(yīng)an , ◇對(duì)應(yīng) bn cn,49,2.4 文法及其語(yǔ)法樹,文法和語(yǔ)言,一、語(yǔ)法樹(推導(dǎo)樹) 直觀定義:用圖表示上下文無(wú)關(guān)文法句型的推導(dǎo)的直觀方法。 語(yǔ)法樹有助于理解一個(gè)句子的語(yǔ)法層結(jié)構(gòu)的層次,語(yǔ)法樹通常表示 成一棵倒立的樹,根在上,枝葉在下。,2. 形式定義 對(duì)文法G=( VN, VT, P, S)相關(guān)聯(lián)的語(yǔ)法樹49滿足以下4個(gè)條件: (1)根結(jié)點(diǎn)由開(kāi)始符號(hào)S所標(biāo)記; (2)每個(gè)結(jié)點(diǎn)都有一個(gè)標(biāo)記,此標(biāo)記是V(即VN∪ VT)的一個(gè)符號(hào); (3) 若某結(jié)點(diǎn)至少有一個(gè)子孫結(jié)點(diǎn),則該結(jié)點(diǎn)所標(biāo)記的符號(hào)是個(gè)非終結(jié)符; (4)從左到右,若結(jié)點(diǎn)A1 , A2 ,… , Ak是結(jié)點(diǎn)A的孩子結(jié)點(diǎn),則存在產(chǎn)生式A→ A1 A2… Ak。,50,從根結(jié)點(diǎn)S開(kāi)始推導(dǎo),當(dāng)非終結(jié)符被它的某個(gè)候選式所替換時(shí),這個(gè)非終結(jié)符的相應(yīng)結(jié)點(diǎn)就產(chǎn)生出下一代新結(jié)點(diǎn),候選式中自左向右的每個(gè)符號(hào)對(duì)應(yīng)一個(gè)新結(jié)點(diǎn),并用這些符號(hào)標(biāo)記其相應(yīng)的新結(jié)點(diǎn)。每個(gè)新結(jié)點(diǎn)與其父結(jié)點(diǎn)間都有一條連線。在一棵語(yǔ)法樹生長(zhǎng)過(guò)程中的任何時(shí)刻,所有那些沒(méi)有后代的端末結(jié)自左向右排列起來(lái)就是一個(gè)句型。,語(yǔ)法樹構(gòu)造的過(guò)程,例1 文法G= ( {E}, {+, *, i , (, )}, P, E),其中P為: E→ E+E | E*E | (E) | i 對(duì)該文法關(guān)于(i*i+i)的推導(dǎo)的語(yǔ)法樹如下所示:,51,接語(yǔ)法樹構(gòu)造舉例,E(根),(,E,),E,+,+,E,E,*,E,,i,i,i,,,什么是樹的邊沿?,52,文法和語(yǔ)言,語(yǔ)法樹的問(wèn)題分析,(1)允許產(chǎn)生同名結(jié)點(diǎn)(反映遞歸性); (2)沒(méi)有后代的結(jié)點(diǎn)為端末結(jié); (3)語(yǔ)法樹不能反映產(chǎn)生后代的先后順序;(例子在下一頁(yè)) (4)一棵語(yǔ)法樹表示了一個(gè)句型種種可能的(但未必是所有的)不同推導(dǎo)過(guò)程。,53,語(yǔ)法樹例子,推導(dǎo)過(guò)程中施用產(chǎn)生式的順序,例: G[S]: S→aAS A→SbA A→SS S→a A→ba,S a A S S b A a a b a,,,,,,,,,,,S?aAS?aAa?aSbAa?aSbbaa?aabbaa S?aAS?aSbAS?aabAS?aabbaS?aabbaa S?aAS?aSbAS?aSbAa?aabAa?aabbaa,54,2.5 文法和語(yǔ)言的一些特性,文法和語(yǔ)言,2.5.1 無(wú)用非終結(jié)符號(hào),如果文法的某個(gè)非終結(jié)符不出現(xiàn)在文法的任何一個(gè)句型中,并且不能從它推導(dǎo)出終結(jié)符號(hào)串,則稱該非終結(jié)符為無(wú)用非終結(jié)符。,例2.13 設(shè)文法G13 [A]: A - aaBbb B - aBb | ab C -cD | c D -Ef 哪些符號(hào)是無(wú)用非終結(jié)符號(hào)?,無(wú)用非終結(jié)符號(hào):D E,對(duì)于文法G[S],為了保證任一非終結(jié)符A在句子推導(dǎo)中出現(xiàn),必須滿足如下兩個(gè)條件: 1)A必須在某句型中出現(xiàn)。 2)必須能從A推出終結(jié)符號(hào)串t來(lái)。,55,文法和語(yǔ)言,2.5.2 不可達(dá)文法符號(hào),如果一個(gè)非終結(jié)符不出現(xiàn)在文法的任何一條產(chǎn)生式的右部,則稱該非終結(jié)符為不可達(dá)文法符號(hào)。,例2.13 設(shè)文法G13 [A]: A - aaBbb B - aBb | ab C -cD | c D -Ef 哪些符號(hào)是不可達(dá)文法符號(hào)?,不可達(dá)文法符號(hào):C,56,文法和語(yǔ)言,多余符號(hào)和多余規(guī)則,無(wú)用非終結(jié)符和不可達(dá)文法符號(hào)都是多余符號(hào)。 包含有多余符號(hào)的規(guī)則(產(chǎn)生式),是多余規(guī)則。 形如 U - U 的產(chǎn)生式,也是多余規(guī)則。,例1 設(shè)文法G13 [A]: A - aaBbb | a B - aBb | aCb C -cD | C D -Ef 應(yīng)刪除哪些多余規(guī)則?,57,文法和語(yǔ)言,多余符號(hào)和多余規(guī)則,應(yīng)刪除哪些多余規(guī)則?,例2:G[S] 1) S→Be 2) B→Ce 3) B→Af 4) A→Ae 5) A→e 6) C→Cf 7) D→f,S→Be B→Af A→Ae A→e,58,文法和語(yǔ)言,2.5.3 可空非終結(jié)符,若存在產(chǎn)生式 A - ε ,則該產(chǎn)生式稱為空產(chǎn)生式,A稱為可空非終結(jié)符。 空產(chǎn)生式有時(shí)候帶來(lái)方便,所以,可以往一個(gè)文法里增加空產(chǎn)生式。,59,2.5.4 最左推導(dǎo)/最右推導(dǎo)/規(guī)范推導(dǎo),最左推導(dǎo):任何一步α= β都是對(duì)α中的最左非終結(jié)符進(jìn)行替換。 最右推導(dǎo)(又稱規(guī)范推導(dǎo)):任何一步α=β都是對(duì)α中的最右非終結(jié)符進(jìn)行替換。 由規(guī)范推導(dǎo)所得到的句型稱為規(guī)范句型。,從一個(gè)句型到另一個(gè)句型的推導(dǎo)過(guò)程往往是不唯一的。 例如 E+E (i+i): (a)E+E = E+i = i+i ——最右推導(dǎo) (b)E+E = i+E = i+i ——最左推導(dǎo),,,,,60,語(yǔ)法樹的特點(diǎn),文法和語(yǔ)言,一棵語(yǔ)法樹是這些不同推導(dǎo)過(guò)程的共性抽象,是它們的代表。一棵語(yǔ)法樹完全等價(jià)于一個(gè)最左(右)推導(dǎo),這種等價(jià)性包括樹的步步生長(zhǎng)和推導(dǎo)的步步展開(kāi)是完全一致的。 例:推導(dǎo)(i*i+i) 最左推導(dǎo):E =(E) =(E+E)=(E*E+E)=(i*E+E)=(i*i+E)= (i*i+i) 最右推導(dǎo):E=(E)=(E+E)=(E+i)=(E*E+i)=(E*i+i)=(i*i+i) 但兩種推導(dǎo)的語(yǔ)法樹相同。,61,文法和語(yǔ)言,一個(gè)句型是否只對(duì)應(yīng)唯一的一棵語(yǔ)法樹?,例:G[E]: E → i E → E+E E → E*E E → (E),句型 i*i+i 的兩個(gè)不同的最左推導(dǎo): 推導(dǎo)1:E ? E+E ? E*E+E ? i*E+E ? i*i+E ? i*i+i 推導(dǎo)2:E ? E*E ? i*E ? i*E+E ? i*i+E ?i*i+i,62,文法和語(yǔ)言,定義2.13 : 一個(gè)文法,如果它的一個(gè)句子對(duì)應(yīng)有兩棵或兩棵以上不同的語(yǔ)法樹,則這個(gè)文法是二義的。 或 一個(gè)文法的某個(gè)句子有兩個(gè)不同的最左(右)推導(dǎo),則這個(gè)文法是二義的。,2.5.5 二義性,區(qū)別 文法的二義性:存在兩個(gè)不同文法G(二義)、G’(無(wú)二義),卻有L(G)=L(G’),即產(chǎn)生語(yǔ)言相同。 語(yǔ)言的二義性:若不存在無(wú)二義性的文法,則該語(yǔ)言是二義性的。,63,二義性其它問(wèn)題,文法和語(yǔ)言,人們已證明,二義性問(wèn)題是不可判定的,即不存在一個(gè)算法,它能在有限步驟內(nèi),確切地判斷一個(gè)文法是否是二義的。我們所能做的就是為無(wú)二義性尋找一些充分條件。 例如對(duì)文法G[E]: E→ E+E | E*E | (E) | i 修改,規(guī)定運(yùn)算符“+”與“*”的優(yōu)先關(guān)系和結(jié)合規(guī)則,設(shè)“*”的優(yōu)先性高于“+”,且服從左結(jié)合。 G’: E→ T | E+T T→ F | T*F F→ (E) | i,64,文法和語(yǔ)言,2.6 分析方法簡(jiǎn)介,句型分析的任務(wù)就是按文法的產(chǎn)生式,識(shí)別輸入的符號(hào)是否是該文法的句型。語(yǔ)法樹——是句型推導(dǎo)過(guò)程的幾何表示,可以十分直觀的顯示某句型的結(jié)構(gòu)。因此在句型時(shí),對(duì)輸入符號(hào)串構(gòu)造語(yǔ)法樹,以此識(shí)別它是否是該文法的一個(gè)句型(或句子)。因此,語(yǔ)法樹又可稱為語(yǔ)法分析樹或分析樹。我們把完成句型分析的程序稱為分析程序或識(shí)別程序,分析算法又稱識(shí)別算法。 分析算法又分為:,,從左到右分析算法; 從右到左分析算法;,,,自上而下的分析法 自下而上的分析法,65,文法和語(yǔ)言,自上而下的分析法,基本思想:從文法的開(kāi)始符號(hào)出發(fā),反復(fù)使用各種產(chǎn)生式,尋找“匹配”輸入符號(hào)串的推導(dǎo)。即對(duì)任何輸入符號(hào)串,從文法的開(kāi)始符號(hào)(根結(jié))出發(fā),自上而下地為輸入串建立一棵語(yǔ)法樹,直到語(yǔ)法樹結(jié)果正好是輸入的符號(hào)串為止。,例如:文法G[S]: S→ xAy A→ aa | a,識(shí)別輸入串xay是否是該文法的一個(gè)句子。,66,文法和語(yǔ)言,自上而下分析法的缺陷,關(guān)鍵:回溯問(wèn)題(∵ 其分析過(guò)程是一種試探過(guò)程) 回溯問(wèn)題是從各種可能的候選式中任選一個(gè),進(jìn)行推導(dǎo)后發(fā)現(xiàn)該候選式是錯(cuò)誤的,則退回去重新選擇候選式的方式。例如上例中的(3)。,S,,,,S,S,x,A,y,(3) —選用第1個(gè)候選式,,a,回溯的產(chǎn)生使算法代價(jià)極低,效率很低。關(guān)于解決回溯問(wèn)題將在第5章中介紹。,,a,67,自下而上的分析法,文法和語(yǔ)言,基本思想:從輸入串開(kāi)始,逐步進(jìn)行“歸約”,直至歸約到文法的開(kāi)始符號(hào)。即從語(yǔ)法樹的末端開(kāi)始,步步向上“歸約”,直到根結(jié)。 歸約:若V= γαδ,W=γβδ,α → β是文法的產(chǎn)生式,如有V=W,則W直接歸約到V。,68,自下而上的語(yǔ)法分析舉例,例1:文法G:S → cAd A → ab A → a 識(shí)別輸入串w=cabd是否該文法的句子,S A A c a b d c a b d c a b d 規(guī)約過(guò)程:S ? cAd ? cabd,,,,,,,,69,文法和語(yǔ)言,例2: 文法G[S]: (1)S→ aAcBe (2) A→ b (3)A→ Ab (4) B→ d 識(shí)別abbcde是否為文法S的一個(gè)句子。,解題思想:掃描abbcde,從中找出一個(gè)子串,該子串與某一產(chǎn)生式的右部相匹配。,70,自下而上分析法舉例,文法和語(yǔ)言,例2解:,71,自下而上分析法存在的問(wèn)題,文法和語(yǔ)言,可歸約串的問(wèn)題;(∵ 該分析的每一步就是從當(dāng)前串中找一個(gè)子串(稱“可歸約串”),將它歸約到某個(gè)非終結(jié)符號(hào)) 自下而上分析法的關(guān)鍵就是找哪個(gè)子串是“可歸約串”,哪個(gè)不是“可歸約串”。例如上例中的(3),因此必須精確定義“可歸約串”,事實(shí)上存在著種種不同的方法刻畫“可歸約串”,對(duì)這個(gè)概念的不同定義,形成了不同的自下而上的分析法。在“規(guī)范歸約”的分析中,用“句柄”來(lái)刻畫“可歸約串”。,72,短語(yǔ)、直接短語(yǔ)、句柄,文法和語(yǔ)言,,,1、短語(yǔ): 令文法G,開(kāi)始符號(hào)為S,αβδ是G的句型(即S αβδ),如果S αAδ且A β,則稱β是句型αβδ相對(duì)于非終結(jié)符A的短語(yǔ)。 2、直接短語(yǔ) 如短語(yǔ)中有A=β,則稱β是句型相對(duì)于規(guī)則A→ β的直接短語(yǔ)。 3、句柄 一個(gè)句型的最左直接短語(yǔ)稱為該句型的句柄。,73,解題方法,文法和語(yǔ)言,,例:文法G[E]: E→ T | E+T T→ F | T*F F→ (E) | i 證明i+i*i是G的一個(gè)句型,并指出這個(gè)句型的所有短語(yǔ)、直接短語(yǔ)、句柄。,證明:E E+T E+T*F E+T*i E+F*i E+i*i T+i*i F+i*i i+i*i,74,接上例,文法和語(yǔ)言,語(yǔ)法樹:,E,,,,E,+,T,,T,,,,T,*,F,,F,,F,,i3,,i1,,i2,第1層 i1+i2*i3 —相對(duì)于E 第2層 i1 —相對(duì)于E ; i2*i3 —相對(duì)于T 第3層 i1 ,i2 —相對(duì)于T; i3 —相對(duì)于F 第4層 i1 ,i2 —相對(duì)于F(F→ i直接短語(yǔ)) 第5層,∴ i+i*i是G的一個(gè)句型,其中i1 , i2 , i3, i2*i3 , i1+i2*i3 都是句型i1+i2*i3 的短語(yǔ),且i1 , i2 , i3 為直接短語(yǔ), i1為句柄,75,分析說(shuō)明,文法和語(yǔ)言,(2)作為“短語(yǔ)”的兩個(gè)條件是不可缺少的,僅僅有A β,未必意味著β就是句型αβδ的一個(gè)短語(yǔ),因?yàn)檫€需要有S αβδ這個(gè)條件。,,例如:上例中有E i1+i2,但i1+i2并不是該句型的一個(gè)短語(yǔ),因?yàn)椴淮嬖趶腅(開(kāi)始符號(hào))到E* i3的推導(dǎo)。,(1)短語(yǔ)、直接短語(yǔ)、句柄是針對(duì)某一句型(S α )而言的;,76,解題方法,⒈先證明前提 ⒉給出語(yǔ)法樹(注意文法是否是二義性的) 如題文法G[E]: E→ E+E|E*E|(E) | i 證明i+i*i是G的一個(gè)句型,并指出這個(gè)句型的所有短語(yǔ)、直接短語(yǔ)、句柄。 ⒊根據(jù)每顆語(yǔ)法樹得出短語(yǔ)、直接短語(yǔ)、句柄 (注意編號(hào)),77,練習(xí)1題目,文法G[T]: T→ F | T*F F →F ↑ P | P P→ (T) | i 證明T*P ↑(T*F)是文法G的一個(gè)句型,并指出這個(gè)句型的所有短語(yǔ)、直接短語(yǔ)、句柄。,78,練習(xí)1解答,證明:T T*F T*F↑P T*F↑(T) T*F↑(T*F) T*P↑(T*F),語(yǔ)法樹:,T,,,,T,*,F,,,,F,↑,P,,P,,T,,,(,),,,,T,*,F,第1層 T*P↑(T*F) —相對(duì)于T 第2層 P↑(T*F) —相對(duì)于F; 第3層 P —相對(duì)于F; (T*F) —相對(duì)于P 第4層 T*F —相對(duì)于T 第5層,∴ T*P↑(T*F)是G的一個(gè)句型,其中T*F , P , (T*F), P↑(T*F), T*P↑(T*F) 都是該句型的短語(yǔ),且T*F , P 為直接短語(yǔ), P為句柄,79,練習(xí)2題目,文法和語(yǔ)言,設(shè)有文法G[S]: S →V1 V1→ V2 | V1iV2 V2→ V3 | V2+V3 V3→ )V1* | ( (1)給出 (+(i( 的最右推導(dǎo),并畫出相應(yīng)的語(yǔ)法樹; (2)證明V2+V3i( 是文法的一個(gè)句型,并指出這個(gè)句型的短語(yǔ)、直接短語(yǔ)、句柄。,80,練習(xí)2解答(1/2),文法和語(yǔ)言,(1)解:S V1 V1iV2 V1iV3 V1i( V2i( V2+V3i( V2+(i( V3+(i( (+(i(,語(yǔ)法樹:,V1,,,,V1,i,V2,,,,(,S,,,V2,,,V2,+,V3,V3,,,V3,,(,(,,81,練習(xí)2解答(2/2),文法和語(yǔ)言,(2)證明: S V1 V1iV2 V1iV3 V1i( V2i( V2+V3i( ∴ V2+V3i(是文法的一個(gè)句型 短語(yǔ):V2+V3 , (, V2+V3i( 直接短語(yǔ): V2+V3 , ( 句柄: V2+V3,82,3.7 有關(guān)文法實(shí)用中的一些說(shuō)明(1/2),作為描述程序語(yǔ)言的上下文無(wú)關(guān)文法,我們對(duì)它有幾點(diǎn)小小的限制,在實(shí)用中,主要是在文法中不得含有有害規(guī)則和多余規(guī)則。 1、不含有害規(guī)則 有害規(guī)則是指形如P→P的產(chǎn)生式,因?yàn)檫@樣的產(chǎn)生式除了引起二義外,沒(méi)有任何用處。 2、不含多余規(guī)則 (1)不可到達(dá)的 即文法中的某些非終結(jié)符不在任何規(guī)則的右部出現(xiàn),則任何句子推導(dǎo)不可能用到它。也就是說(shuō) 對(duì)非終結(jié)符P,不存在S αPβ, α,β∈ (VN∪VT)*,,83,有關(guān)文法實(shí)用中的一些說(shuō)明(2/2),文法和語(yǔ)言,(2) 不可終止的 即文法中的某些非終結(jié)符不能夠從它推出終結(jié)符串。也就是說(shuō) 對(duì)非終結(jié)符P,不存在P t, t∈ VT* 若文法均滿足以上兩個(gè)條件,則稱這個(gè)文法為簡(jiǎn)化了的文法。,,84,本章課后練習(xí),習(xí)題二 P45: 2、5、6、7,- 1.請(qǐng)仔細(xì)閱讀文檔,確保文檔完整性,對(duì)于不預(yù)覽、不比對(duì)內(nèi)容而直接下載帶來(lái)的問(wèn)題本站不予受理。
- 2.下載的文檔,不會(huì)出現(xiàn)我們的網(wǎng)址水印。
- 3、該文檔所得收入(下載+內(nèi)容+預(yù)覽)歸上傳者、原創(chuàng)作者;如果您是本文檔原作者,請(qǐng)點(diǎn)此認(rèn)領(lǐng)!既往收益都?xì)w您。
下載文檔到電腦,查找使用更方便
14.9 積分
下載 |
- 配套講稿:
如PPT文件的首頁(yè)顯示word圖標(biāo),表示該P(yáng)PT已包含配套word講稿。雙擊word圖標(biāo)可打開(kāi)word文檔。
- 特殊限制:
部分文檔作品中含有的國(guó)旗、國(guó)徽等圖片,僅作為作品整體效果示例展示,禁止商用。設(shè)計(jì)者僅對(duì)作品中獨(dú)創(chuàng)性部分享有著作權(quán)。
- 關(guān) 鍵 詞:
- 編譯 原理 及其 習(xí)題 解答 武漢 大學(xué)出版社 課件
鏈接地址:http://appdesigncorp.com/p-2561855.html