📄 4.7.4.1.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.0b.htm'"></img></td>
<td><img src="../images/next.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='4.7.4.1b.htm'"></img></td>
</tr>
</table>
<br><br>
<table><tr><td>&nbsp&nbsp&nbsp&nbsp</td> 
<td class="content">  
<p>下面，我们将给出构筑LALR分析表的第一个算法。基本思想是，首先构造LR(1)项目集族，如果它不存在冲突，就把同心集合并在一起。若合并后的集族不存在归约-归约冲突，就按这个集族构造分析表。</p>   
<p>
<font class="definition">算法4.13 </font> LALR(1)分析表的构造  <br>
&nbsp;&nbsp;&nbsp;&nbsp;输入：一个拓广文法G' 。 <br>    
&nbsp;&nbsp;&nbsp;&nbsp;输出： 关于G'的LALR(1)分析表。 <br>    
&nbsp;&nbsp;&nbsp;&nbsp;方法：<br>  
&nbsp;&nbsp;&nbsp;&nbsp;1. 构造G' 的LR(1)有效项目集族C={I<sub>0</sub>,I<sub>1</sub>,…，I<sub>n</sub>}。<br>  
&nbsp;&nbsp;&nbsp;&nbsp;2. 把C中具有同心的集合并在一起，得到一个新的项目集族C'=｛J<sub>0</sub>，J<sub>1</sub>，…，J<sub>m</sub>｝，其中含有项目[S'→·S,＄] 的J<sub>k</sub>为分析表的初态。<br>    
&nbsp;&nbsp;&nbsp;&nbsp;3. 从C'出发构造action表：<br>  
&nbsp;&nbsp;&nbsp;&nbsp;(a)若［A→α·aβ,b]∈J<sub>i</sub>且go(J<sub>i</sub>,a)=J<sub>j</sub>,则置action[i,a]为S<sub>j</sub>。 <br> 
&nbsp;&nbsp;&nbsp;&nbsp;(b)若［A→α·，a]∈J<sub>i</sub>，则置action[i,a]为用A→α归约，简记为“r<sub>j</sub>&quot;。其中j表示A→α为拓广文法G'的第j个产生式。<br> 
&nbsp;&nbsp;&nbsp;&nbsp;(c)若［S'→S·，＄]∈J<sub>i</sub>则置action[i，＄] 为接受，简记为“acc”。<br>   
&nbsp;&nbsp;&nbsp;&nbsp;4. goto表的构造，设J<sub>k</sub>={I<sub>i1</sub>，I<sub>i2</sub>,…，I<sub>it</sub>}，由于这些I<sub>i</sub>同心，因此go(I<sub>i1</sub>,X)，go(I<sub>i2</sub>,X),…，go(I<sub>it</sub>,X)也同心，记J<sub>i</sub>为所有这些go合并后的集合，那么就有go(J<sub>k</sub>，X)=J<sub>i</sub>。于是若go(J<sub>k</sub>，A)=J<sub>i</sub>，则置goto[K,A]=i。<br> 
&nbsp;&nbsp;&nbsp;&nbsp;5. 凡分析表中不能用规则3或4填入信息的空格均填上出错标志。  
</p>    
<p>经上述步骤构造的分析表若不存在冲突，则称它为文法G的LALR分析表，存在这种分析表的文法称为LALR(1)文法。在第2步中所产生的项目集族称作LALR(1)项目集族。</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.0b.htm'"></img></td>
<td><img src="../images/next.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='4.7.4.1b.htm'"></img></td>
</tr>      
</table>      
      
</BODY>      
</html>
⌨️ 快捷键说明

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