跳至主要内容

用C语言写解释器（一）


用C语言写解释器（一）——我们的目标



redraiment, 2009-10-18


起因



　　最近，我们学院老师联系我，希望我能提供一段用 C 语言编写的 BASIC 解释器，用于 C 语言课程设计教学。我前段时间也正好着迷于“语言”本身，本就有打算写一个解释器，这下正中我下怀，于是欣然接受。


　　以前在图书馆看过梁肇新的《编程高手箴言》，第四章“编程语言的运行机理”中就包含了一段 C 语言编写的 BASIC 解释器代码，但代码好像并不完整（我翻了好几遍，都没发现函数 get_token 的实现代码）；再者，这次的代码还有其他用处，不宜牵涉版权问题；最后的原因是我有“想自己编码”的冲动 ^_^。综上所述，我要从零开始用 C 语言来编写一个 BASIC 解释器。


前置知识



　　1. 要编写解释器，首先就要明白什么是解释器（详细的解释请参看维基百科：http://zh.wikipedia.org/zh-cn/解释器）。盗用《编程高手箴言》里的话：解释程序就是一个字符串的解释器（P165 解释语言的原理）。所以，如果仅仅是为我个人编写的话，我宁可会借助 lex & yacc 甚至 perl，而不会纯粹用 C 语言来写。


　　2. 在起因中已经提过，这个程序会在学弟学妹们学完 C 语言后作为综合实验。因此需要你熟悉 C 语言的语法、单链表添加/删除节点等操作以及栈的概念（这些内容大部分都能在 C 语言的教材中找到），一些相对冷僻的技术（例如 setjmp/longjmp）则不会出现在程序中。


关于语言



　　我在《编程和语言之我见》一文中提过，编程是一个很宽泛的概念。从某种意义上来说所有的软件都是一种特定的语言，但根据程序本身的灵活性可以分为“硬编码”、“可配置”、“可控制”和“可编程”四类（详见《四类程序》）。如果一个程序的灵活性达到了“可编程”，它的配置文件就可以被看作一种“编程语言”，而该程序本身也就是一个“解释器”。


　　要做到“可编程”，程序至少应该具备“输入/输出”、“表达式运算”、“内存管理”和“按条件跳转”四个功能（详见《用DOS批处理来做数字图像处理》）。这正好对应了冯·诺依曼计算机的结构：以运算器和控制器为中心，输入/输出设备与存储器之间的数据传输都要经过运算器。下面详细介绍各个部分。


我们的目标



　　我们要编写解释器，自然也逃不出上面的条条例例。语法就参考 BASIC，但因为是设计我们自己的语言，当然可以根据个人兴趣进行“添油加醋”（比如表达式里提供神往已久的阶乘运算 ^_^）。下面是一段 BASIC 的示例代码（example.bas）：
0009 N = 0
0010 WHILE N < 1 OR N > 20
0011   PRINT "请输入一个1-20之间的数"
0012   INPUT N
0013 WEND
0020 FOR I = 1 TO N
0030   L = "*"
0040   FOR J = 1 TO N - I
0050     L = " " + L
0060   NEXT
0070   FOR J = 2 TO 2 * I - 1 STEP 2
0080     L = L + "**"
0090   NEXT
0100   PRINT L
0110 NEXT
0120 I = N - 1
0130 L = ""
0140 FOR J = 1 TO N - I
0150   L = L + " "
0160 NEXT
0170 FOR J = 1 TO ((2*I) - 1)
0180   L = L + "*"
0190 NEXT
0200 PRINT L
0210 I = I - 1
0220 IF I > 0 THEN
0230   GOTO 130
0240 ELSE
0250   PRINT "By redraiment"
0260 END IF
　　BASIC 语法要求行首提供一个 1->9999 之间的数字作为该行的行号（当前行的行号不小于上一行的行号），供 GOTO 语句跳转时调用。BASIC 的语法比 C 严格，这不仅可以降低代码的复杂性还使语言本身更易学。上面的代码差不多涵盖了我们需要实现的所有功能，如果能被正确解析，你将看到下面的运行效果：
　　下面来依次讨论要实现的功能。


输入/输出（IO）



