📄 4.7.4.2.htm

📁 建立《编译原理网络课程》的目的不仅使学生掌握构造编译程序的原理和技术
💻 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.7.4.1c.htm'"></img></td>
<td><img src="../images/next.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='4.7.4.2b.htm'"></img></td>
</tr>
</table>
<br><br>
<table><tr><td>&nbsp&nbsp&nbsp&nbsp</td> 
<td class="content">  
<p><font class="emphasize">LALR分析表的有效构造方法</font></p>   
<p>
算法4.13虽然简单明确，但在实现中时间和空间的开销还是较大的。我们可以对算法4.13作几点修改，使之在创建LALR(1)分析表的过程中不需要构造出一个完整的LR(1)的项目集族。因LR(1)项目集族比LR(0)项目集族大得多。我们希望用和LR(0)集族相当的空间来构造LALR(1)集族。
</p>  
<p>首先我们看到，可以用一个项目集I的核来表示I,也就是说，可以用初态项目［S'→·S,＄]或那些圆点不在最左端的项目来表示I。因为我们至今所讨论的项目集都是以一定项目为核的闭包。用核代替闭包这将大大缩小它所需要的存储空间。</p>

<p>
让我们看一看如何从核构造action表。设I是一个项目集，K是它的核。我们知道如果action[I,a]为“用A→α 归约”，那么，若α≠ε，则项目A→α·必属于I的核K。若α=ε，意味着在K中必有某个项目[B→γ·Cδ,b]，其中有规范推导C&nbsp<img src="images/equalstar.gif" width="20" height="19">&nbspAη，且a∈<b>FIRST</b>(ηδb)。但是，对任何C，满足规范推导C<img src="images/equalstar.gif" width="20" height="19">Aη的所有非终结符号A是可以预先计算出来的。其次，如果action[I,a]为移进。则这意味着K中有某个项目[B→γ·Cδ,b]，其中有规范推导C<img src="images/equalstar.gif" width="20" height="19">ax,且这个推导的最后一步不使用ε产生式。对于每个C满足规范推导C<img src="images/equalstar.gif" width="20" height="19">ax的所有终结符号a也是可以预先计算出来的。 
</p>   
<p>现在我们来看一看如何通过核构造goto表。如果项目[B→γ·Xδ，b]是在I的核中,那么［B→γX·δ,b]是在go(I，X)的核中。如果一个项目［B→γ·Cδ,b］在I的核中，并且对于某个η有规范推导C<img src="images/equalstar.gif" width="20" height="19">Aη,那么项目［A→X·β,a]也在go(I，X)的核之中。如果对每对非终结符号C和A都预先计算出对一定的η而言是否有关系规范推导C<img src="images/equalstar.gif" width="20" height="19">Aη,那么，从核构造分析表这一工作仅比从闭包构造分析表的工作在效率上稍差一点而已。 
</p>   
<p>为了给一个拓广文法G'构造LALR(1)项目集族，我们从初态项目的核S'→·S开始。之后，正如上面所讲述的，我们计算出从I<sub>0<sub>出发转移到的核。我们继续计算出对于每一个新生成的核的转移直到我们具有了全部LR(0)项目集的核为止。  
</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.7.4.1c.htm'"></img></td>
<td><img src="../images/next.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='4.7.4.2b.htm'"></img></td>
</tr>      
</table>      
      
</BODY>      
</html>
⌨️ 快捷键说明

复制代码 Ctrl + C
搜索代码 Ctrl + F
全屏模式 F11
切换主题 Ctrl + Shift + D
显示快捷键 ?
增大字号 Ctrl + =
减小字号 Ctrl + -