⭐ 欢迎来到虫虫下载站！ | 📦 资源下载 📁 资源专辑 ℹ️ 关于我们
⭐ 虫虫下载站
📤 上传资源

📄 4.2.3.2b.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.2.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.3.htm'"></img></td>
</tr>
</table>
<br><br>
</table>
<table>
	<tr>
		<td>
<font class="definition"><img border="0" src="images/dingyi.gif" width="32" height="31">算法4.2 </font> 计算nullable、<b>FIRST</b>和<b>FOLLOW</b> 
<br><br>
<p>初始化：FIRST和FOLLOW全为空集（除FOLLOW(s)={$}外),nullable全为false</p>
&nbsp;&nbsp;<font size="3"><font color="#0000FF">FOR</font> &nbsp;任一a∈V<sub>T</sub>   
&nbsp;<font color="#0000FF">DO</font> &nbsp;<b>FIRST</b>(a):={a};<br>  
&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000FF">REPEAT</font><br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000FF">FOR</font> 任一A→Y<sub>1</sub> Y<sub>2</sub> …Y<sub>n</sub> ∈P  
<font color="#0000FF"> 
DO</font><br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000FF">BEGIN</font><br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000FF">IF</font> 任一i(1≤i≤n)   
nullable(Y<sub>i</sub> )=true &nbsp;<font color="#0000FF">THEN</font>&nbsp;<br> 
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; nullable(A):=true;<br> 
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000FF">FOR</font> i:=1  
<font color="#0000FF"> TO</font> n <font color="#0000FF"> DO</font><br> 
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000FF">BEGIN</font><br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000FF">IF</font>  
(i=1)OR 任一j(1≤j≤i-1) nullable(Y<sub>j</sub> )=true&nbsp;<font color="#0000FF">THEN&nbsp;</font>  
<b><br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; FIRST</b>(A)=<b>FIRST</b>(A)∪<b>FIRST</b>(Y<sub>i</sub> );<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000FF">IF</font>  
Y<sub>i</sub> ∈V<sub>N</sub> &nbsp;&nbsp;<font color="#0000FF">THEN <br>  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
BEGIN</font><br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000FF">IF</font>  
(i=n) <font color="#0000FF"> OR</font> 任一j(i+1≤j≤n) nullable(Y<sub>j</sub> )=true<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000FF">THEN</font>&nbsp;  
<b>FOLLOW</b>(Y<sub>i</sub> )=<b>FOLLOW</b>(Y<sub>i</sub> )∪<b>FOLLOW</b>(A);<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000FF">IF</font>  
Y<sub>i+1</sub> ∈V<sub>T</sub> &nbsp;&nbsp;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000FF">THEN</font>&nbsp;   
Y<sub>i+1</sub> ∈<b>FOLLOW</b>(Y<sub>i</sub> )<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000FF">ELSE <br> 
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
FOR</font> k:=i+1 <font color="#0000FF"> TO</font> n <font color="#0000FF"> DO</font><br> 
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp<font color="#0000FF">IF</font> (k=i+1)<font color="#0000FF">OR</font> 任一j(i+1≤j≤k-1)nullable(Y<sub>j</sub> )=true<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000FF">THEN</font>&nbsp;  
FOLLOW</b>(Y<sub>i</sub> )=<b>FOLLOW</b>(Y<sub>i</sub> )∪<b>FIRST</b>(Y<sub>k</sub> )<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000FF">END</font><br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000FF">END</font><br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000FF">END</font><br>
&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000FF">UNTIL</font> <b>FIRST</b>,<b>FOLLOW</b>,nullable 不再改变<br>  
</font><br>
&nbsp;&nbsp;&nbsp;&nbsp;
</p>   
	</td>
   </tr>     
</table>
<p><font class="example">例4.5</font> 把算法4.2应用于文法G[E](4.3),得到下面的计算结果：</p>
<p>    
<center class="content">表4.3 文法G[E](4.3)的<b>FIRST</b>和<b>FOLLOW</b>集
<table width="88%" border="1" height="146" cellspacing="0"  cellpadding="0" class="content">
          <tr>
            <td>&nbsp;</td>
            <td>
              <div align="center">
                nullable
              </div>
            </td>
            <td>
              <div align="center">
                FIRST
              </div>
            </td>
            <td>
              <div align="center">
                FOLLOW
              </div>
            </td>
          </tr>
          <tr>
            <td>
              <div align="center">
                E
              </div>
            </td>
            <td>
              <div align="center">
                false
              </div>
            </td>
            <td>
              <div align="center">
                (, id
              </div>
            </td>
            <td>
              <div align="center">
                ), $
              </div>
            </td>
          </tr>
          <tr>
            <td>
              <div align="center">
                E'
              </div>
            </td>
            <td>
              <div align="center">
                true
              </div>
            </td>
            <td>
              <div align="center">
                +
              </div>
            </td>
            <td>
              <div align="center">
                ), $
              </div>
            </td>
          </tr>
          <tr>
            <td>
              <div align="center">
                T
              </div>
            </td>
            <td>
              <div align="center">
                false
              </div>
            </td>
            <td>
              <div align="center">
                (, id
              </div>
            </td>
            <td>
              <div align="center">
                +, ), $
              </div>
            </td>
          </tr>
          <tr>
            <td>
              <div align="center">
                T'
              </div>
            </td>
            <td>
              <div align="center">
                true
              </div>
            </td>
            <td>
              <div align="center">
                *
              </div>
            </td>
            <td>
              <div align="center">
                +, ), $
              </div>
            </td>
          </tr>
          <tr>
            <td>
              <div align="center">
                F
              </div>
            </td>
            <td>
              <div align="center">
                false
              </div>
            </td>
            <td>
              <div align="center">
                (, id
              </div>
            </td>
            <td>
              <div align="center">
                *, +, ), $
              </div>
            </td>
          </tr>
        </table>
 </center>
<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.2.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.3.htm'"></img></td>
</tr>      
</table>      
      
</BODY>      
</html>

⌨️ 快捷键说明

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