编译原理 文法分类以及判别 我们说人话。

文法一共4类，看课本的定义非常晦涩。

我尝试着用通俗的话语讲解这4类文法。

 

我们结合各个博主的说法，来形成我们自己的说法。

我们看到的文法都至少属于0型文法。1型、2型、3型都逐步对0型文法加条件。非常正确。

（有一点要注意，尽管0型到3型文法范围变小，但是每种文法产生的语言增多了，所以文法多少和语言多少没有联系。）

图源自http://www.cnblogs.com/hexiaochun/articles/2480993.html

首先先把符号搞清楚。

什么是“终结符”？

由这个符号（或者是字符串）不能够再产生具体化的字符了，举个例子，假设我们英语中只有小写字母，而我们定义L这个大写字母表示abcde等等26个小写字母中的任意一个，那么这一串字符   “qewLsafd”  是可以产生更具体的字符串，因为L可以变化成26个小写字母中的任意一个字母。用式子写起来，就比较高大上了——  L -> a|b|c|d|...|z 。 终结符是字符的最基础元素，不是一个集合，是一个元素。

什么是“非终结符”？

就是上面解释里面的大写字母L。

 

我们看课本上的规定，可以发现，

大写字母 A等 代表 非终结符，

希腊字母 α、β等 代表 至少包含一个终结符的字符串，

小写字母 a等 代表 终结符。

 

那么，

0型文法的推导式是

     α->β

 

没啥好说的，碰到的文法都至少是0型文法，此种文法人称“递归可举集”

 

1型文法，相比于0型文法，加了|α|<=|β|，就是字符串变长了。  什么是变长？通俗说就是有几个字符，ABC 就比 αC 长，aA比aaaa短。此种文法人称“上下文有关文法”

α->β,  其中|α|<=|β|。

 

2型文法，相比于1型文法，又加了α中没有终结符，也就是说，α实际上是 非终结符，可以用任意一个大写字母表示，我们用A。

α->β,  其中|α|<=|β|，而且α中没有终结符。此种文法人称“上下文无关文法”。

也就是   A->β 。

 

3型文法，相比于2型文法，又加了左线性或者是右线性。什么是“左线性”？就是终结符统一在左边，“右线性”同理。其中要注意的是，你要么加左线性，要么加右线性，同时加就不可以了，就不符合3型文法了。 那么什么是“在左边”？假设说你本来是A，那么“在左边”是在本体的左边，也就是aA，a就在A的左边。那我只有a，也就是A -> a行不行？当然行了，这样你就已经在“最左边”了呀。此种文法人称“正规文法”。

 

A -> aA | a  或者是  A -> Aa | a

 

 

 

在判别4类文法的时候，从0开始判别。

这种文法至少是0型，就看其能爬到几型了。

到不了1型，那么就只能是0型；

到了1型看是不是2型，到不了2型那么就是1型；

到了2型看是不是3型，到不了3型那么就是2型；

加油！加油！加油！