正则文法与正则表达式的相互转化问题(编译原理)
<div id="navCategory"><h5 class="catalogue">目录</h5><ul class="first_class_ul"><li><a href="#_label0">前言</a></li><li><a href="#_label1">一、正则文法</a></li><ul class="second_class_ul"><li><a href="#_lab2_1_0">1.定义</a></li><li><a href="#_lab2_1_1">2.例子</a></li></ul><li><a href="#_label2">二、正则表达式</a></li><ul class="second_class_ul"><li><a href="#_lab2_2_2">1.定义</a></li><li><a href="#_lab2_2_3">2.例子</a></li></ul><li><a href="#_label3">三、转换规则</a></li><ul class="second_class_ul"><li><a href="#_lab2_3_4">1.正则文法转换为正则表达式</a></li><li><a href="#_lab2_3_5">2.正则表达式转换为正则文法</a></li></ul><li><a href="#_label4">四、转换例子</a></li><ul class="second_class_ul"><li><a href="#_lab2_4_6">1.正则文法转换为正则表达式</a></li><li><a href="#_lab2_4_7">2.正则表达式转换为正则文法</a></li></ul><li><a href="#_label5">总结</a></li><ul class="second_class_ul"></ul></ul></div><p class="maodian"><a name="_label0"></a></p><h2>前言</h2><p>在词法分析过程中，如果将每类单词都看作一种语言，则大多数单词词法可以用正则文法来描述。 除了正则文法外，正则表达式也可以相应的用来描述单词，正则文法和正则表达式的能力相同，且可以互相转化。正则表达式比正则文法更直观，有时首选正则表达式来表示正则语言。</p>
<p class="maodian"><a name="_label1"></a></p><h2>一、正则文法</h2>
<p class="maodian"><a name="_lab2_1_0"></a></p><p class="maodian"><a name="_lab2_2_2"></a></p><h3>1.定义</h3>
<p>正则文法在这篇文章（<a href="https://www.jb51.net/program/2940407es.htm" target="_blank">编译原理-文法的定义与分类</a>）中有所讲解，在此处再稍微讲述一遍：</p>
<ul><li>正则文法G = (V，T，P，S)中，对∀α —> β∈P，α β均具有形式A —> w或A —> wB(A —> w或A —> Bw)，其中A，B∈V，w∈T+。</li><li>正则文法描述T上的正则语言。</li></ul>
<p class="maodian"><a name="_lab2_1_1"></a></p><p class="maodian"><a name="_lab2_2_3"></a></p><h3>2.例子</h3>
<p>例子：词法分析中标识符的文法：</p>
<p style="text-align:center"><img alt="" src="https://img.jbzj.com/file_images/article/202308/2023080211095517.png" /></p>
<p class="maodian"><a name="_label2"></a></p><h2>二、正则表达式</h2>
<h3>1.定义</h3>
<p>定义：设∑是一个字母表，则∑上的正则表达式及其所表示的正则语言可递归地定义如下：</p>
<p>⑴ Ø是∑上的一个正则表达式，它表示空集；</p>
<p>⑵ ε是∑上的一个正则表达式，它表示语言{ε}；</p>
<p>⑶ 对于∀a(a∈∑)，a是∑上的一个正则表达式，它表示的正则语言是{a}；</p>
<p>⑷ 假设r和s都是∑上的正则表达式，它们表示的语言分别为L®和L(s)，则：</p>
<p>( r )也是∑上的正则表达式，它表示的语言为L( r )；<br />(r|s)也是∑上的正则表达式，它表示的语言为L( r )∪L(s)；（并操作）<br />(r•s)也是∑上的正则表达式，它表示的语言为L( r )L(s)；（连接操作）<br />(r*)也是∑上的正则表达式，它表示的语言为(L( r ))*；（克林闭包操作）</p>
<p>⑸ 使用上述规则构造的表达式是∑上的正则表达式。</p>
<h3>2.例子</h3>
<p>例子：词法分析中标识符的正则表达式表达：</p>
<p style="text-align:center"><img alt="在这里插入图片描述" src="https://img.jbzj.com/file_images/article/202308/2023080211095518.png" /></p>
<p class="maodian"><a name="_label3"></a></p><h2>三、转换规则</h2>
<p class="maodian"><a name="_lab2_3_4"></a></p><p class="maodian"><a name="_lab2_4_6"></a></p><h3>1.正则文法转换为正则表达式</h3>
<p style="text-align:center"><img alt="" height="589" src="https://img.jbzj.com/file_images/article/202308/2023080211095519.jpg" width="1000" /></p>
<p>具体转换步骤为：</p>
<p><strong>1.根据正则文法G构造正则表达式联立方程组。</strong></p>
<p>假设正则文法G是右线性的，其每个产生式的右部只含有一个终结符，则有如下方程式构造规则：</p>
<p style="text-align:center"><img alt="" height="344" src="https://img.jbzj.com/file_images/article/202308/2023080211095520.jpg" width="1000" /></p>
<p><strong>2.解联立方程组，求等价的正则表达式r。</strong></p>
<p>用代入消元法逐个消去方程组中除开始符号S外的其他变量，最后即可得到关于开始符号S的解。</p>
<p>代入消元规则如下：</p>
<p style="text-align:center"><img alt="" height="565" src="https://img.jbzj.com/file_images/article/202308/2023080211095521.jpg" width="1000" /></p>
<p><strong>求得结果。</strong>如果最后得到的关于S的方程式为如下形式，S=α1|α2|…|αh则将方程式右边所有其中仍然含有语法变量的αi(1≤i≤n)删除，得到的结果就是与G等价的正则表达式。如果任意的αi(1≤i≤n)均含有语法变量，则Ø就是与G等价的正则表达式。</p>
<p class="maodian"><a name="_lab2_3_5"></a></p><p class="maodian"><a name="_lab2_4_7"></a></p><h3>2.正则表达式转换为正则文法</h3>
<p>给定正则表达式r，按如下方法构造正则定义式，并逐步将其转换成正则文法。</p>
<p>引入开始符号S，从如下正则定义式开始：</p>
<p>S—>r</p>
<p>按如下规则将S—>r分解为新的正则定义式，在分解过程中根据需要引入新的语法变量。</p>
<p style="text-align:center"><img alt="在这里插入图片描述" src="https://img.jbzj.com/file_images/article/202308/2023080211095522.png" /></p>
<p class="maodian"><a name="_label4"></a></p><h2>四、转换例子</h2>
<h3>1.正则文法转换为正则表达式</h3>
<p style="text-align:center"><img alt="在这里插入图片描述" src="https://img.jbzj.com/file_images/article/202308/2023080211095523.png" /></p>
<p><strong>过程：</strong></p>
<p style="text-align:center"><img alt="在这里插入图片描述" src="https://img.jbzj.com/file_images/article/202308/2023080211095524.png" /></p>
<h3>2.正则表达式转换为正则文法</h3>
<p>例1.标识符定义的转换：</p>
<p>(1).引入 S<br />(2).S→ (|)*<br />(3).分解为<br />S→ A<br />A→(|)A|ε</p>
<p>例2.(a|b)*a(a|b)(a|b)</p>
<p>转换成正则文法：<br />(1).S->Aa|Ab<br />(2).A->Ba|Bb<br />(3).B->Ca<br />(4).C->Ca|Cb|ε</p>
<p class="maodian"><a name="_label5"></a></p><h2>总结</h2>
<p>正则表达式与正则文法等价：<br />对任意一个正则文法，存在一个定义同一语言的正则表达式；<br />对任意一个正则表达式，存在一个定义同一语言的正则文法。</p>
頁:
[1]