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

<font class="title2"><b>2.3 分析树（parse tree）和二义性</b></font><br><br>  
<font class="title2"><b>2.3.1 分析树</b></font><br>  
<table><tr><td>&nbsp&nbsp&nbsp&nbsp</td>  
<td class="content">  
<p>  
分析树亦称推导树，用来表示一个句型的推导。  
</p>  
<p>  
我们知道一棵树(严格地说，有序有向树)是一个具有如下性质的图：<br>  
&nbsp&nbsp&nbsp&nbsp1.有一个称作根的结点，它无前趋，并且从它到每一个结点只有一条路径；<br>  
&nbsp&nbsp&nbsp&nbsp2.除根以外，每个结点恰有一个前趋；<br>  
&nbsp&nbsp&nbsp&nbsp3.每一个结点的后继“自左”排序。  
</p>  
<p>  
我们将把树的根画在顶上，并让所有的弧(结点到结点的弧)都指向下面。因此，弧上的箭头已不需要用来表明方向了，故而它们将不表示出来。每个结点的后继按自左至右的顺序画出来。  
</p>  
<p>  
对于树而言，有它的特殊术语，与一般图中使用的术语不太一样。结点的后继称作儿子，或子结点，前趋称作父亲，或父结点。若有一条路径自结点v<sub>1</sub>到结点v<sub>2</sub>，那么v<sub>1</sub>称作v<sub>2</sub>的先辈；而v<sub>2</sub>称作v<sub>1</sub>的后裔。没有儿子的结点称为叶，其它结点称为内部结点。  
</p>  
<p>  
我们若把树的每一结点给以编号，并用文法的终结符号或非终结符号加以标记，必要时也可以标上ε；即把这些结点与推导中用到的产生式有机地联系起来；这样，就可以用树来描述句型的推导了。  
</p>  
<p>  
形式地说，设G=(V<sub>T</sub>，V<sub>N</sub>，S，P)是一个上下文无关文法。一棵树是G的一棵分析树，如果：<br>  
&nbsp&nbsp&nbsp&nbsp1. 每一个结点有一个标记，此标记是V<sub>T</sub>∪V<sub>N</sub>∪{ε}中的符号。<br>  
&nbsp&nbsp&nbsp&nbsp2．根的标记是S。<br>  
&nbsp&nbsp&nbsp&nbsp3．如果一个结点是内部结点，且有标记A,那么A必在V<sub>N</sub>中。<br>  
&nbsp&nbsp&nbsp&nbsp4．如果编号为n的结点有标记A,结点n<sub>1</sub>,n<sub>2</sub>,…,n<sub>k</sub>是点n的从左到右的儿子，并分别有标记X<sub>1</sub>,X<sub>2</sub>,…,X<sub>k</sub>，则<br>  
<center> A→X<sub>1</sub>X<sub>2</sub>…X<sub>k</sub> </center>  
必须是P中的产生式。<br>  
&nbsp&nbsp&nbsp&nbsp5. 如果结点n有标记ε，那么结点n是叶子，且是它父亲唯一的儿子。  
</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.2.2j.htm'"></img></td>
<td><img src="../images/next.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='2.3.1b.htm'"></img></td>
</tr>  
</table>  
  
</BODY>  
</html>
⌨️ 快捷键说明

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