📄 4.3.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.3.1.1.htm'" width="24" height="24"></img></td>
<td>
<img src="../images/next.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='4.3.1.2.htm'" width="26" height="24"></img></td>
</tr>
</table>
<br><br>
<table><tr><td>&nbsp&nbsp&nbsp&nbsp</td> 
<td class="content">  
<p>如上所述，在应用算法4.4之前要注意文法中不能带有ε- 产生式；在消除了左递归之后还要对所得到的新文法进行化简，即去除多余的产生式。</p>    
<p>可以证明：若有某个上下文无关文法G=(V<sub>T</sub>，V<sub>N</sub>，S,P)，则存在一个不带ε- 产生式的上下文无关文法G'= (V<sub>T</sub>，V<sub>N</sub>，S，P' )，使得L(G)-{ε}=L(G')。特别是，若L(G)中不含ε，则有</p>    
<p align="center">L(G)＝L(G')</p>    
<p>这里我们不给出形式证明，只给出算法。首先确定出能产生空串ε的所有非终结符号。然后，构造G'的产生式集合P'。方法如下：若A→X<sub>1</sub>X<sub>2</sub>…X<sub>n</sub>在文法G的产生式集合P 中，则将所有产生式A→α<sub>1</sub>α<sub>2</sub>…α<sub>n</sub> 加入到P'中，这里</p>    
<p>1.若X<sub>i</sub>不能产生ε，则α<sub>i</sub>＝X<sub>i</sub> ；</p>    
<p>2.若X<sub>i</sub>能产生ε，则α<sub>i</sub>或是X<sub>i</sub>或是ε</p>  
<p>3.不能所有的α<sub>i</sub> 都取ε</p>   
<p>需要解释的两点是：所谓能产生空串ε的非终结符号A是指存在Aε这样的推导；上述X<sub>i</sub>是文法符号，可以是终结符号也可以是非终结符号。</p>
<P>我们称一个文法是 ε- 无关的，如果它没有ε- 产生式，或者只有一个ε- 产生式：S→ε并且开始符号不出现在任何产生式的右边。</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.3.1.1.htm'" width="24" height="24"></img></td>
<td>
<img src="../images/next.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='4.3.1.2.htm'" width="26" height="24"></img></td>
</tr>        
</table>        
        
</BODY>        
</html>

⌨️ 快捷键说明

复制代码 Ctrl + C

搜索代码 Ctrl + F

全屏模式 F11

切换主题 Ctrl + Shift + D

显示快捷键 ?

增大字号 Ctrl + =

减小字号 Ctrl + -