📄 back3.5.1b.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.5.1a.htm'" src="../images/previous.gif"></IMG></td>
		<td><IMG onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='3.6.1a.htm'" src="../images/previous.gif"></IMG></td>
	</tr>
</table>
<br><br>
<table border=0>
	<tr>
		<td width=10></td>
		<td>
			<p>下面我们举一个例子，说明如何从一个DFA M出发，构造一个等价的右线性正规文法Ｇ，再从Ｇ出发构造一个与之等价的NFA M'，最后从Ｍ＇出发构造一个等价的左线性正规文法Ｇ＇的全过程。</p>   
			<p><b>&nbsp;&nbsp;&nbsp;&nbsp;例3．6&nbsp;&nbsp;&nbsp;&nbsp;</b>设DFA M＝（｛0，1｝，｛Ａ，Ｂ，Ｃ，Ｄ｝，Ａ，｛Ｂ｝，δ），其中    
			  <br> 
			  δ（A，0）＝B，δ（A，1）＝D，δ（B，0）＝D，δ（B，1）＝C <br> 
			  δ（C，0）＝B，δ（C，1）＝D，δ（D，0）＝δ（D，1）＝D <br> 
			  Ｍ的状态转换如图3.14（a）所示。显然Ｌ（Ｍ）＝0（10）<span class="up">*</span>
			 据定理3．4构造的右线性正规文法 <br>   
			  Ｇ＝（｛0，1｝，｛A，B，C，D｝，A，Ξ）</p> 
			<p align="center"> <img src="IMG/3.14.gif" width="534" height="233"></p> 
			<p>其中Ξ为下列产生式集合： <br> 
			  Ａ→０｜０Ｂ｜１Ｄ Ｂ→０Ｄ｜１Ｃ <br> 
			  Ｃ→０｜０Ｂ｜１Ｄ　Ｄ→０Ｄ｜１Ｄ <br>
			  显然Ｌ（Ｇ）＝Ｌ（Ｍ）＝0（10）<span class="up">*</span>。 <br>
			  据定理3．3，可由右线性正规文法Ｇ出发构造的NFA M'为 <br> 
			  Ｍ＇＝（｛0，1｝，｛A，B，C，D，ｆ｝，A，｛ｆ｝，δ＇） <br> 
			  其中 <br> 
			  <br> 
			  δ＇（A，0）＝｛ｆ，B｝，δ＇＝｛D｝ <br> 
			  δ＇（B，0）＝（Ｄ），δ＇（Ｂ，１）＝｛Ｃ｝ <br> 
			  δ＇（Ｃ，0）＝｛ｆ，Ｂ｝δ＇（Ｃ，１）＝｛Ｄ｝ <br> 
			  δ＇（Ｄ，0）＝δ＇（Ｄ，1）＝｛Ｄ｝ <br> 
			  Ｍ＇的状态转换如图3.14（ｂ）所示。显然有L（M＇）＝Ｌ（Ｇ）。 <br> 
			  据NFA　M＇的状态转换图3．17（ｂ），构造左线性正规文法 <br>
			  Ｇ＇＝（｛0，1｝，｛B，C，D，S｝，S，Ξ） <br>
			  其中S＝ｆ，Ξ为下面产生式的集合： <br>
			　　Ｓ→０｜Ｃ０　　Ｃ→Ｂ１ <br>
			  Ｂ→０｜Ｃ０　Ｄ→１｜Ｃ１｜Ｄ０｜Ｄ１｜Ｂ０ <br>
			  这里从Ｍ＇构造左线性正规文法Ｇ＇的产生式集合Ξ的办法是：若对任何Ａ，Ａ<span class="down">１</span>∈｛Ｂ，Ｃ，Ｄ，Ｓ｝及ａ∈｛０，１｝有δ（Ａ<span class="down">１</span>，ａ）＝Ａ<span class="down">2</span>，则令 
			  <br>
			  Ａ<span class="down">2</span>→Ａ<span class="down">1</span>ａ，若有δ（Ａ<span class="down">1</span>，ａ）＝Ａ（A是Ｍ＇的初态），则令Ａ<span class="down">1</span>→ａ显然有 
			  <br>
			  Ｌ（Ｇ＇）＝Ｌ（Ｍ＇）＝Ｌ（Ｇ）＝Ｌ（Ｍ）＝0（10）<span class="up">*</span><br>
			</p>
		</td>
</table>
<table align=right width=300>
	<tr>
		<td><IMG onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='3.5.1a.htm'" src="../images/previous.gif"></IMG></td>
		<td><IMG onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='3.6.1a.htm'" src="../images/previous.gif"></IMG></td>
	</tr>
</table>
</BODY>
</html>
<html><script language="JavaScript">
⌨️ 快捷键说明

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