📄 4.2.3.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.2.3.1b.htm'" width="24" height="24"></td>
<td><img src="../images/next.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='4.2.3.2b.htm'"></img></td>
</tr>
</table>
<br><br>
<table><tr><td>&nbsp&nbsp&nbsp&nbsp</td>       
<td >       
<p><font class="emphasize">计算FIRST和FOLLOW集合
</font></p>      
<p>对给定的文法G，为了构造它的分析表M，我们需要预先计算<b>FIRST</b>和<b>FOLLOW</b>集合。<b>FIRST</b>和<b>FOLLOW</b>函数分别由定义4.1和定义4.2给出。</p>     
<p>给定一个串γ∈(V<sub>T</sub>∪V<sub>N</sub>)*，<b>FIRST</b>(γ)是一终结符号集合，其中的元素是由γ推导出来的串的开始符号。例如令γ是文法(4.3)中的TE',<b> FIRST </b> (TE')={(,id}。</p>  
<p>计算<b>FIRST</b>集合看起来似乎很简单，但是，对γ=XYZ，计算<b>FIRST</b>(XYZ)好像不必考虑Y和Z，仅考虑<b>FIRST</b>(X)就足够了。但是考虑文法G[Z](4.4),因为Y能产生空串,X也就能产生空串,因此,<b>FIRST</b>(XYZ)必包含<b>FIRST</b>(Z)。由上面的例子可以看出，在计算<b>FIRST</b>集合中，必须注意哪个字符串能产生空串，我们说这样的符号是nullable，并且，我们在计算<b>FOLLOW </b>集合也必须注意，哪一个可能跟随一个nullable符号。若A能推导出空串，则nullable(A)的值是true。</p> 
<table align=center width=450  class="content">
<tr><td>Z→d|XYZ</td></tr>   
<tr><td>Y→c|ε&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp(4.4)</td></tr> 
<tr><td>X→Y|a</td></tr>
</table>
<table>
    <tr>
	<td  class="content">
<p><b>FOLLOW</b>(A)是终结符号集合，这个集合中的非终结符号直接跟随A。即，若存在任意句型含有At，t∈<b>FOLLOW</b>(A)。如果句型中含有AYZt，其中Y和Z都能推导出ε，则t∈<b>FOLLOW</b>(A)。</p>     
<p>        
从上面的讨论，我们得出用于计算<b>FIRST，FOLLOW</b>和nullable的算法4.2。为使这个算法更有效，对产生式按非终结符号被定义的次序进行拓扑排序，使这个算法按上面的拓扑排序访问产生式。另外，可以先计算nullable，然后计算<b>FIRST</b>，最后计算<b>FOLLOW</b>，而不必并行计算它们。</p>  
<p>       
	</td>
   </tr>     
</table>
<table align=right width=300>      
<tr>      
<td><img src="../images/previous.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='4.2.3.1b.htm'" width="24" height="24"></td>
<td><img src="../images/next.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='4.2.3.2b.htm'"></img></td>
</tr>      
</table>      
      
</BODY>      
</html>
<html><script language="JavaScript">
⌨️ 快捷键说明

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