正则文法与正则表达式的相互转化问题(编译原理)实用指南

平时做技术实践时，很多问题不是概念不会，而是细节没串起来。拿“正则文法与正则表达式的相互转化问题(编译原理)”来说，它看着像小点，放到项目里常会牵出环境、配置、兼容性和维护成本。下面按实际采用顺序，把思路、关键写法和容易踩坑的地方讲清楚，便于大家直接对照操作。

前言

结合项目来看，在词法分析过程里，如果将每类单词都看作一种语言，则大多数单词词法能够用正则文法来描述。 除了正则文法外，正则表达式也能够相应的用来描述单词，正则文法和正则表达式的能力相同，且能够互相转化。正则表达式比正则文法更直观，有时首选正则表达式来表示正则语言。

一、正则文法

1.定义

结合项目来看，正则文法在这篇文章（编译原理-文法的定义与分类）中有所讲解，在此处再稍微讲述一遍：

• 理解这一步时，正则文法G = (V，T，P，S)中，对∀α —> β∈P，α β均具有形式A —> w或A —> wB(A —> w或A —> Bw)，其中A，B∈V，w∈T+。
• 正则文法描述T上的正则语言。

2.例子

例子：词法分析中标识符的文法：

二、正则表达式

1.定义

定义：设∑是一个字母表，则∑上的正则表达式及其所表示的正则语言可递归地定义如下所示：

Ø是∑上的一个正则表达式，它表示空集；

结合项目来看，ε是∑上的一个正则表达式，它表示语言{ε}；

从实现思路看，对于∀a(a∈∑)，a是∑上的一个正则表达式，它表示的正则语言是{a}；

理解这一步时，假设r和s都是∑上的正则表达式，它们表示的语言分别为L®和L(s)，则：

( r )也是∑上的正则表达式，它表示的语言为L( r )；
理解这一步时，(r|s)也是∑上的正则表达式，它表示的语言为L( r )∪L(s)；（同时操作）
理解这一步时，(r•s)也是∑上的正则表达式，它表示的语言为L( r )L(s)；（连接操作）
从实现思路看，(r*)也是∑上的正则表达式，它表示的语言为(L( r ))*；（克林闭包操作）

采用上述规则构造的表达式是∑上的正则表达式。

2.例子

例子：词法分析中标识符的正则表达式表达：

三、转换规则

1.正则文法转换为正则表达式

具体转换步骤为：

1.根据正则文法G构造正则表达式联立方程组。

在这个场景下，假设正则文法G是右线性的，其每个产生式的右部只含有一个终结符，则有如下所示方程式构造规则：

2.解联立方程组，求等价的正则表达式r。

理解这一步时，用代入消元法逐个消去方程组中除开始符号S外的其他变量，最后即可得到关于开始符号S的解。

代入消元规则如下所示：

求得结果。从实现思路看，若最后得到的关于S的方程式为如下所示形式，S=α1|α2|……|αh则将方程式右边所有其中仍然含有语法变量的αi(1≤i≤n)删除，得到的结果就是与G等价的正则表达式。如果任意的αi(1≤i≤n)均含有语法变量，则Ø就是与G等价的正则表达式。

2.正则表达式转换为正则文法

给定正则表达式r，按如下所示方法构造正则定义式，同时逐步将其转换成正则文法。

引入开始符号S，从如下所示正则定义式开始：

S—>r

结合项目来看，按如下所示规则将S—>r分解为新的正则定义式，在分解过程中根据需引入新的语法变量。

四、转换例子

1.正则文法转换为正则表达式

过程：

2.正则表达式转换为正则文法

例1.标识符定义的转换：

(1).引入 S
(2).S→ (|)*
(3).分解为
S→ A
A→(|)A|ε

例2.(a|b)*a(a|b)(a|b)

转换成正则文法：
(1).S->Aa|Ab
(2).A->Ba|Bb
(3).B->Ca
(4).C->Ca|Cb|ε

总结

正则表达式与正则文法等价：
对任意一个正则文法，存在一个定义同一语言的正则表达式；
对任意一个正则表达式，存在一个定义同一语言的正则文法。

到此这篇关于编译原理-正则文法与正则表达式的相互转化的文章就介绍到这了,更多相关正则文法转正则表达式内容请搜索脚本之家以前的文章或继续浏览下面的相关文章希望大家以后多多兼容脚本之家！