令人头疼的编译原理之文法

提到“编译原理”，大部分人的首要反应就是苦恼。确实，编译原理这一部分的内容在计算机学习中是比较难以理解的一部分。首次接触编译原理，我也感觉很复杂，难以理解。但是当看过几次之后，对于一些简单知识点的理解就有点眉目了。在这里就将有点眉目的知识写一下。

学习编译原理接触的第一个重要的概念就是——文法。那么什么是文法呢？

文法，语言中的每个句子可以用严格定义的规则来构造。通俗的讲就是：根据一些指定的规则，来确定编程语言的语法，从而实现编译器的功能。

那么文法是如何表示的呢？

文法是由非终结符（大写字母）和终结符（小写字母）以及“—>”组成的。给出几个例子就容易理解了。

A—> a、B—>dba、S—> Ab、adB—>d

通过上面的几个例子可以看出：非终结符A、B、S，一般是写在左边，而终结符a、dba、b，一般是写在右边的。当然习惯的写法是非终结符用S（Start）表示，写在左边，自然而然的小写的就在右边了，这样也便于我们记忆文法的表示方式。

话说，在1956年的春天，一个叫乔姆斯基(Chomsky)的人发明了上述文法，他觉得有些文法存在着相似的形式，于是他就给文法分了一下类。

首先有一个前提：设有一个组合G=(Vn,Vt,P,S)。其中Vn是非终结符的集合，Vt是终结符的集合，P是推导式的一个集合，S是开始符。就上面的例子来说，A、B、S是Vn，a、dba、b是Vt，整个的集合为P。

0型文法

这是最简单的一个文法。它比较宽容，没有那么多的限制条件。左边必须要包含这些元素或者元素组合中的至少一个非终结符，右边可以是这些元素的任意组合，这样就构成了0型文法。由于限制最少，所以见到的文法至少是一个0型文法。如：A—> a

1型文法（上下文有关文法）

它在0型文法的基础之上，只添加了一个要求：右边的长度>=左边的长度（终结符或非终结符的个数）。A—> a、B—>dba则是1型文法，而adB—>d不符合1型文法要求

注意这里有一个特殊的形式  S—> ∑（∑表示空），也是一个1型文法。

2型文法（上下文无关文法）

它在1型文法的基础上，有增加了一个要求：左边必须是非终结符（个数不限）。

如：AB—>de 属于2型文法，而 Aa—>DE则不是，因为Aa中含有a。

3型文法（正规文法）

它是在2型的基础上提出了要么一个非终结符推出一个终结符，要么一个非终结符推出一个终结符并且带一个非终结符。

而上图中的左线性、右线性是相互独立的。如：A—>b、A—>bD这是3型文法

但是A—>b、A—>bD、A—>Db则不是3型文法。从这里可以看出，对于3型文法，它不是左右线性的“组合”，要么都是右线性，要么都是左线性。

好了，关于文法就说这么对。对于文法还是通过实战来促进理解比较好。