用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》中我称呼它为“算术运算”。但对于计算机来说，“算术运算”不仅包含诸如“四则运算”等算术运算，还包括“关系运算”和“逻辑运算”。为了避免歧义，在此就改称它为“表达式运算”。“表达式运算”是整个程序的核心，地位相当于计算机的运算器。在我们的程序中，需要实现以下几种运算符：

符号	名称	优先级	结合性
(	左括号	17	left2right
)	右边	17	left2right
+	加	12	left2right
-	减	12	left2right
*	乘	13	left2right
/	除	13	left2right
%	取模	13	left2right
^	求幂	14	left2right
+	正号	16	right2left
-	负号	16	right2left
!	阶乘	16	left2right
>	大于	10	left2right
<	小于	10	left2right
=	等于	9	left2right
<>	不等于	9	left2right
<=	不大于	10	left2right
>=	不小于	10	left2right
AND	逻辑与	5	left2right
OR	逻辑或	4	left2right
NOT	逻辑非	15	right2left

内存管理

　　在我们这个迷你型的解释器中，可以不用考虑内存空间动态分配的问题，只要实现简单的变量管理。我们默认提供 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

总结

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

AutoHotKey 新手入门教程

AutoHotKey 真是一个好玩的工具！短短几行代码就是先了“窗口置顶”、“窗口透明”等功能，之前我还特意为此装了好几个小工具，现在都可以卸掉了。闲来无事，就把 Quick Start 翻译了一下，我没有逐字逐句地翻译，有时候我嫌原文罗嗦就用自己的话概括地描述了一下。原文地址：http://www.autohotkey.com/docs/Tutorial.htm 教程目录创建脚本启动程序模拟鼠标键盘操纵窗口输入变量与剪切板循环操纵文件其他特性创建脚本每个脚本都是一个纯文本文件，由一些能被 AutoHotKey.exe 执行的命令组成。一个脚本可能还包含热键和热字符串。如果没有热键和热字符串，脚本在启动的时候就会从头依次执行到尾。创建一个新的脚本：下载并安装 AutoHotkey。右击鼠标，选择新建 -> 文本文档。输入文件名并确保以 .ahk 结尾。例如：Test.ahk。右击文件，选择编辑脚本。输入以下内容：#space::Run www.google.com 上一行的第一个字符 "#" 代表键盘上的 Windows 键；所以 #space 表示在按住 Windows 键后再按空格键。"::" 后面的命令会在热键激活后执行，在本例中则会打开谷歌主页。继续按下面步骤操作，来执行这个脚本：保存并关闭该文件。双击该文件来启动它。在系统托盘里会出现一个新图标。按下 Windows 和空格键，网页会在默认的浏览器里打开。右击系统托盘里的绿色图标可以退出或编辑当前脚本。注意：可以同时启动多个脚本，并且在系统托盘里都会有一个相应的图标。每个脚本都能定义多个热键和热字符串。想让某个脚本开机即启动，可以将它的快捷方式放到开始菜单的启动目录里。启动程序命令 Run 可以运行程序、打开文档、网页链接或快捷键。请参看以下示例： Run Notepad Run C:\My Documents\Address List.doc Run C:\My Documents\My Shortcut.lnk Run www.yahoo.com Run mailto:someone@somedoma

阅读全文

贪玩的程序员

搜索此博客