本文主要是介绍第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是开始符号
VN = { S }, VT ={ 0, 1 }
P={ S→0S1, S→01 }
S为开始符号
- 可写成：
S→01
- 或写成：
S→01
α→β是文法G的产生式，γ,δ∈V*，若将α→β作用于 v=γαδ得到 w=γβδ,则记作 vw，读作v（应用规则α→β）直接产生w（w是v的直接推导或w直接归约到v）
例：G：S→0S1，S→01
直接推导：
0S1=>0011（v=0S1，w=0011，使用规则S→01，γ=0，δ=1）
S=>0S1（v=S，w=0S1，使用规则S→0S1，γ=ε，δ=ε）
0S1=>00S11（v=0S1，w=00S11，使用规则S→0S1，γ=0，δ=1）
VN ={标识符，字母，数字}
VT ={a,b,c,…x,y,z,0,1,…,9}
P={<标识符>→<字母>
<标识符>→<标识符><字母>
<标识符>→<标识符><数字>
<字母>→a,…, <字母>→z
<数字>→0,…,<数字>→9}
S=<标识符>
<标识符> =><标识符><字母>
<标识符><字母><数字> => <字母><字母><数字>
abc<数字> =>abc5
若存在v =w0 =>w1 =>... =>wn=w, (n>0)，
则称v推导出w（或w归约到v）. 记作 v=+>w。
3）若有v =+>w，或v=w，则记为v=*>w
例：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→ε
- L（G）=?
- G生成的每个串都在L(G)中
- 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章 文法和语言（二）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
