📄 4.3.1.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.3.1.2.htm'"></img></td>
<td><img src="../images/next.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='4.3.2.0.htm'"></img></td>
</tr>
</table>
<br><br>
<table><tr><td>&nbsp&nbsp&nbsp&nbsp</td>        
<td class="content">  
<p>         
<font class="example">例4.9 </font>考虑文法</p>  
<table align=center width=450 class="content">   
<tr><td>S→Ac|c</td></tr>      
<tr><td>A→Bb|b</td></tr>      
<tr><td>B→Sa|a</td></tr>  
</table>   
<p>上述文法虽不具有直接左递归，但S，A,B都是左递归的。令它的非终结符号的排序为B，A ，S 。对于B，不存在直接左递归。把B代入到A的有关候选式后，我们把A的产生式变为</p>  
<table align=center width=450 class="content">   
<tr><td>A→Sab|ab|b</td></tr>  
</table>  
<p>现在的A同样不含有直接主递归，把它代入到S的有关候选式后,S的产生式变为</p>  
<table align=center width=450 class="content">   
<tr><td>S→Sabc|abc|bc|c</td></tr>  
</table>  
<p>经消除了S的直接左递归后，我们得到了整个文法为：</p>  
<table align=center width=450 class="content">   
<tr><td>S→abcS'|bcS'|cs'</td></tr>      
<tr><td>S'→abcS'|ε</td></tr>      
<tr><td>A→Sab|ab|b</td></tr>  
<tr><td>B→Sa|a</td></tr>  
</table>   
<p>显然，其中关于A和B的产生式已是多余的。经化简后最后所得的文法是：</p>  
<table align=center width=450 class="content">   
<tr><td>S→abcS'|bcS'|cS'</td></tr>      
<tr><td>S'→abcS'|ε</td></tr>      
</table>   
<p>注意，由于对非终结符号排序的不同，最后所得的文法在形式上可能是不一样的。但不难证明，它们都是等价的。例如，若对原有文法的非终结符号的排序选为S,A,B,那么，最后所得到的无左递归文法是：</p>  
<table align=center width=450 class="content">   
<tr><td>S→Ac|c</td></tr>      
<tr><td>A→Bb|b</td></tr>      
<tr><td>B→bcaB'|caB'|aB'</td></tr>  
<tr><td>B'→bcaB'|ε</td></tr>  
</table>   
</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.3.1.2.htm'"></img></td>
<td><img src="../images/next.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='4.3.2.0.htm'"></img></td>
</tr>       
</table>       
       
</BODY>       
</html>
⌨️ 快捷键说明

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