编译原理第二章——文法分类

2020-10-02

语言和文法

编译原理第二章文法分类，紫书内容和mooc知识总结，重新回顾了4种文法的知识。

文法分类

乔姆斯基把语言文法分成4类，0型，1型，2型，3型，这几类文法的差别主要在于对产生式的限制不同，等级越高，限制越严格。

0型文法

0型文法是文法限制最弱的一种类型，0型文法的能力又被相当于图灵机模型，或者说任何0型文法都是递归可枚举的，反之，递归可枚举的一定是一个0型语言。

定义：
设$G=(V_N,V_T,P,S)$，如果$P$中的每一个产生式$\alpha$->$\beta$满足条件：

$\alpha \in (V_N \cup V_T)^*$且至少含有一个非终结符。
$\beta \in (V_N \cup V_T)^*$

0型例子：
0型实例

1型文法——上下文有关文法

1型文法中最主要的限制条件主要是对于产生式P均满足$|\beta| \ge|\alpha|$,仅$S \rightarrow \epsilon$除外。
等价定义：

1型例子：
1型文法

2型文法——上下文无关文法

2型文法对应的是下推自动机模型，常用于描述高级语言的语法规则。
定义：
设$G=(V_N,V_T,P,S)$，如果$P$中的每一个产生式$\alpha$->$\beta$满足条件：

$\alpha$是一个非终结符。
$\beta \in (V_N \cup V_T)^*$

2型例子：
在这里插入图片描述

3型文法——正规文法

正规文法对应的是有穷自动机，用来描述高级语言的词法规则
定义：
设$G=(V_N,V_T,P,S)$，如果$P$中的每一个产生式$\alpha$->$\beta$都是$A->aB$或者$A->a$的形式，其中A，B都是非终结符，$a \in V_T^*$即就是，由一个非终结符推导出一个终结符或者一个终结符+一个非终结符构成的字串。

正规文法例子：
这里尖括号括起来的是非终结符，其他的是终结符。

4种文法的定义的限制是逐步增强的，四种文法是逐步包含的，因此每一种正规文法都是上下文无关的，每一种上下文无关文法都是上下文有关的，每一种上下文有关文法都是0型文法。