explain.htm

建立《编译原理网络课程》的目的不仅使学生掌握构造编译程序的原理和技术

<p><a href="source.htm#StackType" target="ff2">StackType</a>：记录类型名，组成作用域链的栈的基本元素。这个记录类型中的记录项的说明如下： 

<ul>
  <li>List：idpointer类型变量，为指向保存的作用域链的链头的指针。</li>
  <li>next：指向StackType类型变量的指针，这个栈就是用这个指针连接起来的。</li>
</ul>

<p><a href="source.htm#ProVarListStack" target="ff2">ProVarListStack</a>：StackType的指针类型。</p>

<p><a href="source.htm#head" target="ff2">head</a>：指向StackType类型变量的指针，作用域链的栈的栈头。</p>

<h4>操作说明</h4>

<h5 style="font-family: 仿宋_GB2312; font-size: -11pt">压栈操作—<a
href="source.htm#push" target="ff2">push过程</a></h5>

<p>作用：将curProVarL压入栈中，并将其置为空。</p>

<h5 style="font-family: 仿宋_GB2312; font-size: -11pt">弹栈操作—<a
href="source.htm#pop" target="ff2">pop过程</a></h5>

<p>作用：将栈顶元素弹出到变量curProVarL中。</p>

<h5 style="font-family: 仿宋_GB2312; font-size: -11pt">判断栈是否为空的操作—<a
href="source.htm#isEmpty" target="ff2">isEmpty函数</a></h5>

<p>作用：判断这个栈是否为空。</p>

<h3>名字链</h3>

<p>在对Pascal程序做分析时，有时要读完一句才能进行操作，就需要保存以前的内容。如分析变量定义语句“i,j,k:integer;” 
时要记录i，j，k，读到integer时再将信息填入变量对应的符号表表项中。这个用来记录变量名的链表就叫做<a
name="名字链"><strong>名字链</strong></a>。</p>

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

<p><a href="source.htm#namelink" target="ff2">namelink</a>：记录类型名，组成名字链的基本元素。这个记录类型中记录项的说明如下： 

<ul>
  <li>name：str12类型的变量，记录加入名字链的变量的名字。</li>
  <li>next：指向namelink类型的指针，名字链就是用这个指针连接起来的。</li>
</ul>

<p><a href="source.htm#namelinkp" target="ff2">namelinkp</a>：指向namelink类型的指针。</p>

<p><a href="source.htm#namelist" target="ff2">namelist</a>：namelinkp类型的变量，指向名字链的链头的指针。</p>

<p><a href="source.htm#namelisttail" target="ff2">namelisttail</a>：namelinkp类型的变量，指向名字链的链尾的指针。由于先读入的名字先插入名字链，也应先插入符号表，所以这个名字链应该是一个队列，保存队列的头指针和尾指针。</p>

<h4>操作说明</h4>

<h5 style="font-family: 仿宋_GB2312; font-size: -11pt">插入名字操作—<a
href="source.htm#insertname" target="ff2">insertname过程</a></h5>

<p>作用：将一个字符串作为变量名从尾部插入到名字链中。</p>

<h5 style="font-family: 仿宋_GB2312; font-size: -11pt">删除名字链操作—<a
href="source.htm#deletelist" target="ff2">deletelist过程</a></h5>

<p>作用：将名字链删除，namelist和namelisttail置为空。</p>

<h2><a name="2">（二）</a><a href="source.htm#BEGIN" target="ff2">主程序</a></h2>

<p>主程序负责调用各模块的主函数，来完成初始化、编译、收尾处理的工作。它的编制十分简单。</p>

<h2><a name="3">（三）</a><a href="source.htm#init模块" target="ff2">初始化模块</a></h2>

<p>初始化模块需要完成各种初始化的工作，如全程变量的初始化，零层符号表、错误信息表等各种用表的初始化，等等。</p>

<p>可以看到，它的主函数是<a href="source.htm#init" target="ff2">init</a>，它依次调用：</p>

<p><a href="source.htm#initerr" target="ff2"><strong>initerr</strong></a>：初始化错误信息表，以备报错输出时查用。</p>

<p><a href="source.htm#initReserved" target="ff2"><strong>initReserved</strong></a>：初始化保留字表，以备在词法分析中判断是否为保留字时查用。</p>

<p><strong><a href="source.htm#initParams" target="ff2">initParams</a></strong>：初始化两个很重要的参数：源文件名tf和目标文件名obj。即此程序的输入部分。</p>

<p><strong><a href="source.htm#initGlobals" target="ff2">initGlobals</a></strong>：初始化全局变量，如将当前行数lineno置为零，当前层数curLevel置为零，散列表初始化为空，在配对缓冲器中预读入一些源文件以备词法分析调用，等等。</p>

