編譯原理及其習(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 ——開始符號(hào)，即文法的第一個(gè)非終結(jié)符。 開始符號(hào)代表了所定義的語(yǔ)言中我們最感興趣的語(yǔ)法范疇，如在程序語(yǔ)言中，我們感興趣的是“程序”,注意： 1、 VN ∩ VT＝φ 即不含公共元素 ； 2 、產(chǎn)生式是有限的； 3、開始符號(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ǔ)言的中心思想是：從文法的開始符號(hào)出發(fā)，反復(fù)連續(xù)使用產(chǎn)生式，對(duì)非終結(jié)符施行替換和展開。 例如文法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) 是從開始符號(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是它的開始符號(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è)例子,,,分析：７條產(chǎn)生式中只有第１條具有遞歸性，其它的產(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開頭，以零個(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}； 同３,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)由開始符號(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開始推導(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)的步步展開是完全一致的。 例：推導(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ǔ)言,自上而下的分析法,基本思想：從文法的開始符號(hào)出發(fā)，反復(fù)使用各種產(chǎn)生式，尋找“匹配”輸入符號(hào)串的推導(dǎo)。即對(duì)任何輸入符號(hào)串，從文法的開始符號(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ǔ)言,基本思想：從輸入串開始，逐步進(jìn)行“歸約”，直至歸約到文法的開始符號(hào)。即從語(yǔ)法樹的末端開始，步步向上“歸約”，直到根結(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，開始符號(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)椴淮嬖趶腅（開始符號(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í)１解答,證明：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í)２解答（１／２）,文法和語(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í)２解答（２／２）,文法和語(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,