📄 5.8.1_2.htm.bak
字号:
<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='5.8.1_1.htm'"></td>
<td><img src="../images/next.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='5.8.2.htm'"></img></td>
</tr>
</table>
<br><br>
<font class="title2"><b>5.8.1.2 类型表达式的等价</b></font>
<table><tr><td>    </td>
<td class="content">
<P>
在类型检查中，要判断两个语言结构的类型是否相等，因而，要判断两个语言结构的类型表达式是否等价。根据语言的类型体制和类型表达式的表示方法，分结构等价和各字等价。
</p>
</td></tr></table>
<br>
<hr size=2 color=red width=90%>
<br>
<table><tr><td>    </td>
<td class="content">
<P>
<b>结构等价 </b>
</p>
</td></tr></table>
<table><tr><td></td>
<td class="content">
<P>
所谓两个类型表达式结构相等，是指两个类型表达式要么是相同的基本类型，要么是同样的类型构造符作用于类型等价的类型表达式。也就是说，两个类型表达式结构等价，当且仅当它们完全相同。图5.30是测试两个类型表达式结构等价的算法，假设类型构造符仅有数组、笛卡儿积、指针和函数，这个算法递归地比较两个类型表达式的结构。
</p>
</td></tr></table>
<table><tr><td>    </td>
<td class="content">
<P>
<b><font color="#0000FF">FUNCTION</font></b> eq(s,t):<font color="#0000FF">boolean</font>; <br>
<b> <font color="#0000FF">BEGIN</font></b> <br>
<b> <font color="#0000FF">IF</font></b> s和t是相同的基本类型 <b><font color="#0000FF">THEN</font></b> <br>
<b> <font color="#0000FF">return</font></b>(<font color="#0000FF">true</font>); <br>
<b> <font color="#0000FF">ELSE
IF</font></b> (s=ARRAY(s<sub>1</sub>,s<sub>2</sub>))
<b><font color="#0000FF">and</font></b> (t=ARRAY(t<sub>1</sub>,t<sub>2</sub>))
<b><font color="#0000FF">THEN</font></b>
<br>
<b> <font color="#0000FF">return</font></b>(eq(s<sub>1</sub>,t<sub>1</sub>)
<b><font color="#0000FF">and</font></b> eq(s<sub>2</sub>,t<sub>2</sub>))
<br>
<b> <font color="#0000FF">ELSE
IF</font></b> (s=s<sub>1</sub>*s<sub>2</sub>) <b><font color="#0000FF">and</font></b>
(t=t<sub>1</sub>*t<sub>2</sub>) <b><font color="#0000FF">THEN</font></b>
<br>
<b>
<font color="#0000FF">return</font></b>(eq(s<sub>1</sub>,s<sub>2</sub>)
<b><font color="#0000FF">and</font></b> (eq(s<sub>2</sub>,t<sub>2</sub>))
<br>
<b>
<font color="#0000FF">ELSE IF</font></b> (s=POINTER(s<sub>1</sub>)) <b><font color="#0000FF">and</font></b>
(t=POINTER(t<sub>1</sub>))<br>
<font color="#0000FF">THEN</font></b>
<b><font color="#0000FF">return</font></b>(eq(s<sub>1</sub>,t<sub>1</sub>))
<br>
<b> <font color="#0000FF">ELSE
IF</font></b> (s=s<sub>1</sub>→s<sub>2</sub>) <b><font color="#0000FF">and</font></b>
(t=t<sub>1</sub>→t<sub>2</sub>) <b><font color="#0000FF">THEN</font></b>
<br>
<b>
 <font color="#0000FF">return</font></b>(eq(s<sub>1</sub>,t<sub>1</sub>)
<b><font color="#0000FF">and</font></b> eq(s<sub>2</sub>,t<sub>2</sub>))
<br>
<b>
<font color="#0000FF">ELSE return</font></b>(<font color="#0000FF">false</font>) <br>
<b> <font color="#0000FF">END</font></b> <br>
<br>
<b>图5.30</b> 两个类型表达式s和t的结构等价测试
</p>
</td></tr></table>
<table><tr><td>    </td>
<td class="content">
<P>
在实际使用中，结构等价的概念常常需要修改以反映源语言的实际类型检查规则。例如，当数组作为参数传递时，我们可以不希望它的界作为类型的一部分，图中关于数组等价测试可改变为
</p>
</td></tr></table>
<table width="487"><tr><td width="16">    </td>
<td class="content" width="457">
<P>
<b><font color="#0000FF">IF</font></b> (s=ARRAY(s<sub>1</sub>,s<sub>2</sub>))
<b><font color="#0000FF">and</font></b> (t=ARRAY(t<sub>1</sub>,t<sub>2</sub>))
<b><font color="#0000FF">THEN</font></b> <br>
<b> <font color="#0000FF">return</font></b>(eq(s<sub>2</sub>,t<sub>2</sub>))
</p>
</td></tr></table>
<table><tr><td>    </td>
<td class="content">
<P>
结果，在判断s和t是否等价中忽略了他们的界。
</p>
</td></tr></table>
<br>
<hr size=2 color=red width=90%>
<br>
<table><tr><td>    </td>
<td class="content">
<P>
<b>类型表达式中的名字 </b>
</p>
</td></tr></table>
<table><tr><td>    </td>
<td class="content">
<P>
在某些语言中，类型可以命名。例如，在Pascal程序片段(5.9)中，标识符Link 被声明为类型↑cell的名字，其实cell也是个类型名称。
</p>
</td></tr></table>
<table><tr><td>    </td>
<td class="content">
<P>
<b><font color="#0000FF">TYPE</font></b> Link=↑cell; <br>
<b> <font color="#0000FF">VAR</font></b> <font color="#0000FF">
</font> next:Link; <br>
Last:Link; <br>
P: ↑cell; (5.9) <br>
q,r: ↑cell; <br>
</p>
</td></tr></table>
<table><tr><td>    </td>
<td class="content">
<P>
为了适应这种情况，类型表达式中允许出现名字。在这种情况下，类型等价的含义取决于如何看待类型表达式中的名字。所谓名字等价，是把每一个类型名字看成一个特殊的类型，因此，两个类型表达式名字等价当且仅当他们是完全一样的。在结构等价中，名字被它们代表的类型表达式代替，在类型表达式中的所有名字被替换后，两个类型表达式等价即是结构等价。
</p>
</td></tr></table>
<table><tr><td>    </td>
<td class="content">
<P>
<b>例5.26</b> 下面给出和声明（5.9）中的5个变量相联系的类型表达式。
</p>
</td></tr></table>
<table><tr><td>    </td>
<td class="content">
<P>
变 量 类 型
表 达 式 <br>
next
Link
<br>
last
Link <br>
p
Pointer(cell) <br>
q
Pointer(cell)
<br>
r
Pointer(cell)
</p>
</td></tr></table>
<table><tr><td>    </td>
<td class="content">
<P>
在名字等价下，变量next和last有同样的类型，因为它们的类型表达式是同一个类型名，但是，next和p的类型不相同，因为它们有不同的类型表达式。在结构等价下，所有五个变量都有同样的类型。 不同的语言中，变量标识符和类型通过声明联系的规则是不同的，在解释这些规则时，结构等价和名字等价是两个有用的概念。
</p>
</td></tr></table>
<table><tr><td>    </td>
<td class="content">
<P>
<b>例5.27</b> 在一些Pascal的实现中，用隐含的类型名和每个声明的变量标识符相联系，如果声明中出现没有名字的类型表达式，就建立一个隐含的类型名。每当变量声明中出现类型表达式，就建立一个新的类型名。于是，在(5.9)中，分别为p,q和r的声明建立两个隐含的类型名np和nqr。即，把（5.9）看成：
</p>
</td></tr></table>
<table><tr><td>    </td>
<td class="content">
<P>
<b><font color="#0000FF">TYPE</font></b> <br>
sLink=↑cell; <br>
np=↑cell; <br>
nqr=↑cell; <br>
<b><font color="#0000FF">VAR</font></b> <br>
next:link; <br>
last:link; <br>
p:np; <br>
q,r:nqr; <br>
</p>
</td></tr></table>
<table><tr><td>    </td>
<td class="content">
<P>
在名字等价下，next和last类型等价，q和r类型等价，而next、p、q类型不等价。 典型的实现是构造一张类型图，每当遇到类型构造符和基本类型，就建立一个新结点，但要记住类型名所命名的类型表达式。在这种方法中，如果两个类型表达式用类型图中同样的结点表示，那么，它们等价。图5.31描述了(5.9)声明的类型图。虚线表示变量和类型图结点的联系。注意，类型名cell有三个父结点，它们都标记为POINTER，等价出现在类型名Link和用它命名的类型图之间。
</p>
<center><img src="images/5_31.gif"></center>
</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='5.8.1_1.htm'"></img></td>
<td><img src="../images/next.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='5.8.2.htm'"></img></td>
</tr>
</table>
</BODY>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -