记录编译原理中文法的知识点 编译原理顾名思义就是处理高级语言，使之称为计算机能够识别的语言（低级语言）的原理。而文法呢？就是用来描述程序设计语言的方法。类似佛法,用来描述佛家的诵经禅道的规则的。
@toc
概念
正如英语是由句子组成的集合，而句子又是由单词和标点符号组成的序列那样。程序设计语言 C 语言，是由 C 程序所组成的集合，而程序是由类似 if , begin, end 的符号，字母和数字这样一些基本符号所组成。
从字面上看，每个程序都是一个“基本符号”串，设有一基本符号串，那么 C 语言可看成是在这个基本符号集上定义的，按一定规则构成的一切基本符号串组成的集合。
通俗的讲就是：根据一些指定的规则，来确定编程语言的语法，从而实现编译器的功能。
终结符和非终结符
文法是由非终结符（大写字母）和终结符（小写字母）以及“—>”组成的。
1 | A—> a |
通过上面的几个例子可以看出：非终结符A、B、S，一般是写在左边，而终结符a、dba、b，一般是写在右边的。当然习惯的写法是非终结符用S（Start）表示，写在左边，自然而然的小写的就在右边了，这样也便于我们记忆文法的表示方式。
1 | G2[S] |
如上所示：在这个推导式的集合中，存在六个推导式。其中S、A、B为非终结符。a、b、c、d、q、p为终结符。终结符是原子不可分的。
分类
在1956年的春天，一个叫乔姆斯基(Chomsky)的人发明了上述文法，他觉得有些文法存在着相似的形式，于是他就给文法分了一下类。
首先有一个前提：设有一个组合G=(Vn,Vt,P,S)。其中Vn是非终结符的集合，Vt是终结符的集合，P是推导式的一个集合，S是开始符。就上面的例子来说，A、B、S是Vn，a、dba、b是Vt，整个的集合为P。
0型文法
这是最简单的一个文法。它比较宽容，没有那么多的限制条件。左边必须要包含这些元素或者元素组合中的至少一个非终结符，右边可以是这些元素的任意组合，这样就构成了0型文法。由于限制最少，所以见到的文法至少是一个0型文法。如：
1 | A->a |
1型文法（上下文有关文法）
1型文法也叫上下文有关文法，此文法对应于线性有界自动机。
它在0型文法的基础之上，只添加了一个要求：右边的长度>=左边的长度（终结符或非终结符的个数）。A—> a、B—>dba则是1型文法，而adB—>d不符合1型文法要求 注意这里有一个特殊的形式 S—> ∑（∑表示空），也是一个1型文法。
2型文法（上下文无关文法）
2型文法也叫上下文有关文法，此文法对应于下推自动机自动机。
它在1型文法的基础上，有增加了一个要求：左边必须是非终结符（个数不限）。 如：AB—>de 属于2型文法，而 Aa—>DE则不是，因为Aa中含有a。
3型文法（正规文法）
3型文法也叫正规文法，它对应有限状态自动机。
它是在2型的基础上提出了要么一个非终结符推出一个终结符，要么一个非终结符推出一个终结符并且带一个非终结符。
A->a | aB（右线性）或 A->a | Ba（左线性）
而上面的左线性、右线性是相互独立的。如：A—>b、A—>bD这是3型文法
但是A—>b、A—>bD、A—>Db则不是3型文法。从这里可以看出，对于3型文法，它不是左右线性的“组合”，要么都是右线性，要么都是左线性。
三种文法关系
\[ 3\text{型文法} \subset2\text{型文法} \subset1\text{型文法} \subset0\text{型文法} \]
正规式
| item | 文法产生式 | 正规式 |
|---|---|---|
| 规则1 | \[A->xB,B->y\] | \[A=xy\] |
| 规则2 | \[A->xA\vert y\] | \[A=x^*y\] |
| 规则3 | \[A->x,A->y\] | \[A=x\vert y\] |
实例
实例1
\[ A->\varepsilon|aB,B->Ab|a \]
判断上面推导式中满足什么类型的文法
首先要判断哪些是终结符和非终结符,简单来讲终结符就是终结的,最小的不可拆分的元素,而不是终结符的都是非终结符.这个应该是没有任何问题的,所以上题中,的非终结符就是AB,其他都是非终结符.而0型文法中,讲到只需要在p中至少有一个非终结符,也就是在推导式的左边至少存在一个非终结符就可以了.这样一来,我们看到在等式的左边,两个都是非终结符.肯定满足0型文法,下面就是1型文法了,1型文法是怎么规定的呢?在0型文法的基础上,推导式的左边的长度肯定小于或者等于右边的长度,题中p集合里面左边的长度都小于右边的长度,所以肯定符合1型文法;接下来就是看看是否满足2型文法了.2型文法是怎么来限定的呢？在1型文法的基础上，在推导式的左边每个都是非终结符，如题，每个推导式的左边都是非终结符，所以肯定是2型文法了；3型文法的意思就是2型文法的基础上，看看是否满足右线性或者左线性，我们将这个推导式分开来判断。A–>a或者A—>aB，第一个拆开的推导式是右线性，而B—>A是左线性的，3型文法是怎么规定的呢？是符合左线性或者右线性。
实例2
\[ \begin{align*} &\mbox{文法}: G: S->xSx | y\mbox{所识别的语言是}（）。\\ &A. xyx\\ &B. (xyz)^*\\ &C. x^*yx^*\\ &D. x^nyx^n(n\geq0)\\ \end{align*} \]
解析：D。 \[S->xSx->xxSxx->x…S…x->x…y...x->x^nyx^n\] 因为S->y，所以 n 可以为0，即 n 的范围为大于等于0。
实例3
1 | 给定文法A->bA|ca,该文法的句子是： |
解析：C。A->bA->bca。第二次替换A的时候，使用候选式A->ca 即可。
实例4
\[ \begin{align*} &\text{对于一下编号为①，②，③的正则式，正确的说法是___。}\\ &\begin{matrix} \text{①}(aa^*|ab)^b & \text{②}(a|b)^b & \text{③}((a|b)^*|aa)^b \\ \qquad \\ \end{matrix}\\ &\begin{matrix} A. \text{正则式①，②等价} & \qquad & B. \text{正则式①，③等价}\\ C. \text{正则式②，③等价} & \qquad & D. \text{正则式①，②，③互不等价} \end{matrix} \end{align*} \]
解析：C。①中任意个前始终有b，②中为任意个a或b，故①②不等价，③中包含②并且任意长度a和故b组成的串，aa限制条件不是必要条件故②③等价。
实例5
\[ \begin{align*} &\text{语言}L=\{a^mb^n|m\geq0,n\geq1\} \text{的正规表达式是_____。}\\ &\begin{matrix} A. a^*bb^* & B. aa^*bb^* & C. aa^*b^* & D. a^*b^* \end{matrix} \end{align*} \]
解析：A。\(a^*\)代表若干个a包括零个a，\(b^*b\)表示至少一个b。 default