📄 5.5.1.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='5.5.0.htm'" width="65" height="27"></td>
<td><img src="../images/next.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='5.5.1_1.htm'"></img></td>
</tr>
</table>
<br><br>
<font class="title2"><b>5.5.1 从翻译模式中消除左递归 </b></font>
<table>
<tr>
<td>    </td>
<td class="content">
<p>由于大多数算术运算符号都是左结合的，因此我们很自然地用左递归文法来定义算术表达式。现在我们把前面讨论过的消除左递归的算法加以扩充，以便当一个翻译模式的基本文法被转换时考虑属性。这种转换适合带综合属性的翻译模式。它可以允许第5.1节和5.2节中的许多语法制导定义使用预测分析来实现。下面是一个转换的例子。
</p>
</td>
</tr>
</table>
<table><tr><td>    </td>
<td class="content">
<p>
<b>例5.14</b> 图5.13的带左递归的文法的翻译模式被转换成图5.14的带右递归的文法的翻译模式。新的翻译模式产生的表达式9－5＋2的带注释的分析树如图5.15所示。图中的箭头标明了表达式求值的顺序。
</p>
</td></tr></table>
<table><tr><td> </td>
<td class="content">
<p>
E->E<sub>1</sub>+T｛E.val:=E<sub>1</sub>.val+T.val}<br>
E->E<sub>1</sub>-T｛E.val:=E<sub>1</sub>.val-T.val｝<br>
E->T{E.val:=T.val}<br>
T->(E) ｛T.val:=E.val｝<br>
T->num ｛T.val:=num.val}
</p>
</td>
</tr>
</table>
<p >
图5.13 带左递归的文法的翻译模式</p>
<table>
<tr>
<td><font class="yanshi">     观看演示 </font></td>
<td><font color=blue onmouseover="javascript:style.cursor='hand'" onclick="javascript:open('compile5/page1.htm','_blank','menu=no,toolbar=no,location=no,directories=no,status=no,scrollbars=yes,resizable=yes,copyhistory=no,left=100,top=100,width=800,height=600')">表达式9-5+2的分析树和依赖图</font></td>
<td><img src="../images/yanshi.gif"></img></td>
</tr>
</table>
<br>
<table><tr><td>    </td>
<td class="content">
<p>
在新的翻译模式中，每个数都是由T产生的，并且T.val的值就是数的词法值。这个值通过属性<b>num</b>.val给出。子表达式9-5中的数字9是由最左边的T生成的，但是减号和5是由根的右子结点生成的。继承属性R.i从P.val得到值9。计算9-5＃把结果4传递到中间的R结点，这是通过在产生式R→-T
R<span class="down">1</span>中插入动作｛R<span class="down"><sub>1</sub></span>.i:=R.i-T.val｝而实现的。类似的动作是把2加到9-5的值上，在R的最下面的结点处得到结果R.i=6。这个结果将成为在根结点处的E.val的值；R的综合属性s在图5.15中没有表示出来，它用来向上复制这一结果直到树根。
</p>
</td>
</tr>
</table>
<table><tr><td>    </td>
<td class="content">
<p>
E→T {R.i:=T.val}<br>
R｛E.val:=R.s｝<br>
R→＋<br>
T｛R<sub>1</sub>.i:=R.i+T.val}<br>
R<span class="down"><sub>1</sub></span>｛R.s:=R<span class="down"><sub>1</sub></span>.s}<br>
R→-<br>
T｛R<span class="down"><sub>1</sub></span>.i:=R.i-T.val}<br>
R<span class="down"><sub>1</sub></span>｛R.s:=R<span class="down"><sub>1</sub></span>.s}<br>
R→ε｛R.s:=R.i}<br>
T→（<br>
E<br>
） ｛T.val:=E.val}<br>
T→<b>num</b> {T.val:=<b>num</b>.val}<br>
<br>
<font face="楷体_GB2312"> 图5.14经过转换的带有右递归文法的翻译模式</font>
</p>
</td>
</tr>
</table>
<table><tr><td>    </td>
<td class="content">
<p>
对于自顶向下的分析，我们可以假设动作是在与之处于相同位置上的一个符号被充分展开后被执行的。例如，图5.14的第二个产生式中，第一个动作（对R<span class="down"><sub>1</sub></span>.i赋值）是在T被完全展开成终结符号后执行的；第二个动作是在R<span class="down">1</span>被完全展开后执行的。正如第5.4节中讨论的L-属性定义那样，一个符号的继承属性必须由这个符号以前出现的动作来计算，并且产生式左边非终结符号的综合属性必须在它所依赖的所有属性都计算出来以后才能计算。
</p>
</td>
</tr>
</table>
<p align=center><img src="5_15.gif" width="469" height="277"></p>
<p align=center>图5.15 表达式9-5+2的计算</p>
<br>
<table align=right width=300>
<tr>
<td><img src="../images/previous.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='5.5.0.htm'"></img></td>
<td><img src="../images/next.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='5.5.1_1.htm'" width="63" height="27"></td>
</tr>
</table>
</BODY>
<html><script language="JavaScript">⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -