2009-10-18

用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语言写解释器(二)》。

2009-10-04

庆中秋:用Windows XP桌面图标玩贪吃蛇(原理)

庆中秋:用Windows XP桌面图标玩贪吃蛇(原理)

redraiment, 2009-10-04

到处都有好玩的玩意儿





  计算机的世界里离散的:内存从 0 -> 2n 编号;整个屏幕的画面也是由许多颗像素点组成……如果你不介意的话,把脸尽量地贴近显示器(或者电视屏幕),你会看到整个屏幕是由一颗颗显示不同颜色的小颗粒拼成的。如果这样感受还不深,那你还记得小时候玩过的最初型掌上游戏机吗?如下图:
  其中经典的飞机、坦克、俄罗斯方块等都是由一个个正方形的黑色方块拼成的。
  放眼周边的世界,到处都有这样规则排列的、方方正正的“游戏元素”:摩天大楼的窗户、大教堂的座位、从楼上往下看的人群……当然还有今天要介绍的桌面图标!在优库上一搜索就会出现很多结果,有用寝室楼电灯玩贪吃蛇的、也有军训时集体玩 AK47 阵列的等等,原理都是这样~
  在看完这篇文章后,你也可以尝试照样画葫芦,比如开启很多个“记事本”,将他们的窗口调整成四四方方的,然后用它们玩俄罗斯方块。^_^

程序原理

  我在优库上发布了视频——用Windows XP桌面图标玩贪吃蛇(视频地址为 http://v.youku.com/v_show/id_XMTIyODk2Njky.html),一些朋友在评论中猜测程序原理:有人说是用批处理,还有人说是用汇编,甚至有人直接否定说是我用静态帧拼接起来的,呵呵。其实没大家想的这么复杂,我的程序主要是用 VB 开发的(为方便以后使用,移动桌面图标的代码用 C 语言写,并打包成 DLL 文件。程序的核心语句就是下面这句话:
SendMessage ( hwnd, LVM_SETITEMPOSITION, i, MAKELPARAM(x,y) );
  SendMessage 是系统调用,可以向指定的窗口发送消息。整条语句的作用是向桌面发送消息,请求将第“i”个图标移动到坐标“x,y”位置。下面按照视频里播放的顺序依次介绍原理:

一、创建文件

  在视频的最开始,我开启了一个命令提示符执行一条命令。可能正是因为这个原因让大家误以为这个程序是用批处理写的。如果你看了我上次的高清AVI版视频,就知道我命令是:“for /l %d in (1,1,16) do echo. >%d.txt”。正如网友“Sypeace”在评论了说的,这条命令的作用就是在桌面创建十六个文本文档来作为贪吃蛇的身体。只要你不怕麻烦当然可以通过右键新建文本文档然后重命名,这只是我的个人习惯,呵呵。

二、启动游戏

  文件创建好了,我双击桌面那个蛇形的图标,就是本程序“桌面贪吃蛇”启动游戏。这时候桌面只剩下三个图标,有两个在左下角,代表贪吃蛇;另一个随机出现,就是食物;其他图标都被移出屏幕,具体坐标为(0, -100),只有当食物被吃掉后下一个才出现。
  眼尖的朋友可能发现了屏幕的右上角有个白色小框,其实这就是本程序的界面,里面显示了剩余食物的个数。当然这里还包含了另一个秘密,在下一节揭晓!

三、控制方向

  贪吃蛇每隔 200 毫秒前进一格,期间还得接受键盘的方向输入。如果你用 C 语言从零开始实现,这固然可行但很繁琐。在 VB 中不用考虑这么多,把贪吃蛇移动的代码加到一个定时器里即可(这也是我选用 VB 的原因);然后监听窗口 Form 的键盘输入,改变贪吃蛇的前进方向。
  也许你发现了,其实键盘输入应该用系统钩子来捕获更合理,这样即使焦点离开了主程序也依然可用。这正是此程序现在最大的缺点,如果你不小心在运行的时候将鼠标点了一下桌面,焦点离开了主程序,就会发现贪吃蛇不再受控制。这一切都因为1. 我怕麻烦,2. 想快速开发。但也许你可以来帮我完善它!

四、老板来了

  这是个无伤大雅的玩笑。视频播放到最后,你会看到桌面背景变成一个警告:“危险,危险!!老板来了!!”。然后我按键盘上的“Q”退出游戏后背景恢复。刷新一下,图标排列整齐。这样桌面就恢复原样,也许老板不晓得你摆弄桌面图标是在玩游戏^_^

初衷

  最近很流行说“寂寞”,身边的同学也动不动就冒出一句“哥读的不是书,是寂寞”,很烎很囧哈 ^_^。其实,身为光棍的我情感并没大家想的那么丰富,就像我之前在迷你博客里说的“为什么写这些小玩意儿?Because we can~”。

关于源码

  本程序的源码是开发的,欢迎你参与完善。有朋友反映没找到源码,因为我只给了我 Google Sites 的主页地址。是我说的不够详细,这个程序在“天晴”版块,顺便介绍一下“天晴”这个版块放的都是和游戏相关的程序。该程序的链接地址是:http://sites.google.com/site/redraiment/sunshine/snake/。进入后下载 Snake_with_src.zip 这个文件就可以了。


2009-10-01

迎国庆,DuplexPipe 发布 0.3.0 版

迎国庆,DuplexPipe 发布 0.3.0 版

redraiment, 2009-10-01





  今天是中华人民共和国建国六十周年,普天同庆!作为一个程序员,当然是努力工作报效祖国啦~特地抽空完善 DuplexPipe,主要更新如下:
  1. 实现了 UDP 通信模式;
  2. 增加了对多语言的支持,Download 中提供中文版,你还可以通过源码自行编译英文版;
  3. 修正了一些 v0.1.0 中的小错误。
  最新版的源码以及 JAR 包请到项目主页(http://code.google.com/p/duplexpipe/)下载。有了 UDP 模式,现在连接模式一共有以下四种:
  1. TCP 监听模式
  2. TCP 连接模式
  3. UDP 监听模式
  4. UDP 连接模式
  根据两个连接模式排列,可以得到 4×4=16 种模式。由于类似“TCP 监听模式 - TCP 连接模式”和“TCP 连接模式 - TCP 监听模式”等模式属于同一种,排除重复项后总共剩下以下十种模式:
  1. TCP 监听模式 - TCP 监听模式
  2. TCP 监听模式 - TCP 连接模式
  3. TCP 监听模式 - UDP 监听模式
  4. TCP 监听模式 - UDP 连接模式
  5. TCP 连接模式 - TCP 连接模式
  6. TCP 连接模式 - UDP 监听模式
  7. TCP 连接模式 - UDP 连接模式
  8. UDP 监听模式 - UDP 监听模式
  9. UDP 监听模式 - UDP 连接模式
  10. UDP 连接模式 - UDP 连接模式
  到这里还没有结束。我们知道 UDP 属于非安全连接,通讯之前没有经过三次握手确认。因此在“UDP 连接模式端”发送数据包到“UDP 监听模式端”之前,“监听端”并不知道“连接端”的位置,所以也就无法主动给“连接端”发送数据。而我们的 DuplexPipe 只是一个数据转发工具,本身并不向两端程序发送任何多余的信息。因此第十种模式“UDP 连接模式 - UDP 连接模式”并不能正常工作。于是,真正能建立通讯的模式就只剩下前面九种。我暂时想不出解决方法,如果其他朋友知道如何解决(当然不能让 DuplexPipe 主动发送冗余数据),欢迎联系我(redraiment@gmail.com),谢谢!

相关文章