　　通过输入/输出来和外部程序或人交互，这是脱离“硬编码”的最基本要求。输入/输出也是很抽象的概念，它并不局限于标准输入输出端（键盘、显示器等），也可以通过文件、互联网等方式获得数据（因此 C 语言中除了 scanf、printf 等，其实 #include 指令也算是一种 IO 操作）。我们这个程序并不强调 IO，因此只要求实现 INPUT 和 PRINT 两条指令，分别用于从键盘输入数据和打印到屏幕。指令的格式如下：


INPUT var[, var ...]
其中 var 代表变量名(下同)，变量之间用逗号隔开。
作用：从键盘获得一个或多个值，并赋值到相应的变量。同时输入多个变量时，输入的每个数之间用空格、回车或制表符隔开。
例如：INPUT A, B, C

PRINT expression[, expression ...]
其中 expression 为表达式（下同），表达式之间用逗号隔开。
作用：对表达式求值，将结果输出到屏幕并换行。如果有多个表达式，表达式之间用制表符（\t）隔开。
例如：PRINT I * 3 + 1, (A + B)*(C + D)


表达式运算



　　在《DOS》中我称呼它为“算术运算”。但对于计算机来说，“算术运算”不仅包含诸如“四则运算”等算术运算，还包括“关系运算”和“逻辑运算”。为了避免歧义，在此就改称它为“表达式运算”。“表达式运算”是整个程序的核心，地位相当于计算机的运算器。在我们的程序中，需要实现以下几种运算符：
符号名称优先级结合性
(左括号17left2right
)右边17left2right
+加12left2right
-减12left2right
*乘13left2right
/除13left2right
%取模13left2right
^求幂14left2right
+正号16right2left
-负号16right2left
!阶乘16left2right
>大于10left2right
<小于10left2right
=等于9left2right
<>不等于9left2right
<=不大于10left2right
>=不小于10left2right
AND逻辑与5left2right
OR逻辑或4left2right
NOT逻辑非15right2left


内存管理



　　在我们这个迷你型的解释器中，可以不用考虑内存空间动态分配的问题，只要实现简单的变量管理。我们默认提供 A-Z 26个可用的弱类型变量（可以随意赋值为整数、浮点数或字符串）。变量要求先赋值才能使用，否则就会提示变量不可用（因此示例代码中第一行就是给 N 赋值为 0）。赋值语句的格式为
[LET] var = expression
其中 LET 是可选的关键字。BASIC 中不允许出现 var1 = var2 = expression 这样的赋值语句，因为在表达式中“=”被翻译为“等于”，所以赋值符合没有出现在上面的表格中。
作用：计算表达式的值，并将结果赋值给变量 var。
例如：I = (123 + 456) * 0.09


按条件跳转



　　如果设计一门最简洁的语言，那它的控制语句就只需提供像汇编中的 JMP、JNZ 等根据条件跳转的语句即可，通过它们的组合即可模拟出 IF、WHILE、FOR、GOTO 等控制语句。但 BASIC 作为一门高级语言，需要提供更高层、更抽象的语句。我们将会实现以下四条语句：
1)
GOTO expression
　　其中 expression 是一个数值表达式，计算结果必须为可用的行号。因为它是一个表达式，通过动态计算就能模拟子程序调用。
　　作用：无条件跳转到指定行。
　　例如：GOTO 120+10
2)
IF expression THEN
  sentence1
[ELSE
  sentence2]
END IF
　　其中 sentence 是语句块（下同），包含一条或多条可执行语句。ELSE 为可选部分。
　　作用：分支结构。但表达式值为真（数字不等于0或者字符串不为空）时执行语句块1；否则，有 ELSE 语句块时执行 ELSE 语句块。
　　例如：
        IF 1=1 THEN
           PRINT "TRUE"
        ELSE
           PRINT "FALSE"
        END IF
3)
FOR var = expression TO expression [STEP expression]
  sentence
NEXT
　　所有表达式均为数值表达式。STEP 为可选部分，为迭代器的步长。步长表达式的值不允许为 0。
　　作用：循环迭代结构
　　例如：
        FOR I = 1 TO 10 STEP 3
          PRINT I
        NEXT
4)
WHILE expression
  sentence
WEND
　　作用：迭代执行语句块，直到表达式的值为假。
　　例如：
        WHILE N < 10
          N = N + 1
        WEND


更多细节


    1. BASIC 的源代码不区分大小写；
    2. 本程序在实现中没有处理字符转义，因此无法无法输出双引号。在介绍完所有源码后，如果你有兴趣可以尝试自行完善；
    3. 本程序同样没有考虑注释（REM 关键字）。其实这很简单，但这个问题同样留给你来处理 ^_^；
    4. 也许你也会有兴趣添加 GOSUB 和 RETURN 关键字，让子程序功能从 GOTO 中解放出来。

