【编译原理】文法的分类

前言

编译原理课上布置了作业，是判断下列三种文法分别是哪种类型文法，我没怎么听，想着书上有例子，应该不难写。但我们教材和龙书好像都没怎么写（或许是我没找到），找到的只有上下文无关文法。在B站上看了下视频，又在各位大佬的博客上兜了几圈，现在略懂，写篇博客记录一下。

文法的定义

文法的形式化定义为G=(V_T，V_N，P，S)

• V_T:终结符集合，一般为小写字母、数字
• V_N:非终结符集合，一般为大写字母
• P:产生式集合，如α→β
• S:开始符号，S∈V_N

文法的分类

0型文法：又称无限制文法 或 短语结构文法

• 例：A→a, Aa→aA, AA→a, AA→Aa
• 左边至少有一个非终结符

1型文法：又称上下文有关文法

• 例：A→a, Ab→Abc, AB→Bc
• 在0型文法的基础上，左边字符个数≤右边字符个数(α→ε除外)

2型文法：又称上下文无关文法

• 例：A→a, A→aB, B→a, B→ab
• 在1型文法的基础上，限制左边不能有终结符

3型文法：又称正则文法，包含右线性文法 和 左线型文法

右线性文法

• 例：A→a, A→aB
• 产生式右边的产生式是
  1.只有终结符的格式
  2.（终结符+非终结符）的格式

左线型文法

• 例：B→a, B→cB
• 产生式右边的产生是
  1.只有终结符的格式
  2.（非终结符+终结符）的格式

注意：产生式右边的格式一定要一致，也就是说左线型和右线性不能同时出现，同时出现则不属于3型文法

四种文法之间的关系

若不考虑空产生式的话，四种文法是逐级限制的关系

所以，判断哪种文法类型时，先判断是不是3型文法，再判断是不是2型文法，是不是1型文法，最后都不是的话，就是0型文法