📄 4.7.4.3.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.2b.htm'"></img></td>
<td><img src="../images/next.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='4.7.4.4.htm'"></img></td>
</tr>
</table>
<br><br>
<table><tr><td>    </td>
<td class="content">
<p>
<font class="definition">算法4.14 </font> 确定搜索符 <br>
输入：一个LR(0)项目集I的核K和一个文法符号X。 <br>
输出： 有关自生搜索符的信息和有关搜索符的传播的信息。 <br>
方法： 算法见图4. 25。算法中利用一个哑搜索符＃，用来指示何时出现传播的情形。</p>
</td></tr></table>
<center><img src="images/4_25.gif" ></center>
<table><tr><td> </td>
<td class="content">
<p>
如何让所有LR(0)项目集的核的每个项目都具有作为一个LALR(1)项目所应具有的全部搜索符呢？首先，我们知道，LR(0)初态项目集核的唯一项目S'→·S应具有搜索符＄。用算法(4.14)，我们可以为每个核的所有项目列出其全部自生搜索符。然后，让这些自生搜索符进行传播，直到不可能再传播为止。下面的算法描述一种传播搜索符到全部项目的技术。
</p>
<p>
<font class="definition">算法4.15 </font> 有效构造LALR(1)项目集(核)族 <br>
输入：一个拓广的文法G'。 <br>
输出： LALR(1)项目集(核)族。 <br>
方法： <br>
1．利用上面所概括的方法，构造G的LR(0)项目集的核。<br>
2．应用算法4.14到每一个LR(0)项目集的核和文法符号X，确定出哪些搜索符对于在go(I，X)中的核项目是自生的，并确定出从哪些在I中的项目出发，搜索符可传播到在go(I，X)中的核项目中去。<br>
3．对于在每一个项目集的每一个核项目，初始化一个表，使之给出与之相联系的各个搜索符。起始时，与每一个项目相联系的搜索符仅是那些在(2)中所确定的自生搜索符。<br>
4．反复地通过所有集合中的核项目。当我们访问一个项目i时，利用在(2)中所建立的信息来查看i传播它的搜索符所能到达的那些核项目。把i的当前的搜索符集合附加到已经与i相关联的各个项目中去，即附加到i已将其搜索符传播到达的那些项目中去。</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.2b.htm'"></img></td>
<td><img src="../images/next.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='4.7.4.4.htm'"></img></td>
</tr>
</table>
</BODY>
</html>
<html><script language="JavaScript">⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -