葛寒松

(商丘师范学院 信息技术学院，河南 商丘 476000)

可扩展语言编译器的设计

葛寒松

(商丘师范学院 信息技术学院，河南 商丘 476000)

传统的编译器设计和实现的方法论限制了编程语言的开放性与可扩展性.一般在语言彻底定型后开始制作编译器，一旦语言扩展成新的语言，就需要重新开发一个编译器.可扩展语言编译器的设计过程中，考虑语言的进一步扩展，编译器开发也会为进一步扩展预留一定的接口.开发过程中，严格遵守软件开发的基本法则，应用软件工程中的增量模型，进行迭代开发，开发过程通过利用面向对象思想使程序具有高扩展性，从而大大降低重新开发编译器的风险.

编译器，开放性，可扩展性，渐增式，面向对象

0 引 言

随着计算机技术被应用到方方面面，编程思想在不断的进步；同时，计算机语言也在快速的发展着.计算机语言的发展是一个不断演化的过程.其根本的推动力就是抽象机制更高的要求以及对程序设计思想的更好的支持.具体地说，就是把机器能够理解的语言提升到也能够很好地模仿人类思考问题的形式.计算机语言的演化从最开始的机器语言到汇编语言再到各种结构化高级语言，最后到支持面向对象技术的面向对象语言.[1]

随着编译技术的发展，编译器变得越来越复杂.但是，编程语言是在不停的演化与发展的，这给编译器的设计与制作带来了潜在的风险.传统的编译器设计和实现的方法论限制了编程语言的开放性与可扩展性.

新的编译器开发方法的整体思路是，语言的特征是渐增式地添加到一系列编译器中.编译器的每个版本都会更多地关注可扩展性的设计.整个开发过程会完全遵守软件开发的基本法则，面向对象思想在软件开发以及可扩展设计过程中起着关键的作用.我们将整个过程以及由之带来的一系列语言命名为Couplet.Couplet会为C0,C1,C2和C3这一系列语言编写编译器.除了初始语言C0，编写每一个Cn的时候我们都是通过扩展开发它的前一个版本的语言Cn-1(n>1)而来.

1 传统编译器设计与开发现状

语言的演变和编译过程的复杂性以及重要性，需要以一种合适的方式构建编译的过程.一方面使得编译过程能够简单易学，另一方面能够使得编译器可以很好地应对语言的演化.随着编译技术的发展，将编译过程分解为多步，一方面能更好地分析源码，实现编译过程，另一方面也简化了整个编译过程理解的难度和梯度.不过，在应对语言演化方面，一直没有很成形的办法，一般在语言彻底定型后开始制作编译器，语言发生变化时就成了新的语言，最简便的方式便是将当前语言翻译为与其相近的语言，但是，整个过程需要重新开发一个编译器.

编译的发展过程经历了由一步翻译到多步分析的历程.现在计算机界的语言设计以及编译器开发都基于一个5步分析的编译过程：词法分析、语法分析、语义检查和中间代码生成、代码优化、目标代码生成[2].

这个编译过程的特点是，编译器开发开始必须在语言设计完成之后.编译器开发过程每一步的开始都必须在上一步完全完成之后.在整个开发过程中，无法得到有完整功能的编译器，只有开发完全完成的时候，编译器才能第一次试用.这种开发方法需要在语言定义较为固定、无重大变化的前提下,可是却无法面对语言设计上可能出现的改变或功能上的扩充,虽然稳定可靠，却缺乏一定的可扩展性.

2 可扩展语言编译器设计原理

可扩展语言编译器的设计过程中，语言定义将不再一步到位，而是将语言特性逐渐地加入到语言中.每次语言的定义以及编译器的实现过程中，都会考虑语言的进一步扩展，编译器开发也会为进一步扩展预留一定的接口.

把设计过程中定义的语言命名为Couplet，Couplet分为几个版本，分别是C0，C1，C2，C3；并分别定义了每个版本语言的特征，每一个高级版本的语言都是在扩展低级版本的语言特性后得来的.设计过程中为每一个版本的语言编写编译器.除了初始语言C0，编写每一个Cn的时候都是通过扩展开发它的前一个版本的语言Cn-1(n>1)而来.

开发过程中，严格遵守软件开发的基本法则，应用软件工程中的增量模型[3]，进行迭代开发，开发过程通过利用面向对象思想使程序具有高扩展性.

