大家好，又见面了，我是你们的朋友全栈君。
文法(Grammar)：
G={VT，VN，S，P}
VT是一个非空有限的符号集合，它的每个元素称为终结符号（Terminal）
VN是一个非空有限的符号集合，它的每个元素称为非终结符号（Non-Terminal）
S∈VN，称为文法G的开始符号
P是一个非空有限集合，它的元素称为产生式。
VT∩VN=∅
产生式，其形式为α→β，α称为产生式的左部，β称为产生式的右部，符号“→”表示“定义为”，并且α、β∈(VT∪VN) *，α≠ε，即α、β是由终结符和非终结符组成的符号串。
开始符S必须至少在某一产生式的左部出现一次。
另外可以对形式α→β，α→γ的产生式缩写为α→β|γ，以方便书写。
解释：
(VT∪VN) *：也就是VT∪VN的Kleene闭包
α≠ε：α不等于空符号串
用小写字母代表终结符，如：abc……，不能被拆分
用大写字母代表非终结符，如：ASBX……，可以被拆分
著名语言学家NoamChomsky(乔姆斯基)根据对产生式所施加的限制的不同，把文法分成四种类型，即0型、1型、2型和3型。
文法类型 | 产生式的限制 | 文法产生的语言 |
|---|---|---|
0型文法 | α→β 其中α、β∈(VT∪VN) *，∣α∣≠0 | 0型语言 |
1型文法 | α→β 其中α、β∈(VT∪VN) *，∣α∣≤∣β∣ | 1型语言，即上下文有关语言 |
2型文法 | A→β 其中A∈VN，β∈(VT∪VN) * | 2型语言，即上下文无关语言 |
3型文法 | A→α|αB(右线性)或A→α|Bα(左线性) 其中，A，B∈VN，α∈VT∪{ ε} | 3型语言，即正规语言， 又分为左线性语言和右线性语言 |
0型文法：α∈(VT∪VN) * 且至少含有一个非终结符，而β∈(VT∪VN) *
例：A→a，Aa→a,aA→a(左边至少有一个大写字母)
1型文法：有一特例：α→ε也满足1型文法。
例：A→a，A→ab，Aa→BAc（左边至少有一个大写字母，且左边的长度小于等于右边的长度）
2型文法：每一个A→β都有A是非终结符
例：A→a，A→ab，AB→BAc（在1型文法的前提下，左边必须都是大写字母）
3型文法：如有：A→a,A→aB,B→a,B→cB，则符合3型文法的要求。
但如果推导为：A→ab,A→aB,B→a,B→cB或推导为：A→a,A→Ba,B→a,B→cB则不符合3型方法的要求了。
例子：A→ab,A→aB,B→a,B→cB中的A→ab不符合3型文法的定义,如果把后面的ab,改成aB(即“一个非终结符＋一个终结符”)就对了。
例子：A→a,A→Ba,B→a,B→cB中如果把B→cB改为B→Bc的形式就对了，因为A→α|αB(右线性)和A→α|Bα(左线性)两套规则不能同时出现在一个语法中，只能完全满足其中的一个，才能算3型文法。
如果所有的终端结点都是与终结符关联的，每棵推导树的终端结点自左至右所构成的字符串应该是文法G的一个句型，则该字符串是文法G的一个句子，此时该推导树是完全推导树。
如：文法G=（{a,b}，{S,A},S,P）,其中：S→aAS|a,A→SbA|SS|ba,句型aabAa相对应的构造树。
解释：
文法G={VT，VN，S，P}，即VT={a,b}，VN={S,A}
S→aAS|a，即S→aAS，S→a
A→SbA|SS|ba，即A→SbA，A→SS，A→ba
发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/105720.html原文链接：https://javaforall.cn
