【正文】 語法樹 設(shè) G=( VN,VT,P,S)為一 cfg，若一棵樹滿足下列 4個條件，則此樹稱作 G的語法樹 (推導(dǎo)樹 )(派生樹）： 1. 每個結(jié)點都有一個標(biāo)記，此標(biāo)記是 V的一個符號 2. 根的標(biāo)記是 S 3. 若一結(jié)點 n至少有一個它自己除外的子孫，并且有標(biāo)記 A，則肯定 A∈V N 4. 如果結(jié)點 n有標(biāo)記 A,其直接子孫結(jié)點從左到右的次序是 n1， n2， … ， nk，其標(biāo)記分別為 A1， A2， … ，Ak，那么 A→A 1A2， … ， Ak一定是 P中的一個產(chǎn)生式 語法樹的結(jié)果： 從左到右讀出葉子的標(biāo)記而構(gòu)成的行謂之 40 上下文無關(guān)文法的語法樹 ?句型 aabbaa的可能 推導(dǎo) 序列和語法樹 例 : 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 41 語法樹 句型推導(dǎo) 的 直觀表示 給定文法 G=(VN,VT,P,S)，對于 G的任何句型都能構(gòu)造與之關(guān)聯(lián)的語法樹 (推導(dǎo)樹 ) 定理： G為上下文無關(guān)文法， 對于 α ≠ ε ，有 S =* α ，當(dāng)且僅當(dāng) 文法 G有以 α 為結(jié)果的一棵語法樹 (推導(dǎo)樹 ) 42 一棵語法樹表示了一個句型的種種可能的 (但未必是所有的 )不同推導(dǎo)過程，包括最左(最右 )推導(dǎo)。 從左到右的分析算法 ，即 總是從 左 到 右 地 識別輸入符號串 ，首先識別符號串中的 最左符號，進而 依次識別右邊 的一個符號， 直到分析結(jié)束 。 2）文法中某些 非終結(jié)符 ，由它 不能推出終結(jié)符號串 ，該非終結(jié)符稱 為 不可終止 。 57 上下文無關(guān)文法中的 ε規(guī)則 上下文無關(guān)文法中某些規(guī)則可具有形式 A→ ε，稱這種規(guī)則為 ε規(guī)則 因為 ε規(guī)則會使得有關(guān)文法的一些討論和證明變得復(fù)雜 ,有時會限制這種規(guī)則的出現(xiàn) 兩種定義的唯一差別是 ε句子在不在語言中 文法構(gòu)思的啟示是要找出語言的有窮描述，而如果語言 L有一個有窮的描述，則 L1=L∪ ｛ ε｝也同樣有一個有窮的描述，并且可以證明，若 L是上下文有關(guān)語言、上下文無關(guān)語言或正規(guī)語言，則L∪ ｛ ε｝和 L｛ ε｝分別是上下文有關(guān)語言、上下文無關(guān)語言和正規(guī)語言。 自下而上分析法 ： 從 輸入符號串 開始 ， 逐步進行 歸約 ，直至歸約 到 文法的 開始符號 。因為可能有兩個不同的文法 G和 G′ ，其中 G是二義的，但是卻有 L(G)=L(G′) ，也就是說，這兩個文法所產(chǎn)生的語言是相同的。 對 G中的形如 D→tB 的產(chǎn)生式 ,t為終結(jié)符或 ε ,有 f(D,t)=B； 對 G中形如 D→t 的產(chǎn)生式， t為終結(jié)符或 ε ,有 f(D,t)=N。其識別系統(tǒng)是線性界限自動機。BEGIN READ(標(biāo)識符 ) END. (標(biāo)識符 ?A) VAR A。語言的有窮表示有兩個途經(jīng)： 生成方式 （文法）：語言中的每個句子可以用嚴(yán)格 定義的規(guī)則來構(gòu)造。 S:稱作識別符號或開始符號的一個非終結(jié)符，它至少要在一條產(chǎn)生式中作為左部出現(xiàn)。 ?句子 有文法 G，若 S =* x，且 x∈V T*，則稱 x是文法 G的句子。 3型文法（正規(guī)文法 RG）：產(chǎn)生的語言是有窮自動機（ FA）所接受的集合 28 3型文法產(chǎn)生的語言是有窮自動機（ FA）所接受的集合 . 定理 設(shè) G=（ VN， VT， P， S）是 3型文法，則存在一個有窮自 動機 M=(K, ∑ , f, A, Z) ，使得 L(M)=L(G) 有窮自動機 NFA M VN= K 46 （ 上下文無關(guān)文法） 句型的分析 句型分析 就是 識別 一個符號串是否為某文法的 句型 ，是某個 推導(dǎo) 的構(gòu)造過程。 導(dǎo)致失敗的原因是在分析中對A的選擇不是正確的。 〈 表達(dá)式 〉 ∷ =a|(〈 表達(dá)式 〉 )|〈 表達(dá)式 〉〈 運算符 〉〈 表達(dá)式 〉 〈 運算符 〉 ∷ =+||*|/ 3. 令文法 G［ E］為： E→T|E+T|E T T→F|T*F|T/F F→(E)|i 證明 E+T*F是它的一個句型 59 練習(xí) 4. 給出生成下述語言的上下文無關(guān)文法： （ 1） { anbnambm| n， m=0} (2) { 1n0m 1m0n| n， m=0} 5. 給出生成下述語言的三型文法： (1) { anbm|n,m=1 } (2){anbmck|n,m,k=0 } 6. 給出下述文法所對應(yīng)的正規(guī)式： S→0A|1B A→1S|1 B→0S|0