第二章高級語言及其語法描述-資料下載頁
2025-07-20 05:23本頁面
【正文】 S]： S→aB|bA A→a|aS|bAA B→b|bS|aBB 文法 G[S]： S→0A|1B|0 A→0A|1B|0S B→1B|1|0 文法的類型 ? 例：定義標識符的 3型（正規(guī)）文法 文法 G[I]： I → lT I → l T → lT T → dT T → l T → d 文法和語言 – 0型文法產(chǎn)生的語言稱為 0型語言 – 1型文法或上下文有關(guān)文法（ CSG ） 產(chǎn)生的語言稱為 1型語言 或上下文有關(guān) 語言（ CSL） – 2型文法或上下文無關(guān)文法（ CFL ） 產(chǎn)生的語言稱為 2型語言 或上下文無關(guān) 語言（ CF L ） – 3型文法或正則（正規(guī)）文法（ RG ） 產(chǎn)生的語言稱為 3型語言 正則（正規(guī)） 語言（ RL ） 文法和識別系統(tǒng) ? 0型文法（短語文法）的能力相當于圖靈機，可以表征任何遞歸可枚舉集，而且任何 0型語言都是遞歸可枚舉的 ? 1型文法（上下文有關(guān)文法）：產(chǎn)生式的形式為 α 1Aα 2→ α 1βα2， 即只有 A出現(xiàn)在 α 1和 α 2的上下文中時，才允許 β 取代A。 其識別系統(tǒng)是線性界限自動機。 文法的類型 ? 2型文法（上下文無關(guān)文法、 CFG）： 產(chǎn)生式的形式為 A→ β ， β 取代 A時與 A的上下文無關(guān)。其識別系統(tǒng)是不確定的下推自動機。 ? 3型文法（正規(guī)文法、右線性文法）：產(chǎn)生的語言是有窮自動機（ FA） 所接受的集合 上下文無關(guān)文法及其語法樹 ? 上下文無關(guān)文法有足夠的能力描述現(xiàn)今程序設計語言的語法結(jié)構(gòu) – 算術(shù)表達式 – 語句 ? 賦值語句 ? 條件語句 ? 讀語句 ? …… 算術(shù)表達式 上下文無關(guān)文法表示 ? 文法 G=({E}, {+,*,I,(,)}, P, E} P: E → i E → E+E E → E*E E → (E) 條件語句 上下文無關(guān)文法表示 條件語句 → if條件 then語句 | if條件 then語句 else 語句 上下文無關(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é)點。 從左到右讀出推導樹的葉子標記，所得的句型為推導樹的結(jié)果。也把該推導樹稱為該句型的語法樹。 上下文無關(guān)文法的語法樹 ? 給定文法 G， 對于 G的任何句型都能構(gòu)造與之關(guān)聯(lián)的語法樹（推導樹）。這棵樹滿足下列 4個條件： 每個結(jié)點都有一個 V中的符號作標記 根的標記是開始符號 S 若一結(jié)點 n至少有一個它自己除外的子孫，并且 n有標記 A， 則 A∈V N 如果結(jié)點 n的直接子孫，從左到右的次序是結(jié)點 n1,n2,…,n k， 其標記分別為 A1,A2,…,A k，那么 A→ A1A2,…,A k一定是 P中的一個產(chǎn)生式 上下文無關(guān)文法的語法樹 ? 推導過程中施用產(chǎn)生式的 順序 例 : G[S]: S→ aAS A→ SbA A→ SS S→ a A→ ba S a A S S b A a a b a S?aAS?aAa?aSbAa?aSbbaa?aabbaa S?aAS?aSbAS?aabAS?aabbaS?aabbaa S?aAS?aSbAS?aSbAa?aabAa?aabbaa ? 最左（最右）推導：在推導的任何一步α ?β ， 其中 α 、 β 是句型，都是對 α 中的最左（右）非終結(jié)符進行替換 ? 最右推導被稱為規(guī)范推導。 ? 由規(guī)范推導所得的句型稱為規(guī)范句型 ? 問題：一個句型是否對應唯一的一棵語法樹？ ? 例： G[E]: E → i E → E+E E → E*E E → (E) E E + E E * E i i i E E * E i E + E i i 句型 i*i+i 的兩個不同的最左推導： 推導 1： E ? E+E ? E*E+E ? i*E+E ? i*i+E ? i*i+i 推導 2： E ? E*E ? i*E ? i*E+E ? i*i+E ?i*i+i
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1