📄 4.2.2.1b.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>
<table align=right width=300>
<tr>
<td><img src="../images/previous.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='4.2.2.1.htm'"></img></td>
<td><img src="../images/next.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='4.2.2.2.htm'"></img></td>
</tr>
</table>
<br><br>
<table><tr><td>    </td>
<td class="content">
<p>构造转换图的目的是希望用这种转换图来识别输入符号串，或者说从转换图出发来构造预测分析器。这样构造出来的预测分析器的工作要点如下所述。从文法的开始符号所对应的转换图的开始状态开始分析，若在某些动作之后处于状态s并且从状态s 出发有一条标志以终结符号a的箭弧到达状态t，且若下一个输入符号为a，则分析器将把输入指针向右移动一个位置并将状态转移到t。另一方面，如果箭弧的标志是非终结符号A，那么分析的控制立刻转移到A的开始状态，此时不移动输入指针。如果分析到达了A的终结状态，控制立刻转移到(返回到)状态t。事实上，在从状态s至状态t的期间从输入中“读入”了A的有关信息。最后，如果箭弧标志以ε，那么立刻从状态s转移到状态t，而不移动输入指针。</p>
<p>如果给定的转换图不存在非确定性，则上述方法可顺利进行。我们称一个非终结符号转换图是“确定的”，如果它的每个状态结的所有射出弧不存在同名弧，不存在ε-弧，而且，如果有以非终结符号为标志的弧，则这弧是此结点的唯一射出弧。如果一个文法的所有非终结符号转换图都是确定的，那么，就可以用它们来构造预测分析器。然而如有不确定性发生，我们常常可以用特殊的方法加以解决。如果非确定性不能消除，我们虽然不能建立预测分析器但是可以建立带回溯的递归下降分析器(见4.4)，以用来系统地试验各种可能性。</p>
<p>
例如在图4.4中，其非确定性仅涉及到ε箭弧的问题。我们看到，从E'的转换图的状态3射出两条箭弧，一条标志以+，另一条标志以ε。对此解释为，若下一个输入符号为+，则转向状态4，输入指针向前移动一个位置；若下一个输入是其它符号，则按ε箭弧转移至状态6, 此时输入指针保持不动。同样可以解释在图4.4中T'的转换图的ε箭弧。于是非确定性即可移走，这样，我们就可以利用转换图为文法(4.3)书写一个预测分析程序。另外，对某些转换图还需考虑化简。</p>
</td></tr></table>
<br>
<table align=right width=300>
<tr>
<td><img src="../images/previous.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='4.2.2.1.htm'"></img></td>
<td><img src="../images/next.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='4.2.2.2.htm'"></img></td>
</tr>
</table>
</BODY>
</html>
<html><script language="JavaScript">⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -