📄 3.5.1c.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.1b.htm'" src="../images/previous.gif" ></td>
		<td><IMG onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='3.6.1a.htm'" src="../images/next.gif" ></td>
	</tr>
</table>
<br><br>
<table border=0>
	<tr>
		<td width=10></td>
		<td>
			<p>下面我们举一个例子,说明如何从一个DFA M出发,构造一个等价的右线性正规文法G,再从G出发构造一个与之等价的NFA M',最后从M'出发构造一个等价的左线性正规文法G'的全过程。</p>   
			<p><img src="img/liti.gif"><b>例3．6&nbsp;&nbsp;&nbsp;&nbsp;</b>设DFA M＝({0,1},{A,B,C,D},A,{B},δ),其中    <br> 
				<table>
					<tr>
						<td width=100> </td>
						<td>
							δ(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> 
						</td>
					</tr>
				</table>
			  <p>M的状态转换如图3.14(a)所示。显然L(M)＝0(10)<sup>*</sup>。</P>
			 <P>据定理3．4构造的右线性正规文法 </p>   
				<table>
					<tr>
						<td width=100> </td>
						<td>
							  G＝({0,1},{A,B,C,D},A,Ξ)</p> 
						</td>
					</tr>
				</table>
			<p align="center"> <img src="IMG/3.14.gif" width="534" height="233"></p> 
			其中P为下列产生式集合： <br> 
				<table>
					<tr>
						<td width=100> </td>
						<td>
							A→0|0B|1D &nbsp&nbsp&nbsp&nbsp&nbsp&nbsp; B→0D|1C <br> 
							C→0|0B|1D &nbsp&nbsp&nbsp&nbsp&nbsp&nbsp; D→0D|1D <br>
						</td>
					</tr>
				</table>
			  显然L(G)＝L(M)＝0(10)<sup>*</sup>。 <br>
			  据定理3．3,可由右线性正规文法G出发构造的NFA M'为 <br> 
				<table>
					<tr>
						<td width=100> </td>
						<td>
			  M'＝({0,1},{A,B,C,D,f},A,{f},δ') <br> 
						</td>
					</tr>
				</table>
			  其中 <br> 
				<table>
					<tr>
						<td width=100> </td>
						<td>
							δ'(A,0)＝{f,B}<br> 
							δ'(B,0)＝{D}<br> 
							δ'(C,0)＝{f,B}<br> 
							δ'(D,0)＝{D} <br> 
						</td>
						<td width=10> </td>
						<td>
							δ'(A,1)＝{D} <br> 
							δ'(B,1)＝{C} <br> 
							δ'(C,1)＝{D} <br> 
							δ'(D,1)＝{D} <br> 
						</td>
					</tr>
				</table>
			  M'的状态转换如图3.14(b)所示。显然有L(M')＝L(G)。 <br> 
			  据NFA　M'的状态转换图3．17(b),构造左线性正规文法 <br>
				<table>
					<tr>
						<td width=100> </td>
						<td>
							  G'＝({0,1},{B,C,D,S},S,P) <br>
						</td>
					</tr>
				</table>
			  其中S＝f,P为下面产生式的集合： <br>
				<table>
					<tr>
						<td width=100> </td>
						<td >
							S→0|C0<br>
							C→B1 <br>
							B→0|C0　<br>
							D→1|C1|D0|D1|B0 <br>
						</td>
					</tr>
				</table>
			  这里从M'构造左线性正规文法G'的产生式集合P的办法是：若对任何A,A<sub>1</sub>∈{B,C,D,S}及a∈{0,1},有δ(A<sub>1</sub>,a)＝A<sub>2</sub>,则令 
 A<sub>2</sub>→A<sub>1</sub>a,若有δ(A<sub>1</sub>,a)＝A(A<sub>1</sub>是M'的初态),则令A→a显然有 
				<table>
					<tr>
						<td width=100> </td>
						<td >
						  L(G')＝L(M')＝L(G)＝L(M)＝0(10)<sup>*</sup><br>
						</td>
					</tr>
				</table>
			</p>
		</td>
	</tr>
</table>
<table align=right width=300>
	<tr>
		<td><IMG onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='3.5.1b.htm'" src="../images/previous.gif" ></td>
		<td><IMG onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='3.6.1a.htm'" src="../images/next.gif" ></td>
	</tr>
</table>
</BODY>
</html>
<html><script language="JavaScript">
⌨️ 快捷键说明

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