编译原理(六) 文法的分类

文法分类体系有四种文法

1. 0型文法

无限制文法, 或者短语结构文法

任意a -> b ∈ p ,a中至少包含一个非终结符

由0型语法形成的语言称为0型语言

2. 1型文法(CSG)

上下文有关文法

任意a -> b ∈ P, |a| <= |b|

产生式的一般形式 a1 A a2 -> a1 β a2 (β != ε)

CSG中不包含空串

由上下文有关语法形成的语言称为上下文有关语法

3. 2型文法(CFG)

上下文无关语法

任意a -> b ∈ P a ∈ Vn

产生式一般形式: A -> β

例:

S -> L | LT

T -> L| D | TL | TD

L -> a | b | c | d |…|z

D -> 0 | 1 | 2 | 3 | … | 9

4. 3型文法(RG)

正则文法

右线性文法 : A -> wB 或者 A->w

左线性文法 : A ->Bw 或者 A->w

左线性文法和右线性文法都称为正则文法

例 :

S -> a | b | c | d

S ->aT | bT | cT | dT

T -> a | b | c | d | 0 | 1 | 2 | 3 | 4 | 5

T ->aT | bT | cT | dT | 0T | 1T |2T | 3T | 4T | 5T

5.四种文法关系

逐级限制

0型文法要求a至少包含1个非终结符

1型文法要求 |a| <= |b|

2型文法要求 a ∈ Vn

3型文法要求 A -> wB 或 A -> w (A -> Bw 或 A ->w)