【正文】 N,VT,P,S)為一 cfg，若一棵樹滿足下列 4個條件，則此樹稱作 G的語法樹 (推導樹 )(派生樹）： 1. 每個結(jié)點都有一個標記，此標記是 V的一個符號 2. 根的標記是 S 3. 若一結(jié)點 n至少有一個它自己除外的子孫，并且有標記 A，則肯定 A∈V N 4. 如果結(jié)點 n有標記 A,其直接子孫結(jié)點從左到右的次序是 n1， n2， … ， nk，其標記分別為 A1， A2， … ，Ak，那么 A→A 1A2， … ， Ak一定是 P中的一個產(chǎn)生式 語法樹的結(jié)果： 從左到右讀出葉子的標記而構(gòu)成的行謂之 66 語法樹 句型推導 的 直觀表示 給定文法 G=(VN,VT,P,S)，對于 G的任何句型都能構(gòu)造與之關(guān)聯(lián)的語法樹 (推導樹 ) 定理： G為上下文無關(guān)文法， 對于 α ≠ ε ，有 S =* α ，當且僅當 文法 G有以 α 為結(jié)果的一棵語法樹 (推導樹 ) 67 構(gòu)造語法樹 G[E]： E→E+T|T T→T*F|F F→(E)|a E?E+T ?T+T ?F+T ?a+T ?a+T*F ?a+F*F ?a+a*F ?a+a*a E E E + T E + T T E E + T T F 68 E?E+T ?T+T ?F+T ?a+T ?a+T*F ?a+F*F ?a+a*F ?a+a*a E?E+T ?E+T*F ?E+T*a ?E+F*a ?E+a*a ?T+a*a ?F+a*a ?a+a*a E?E+T ?T+T ?T+T*F ?F+T*F ?F+F*F ?a+F*F ?a+F*a ?a+a*a E E + T T T * F F F a a a 看不出句型中的符號被替代的順序 69 上下文無關(guān)文法的語法樹的用處 用于描述上下文無關(guān)文法 句型推導 的 直觀方法 例 : G[S]: S→ aAS A→ SbA A→ SS S→ a A→ ba S a A S S b A a a b a 句型 aabbaa的 語法樹 （推導樹） 葉子結(jié)點 ：樹中 沒有子孫的結(jié)點 。 S = A VT =∑ 對 G中的形如 D→tB 的產(chǎn)生式 ,t為終結(jié)符或 ε ,有 f(D,t)=B； 對 G中形如 D→t 的產(chǎn)生式， t為終結(jié)符或 ε ,有 f(D,t)=N。 A=S ∑= VT 其識別系統(tǒng)是不確定的下推自動機。其識別系統(tǒng)是線性界限自動機。 語言之間的關(guān)系依次：有不是上下文有關(guān)語言的 0型語言，有不是上下文無關(guān)語言的1型語言，有不是正則語言的上下文無關(guān)語言。即有： S =* anBnEn 接著，使用產(chǎn)生式 (4)一次，得到 S =* anbBn1En，然后使用產(chǎn)生式 (5)n1次得到： S =* anbnEn，最后使用產(chǎn)生式 (6)一次，使用產(chǎn)生式(7)n1次，得到： S =* anbnen 也能證明，對于 n≥1，串 anbnen是唯一形式的終結(jié)符號串 40 文法的等價 ?若 L（ G1） =L（ G2），則稱文法 G1和 G2是等價的。然后從 an(BE)n繼續(xù)推導，總是對 EB使用產(chǎn)生式 (3)的右部進行替換，而最終在得到的串中，所有的 B都先于所有的 E。 句子 有文法 G，若 S =* x，且 x∈V T*，則稱 x是文法 G的句子。BEGIN READ(標識符 )END. ? VAR A。α稱為規(guī)則的左部， β稱作規(guī)則的右部。 S稱作識別符號或開始符號，它是一個非終結(jié)符，至少要在一條產(chǎn)生式中作為左部出現(xiàn)。 識別方式 （自動機）：用一個過程，當輸入的一任意串屬于語言時，該過程經(jīng)有限次計算后就會停止并回答“是”，若不屬于，要麼能停止并回答“不是”，（要麼永遠繼續(xù)下去。 L的 n次連接 Ln= LL...L 20 語言 上 的運算 語言 L的 閉包 記 為 L*， L*= L0 ? L1 ? L2 ? ... L0= ?ε ? ， Ln= L Ln1= Ln1 L,n?1 語言 L的正 閉包 記 為 L+， L+= L1 ? L2 ? L3 ... L+= LL*= L*L L*= L+ ? ?ε ? 如： L1 ={a,b,… y,z} M1 ={1,2… 8,9 } （ L1?M1） ={a,b,… y,z， 1,2… 8,9 } （ L1?M1） *={a,b,… y,z， 1,2… 8,9 ，aa,1a,…xyz,6789st..} L1（ L1?M1） *={所有字母打頭的字母和數(shù)字符號串 } 21 文法和語言的形式定義 如何來描述一種語言？ 如果語言是有窮的（只含有有窮多個句子），可以將句子逐一列出來表示 如果語言是無窮的，找出語言的有窮表示。 19 給出語言 上 的有關(guān)運算 設(shè) L是（ ?上的）一個語言 ,M是（ ?上的）一個語言 , 語言 L和 M的并，交，差，補 是一個語言。 ?ε ?是一個語言。 例如： 字母表 Σ ={a,b} ,Σ *={ε ,a,b,aa,ab,ba,bb,aaa,aab,… } 集合 {ab,aabb,aaabbb,… ,anbn,… } 或表示為 {w|w∈ Σ *且 w=anbn,n≥1} 為 字母表 ?上 的一個語言。 17 例： Σ ={a,b} Σ *={ε ,a,b,aa,ab,ba,bb,aaa,aab,… } Σ +={a,b,aa,ab,ba,bb,aaa,aab,… } . . . . . .}{ 2* ??????? ?. . . . . .}{ 32** ?????????????? ? ?18 有關(guān)定義和記號 語言 是由句子組成的集合，是由一組符號所構(gòu)成的集合。 ?上的 除 ε 外 的所有符號串組成的集合記為?+ 。 兩個符號串集合 A和 B的乘積定義為 AB =?xy|x?A且 y?B? 若 集合 A=?ab,cde? B = ?0,1? 則 AB =?ab1,ab0,cde0,cde1? 使用 ?* 表示 ?上的一切符號串（包括 ε ）組成的集合。 符號串 s的真前綴，真后綴，真子串：任何非空符號串 x,相應(yīng)地，是 s的前綴，后綴或子串，并且 s ? x 符號串的運算 符號串的長度：符號串中符號的個數(shù) .符號串 s的長度記為 |s|。 ε (沒有 符號的符號串 )是 ?上的符號串 x是 ?上的符號串 ,a是 ?的元素 ,則 xa是 ?上的符號串 3. y是 ?上的符號串 ,當且僅當它可以由 1和 2導出。 字母表 ?：符號（元素）的非空有窮集合。 是程序設(shè)計語言語法分析研究的基礎(chǔ) ?！?形式 ” 是指這樣的事實：語言的所有規(guī)則只以什麼符號串能出現(xiàn)的方式來陳述 。 12 如果不考慮語義和語用 ， 即只從語法這一側(cè)面來看語言 ， 這種意義下的語言稱作形式語言 。 這兩個意義并非總是一樣的 ， 前者稱為語言的語義 ， 后者是其語用意義 。 11 每種語言具有兩個可識別的特性 ， 即語言的形式和該形式相關(guān)聯(lián)的意義 。 漢語 所有符合漢語語法的句子的全體 英語 所有符合英語語法的句子的全體 程序設(shè)計語言 所有該語言的程序的全體 每個句子構(gòu)成的規(guī)律 研究語言 每個句子的含義 每個句子和使用者的關(guān)系 9 研究程序設(shè)計語言 每個程序構(gòu)成的規(guī)律 每個程序的含義 每個程序和使用者的關(guān)系 語言研究的三個方面 語法 Syntax 語義 Semantics 語用 Pragmatics 10 語法 表示構(gòu)成語言句子的各個記號之間的組合規(guī)律 語義 表示各個記號的特定含義。其中一種描述元語言稱為文法。這些規(guī)則成為我們判別句子結(jié)構(gòu)合法與否的依據(jù)，換句話說，這些規(guī)則看成是一種元語言，用它描述漢語。是漢語的一個句子 〈 句子 〉 ∷ =〈 主語 〉〈 謂語 〉 〈 主語 〉 ∷ =〈 代詞 〉 ｜ 〈 名詞 〉 〈 代詞 〉 ∷ =我 ｜ 你 ｜ 他 〈 名詞 〉 ∷ =王明 ｜ 大學生 ｜ 工人 ｜ 英語 〈 謂語 〉 ∷ =〈 動詞 〉〈 直接賓語 〉 〈 動詞 〉 ∷ =是 ｜ 學習 〈 直接賓語 〉 ∷ =〈 代詞 〉 ｜ 〈 名詞 〉 5 有了一組規(guī)則以后，按照如下方式用它們導出句子：開始去找∷ =左端的帶有 〈 句子 〉 的規(guī)則并把它由 ∷ =右端的符號串代替，這個動作表示成： 〈 句子 〉 ? 〈 主語 〉〈 謂語 〉 ， 然后在得到的串 〈 主語 〉〈 謂語 〉 中，選取 〈 主語 〉 或 〈 謂語 〉 ，再用相應(yīng)規(guī)則的 ∷ =右端代替之?！靶问健笔侵高@樣的事實：語言的所有規(guī)則只以什麼符號串能出現(xiàn)的方式來陳述 2 本章知識點 (內(nèi)容 ) 引言和預(yù)備知識 文法和語言的形式定義 文法的類型 上下文無關(guān)文法及其語法樹 上下文無關(guān)文法 的句型分析 有關(guān)文法實用中的一些說明 3 文法的直觀概念和 語言概述 當我們表述一種語言時，無非是說明這種語言的句子，如果語言只含有有窮多個句子，則只需列出句子的有窮集就行了，但對于含有無窮句子的語言來講，存在著如何給出它的有窮表示的問題。1 第四章 文法和語言 本章目的 為語言的語法描述尋求工具 工具要對程序設(shè)計語言給出精確無二義的語法描述。（嚴謹、簡潔、易讀） 形式 工具 形式語言抽象地定義為一個數(shù)學系統(tǒng)。 以自然語言為例，人們無法列出全部句子，但是人們可以給出一些規(guī)則，用這些規(guī)則來說明 (或者定義 )句子的組成結(jié)構(gòu)，比如漢語句子可以是 由主語后隨謂語而成，構(gòu)成謂語的是動詞和直接賓語，我們采用第 2章所介紹的 EBNF來表示這種句子的構(gòu)成規(guī)則： 4 “我是大學生 ” 。比如，選取了 〈 主語 〉 ，并采用規(guī)則 〈 主語 〉 ∷ =〈 代詞 〉 ， 那么得到： 〈 主語 〉〈 謂語 〉 ? 〈 代詞 〉〈 謂語 〉 ， 重復(fù)做下去， 句子： “ 我是大學生 ” 的全部動作過程是： 〈 句子 〉 ? 〈 主語 〉〈 謂語 ? 〈 代詞 〉〈 謂語 〉 ?我 〈 謂語 ?我 〈 動詞 〉〈 直接賓語 〉 ? 我是 〈 直接賓語 〉 ?我是 〈 名詞