总结

　　这一篇主要介绍了我们编写的解释器要实现的功能，接下来会有一系列文章来逐步详细介绍解释器的实现。在下一篇中会首先介绍解释器的核心部分——表达式求值。请关注《用C语言写解释器（二）》。

评论

发表评论

此博客中的热门博文

JavaScript中的字符串乘法

JavaScript中的字符串乘法 redraiment, Date 原文 原文地址： http://www.davidflanagan.com/2009/08/string-multipli.html 原作者：David Flanagan In Ruby, the "*" operator used with a string on the left and a number on the right does string repetition. "Ruby"*2 evaluates to "RubyRuby", for example. This is only occasionally useful (when creating lines of hyphens for ASCII tables, for example) but it seems kind of neat. And it sure beats having to write a loop and concatenate n copies of a string one at a time--that just seems really inefficient. I just realized that there is a clever way to implement string multiplication in JavaScript: String.prototype.times = function(n) {     return Array.prototype.join.call({length:n+1}, this); }; "js".times(5) // => "jsjsjsjsjs" This method takes advantage of the behavior of the  Array.join()  method for arrays that have undefined elements. But it doesn't even bother creating an array with n+1 undefined ele...
发表评论
阅读全文

DAO层测试

<dependency> <groupId>com.wix</groupId> <artifactId>wix-embedded-mysql</artifactId> <version>2.1.4</version> <scope>test</scope> </dependency> 利用 wix-embedded-mysql 把MySQL嵌入到进程中，作为内存型的MySQL来做单元测试。 脚本： resources/migrations/mysql/<database>/<timestamp>_<action>.sql 但多个项目需要共享数据库脚本，可能可以用 git submodule 共享。
发表评论
阅读全文

人所不欲，勿施于人

谁说博客也要像论文一样结构清晰、有条理？！ 软件卸载 昨天整理自己的本本，卸载了 VMware 7.0 + 深度XP，MS Office 2007 以及 Visual Basic 6.0。我承认这些都是盗版软件，不过剩下的应用程序都是自由软件（freeware）或免费软件（freeware），这下我的计算机“干净”了。闲来无事，我就细数了一下当初装这些软件的原因： VMware + XP：当初刚买本本的时候，正好在上软件工程实践，紧遵老师的教导“将自己的开发环境随身携带”，自然第一款软件就是装了虚拟机（学校机房里是肆无忌惮地用盗版 VMware），另外上课指定使用 Visio 作图，那也只好一起装了；当然，也有部分原因是因为某些人的计算机装的是 XP，我这边有个 XP 环境也是为了方便问题重现（我的本本预装了 Vista）。 MS Office 2007：在毕设期间，我也还是用 Open Office 和 WPS 2010，但现在公司用的却是 Office 2007（正版）。我这次卸载这款办公软件其实也是在提醒自己：工作的事情要在工作时间里完成！ VB 6：你可能无法想象在我们科班的毕业设计中有多少是 VB6 项目，从大二开始，每逢毕业将至，总会有人来找我帮忙看那些不晓得从哪儿搜罗来的 VB6 代码，经不住软磨硬泡，我总会帮着改改；另一个原因在我自己，我一直下不了决心去学 MFC 等，所以但凡要做 GUI 程序，我都是拿 VB6 来画界面，再调用由 C 语言开发的 DLL 库，不过现在改用 QT，于是 VB6 可以功成身退了。 己所不欲，勿施于人 有些人就喜欢把自己的事全盘交托给别人来做，我一直不明白他们既然有精力去说服别人，为什么就没耐心自己去完成（所以我下面说人和人之间是无法理解的）。既然自己都认为这是无聊的事情，为什么偏偏又假设其他人会愿意无偿地帮你来完成呢？ 两千多年前，孔老夫子提出“己所不欲，勿施于人”的观点，但到了今天，我听到关于这句话时的语境普遍是，A说：“那个XX东西你也不要了（或要了也没用），不如就让给我吧？”，B就义正言辞地反对：“那怎么可以！己所不欲，勿施于人嘛。” 己所甚欲，勿施于人 易中天老师在《百家讲坛》讲解诸子百家...
发表评论
阅读全文