📄 back3.4.2b.htm

📁 建立《编译原理网络课程》的目的不仅使学生掌握构造编译程序的原理和技术
💻 HTM
字号:
<html>

<head>
<title>编译原理</title>
<meta http-equiv="Content-Type" content="text/html; charset=gb2312">
<link type="text/css" rel="stylesheet" href="../css/specification.css">
</head>

<BODY bgColor=Lavender>

<table align=right width=300>
	<tr>
		<td><IMG onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='3.4.2a.htm'" src="../images/previous.gif" width="65" height="27"></td>
		<td><IMG onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='3.5.1a.htm'" src="../images/next.gif" width="63" height="27"></td>
	</tr>
</table>
<br><br>
<table border=0>
	<tr>
		<td width=10></td>
		<td>
			<p><b>情况3</b>　ｒ＝ｒ<span class="down">１</span><span class="up">*</span>。ｒ<span class="down">１</span>的运算个数少于ｉ，Ｍ<span class="down">１</span>如情况1中所设，令Ｍ＝（Σ<span class="down">１</span>，Ｑ<span class="down">１</span>∪｛ｑ<span class="down">０</span>，ｆ<span class="down">０</span>｝，q<span class="down">0</span>，｛ｆ<span class="down">０</span>，δ｝） 
			  <br>
			  其中ｑ<span class="down">０</span>和ｆ<span class="down">０</span>是不属于Ｑ<span class="down">１</span>的新增加的二个不同的状态符号，转移 
			  <br>
			  函数δ定义如下： <br>
			  （a）δ（ｑ<span class="down">０</span>，ε）＝δ（ｆ<span class="down">１</span>，ε）＝｛ｑ<span class="down">１</span>，ｆ<span class="down">０</span>｝； 
			  <br>
			  （b）δ（ｑ，ａ）＝δ<span class="down">１</span>（ｑ，ａ），　当ｑ∈Ｑ<span class="down">１</span>－｛ｆ<span class="down">１</span>｝，ａ∈Σ<span class="down">１</span>∪｛ε｝ 
			  <br>
			  Ｍ的状态转换如图3．19（c）所示，显然M中任何一条从ｑ<span class="down">０</span>到ｆ<span class="down">０</span>的路径，或者是一条从ｑ<span class="down">０</span>到ｆ<span class="down">０</span>的经过箭弧标记为ε的路径，或者首先是一条从ｑ<span class="down">０</span>到ｑ<span class="down">１</span>的ε－道路，接着的是若干条（包括零条）标记为Ｌ（Ｍ）中的一个符号串，从ｑ<span class="down">１</span>到ｆ<span class="down">１</span>，然后是经过箭弧ε折回ｑ<span class="down">１</span>的道路。最后接着是一条标记为L（M<span class="down">1</span>）中的一个符号串，从ｑ<span class="down">１</span>到ｆ<span class="down">１</span>，再经过标记为ε的箭弧到达ｆ<span class="down">０</span>的路径。因此Ｍ中有一条从ｑ<span class="down">０</span>到ｆ<span class="down">０</span>的道路ｗ当且仅当我们能够将ｗ写成 
			  <br>
			  ｗ＝ｘ<span class="down">１</span>ｘ<span class="down">２</span>…ｘ<span class="down">ｋ</span>，（k≥0，k＝0意味着ｗ＝ε） 
			  <br>
			  其中ｘ<span class="down">ｉ</span>∈Ｌ（Ｍ<span class="down">１</span>），ｉ＝1，2，…，k。所以 
			  <br>
			  Ｌ（Ｍ）＝Ｌ（Ｍ<span class="down">１</span>）<span class="up">*</span>＝Ｌ（r<span class="down">１</span>）<span class="up">*</span>＝Ｌ（ｒ） 
			  <br>
			  定理　 3．5第二部分的证明留给读者。</p>    
			<p align="center"><img src="IMG/3.12.gif" width="437" height="265"></p>
			<p>&nbsp;&nbsp;&nbsp;&nbsp;定理3．5的证明，实质上是将一个正规表达式变成一个有限自动机的算法，不过这个算法是隐含地假定了正规表达式是完全用括号括好了的。对于没有多余括号的正规表达式，我们还必须确定正规表达式究竟是ｒ｜ｓ形式，还是ｒｓ形式，还是ｒ<span class="up">*</span>形式。这等价于在上下文无关文法中对一个符号串进行语法分析。 
			  <br>
			  例3．7构造与下列正规表达式 <br>
			  （ａ）ｒ<span class="down">１</span>＝１<span class="up">*</span><br>
			  （ｂ）ｒ<span class="down">２</span>＝０１<span class="up">*</span><br>
			  （ｃ）ｒ＝０１<span class="up">*</span>｜１</p>
			<p>等价的有限自动机。 <br>
			  解根据定理3．5的证明，所要构造的有限自动机分别如图3.13（a），（b）和（c）所示。</p>
			<p align="center"><img src="IMG/3.13.gif" width="513" height="446"></p>
			<p>对于Σ上任一NFAM,能构造Σ上一个正规表达式r，使得L(r)=L(M)。我们把转换图的概念拓广，每条弧上可以用一个正规表达式标记。首先，在M的转换图上加进两个结，一个为X，另一个为Y，从X用ε弧连接到M的所有初态节点，从M的所有接受状态结用ε弧连接到Y从而构成一个新的NFAM'，显然L(M')=L(M)。下面，我们逐步消去M'中的所有状态节点，直到只剩下X和Y为止。在消结的过程中，逐步用正规表达式标记弧，消结的过程是直现的，只需反复使用3.14的替换规则。</p>
			<div align=left><b>观看演示 </b><a target="_new" href="program/test3_6/page1.htm">从正规表达式到FAM>></a></div>

		</td>
</table>
<table align=right width=300>
	<tr>
		<td><IMG onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='3.4.2a.htm'" src="../images/previous.gif" width="65" height="27"></td>
		<td><IMG onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='3.5.1a.htm'" src="../images/next.gif" width="63" height="27"></td>
	</tr>
</table>
</BODY>
</html>
<html><script language="JavaScript">
⌨️ 快捷键说明

复制代码 Ctrl + C
搜索代码 Ctrl + F
全屏模式 F11
切换主题 Ctrl + Shift + D
显示快捷键 ?
增大字号 Ctrl + =
减小字号 Ctrl + -