【软考】（一）编译原理-文法

    

    关于编译原理这块之前根本没有涉及过，这次要用到这里的知识就需要来接触一下这里的内容。编译原理顾名思义就是处理高级语言，使之称为计算机能够识别的语言（低级语言）的原理。而文法呢？就是用来描述程序设计语言的方法。类似佛法,用来描述佛家的诵经禅道的规则的。不用去纠结这个名字，知道这个含义，足以。

文法

概念

终结符和非终结符

       

如图：在p这个推导式的集合中，存在六个推导式。其中S、A、B为非终结符。a、b、c、d、q、p为终结符。终结符是原子不可分的。

分类

文法的分类也就这几种了，先看各自的定义，在定义中，先了解个大概。明白定义中一些的关键字的意思就可以了，在后面通过例子再来巩固就没有问题了。

O型文法

看到这个定义，我又想起当年高中那段如歌的日子了。哈哈！上面的定义中Vn，Vt,P,S

Vn：就是代表了非终结符。

Vt：终结符。

P：表示推导式的集合。一如在第一张图中见到的六个推导式就是p了。

S：开始符，SAB。知道了上面这些关键字是很重要的。

当推导式中，左边的推导式只要满足至少一个是非终结符那么也就是0型文法。

1型文法

定义中最重要的也就是左边的长度必须小于右边的长度，在0型的基础上。

2型文法

            、

          定义中2型文法相对1型文法，多了一个条件，也就是要求推导式的左边都是非终结符。相对于0型文法，一个要求是至少有一个，这里的要求全部为非终结符。

3型文法

     

    

    

    3型文法中的定义也就是右线性和左线性的条件只必须满足一个，这里需要注意的就是满足一个条件，所以说两个都满足是不能为3型文法的。

 

三种文法关系

   

   

实例

    通过一个实例来说明之上各个文法的含义

    

    判断上面推导式中满足什么类型的文法

     解这种题型呢 ? 首先要判断哪些是终结符和非终结符 , 简单来讲终结符就是终结的 , 最小的不可拆分的元素 , 而不是终结符的都是非终结符 . 这个应该是没有任何问题的 , 所以上题中 , 的非终结符就是 AB, 其他都是非终结符 . 而 0 型文法中 , 讲到只需要在 p 中至少有一个非终结符 , 也就是在推导式的左边至少存在一个非终结符就可以了 . 这样一来 , 我们看到在等式的左边 , 两个都是非终结符 . 肯定满足 0 型文法 , 下面就是 1 型文法了 ,1 型文法是怎么规定的呢 ? 在 0 型文法的基础上 , 推导式的左边的长度肯定小于或者等于右边的长度 , 题中 p 集合里面左边的长度都小于右边的长度 , 所以肯定符合 1 型文法 ; 接下来就是看看是否满足 2 型文法了 .2 型文法是怎么来限定的呢？在 1 型文法的基础上，在推导式的左边每个都是非终结符，如题，每个推导式的左边都是非终结符，所以肯定是 2 型文法了； 3 型文法的意思就是 2 型文法的基础上，看看是否满足右线性或者左线性，我们将这个推导式分开来判断。 A-->a 或者 A--->aB ，第一个拆开的推导式是右线性，而 B--->A 是左线性的， 3 型文法是怎么规定的呢？是符合左线性或者右线性。