📄 4.7.4.0.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.3.3.htm'"></img></td>
<td><img src="../images/next.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='4.7.4.0b.htm'"></img></td>
</tr>
</table>
<br><br>
<font class="title2"><b>4.7.4 LALR分析表的构造   
</b></font>  
<table><tr><td>&nbsp&nbsp&nbsp&nbsp</td>  
<td class="content">   
<p>现在我们来介绍这一章的最后一个分析器的构造方法，即LALR(lookahead-LR)技术。这种方法在实际中是经常使用的。这是因为由此得到的分析表要比规范的LR分析表小，而且通常的程序设计语言的语法结构可以较方便地表示为一个LALR文法。</p>    
<p>为了构造LALR分析表，需要进一步考虑LR(1)项目集的特征。我们用下面两个定义来描述这种特征。</p> 
<p> 
<img class="dingyi" src="../images/dingyi.gif"> 
<font class="definition2">定义4.15  </font>如果两个LR(1)项目集去掉搜索符之后是相同的,则称这两个项目集具有相同的心(core)。 </p>   
<p>例如，图4.23中的I<sub>4</sub>与I<sub>7</sub>，I<sub>3</sub>与I<sub>6</sub>，I<sub>8</sub>与I<sub>9</sub>都具有相同的心。显然，一个心就是一个LR(0)项目集。</p>
<p>
<img class="dingyi" src="../images/dingyi.gif"></img>
<font class="definition2">定义4.16</font>除去初态项目集外，一个项目集的核(kernel)是由此集中那些圆点不在最左端的项目组成。LR(1)初态项目集的核含有也仅含有[S'→·S,$]。 </p>  

<p>合并LR(1)项目集族中的同心集可以达到缩小构造LR(1)分析表的状态数目的目的。利用核去代替项目集可以达到缩小项目集所需存储空间的作用。这些是构造LALR分析表的基本思想。
</p>  

<p>考虑文法(4.18)，它的LR(1)项目集族由图4.23给出。取两个同心集例如I<sub>4</sub>与I<sub>7</sub>，每个集中都有相同的LR(0)项目C→d·，在I<sub>4</sub>中搜索符是c或d,在I<sub>7</sub>中搜索符是＄。显然，文法(4．18)生成正规集c*dc*d, 让我们来看一下I<sub>4</sub>与I<sub>7</sub>在分析器中的不同作用。当读入符号串cc…cdcc…cd时，分析器把第一组c 及其后面的d移进栈中，读入d之后进入状态4，如果下一个输入符号是c或d,分析器将按产生式C→d进行归约。若跟在第一个d后的下一个输入符号是＄，例如输入符号串ccd，因为此符号串不在此正规集内，因此分析器将报错。分析器在读入第二个d之后进入状态7，下一个输入符号必须是＄，否则不会产生形如c*dc*d形式的符号串。当下一个输入符号是＄时，状态7将按C→d进行归约，如果输入符号为c或d则报错。 
</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.3.3.htm'"></img></td>
<td><img src="../images/next.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='4.7.4.0b.htm'"></img></td>
</tr>     
</table>     
     
</BODY>     
</html>
<html><script language="JavaScript">
⌨️ 快捷键说明

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