📄 3.2.1c.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.2.1b.htm'" src="../images/previous.gif"></td>
<td><IMG onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='3.2.2.htm'" src="../images/next.gif"></IMG></td>
</tr>
</table>
<br><br>
<table border=0>
<tr>
<td width=10></td>
<td colspan=2>
<p>例3.1的状态转换如图3.2所示。其中终态结用双圈表示。</p>
<p align="center"><IMG src="img/3.2.gif" ><br>
</p>
<p>对Σ上的任何符号串ｗ∈Σ<span class="up"><sup>*</sup></span>，若存在一条从初态结到终态结的道路，在这条路上所有箭弧标记符号连接成的符号串恰好是ｗ，则称ｗ为DFA
M所识别（或接受或读出）。DFA M所能识别的符号串的全体记为L（M），称为DFA M所识别的语言。例3.1中M所接受的语言Ｌ（M）是由{ａ，ｂ}<span class="up"><sup>*</sup></span>中所有含有相继二个为ａ或相继二个为b的符号串组成的集合。
<br>
<br>
如果我们对所有ｗ∈Σ<span class="up"><sup>*</sup></span>，以下述方式递归地扩张δ的定义：</p>
<div align=center>
δ（ｑ，ε）＝ｑ <br>
δ（ｑ，ｗａ）＝δ（δ（ｑ，ｗ），ａ）
</div>
对任何ａ∈Σ<span class="up"></span>，ｑ∈Ｑ 有
<p> Ｌ（M）＝｛ｗ｜ｗ∈Σ<span class="up"><sup>*</sup></span>，若存在ｑ∈Ｆ，使δ（ｑ<sub>0</sub>，ｗ）＝ｑ｝
<br>
上面L（M）的表示的集合，实际上是ＤＦＡ M所识别语言的形式定义。</p>
<p> 下面的算法模拟DFA的行为。</p>
<p><IMG class=dingyi src="img/liti.gif" > <b> 算法3.1</b> 模拟DFA
</td>
</tr>
<tr>
<td width=10></td>
<td colspan=2>
<table>
<tr>
<td width=190>
</td>
<td>
q:=q<sub>0</sub>; <br>
a:=nextchar; <br>
<font color=blue>WHILE</font> a <>"$" <font color=blue>DO</font> <br>
<font color=blue>BEGIN</font> <br>
q:=move(q,a); <br>
a:=nextchar; <br>
<font color=blue>END</font>; <br>
<font color=blue>IF</font> q <font color=blue>IN</font> F <br>
<font color=blue>THEN return</font> ("YES"); <br>
<font color=blue>ELSE return</font> ("NO"); <br>
<br>
</td>
</tr>
</table>
</td>
</tr>
<tr>
<td width=10></td>
<td colspan=2>
输入：输入串w，由$结尾。一个DFA M，开始状态为q<sub>0</sub>，接受状态集合为F。 <br>
输出：如果M接受w，则回答“yes”,否则回答“No” <br>
方法：上述算法施加于输入串w，函数move(q,a)给出一个状态，它是面临输入a，从状态q的变换。函数nextchar返回输入串w中的下一个字符。
<br>
</p>
<p>如果我们能构造一个DFA M，使得L(M)是编译器处理的程序语言中的单词，那么模拟DFA
M的程序将可以用作词法分析器的控制程序。 </p>
<div align=left><b>观看演示 </b><font color="blue" onmouseover="javascript:style.cursor='hand';" onclick="javascript:open('program/test3_2/page1.htm','_blank','left=100,top=100,scrollbars=yes,resizable=yes,width=850,height=600')">模拟一个DFA M识别一个输入串</font><IMG src="../images/yanshi.gif"></img></div>
</td></tr>
</table>
<table align=right width=300>
<tr>
<td><IMG onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='3.2.1b.htm'" src="../images/previous.gif"></td>
<td><IMG onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='3.2.2.htm'" src="../images/next.gif"></IMG></td>
</tr>
</table>
</BODY>
</html>
<html><script language="JavaScript">⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -