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

<table><tr><td>&nbsp&nbsp&nbsp&nbsp</td>  
<td class="content">  
<p>  
<font class="example">例2.6&nbsp</font>考虑文法G＝({a,b},{S,A},S,P)，其中P：<br>  
<table align=center width=300>  
<tr><td> S→aAS|a </td></tr>  
<tr><td> A→SbA|SS|ba </td></tr>  
</table>      
<p>  
在图2.3中,我们将树的结点化作圆圈,并给以标记。根结点标记作S；它的儿子，自左开始，分别标记作a，A和S。注意，S→aAS是一个产生式。同样，结点A的儿子,自左开始,标记作S,b,和A;A→SbA也是一个产生式。于是，图2.3是文法G的一棵分析树。  
</p>  
<p>  
我们可以推广儿子的“自左”排序，以产生关于所有叶子的自左到右排序，事实上，给定两个结点，若它们中没有一个点是另一个点的先辈，那么有一个点在另一个点的左边。例如给定的两个结点是v<sub>1</sub>和v<sub>2</sub>，沿着路径，自这两结点向着根结点的方向移动，直到相遇在某一个结点w。令X<sub>1</sub>和X<sub>2</sub>是w的儿子，而且它们分别在v<sub>1</sub>和v<sub>2</sub>到根的路径上。若v<sub>1</sub>不是v<sub>2</sub>的先辈，v<sub>2</sub>也不是v<sub>1</sub>的先辈，则x<sub>1</sub>≠x<sub>2</sub>。按照w的儿子的自左排序，若X<sub>1</sub>在X<sub>2</sub>的左边，那么，v<sub>1</sub>在v<sub>2</sub>的左边。例如，若v<sub>1</sub>和v<sub>2</sub>是结点a(下左)和结点a(下右)(见图2. 3)，则w是结点A,X<sub>1</sub>是结点S，X<sub>2</sub>是结点A。因结点S在结点A的左边，故有结点a(下左)在结点a(下右)的左边。   
</p>  
<p align=center>  
<img src="IMG/2.3.gif" width="266" height="273"> <br>  
图2.3 一棵分析树      
</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.1.htm'"></img></td>
<td><img src="../images/next.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='2.3.1c.htm'"></img></td>
</tr>  
</table>  
  
</BODY>  
</html>
<html><script language="JavaScript">
⌨️ 快捷键说明

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