3 可扩展语言及编译器的扩展设计

语言的扩展按照C0，C1，C2……的扩展原则，编译器设计也会为进一步扩展预留一定的接口.

3.1 基本扩展思路

首先从目录结构进行解释.在根目录(trunk)下分设1.0、2.0等分目录依次对应于C1、C2等，然后每个分目录是一个单独的eclipse项目，它们分别都包含src、.settings等文件夹.

以下由C1扩展到C2说明扩展过程.扩展后，2.0目录下的C2项目需要将C1项目生成的.jar包含进Referenced Libraries，然后就可以继承其中的各个类了.C1的代码已经写好，生成的.jar包不再更改，C2在此基础上扩展.

在C1生成.jar包的时侯首先的任务是在C1下增加一组回归测试，找些典型的、覆盖面广的源程序给c1编译，以后一旦更改了C1代码，通过这些测试用例可以基本保证原有的正确性.

在C2中，包结构应该保持类似.couplet顶层包中的类原则上不需要改动，它们约定了最基本的“概念”；也就是说，C2中的couplet包是空的(当然couplet的物理目录中还有子目录).C1为其后Cx“预留”或是“定义”的接口，全部体现在这里.依靠这套接口的封装，理论上应该可以实现整体替换，实际中可能还需根据C2进行调整.

即将建立的couplet.c2包开始出现针对C2的实现，通常的类应当形如代码：

package couplet.c2;

public class Lexer extends couplet.c1.Lexer implements couplet.Lexer {

// ......

}

而其中的方法，有些无需扩展的，继承后自然实现，有些可能需要补充，形如代码：

@Override

