文法和语言
终结符和非终结符
终结符可以简单地理解为「推导到这里就终结了」，也就是说不能再继续通过生成式向下推倒的元素就是终结符。
比如 T->abc。T 推导为串 abc 后已经得到了实质上的字符，不用在向下推导了，那么 T 为非终结符，abc 无法继续推导，则为终结符。（在一系列生成式中，式子左边的一定是非终结符，从未出现在式子左边的一定是终结符）
句子与句型
如果符号串x是由起始符号推导出的，则称x是文法G[S]的句型。
如果x中只包含终结符，则称x是文法G[S]的句子。
文法描述的语言是该文法一切句子的集合。
四种文法
0型文法：α→β，其中α至少包含一个非终结符。
1型文法（上下文有关文法）：α→β，其中|β|≥|α|，S→ε除外。
2型文法（上下文无关文法）：a→β，其中a是一个非终结符。
3型文法（规范文法）：A→a或A→aB.
4种文法是逐渐增加限制的，所以规范文法一定是0型文法、1型文法、2型文法，上下文无关文法也一定是0型文法、1型文法…
上下文有关文法与上下文无关文法
在应用一个产生式进行推导时，前后已经推导出的部分结果就是上下文。上下文无关指，只要文法的定义里有某个产生式，不管一个非终结符前后的串是什么，就可以应用相应的产生式进行推导。
上下文无关文法例子：
1 | 产生式： |
这个文法可以生成如下句子（共 16 种组合）：
｛人吃饭，天下雨，人吃肉，天下雪，人下雪，天下饭，天吃肉，……｝
可以看到，其中有一些搭配在语义上是不恰当的，例如”天吃肉“。其（最左）推导过程为：
Sent -> SVO -> 天VO -> 天吃O -> 天吃肉
而上下文有关文法例子如下：
1 | Sent -> S V O |
可以看到，这里对 V 的推导过程施加了约束：虽然 V 还是能推出”吃“和”下“两个词，但是仅仅当 V 左边是”人“时，才允许它推导出”吃“；而当 V 左边是”天“时，允许它推导出”下“。这样通过上下文的约束，就保证了主谓搭配的一致性。类似地，包含 O 的产生式也约束了动宾搭配的一致性。（就是语法的强约束条件，导致上下文有关了）
这样一来，这个语言包含的句子就只有｛人吃饭，天下雨，人吃肉，天下雪｝这四条，都是语义上合理的。
以”人吃饭“为例，推导过程为：
Sent -> SVO -> 人VO -> 人吃O -> 人吃饭
（这与语法的歧义性还是不同的，要有所区分）
1型文法比2型文法识别的语言集合更大？
上例看到，感觉上下文有关文法所解释的句子集合更少。
这里的“1型文法比2型文法识别的语言集合更大” 这里的集合不是产生的结果集（字符串集合），而是语言规则集。 2型文法规则一定是1型文法规则，而有些语言能用1型文法规则描述，但用2型文法规则描述不出来。