一个诠释编译理论的解释器Tina

房超 杨连贺

摘要：传统的C、C++、Java编译系统大而全，集成了大量的库和框架，足让开发者使用非常方便，却不利于开发者对编译理论与技术的理解。该文针对上述问题，研究了简單的代码编译器的技术构成，开发出了一个具有通用意义的简单编译系统，可使读者更好地学习编译原理和技术并提高对这门课的兴趣。首先，该文对Tina解释器的主要功能和应用进行了概述，并对其执行过程进行了分析和讨论；针对该研究领域的实际情况，提出了Tina解释器的设计方法。 其次，从Tina的代码结构和格式入手，分析了常见的词法、语法问题；研究了编译技术，并对程序的控制结构、判断的解析过程进行详细的分析。编译过程分为词法分析、语法分析以及代码生成和处理三个阶段。以Windows系统为开发平台、以C语言为开发工具，运用递归技术和链表、队列、栈等数据结构对这三个模块进行了具体的设计。

关键词：编译技术；解释器；词法分析；语法分析

中图分类号：TP314 文献标识码：A 文章编号：1009-3044（2018）14-0223-03

Abstract： The traditional C、C ++、Java compiler system are large and integrate a large number of libraries and frameworks， allowing developers to use conveniently， are not conducive to understand the compiler theory and technology. In this paper， aiming at the above problems， we research the a simple structure of code compiler technology， developed a simple compiler system with common sense，making the reader betterly learn compiler theory and technology and increasing the interest of this course. Firstly， the main features and applications what Tina interpreter were discussed， and the analysis and discussion of the implementation process. The actual situation in the field of researching， proposed Tina compiler which is the design method of this solution. Secondly， from code structure and format of Tina， it analyzes the common lexical， grammatical problems. Research on the compiler technology， control structures and procedures， parsing judgment for detailed analysis. Compilation process is divided into lexical analysis， syntax analysis and code generation three processing stages，which let the Windows system as the development platform and let C language as development tools and use recursive technique and the data structure of lists and queue and stacks implementing the three modules of the specific design.

Key words： compiler technology； lexical analysis； lexical analysis； interpreter parsing

1 Tina解释器功能简介

Tina解释器程序完成从源程序的输入、预处理、加载、词法分析、语法分析、语义分析并生成中间逆波兰表达式、用虚拟机执行中间代码、返回结果等一系列过程[1-3]，其中包括对while、for、if、function、var、expression、class、array、return、print、API（系统自带函数）的解释过程。Tina是个很小的脚本语言解释器，支持类的继承和加、减、乘、除、与、或运算，可以输出字符串和经基本运算处理后的结果，并且假设程序员编写的应用程序没有语法错误[4]。Tina是用C语言设计的一款简单脚本语言，其中主要运用了栈、队列、链表、数组等简单数据结构。它实现的功能过于简单，并无商业价值可言，仅仅是让人们对编译理论的实现以及编译技术有一个更好的理解[5]。图1是用Tina写的应用程序，图2是程序的输出结果。

2 Tina解释器的执行过程

程序从解释器的主函数开始，如果未加说明则解释执行本地的test.tina脚本，然后向虚拟机中注册一个函数，输入它在脚本中的名字，以及它的函数指针、参数个数，函数的样式为 void API_FUNC （）。之后建立函数，分三步：第一步，加载；第二步，预处理；第三步，扫描。每一步都有一个独立的C程序模块对Tina脚本进行处理，下面分别介绍之。

（1） 加载。把以.tina为后缀的源文件作为函数输入，通过C语言自带的读文件函数，把读到的所有源文件的字符全部放入缓冲区中，等待下一步的处理。

（2） 预处理。从缓冲区中读出源程序，并且去掉单行注释和块注释。

