【正文】 語(yǔ)法樹(shù)的構(gòu)造： 從輸入符號(hào)串開(kāi)始，以它作為語(yǔ)法樹(shù)的末端結(jié)點(diǎn)符號(hào)串，自底向上的構(gòu)造語(yǔ)法樹(shù) 例 文法 G： S → cAd A → ab A → a 識(shí)別輸入串 w=cabd是否為該文法的句子 c a b d 歸約過(guò)程： 用“ |”表示歸約，下劃線(xiàn)部分為被歸約符號(hào) cabd |cAd |S A S ?自下而上分析的主要問(wèn)題 對(duì)輸入串 cabd的兩種歸約過(guò)程 （ 1） cabd|cAd|S 歸約到開(kāi)始符 （ 2） cabd|cAbd 不能歸約到開(kāi)始符 在自下而上的分析方法中 ， 每一步都是從當(dāng)前串中選擇一個(gè)子串加以歸約 ， 該子串暫稱(chēng) “ 可歸約串 ” 。 對(duì)于程序設(shè)計(jì)語(yǔ)言來(lái)說(shuō) ， 句型分析就是一個(gè)識(shí)別輸入符號(hào)串是否為語(yǔ)法上正確的程序的過(guò)程 。也把該語(yǔ)法樹(shù)稱(chēng)為該句型的語(yǔ)法樹(shù)。 例如 文法 G1[A]： A→0R A→01 R→A1 G2[S]： S→0S1 S→01 所定義的語(yǔ)言都是 0n1n 故 ,兩文法等價(jià) (一 )形式語(yǔ)言理論 (二 )語(yǔ)言和文法的直觀(guān)概念 (三 )字母表、串、語(yǔ)言 (四 )文法和語(yǔ)言的形式定義 (五 )文法的類(lèi)型 (六 )上下文無(wú)關(guān)文法及語(yǔ)法樹(shù) (七 )句型的分析 (八 )有關(guān)文法實(shí)用中的一些說(shuō)明 (一 )形式語(yǔ)言理論 (二 )語(yǔ)言和文法的直觀(guān)概念 (三 )字母表、串、語(yǔ)言 (四 )文法和語(yǔ)言的形式定義 (五 )文法的類(lèi)型 (六 )上下文無(wú)關(guān)文法及語(yǔ)法樹(shù) (七 )句型的分析 (八 )有關(guān)文法實(shí)用中的一些說(shuō)明 (五 )文法的類(lèi)型 通過(guò)對(duì)產(chǎn)生式施加不同的限制， Chomsky將文法分為四種類(lèi)型： ?0型文法 (短語(yǔ)文法 )： 對(duì)任一產(chǎn)生式 α → β ，都有 α ∈(V N∪V T)*且至少含一個(gè)非終結(jié)符，β ∈(V N∪V T)* ?1型文法 (上下文有關(guān) )： 是 0型文法的特例，對(duì) P中的任一產(chǎn)生式 α → β ，都 |β |≥| α |， 僅僅 S→ ε 除外 例 文法 G[S]： S→aSBC S→abC CB→BC bB→bb bC→bc cC→cc 1型文法產(chǎn)生式的一般形式是 ?A?→ ???， ?,? ∈V * ，A∈V N , ?∈V ＋ ,它表示當(dāng) A的上文為 ?且下文為 ?時(shí)可把A替換成 ?，因此稱(chēng) 1型文法為上下文有關(guān)文法。 ? 空集 Φ——即 { } ? 符號(hào)串集合的和與乘積 (A和 B為符號(hào)串集合 ) ? 和 A+B（或 A?B） ={w | w∈ A或 w∈ B} ? 乘積 AB ={xy | x∈ A且 y∈ B} 若集合 A = ?ab,cde? B = ?0,1? 則 AB = ?ab0,ab1,cde0,cde1? 注 : A{ε }= {ε}A = A AΦ= ΦA(chǔ) = Φ 注 : ε ∈ Φ {ε} = Φ ?符號(hào)串集合的方冪 : 設(shè) A是符號(hào)串的集合，則稱(chēng) Ai為符號(hào)串集 A的方冪，其中 i是非負(fù)整數(shù)。 有兩個(gè)途經(jīng)： 1. 生成方式 （產(chǎn)生式）： 語(yǔ)言中的每個(gè)句子可以用嚴(yán)格定義的規(guī)則來(lái)構(gòu)造 2. 識(shí)別方式（自動(dòng)機(jī)）： 用一個(gè)過(guò)程，當(dāng)輸入的一任意串屬于語(yǔ)言時(shí)，該過(guò)程經(jīng)有限次計(jì)算后就會(huì)停止并回答“是”，若不屬于，要么能停止并回答“不是”，要么永遠(yuǎn)繼續(xù)下去。然而，若不考慮 語(yǔ)義 ，則我們就必須承認(rèn)它們是語(yǔ)法上 合法 的句子。每次替換稱(chēng)為一步（直接） 推導(dǎo) ，并用符號(hào)“ ?” 表示。并設(shè)每個(gè)句子都是“主 謂 賓”結(jié)構(gòu) ? 文法 —— 見(jiàn)右。其中，每個(gè)用 括起來(lái)的部分是所要定義語(yǔ)言中的一個(gè)語(yǔ)法實(shí)體（稱(chēng)為語(yǔ)法單位、語(yǔ)法結(jié)構(gòu)、語(yǔ)法范疇、語(yǔ)法變量等）。 例如 ? 首先用規(guī)則①進(jìn)行第一步推導(dǎo)，可得到 主語(yǔ)短語(yǔ) 動(dòng)詞短語(yǔ) ，即 ? 句子 ? 主語(yǔ)短語(yǔ) 動(dòng)詞短語(yǔ) ? 所得符號(hào)串 主語(yǔ)短語(yǔ) 動(dòng)詞短語(yǔ) 含有兩個(gè) 語(yǔ)法實(shí)體 ，可對(duì)其中任一個(gè)（例如對(duì) 動(dòng)詞短語(yǔ) ）進(jìn)行新的 推導(dǎo) ? 句子 ? 主語(yǔ)短語(yǔ) 動(dòng)詞短語(yǔ) ? ? 主語(yǔ)短語(yǔ) 動(dòng)詞 賓語(yǔ)短語(yǔ) ? 重復(fù)上述過(guò)程，可得到一個(gè)推導(dǎo)序列（見(jiàn)下頁(yè)）。 (二 )語(yǔ)言和文法的直觀(guān)概念 1. 程序設(shè)計(jì)語(yǔ)言的定義 語(yǔ)言是一個(gè)記號(hào)系統(tǒng)。 例 :“the monkey eat a banana” back b S U V Q a a a b a， b b back (一 )形式語(yǔ)言理論 (二 )語(yǔ)言和文法的直觀(guān)概念 (三 )字母表、串、語(yǔ)言 (四 )文法和語(yǔ)言的形式定義 (五 )文法的類(lèi)型 (六 )上下文無(wú)關(guān)文法及語(yǔ)法樹(shù) (七 )句型的分析 (八 )有關(guān)文法實(shí)用中的一些說(shuō)明 (一 )形式語(yǔ)言理論 (二 )語(yǔ)言和文法的直觀(guān)概念 (三 )字母表、串、語(yǔ)言 (四 )文法和語(yǔ)言的形式定義 (五 )文法的類(lèi)型 (六 )上下文無(wú)關(guān)文法及語(yǔ)法樹(shù) (七 )句型的分析 (八 )有關(guān)文法實(shí)用中的一些說(shuō)明 (三 )字母表、串、語(yǔ)言 1. 字母表 ? 定義 :元素的非空有窮集合 ? 例： ∑={0?1} Α={a?b,c} ? 元素也稱(chēng)為符號(hào)，字母表也稱(chēng)符號(hào)集。具體定義如下 : ?A0 ={ε} ?A1 = A , A2 = A A ?AK = AA......A(k個(gè) ) 5. 集合的閉包 ? 閉包 集合 A的閉包 A *定義如下： A * = A0∪ A1∪ A 2∪ A 3∪ … 例：設(shè)有字母表 Σ={0， 1} 則 Σ*=Σ0∪ Σ1∪ Σ2∪ … ={ε,0,1,00,01,10,11,000,… } 即 Σ*表示 Σ上所有有窮長(zhǎng)的串的集合 。 ?2型文法（上下文無(wú)關(guān)文法） ： 它是 1型文 法的特例，對(duì)任一產(chǎn)生式 α→β ，都有 α∈ VN ， β∈ (VN∪ VT)* 例 文法 G[S]： S→AB A→BS|0 B→SA|1 ?2型文法產(chǎn)生式的一般形式是 : A→ ?，它表示不管 A的上下文如何都可把 A替換成 ?，因此被稱(chēng)為上下文無(wú)關(guān)文法 ?通常程序設(shè)計(jì)語(yǔ)言的語(yǔ)法，可用 2型文法來(lái)描述，因此重點(diǎn)研究 ? 3型文法 (正規(guī)文法 )： 它是 2型文法的特例， 任一產(chǎn)生式 α → β 的形式都為 A→aB 或 A→a ，其中 A ， B∈V N ， a∈V T 例如 文法 G[S]： S→0A|1B|0 A→0A|1B|0S B→1B|1|0 在程序設(shè)計(jì)語(yǔ)言中 ， 3型文法通常用來(lái)描述單詞的結(jié)構(gòu) 。 ? 例 文法 G： E→E+T|T T→T F|F F→(E)|i 句子 i+i i的推導(dǎo)過(guò)程如下： 最左推導(dǎo)： E=E+T=T+T=F+T=i+T=i+T F=i+F F =i+i F=i+i i 最右推導(dǎo)： E=E+T=E+T F=E+T i=E+F i=E+i i = T+i i=F+i i=i+