📄 3.2.1a.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.1.3.htm'" src="../images/previous.gif"></IMG></td>
<td><IMG onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='3.2.1b.htm'" src="../images/next.gif"></IMG></td>
</tr>
</table>
<br><br>
<table border=0>
<tr>
<td colspan=3>
<font class="title2"><b>3.2 词法分析器的构造</b></font>
</td>
</tr>
<tr>
<td height="190%" colspan="3"><br>
<p>为了构造词法分析器，我们不仅要研究词法，每种词类的结构模式，而且要研究识别它的数学模型——有限自动机。有限自动机是由集合、序列和函数定义的纯数学概念，通过对它性能和工作情况的研究，可以用程序模拟它的工作，而这个模拟程序可以作为词法分析器的控制程序。</p>
<hr size=2 width=100% align=center color=red>
</td>
</tr>
<tr>
<td width=5></td>
<td colspan=2>
<br>
<b>3.2.1 确定的有限自动机（Deterministic Finite Automate）</b><br><br>
</td>
</tr>
<tr>
<td width=10></td>
<td colspan=2>
<p>确定的有限自动机是一种受限定的有限自动机，它对于字母表Σ上的输入序列W，判定是可接受的还是不可接受的。</p>
<p>例如，我们要设计一个确定的有限自动机M，它接受Σ ={0，1}上含有奇数个1的所有序列，拒绝含有偶数个1的序列。尽管它是个数学模型，我们可以把它看成一个假想的计算机，称它为奇偶检验器。</p>
<p>可以设想有一条输入带和一个读头，读头每次从输入带上顺序读入输入序列W中的一个符号。已输入的符号信息使M进入到某个给定的状态，因此，这个状态代表M关于已读入W子串的记忆。</p>
<p>M是奇偶检验器，它应该能记住，初始序列是具有奇数个1还是偶数个1。为此，我们设M有两个状态，分别称为<font class="definition3">odd</font>和<font class="definition3">even</font>。令even为开始状态，因为开始时，1的个数为0，且0是偶数。</p>
<p>当读入一个符号时，M按照某种方式改变它的状态，其变化取决于当前状态和输入符号，这种状态的改变称为<font class="definition3">变换</font>或<font class="definition3">状态转换</font>。数学上用δ描述，它利用当前状态q<sub>old</sub>和当前读入符号a，给出新的状态q<sub>new</sub>，表示成</p>
<div align=center><font color=red>δ(q<sub>old</sub>，a)=q<sub>new</sub></font></div>
<p>对M来说，其转换函数为：</p>
<div align=center>
<font color=red>
δ（even，0）=even δ（even，1）=odd <br>
δ（odd，0）=odd δ（odd，1）=even
</font>
</div>
<p>其中，状态even表示已读入的子串中含有1的个数为偶数；状态odd表示已读入的子串中含有1的个数为奇数，且仅当读入符号为1时，已读入子串的奇偶性要改变，也就要转换到不同的状态。</p>
<p>机器M的某些状态被指定为接受状态（又称终止状态），如果一个输入序列w使M从开始状态出发，最后到达一个接受状态，则说w为M所接受；否则，则说w为M所拒绝。奇偶检验器M有一个接受状态，即是odd。</p>
</td>
</tr>
</table>
<table align=right width=300>
<tr>
<td><IMG onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='3.1.3.htm'" src="../images/previous.gif"></IMG></td>
<td><IMG onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='3.2.1b.htm'" src="../images/next.gif"></IMG></td>
</tr>
</table>
</BODY>
</html>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -