【文章內(nèi)容簡介】 和 P是非空有窮集 ? VN∩VT=φ ? S是一個(gè)非終結(jié)符，且至少要在一條產(chǎn)生式左部出現(xiàn) ? 非終結(jié)符代表一個(gè)語言中的語法成分，是構(gòu)成程序的一個(gè)語法成分，這個(gè)符號(hào)本身不會(huì)在程序中出現(xiàn) ? 終結(jié)符是組成程序的具體的符號(hào) 例 1： 文法 G=(VN,VT,P,S) 其中： VN={S}， VT={0， 1}， P={S→0S1 ， S→01} 開始符為 S 例 2： 文法 G=(VN,VT,P,S) VN ={標(biāo)識(shí)符，字母，數(shù)字 }， VT ={a,b,c,…x,y,z,_,0,1,…,9} ， P={標(biāo)識(shí)符 → 字母 ， 標(biāo)識(shí)符 → 標(biāo)識(shí)符 字母 ， 標(biāo)識(shí)符 → 標(biāo)識(shí)符 數(shù)字 ， 字母 → a, …, 字母 →z ， 字母 → _， 數(shù)字 →0, … ,數(shù)字 →9 }， S=標(biāo)識(shí)符 2．文法的簡化表示法 ? 簡化表示法 : 通常不用將文法的四元組表示出來， 只寫出產(chǎn)生式 ? 約定： ? 第一條產(chǎn)生式的左部是開始符號(hào) 或用 G[S]表示 S是開始符號(hào) ? 用大寫字母（或用尖括號(hào) 括起來）表示非終結(jié)符 ? 用小寫字母表示終結(jié)符 ? 左部相同的產(chǎn)生式 A→α,A→β 可以記為 A→α|β ， 其中“ |”是“或”的意思， α,β分別稱為侯選式 ?例 3——改寫例 2 文法 G[S]： S→A|SA|SD A→_|a|b| … |z D→ 0|1|… |9 3. 推導(dǎo) (Derivation)與歸約 (Reduction) ?直接推導(dǎo)和直接歸約： α → β 是文法 G的產(chǎn)生式，若有 v， w滿足： v=γ α δ ,w=γ β δ , 其中 γ ,δ ∈V * 則稱 v直接推導(dǎo) 出 w,也稱 w直接歸約 到 v, 記作 v ? w 或 w | v ? 直接推導(dǎo) 就是用產(chǎn)生式的右部替換產(chǎn)生式的左部的過程 ? 直接歸約 就是用產(chǎn)生式的左部替換產(chǎn)生式的右部的過程 例 文法 G： S→0S1 ， S→01 有直接推導(dǎo)： S ?0S1 （ S→0S1 ） 0S1 ?00S11 （ S→0S1 ） 00S11 ?000S111 （ S→0S1 ） 000S111 ?00001111（ S→01 ） ?推導(dǎo)和歸約 ?若存在 v=w0 ?w1 ?... ?wn=w ,(n0) 則稱 v推導(dǎo)出 w，或 w歸約到 v,記為 v =+ w ?若有 v =+ w或 v = w，則記作 v =* w ?例 文法 G： S→0S1 ， S→01 S ? 0S1 ? 00S11 ? 000111 S =+ 000111 S =* 000111 S =* S 4．句型、句子、語言的定義 ?句型和句子 設(shè)有文法 G[S]，若符號(hào)串 α 是從開始符推導(dǎo)出來的 ,即 S =* α ，則稱 α 是文法 G的 句型 。若 α 僅由終結(jié)符組成 ,即 S =* α ，且α ∈V T*，則稱 α 是文法 G的 句子 例 文法 G[S]： S→0S1 ， S→01 因?yàn)?S ? 0S1 ? 00S11 ? 000S111 ? 00001111 所以 S,0S1 ,00S11 ,000S111,00001111都是 G的句型 00001111是 G的句子 ? 語言的定義 由文法 G生成的語言記為 L(G),它是文法 G的一切句子的集合 ,即 L(G)={x|S =* x，且 x∈V T* } 例 文法 G： S→0S1 ， S→01 S?0S1 ? 00S11 ? 03S13? … ? 0n1S1n1 ? 0n1n L(G)={0n1n|n≥1} ? 文法和語言的關(guān)系： 文法 G生成的每個(gè)串都在 L(G)中 L(G)中的每個(gè)串確實(shí)能被 G生成 ? 根據(jù)文法，可以通過推導(dǎo)得到該文法相應(yīng)的語言； 例： 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 表示一切能用符號(hào) a， +， ， (， )構(gòu)成的算術(shù)表達(dá)式 ? 有了語言的要求，也可以為該語言設(shè)計(jì)文法 例：若語言由 0、 1符號(hào)串組成，串中 0和 1的個(gè)數(shù)相同，構(gòu)造其文法為： A → 0B|1C B → 1|1A|0BB C → 0|0A|1CC 5．文法的等價(jià) 若 L(G1)=L(G2)，則稱文法 G1和 G2是等價(jià)的。 例如 文法 G1[A]： A→0R A→01 R→A1 G2[S]： S→0S1 S→01 所定義的語言都是 0n1n 故 ,兩文法等價(jià) (一 )形式語言理論 (二 )語言和文法的直觀概念 (三 )字母表、串、語言 (四 )文法和語言的形式定義 (五 )文法的類型 (六 )上下文無關(guān)文法及語法樹 (七 )句型的分析 (八 )有關(guān)文法實(shí)用中的一些說明 (一 )形式語言理論 (二 )語言和文法的直觀概念 (三 )字母表、串、語言 (四 )文法和語言的形式定義 (五 )文法的類型 (六 )上下文無關(guān)文法及語法樹 (七 )句型的分析 (八 )有關(guān)文法實(shí)用中的一些說明 (五 )文法的類型 通過對(duì)產(chǎn)生式施加不同的限制， Chomsky將文法分為四種類型： ?0型文法 (短語文法 )： 對(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替換成 ?，因此稱 1型文法為上下文有關(guān)文法。 ?2型文法（上下文無關(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替換成 ?，因此被稱為上下文無關(guān)文法 ?通常程序設(shè)計(jì)語言的語法，可用 2型文法來描述，因此重點(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ì)語言中 ， 3型文法通常用來描述單詞的結(jié)構(gòu) 。 因此重點(diǎn)研究 文法類別 產(chǎn)生式形式