面向实验教学的可拆卸小型编译器设计

谌志群　王小华

【摘要】“编译原理”是计算机专业的重要专业课之一，理论性和实践性要求均很高，在计算机本科教学体系中占有十分重要的地位。设计实现了一个面向“编译原理”实验教学的可拆卸小型编译器——SMini。详细介绍了SMini的系统结构、设计方法与实现技术。

【关键词】 编译原理；编译器；实验教学；可拆卸

【中图分类号】G40-057【文献标识码】A 【论文编号】1009—8097（2009）06—0111—03

编译系统作为计算机系统最基本的组成部分，已发展成为一门具有完整的理论、方法和技术的计算机学科[1][2]。国内外高校都将“编译原理”列为计算机专业的主要课程，它对提高学生软件设计素养，认识计算机信息处理本质起着重要作用。“编译原理”是门实践性很强的课程，实验是课程教学过程中很重要的一个环节。目前国内的大多数高校在“编译原理”课程的实践环节都是不分授课对象要求学生能上机实现一个小型模型语言的完整编译程序。在只是空洞地学习了一些编译理论与算法并且没有很好掌握的情况下，这对于大部分学生来说都是不可能完成的任务。造成很大部分学生在动手之前就早早放弃了努力，也就不可能达到预定的实验效果。为了解决这个问题，在教学实践中，设计了一个简单的具有高级语言主要特点的模型语言（本文称S语言），设计了该语言的目标代码格式，实现了从源语言到目标代码转化的小型编译器（本文称SMini）的各个模块，给出了模块之间接口的定义。模块是可拆卸的，在实验教学时可根据实际情况要求学生实现S语言编译系统的部分模块，并且实现的模块可以方便地嵌入到SMini中进行测试。本文详细介绍了SMini编译器的系统结构、核心模块的设计方法与实现技术。

一 模型语言

本文设计的模型语言（S语言）的文法用类产生式系统描述如下：

（1） <程序>→[<常量说明>][<变量说明>]<语句>

（2） <常量说明>→Const <常量定义>{，<常量定义>}；

（3） <常量定义>→<标识符>＝<无符号整数>

（4） <无符号整数>→<数字>{<数字>}

（5） <字母>→a|b|c| … |z

（6） <数字>→0|1|2| … |9

（7） <标识符>→<字母>{<字母>|<数字>}

（8） <变量说明>→Var <标识符>{，<标识符>}；

（9） <语句>→<赋值语句>|<条件语句>|<当循环语句>|<读入语句>|<输出语句>|<复合语句>|ε

（10） <赋值语句>→<标识符>＝<表达式>;

（11） <表达式>→[＋|－]<项>{<加法运算符><项>}

（12） <项>→<因子>{<乘法运算符><因子>}

（13） <因子>→<标识符>|<无符号整数>|‘(<表达式>‘)

（14） <加法运算符>→＋|－

（15） <乘法运算符>→* |／

（16） <条件语句>→if <条件> then <语句>| if <条件> then <语句> else <语句>

（17） <条件>→<表达式><关系运算符><表达式>

（18） <关系运算符>→＝＝|＜＝|＜|＞|＞＝|＜＞

（19） <当循环语句>→while <条件> do <语句>

（20） <复合语句>→begin <语句>{；<语句>} end

注：产生式中<、>括起的部分表示一个非终结符号，[、]括起的部分表示可选项，{、}括起的部分表示可重复，符号 | 表示“或”。

上述模型语言具有高级程序设计语言的主要特点，也是SMini编译器处理的源语言。

二 系统设计与实现

1 系统结构

整个系统由3个模块构成，包括源程序编辑模块、编译模块和信息输出模块。各个模块又包含若干子模块。系统结构如图1所示。

源程序编辑模块主要实现源程序的 编辑的工作，在主屏幕窗口中可以输入、修改源程序，通过菜单栏可以新建 、打开、保存S语言源代码文件。编译模块完成实际的编译功能，分为4个子步骤：词法分析、语法分析、语义分析、目标代码生成。信息输出模块有两个子模块：错误信息输出和中间结果输出。错误信息输出子模块实时输出编译时刻的错误信息。中间结果输出子模块通过一个窗口来察看编译信息文件，包括词法分析结果，语法分析结果（语法树）， 语义分析结果（符号表）和三地址代码。为了屏蔽机器代码的复杂性，SMini采用三地址代码作为目标代码。

2 核心模块设计

（1） 词法分析模块

