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

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

文法分类体系有四种文法


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)

目录
打赏
0
0
0
0
6
分享
相关文章
编译原理复习五:属性文法与三地址码的生成(附题目与答案 超详细)
编译原理复习五:属性文法与三地址码的生成(附题目与答案 超详细)
638 0
|
9月前
根据文法求对应的语言
根据文法求对应的语言
70 0
|
9月前
编译原理——构造预测分析表(判断某字符串是否是文法G(E)的句子)
编译原理——构造预测分析表(判断某字符串是否是文法G(E)的句子)
149 0
编译原理(四) 语言及其文法的基本概念
编译原理(四) 语言及其文法的基本概念
108 0
C语言哈夫曼编码实现细则(附代码以及详细实现解释)
C语言哈夫曼编码实现细则(附代码以及详细实现解释)
337 0
编译原理 实验二:词法分析器的手动实现(基于状态机的词法分析器)
编译原理 实验二:词法分析器的手动实现(基于状态机的词法分析器)
1131 0
编译原理 实验二:词法分析器的手动实现(基于状态机的词法分析器)
C++ Primer Plus 第十一章答案 使用类
只有聪明人才能看见的摘要~( ̄▽ ̄~)~
90 0