編譯原理及其習(xí)題解答武漢大學(xué)出版社課件.ppt

《編譯原理及其習(xí)題解答武漢大學(xué)出版社課件.ppt》由會員分享，可在線閱讀，更多相關(guān)《編譯原理及其習(xí)題解答武漢大學(xué)出版社課件.ppt（84頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1,第二章 文法和語言,要點(diǎn)(本章是基礎(chǔ)) 1、概念:文法,推導(dǎo),直接推導(dǎo),最左(右)推導(dǎo),產(chǎn)生式,句型,短語,直接短語,句柄,語法樹,規(guī)范推導(dǎo),二義文法等 2、4種文法的定義、文法的構(gòu)造和文法的推導(dǎo) 3、語法樹的構(gòu)造和最左（右）推導(dǎo)； 4、二義文法、二義性的證明； 5、句型分析；,2,詞法規(guī)則：自動機(jī) 語法規(guī)則：上下文無關(guān)文法,3,引言,語言包括語法和語義兩方面。 語法是一組規(guī)則，用以判斷什么樣的符號序列是合法的； 語義指含義，如變量的類型、作用域是否符合正確的語法。常把程序設(shè)計語言的語義分為二類：靜態(tài)語義和動態(tài)語義。靜態(tài)語義是一系列限定規(guī)則，并確定哪些合乎語法的程序是合適的；動態(tài)語義（或稱運(yùn)行語義、執(zhí)行語義），表明程序要做些什么，要計算什么。 闡明語法的一個工具是文法，常采用上下文無關(guān)文法作為程序設(shè)計語言語法的描述工具。,4,補(bǔ)充： 文法的直觀概念(1/5),描述一種語言，無非是說明這種語言的句子。如果該語言所含的句子是有限的，那么只要一一列舉出即可；若是無限的，則存在如何給出有窮表示的問題。但無論如何，某語言的句子總是存在著一種組成結(jié)構(gòu)，即所謂的規(guī)則（或稱文法）。 文法：描述語言的語法結(jié)構(gòu)的形式規(guī)則（即語法規(guī)則）。,5,直觀文法舉例(2/5),例如：簡單的漢語句子的構(gòu)成規(guī)則 ::= ::= | ::= 我 | 你 | 他 ::=王明| 大學(xué)生|工人|英語 ::= ::=是 |學(xué)習(xí) ::= | 則 “我是大學(xué)生”是句子,6,“我是大學(xué)生”的推導(dǎo)過程： 我 我 我是 我是 我是大學(xué)生 依次可以推導(dǎo)出句子“王明是大學(xué)生”、“我學(xué)習(xí)英語”等等,推導(dǎo)過程(3/5),7,程序設(shè)計語言對文法的要求(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ī)則把語言的全部句子描述出來，以有窮集合刻劃無窮集合。,9,2 符號串及其運(yùn)算 （1）符號串：由字母表中的符號組成的任何有窮序列。 說明: 字母間的順序 不同順序組成的符號串是不同的； （2）符號串長度 符號串內(nèi)所含符號的個數(shù)，若x=string,則|x|=6; 其中不含任何符號的符號串稱為空符號串ε，長度| ε |＝0,2.1 語言成分,1 字母表（符號表）與符號 元素（或稱符號）的非空有窮集合，用符號Σ表示。 不同語言有不同的字母表。如漢語包括漢字、數(shù)字、標(biāo)點(diǎn)符號等；C語言包括字母、數(shù)字和保留字等等。,10,符號串的運(yùn)算(1/3),符號串的頭尾，固有頭和固有尾： 設(shè) z=xy 是一個符號串，則x是z的頭，y是z的尾。如果x是非空的，那么y是是固有尾；如果y是非空的，那么x是固有頭。,例：z=abc，則 z的頭：ε、a、ab、abc； 固有頭： ε、a、ab； z的尾：ε、c、bc、abc； 固有尾： ε、c、bc；,當(dāng)我們對符號z=xy 的頭感興趣而對其余部分不感興趣時，我們可以采用省略寫法：z=x…。如果只是為了強(qiáng)調(diào)x在符號串中的某處出現(xiàn)，則可表示為：z=…x…；符號t是符號串z的第一個符號，則表示為：z=t…。,11,(3)符號串的連接,設(shè)x和y是符號串，它們的連接xy是把y的符號寫在x的符號之后得到的符號串。 例如：x=abc，y=DEF，則xy=abcDEF；,若| x | = n，| y |＝m，則| xy | = n+m,對任意的符號串x，有ε x = x ε = x,12,（4） 符號串集合的乘積,設(shè)A、B是兩個符號串的集合，則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ū)別： ε，{}，{ε}三種表示方法的含義,13,（5） 符號串的方冪,同一符號串的連接可以寫成方冪的形式。 設(shè)x是符號串，把x自身連接n次得到的符號串z，即z=xx…xx，稱為符號串x的方冪，記作z=xn，有： x0=ε x1= x x2= xx x3= xxx … 當(dāng)n0時， xn ＝x xn-1 = xn-1 x,14,（6）符號串集合的方冪,同一符號串集合的連接也可以寫成方冪的形式。 設(shè)符號串集合為A，則有： A0={ε} A1= A A2= AA A3= AAA … 當(dāng)n0時， An ＝A An-1 = An-1 A 例如：A={ab，c}，則AA={ ……} AAA={ ……},15,（7）符號串集合的正閉包,設(shè)符號串集合為A，則A的正閉包記為A+ ，定義為： A+ = A1 ∪ A2∪… ∪ An 表示A上所有有窮長串的集合 例如：A={ab，c}，AA={ }， AAA={ },（8）符號串集合的自反閉包,設(shè)符號串集合為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)生式文法和語言,2.2.1 文法的形式定義——是一個四元組 G =（VN，VT，P，S） VN —— 非終結(jié)符號集，非終結(jié)符號代表的是語法范疇，也就是它是一類（或集合）的記號，而不是一個個體記號。如“表達(dá)式”、“語句”、“分程序”等等，都是表達(dá)一定的語法概念。因此，每個非終結(jié)符表示一定符號串的集合（由終結(jié)符和非終結(jié)符 組成）；(如簡單漢語句子中。。。）,VT —— 終結(jié)符號集合，終結(jié)符是構(gòu)成語言的基本符號，也就是說，它是一個語言的不可再分的基本符號；,P ——產(chǎn)生式（或稱規(guī)則,重寫規(guī)則,生成式）集合。所謂產(chǎn)生式是定義語法范疇的一種書寫規(guī)則。一個產(chǎn)生式的形式是α→β （或α::= β )，其中 “→”讀為“是”或“定義為”； 產(chǎn)生式的左部 α∈ (VN∪VT )*且至少含有一個非終結(jié)符號，右部β∈(VN∪VT)* ,即由終結(jié)符或（與）非終結(jié)符組成的一符號串，β允許是空字ε,17,2.2 產(chǎn)生式文法和語言,例如：簡單的漢語句子的構(gòu)成規(guī)則 ::= ::= | ::= 我 | 你 | 他 ::=王明| 大學(xué)生|工人|英語 ::= ::=是 |學(xué)習(xí) ::= | 則 “我是大學(xué)生”是句子,18,文法的形式定義,S ——開始符號，即文法的第一個非終結(jié)符。 開始符號代表了所定義的語言中我們最感興趣的語法范疇，如在程序語言中，我們感興趣的是“程序”,注意： 1、 VN ∩ VT＝φ 即不含公共元素 ； 2 、產(chǎn)生式是有限的； 3、開始符號S至少必須在某個產(chǎn)生式的左部出現(xiàn)一次； 4、為書寫方便，若干個左部相同的產(chǎn)生式如： P→α1, P→α2，…，P→αn 合并成： P→α1|α2|…|αn 其中αi稱為P的一個候選式。,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ù)字}， 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,用文法定義語言的中心思想是：從文法的開始符號出發(fā)，反復(fù)連續(xù)使用產(chǎn)生式，對非終結(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 )的一個推導(dǎo)，這個推導(dǎo)提供了一個證明，證明( i+i )是文法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-γ是一個產(chǎn)生式，且α、β∈(VN∪VT)* 符號‘ =’指推導(dǎo)一步，即推導(dǎo)每前進(jìn)一步總是引用一條規(guī)則（產(chǎn)生式）,定義2.4 長度為n（n≥1）的推導(dǎo) 若存在直接推導(dǎo)序列a1= a2= … =an，則稱a1可推導(dǎo)出an。 a1 an 表示：從a1出發(fā)經(jīng)過一步或若干步，可推導(dǎo)出an 。,,定義2.5 長度為n（n≥0）的推導(dǎo) a1 an 表示：從a1出發(fā)經(jīng)過0步（ a1 ＝an ）或若干步，可推導(dǎo)出an 。,,,,23,2.2.3 句型、句子、語言,,,例1：證明終結(jié)符號串( i*i+i )是文法G：E→ E+E | E*E | (E)| i的一個句子 證明：∵ E =( E ) =(E+E)=(E*E+E) =(i*E+E) =(i*i+E)=(i*i+i) 是從開始符號E到( i*i+i )的一個推導(dǎo)。 其中E、(E)、(E+E)、(E*E+E)、 (i*E+E) 、 (i*i+E) 、 (i*i+i)都是這個文法的一個句型,,1.句型：設(shè)G[S]是一個文法，S是它的開始符號，若S α ,則稱α是文法G[S]的句型。 2.句子：僅含終結(jié)符的句型是一個句子，即S α，α∈VT*, 則α是句子。 3.語言：文法G所產(chǎn)生的句子的全體是一個語言，記作L(G) L(G)={α|S α,且α∈VT*},24,語言的例子,例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]的語言是什么？ 解：對第一個產(chǎn)生式使用n-1次，然后使用第二個產(chǎn)生式一次，得到： S = 0S1 = 00S11= …… = 0n-1S1n-1 = 0n1n 因此L(G)={0n1n|n ≥1},例4：下列文法的語言是什么？ G[S]=（{S}, {ε }, { S - ε }, S ） G[A]=（{A}， {ε }， { }，A ）,25,2.2.4 文法的等價,若L(G1) = L(G2)，則稱文法G1和G2是等價的 例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ī)則右部有與左部相同的符號 對于 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ī)則，定義無窮語言,例：對于前面給出的標(biāo)識符的文法是有遞歸文法，用y有限條規(guī)則就可以定義出所有的標(biāo)識符。若不用遞歸文法，那將要用多少條規(guī)則呢？,!,3. 左遞歸文法的缺點(diǎn)：不能用自頂向下的方法來進(jìn)行語 分析,會造成死循環(huán),28,2.3 文法的分類,2.3.1 文法分類 喬姆斯基（Chomsky)建立的形式語言對計算機(jī)科學(xué)的發(fā)展具有深刻的意義。他把文法分成四種類型：0型、1型、2型和3型。0型強(qiáng)于1型，1型強(qiáng)于2型，2型強(qiáng)于3型，它們的差別在于對產(chǎn)生式施加不同的限制。,,29,定義 0型文法（或稱短語文法, phrase structure grammar,PSG）,G=( VN, VT, P, S)是0型文法是指： 若它的每個產(chǎn)生式α→β是這樣一種結(jié)構(gòu): α∈(VN∪VT)+且至少含有一個非終結(jié)符， β∈(VN∪VT)*。 任何0型文法都是遞歸可枚舉的。 0型文法的能力相當(dāng)于圖靈機(jī)（計算機(jī)的一種簡單的理論模型）。 稱L為遞歸可枚舉的：若存在一個產(chǎn)生L的過程。 稱L為遞歸的：若存在一個識別L的算法。,30,定義 1型文法（或稱上下文有關(guān)文法,CSG Context Sensitive Grammar）,如果對0型文法加以以下的限制，則可得到1型文法。 設(shè)G=( VN, VT, P, S)為一文法，若G的任何產(chǎn)生式α→ β均滿足|α| ≤ |β| (指符號串的長度)，僅僅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]的語言是什么。,31,接上頁例子,,,分析：７條產(chǎn)生式中只有第１條具有遞歸性，其它的產(chǎn)生式最終都向終結(jié)符靠攏。 注意： S→ aSBE 與S→0S1的相似性，都可用同一模板來表示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},,說明：上述分析中，步驟③是關(guān)鍵一步，否則不能推導(dǎo)出終結(jié)符號串。例如假設(shè)n=3，S aaaBEBEBE aaaBBEEBE aaabBEEBE aaabbEEBE aaabbeEBE aaabbeeBE,33,上下文有關(guān)，顧名思義就是對非終結(jié)符進(jìn)行替換時必須考慮上下文。例如，1型文法G的產(chǎn)生式也可寫成αAβ→ αγβ，其中α、β、γ都在(VN∪VT)*中，且γ≠ ε，A∈ VN ，則說明了非終結(jié)符A必須在α、β這樣一個上下文環(huán)境中才可以替換。 上下文有關(guān)文法能生成anbncn類特征的語言。但它不能描述L={αcα|α∈(a|b)*}類語言。,對上下文有關(guān)文法的說明,34,定義 2型文法（或稱上下文無關(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,上下文無關(guān)文法的說明,上下文無關(guān)，顧名思義就是非終結(jié)符的替換可以不必考慮上下文。由于這種文法對程序已基本可以描述，因此，上下文無關(guān)文法常簡稱為文法。 上下文無關(guān)文法最多能生成anbn類特征的語言，不能生成anbncn類特征的語言。,36,設(shè)G=( VN, VT, P, S)為一文法，若G的任何產(chǎn)生式A→ α或A→ α B ，其中A、B ∈ VN ，α ∈ VT* 。 對任何正規(guī)文法G，都可以設(shè)計一個不確定的有窮自動機(jī)NFA，它能夠而且只能夠識別G的語言。,定義 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 文法分類的意義,自動機(jī) 具有有窮描述的某種機(jī)器，對于給定文法，可接收某個終結(jié)符號串，并確定是否能從該文法推導(dǎo)出來。 分析器 判定（分析）一個終結(jié)符號串是否是某個文法的句子，給出給定串的推導(dǎo)序列，完成此工作的自動機(jī)，稱為分析器。 正規(guī)文法與自動機(jī) 自動機(jī)由一個有窮狀態(tài)集和一個狀態(tài)對偶之間的轉(zhuǎn)換集組成。 CFG與自動機(jī) CFG可以由下推自動機(jī)來識別。,,,,,39,文法分類的意義,文法的分類，對于實(shí)現(xiàn)程序設(shè)計語言的編譯程序， 具有重要意義。 語言的詞法規(guī)則：用正規(guī)文法（RG）描述。 語言的語法規(guī)則：局部語法用CFG描述； 全局語法用CSG描述。 語言的語義描述：CSG（實(shí)際定義采用CFG）。 編譯程序在實(shí)現(xiàn)時，一般采用CFG識別技術(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開頭，以零個或多個10組成的符號串的語言。 （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ù)來構(gòu)造其它文法。 給出下面語言相應(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 },對文法的構(gòu)造的求解要多做練習(xí)。,44,文法的構(gòu)造的分析（補(bǔ)充）,類型：①A →□A或A →A□對應(yīng)于{an| n≥ 1}類 ② A →□A◇對應(yīng)于{anbcn| n≥ 1}類 ③ 分步：先用A →□A◇對應(yīng)于{an(BC)n| n≥ 1}，然后再通過改變排列順序，最終實(shí)現(xiàn) {anbncn| n≥ 1}類,45,文法構(gòu)造的方法（補(bǔ)充）,①分析所用文法的類型 ②對照典型的幾種文法構(gòu)造方法，來指導(dǎo)構(gòu)造新的文法 ③利用模塊化設(shè)計思想來指導(dǎo)構(gòu)造過程 ④注意邊界問題,46,文法的構(gòu)造舉例(1/3),1、L1={abna | n≥ 0}； 對應(yīng)模板： A →□A或A →A□ 劃分模塊：bn 2、L2={an bn+mcm | m,n≥ 1}； 對應(yīng)模板： A →□A ◇ 劃分模塊： □ ◇ ； □ 對應(yīng)an bn， ◇對應(yīng) bmcm,47,文法的構(gòu)造舉例（2/3）,3、L3={anbnci | n≥ 1，i ≥ 0}； 對應(yīng)模板： A →□A或A →A□ A →□A ◇ 劃分模塊： □ ◇ ； □ 對應(yīng)an bn， ◇對應(yīng) ci 4、L4={aibncn | n≥ 1，i ≥ 0}； 同３,48,文法的構(gòu)造舉例（3/3）,5、L5={anbncn|n ≥ 1 } 對應(yīng)模板： A →□A ◇ 劃分模塊： □ ◇ ； □ 對應(yīng)an bn， ◇對應(yīng) cn或 對應(yīng)an ， ◇對應(yīng) bn cn,49,2.4 文法及其語法樹,文法和語言,一、語法樹（推導(dǎo)樹） 直觀定義：用圖表示上下文無關(guān)文法句型的推導(dǎo)的直觀方法。 語法樹有助于理解一個句子的語法層結(jié)構(gòu)的層次，語法樹通常表示 成一棵倒立的樹，根在上，枝葉在下。,2. 形式定義 對文法G=( VN, VT, P, S)相關(guān)聯(lián)的語法樹49滿足以下4個條件： （1）根結(jié)點(diǎn)由開始符號S所標(biāo)記； （2）每個結(jié)點(diǎn)都有一個標(biāo)記，此標(biāo)記是V(即VN∪ VT)的一個符號； （3） 若某結(jié)點(diǎn)至少有一個子孫結(jié)點(diǎn)，則該結(jié)點(diǎn)所標(biāo)記的符號是個非終結(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é)符被它的某個候選式所替換時，這個非終結(jié)符的相應(yīng)結(jié)點(diǎn)就產(chǎn)生出下一代新結(jié)點(diǎn)，候選式中自左向右的每個符號對應(yīng)一個新結(jié)點(diǎn)，并用這些符號標(biāo)記其相應(yīng)的新結(jié)點(diǎn)。每個新結(jié)點(diǎn)與其父結(jié)點(diǎn)間都有一條連線。在一棵語法樹生長過程中的任何時刻，所有那些沒有后代的端末結(jié)自左向右排列起來就是一個句型。,語法樹構(gòu)造的過程,例1 文法G= ( {E}, {+, *, i , (, )}, P, E)，其中P為： E→ E+E | E*E | (E) | i 對該文法關(guān)于(i*i+i)的推導(dǎo)的語法樹如下所示：,51,接語法樹構(gòu)造舉例,E(根),（,E,）,E,+,+,E,E,*,E,,i,i,i,,,什么是樹的邊沿？,52,文法和語言,語法樹的問題分析,（1）允許產(chǎn)生同名結(jié)點(diǎn)（反映遞歸性）； （2）沒有后代的結(jié)點(diǎn)為端末結(jié)； （3）語法樹不能反映產(chǎn)生后代的先后順序；（例子在下一頁） （4）一棵語法樹表示了一個句型種種可能的（但未必是所有的）不同推導(dǎo)過程。,53,語法樹例子,推導(dǎo)過程中施用產(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 文法和語言的一些特性,文法和語言,2.5.1 無用非終結(jié)符號,如果文法的某個非終結(jié)符不出現(xiàn)在文法的任何一個句型中，并且不能從它推導(dǎo)出終結(jié)符號串，則稱該非終結(jié)符為無用非終結(jié)符。,例2.13 設(shè)文法G13 [A]： A - aaBbb B - aBb | ab C -cD | c D -Ef 哪些符號是無用非終結(jié)符號？,無用非終結(jié)符號：D E,對于文法G[S]，為了保證任一非終結(jié)符A在句子推導(dǎo)中出現(xiàn)，必須滿足如下兩個條件： 1）A必須在某句型中出現(xiàn)。 2）必須能從A推出終結(jié)符號串t來。,55,文法和語言,2.5.2 不可達(dá)文法符號,如果一個非終結(jié)符不出現(xiàn)在文法的任何一條產(chǎn)生式的右部，則稱該非終結(jié)符為不可達(dá)文法符號。,例2.13 設(shè)文法G13 [A]： A - aaBbb B - aBb | ab C -cD | c D -Ef 哪些符號是不可達(dá)文法符號？,不可達(dá)文法符號：C,56,文法和語言,多余符號和多余規(guī)則,無用非終結(jié)符和不可達(dá)文法符號都是多余符號。 包含有多余符號的規(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,文法和語言,多余符號和多余規(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,文法和語言,2.5.3 可空非終結(jié)符,若存在產(chǎn)生式 A - ε ，則該產(chǎn)生式稱為空產(chǎn)生式，A稱為可空非終結(jié)符。 空產(chǎn)生式有時候帶來方便，所以，可以往一個文法里增加空產(chǎn)生式。,59,2.5.4 最左推導(dǎo)/最右推導(dǎo)/規(guī)范推導(dǎo),最左推導(dǎo)：任何一步α= β都是對α中的最左非終結(jié)符進(jìn)行替換。 最右推導(dǎo)（又稱規(guī)范推導(dǎo)）：任何一步α=β都是對α中的最右非終結(jié)符進(jìn)行替換。 由規(guī)范推導(dǎo)所得到的句型稱為規(guī)范句型。,從一個句型到另一個句型的推導(dǎo)過程往往是不唯一的。 例如 E+E (i+i)： （a）E+E = E+i = i+i ——最右推導(dǎo) （b）E+E = i+E = i+i ——最左推導(dǎo),,,,,60,語法樹的特點(diǎn),文法和語言,一棵語法樹是這些不同推導(dǎo)過程的共性抽象，是它們的代表。一棵語法樹完全等價于一個最左（右）推導(dǎo)，這種等價性包括樹的步步生長和推導(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)的語法樹相同。,61,文法和語言,一個句型是否只對應(yīng)唯一的一棵語法樹？,例：G[E]: E → i E → E+E E → E*E E → (E),句型 i*i+i 的兩個不同的最左推導(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,文法和語言,定義2.13 ： 一個文法，如果它的一個句子對應(yīng)有兩棵或兩棵以上不同的語法樹，則這個文法是二義的。 或 一個文法的某個句子有兩個不同的最左（右）推導(dǎo)，則這個文法是二義的。,2.5.5 二義性,區(qū)別 文法的二義性：存在兩個不同文法G(二義)、G’(無二義)，卻有L(G)=L(G’)，即產(chǎn)生語言相同。 語言的二義性：若不存在無二義性的文法，則該語言是二義性的。,63,二義性其它問題,文法和語言,人們已證明，二義性問題是不可判定的，即不存在一個算法，它能在有限步驟內(nèi)，確切地判斷一個文法是否是二義的。我們所能做的就是為無二義性尋找一些充分條件。 例如對文法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,文法和語言,2.6 分析方法簡介,句型分析的任務(wù)就是按文法的產(chǎn)生式，識別輸入的符號是否是該文法的句型。語法樹——是句型推導(dǎo)過程的幾何表示，可以十分直觀的顯示某句型的結(jié)構(gòu)。因此在句型時，對輸入符號串構(gòu)造語法樹，以此識別它是否是該文法的一個句型（或句子）。因此，語法樹又可稱為語法分析樹或分析樹。我們把完成句型分析的程序稱為分析程序或識別程序，分析算法又稱識別算法。 分析算法又分為：,,從左到右分析算法； 從右到左分析算法；,,,自上而下的分析法 自下而上的分析法,65,文法和語言,自上而下的分析法,基本思想：從文法的開始符號出發(fā)，反復(fù)使用各種產(chǎn)生式，尋找“匹配”輸入符號串的推導(dǎo)。即對任何輸入符號串，從文法的開始符號（根結(jié)）出發(fā)，自上而下地為輸入串建立一棵語法樹，直到語法樹結(jié)果正好是輸入的符號串為止。,例如：文法G[S]: S→ xAy A→ aa | a，識別輸入串xay是否是該文法的一個句子。,66,文法和語言,自上而下分析法的缺陷,關(guān)鍵：回溯問題（∵ 其分析過程是一種試探過程） 回溯問題是從各種可能的候選式中任選一個，進(jìn)行推導(dǎo)后發(fā)現(xiàn)該候選式是錯誤的，則退回去重新選擇候選式的方式。例如上例中的(3)。,S,,,,S,S,x,A,y,(3) —選用第1個候選式,,a,回溯的產(chǎn)生使算法代價極低，效率很低。關(guān)于解決回溯問題將在第5章中介紹。,,a,67,自下而上的分析法,文法和語言,基本思想：從輸入串開始，逐步進(jìn)行“歸約”，直至歸約到文法的開始符號。即從語法樹的末端開始，步步向上“歸約”，直到根結(jié)。 歸約：若V= γαδ，W=γβδ，α → β是文法的產(chǎn)生式，如有V=W，則W直接歸約到V。,68,自下而上的語法分析舉例,例1：文法G：S → cAd A → ab A → a 識別輸入串w=cabd是否該文法的句子,S A A c a b d c a b d c a b d 規(guī)約過程：S ? cAd ? cabd,,,,,,,,69,文法和語言,例2： 文法G[S]： (1)S→ aAcBe (2) A→ b (3)A→ Ab (4) B→ d 識別abbcde是否為文法S的一個句子。,解題思想：掃描abbcde，從中找出一個子串，該子串與某一產(chǎn)生式的右部相匹配。,70,自下而上分析法舉例,文法和語言,例2解：,71,自下而上分析法存在的問題,文法和語言,可歸約串的問題；（∵ 該分析的每一步就是從當(dāng)前串中找一個子串（稱“可歸約串”），將它歸約到某個非終結(jié)符號） 自下而上分析法的關(guān)鍵就是找哪個子串是“可歸約串”，哪個不是“可歸約串”。例如上例中的(3),因此必須精確定義“可歸約串”，事實(shí)上存在著種種不同的方法刻畫“可歸約串”，對這個概念的不同定義，形成了不同的自下而上的分析法。在“規(guī)范歸約”的分析中，用“句柄”來刻畫“可歸約串”。,72,短語、直接短語、句柄,文法和語言,,,1、短語： 令文法G，開始符號為S，αβδ是G的句型（即S αβδ），如果S αAδ且A β，則稱β是句型αβδ相對于非終結(jié)符A的短語。 2、直接短語 如短語中有A=β，則稱β是句型相對于規(guī)則A→ β的直接短語。 3、句柄 一個句型的最左直接短語稱為該句型的句柄。,73,解題方法,文法和語言,,例：文法G[E]: E→ T | E+T T→ F | T*F F→ (E) | i 證明i+i*i是G的一個句型，并指出這個句型的所有短語、直接短語、句柄。,證明：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,接上例,文法和語言,語法樹：,E,,,,E,+,T,,T,,,,T,*,F,,F,,F,,i3,,i1,,i2,第1層 i1+i2*i3 —相對于E 第2層 i1 —相對于E ; i2*i3 —相對于T 第3層 i1 ,i2 —相對于T; i3 —相對于F 第4層 i1 ,i2 —相對于F(F→ i直接短語) 第5層,∴ i+i*i是G的一個句型，其中i1 , i2 , i3, i2*i3 , i1+i2*i3 都是句型i1+i2*i3 的短語，且i1 , i2 , i3 為直接短語， i1為句柄,75,分析說明,文法和語言,(2)作為“短語”的兩個條件是不可缺少的，僅僅有A β，未必意味著β就是句型αβδ的一個短語，因為還需要有S αβδ這個條件。,,例如：上例中有E i1+i2，但i1+i2并不是該句型的一個短語，因為不存在從E（開始符號）到E* i3的推導(dǎo)。,(1)短語、直接短語、句柄是針對某一句型（S α ）而言的;,76,解題方法,⒈先證明前提 ⒉給出語法樹（注意文法是否是二義性的） 如題文法G[E]: E→ E+E|E*E|(E) | i 證明i+i*i是G的一個句型，并指出這個句型的所有短語、直接短語、句柄。 ⒊根據(jù)每顆語法樹得出短語、直接短語、句柄 （注意編號）,77,練習(xí)1題目,文法G[T]: T→ F | T*F F →F ↑ P | P P→ (T) | i 證明T*P ↑(T*F)是文法G的一個句型，并指出這個句型的所有短語、直接短語、句柄。,78,練習(xí)１解答,證明：T T*F T*F↑P T*F↑(T) T*F↑(T*F) T*P↑(T*F),語法樹：,T,,,,T,*,F,,,,F,↑,P,,P,,T,,,(,),,,,T,*,F,第1層 T*P↑(T*F) —相對于T 第2層 P↑(T*F) —相對于F; 第3層 P —相對于F; (T*F) —相對于P 第4層 T*F —相對于T 第5層,∴ T*P↑(T*F)是G的一個句型，其中T*F , P , (T*F), P↑(T*F), T*P↑(T*F) 都是該句型的短語，且T*F , P 為直接短語， P為句柄,79,練習(xí)2題目,文法和語言,設(shè)有文法G[S]: S →V1 V1→ V2 | V1iV2 V2→ V3 | V2+V3 V3→ )V1* | ( (1)給出 (+(i( 的最右推導(dǎo)，并畫出相應(yīng)的語法樹； (2)證明V2+V3i( 是文法的一個句型，并指出這個句型的短語、直接短語、句柄。,80,練習(xí)２解答（１／２）,文法和語言,(1)解：S V1 V1iV2 V1iV3 V1i( V2i( V2+V3i( V2+(i( V3+(i( (+(i(,語法樹：,V1,,,,V1,i,V2,,,,(,S,,,V2,,,V2,+,V3,V3,,,V3,,(,(,,81,練習(xí)２解答（２／２）,文法和語言,(2)證明： S V1 V1iV2 V1iV3 V1i( V2i( V2+V3i( ∴ V2+V3i(是文法的一個句型 短語：V2+V3 , (, V2+V3i( 直接短語： V2+V3 , ( 句柄： V2+V3,82,3.7 有關(guān)文法實(shí)用中的一些說明(1/2),作為描述程序語言的上下文無關(guān)文法，我們對它有幾點(diǎn)小小的限制，在實(shí)用中，主要是在文法中不得含有有害規(guī)則和多余規(guī)則。 1、不含有害規(guī)則 有害規(guī)則是指形如P→P的產(chǎn)生式，因為這樣的產(chǎn)生式除了引起二義外，沒有任何用處。 2、不含多余規(guī)則 (1)不可到達(dá)的 即文法中的某些非終結(jié)符不在任何規(guī)則的右部出現(xiàn)，則任何句子推導(dǎo)不可能用到它。也就是說 對非終結(jié)符P，不存在S αPβ， α,β∈ (VN∪VT)*,,83,有關(guān)文法實(shí)用中的一些說明(2/2),文法和語言,(2) 不可終止的 即文法中的某些非終結(jié)符不能夠從它推出終結(jié)符串。也就是說 對非終結(jié)符P，不存在P t， t∈ VT* 若文法均滿足以上兩個條件，則稱這個文法為簡化了的文法。,,84,本章課后練習(xí),習(xí)題二 P45： 2、5、6、7,