public void method(Object parameter) {

super.method(parameter);

// ......}

以上都是最理想的情况，可能不易达到，有些方法需要完全重写，即上述代码中不再调用super的对应方法，而是从头编写.如上过程需要更改c1代码的，自行处理即可，C1中的protected方法应该是重写的主要单元.

诸如scan()、parse()这些实现顶层接口的public方法可被完整重用，因为它们是对整体流程的高层描述，各个Cx本质相同.而各个Cx不同的部分，应该作为protected方法单独抽象出来，不断重写，以实现扩展.这也就意味着，c1中减小public方法的粒度，分割出小的protected方法以便于重用.在设计时明确哪些是该重用的、哪些是该重写的.

把main方法写在couplet.cx.Compiler类中，couplet顶层包的Compiler是一个类.这个类在compile()方法中基于同级别的其他接口构造起主流程；构造方法参数不再留空，而是那些Lexer、Parser、TCGenerator、TCEmitter等接口.[4]这样，下层各个Cx包中的main方法只要将本Cx的各个实现类对象传入Compiler的构造方法，就可以调用compile()方法完成编译，这样就完成了完美抽象.

再下一层目录，像couplet.c1.ast包中，原有的大部分类理论上不需要被继承.这层的“扩展”，更多的不是通过继承，而是通过加入并列的新的类，如新补的token、ast节点等.相应地，这层中那些需要被继承的类，部分可以考虑调到上一层(但不一定，比如有些父ast节点在各Cx中有不同子类，这样的继承就不意味着应上调).

3.2 Couplet顶层接口设置

与其他编译器不同，为了方便扩展，设计过程中设置了顶层的接口.将编译器的一般逻辑设计成通用接口，再在各级语言中实现这个接口.这样，就为重用提供了可能.基本编译器的整体思路都是相同的，包括词法分析、语法分析等.假设语言的扩展中，需要加入新的语法允许的元素，而token并不需要改变，那么设计过程中至少可以重用的内容有顶层的基本逻辑和词法分析器.顶层逻辑是相同的，所以类型的申明不需要改变，需要做的只需要写一个新的入口函数，申请和原来相同的编译器类，但是传参数的时候，只需要传入需要改变的类.比如语法分析器需要改变，那么只需要重新编写语法分析器，并传入到编译器类中.

3.3 扩展中的问题及解决办法

3.3.1 关于数据结构类型的扩展

这里的数据结构指的是存储Token、AST、IC、TC的类.语言扩展后，Token、AST、IC、TC的结构一般也会相应的扩展，新的数据结构直接依据其与原有数据结构类的关系向下继承即可.但是，现在的问题是，为了方便地识别一个数据结构的类型(例如某个AST是IfStatement还是Identifier)，我们之前采用了整型常量作为类型编码，这些常量定义在 C1语言相应数据结构的基类中(如ASTNode)，现在数据结构扩展了，相应的类型编码也要扩展，那么这些新的常量应该定义在哪里？如果C2语言的所有AST 能够有一个基类，那么这些常量可以定义在这个基类中，但是现在不可能；如果各自定义在新的数据结构类本身中，无法通过一种方便、统一的手段访问到.

现在有两种解决方案：第一种方案是根本不使用类型编码.一种观点认为可以不要有类型编码和获得类型的方法，直接使用instance of进行判断.现在看来，在许多情况下，这个getXXXType的方法作用不大(在AST、IC、TC中)，只有个别地方需要根据类型进行不同的操作.但是对于Token来说，这个编码还是发挥了至关重要的作用(在语法分析中经常需要根据下一个Token的类型来选择操作)，更重要的是，Token的类型层次和TokenType的类型编码是不对应的(例如Token的类型层只划分到Punctuation、Keyword等，但是语法分析器要用到的类型是精确到具体哪个标点、哪个关键字来进行判断的).这样，如果一定不使用类型编码的话，要么选择扩展Token的类型层次(例如Punctuation下派生出Semi、Equal、Plus等)，否则语法分析器中的判断代码就会很复杂.不使用类型编码后，原有一些case结构的语句更改为if...else if...的形式，可读性稍有影响，但也不算很大的问题.第二种方案是创建一个单独的类(可以抽象类或者接口)维护类型编码.例如，创建一个ASTType的类，里面只是声明了一组表示AST类型编码的常量，C2中还可以有一个这样的类，继承于C1的ASTType，里面声明新的类型编码常量，这样C2的ASTType可以访问到所有C1、C2的类型编码.但是，维护常量类型编码这种方法本身也是存在一定缺陷的，例如，编码的值需要人工编码，并且一定不能重复，这当存在继承的时候还是有一定不可靠性的(需要回头去看父类的编到几号，然后按顺序继续，可能会出现错误，并且很难查出)，还有另一方法是用一个累加计数器来维护类型编码[5]，但是这相当于把常量变成变量了，这种类型的编码虽然还是有final修饰符，但是不能用在case语句中了.其实本来在这里使用Enum是很理想的，但是可惜Enum不支持继承，无法满足我们扩展的需要.

这两种方案的利弊大抵相当，采用哪种都无妨，虽然有点小瑕疵，但不算很严重的缺陷.

3.3.2 访问者模式的问题

这个问题目前采用思路的具体代码可以这样写：

class B extends A {

@Override

void accept(VisitorA visitor) {

if (visitor instanceof VisitorB) {

accept((VisitorB)visitor);

}

void accept(VisitorB visitor) {

visitor.visit(this);

}

}

这有点类似于适配器模式的思想，相当于需要accept(VisitorA visitor)方法，而实际功能在accept(VisitorB visitor)方法，于是在accept(VisitorA visitor)方法中将其适配到accept(VisitorB visitor).[6]这种方法存在一定的重复性代码，好在C2中新增类型的accept(VisitorA visitor)方法中的内容完全相同，可以通过复制粘贴快速完成(实际上访问者模式的accept方法本身就是完全雷同的).

3.3.3 操作类的扩展

这里的操作类指的是Compiler、Lexer、Parser、ICGenerator、TCGenerator等进行具体操作的类.下面逐个考虑.

Compiler类中的内容其实很简单(不考虑我们用于输出中间结果的main方法)，不论Cx语言，其大体结构是相似的.但是这里涉及一个问题，这些操作类中的成员变量是否都使用顶层接口的类型(例如C1的Compiler中的lexer这个成员的类型是couplet.c1.Lexer这个类型还是couplet.Lexer这个类型).我们认为，应该尽可能地使用顶层接口进行操作(最好能全都使用).但这里又涉及了另一个问题——访问者模式的accept方法，这个方法不适合放在顶层接口中，那么在需要调用accept方法的时候，又要将其强制转换为具体的Cx的某个类，这样在一定程度上降低了抽象性，对于扩展以后的复用也不利(例如C1要转成C1的类，C2要转成C2的类，这种语句在一个方法中一旦出现一次，就可能导致整个方法需要在子类中重写，即使其它部分的内容是完全相同的).总地来说使用顶层接口进行操作还是利大于弊的，使用顶层接口以后，可能只需要在子类的构造方法中实例化不同语言的具体类，其它操作代码可以不改动(当然也有可能改动，比如C1没有类型检查，C2加上了类型检查，这样compile这个方法还是要重写的，但是C2到C3如果没有再增加什么中间步骤的话，comile这个方法就可以复用).

Lexer类的改动也不大，区别主要在于关键字和操作符.关键字只要在子类的静态方法中添加到reserved这个Map中即可(但是使用Map的这种方法是否合适还保留一点疑问，包括后来在Lexer中使用的terminalMap)，操作符的识别需要重写recognizeOperator这个方法.

Parser类主要随产生式的变化而变化.设计的总体思想就是，产生式中一个非终极符对应Parser中的一个方法.这样新增的非终极符对应于一个新增的方法，原有的非终极符如果新增了可推导出的产生式，则原有的方法也要重写(这样可能会重复写一大部分原有的代码，只是新增了一条case而已，但是目前没有更好的解决方案).

ICGenerator类和TCGenerator类这两个类的情况类似，也比较好处理.例如，C2的ICGenerator继承C1的ICGenerator ，实现C2的ASTVisitor，这样实现ASTVisitor中的这些方法即可完成对新的AST的翻译处理，原有的AST的处理如果确有改变，则重写父类的方法.

4 可扩展语言编译器设计的意义

从理论价值看，可扩展语言编译器的设计将软件开发模式引用到编译原理中，希望通过模式的改变进一步优化和改进编程语言的设计思想和编译器的开发流程.传统的编译方式一直局限于瀑布模型，缺乏迭代与反馈，不能很好地适应编程语言的进一步发展与扩充.本设计希望在语言设计以及编译过程中引入增量模型的思想，做以下尝试：在语言设计时考虑进一步扩充的可能和方向，在编译器开发时，为语言的改变和进一步扩充预留接口，并做充分的准备.每一步都为进一步的开发做基础和铺垫.

从实际价值看，随着语言以及编译技术的发展，语言设计更加复杂，编译器的功能也更加强大.然而这快速的发展却带来了一种限制与风险.由于编译器的开发需要在语言完全定义好之后，而且基本应用瀑布模型，无法根据语言定义的扩展而作相应的扩展.一旦语言有扩展或者改变的需要，编译器就可能需要重新开发，上个版本只能提供少量的思想，却不能做到大量的设计和代码上的重用.这样的现象，一方面限制了语言的进一步扩展和发展，另一方面也给编译器的开发带来了一定的风险.通过这次设计，希望可以减少编程语言进一步扩展上的限制，降低编译器在语言扩展后需要重新开发的风险.

[1]李源．计算机语言发展的历史、现状和未来[J]．数码世界，2008(12):20-21．

[2]Alfred V.Aho, Monica S.Lam, Ravi Sethi, Jeffrey D.Ullman.Compilers Principles, Techniques, & Tools.Second Edition.[M]．Addison-Wesley, 2006．

[3]张海藩．软件工程导论[M]．北京：清华大学出版社，1999．

[4]王翔．设计模式——基于C#的工程化实现及扩展[M]．北京：电子工业出版社，2008．

[5]张昱，陈意云.编译原理实验教程[M]．北京：高等教育出版社，2009．

[6]莫勇腾．深入浅出设计模式(C#/Java版)[M]．北京：清华大学出版社，2006．

[责任编辑：王 军]

On the design of extensible language compiler

GE Hansong

(College of Information Technology, Shangqiu Normal University, Shangqiu 476000，China)

The traditional methodology on the design and implementation of compiler imposes restriction on the openness and extensibility of programming language.Compiler is usually made after the complete fix of language, so if the language is extended into a new one, a new complier is needed to develop.In the designing process of the extensible language complier, the language extensibility is taken into consideration, and some connectors are reserved for language extensibility.In development, the basic laws on software designing are strictly followed; the incremental model in software engineering is applied for iterative development, and the design is based on the thought of object-oriented, which can make the program get high extensibility, so as to reduce the risk of compiler redevelopment to the least point.

compiler; openness; extensibility; incremental; object-oriented

2016-09-14

商丘师范学院校级骨干教师项目(2016GGJS14)

葛寒松(1978—)，男，河南虞城人，商丘师范学院讲师，硕士，主要从事编译原理及数据库理论的研究.

TP313

A

1672-3600(2017)06-0053-04