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

<table><tr><td>&nbsp&nbsp&nbsp&nbsp</td> 
<td class="content"> 
<p> 
对于程序语言来说，我们总可以写出它的无二义性文法。但是，也确实存在这样的语言，它们不存在无二义性文法；这样的语言称为先天二义性的语言。 
</p> 
<p> 
我们常常使用无二义性文法，但是，一个语言的二义性文法常比无二义性文法简单明了，if语句的两个文法(2.2)和(2.7)就是例子。因此，在描述语言语法和构造编译程序时，也使用二义性文法。显然，在使用二义性文法时，我们要清楚知道，使用的文法因何会出现二义性以及在什么条件的约束下可消除这种二义性。然而，已经证明二义性问题是不可判定的。这就是说，不存在一种算法，它能在有限步骤内，确切地判定任给的一个文法是否是二义的。我们所能做的，就是找到一些充分条件，当文法满足这些条件时，就使我们确信该文法是无二义性的。这些条件是充分的，未必是必要的。例如，根据定义可知，文法(2.6),即G'是二义性的。但当我们规定了运算符的优先顺序和结合规则，比如说，让“*”的优先性高于“+"，且它们都服从左结合，那么就可以构造出一个无二义性文法，这个文法正是文法(2.1)，即G。此时句子a+a*a的分析树是唯一的。且有L(G)＝L(G')。 
</p> 
<p> 
最后，我们对上下文无关文法作某些实用上的限制。这些限制条件并不真正限制由文法所能描述的语言集合，但对于分析算法是很有好处的。具体说来，有如下两点限制：<br>  
&nbsp&nbsp&nbsp&nbsp1．在文法中不包含任何下面形式的产生式： <br> 
<center> A→A </center> 
因为这种产生式除了引起二义性外没有任何用处。<br>  
&nbsp&nbsp&nbsp&nbsp2. 每个非终结符号A必须都有用处。这一方面意味着，从开始符号S出发，存在推导：<br> 
<center> S<img src="img\equalstar.gif"  width="20" height="23">αAβ </center> 
即存在含A的句型。另一方面意味着，必须存在终结符号串γ∈V<sub>T</sub>*,使得A<img src="img/equaladd.gif">γ;即对于A不存在永不终结的回路。 
</p> 
<p> 
以后所讨论的文法都假定满足上述两条件。这种文法称为压缩过的文法，或称化简了的文法。  
</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='2.3.3b.htm'"></img></td>
<td><img src="../images/next.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='2.4.1.htm'"></img></td>
</tr> 
</table> 
 
</BODY> 
</html>
<html><script language="JavaScript">
⌨️ 快捷键说明

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