文法的分类
# 文法的分类 -- Chomsky 文法分类体系
课件
# Type-0 Grammar(0 型文法)
- 无限制文法(Unrestricted Grammar) /短语结构文法(Phrase Structure Grammar, PSG )
, 中至少包含 1 个非终结符
- 0 型语言
- 由 0 型文法
生成的语言
- 由 0 型文法
# Type-1 Grammar(1 型文法)
- 上下文有关文法(Context-Sensitive Grammar , CSG )
- 产生式的一般形式:
- 上下文有关语言(
型语言) - 由上下文有关文法 (
型文法) 生成的语言
- 由上下文有关文法 (
# Type-2 Grammar(2 型文法)
上下文无关文法 (Context-Free Grammar, CFG)
- 产生式的一般形式:
示例
上下文无关语言(2型语言)
- 由上下文无关文法 (2型文法)
生成的语言
- 由上下文无关文法 (2型文法)
# Type-3 Grammar(3 型文法)
- 正则文法 (Regular Grammar, RG )
- 右线性(Right Linear)文法:
或 右线性文法示例
- 左线性(Left Linear)文法:
或 - 左线性文法和右线性文法都称为正则文法
- 正则文法能描述程序设计语言的多数单词
- 右线性(Right Linear)文法:
- 正则语言(3型语言)
- 由正则文法 (3型文法)
生成的语言
- 由正则文法 (3型文法)
# 四种文法之间的联系
- 逐级限制
- 0型文法:
中至少包含1个非终结符 - 1型文法(CSG):
- 2型文法(CFG):
- 3型文法(RG):
或 ( 或 )
- 0型文法:
- 逐级包含
示意图
编辑 (opens new window)