当前课程知识点：编译原理 > 第3章 词法分析 > 3.6 正规文法与正规式 > 正规文法与正规式
同学们
在我们前面的学习当中
我们知道
一个正规语言可以由正规文法来定义
也可以由正规式来定义
对于任何一个正规文法
存在一个定义同一个正规语言的正规式
反之 对于每一个正规式
存在一个生成同一语言的正规文法
那么今天我们就来探讨一下
正规式和正规文法的等价性
有一些正规语言很容易用
正规文法来定义
有一些语言更容易用正规式来定义
现在我们就来介绍一下
两者之间的转换
从结构上建立它们的等价性
首先将一个正规文法
转换为正规式的规则是这样子的
对于形如A→xB B→y的产生式
改写之后的正规式是A=xy
对于形如A→xA|y
或者是A→xA A→y 的产生式
改写之后定义的产生式是A=x*y
对于形如A→x|Ay
或者是A→x A→Ay的产生式
改写之后的正规式是A=xy*
对于形如A→x A→y的产生式
改写之后的正规式是A=x|y
那么接下来它的转换步骤是这样子的
首先将每条产生式都改写成正规式
接着用代入法来求解正规式方程组
不断的收缩产生式
直到剩下一个开始符号
定义的正规式为止
并且这个等式的右部
是不含有非终结符的
接下来我们来看一个这个例子
文法的产生式分别是S→aA|a
A→dA|d
首先我们将产生式改写成为正规式
也就是说S=aA|a A=dA|d
根据规则2
得到的是A= d*d
将其代入S的正规式
我们可以得到ad*d|a
再根据分配率
就得到了a(d+|ε)
最后我们就得到了由S定义的
这样的一个正规式
S= ad*
接下来 我们再看一个经典的例子
正规文法G1它的产生式
分别是S →aS|aB
B→bB|bA
A→cA| c
求它们所定义的正规式
首先由产生式写出对应的联立方程组
这方程组是这样子的
S＝aS|aB
B＝bB|bA
A＝cA| c
接下来我们根据规则2
由式(1)S ＝aS|aB得到的是
S=a*aB=a+B ……
同理 由(2)式B ＝bB|bA得到的是
B=b+A ……
同理 由式(3)A ＝cA| c得到的是
A=c*c=c+……
那接下来我们把式(6)
代入式(5)就得到了
B=b+c+ ……
将(7)式再代入(4)式之后我们就得到了
最后的这个正则表达式
S=a+b+c+ ……
下面我们来看如何将
正规式转换成正规文法
假设S是文法的开始符号
首先形成这样的一个产生式S→r
r就是我们说到的正规式
对于形如A=xy的正规产生式
重写产生式为
A→xB B→y
对于形如A=x*y的正规产生式
重写产生式为
A→xA A→y
对于形如A=xy*这样的正规式
重写产生式为
A→x A→Ay
对于形如A=x|y的正规式
重写产生式为
A→x A→y
接下来就是不断利用
上述的规则做变换
直到每个产生式都符合
正规文法的要求为止
接下来我们就来展示一下
如何将正规式a(a|d)*
转换为相应的正规文法的过程
首先 形成这样的一个产生式
S→a(a|d)*
接下来根据规则1
将其重写为S→aA A→(a|d)*
A→(a|d)*可以根据规则3
被重写为A→(a|d)A
根据分配率的原则
将A→(a|d)A重写为
A→aA|dA A→ε
再根据规则4将其重写为
A→aA A→dA
所以最后我们形成的文法是这样子的
它的产生式规则为
P={S→aA, A→aA, A→dA, A→ε }
这个就是我们用正规式
表述的某种语言的变量声明
(int|float)id(,id)*
我们来看一下它的等价的
正规文法是什么样子的
首先形成了一个这样的产生式
D →(int | float ) id (, id )*
根据规则1
我们可以把这个正规式写成这样子
D→( int | float )L
L是什么呢
L→ id (, id )*
再根据分配率的原则
我们将D→( int | float )L改写成
D→ int L | float L
再根据规则3
将L→ id (, id )*改写成
L→ L, id | id
这样我们就得到了
文法的所有产生式
在这一节当中
我们主要探讨的是
正规文法和正则表达式之间的
相互转换
这节课就到这里
谢谢
-1.1 什么是编译原理
--什么是编译原理
--什么是编译程序
--讨论：翻译程序、汇编程序、编译程序、解释程序的区别和联系。
--练习1
-1.2 编译的基本过程
--编译的基本过程
--编译的基本过程
--练习2
-1.3 编译程序的组织
--编译程序的组织
--编译程序的组织
--练习3
-编译原理概述
-2.1 文法与语言
--文法与语言
--文法与语言
-2.2 文法和语言的形式定义
--练习1
-2.3 文法的类型
--文法的类型
--文法的类型
--练习2
-2.4 上下文无关文法及语法树
--练习3
-2.5 上下文无关文法的句型分析
--练习4
-编译理论基础作业
-3.1 词法分析概述
--词法分析概述
--词法分析概述
--练习1
-3.2 正规文法和状态转换图
--练习2
-3.3 有限状态自动机
--有限状态自动机
--有限状态自动机
--练习3
-3.4 NFA与DFA的等价性
--练习4
-3.5 正规表达式与正规集
--练习5
-3.6 正规文法与正规式
--正规文法与正规式
--正规文法与正规式
--练习6
-3.7 正规式与FA
--正规式与FA
--正规式与FA
--练习7
-词法分析作业
-4.1 自顶向下语法分析及其面临的问题
--练习1
-4.2 文法的等价转化
--文法的等价转化
--文法的等价转化
--练习2
-4.3 LL(1)文法与递归下降分析法
--练习3
-4.4 构建FIRST集合FOLLOW集合
--练习4
-4.5 LL(1)分析器工作原理
-- LL(1)分析器工作原理
-4.6 LL(1)分析表构造算法
--练习5
-5.1 自底向上的语法分析及优先分析
--练习1
-5.2 LR分析器
--LR分析器
--LR分析器
--练习2
-5.3 活前缀和LR(0)项目
-- 活前缀和LR(0)项目
--练习3
-5.4 构造识别活前缀的FA
--练习4
-5.5 LR(0)分析表构造算法
--练习5
-5.6 SLR(1)分析法
--练习6
-5.7 LR(1)分析法与LALR分析法
--练习7
-6.1 语义分析和语法制导翻译概述
--练习1
-6.2 常见中间语言简介
--常见中间语言简介
--常见中间语言简介
--练习2
-6.3 简单算术表达式和赋值语句翻译
--练习3
-6.4 布尔表达式和复制语句翻译
-6.5 拉链和回填
--拉链与回填
--拉链与回填
--练习4
-6.6 程序控制语句翻译
--程序控制语句翻译
--程序控制语句翻译
--练习5
-6.7 for循环语句的翻译
-6.8 GOTO语句和情况语句的翻译
--练习6
-6.9 含数组元素的算术表达式的翻译
--练习7
-6.10 数组元素赋值语句的翻译
--练习8
-7.1 符号表概述
--符号表概述
--符号表概述
--练习1
-7.2 符号表的建立
--符号表的建立
-- 符号表的建立
--练习2
-8.1 运行时存储空间组织概述
-8.2 运行时分配策略
--运行时分配策略
--运行时分配策略
--练习
-9.1 线性窥孔优化
--线性窥孔优化
--线性窥孔优化
-9.2 基本块及其优化方法
-9.3 循环概念
--循环概念
--循环概念
-9.4 循环优化
--循环优化
--循环优化
-代码优化作业