（3） 扫描。扫描进行三遍，第一遍扫描， 如图3所示，扫描所有的全局函数声明，用token_get（）函数进行词法分析和语法分析[6]，把扫描到的字符放到图4所示的t_k结构体中，并根据扫描到的符号类型，来判断是否为函数符号。如果是，则调用函数定义解析模块进行解析；如果扫描到的是类，则略过类的名字和定义块。第二遍扫描，扫描所有类的定义，发现类的定义并调用类解析模块进行解析。第三遍扫描，发现函数的名字以及定义，并调用函数定义解析模块进行解析。这三遍中用到的解析模块以及进行词法分析的token_get（）函数将在后面介绍[7]。

3 Tina解释器的体系结构

Tina解释器的体系结构从主程序模块main.c开始，这个模块包括五个部分，其中构建模块也包括五个部分，函数解析模块包含七部分：词法分析模块，贯穿整个函数解析模块；中间代码执行模块调用函数解析模块、虚拟机运行模块、API解析模块和变量处理模块；变量处理和表达式解析模块会调用词法分析、变量处理、函数解析模块。

3.1 token_get（）函数

从当前位置（pos）解析一个词法标记，并将词法标记的相关信息存入t_k所指向的TokenInfo对象里，解析之后，当前位置会向后跳跃一个词法标记，我们假设整个待输入的缓存中的词法是无错的（即不存在无效的词法单元）。

首先，刷新t_k的字符串内容，建立临时储存词法标记字符串的数组并且清零。检测是否已经到了文件尾并且删除前导空白符（回车、换行、空格），检查复合运算符（>=，<=，==，！=，+=，-=，*=，/=）、运算符（.，+，-，*，/，>，<，=，（，[）、引用标记（&、]、）、{、}）、分号和逗号，如果遇到数字或字母，则一定是字符或者数字常量，如果是字符，则依次检查是否为关

键字，是否为引用成员运算符，是否为API函数，是否为自定义函数，并把判断的类型存入t_k结构体中。

3.2 function函数解析模块

模块分为两部分：函数声明的解析和函数定义的解析[8]。

函数声明的解析：用token_get（）获取函数名称，为局部变量加入后缀“_M”，防止与全局变量的声明混淆，检查有无重名函数，没有则创建函数。

函数定义的解析：我们已经预扫描过了函数的声明，现在我们直接通过函数的名字获取该函数的结构，并设置该函数为当前扫描函数，解析参数形如（a，b，c），我们把参数当作函数的最外层的几个变量，调用解析变量模块对函数体内的局部变量进行扫描，确定其相对索引，并放在变量列表队列中。

（1） 遇到变量定义、数字、自身引用、布尔值都调用表达式解析模块进行解析；

（2） 如果有返回值，则调用返回值表达式解析；

（3） 遇到左括号，当前层次增加1，遇到右括号当前层次减少1，整段地销毁原先最内层次的变量，括号平衡（值为0）的话则函数定义结束。

（4） while、for、if、print表达式调用相应的解析模块进行解析。

（5） 最后如果是左小括号的话，回退一格，进行表达式求值，如果不是，则提示出现编译错误。

3.3 class类的解析

Class类的解析过程是：获取类的名字；探测是否有继承符号，如果有则获取基类的名字。因为我们以基类的名字创建了一个函数，所以获得的词法标记应该为一个API函数；获取基类成员并添加基类成员。

（1） 如果有函数，首先进行函数定义解析，遇到大括号就跳转，继续监测其访问性与密封性以及类成员变量；

（2） 如果发现了函数定义符号，则调用函数定义解析模块解析，并且检查是否为一个API函数还是一个普通函数，添加到函数列表中，遇到右大括号则退出。

在没有到达文件尾的时候，循环进行以上操作。

3.4 while循环语句的解析

首先略过while的判断表达式的左小括号，保留表达式的位置，稍后再解析。创建第一个跳转节点，并且创建与第一个跳转对应的标记，跳过条件表达式，先解析语句[9]。循环解析，直到文件结束或者跳出循环。

（1） 遇到break或者continue会插入一些节点；

（2） 遇到执行自身的指针、变量定义、布尔值、数字、自定义函数、API函数将调用表达式解析；

（3） 遇到打印操作就调用打印解析模块解析；