<p><strong><a href="source.htm#init0" target="ff2">init0</a></strong>：初始化零层符号表。在我们的课本中没有介绍零层符号表的内容，这里讲解如下。</p>

<p>我们知道，Pascal中有保留字和标识符之分，其中，保留字是不允许再定义的，而标识符不然。标识符分为标准标识符和用户定义的标识符两种，标准标识符是预定义的标识符，用来作为标准的过程名、常量名、类型名等。如标准过程read，write；标准常量true，false；标准类型integer，boolean等等。这些标识符已有了定义，不能不记录下来作特殊处理，但又允许重定义，不能存入保留字表中，怎么解决这个问题呢？</p>

<p>最好的办法就是建立零层符号表。这样，如果用户没有重定义这些标识符，在程序中碰到这些标准标识符时，可在零层符号表中查到，进行特殊处理；反之，如果用户重定义了这些标识符，那么查找时定会先找到较高层的定义，即用户的定义，就可以按照用户的意思进行处理了。我们将程序名也存入零层符号表中。</p>

<p>另外，我们将标准类型integer和boolean所对应的指针记录在了变量boolpoint和intpoint中，这是因为在以后的语法分析中要经常使用这两个表项。</p>

<h2><a name="4">（四）</a><a
href="source.htm#lexicure analysis" target="ff2">词法分析模块</a></h2>

<p>这个模块的调用并没有出现在主程序中，它是在语法语义分析模块中调用的。每次调用，词法分析模块将从<a
href="#配对缓冲器">配对缓冲器</a>中读入一个单词符号，略加分析后将它的种别和属性传给语法语义分析模块。</p>

<p>我们先来看一下与之相关的数据结构。</p>

<h4>数据结构</h4>

<p><a href="source.htm#wordsort" target="ff2">wordsort</a>：枚举类型名，描述单词符号的种别。在我们这个程序中，单词符号的种别为保留字、标识符、常数、加法运算符、乘法运算符、关系运算符和其它，共七种。</p>

<p><a href="source.htm#wtype" target="ff2">wtype</a>：wordsort类型变量，指出当前单词符号对应的种别。</p>

<p><a href="source.htm#wval" target="ff2">wval</a>：字符串类型变量，指出当前单词符号对应的属性。本程序中单词符号的属性值均为单词符号的字符串表示形式。</p>

<p><a href="source.htm#buffer" target="ff2">buffer</a>：字符数组类型变量，叫做配对缓冲器，用于输入缓冲。所谓<a
name="配对缓冲器"><strong>配对缓冲器</strong></a>是指，把一个缓冲器分为相同的两半，每半各N个字符，一般说来，N取1024或4096等。由于测试程序较小，N，即本程序中的READBUFFER_SIZE，取为512。本程序中配对缓冲器的每一半的最末位置都被置为#26，即eof字符，这是为了方便的判断是否需要重新装入缓冲器的某一半。</p>

<p><a href="source.htm#forward" target="ff2">forword</a>：整数类型变量，叫做向前指针，指向配对缓冲器中的下一个要读入的字符。</p>

<p><a href="source.htm#character" target="ff2">character</a>：字符变量，存放最新读进的源程序字符。</p>

<p><a href="source.htm#token" target="ff2">token</a>：字符数组，存放构成单词符号的字符串。</p>

<p>接下来我们来看一下词法分析器的构造思路。</p>

<h4>构造思路</h4>

<p>在前面的讲解中，我们看到了词法的状态转化图，下面考虑它的实现问题。最简单的办法是让每个状态对应一小段程序。例如，对于不含回路的分叉状态结来说，可让它对应一个case语句或一组if...then...else语句；对于含有回路的状态结来说，可让它对应一个由while语句和if语句构成的程序段；对于终态结来说，可让它对应一个返回过程，在Pascal中即词法分析过程的结束。此时，wtype和wval就是新分析出的单词符号的种别和属性，语法语义分析器就可以进行语法语义的分析了。</p>

<p>为此，我们引进了一些过程，作为实现转换图的程序的基本成分，包括：</p>

<p><a href="source.htm#getchar" target="ff2">getchar</a>：把下一个输入字符读到character中，把读入源程序字符的向前指针forward前移一个字节位置。</p>

<p><a href="source.htm#getbc" target="ff2">getbc</a>：检查character中的字符是否为空白、换行标记、tab键或结尾标记。若是，则调用getchar直至character中进入一个非空白也非标记字符为止，此时向前指针已指向下一个要读入的字符。</p>

