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

前言

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

一、正则文法

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|ε

总结

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

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

最新评论