第3章 文法和语言（二）

本文主要是介绍第3章 文法和语言（二），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

四、文法和语言的形式定义

1、文法的形式定义
1）规则（重写规则、产生式或生成式）：是一个有序对（α，β）。记为α→β或
    α∷=β，其中α∈V+，β∈V* 。
    α称为规则的左部(或生成式的左部)。
    β称为规则的右部(或生成式的右部)。

2）文法G[S]：文法为四元组（VN，VT，P，S）
     VN ：非终结符集
     VT ：终结符集
     P：产生式（规则）集合
     S：开始符号（识别符号）
     VN、VT 和 P 是非空有穷集。S 至少在一条规则中作为左部出现。
     VN∩VT=φ， S∈VN
     V=VN∪VT，称为文法G的字母表（字汇表）

例: 文法G=（VN，VT，P，S）
VN = { S },  VT ={ 0, 1 }
P={ S→0S1,  S→01 }
S为开始符号

例:   文法G=（VN，VT，P，S）
VN ={标识符，字母，数字}
VT ={a,b,c,…x,y,z,0,1,…,9}
P={<标识符>→<字母>
    <标识符>→<标识符><字母>
<标识符>→<标识符><数字>
    <字母>→a,…, <字母>→z
    <数字>→0,…, <数字>→9}
S=<标识符>

习惯上只将产生式写出。并有如下约定：

• 第一条产生式的左部是开始符号
• 用尖括号括起的是非终结符，否则为终结符。或者大写字母表示非终结符，小写字母表示终结符
• G可写成G[S]，其中S是开始符号

例：G： S→0S1， S→01
0S1 =>00S11=>000S111 =>00001111  即 0S1=+>00001111
也记作 0S1=*>00001111

4、文法的句型、句子的定义

1）句型
设G[S]是一文法，如果符号串x是从识别符号推导出来的，即S=*>x，则称x是文法G[S]的句型。

2）句子
x仅由终结符号组成（即S=*>x，且x∈VT*），则称x是G[S]的句子。

例：G： S→0S1， S→01
　S =>0S1 =>00S11=>000S111 =>00001111

3）语言

 由文法G产生的所有句子组成的集合叫做文法G所成描述的语言，记为L(G)。

L(G)={x|S=*>x，其中S为文法的开始符号，且x ∈VT*}

例：G： S→0S1， S→01
                L(G)={0n1n|n≥1}
   注：产生式中含有递归式，产生的句子是无穷的

例:文法G[S]：
（1）S→dAB
（2）A→aA
（3）A→a
（4）B→Bb
（5）B→ε

1. L（G）=?
2. G生成的每个串都在L(G)中
3. L(G)中的每个串确实能被G生成

分析：n≧1，所以必须用递归规则。a和b的个数 一样多，但c的个数不同，所以将生成含 a,b的部分与生成含e的部分分开，A生成ab，B生成e.
          G[Z]:Z→AB
               A→aAb|ab
               B→eB|ε

4)文法的等价

若L（G1）=L（G2），则称文法G1和G2是等价的。

如文法G1[A]：A→0R 与 G2[S]：S→0S1 等价
             A→01           S→01
             R→A1

这篇关于第3章 文法和语言（二）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---