一. 文法公式
文法定义公式如下:
G = (VT , VN , P , S)
-
VT: 终结符集合
终结符就是不可以再推导的字符。
也就是说对于一个字符a,它属于终结符集合VT(a∈VT) ,a不可以再推导的字符，即不能用其他字符表示a。表现形式就是a不能单独出现在产生式左边。
-
VN: 非终结符集合
非终结符即可以继续推导的字符。
-
P: 产生式集合
产生式就是推导公式，表示这个文法的定义规则。
产生式形式α→β，其中α和β都是属于文法符合串 (VN∪VT)* 。α称为产生式的左部或者头部；β称为产生式的右部或者体。
文法符合串，即终结符集合和非终结符集合任一排列组合成的字符串。例如aAbbB, 其中 (a,b∈VT , A,B∈VN) 就是一个文法符合串。
-
S: 开始符号
即文法从这个符号
S利用产生集合P开始推导。S是一个非终结符，即 S∈VN。
一般情况下，第一个产生式左部符号就是开始符号。
二. 文法分类
Chomsky 文法分类将文法分为四种，0型文法(PSG)、1型文法(CSG)、2型文法(CFG)和3型文法(RG)。
其实不同的文法就是对产生式进行逐层限制形成的。
2.1 0型文法(PSG)
又被称为无限制文法(Unrestricted Grammar), 或者短语结构文法（Phrase Structure Grammar）
定义: 对于产生式 α→β ，α 至少包含一个非终结符。
即 α,β∈(VN∪VT)* ,
α和β都是文法符合串，并且α文法符合串中必须包含一个非终结符。
例如: aA→0bB; A0→11bB; 其中 (a,0,b∈VT),(A,B∈VN)。
为什么要叫无限制文法，明明它要求产生式的左部必须包含一个非终结符。
因为我们知道终结符是不能再推导出其他字符的，所以产生式的左部不能全是终结符组成的文法符合串(VT*)，这个是不允许的，所以产生式的左部必须包含一个非终结符。
2.2 1型文法(CSG)
又被称为上下文有关文法(Context-Sensitive Grammar)
定义：对于产生式 α→β , |α| <= |β|, 仅仅 S→ε 除外
|α|表示α这个文法符合串中字符个数。例如aAb这个字符个数就是3个。
也就是说1型文法要求产生式右部文法符合串
β的字符个数要不小于产生式左部文法符合串α的字符个数；但是空产生式(S→ε) 除外。
ε表示空串，即文法符号串中没有任何字符元素(|ε|=0)
为什么叫做上下文有关文法？
因为对于任何一个非终结符
A(即 A∈VN)，想要将它替换成其他文法符号串，必须要有对应形式的产生式。
一般情况下，这种产生式的形式为 α1Aα2→α1βα2
其中 α1,α2,β∈(VN∪VT)*, β≠ε，A∈VN。
所以对于非终结符A, 出现在α1和α2上下文中，就可以替换成文法符号串β。
例如: 对于这个产生式
1A2→112342，可以将非终结符A替换成文法符号串1234。
2.3 2型文法(CFG)
又被称为上下文无关文法(Context-Free Grammar)
定义：对任一产生式 α→β，都有 α∈VN，β∈(VN∪VT)*
对产生式左部进行了限制，
α就是非终结符集合VN中一个字符元素。
当然一个非终结符也是一个特殊的文法符号串，串中只有一个字符，且是一个非终结符。
β∈(VN∪VT)*,β表示一个文法符号串，其中空串 ε 也是一个特殊文法符号串。
所以对于2型文法也有空产生式 (S→ε)
为什么叫上下文无关文法？
因为对于任何一个非终结符
A(即 A∈VN)，可以直接根据产生式替换成一个文法符号串，而不需要特殊的上下文环境。
2.4 3型文法(RG)
又被称为正则文法（Regular Grammar，RG），分为右线性（Right Linear）文法和左线性（Left Linear）文法。
定义: 对任一产生式 α→β，都有 α∈VN，β最多两个字符元素，如果有二个字符必须是（终结符+非终结符）的格式，如果是一个字符，那么必须是终结符。
产生的左部只能是一个非终结符元素。
产生的右部最多两个字符元素 (即bB,Bb其中 b∈VT, B∈VN)，或者只有一个元素,且必须是终结符(即b, b∈VT)。
根据产生式右部非终结符位置不同，分为右线性文法和左线性文法。
- 右线性文法:
A→bB或者A→b - 左线性文法:
A→Bb或者A→b
注: 正则文法产生式集合中每个产生式有相同的线性，即所有产生式要么都是右线性文法，要么都是左线性文法。
2.5 小结
可以看出，不同文法就是对产生式进行逐层的限制，所以各个文法是包含关系，即0型文法包含1型文法；1型文法又包含2型文法；2型文法最后包含3型文法。
网友评论