【正文】 文法的直觀概念 如何來描述一種語言？ ?如果語言是有窮的（只含有有窮多個(gè)句子），可以將句子逐一列出來表示 ?如果語言是無窮的，要找出語言的有窮表示。 有兩個(gè)途經(jīng)： 1. 生成方式 （產(chǎn)生式）： 語言中的每個(gè)句子可以用嚴(yán)格定義的規(guī)則來構(gòu)造 2. 識別方式（自動機(jī)）： 用一個(gè)過程，當(dāng)輸入的一任意串屬于語言時(shí)，該過程經(jīng)有限次計(jì)算后就會停止并回答“是”，若不屬于，要么能停止并回答“不是”，要么永遠(yuǎn)繼續(xù)下去。 例 :“the monkey eat a banana” back b S U V Q a a a b a， b b back (一 )形式語言理論 (二 )語言和文法的直觀概念 (三 )字母表、串、語言 (四 )文法和語言的形式定義 (五 )文法的類型 (六 )上下文無關(guān)文法及語法樹 (七 )句型的分析 (八 )有關(guān)文法實(shí)用中的一些說明 (一 )形式語言理論 (二 )語言和文法的直觀概念 (三 )字母表、串、語言 (四 )文法和語言的形式定義 (五 )文法的類型 (六 )上下文無關(guān)文法及語法樹 (七 )句型的分析 (八 )有關(guān)文法實(shí)用中的一些說明 (三 )字母表、串、語言 1. 字母表 ? 定義 :元素的非空有窮集合 ? 例： ∑={0?1} Α={a?b,c} ? 元素也稱為符號，字母表也稱符號集。 ? 例：程序語言的字母表由字母數(shù)字和若干專用符號組成。 2. 符號串 ? 定義 :由字母表中的符號組成的任何有窮序列 ? 例： 0,00,10是字母表 ∑={0?1}上的符號串 a,ab,aaca是 Α={a?b?c}上的符號串 ? 在符號串中，符號是有順序的，順序不同 ,代表不同的符號串，如 :ab和 ba不同 ? 不含任何符號的符號串稱為空串，用 ε表示 注意 :{ε}并不等于空集合 { } ? 符號串長度 : 符號串中含有符號的個(gè)數(shù) 如 : |abc|=3 | ε|=0 3. 符號串 的運(yùn)算 ? 符號串的連接： 設(shè) x、 y是符號串 ,它們的連接是把 y的符號寫在 x的符號之后得到的符號串 xy 例如 x=ST， y=abu ， 則 xy=STabu 顯然 εx = xε=x ? 符號串的方冪： 把 符號串 a自身連接 n次得到的符號串 an = aa… aa (n個(gè) a) 例如 a1=a a2=aa a0=ε 4. 符號串集合： ? 定義 : 若集合 A中所有元素都是某字母表 ?上的符號串，則稱 A為字母表 ?上的符號串集合。 ? 空集 Φ——即 { } ? 符號串集合的和與乘積 (A和 B為符號串集合 ) ? 和 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ǔ) = Φ 注 : ε ∈ Φ {ε} = Φ ?符號串集合的方冪 : 設(shè) A是符號串的集合，則稱 Ai為符號串集 A的方冪，其中 i是非負(fù)整數(shù)。具體定義如下 : ?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,… } 即 Σ*表示 Σ上所有有窮長的串的集合 。 ?正閉包 A+ = A1∪ A2∪ A3∪ … 稱為 Σ的正閉包 A + 表示 ?上的 除 ε 外 的所有用窮長串的集合 注 : Σ* = Σ0∪ Σ+ 注 : Σ+ = ΣΣ* = Σ* Σ 字母表 ?上 的一個(gè)語言 是 ?上符合某種規(guī)則的一些符號串的集合 ， 是 ?*的一個(gè)子集 例如： Σ ={a,b} Σ *={ε ,a,b,aa,ab,ba,bb,aaa,aab,… } 1. 集合 {ab,aabb,aaabbb,… ,anbn,… }或 {w|w∈ Σ *且 w=anbn,n≥1} 為 字母表 ?上 的一個(gè)語言 2. 集合 {a,aa,aaa,… }或 {w|w∈ Σ *且 w=an,n≥1} 為字母表 ?上 的一個(gè)語言 3.?ε ?為 字母表 ?上 的一個(gè)語言 4. ?即 ? ?為 字母表 ?上 的一個(gè)語言 (一 )形式語言理論 (二 )語言和文法的直觀概念 (三 )字母表、串、語言 (四 )文法和語言的形式定義 (五 )文法的類型 (六 )上下文無關(guān)文法及語法樹 (七 )句型的分析 (八 )有關(guān)文法實(shí)用中的一些說明 (一 )形式語言理論 (二 )語言和文法的直觀概念 (三 )字母表、串、語言 (四 )文法和語言的形式定義 (五 )文法的類型 (六 )上下文無關(guān)文法及語法樹 (七 )句型的分析 (八 )有關(guān)文法實(shí)用中的一些說明 (四 )文法和語言的形式定義 1．文法的定義 2． 文法的簡化表示法 3． 推導(dǎo)與歸約 4． 句型 、 句子 、 語言的定義 5．文法的等價(jià) 1．文法的定義 ? 產(chǎn)生式（規(guī)則） 產(chǎn)生式是一個(gè)有序?qū)?(α,β)，通常寫作 α→β （或 α::=β ） ? 文法定義 : 文法 G(Grammar)定義為四元組（ VN， VT， P， S） VN (Nonterminal)：非終結(jié)符集 VT (Terminal)：終結(jié)符集 P (Production)：產(chǎn)生式 （ 規(guī)則 ） 集合 S：開始符號或識別符號 },,{ ,.,)2(at h ehase a tbananam o n k e yV Vt t? 有本例中表示用集合稱為終結(jié)符號集其稱為終結(jié)符號它們不需要進(jìn)一步定義含有若干基本符號S = 句子 go }冠 詞,動詞 短 語,主 語語 短,句子{V 有,對 ,集合稱 為 合 稱為 非 終其,稱 為為 非 終結(jié) 符,語 法范 疇含有一系列需要定 義 有( 1 )NN ????????? ?}冠 詞,動詞 短 語,主 語語 短,句子{V 有,對 ,集合稱 為 合 稱為 非 終其,稱 為為 非 終結(jié) 符,語 法范 疇含有一系列需要定 義 有(1)NN ????????? ?① 句子 ::=主語短語 動詞短語 ② 主語短語 ::= the 名詞 ③ 動詞短語 ::=動詞 賓語短語 ④ 賓語短語 ::=冠詞 名詞 ⑤ 名詞 ::=monkey ⑥ 名詞 ::=banana ⑦ 動詞 ::=eat ⑧ 動詞 ::=has ⑨ 冠詞 ::=the ⑩ 冠詞 ::=a back ? 說明 : ? V=VN∪ VT， V稱為文法 G的字母表 ? P中產(chǎn)生式形如： α→β, 其中 α∈ V+且至少含一個(gè)非終結(jié)符， β∈ V* ? VN,VT