编译原理(清华大学出版社)-- 文法和语言 -- 文法和语言的形式定义

规则(重写规则、产生式或生成式)

  • 形如 α→β 或 α::=β 的(α,β)有序对,其中α称为规则的左部,β称为规则的右部,这里的符号 →(::=)读作 "定义为",例如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

设G=(VN, VT, P, S),VN = {S, B, E}, VT = {a, b, e},P由下列产生式组成

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

若L(G1) = L(G2),则称文法G1和G2是等价的

例如文法 G[A]:

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