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

<table><tr><td>&nbsp&nbsp&nbsp&nbsp</td> 
<td class="content"> 
<p> 
为了使用合适的文法构造编译程序，使得它能唯一地分析所有合法的源程序，必须深刻理解这种文法现象，由此引出下面定义。 
</p> 
<p> 
<font class="definition2">定义2.6&nbsp</font>如果一文法的句子存在两棵分析树，那么，该句子是二义性的。如果一文法包含二义性的句子，则就说这个文法是<font class="definition3">二义性</font>的；否则，该文法是<font class="definition3">无二义性的</font>。      
</p> 
<p> 
试考虑如下文法G' <br> 
<table align=center width=450> 
<tr><td colspan=2>G'=({a,+,*,(,)},{E},E,P)&nbsp&nbsp&nbsp&nbsp(2.6)</td></tr> 
<tr><td width=80>其中P：</td><td></td></tr> 
<tr><td></td><td> E→E＋E|E*E|(E)|a </td></tr> 
</table> 
a+a*a是文法(2.6)的句子，因而有以下的推导成立：<br>  
<center> E <img src="IMG/equal.gif"></img> E＋E <img src="IMG/equal.gif"></img> a+E <img src="IMG/equal.gif"></img> a+E*E <img src="IMG/equal.gif"></img> a+a*E <img src="IMG/equal.gif"></img> a+a*a </center> 
对应于这一推导的分析树表示于图2.7(a)。但要注意，对于这一句子而言，还存在以下的推导：<br> 
<center> E <img src="IMG/equal.gif"></img> E*E <img src="IMG/equal.gif"></img> E+E*E <img src="IMG/equal.gif"></img> a+E*E <img src="IMG/equal.gif"></img> a+a*E <img src="IMG/equal.gif"></img> a+a*a </center> 
对应于这一推导的分析树表示于图2.7(b)。即句子a+a*a具有两棵分析树，根据定义2.6, 文法(2.6)是二义性文法。 
<p> 
但要注意，文法的二义性和语言的二义性是两个不同的概念。我们可能有两个不同的文法G和G'，而且其中一个是二义性的，另一个是无二义性的，但是却有L(G)=L(G')。即文法G和G'所产生的语言是相同的。或者说，我们有时能改变一个二义性文法(当然不改变它的句子)，得到同一个句子集合的无二义性文法。 
</p> 
<p> 
例如，对于if语句来说，一般规定“else必须匹配最近那个未匹配的then”。这个避免二义性的规定可以直接结合到文法中。可以改写文法(2.2)成无二义性文法(2.7)。主要的想法是，使出现在then和else中间的语句必须是“匹配的语句”。一个匹配的语句或者是if-then-else型的不包括非匹配语句的条件语句，或者是非条件语句的其它语句。在文法(2．7)中分别用matched-stmt和unmatched-stmt表示匹配的语句和非匹配的语句。 
</p> 
<p> 
<table align=center width=80%> 
<tr><td>stmt→matched-stmt </td></tr> 
<tr><td>&nbsp&nbsp&nbsp&nbsp |unmatched-stmt </td></tr> 
<tr><td>matched-stmt→<b>if</b> expr <b>then</b> matched-stmt <b>else</b> matched-stmt </td></tr> 
<tr><td>&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp |<b>other</b> </td></tr> 
<tr><td>unmatched-stmt→<b>if</b> expr <b>then</b> stmt </td></tr> 
<tr><td>&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp|<b>if</b> expr <b>then</b> matched-stmt <b>else</b> unmatched-stmt &nbsp&nbsp(2.7)</td></tr> 
</table> 
<p> 
此文法与文法(2.2)一样生成同样的符号串集合。文法(2.7)是无二义性的,它对于符号串(2.3)只给出唯一的分析。 
</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.3.htm'"></img></td>
<td><img src="../images/next.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='2.3.3c.htm'"></img></td>
</tr> 
</table> 
 
</BODY> 
</html>
<html><script language="JavaScript">
⌨️ 快捷键说明

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