編譯原理（清華大學出版社）-- 文法和語言 -- 文法和語言的形式定義

規則，推導

規則（重寫規則、産生式或生成式）

• 形如 α→β 或 α::=β 的（α，β）有序對，其中α稱為規則的左部，β稱為規則的右部，這裡的符号 →（::=）讀作 "定義為"，例如A→a讀作 “A定義為a”
• 文法 G定義為四元組（VN，VT，P，S）
• 其中VN為非終結符集（文法實體 或 變量）；VT終結符集；P為規則（α→β）的集合，α∈（VN∪VT）* ，且至少包含一個非終結符，β∈（VN∪VT）*，VN，VT和P都是非空有窮集
• S稱為識别符或者開始符，它是一個非終結符，至少要在一條規則中作為左部出現
• VN 和 VT 不含公共的元素，即VN ∩ VT = Ø
• 通常用 V 表示 VN ∪ VT ，V稱為文法G的字母表或詞彙表

例2.1 有文法G=<VN，VT，P，S>，其中，VN={S}，VT={0，1}，P={S→0S1，S→01}，這裡非終結符集中隻含一個元素S，終結符号集由兩個元素 0，1組成，有兩條産生式，開始符是S

該例子也可以寫成

G： S→0S1

　　S→01

或者

G[S]：S→0S1

           S→01

例2.2 有文法G=（VN，VT，P，S），其中 VN = {辨別符，字母，數字}，VT = {a，b，c，...，x，y，z，0，1，...，9}

P = { <辨別符>→<字母>

　　  <辨別符>→<辨別符><字母>

　　  <辨別符>→<辨別符><數字>

         <字母>→a

         <字母>→b

　　  ...

　　  <字母>→z

　　  <數字>→0

　　  <數字>→1

 　　 ...

　　  <數字>→9

}

S=<辨別符>

為定義文法所産生的語言，還需要引入 推導 的概念，定義 V* 中的符号之間的關系，直接推導=>，長度為n（n≥1）的推導 

 和長度為n（n≥0）的推導 

直接推導/直接歸約的定義

• 設α→β是文法G=(VN，VT，P，S)的規則（或者是P中的一個産生式），γ 和 δ 是V*中的任意符号
• 若有符号串 v、ω滿足，v = γαδ，ω=γβδ，則說v（應用規則α→β）直接産生ω，或說ω是v的直接推導，或說ω直接歸約到v，記作v=>ω

例如，對于例2.1的文法G，可以給出一些例子

1. v=0S1，ω=0011，直接推導：0S1=>0011，使用的規則：S→01，這裡γ=0，δ=1
2. v=S，ω=0S1，直接推導：S=>0S1，使用的規則：S→0S1，這裡γ=ε，δ=ε，ε類似于群裡面的幺元
3. v=0S1，ω=00S11，直接推導：0S1=>00S11，使用的規則，S→0S1，這裡γ=0，δ=1

對于例2.1的文法G，直接推導的例子如下

1. v=<辨別符> ，ω=<辨別符><字母>，直接推導：<辨別符>=><辨別符><字母>，使用的規則：<辨別符>→<辨別符><字母>，這裡γ=δ=ε
2. v=<辨別符><字母><數字>，ω=<字母><字母><數字>，直接推導：<辨別符><字母><數字>=><字母><字母><數字>，使用的規則：<辨別符>→<字母>，這裡γ=ε，δ=<字母><數字>
3. v=abc<數字>，ω=abc5，直接推導：abc<數字>=>abc5，使用的規則：<數字>→5，這裡γ=abc，δ=ε

序列中的推導定義

• 如果存在直接推導的序列：v=ω0 => ω1 => ω2 => ... => ωn = ω （n>0）則稱v推導出（産生）ω（推導長度為n），或稱ω歸約到v，記作v 

  

  ω
• 若有 v 

  

  ω，或 v = ω，則記作 v 

  

  ω 對例2.1的文法，存在直接推導序列 v=S1 => 00S11 => 000S11 => 00001111 = ω，即 0S1 

  

   00001111，也可記作 0S1 

  

  00001111
• 對例2.2的文法，存在直接推導序列 v = <辨別符> => <辨別符><數字> => <字母><數字> => x<數字> => x1 = ω，即 <辨別符> 

  

  x1

句型（推導出來的結果）和句子（僅由終結符号組成的句型）的定義

• 設G[S]是一個文法，如果符号串x是從識别符号推導出來的，即有 S 

  

   x，則稱x是文法 G[S] 的句型
• 若x僅由終結符号組成， 即 S 

  

   x，x∈V*T ，則稱x為G[S]的句子
• 例如，在例2.1中，S、0S1、000111都是例2.1的文法G的句型，其中000111是G的句子
• 在例2.2中，<辨別符><字母>，<字母><數字>，a1都是例2.2文法G的句型，其中a1是G的句子

文法G産生的語言定義

• 文法G産生的語言定義為集合{x|S

  

  x，其中S為文法識别符号，且x∈V*T}，可用L（G）表示該集合

文法描述的語言是該文法一切句子（僅由終結符号組成的句型）的集合

考慮例2.1的文法G，有兩條産生式（規則）：S→0S1 和 S→01，通過對第一個産生式使用 n-1 次，然後使用第二個産生式一次，得到 S=>0S1=>00S11=>...=>0n-1S1n-1=>0n1n

L(G)={0n1n|n≥1}

例題2.3

1. S→aSBE
2. S→aBE
3. EB→BE
4. aB→ab
5. bB→bb
6. bE→be
7. eE→ee

• • A→0R
  • A→01
  • R→A1

論讀書睜開眼，書在面前 閉上眼，書在心裡