編譯原理形式語(yǔ)言(編輯修改稿)
2025-02-16 10:57 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 和 P是非空有窮集 ? VN∩VT=φ ? S是一個(gè)非終結(jié)符，且至少要在一條產(chǎn)生式左部出現(xiàn) ? 非終結(jié)符代表一個(gè)語(yǔ)言中的語(yǔ)法成分，是構(gòu)成程序的一個(gè)語(yǔ)法成分，這個(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} 開(kāi)始符為 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．文法的簡(jiǎn)化表示法 ? 簡(jiǎn)化表示法 : 通常不用將文法的四元組表示出來(lái)， 只寫(xiě)出產(chǎn)生式 ? 約定： ? 第一條產(chǎn)生式的左部是開(kāi)始符號(hào) 或用 G[S]表示 S是開(kāi)始符號(hào) ? 用大寫(xiě)字母（或用尖括號(hào) 括起來(lái)）表示非終結(jié)符 ? 用小寫(xiě)字母表示終結(jié)符 ? 左部相同的產(chǎn)生式 A→α,A→β 可以記為 A→α|β ， 其中“ |”是“或”的意思， α,β分別稱為侯選式 ?例 3——改寫(xiě)例 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)生式的左部的過(guò)程 ? 直接歸約 就是用產(chǎn)生式的左部替換產(chǎn)生式的右部的過(guò)程 例 文法 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．句型、句子、語(yǔ)言的定義 ?句型和句子 設(shè)有文法 G[S]，若符號(hào)串 α 是從開(kāi)始符推導(dǎo)出來(lái)的 ,即 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的句子 ? 語(yǔ)言的定義 由文法 G生成的語(yǔ)言記為 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} ? 文法和語(yǔ)言的關(guān)系： 文法 G生成的每個(gè)串都在 L(G)中 L(G)中的每個(gè)串確實(shí)能被 G生成 ? 根據(jù)文法，可以通過(guò)推導(dǎo)得到該文法相應(yīng)的語(yǔ)言； 例： 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á)式 ? 有了語(yǔ)言的要求，也可以為該語(yǔ)言設(shè)計(jì)文法 例：若語(yǔ)言由 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 所定義的語(yǔ)言都是 0n1n 故 ,兩文法等價(jià) (一 )形式語(yǔ)言理論 (二 )語(yǔ)言和文法的直觀概念 (三 )字母表、串、語(yǔ)言 (四 )文法和語(yǔ)言的形式定義 (五 )文法的類型 (六 )上下文無(wú)關(guān)文法及語(yǔ)法樹(shù) (七 )句型的分析 (八 )有關(guān)文法實(shí)用中的一些說(shuō)明 (一 )形式語(yǔ)言理論 (二 )語(yǔ)言和文法的直觀概念 (三 )字母表、串、語(yǔ)言 (四 )文法和語(yǔ)言的形式定義 (五 )文法的類型 (六 )上下文無(wú)關(guān)文法及語(yǔ)法樹(shù) (七 )句型的分析 (八 )有關(guān)文法實(shí)用中的一些說(shuō)明 (五 )文法的類型 通過(guò)對(duì)產(chǎn)生式施加不同的限制， Chomsky將文法分為四種類型： ?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替換成 ?，因此稱 1型文法為上下文有關(guān)文法。 ?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替換成 ?，因此被稱為上下文無(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) 。 因此重點(diǎn)研究 文法類別 產(chǎn)生式形式
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1