⭐ 欢迎来到虫虫下载站！ | 📦 资源下载 📁 资源专辑 ℹ️ 关于我们
⭐ 虫虫下载站
📤 上传资源

📄 explain.htm

📁 建立《编译原理网络课程》的目的不仅使学生掌握构造编译程序的原理和技术
💻 HTM
📖 第 1 页 / 共 4 页
字号:
🔍
1234 
<html>

<head>
<title>程序讲解</title>
<style>
.unnamed1 {  font-family: "宋体"; font-size: 9pt; text-decoration: none; color: #666666}
body {  font-family: "宋体", "仿宋_GB2312", "楷体_GB2312"; font-size: 9pt}
tr {  font-family: "宋体", "仿宋_GB2312", "楷体_GB2312"; font-size: 9pt}
body {
background-color:#FFFFFF;
SCROLLBAR-FACE-COLOR: #f0f0f0;
SCROLLBAR-HIGHLIGHT-COLOR: #ffffff;
SCROLLBAR-SHADOW-COLOR: #339966;
SCROLLBAR-3DLIGHT-COLOR: #339966;
SCROLLBAR-ARROW-COLOR: #000000;
SCROLLBAR-TRACK-COLOR: #f0f0f0;
SCROLLBAR-DARKSHADOW-COLOR: #ffffff
}
a { text-transform: none; text-decoration: none }
-->
</style>
</head>

<body topmargin="0" leftmargin="0" marginheight="0" marginwidth="0" bgcolor="#FFFFFF" text="#669933" link="#CC3300" bgproperties="fixed" background="bj.gif">

<p>这个程序的主要程序模块有七个，分别为：</p>

<p>1、<a href="#1">信息表管理模块</a></p>

<p>2、<a href="#2">主程序</a></p>

<p>3、<a href="#3">初始化模块</a></p>

<p>4、<a href="#4">词法分析模块</a></p>

<p>5、<a href="#5">语法语义分析模块</a></p>

<p>6、<a href="#6">收尾处理模块</a></p>

<p>7、<a href="#7">错误处理模块</a></p>

<p>这和我们前面所学的知识是一致的，只不过我们将语法分析、语义分析合为了一个模块——语法语义分析模块。另外，我们剔除了中间代码的生成，直接生成目标代码。这个程序执行完成后，所产生的目标程序就可以直接在虚拟机上运行了。</p>

<p>下面分别介绍这些模块的功能和原理。</p>

<h2><a name="1">（一）</a><a href="source.htm#op hashtable" target="ff2">信息表管理模块</a></h2>

<p>首先让我们来看信息表管理模块。这个模块涉及到本程序大部分的基本数据结构，包括符号表、<a
href="#作用域链">作用域链</a>堆栈和<a href="#名字链">名字链</a>。下面分别介绍。</p>

<h3 style="font-size: -15pt; font-family: 宋体">符号表</h3>

<p>编译程序使用符号表来保存关于标识符的作用域和有关联编信息。每当在源程序正文中遇到一个标识符时，就要在符号表中进行搜索。如果出现一个新的标识符或者对于已经存放在符号表中的标识符的新信息，符号表就要发生变化。符号表机制必须允许方便地加入新的表项并能有效的查找已经存在的表项。本程序中，使用的是散列表机制。</p>

<p>符号表中的每一个表项都是为一个标识符的说明而建立的。表项的格式不必是一致的，因为表中存放的有关标识符的信息是依赖于标识符的使用的。这些信息是在词法分析、语法语义分析的过程中陆续填入的。</p>

<h4 style="font-size: -13pt; font-family: 宋体">数据结构说明</h4>

<p>我们来看一下符号表表项的数据结构，这是一个记录类型的数据结构。在说明这个数据结构之前，我们先看一下这个数据结构中用到的类型定义。</p>

<p><a href="source.htm#str12" target="ff2">str12</a>：长为12个字符的字符串类型。</p>

<p><a href="source.htm#idtype" target="ff2">idtype</a>：枚举类型，用来表示标准类型中的整型和布尔型。</p>

<p><a href="source.htm#idpointer" target="ff2">idpointer</a>：指向符号表表项的指针类型。</p>

<p><a href="source.htm#field" target="ff2">field</a>：记录类型，记录了记录域的名字、类型和记录类型的内部偏址。</p>

<p><a href="source.htm#param" target="ff2">param</a>：记录类型，记录了参数的类型和是否为变参。</p>

<p>了解了这些类型定义，让我们来看<a
href="source.htm#identifier" target="ff2">符号表表项identifier</a>中每个记录项的说明如下： 

<ul>
  <li>name：长为12个字符的字符串类型变量，记录了标识符的名字。可以看出，本程序只识别标识符的前12个字符，超过12个字符的部分无效。</li>
  <li>size：整型变量，记录了这个标识符所需占内存的大小，以字节记。</li>
  <li>level：整型变量，记录了这个标识符的嵌套深度。令程序名字的嵌套深度为0；每当我们从一个包围过程进入到一个被包围过程时嵌套深度加1。过程（程序）名的嵌套深度总比过程（程序）内部变量的嵌套深度少1。嵌套深度的概念是用来实现词法作用域规则的。</li>
  <li>next_hash_id：指向表项的指针，本程序使用开放散列表技术，这里的“开放”是指对于表中同一个索引值的表项的个数不加限制。这些对应同一索引值的表项被这一指针链接到一起的，这条链叫做索引链。</li>
  <li>next_varList_id：指向表项的指针，同一个过程的所有表项被这一指针连接到一起，所以这条链又叫<strong><a
    name="作用域链">作用域链</a></strong>。当处理完一个过程的作用域时可以利用作用域链把该过程的所有表项从散列表中删除。</li>
  <li>idclass：1至6之间的整数，表示这个标识符的类型。标识符可以是常数名、数组类型名、记录类型名、标准类型名（整型或布尔型）、变量名、过程名，这时idclass分别取1、2、3、4、5、6。</li>
  <li>value：整型变量，若此标识符为常数名时，它表示这个常数的值。</li>
  <li>consttype：idtype类型变量，若此标识符为常数名时，它表示这个常数的类型，整型还是布尔型。</li>
  <li>minindex，maxindex：整型变量，若此标识符为数组类型名时，它们表示这个数组类型下标的上下界。</li>
  <li>indextype：idtype类型变量，若此标识符为数组类型名时，它表示这个数组类型的下标类型。</li>
  <li>elementtype：指向表项的指针，若此标识符为数组类型名时，它指向这个数组元素的类型所对应的表项。</li>
  <li>items：field类型的数组，若此标识符为记录类型名时，它记录着这个记录类型的所有域的名字、类型和记录类型的内部偏移量。</li>
  <li>itemnum：整型变量，若此标识符为记录类型名时，它记录着这个记录类型的域的个数。</li>
  <li>typename：idtype类型变量，若此标识符为标准类型名，它表示这个标准类型是整型还是布尔型。</li>
  <li>vartype：指向表项的指针，若此标识符为变量名，它指向这个变量的类型所对应的表项。</li>
  <li>offset：整型变量，若此标识符为变量名，它记录了这个变量的偏移量。</li>
  <li>isvarparam：布尔型变量，若此标识符为变量名，它记录了这个变量是否为变参。</li>
  <li>isStandard：布尔型变量，若此标识符为过程名，它记录了这个过程是否为标准过程read，write。</li>
  <li>params： param类型的数组，若此标识符为过程名，它记录了这个过程所需参数的类型和这个参数是否为变参。</li>
  <li>paramnum：整型变量，若此标识符为过程名，它记录了这个过程所需参数的个数。</li>
  <li>paramlength：整型变量，若此标识符为过程名，它记录了这个过程所需参数总共占内存的大小，以字节记。</li>
  <li>address：整型变量，若此标识符为过程名，它记录了这个过程在目标文件中的位置。</li>
</ul>

<h4 style="font-family: 宋体; font-size: -13pt">操作说明</h4>

<p>了解了符号表的数据结构，下面我们来看一下符号表的基本操作，它包括符号表的查找、当前层查找、插入、删除当前表项、删除当前层，共五个。</p>

<h5 style="font-size: -11pt; font-family: 仿宋_GB2312">散列函数计算—<a
href="source.htm#hashindex" target="ff2">hashindex函数</a></h5>

<p>在介绍这些符号表操作之前，我们必须先了解符号表的组织情况。由于本程序中的符号表采用开放散列表技术，即根据名字计算出的散列值将标识符散列到符号表中，对应同一散列值的符号表表项用next_varList_id链接起来。所以我们先来看一下散列值的计算。</p>

<p>输入：名字字符串s</p>

<p>输出：此名字对应的散列值</p>

<p style="font-size: -11pt; font-family: 宋体 ">步骤： 

<ol>
  <li>用名字字符串s之中的所有字符确定一个正整数h。一个简单的方法是将字符串中的所有字符对应的整数值加在一起，更好的方法是在加入下一个字符的值以前将老的h值乘以一个常数a。本程序采用了第二种方法，a值取为16，即将老的h值左移了四位。</li>
  <li>把上面确定的整数h转化成散列表的编号，最简单的方法是用h除以散列表的长度，把余数作为散列值。这时，散列表长度为素数是效果最好，本程序的散列表长度取为211。</li>
</ol>

<h5 style="font-size: -11pt; font-family: 宋体"><font face="仿宋_GB2312">符号表的查找—<a
href="source.htm#lookup" target="ff2">lookup函数</a></font></h5>

<p>后面将要介绍的插入操作是从符号表的前端进行的，<font
face="宋体">查找时也应从前端开始。这样，后定义的标识符在靠近前端的地方，可以先找到，而屏蔽掉以前的定义；当前层未定义的标识符也可以找到其最近的定义。</font>符合作用域规则。</p>

<p>输入：名字字符串</p>

<p>输出：若此名字存在于符号表中，输出对应表项的指针；否则，输出空指针nil</p>

<p>步骤： 

<ol>
  <li>求出此名字对应的散列值。 </li>
  <li>根据这个散列值在符号表中顺着next_hash_id查找，看符号表项的name域记录的内容与输入的名字字符串是否相同。</li>
  <li>如果找到相同者，则返回这个符号表项的指针；如果到链的末尾仍没有，则返回空指针。</li>
</ol>

<h5 style="font-size: -11pt; font-family: 宋体"><font face="仿宋_GB2312">当前层符号表的查找—<a
href="source.htm#lookup_in_curLevel" target="ff2">lookup_in_curLevel函数</a></font></h5>

<p style="font-size: -11pt; font-family: 宋体">由于同一层的符号表中不允许出现相同的名字，所以将一个名字插入符号表时，必须在当前层的符号表中查找，确定没有相同名字的表项时才能插入。</p>

<p>输入：名字字符串</p>

<p>输出：若此名字存在于符号表的当前层中，输出对应表项的指针；否则，输出空指针nil</p>

<p>步骤： 

<ol>
  <li>求出此名字对应的散列值。</li>
  <li>根据这个散列值在符号表中顺着next_hash_id查找，注意只在level域等于curLevel的表项中查找。</li>
  <li>如果找到满足条件的表项，返回对应的指针；否则，如果到达链的末尾或level域已经不在等于curLevel时仍未找到，则返回空指针。</li>
</ol>

<h5 style="font-size: -11pt"><font face="仿宋_GB2312">符号表的插入操作—<a
href="source.htm#insert" target="ff2">insert函数</a></font></h5>

<p><font face="宋体">插入操作是在符号表的前端进行的，原因在前面查找操作的介绍中已经给出。</font></p>

<p><font face="宋体">输入：名字字符串</font></p>

<p><font face="宋体">输出：新插入表项的指针；如果出现重定义，则返回空指针</font></p>

<p style="font-size: -11pt; font-family: 仿宋_GB2312"><font face="宋体">步骤：</font> 

<ol>
  <li><font face="宋体">在当前层查找是否有重定义出现。</font></li>
  <li><font face="宋体">若 没有重定义 则 
    求出此名字对应的散列值；为此名字分配一个新表项，填写此表项的name，level域；将这个表项插入索引链的前端和作用域链的前端。返回新表项的指针。</font></li>
  <li><font face="宋体">若 已存在相同名字的表项 则 返回空指针。</font></li>
</ol>

<h5 style="font-size: -11pt; font-family: 仿宋_GB2312"><font face="仿宋_GB2312">删除当前表项操作—<a
href="source.htm#deleteCurent" target="ff2">deleteCurent过程</a></font></h5>

<p><font face="宋体">在对标识符定义部分进行语法分析时，要填写符号表。如果已经将标识符插入符号表了，却发现这个标识符的定义有错误，这时，就要将这个标识符从符号表中删除，以免影响以后的语法分析。</font></p>

<p><font face="宋体">考虑到插入操作都是在索引链和作用域链的前端进行的，新插入表项应该就是索引链和作用域链最前端的表项。</font></p>

<p style="font-size: -11pt; font-family: 仿宋_GB2312"><font face="宋体">步骤：</font> 

<ol>
  <li><font face="宋体">计算作用域链前端指针curProVarL指向的表项的索引值。</font></li>
  <li><font face="宋体">用一个临时变量指向作用域链最前端表项。</font></li>
  <li><font face="宋体">改变索引链和作用域链的前端指针。</font></li>
  <li><font face="宋体">收回临时变量指向的表项所占用的空间。</font></li>
</ol>

<h5 style="font-size: -11pt; font-family: 仿宋_GB2312"><font face="仿宋_GB2312">删除当前层所有标识符的操作—<a
href="source.htm#del_curProVarList" target="ff2">del_curProVarList过程</a></font></h5>

<p><font face="宋体">当对一个过程完成语法语义分析，就要将这个过程中定义所有标识符从符号表中删除，表示这些局部变量不在起作用。</font></p>

<p><font face="宋体">考虑到作用域链将这个过程中的所有局部变量串联起来，我们可以顺着作用域链将表项从符号表中删除。</font></p>

<p style="font-size: -11pt; font-family: 仿宋_GB2312"><font face="宋体">步骤：</font> 

<ol>
  <li><font face="宋体">顺着作用域链，改变与表项有关的索引链，删除表项</font></li>
</ol>

<h3 style="font-size: -15pt; font-family: 宋体">作用域链的栈</h3>

<p>我们已经知道同一个过程中的局部变量是被作用域链连接在一起的。当分析完一个过程时，这个过程中的所有局部变量将被取消，取而代之的应该是这个过程的外围过程的局部变量。即当前的作用域链被老的作用域链取代。所以，作用域链应该用栈来保存。每当开始分析一个新过程时，老的作用域链被栈保存起来，开始一条新的作用域链；当这个过程分析完成时，当前作用域链上的局部变量都被取消，老的作用域链从栈中弹出，取代新链的地位。</p>

<h4>数据结构说明</h4>

<p><a href="source.htm#curProVarL" target="ff2">curProVarL</a>：idpointer类型变量，为指向当前作用域链链头的指针。作用域链的栈的作用就是保存这个指针，能够访问这个指针，就能够访问整条作用域链。</p>
1234

⌨️ 快捷键说明

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