📄 4.2.1.1b.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.1.1.htm'"></img></td>
<td><img src="../images/next.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='4.2.2.0.htm'"></img></td>
</tr>
</table>
<br><br>
<p>    

<table><tr><td>&nbsp&nbsp&nbsp&nbsp</td>     
<td class="content">     
<p>     
使用文法(4.1)，在推导过程中完全可以根据当前的向前看符号决定选择哪个产生式往下推导，因此，分析过程是完全确定的。这种分析称为自顶向下的预测分析。之所以能进行预测分析，原因是在文法(4.1)中，对于每个非终结符A的定义<center>A→α<sub>1</sub>|α<sub>2</sub>|...|α<sub>n</sub></center>
任给i,j(1≤i,j≤n & i<>j),从α<sub>i</sub>和α<sub>j</sub>推导出来的第一个终结符号集合(称为<b>FIRST</b>)不相交,即:FIRST(α<sub>i</sub>)∩FIRST(α<sub>j</sub>)=Φ</p>    
<p>     
为精确计算<b>FIRST</b>(α),下面给出<b>FIRST</b>(α)的定义。</p>   
<p>
<img class="dingyi" src="../images/dingyi.gif"> 
<font class="definition2">定义4.1  </font>令G[S]=(V<sub>T</sub>，V<sub>N</sub>，S，P)，则<br> 
<center>FIRST(α)={a|α&nbsp;<img src="images/equalstar.gif" width="20" height="19">&nbsp;a...,&a∈V<sub>T</sub>}</center></p>     
<p>文法4.1中无ε-产生式,下面考虑有ε-产生式会出现的情况</p> 
<hr size=2 width=90% align=center color=red><br> 
<p>      
<font class="example">例4.2 </font>试若有文法G[S]，其产生式如下：</p> 
<table align=center width=350 class="content"> 
<tr><td>S→aA|d</td><td></td></tr>    
<tr><td>A→bAS|ε </td><td>(4.2)</td></tr>   
</table> 
<p>若输入串w=abd，则构造最左推导的过程如下：</p> 
<table align=center width=450 class="content"> 
<tr><td>S</td><td>&nbsp;<img src="images/equal.gif">&nbsp;aA {注：A=S，a=a，S→aA}</td></tr> 
<tr><td></td><td>&nbsp;<img src="images/equal.gif">&nbsp;abAS {注：A=A，a=b，A→bAS}</td></tr>    
<tr><td></td><td>&nbsp;<img src="images/equal.gif">&nbsp;abS {注：A=A，a=d，A→ε}</td></tr>    
<tr><td></td><td>&nbsp;<img src="images/equal.gif">&nbsp;abd {注：A=S，a=d，S→d}</td></tr>    
</table> 
<p>在第三步推导中，被替换的最左非终结符A的第一个候选式的<b>FIRST</b>(bAS)={b}，而向前看符号是d，因此，选择A的第二个候选式ε替换A，abAS中，A后面的符号尾S，S的开始符号中含有d，因此，可以正确的分析下去。</p>     
<p> d是句型abAS中紧跟随非终结符A的终结符号，把紧跟随非终结符A的终结符号集记作<b>FOLLOW</b>(A)，其定义如下：</p>
<hr size=2 width=90% align=center color=red><br>
<p>
<img class="dingyi" src="../images/dingyi.gif"> 
<font class="definition2">定义4.2  </font><br> 
&nbsp&nbsp&nbsp&nbsp设G=(V<sub>T</sub>,V<sub>N</sub>,S,P),<b>FOLLOW</b>(A)={a|S&nbsp;<img src="images/equalstar.gif" width="20" height="19">&nbsp;...Aa..., &a∈V<sub>T</sub> ,A∈V<sub>N</sub>}若&nbsp;S<img src="images/equalstar.gif" width="20" height="19">&nbsp;...A,则规定$∈<b>FOLLOW</b>(A)。<br>
&nbsp&nbsp&nbsp&nbsp这里，'$'作为输入串的结束符号。</p>
<p>在构造最左推导的过程中，若当前被替换的非终结符号是A，向前看符号a不出现A的所有非空候选式的<b>FIRST</b>集合中，此时若A有一个ε候选式，则向前看符号a应该出现在<b>FOLLOW</b>(A)中。</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.2.1.1.htm'"></img></td>
<td><img src="../images/next.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='4.2.2.0.htm'"></img></td>
</tr>     
</table>     
     
</BODY>     
</html>
⌨️ 快捷键说明

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