描述语言语法结构的规则
文法G是一个四元组，可表示为G=（VN,VT,P,S）
PS:
- VN：表示非终结符集合，一般使用大写字母表示
- VT：表示终结符集合，一般用小写字母表示
- P:表示产生式的集合
- S：表示开始符号
用产生式的右侧替换产生式的左侧，直到产生一个终结符的序列为止。
例子：
文法G[S]:S->0S1
S->01
S=>0S1=>00S11=>000111
在推导的时候有直接推导，这时候会遇见两种符号 “+” 和 “*” 这两个分表表示什么呢？
+：表示至少一次
*：表示任意次
推导分为两类：最左推导和最右推导，其中最右推导为规范推导
例子：
文法G[S]:S->aSbA
A->aA|a
S->a
如皋要得到最后的推导的结果是aabaa，使用最右推导是怎样的呢？
S=>aSbA=>aSbaA=>aSbaA=>aSbaa=>aabaa (在=>上面写r就可以了)
其实就是要在文法最右侧开始进行推导，此题中也就是aSbA的最右侧开始，最左推导就是与其相反，在aSbA的最左侧开始
用产生式的左侧替换产生式的右侧
例子：
文法G[S]:S->0S1
S->01
000111=>00S11=>0S1=>S
归约分为两种归约：最左归约和最右归约，其中最左归约为规范归约
归约就是推导的反面。
| 类 型 |
别 名 |
代 表 |
描 述 |
| 0型文法 |
短语文法 |
图灵机 |
文法的每一个产生式α->β，均有α∈（VN∪VT）^+,α至少含有一个非终结符，且β∈（VN∪VT）^*
|
| 1型文法 |
上下文有关文法 |
线性界限自动机 |
在0型的基础上，文法的每一个产生式任意α->β，且|α|<=|β|
|
| 2型文法 |
上下文无关文法 |
下推自动机 |
在1型的基础上，文法的每一个产生式α->β，且α属于非终结符
|
| 3型文法 |
正规文法 |
有限自动机 |
在2型的基础上，文法的每一个产生式任意α->β，且有类似于A->aB或者A->a(其中A,B为非终结符，a为终结符)
|