词法分析模块的主要功能是识别S语言源程序中的记号（Token）。Token的识别由函数getToken来完成。函数getToken每次被调用时从输入缓冲区中读入输入字符序列并识别一个Token。该函数采用基于DFA状态转换图的算法，起始状态为START，结束状态为DONE。每次调用，该函数从起始状态START开始，不断调用getNextChar函数，根据其返回值进行相应的状态转移，一直到当前状态为DONE为止。函数中使用另一个变量save用来指定是否将读入的字符存入全局变量tokenString中。一般来说，构成一个Token的所有有效字符都将被存入tokenString，而空白，注释和将被退回的字符不被存入tokenString。此外，如果编译选项TraceScan被设为真，该函数还将调用函数printToken打印当前Token的有关信息到编译信息文件中，包括行号和Token的类型。

（2） 语法分析模块

语法分析模块的功能是以词法分析程序生成的Token序列作为输入，在分析过程中验证这个Token序列是否符合S语言的文法。若是，则以语法树作为输出；若不是则指明错误，并指出错误的性质和位置。关键问题是建立语法树，这里采用了自顶向下的递归分析法来实现，即为每一条产生式写一个match函数，从顶部（树根）到底部（树叶）来建立语法树。match函数的基本逻辑是根据S语言文法比较实际的Token与预计的Token是否一致，如果一致则取下一个Token，如果不一致则给出错误类型并调用syntaxError函数输出错误。实际的语法树是以为文本形式输出的。语法树中的父子关系由文本行开头的数字序列和嵌套关系来体现。如一个简单语句“while a>0 do a=a-1;”的语法树如图2所示。

图2 语法树的文本输出形式

（3） 语义分析模块

语义分析部分的主要功能是遍历语法分析时建立的语法树，建立符号表并进行简单的类型检查，即判断源程序中语句部分中的变量是否已定义和是否赋值给常量。S语言没有作用域信息，并且所有的变量都是整型，符号表数据结构BucketList设计如下：

typedef struct LineListRec

{ int lineno;

struct LineListRec * next;

} * LineList;

其中：lineno为常量或变量所在的行的行号，next指向下一同类型标识符。

（4） 目标代码生成模块

目标代码生成部分的主要功能是生成与源程序等价的三地址代码。主要函数是CGen::cGen( TreeNode * tree,int snextl)。由于建立语法树时语句和表达式都是FirstK类型的结点，所以它仅检测此类型的节点，并根据不同的分类作相应处理，然后递归调用 自身完成对整个语法树的遍历。例：语句“while a>0 do a=a-1;”对应的三地址代码如图3所示。

图3 三地址代码序列

3 系统实现与界面设计

SMini在Visual C++集成环境[3]下开发。首先用MFC AppWizard创建工程文件，建立后会自动生成文件：应用程序：CsminiApp类，框架：CmainFrame类，文档：CsminiDoc类，视窗：CsminiView类，对话框有关的CaboutDlg类，还包括了一些在主框架中的初始化工具条的工作，在此基础上实现具体的功能与界面。软件界面采用单文档构架，拆分窗口视图，界面主要分为五个部分：菜单栏、工具栏、编辑区、信息输出区和状态栏。操作方法与目前流行的编译器相似，可通过窗口实现源程序的编辑、修改、编译与信息察看。系统主界面如图4所示。

图4 系统界面

三 结束语

“编译原理”课程是计算机科学与技术专业的主干必修课，也是软件工程专业的重要专业基础课。实验教学是“编译原理”课程教学的重要环节也是薄弱环节，通过开发辅助实验教学系统提高课程实验教学的效果具有现实意义。设计开发了一个简单模型语言的可拆卸编译器，可辅助课程实践环节的教学，解决了以往由于设计一个完整的编译器难度与工作量太大，造成实验效果不好的弊端。该系统还可提高教师验收学生实验成果的效率，在实际的教学过程中已取得了较好的效果。

参考文献

[1] Alfred V Aho, Ravi Sethi, Jeffrey D Ullman. Compilers:Principles,Techniques,and Tools[M].北京:人民邮电出版社,2002:1-24.

[2] 张素琴,吕映芝,蒋维杜等.编译原理(第2版)[M].北京:清华大学出版社,2005:1-11.

[3] 朱磊,周彬.Windows下的C/C++高级编程[M].北京:人民邮电出版社,2002:1-120.

Dismountable Mini Compiler Design for Experiment Teaching

CHEN Zhi-qun WANG Xiao-hua

(Institute of Computer Application Technology, Hangzhou Dianzi University, Hangzhou, Zhejiang, 310018, China)

Abstract: Compiler principle is one of the important specialized courses in the computer science, requiring highly both in theory and practice, and it occupy the essential position in the computer's teaching system. SMini- a dismountable mini compiler for experiment teaching of compiler principle is implemented. This paper introduces the system architecture, design method and implementation technology of SMini.

Keywords: Compiler Principle; Compiler; Experiment Teaching; Dismountability