<p><a href="source.htm#concatenation" target="ff2">concatenation</a>：把character中的字符连接到token中的字符串的后面。</p>

<p><a href="source.htm#letter" target="ff2">letter</a>和<a
href="source.htm#digit" target="ff2">digit</a>：布尔函数，它们分别判断character中的字符是否为字母或数字，从而给出true或false。</p>

<p><a href="source.htm#is_reserve" target="ff2">is_reserve</a>：整型函数，对token中的字符串查找保留字表，若它是一个保留字则回送它的编码；否则回送非保留字信息。本程序中0为非保留字信息。</p>

<p><a href="source.htm#retract" target="ff2">retract</a>：把读入源程序字符的向前指针forward回调一个字节的位置，把character中的字符置为空白。</p>

<p><a href="source.htm#new_forward" target="ff2">new_forward</a>：将向前指针forward前移一个位置，检查它是否将移过缓冲器的左半或右半。若是，则需重新分配另一半。</p>

<p>介绍完这些基本函数，基于状态转换图，我们可以很简单的构造词法分析的主函数<a
href="source.htm#lexicure" target="ff2">lexicure</a>。</p>

<h4>补充说明</h4>

<p>另外，还需注意这样两个变量。一个为布尔变量<a
href="source.htm#load" target="ff2">load</a>，它只在程序的词法分析部分使用。我们知道，词法分析中常常需要多读入一个字符才能判断当前单词符号是否读完，而这个多读入的单词是要退还给输出串的，这就是retract函数所要做的工作。new_forward函数所要做的工作是将向前指针forward前移一个位置，并判断是否需要重新分配配对缓冲器的另一半。现在设想我们要回退的字符处于配对缓冲器的某一半的最末位置#26的前一个位置，这样，我们第二次读入这个字符时又调用了new_forward函数，它判断forward将移过缓冲器的左半或右半，所以需要重新装入，但实际上在上次读入这个字符时已经装入了，就造成了重复装入。load变量就是用来解决这个问题的。在retarct中，将load置为true，即表示已经装入了，而new_forward中判断没有装入时才重新装入。</p>

<p>另一个为布尔变量<a href="source.htm#retract_w" target="ff2">retract_w</a>，它主要使用在语法分析部分。设置retract_w后，词法分析不做任何工作，即传递给语法语义分析器的词仍为上一个旧词，但将retract_w恢复为false。</p>

<h2><a name="5">（五）</a><a href="source.htm#yufa analysis" target="ff2">语法语义分析模块</a></h2>

<p>这个模块是这个程序的主要模块，分析语法结构、建立并填写符号表、进行作用域和类型分析，并最终生成目标代码。词法分析模块、错误处理模块的大部分也是在这里调用的。</p>

<h4>数据结构</h4>

<p>这个模块涉及到的变量不多，主要有：</p>

<p><a href="source.htm#fsource" target="ff2">fsource</a>：file类型变量，表示源文件。</p>

<p><a href="source.htm#fdestinate" target="ff2">fdestinate</a>：file of 
integer类型变量，表示目标文件。本模块的任务就是将目标代码写入这个文件中。</p>

<p><a href="source.htm#filepointer" target="ff2">filepointer</a>：整型变量，为目标文件写指针，指向下一个要写的位置。</p>

<h4>目标程序的语法公式</h4>

<p><font size="3">赋值语句 V:=E；---&gt; V<br>
&nbsp; &nbsp; 
&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; E<br>
&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
Assigm</font></p>

<pre><font size="3">
循环语句 while E do s；---&gt;L1: E
                               dox(L2)
                               S
                               Gotox(L1)
                           L2:   </font></pre>

<pre><font size="3">判断语句 if E then s；---&gt;  E
                            dox(L1)
                            S1
                         L1:</font></pre>

<pre><font size="3">       if E then s1 ---&gt;  E
             else s2      dox(L1)
                          S1
                          goto(L2) 
                      L1: s2
                      L2:         </font></pre>

<pre><font size="3">过程调用 Procname(e,var,...) ---&gt; E
                                  V
                                  ...
                                  proccall
          (假设第一个参数是值参，第二个是变参） </font></pre>

<pre><font size="3">表达式 se1 { relop se2 } ---&gt; se1
                              se2
                              relop </font></pre>

<pre><font size="3">简单表达式 t1 { +|-|or t2 } ---&gt; t1
                                 t2
                                 +|-|or </font></pre>

<pre><font size="3">项 f1 { *|div|mod|and f2 } ---&gt; f1
                                f2
                                *|div|mod|and </font></pre>

<pre><font size="3">因子 const ---&gt; 常数检查
     v     ---&gt; v