📄 4.5.1.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.5.1.1.htm'"></img></td>
<td><img src="../images/next.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='4.5.1.2.htm'"></img></td>
</tr>
</table>
<br><br>
<table><tr><td>    </td>
<td class="content">
<p><font class="emphasize">规范归约</font></p>
<p>例4.12对句子abbcde的归约过程称为规范归约。LR分析采用这种归约过程，它的形式定义如下：</p>
<p>
<img class="dingyi" src="../images/dingyi.gif">
<font class="definition2">定义4.3 </font>假定α是文法G的一个句子。我们称右句型序列<br> <br>
      α<sub>n</sub>,α<sub>n-1</sub>,…,α<sub>1</sub>,α<sub>0</sub> <br><br>
是α的一个规范归约，如果序列满足<br>
1. α<sub>n</sub>=α，α<sub>0</sub>=S；<br>
2.对任何i(0＜i≤n),α<sub>i-1</sub>是从α<sub>i</sub>经过把句柄替换为相应产生式的左部符号而得到的。
<p>显而易见，规范归约是关于α的一个最右推导的逆过程。因此，规范归约也称最左归约。 在形式语言中，最右推导常被称为规范推导。由规范推导所得到的句型称为规范句型。如果文法G是无二义的，那么，规范推导(最右推导)的逆过程必是规范归约(最左归约)。</p>
<p>请注意句柄的“最左”特征，这一点对于移进-归约方法来说是重要的。读者将在以后的讨论中看到，句柄的“最左”性和符号栈的栈顶两者是相关的。对于规范句型来说，句柄的后面不会出现非终结符号(即，句柄的后面只能出现终结符号)。基于这一点，我们可用句柄来刻画移进一归约过程的“可归约串”。图4.12描述了这一情景。其中αβw 表示一个规范句型。β是该句型的句柄。α是位于β之前的符号串，它可以含有非终结符号和终结符号。α是在β归约之前所进行的规范归约过程中得到的结果。而w是位于β之后的符号串，它只能含有终结符号。图中还假设该规范句型的最左的只有父子两代的子树的根结点为A。句柄β是可归约串，它即将被归约到A。</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.5.1.1.htm'"></img></td>
<td><img src="../images/next.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='4.5.1.2.htm'"></img></td>
</tr>
</table>
</BODY>
</html>
<html><script language="JavaScript">⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -