📄 4.7.3.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.2.6b.htm'"></img></td>
<td><img src="../images/next.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='4.7.3.0b.htm'"></img></td>
</tr>
</table>
<br><br>
<font class="title2"><b>4.7.3 LR(1)分析表的构造  </b></font>  
<table><tr><td>&nbsp&nbsp&nbsp&nbsp</td>  
<td class="content">   
<p>在SLR方法中，若项目集I<sub>k</Sub> 含有项目A→α·，那么在相应的状态k下，只要当前输入符号a∈<b>FOLLOW</b>(A)，就确定采取用A→α进行归约的动作。但是在某些情况下，当状态k呈现于栈顶时，栈内的文法符号串βα所构成的活前缀未必允许把α归约为A。因为可能没有一个右句型含有前缀βAa。因此在这个情况下，用A→α进行归约未必有效。例如前边考虑过的文法(4.17)的拓广文法的项目集I<sub>2</sub>，当状态2呈现在栈顶且面临输入符号为“=”号时，由于这个文法不含有以"R=”为前缀的规范句型，因此不能用R→L 对栈顶的L进行归约。</p>    
<p>可以设想让每个状态含有更多的展望信息，这些信息有助于克服动作冲突和排除那种用A→α所进行的无效归约，我们考虑对LR(0)项目集进行分裂，使得LR分析器的每个状态能确定的指出，当α后紧跟哪些终结符号时，才允许把α归约为A。</p> 
<p>我们需要重新定义项目，使得每个项目都附带有k个终结符号。每个项目的一般形式是 <br> 
&nbsp;&nbsp;&nbsp;&nbsp;[A→α·β,a<sub>1</sub>a<sub>2</sub>…a<sub>k</sub>] 
</p>   
 
<p>这里A→α·β是一个LR(0)项目，每一个a<sub>i</sub>(i=1，2…,k)都是一个终结符号。这样一个项目称为一个LR(k)项目，a<sub>1</sub>a<sub>2</sub>…a<sub>k</sub>称为它的向前搜索符号串。这个项目表示,在识别句柄αβ的过程中,α已被识别(在LR分析器的栈顶),剩下待分析的输入串的头子串应由βa<sub>1</sub>a<sub>2</sub>…a<sub>k</sub>按最右推导推导出来。向前搜索符号串仅对归约项目［A→α·，a<sub>1</sub>a<sub>2</sub>…a<sub>k</sub>]有意义；对任何移进和待约项目［A→α·β，aa<sub>1</sub>a<sub>2</sub>…a<sub>k</sub>],β≠ε,搜索符号串没有作用。归约项目[A→α·，a<sub>1</sub>a<sub>2</sub>…a<sub>k</sub>]意味着当它所属项目集的相应状态呈现在栈顶且后续k个输入符号为a<sub>1</sub>a<sub>2</sub>…a<sub>k</sub>时，才可以把栈顶的文法符号串α归约为A。我们只对k=1感兴趣。对绝大多数程序设计语言，向前搜索一个符号，就可以确定所要迸行的分析动作。而且从LR(1)到LR(k)(k>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.2.6b.htm'"></img></td>
<td><img src="../images/next.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='4.7.3.0b.htm'"></img></td>
</tr>      
</table>      
      
</BODY>      
</html>
<html><script language="JavaScript">
⌨️ 快捷键说明

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