（4） 遇到返回表达式就调用返回解析模块解析；

（5） 遇到左括号，当前层次增加1，遇到右括号，当前层次减少1，整段地销毁原先最内层次的变量；

（6） 遇到if、while、for就调用相应的解析模块解析；

3.5 for循环语句的解析

for循环是形如for（exp1； exp2；exp3） {..........}的语句，for循环的解析与while类似，但并不完全相同，其步骤如下：

（1） 創建四个跳转节点并且创建四个与跳转对应的标记，允许for语句的首个表达式出现定义语句，所以要检查有无 var关键字，如果有就用token_get（）跳过；

（2） 解析表达式1，并且保存表达式2和表达式3的位置，留着以后解析，并且略过这两个表达式；

（3） 布尔值、数字、符号、API、自定义函数、变量都用解析表达式模块解析，返回值表达式用解析返回值表达式解析；

（4） 遇到左括号，当前层次增加1，遇到右括号当前层次减少，整段的销毁原先最内层次的变量，如果括号平衡，则跳出循环解析表达式2和表达式3。这里的两个表达式都属于for内层的语句，但是因为是在跳出了for的括号之后才解析的，所以层次变量layer需要增加1；

（5） if、while、for用相应的解析函数解析；

（6） 如果是左小括号的话，回退一格，进行表达式求值，如果不是，则提示出现编译错误。

把解析后的表达式放到中间表达式的节点中，当执行到某个节点是，取当前一个表达式的结果作为返回值，返回给上一层函数。中间表达式是一个五项的结构体。

3.6 if表达式的解析

if表达式的解析过程如下：

（1） 略过if的判断表达式的左小括号，先用解析表达式模块解析if之后的条件表达式；

（2） 创建跳转节点和创建与跳转对应的标记，以便把解析后的中间表达式存放到节点中；

（3） 略过大括号，进入新层次，并开始循环。

（4） 遇到操作符的时候，判断下一个字符，如果是左小括号的话，進行表达式求值，如果不是，则提示出现编译错误。

3.7 print解析函数

该解析函数调用表达式解析函数，即exp-parse（），并且插入中间节点。

4 总结

运用编译原理的知识，本文实现了源程序输入、进入缓冲区、词法分析、语法分析、生成中间表达式、用虚拟机执行并返回中间结果的功能，并对循环语句、返回输出语句、函数、数组、判断语句以及类的继承进行了解析。

第一部分：对Tina解释器的功能进行简单介绍。

第二部分：对解释器执行的过程进行说明，主要包括三步，分别为：加载、预处理、扫描。

第三部分：研究了Tina的代码结构，对Tina完成的功能进行详细的分析，给出每一个功能解析的详细步骤。

参考文献：

[1] 金龙飞，刘磊. 编译器前端构造工具及JLUCC的实现[J]. 吉林大学学报（信息科学版），2005（04）.

[2] 付争方，张海娟. LR语法分析器构造方法初探[J]. 中国科技信息，2005（15）.

[3] Liu Lei， Huang Yi. Achieve bottom-up parsing using recursive descent method[J]. Journal of Jilin University （Information Science Edition），2004 （03） （in Chinese）.

[4] Dou Xun， Wang Ping， Zhou Ming. Recursive descent analysis method in combination query[J]. Microcomputer Development，2004 （06） （in Chinese）.

[5] 宿洁，袁军鹏. 防火墙技术及其进展[J]. 计算机工程与应用，2004（09）.

[6] 陈海明，董韫美. 上下文无关语言分析树的一种表示形式[J]. 计算机研究与发展，2000（10）.

[7] Wang Li， Liu Jian. Parser design and implementation of high-level programming language statements[J]. Silicon Valley，2012 （06） （in Chinese）.

[8] Xiang Wei. Implementation and optimization of micro-compiler[D]. University of Electronic Science and Technology，2007（in Chinese）.

[9] 王心光. 虚拟数控加工通用G代码编译器的研究[D]. 浙江大学， 2005.