第一章 第4节 文法的分类

• 0型文法 type-0 Grammar
• 1型文法 type-1 Grammar
• 2 型文法 type-2 Grammar
• 3 型文法 type-3 Grammar

0型文法

无限制文法 /短语结构文法

假设 a -> β ∈ P ，a中至少包含一个非终结符

1型文法

上下文有关文法 CSG(Context-Sensitive Grammar)

假如 a ->β ∈ P ,|a| ≤ |β|

产生式的一般形式 a1Aa2 -> a1Ba2 (B ≠ 空集), 只有上下文为a1和a2时，才可以替换 A 和 B

CSG 中不包含 空 产生式

2型文法

上下文无关文法 CFG(Context-free Grammar)

假设 a -> β ∈ P ,a 属于 Vn （非终结符集合）

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

3型文法

正则文法 (Regular Grammar)** RG**
右线性 文法 Right Linear A-> wB 或者 A -> w
左线性 文法 Left Linear A -> Bw 或者 A -> w

image.png

等价于

image.png

左线性文法：(不知道对错 自己写的)

1. S -> a | b | c | d 
2. S -> Ta | Tb | Tc | Td 
3. T -> a | b | c | d 
4. T -> Ta | Tb | Tc | Td | T1 | T2 | T3 |T4 | T5 

正则文法能描述程序设计语言的多数单词

四种文法的关系

逐级限制

image.png

逐级包含

image.png