2009-11-19

好玩的数学——吉普赛读心术解密

好玩的数学——吉普赛读心术解密

redraiment, 2009-11-19

神奇的吉普赛读心术





  闲着无聊窜寝室,看到一个同学在玩一个 flash 游戏:吉普赛读心术(http://gb.cri.cn/mmsource/flash/2006/04/10/er060410001.swf)。规则如下:
任意选择一个两位数(或者说,从10~99之间任意选择一个数),把这个数的十位与个位相加,再把任意选择的数减去这个和。例如:你选的数是23,然后2+3=5,然后23-5=18
在图表中找出与最后得出的数所相应的图形,并把这个图形牢记心中,然后点击水晶球。你会发现,水晶球所显示出来的图形就是你刚刚心里记下的那个图形。
  咋看之下觉得很神奇,但仔细把玩两三回后你就会发现其中的奥秘:
  1. 右边的图标每次都会改变;
  2. 9、18、27、...、81 这9个图标永远是一样的。
  假设你选择的两位数是 ab(即 ab=a×10+b),其中 1≤a≤9, 0≤b≤9 。按照规则计算就是 (a×10+b)-(a+b)=9×a,结果是 9 的倍数,∵ 1≤a≤9 ∴ 结果为 9、18、27、...、81 中的任意一个。又∵ 这9个图标是一样的,∴ 水晶球神奇地知道你记的图标。

手指计算器

  无独有偶,记的小学数学课上老师教我们用手指计算任意两个5-10之间的数的积。
  例如 6×8 ,一只手伸出 6-5=1 根指头,另一只手伸出 8-5=3 根指头。1+3=4,4 就是积的十位数;把两手弯曲的指头数相乘得 4×2=8,8 是积的个位数。则 6×8=48。
  道理和上面相同:a×b=[(a-5)+(b-5)]×10+(10-a)×(10-b)

神秘的失踪

  做这道题一定要的亲自动手才有滋味!否则就会像浮光掠影,印象不深。
  将一个正方形分割成 7×7=49 的小方格,并按下图将它们分为“甲、乙、丙、丁、戊”五部分。
  然后,甲块不动、乙块和丙块对调、戊块上移、丁块右移。得到新图如下:
  经过这样重新组合拼成的新正方形,中间奇迹般地空出了一个洞!
  实际上这只不过是一个小戏法,上面的新图形并不是真的正方形。
观察原始图可知 △ABC 和 △AED 是相似三角形
∴ DE:CB=AD:AC=4:7
∴ DE=8/7
∴ EF=DE+DF=36/7
∴ 上图中所谓的正方形的另一条边的长度为 36/7+2=50/7≠7
  因此新图形的面积为 7×50÷7=50,而原始图的面积为 7×7=49。因此少了总结红色的一块。上面的图并不精确,精确的图如下:
  从上图可以很去轻易地看出前两行比原始图要高。因此,有时候画精确的图对解题也很有帮助!
  只要你细心观察,还会看到数学中有很多好玩的东西,希望你也能和我分享^_^!


2009-11-08

环境驱动编程

环境驱动编程——参加算法论坛后有感

redraiment, 2009-11-07

现场回顾





  我很荣幸地作为特邀专家入京参加 CSDN 主办的 SD2.0 大会。大会以“移动+嵌入+云”为主题,举办了三天。白天有很多名家讲座,晚上还有5个主题沙龙,我参加的是算法论坛的沙龙。主持人是王尧(左轻侯),曾经先后工作于 Borland 中国公司和微软中国公司,现供职于 IBM 中国开发中心,从事 DB2 的研发工作。与会的还有五位嘉宾:
  1. 王炜:北京南天软件有限公司总架构师;
  2. 宋兴烈:起步软件公司总工程师;
  3. 云风:网易公司技术研发经理;
  4. 贾自艳:腾讯搜索技术研发中心研究员;
  5. 顾森:北大在校学生(http://www.matrix67.com/)。
  论坛围绕“在新一轮技术浪潮中,算法又重新站到了重要位置”这一话题展开讨论。本来有几个问题想和各位嘉宾讨论,但由于时间不足,加上我住处较远,只好忍痛在 21:20 出去赶班车,到家已经 23:40 了。不过收获还是不少,我结合大会上其他专家的一些观点,将其整理出来和大家分享。

算法重获重视

  IT 行业经历了大型机时代、PC 时代、互联网时代,以及即将到来的移动终端+云计算时代。早期由于硬件的先天不足,需要靠软件后天来补;随着硬件的高速发展,一个普通的算法在十八个月以后性能就可以提升一倍,而且大部分经过高度优化的算法都被打包成类库,需要可以方便地调用;但随着互联网时代的到来,用户能够主动参与建设互联网,算法要处理的不再是几台 PC 中存储的数据,而是整个互联网中的信息。
  引用李德毅院士的话:“集中统一的调度,顺序的、确定的输入,不能描述互联网的工作机理和交互机理,互联网突破了图灵机的描述范畴。”李院士将云计算定义为传统的“图灵计算”结合“大众计算”,“大众计算”意味着至少能处理这浩如烟海的互联网信息,因此算法也必须与时俱进。

环境驱动编程

  在讨论中,王玮一直强调要灵活地运用算法,这个我以前提的“工具理论”不谋而合。他现场举了个例子:字符串匹配算法中,Rabin-Karp 算法理论上并非最优的,但在实际运用地比较好。这是由于硬盘的I/O效率远低于内存等高速存储器,并非理想的高效随机存储器。其他匹配算法都需要反复读取前面的数据,而 RK 算法只需按顺序从前往后以此处理,在处理大数据时避免了大量的读取操作,因此在实践中的表现反而比其他理论上更高效的算法要好。如果有一天,硬盘的随机存取速度达到了内存甚至寄存器的水平,那这些原本最优的算法可能又会变得没有优势。
  我在上一篇文章中也提过,真的要深入研究算法,就不可能仅局限于理想状况,必须结合硬件等现实环境。这意味着编程时选用什么算法,受到程序所处环境的制约。比如现在主流操作系统选用“分时机制”而不是“批处理机制”,也是因为受到所处环境需要实时交互的制约,而“分时机制”在频繁调度作业时也需要开销,机器利用率反而比不上“批处理机制”。
  我将这个思想称作“环境驱动编程”,它是“工具理论”在编程实践中的运用。但要真正能做到“环境驱动编程”并不简单,需要我们有很深厚的算法功底,就像在《做到忘记》一文中提到的,要做到无招胜有招,必须先把所有招数融会贯通。讨论中云风也提到:“在将来,把克努特的《计算机程序设计艺术》三卷本读完,可能只是作为程序员的基本素质!”

我的发言

  那天云风在现场提问:对一个长度为 N 的数组实现洗牌算法。作为大学生的我初生牛犊不畏虎,也不怕丢人就举手回答了。当时我的原话是:“用一个 FOR 循环从 N 倒退回 1,每次都随机产生一个 0 到 i 之间的数,对应的元素与第 i 个元素交换。”翻译成 C++ 代码就是:
for ( int i = v.size() - 1; i > 0; i-- ) {
    swap ( v[i], v[rand() % i] );
}
  但几位嘉宾似乎没听清楚,于是我重新组织语言重复了一遍,但好像还是没讲清楚,只好坐下让顾森自己来讲。以前我的队友反映我说话难懂我还不相信,看来真的要去学学口才基础了,呵呵。

我的遐想

  据顾森自己介绍,他最近在研究中文分词技术。他觉得很多人将计算机“神话”了,认为它无所不能,还举了一个例子:想知道今天北京的天气,只需在搜索引擎中输入“北京”、“天气”这两个关键词即可,但很多“脑子不好使的人”(这是原话)就喜欢输入“今天北京气温多少度?”等计算机无法理解的话。他一说完,我随即也听到了一些反对的声音:“你那样才是脑子不好使,人家的做法才算正常。”
  我当时脑海中想起 TAOCP 作者克努特在做 ACM 图灵奖演讲时举的例子:“电影制造厂家在1920年强烈地反对有声电影的引进,因为他们为能够不用声音也可以传递词语这样一种方式感到自豪。”因为较少的设施总能给人带来更多的快乐,我之前也大侃特侃《物尽其(奇)用》,以至于很难割舍那些很有美感的方法。我能理解巧妙运用关键词而快速获得信息的乐趣,因为这是一门艺术,并非所有人都能运用自如。但计算机终究需要是一台可以方便使用的工具。在对艺术有了深入了解后,艺术就慢慢地过渡到科学。关于科学与艺术的讨论可以参看克努特1974年获得图灵奖时的演讲。
  在参加完为期三天的大会后,我一直在思索一个问题:IT 业不断地发展,累计下来的知识越来越丰富,今天进入了移动终端时代,也许明天就迎来量子计算的时代。云风说看完 TAOCP 三卷本也许对很多人来说是玩笑话,但转眼看看现在的大学本科教育,它也非常矛盾:踏踏实实从基础学起,四年时间不够了解冰山一角;讲究实用直接建造空中楼阁,又会缺乏理论基础,很难有突破。如果真有那么一天,花毕生精力也不能全面了解,那这个行业将如何发展?
  我猜测将来会提有一套新的体系来取代现有的图灵模型和冯式计算机。现在用计算机解决问题,都习惯将问题划分成小规模的子问题来解决,这意味着子问题的性质和问题本身相同,有点像化学中的“分子”,麻雀虽小五脏俱全。但现实就像薛定谔的那只猫一样,都是概率问题:个人的运动时无规则的,但组合成一个整体后是有规律的。就像一个人的形态是稳定的,而具体到每个原子的运动又是无规律的。如果未来的计算机也是如此,能够整个这些并发的无规则计算,由量变引起质变,产生有规则的计算结果,那世界又会如何呢?期待一下 ^_^。

总结

  整个大会都很精彩,让我这只一直窝在学校里的井底之蛙开阔了视野。这次是我第一回去北京,住处安排得太远,只好忍痛舍弃第二天的沙龙,非常可惜。希望以后还有机会参加!


2009-11-05

用C语言写解释器(五)

用C语言写解释器(五)——其他一些东西

redraiment, 2009-11-05

写完解释器之后





  这一篇文章我只想和大家侃侃编程语言的事情,不会被放到书中。因此可以天南地北地扯淡,不用像前几篇一样畏首畏尾的了。
  经过前面几篇文章的讨论,已经把用纯 C 语言来实现一个解释器的方法介绍完了。但那些是写给我校 C 语言初学者看的,并不只是你,我得也觉得很不过瘾 ^_^。因此准备继续深入学习编译原理等课程,希望有志同道合的朋友和我一起交流!

富饶的语言(工具)

  在前几篇文章中一直在鼓吹我拍脑袋想出的语言四大要素:“内存管理”、“表达式求值”、“输入/输出”、“按条件跳转”,在这篇文章中您就姑且信一回当它是真的。按照这四条准则去匹配,汇编语言是完全符合的。那为什么又需要 C 语言、Java、C# 等高级语言?这是因为编程除了需要“语言”之外还需要“抽象”!
  “抽象”是个很有效的工具,相信你在为别人介绍自己房间时不会具体到每个木纤维、油漆分子和铁原子。同样的,我们也不乐意总是写一堆 JNZ、JMP 指令,而仅仅是为了实现 if、for、while 等控制结构。C 语言等高级语言提供的抽象的层次更高、表现力更强,允许用更少的语句描述更多的操作。感谢如此富饶的语言为我们带来不同的视角去审视这个世界。
  高级语言相较于低级语言属于更高地抽象层次,高级语言之间的差别主要体现在适用范围上。比如一些语言适合写 WEB 程序,另一些适合做数值分析等。术业有专攻,你只需根据自己的问题来选择一门合适的语言。

什么时候需要创造新的语言

  当我们碰到一类新的问题时,首先考虑的就是定义新的数据结构,并设计多个函数去操作它,最后将它们独立出来打包成一个类库方便在其他地方调用(比如处理图形图像的 OpenGL 库)。上面已经提过,每种语言都有它适合的领域,强行将一门语言用在它不擅长的领域中就出现冗长、繁琐的代码。自然语言也是如此:英语中有种语法叫虚拟语气,描述的是一种假设,并非事实。比如“If I have time, I will go to see you. ”。如果按原意一字不差地翻译相信会很繁琐,我知道台湾作家痞子蔡在使用中文式的虚拟语气很有一套:
如果我还能活一天,
我就要做你的爱侣。
我能活一天吗?可惜。
所以我不是你的爱侣。  ——《第一次亲密接触》
  上面是一段完整表现虚拟语气精髓的话,相信在生活中我们不会这么罗嗦。同样的,如果你发现用现有语言来描述某个特定领域问题时显得力不从心,就可以考虑为这个领域定制一种特定的语言了(Domain Specific Language)!使用现成的词法分析器和语法分析器(比如 lex 和 yacc)对提高开发效率很有帮助,但你也可以考虑采用像 REBOL 这样的语言设计一个“方言”,这会更简单。如果你对 DSL 或 REBOL 有兴趣,可以加入阿里旺旺 REBOL 群(16626148)和蔡学镛前辈交流,他是这方面的专家。

从语言(工具)中挣脱

  从写解释器这件事中可以获得一些建议:不要再争论哪个语言更优秀,只有最适合的;用高级语言写代码首先力求可读性好。第一条建议我在以前讨论“工具理论”时提过很多次,就不再重复,主要交流一下可读性的问题。
  经过了上面冗长的解释和亲自实现解释器以后,大家应该能了解到:一门新语言诞生的动机多数情况下不是为了提高执行效率,而是为了提高开发效率。很多人都沉浸在“++i”比“i++”高效、“10>>1”比“10/2”快等奇技淫巧中,但在你自己实现过解释器后希望能明白,如果真有哪个解释器执行语句“i++;”的效率比“++i;”低,那只能说明这个解释器写得烂!像现代的 C 语言编译器都会有优化的选项,编译时去识别一些常见的热点进行优化,难保那些自以为是的优化反而将代码破坏得连编译器也无法识别。所以要迁就解释器而将代码改得乱七八糟,我宁可换一个更好的解释器!
  真的想深入研究算法,就势必会和硬件相关。你需要精确地知道代码一共执行了多少个时钟周期,而不是简单地根据嵌套了几层 FOR 循环来判断复杂度是 O(n) 还是 O(n2)。除非你深入了解你的解释器,否则无从知晓执行一条 FOR 语句时解释器会不会背着你扫描了整个内存空间。无怪乎经典巨著《计算机程序设计艺术》三卷本中要使用汇编语言来编写代码。

总结

  废话了这么多,我只是想表达“我们是主人”,不要被一个蹩脚的工具牵着鼻子走。当你发现打字员平均打字速度忙时,总不会为了迁就她而只说一些她打得快的字吧?以上内容属于个人观点,切莫认真。欢迎大家通过邮件和我交流你们的想法,我的邮箱地址:redraiment@gmail.com


2009-11-03

用C语言写解释器(四)

用C语言写解释器(四)——语句分析

redraiment, 2009-11-02

语句

  在前面的章节中已经成功实现了内存管理和表达式求值模块。之所以称表达式求值是解释器的核心部分,是因为几乎所有语句的操作都伴随着表达式求值。也许你已经迫不及待地给 eval 传值让它执行复杂的运输了,但目前来讲它充其量只是一个计算器。要想成为一门语言,还需要一套自成体系的语法,包括输入输出语句和控制语句。但在进行语法分析之前,首先需要将 BASIC 源码载入到内存中。

BASIC 源码载入

  在《用C语言写解释器(一)》中附了一段 BASIC 参考代码,每一行的结构是一个行号+一条语句。其中行号为 1-9999 之间的正整数,且当前行号大于前面的行号;语句则由以下即将介绍的 3 条 I/O 语句和 8 条控制语句组成。为方便编码,程序中采用静态数组来保存源代码,读者可以尝试用链表结构实现动态申请的版本。下面是代码结构的定义。
// in basic_io.h
#define PROGRAM_SIZE (10000)

typedef struct {
    int ln;     // line number
    STRING line;
} CODE;

extern CODE code[PROGRAM_SIZE];
extern int cp;
extern int code_size;
  其中 code_size 的作用顾名思义:记录代码的行数。cp (0 ≤ cp < code_size)记录当前行的下标(比如 cp 等于5时表明执行到第5行)。下面是载入 BASIC 源码的参考代码,在载入源码的同时会去除两端的空白字符。
// in basic_io.c
void load_program ( STRING filename )
{
    FILE *fp = fopen ( filename, "r" );
    int bg, ed;

    if ( fp == NULL ) {
        fprintf ( stderr, "文件 %s 无法打开!\n", filename );
        exit ( EXIT_FAILURE );
    }

    while ( fscanf ( fp, "%d", &code[cp].ln ) != EOF ) {
        if ( code[cp].ln <= code[cp-1].ln ) {
            fprintf ( stderr, "Line %d: 标号错误!\n", cp );
            exit ( EXIT_FAILURE );
        }

        fgets ( code[cp].line, sizeof(code[cp].line), fp );
        for ( bg = 0; isspace(code[cp].line[bg]); bg++ );
        ed = (int)strlen ( code[cp].line + bg ) - 1;
        while ( ed >= 0 && isspace ( code[cp].line[ed+bg] ) ) {
            ed--;
        }
        if ( ed >= 0 ) {
            memmove ( code[cp].line, code[cp].line + bg, ed + 1 );
            code[cp].line[ed + 1] = 0;
        } else {
            code[cp].line[0] = 0;
        }

        cp++;
        if ( cp >= PROGRAM_SIZE ) {
            fprintf ( stderr, "程序%s太大,代码空间不足!\n", filename );
            exit ( EXIT_FAILURE );
        }
    }

    code_size = cp;
    cp = 1;
}

语法分析

  源码载入完成后就要开始逐行分析语句了,程序中总共能处理以下 11 种语句:
// in main.c
typedef enum {
    key_input = 0,  // INPUT
    key_print,      // PRINT
    key_for,        // FOR .. TO .. STEP
    key_next,       // NEXT
    key_while,      // WHILE
    key_wend,       // WEND
    key_if,         // IF
    key_else,       // ELSE
    key_endif,      // END IF
    key_goto,       // GOTO
    key_let         // LET
} keywords;
  《用C语言写解释器(一)》中详细描述了每个语句的语法,本程序中所谓的语法其实就是字符串匹配,参考代码如下:
// in main.c
keywords yacc ( const STRING line )
{
    if ( !strnicmp ( line, "INPUT ", 6 ) ) {
        return key_input;
    } else if ( !strnicmp ( line, "PRINT ", 6 ) ) {
        return key_print;
    } else if ( !strnicmp ( line, "FOR ", 4 ) ) {
        return key_for;
    } else if ( !stricmp ( line, "NEXT" ) ) {
        return key_next;
    } else if ( !strnicmp ( line, "WHILE ", 6 ) ) {
        return key_while;
    } else if ( !stricmp ( line, "WEND" ) ) {
        return key_wend;
    } else if ( !strnicmp ( line, "IF ", 3 ) ) {
        return key_if;
    } else if ( !stricmp ( line, "ELSE" ) ) {
        return key_else;
    } else if ( !stricmp ( line, "END IF" ) ) {
        return key_endif;
    } else if ( !strnicmp ( line, "GOTO ", 5 ) ) {
        return key_goto;
    } else if ( !strnicmp ( line, "LET ", 4 ) ) {
        return key_let;
    } else if ( strchr ( line, '=' ) ) {
        return key_let;
    }

    return -1;
}
  每个语句对应有一个执行函数,在分析出是哪种语句后,就可以调用它了!为了编码方便,我们将这些执行函数保存在一个函数指针数组中,请看下面的参考代码:
// in main.c
void (*key_func[])( const STRING ) = {
    exec_input,
    exec_print,
    exec_for,
    exec_next,
    exec_while,
    exec_wend,
    exec_if,
    exec_else,
    exec_endif,
    exec_goto,
    exec_assignment
};

int main ( int argc, char *argv[] )
{
    if ( argc != 2 ) {
        fprintf ( stderr, "usage: %s basic_script_file\n", argv[0] );
        exit ( EXIT_FAILURE );
    }

    load_program ( argv[1] );

    while ( cp < code_size ) {
        (*key_func[yacc ( code[cp].line )]) ( code[cp].line );
        cp++;
    }

    return EXIT_SUCCESS;
}
  以上代码展示的就是整个程序的基础框架,现在欠缺的只是每个语句的执行函数,下面将逐个详细解释。

I/O语句

  输入输出是一个宽泛的概念,并不局限于从键盘输入和显示到屏幕上,还包括操作文件、连接网络、进程通信等。《我们的目标》中指出只需实现从键盘输入(INPUT)和显示到屏幕上(PRINT),事实上还应该包括赋值语句,只不过它属于程序内部的I/O。

INPUT 语句

  INPUT 语句后面跟着一堆变量名(用逗号隔开)。因为变量是弱类型,你可以输入数字或字符串。但C语言是强类型语言,为实现这个功能就需要判断一下 scanf 的返回值。我们执行 scanf ( "%lf", &memory[n].i ),如果你输入的是一个数字,就能成功读取一个浮点数,函数返回 1、否则就返回 0;不能读取时就采用 getchar 来获取字符串!参考代码如下:
// in basic_io.c
void exec_input ( const STRING line )
{
    const char *s = line;
    int n;

    assert ( s != NULL );
    s += 5;

    while ( *s ) {
        while ( *s && isspace(*s) ) {
            s++;
        }
        if ( !isalpha(*s) || isalnum(*(s+1)) ) {
            perror ( "变量名错误!\n" );
            exit ( EXIT_FAILURE );
        } else {
            n = toupper(*s) - 'A';
        }

        if ( !scanf ( "%lf", &memory[n].i ) ) {
            int i;
            // 用户输入的是一个字符串
            memory[n].type = var_string;
            if ( (memory[n].s[0] = getchar()) == '"' ) {
                for ( i = 0; (memory[n].s[i]=getchar())!='"'; i++ );
            } else {
                for ( i = 1; !isspace(memory[n].s[i]=getchar()); i++ );
            }
            memory[n].s[i] = 0;
        } else {
            memory[n].type = var_double;
        }

        do {
            s++;
        } while ( *s && isspace(*s) );
        if ( *s && *s != ',' ) {
            perror ( "INPUT 表达式语法错误!\n" );
            exit ( EXIT_FAILURE );
        } else if ( *s ) {
            s++;
        }
    }
}

PRINT 语句

  输出相对简单些,PRINT 后面跟随的是一堆表达式,表达式只需委托给 eval 来求值即可,因此 PRINT 要做的仅仅是按照值的类型来输出结果。唯一需要小心的就是类似 PRINT "hello, world" 这样字符串中带有逗号的情况,以下是参考代码:
// in basic_io.c
void exec_print ( const STRING line )
{
    STRING l;
    char *s, *e;
    VARIANT v;
    int c = 0;

    strcpy ( l, line );
    s = l;

    assert ( s != NULL );
    s += 5;

    for (;;) {
        for ( e = s; *e && *e != ','; e++ ) {
            // 去除字符串
            if ( *e == '"' ) {
                do {
                    e++;
                } while ( *e && *e != '"' );
            }
        }
        if ( *e ) {
            *e = 0;
        } else {
            e = NULL;
        }

        if ( c++ ) putchar ( '\t' );
        v = eval ( s );
        if ( v.type == var_double ) {
            printf ( "%g", v.i );
        } else if ( v.type == var_string ) {
            printf ( v.s );
        }

        if ( e ) {
            s = e + 1;
        } else {
            putchar ( '\n' );
            break;
        }
    }
}

LET 语句

  在 BASIC 中,“赋值”和“等号”都使用“=”,因此不能像 C 语言中使用 A = B = C 这样连续赋值,在 BASIC 中它的意思是判断 B 和 C 的值是否相等并将结果赋值给 A 。而且关键字 LET 是可选的,即 LET A = 1 和 A = 1 是等价的。剩下的事情那个就很简单了,只要将表达式的值赋给变量即可。以下是参考代码:
// in basic_io.c
void exec_assignment ( const STRING line )
{
    const char *s = line;
    int n;

    if ( !strnicmp ( s, "LET ", 4 ) ) {
        s += 4;
    }
    while ( *s && isspace(*s) ) {
        s++;
    }
    if ( !isalpha(*s) || isalnum(*(s+1)) ) {
        perror ( "变量名错误!\n" );
        exit ( EXIT_FAILURE );
    } else {
        n = toupper(*s) - 'A';
    }

    do {
        s++;
    } while ( *s && isspace(*s) );
    if ( *s != '=' ) {
        fprintf ( stderr, "赋值表达式 %s 语法错误!\n", line );
        exit ( EXIT_FAILURE );
    } else {
        memory[n] = eval ( s + 1 );
    }
}

控制语句

  现在是最后一个模块——控制语句。控制语句并不参与交互,它们的作用只是根据一定的规则来改变代码指针(cp)的值,让程序能到指定的位置去继续执行。限于篇幅,本节只介绍 for、next 以及 goto 三个控制语句的实现方法,读者可以尝试自己完成其他函数,也可以参看附带的完整代码。

FOR 语句

  先来看一下 FOR 语句的结构:
FOR var = expression1 TO expression2 [STEP expression3]
  它首先要计算三个表达式,获得 v1、v2、v3 三个值,然后让变量(var)从 v1 开始,每次迭代都加 v3,直到超出 v2 的范围位置。因此,每一个 FOR 语句,我们都需要保存这四个信息:变量名、起始值、结束值以及步长。另外,不要忘记 FOR 循环等控制语句可以嵌套使用,因此需要开辟一组空间来保存这些信息,参考代码如下:
// in grammar.h
static struct {
    int id;           // memory index
    int ln;           // line number
    double target;    // target value
    double step;
} stack_for[MEMORY_SIZE];
static int top_for = -1;
  分析的过程就是通过 strstr 在语句中搜索“=”、“TO”、“STEP”等字符串,然后将提取的表达式传递给 eval 计算,并将值保存到 stack_for 这个空间中。参考代码如下:
// in grammar.c
void exec_for ( const STRING line )
{
    STRING l;
    char *s, *t;
    int top = top_for + 1;

    if ( strnicmp ( line, "FOR ", 4 ) ) {
        goto errorhandler;
    } else if ( top >= MEMORY_SIZE ) {
        fprintf ( stderr, "FOR 循环嵌套过深!\n" );
        exit ( EXIT_FAILURE );
    }

    strcpy ( l, line );

    s = l + 4;
    while ( *s && isspace(*s) ) s++;
    if ( isalpha(*s) && !isalnum(s[1]) ) {
        stack_for[top].id = toupper(*s) - 'A';
        stack_for[top].ln = cp;
    } else {
        goto errorhandler;
    }

    do {
        s++;
    } while ( *s && isspace(*s) );
    if ( *s == '=' ) {
        s++;
    } else {
        goto errorhandler;
    }

    t = strstr ( s, " TO " );
    if ( t != NULL ) {
        *t = 0;
        memory[stack_for[top].id] = eval ( s );
        s = t + 4;
    } else {
        goto errorhandler;
    }

    t = strstr ( s, " STEP " );
    if ( t != NULL ) {
        *t = 0;
        stack_for[top].target = eval ( s ).i;
        s = t + 5;
        stack_for[top].step = eval ( s ).i;
        if ( fabs ( stack_for[top].step ) < 1E-6 ) {
            goto errorhandler;
        }
    } else {
        stack_for[top].target = eval ( s ).i;
        stack_for[top].step = 1;
    }

    if ( (stack_for[top].step > 0 && 
         memory[stack_for[top].id].i > stack_for[top].target)||
         (stack_for[top].step < 0 && 
         memory[stack_for[top].id].i < stack_for[top].target)) {
        while ( cp < code_size && strcmp(code[cp].line, "NEXT") ) {
            cp++;
        }
        if ( cp >= code_size ) {
            goto errorhandler;
        }
    } else {
        top_for++;
    }

    return;

errorhandler:
    fprintf ( stderr, "Line %d: 语法错误!\n", code[cp].ln );
    exit ( EXIT_FAILURE );
}

NEXT 语句

  NEXT 的工作就简单得多了。它从 stack_for 这个空间中取出最后一组数据,让变量的值累加上步长,并判断循环是否结束。如果结束就跳出循环执行下一条语句;否则就将代码指针移回循环体的顶部,继续执行循环体。下面是参考代码。
// in grammar.c
void exec_next ( const STRING line )
{
    if ( stricmp ( line, "NEXT" ) ) {
        fprintf ( stderr, "Line %d: 语法错误!\n", code[cp].ln );
        exit ( EXIT_FAILURE );
    }
    if ( top_for < 0 ) {
        fprintf ( stderr, "Line %d: NEXT 没有相匹配的 FOR!\n", code[cp].ln );
        exit ( EXIT_FAILURE );
    }

    memory[stack_for[top_for].id].i += stack_for[top_for].step;
    if ( stack_for[top_for].step > 0 && 
         memory[stack_for[top_for].id].i > stack_for[top_for].target ) {
        top_for--;
    } else if ( stack_for[top_for].step < 0 && 
         memory[stack_for[top_for].id].i < stack_for[top_for].target ) {
        top_for--;
    } else {
        cp = stack_for[top_for].ln;
    }
}

GOTO 语句

  也许你认为 GOTO 语句只是简单的将 cp 的值设置为指定的行,但事实上它比想象中的要复杂些。考虑下面的 BASIC 代码:
0010 I = 5
0020 GOTO 40
0030 FOR I = 1 TO 10
0040   PRINT I
0050 NEXT
  像这类代码,直接跳到循环体内部,如果只是简单地将 cp 移动到指定位置,当代码继续执行到 NEXT 时就会报告没有对应的 FOR 循环!跳到其他的控制结构,如 WHILE、IF 等,也会出现相同的问题。以下是参考代码(有删减)。
// in grammar.c
void exec_goto ( const STRING line )
{
    int ln;

    if ( strnicmp ( line, "GOTO ", 5 ) ) {
        fprintf ( stderr, "Line %d: 语法错误!\n", code[cp].ln );
        exit ( EXIT_FAILURE );
    }

    ln = (int)eval ( line + 5 ).i;
    if ( ln > code[cp].ln ) {
        // 往下跳转
        while ( cp < code_size && ln != code[cp].ln ) {
            if ( !strnicmp ( code[cp].line, "IF ", 3 ) ) {
                top_if++;
                stack_if[top_if] = 1;
            } else if ( !stricmp ( code[cp].line, "ELSE" ) ) {
                stack_if[top_if] = 1;
            } else if ( !stricmp ( code[cp].line, "END IF" ) ) {
                top_if--;
            } else if ( !strnicmp ( code[cp].line, "WHILE ", 6 ) ) {
                top_while++;
                stack_while[top_while].isrun = 1;
                stack_while[top_while].ln = cp;
            } else if ( !stricmp ( code[cp].line, "WEND" ) ) {
                top_while--;
            } else if ( !strnicmp ( code[cp].line, "FOR ", 4 ) ) {
                int i = 4;
                VARIANT v;
                while ( isspace(code[cp].line[i]) ) i++;
                v = memory[toupper(code[cp].line[i])-'A'];
                exec_for ( code[cp].line );
                memory[toupper(code[cp].line[i])-'A'] = v;
            } else if ( !stricmp ( code[cp].line, "NEXT" ) ) {
                top_for--;
            }
            cp++;
        }
    } else if ( ln < code[cp].ln ) {
        // 往上跳转
        // 代码类似,此处省略
    } else {
        // 我不希望出现死循环,你可能有其他处理方式
        fprintf ( stderr, "Line %d: 死循环!\n", code[cp].ln );
        exit ( EXIT_FAILURE );
    }

    if ( ln == code[cp].ln ) {
        cp--;
    } else {
        fprintf ( stderr, "标号 %d 不存在!\n", ln );
        exit ( EXIT_FAILURE );
    }
}

总结

  本章介绍了源码载入、语法分析以及部分语句的实现,WHILE 和 IF 等控制语句方法和 FOR、NEXT 类似,有兴趣的读者请尝试自己实现(或者参看附带的完整源码)。这样一个解释器的四个关键部分“内存管理”、“表达式求值”、“输入输出”和“控制语句”就全部介绍完了,希望你也能写出自己的解释器。下一篇我将总结一下我个人对编程语言的一些思考,如果你也有兴趣请继续关注《用C语言写解释器(五)》!

2009-11-01

用C语言写解释器(三)


用C语言写解释器(三)——中缀转后缀



redraiment, 2009-11-01


操作符排序



  如果你忘记了后缀表达式的概念,赶紧翻回上一篇《用C语言写解释器(二)》回顾一下。简单地说,将中缀表达式转换成后缀表达式,就是将操作符的执行顺序由“优先级顺序”转换成“在表达式中的先后顺序”。因此,所谓的中缀转后缀,其实就是给原表达式中的操作符排序。
  比如将中缀表达式 5 * ((10 - 1) / 3) 转换成后缀表达式为 5 10 1 - 3 / *。其中数字 5 10 1 3 仍然按照原先的顺序排列,而操作符的顺序变为 - / ×,这意味着减号最先计算、其次是除号、最后才是乘号。也许你还在担心如何将操作符从两个操作数的中间移到它们的后边。其实不用担心,在完成了排序工作后你就发现它已经跑到操作数的后面了 ^_^。
  从中缀表达式 1+2×3+4 中逐个获取操作符,依次是 + × +。如果当前操作符的优先级不大于前面的操作符时,前面操作符就要先输出。比如例子中的第二个加号,它前面是乘号,因此乘号从这个队伍中跑到输出的队伍中当了“老大”;此时第二个加号再前面的加号比较,仍然没有比它大,因此第一个加号也排到新队伍中去了;最后队伍中只剩下加号自己了,所以它也走了。得到新队伍里的顺序 × + + 就是所求解。下面的表格中详细展示每一个步骤。
序号输入临时空间输出
1+

2×+
3++ ×
4
+ × +
5
+ +×
6
+× +
7

* + +
  相信你心里还是牵挂着那些操作数。很简单,如果碰到的是操作符就按上面的规则处理,如果是操作数就直接输出!下面的表格加上了操作数,将输出完整的后缀表达式。
序号输入临时空间输出
11

2+
1
32+1
4×+1 2
53+ ×1 2
6++ ×1 2 3
7
+ × +1 2 3
8
+ +1 2 3 ×
94+1 2 3 × +
10
+1 2 3 × + 4
11

1 2 3 × + 4 +
  得到最终结果 1 2 3 × + 4 + 就是所求的后缀表达式。下面是程序中的参考代码(有删减)。

操作符优先级

  上一节介绍了中缀转后缀的方法。其中关键的部分就是比较两个操作符的优先级大小。通常情况下这都很简单:比如乘除的优先级比加减大,但括号需要特殊考虑。
  中缀表达式中用括号来提升运算符的优先级,因此左括号正在放入(incoming)临时空间时优先级比任何操作符都大;一旦左括号已经放入(in-stack)空间中,此时它优先级如果还是最大,那无论什么操作符过来它就马上被踢出去,而我们想要的是任何操作符过来都能顺利放入临时空间,因此它放入空间后优先级需要变为最小。这意味着左括号在放入空间前后的优先级是不同的,所以我们需要用两个优先级变量 icp 和 isp 来分别记录操作符在两个状态下的优先级(还记得上一篇的问题吗)。
  另一个是右括号,它本身和优先级无关,它会将临时空间里的操作符一个个输出,直到碰到左括号为止。下面是本程序中中缀转后缀的代码(有删减)。
// in expression.c
PTLIST infix2postfix ()
{
    PTLIST list = NULL, tail, p;
    PTLIST stack = NULL;

    // 初始时在临时空间放一个优先级最低的操作符
    // 这样就不用判断是否为空了,方便编码
    stack = (PTLIST)calloc(1, sizeof(TOKEN_LIST));
    stack->next = NULL;
    stack->token.type = token_operator;
    stack->token.ator = operators[oper_min];

    // before 为全局变量,用于保存之前的操作符
    // 具体作用参看下面的章节
    memset ( &before, 0, sizeof(before) );
    for (;;) {
        p = (PTLIST)calloc(1, sizeof(TOKEN_LIST));
        // calloc 自动初始化
        p->next = NULL;
        p->token = next_token ();
        if ( p->token.type == token_operand ) {
            // 如果是操作数,就不用客气,直接输出
            if ( !list ) {
                list = tail = p;
            } else {
                tail->next = p;
                tail = p;
            }
        } else if ( p->token.type == token_operator) {
            if ( p->token.ator.oper == oper_rparen ) {
                // 右括号
                free ( p );
                while ( stack->token.ator.oper != oper_lparen ) {
                    p = stack;
                    stack = stack->next;
                    tail->next = p;
                    tail = p;
                    tail->next = NULL;
                }
                p = stack;
                stack = stack->next;
                free ( p );
            } else {
                while ( stack->token.ator.isp >= p->token.ator.icp ) {
                    tail->next = stack;
                    stack = stack->next;
                    tail = tail->next;
                    tail->next = NULL;
                }
                p->next = stack;
                stack = p;
            }
        } else {
            free ( p );
            break;
        }
    }
    while ( stack ) {
        p = stack;
        stack = stack->next;
        if ( p->token.ator.oper != oper_min ) {
            p->next = NULL;
            tail->next = p;
            tail = p;
        } else {
            free ( p );
        }
    }

    return list;
}


获取标识符



  在上面的代码中你会看到一个陌生的函数 next_taken() 。它会从中缀表达式中获得一个标记,方法类似从字符串中提取单词(参看课后习题)。在本程序中能识别的标记除了操作符,还有纯数字、字符串、变量名等操作数。唯一要注意的就是操作符和操作数之间可以存在零到多个空格。下面是参考代码(有删减)。
// in expression.c
static TOKEN next_token ()
{
    TOKEN token = {0};
    STRING s;
    int i;

    if ( e == NULL ) {
        return token;
    }

    // 去掉前导空格
    while ( *e && isspace(*e) ) {
        e++;
    }

    if ( *e == 0 ) {
        return token;
    }

    if ( *e == '"' ) {
        // 字符串
        token.type = token_operand;
        token.var.type = var_string;
        e++;
        for ( i = 0; *e && *e != '"'; i++ ) {
            token.var.s[i] = *e;
            e++;
        }
        e++;
    } else if ( isalpha(*e) ) {
        // 如果首字符为字母则有两种情况
        // 1. 变量
        // 2. 逻辑操作符
        token.type = token_operator;
        for ( i = 0; isalnum(*e); i++ ) {
            s[i] = toupper(*e);
            e++;
        }
        s[i] = 0;
        if ( !strcmp ( s, "AND" ) ) {
            token.ator = operators[oper_and];
        } else if ( !strcmp ( s, "OR" ) ) {
            token.ator = operators[oper_or];
        } else if ( !strcmp ( s, "NOT" ) ) {
            token.ator = operators[oper_not];
        } else if ( i == 1 ) {
            token.type = token_operand;
            token.var = memery[s[0]-'A'];
            if ( token.var.type == var_null ) {
                memset ( &token, 0, sizeof(token) );
                fprintf ( stderr, "变量%c未赋值!\n", s[0] );
                exit ( EXIT_FAILURE );
            }
        } else {
            goto errorhandler;
        }
    } else if ( isdigit(*e) || *e == '.' ) {
        // 数字
        token.type = token_operand;
        token.var.type = var_double;
        for ( i = 0; isdigit(*e) || *e == '.'; i++ ) {
            s[i] = *e;
            e++;
        }
        s[i] = 0;
        if ( sscanf ( s, "%lf", &token.var.i ) != 1 ) {
            // 读取数字失败!
            // 错误处理
        }
    } else {
        // 剩下算数运算符和关系运算符
        token.type = token_operator;
        switch (*e) {
        case '(':
            token.ator = operators[oper_lparen];
            break;
        // ...
        // 此处省略其他操作符的代码
        default:
            // 不可识别的操作符
            break;
        }
        e++;
    }
    before = token;

    return token;
}

总结

  本章主要介绍中缀表达式转后缀表达式的方法,并给出了相应的参考代码。和前一篇文章结合起来就完成了解释器中“表达式求值”和“内存管理”两部分,在下一篇文章中我们将介绍语句的解析,其中包含了输入/输出、分支以及循环语句,请关注《用C语言写解释器(四)》。

用C语言写解释器(二)


用C语言写解释器(二)——表达式求值



redraiment, 2009-10-31


内存管理



  既然是表达式求值,自然需要在内存中保存计算结果以及中间值。在《用C语言写解释器(一)》中提过:变量要求是若类型,而 C 语言中的变量是强类型,为实现这个目标就需要定义自己的变量类型,参考代码如下(注释部分指出代码所在的文件名,下同):
// in basic_io.h
#define MEMERY_SIZE (26)

typedef enum {
    var_null = 0,
    var_double,
    var_string
} variant_type;
typedef char STRING[128];
typedef struct {
    variant_type type;
    union {
        double i;
        STRING s;
    };
} VARIANT;

extern VARIANT memery[MEMERY_SIZE];

// in expression.h
typedef VARIANT OPERAND;
  程序自带 A-Z 26个可用变量,初始时都处于未赋值(ver_null)状态。所有变量必须先赋值再使用,否则就会报错!至于赋值语句的实现请参见后面语法分析的章节。

操作符

  表达式中光有数值不行,还需要有操作符。在《》中“表达式运算”一节已经给出了解释器需要实现的所有操作符,包括“算术运算”、“关系运算”和“逻辑运算”。下面给出程序中操作符的定义和声明:
// in expression.h
typedef enum {
    /* 算数运算 */
    oper_lparen = 0,    // 左括号
    oper_rparen,        // 右括号
    oper_plus,          // 加
    oper_minus,         // 减
    oper_multiply,      // 乘
    oper_divide,        // 除
    oper_mod,           // 模
    oper_power,         // 幂
    oper_positive,      // 正号
    oper_negative,      // 负号
    oper_factorial,     // 阶乘
    /* 关系运算 */
    oper_lt,            // 小于
    oper_gt,            // 大于
    oper_eq,            // 等于
    oper_ne,            // 不等于
    oper_le,            // 不大于
    oper_ge,            // 不小于
    /* 逻辑运算 */
    oper_and,           // 且
    oper_or,            // 或
    oper_not,           // 非
    /* 赋值 */
    oper_assignment,    // 赋值
    oper_min            // 栈底
} operator_type;
typedef enum {
    left2right,
    right2left
} associativity;
typedef struct {
    int numbers;        // 操作数
    int icp;            // 优先级
    int isp;            // 优先级
    associativity ass;  // 结合性
    operator_type oper; // 操作符
} OPERATOR;

// in expression.c
static const OPERATOR operators[] = {
    /* 算数运算 */
    {2, 17, 1, left2right, oper_lparen},     // 左括号
    {2, 17, 17, left2right, oper_rparen},    // 右括号
    {2, 12, 12, left2right, oper_plus},      // 加
    {2, 12, 12, left2right, oper_minus},     // 减
    {2, 13, 13, left2right, oper_multiply},  // 乘
    {2, 13, 13, left2right, oper_divide},    // 除
    {2, 13, 13, left2right, oper_mod},       // 模
    {2, 14, 14, left2right, oper_power},     // 幂
    {1, 16, 15, right2left, oper_positive},  // 正号
    {1, 16, 15, right2left, oper_negative},  // 负号
    {1, 16, 15, left2right, oper_factorial}, // 阶乘
    /* 关系运算 */
    {2, 10, 10, left2right, oper_lt},        // 小于
    {2, 10, 10, left2right, oper_gt},        // 大于
    {2, 9, 9, left2right, oper_eq},          // 等于
    {2, 9, 9, left2right, oper_ne},          // 不等于
    {2, 10, 10, left2right, oper_le},        // 不大于
    {2, 10, 10, left2right, oper_ge},        // 不小于
    /* 逻辑运算 */
    {2, 5, 5, left2right, oper_and},         // 且
    {2, 4, 4, left2right, oper_or},          // 或
    {1, 15, 15, right2left, oper_not},       // 非
    /* 赋值 */
    // BASIC 中赋值语句不属于表达式!
    {2, 2, 2, right2left, oper_assignment},  // 赋值
    /* 最小优先级 */
    {2, 0, 0, right2left, oper_min}          // 栈底
};
  你也许会问为什么需要 icp(incoming precedence)、isp(in-stack precedence) 两个优先级,现在不用着急,以后会详细解释!

后缀表达式

  现在操作数(operand)和操作符(operator)都有了,一个表达式就是由它们组合构成的,我们就统称它们为标记(token)。在程序中定义如下:
// in expression.h
typedef enum {
    token_operand = 1,
    token_operator
} token_type;
typedef struct {
    token_type type;
    union {
        OPERAND var;
        OPERATOR ator;
    };
} TOKEN;
typedef struct tlist {
    TOKEN token;
    struct tlist *next;
} TOKEN_LIST, *PTLIST;
  我们平时习惯将表达式符写作:operand operator operand(比如1+1),这是一个递归的定义,表达式本身也可作为操作数。像这种将操作符放在两个操作数之间的表达式称为中缀表达式,中缀表达式的好处是可读性强,操作数之间泾渭分明(尤其是手写体中)。但它有自身的缺陷:操作符的位置说明不了它在运算的先后问题。例如 1+2×3 中,虽然 + 的位置在 × 之前,但这并不表示先做加运算再做乘运算。为解决这个问题,数学中给操作符分了等级,级别高的操作符先计算(乘号的级别比加号高),并用括号提高操作符优先级。因此上例表达式的值是 7 而不是 (1+2)*3=9。
  但对于计算机来说,优先级是一个多余的概念。就像上面提到的,中缀表达式中操作符的顺序没有提供运算先后关系的信息,这就好比用4个字节的空间仅保存1个字节数据——太浪费了!索性将操作符按照运算的先后排序:先计算的排最前面。此时操作符就不适合再放中间了,可以将它移到被操作数的后面:operand operand operator(比如 1 1 +)。上例中 1+2×3 就变化为 1 2 3 × +;(1+2)×3 变化成 1 2 + 3 ×,这种将操作符符放到操作数后面的表达式称为后缀表达式。同理还有将操作符符按照逆序放到操作数的前面的前缀表达式。
  无论是前缀表达式还是后缀表达式,它们的优点都是用操作符的顺序来代替优先级,这样就可以舍弃括号等概念,化繁为简。

后缀表达式求值

  请看下面的梯等式计算,比较中缀表达式和后缀表达式的求值过程。
  8 × ( 2 + 3 )        8 2 3 + ×
= 8 * 5              = 8 5 ×
= 40                 = 40
  后缀表达式的求值方式:从头开始一个标记(token)一个标记地往后扫描,碰到操作数时先放到一个临时的空间里;碰到操作符就从空间里取出最后两个操作数,做相应的运算,然后将结果再次放回空间中。到了最后,空间中就只剩下操作数即运算结果!这个中缀表达式求值类似,只不过中缀表达式操作数取的是前后各一个。下面的代码是程序中后缀表达式求值的节选,其中只包含加法运算,其他运算都是类似的。
// in expression.c
VARIANT eval ( const char expr[] )
{
    // ...
    // 一些变量的定义和声明

    // 将中缀表达式转换成后缀表达式
    // 转换方法将在后续文章中介绍
    list = infix2postfix ();
    while ( list ) {
        // 取出一个 token
        p = list;
        list = list->next;

        // 如果是操作数就保存到 stack 中
        if ( p->token.type == token_operand ) {
            p->next = stack;
            stack = p;
            continue;
        }

        // 如果是操作符...
        switch ( p->token.ator.oper ) {
        // 加法运算
        case oper_plus:
            // 取出 stack 中最末两个操作数
            op2 = stack;
            op1 = stack = stack->next;

            if ( op1->token.var.type == var_double &&
                 op2->token.var.type == var_double ) {
                op1->token.var.i += op2->token.var.i;
            } else {
                // 字符串的加法即合并两个字符串
                // 如果其中一个是数字则需要先转换为字符串
                if ( op1->token.var.type == var_double ) {
                    sprintf ( s1, "%g", op1->token.var.i );
                } else {
                    strcpy ( s1, op1->token.var.s );
                }
                if ( op2->token.var.type == var_double ) {
                    sprintf ( s2, "%g", op2->token.var.i );
                } else {
                    strcpy ( s2, op2->token.var.s );
                }
                op1->token.type = var_string;
                strcat ( s1, s2 );
                strcpy ( op1->token.var.s, s1 );
            }
            free ( op2 );
            break;
        // ...
        // 其他操作符方法类似
        default:
            // 无效操作符处理
            break;
        }
        free ( p );
    }

    value = stack->token.var;
    free ( stack );

    // 最后一个元素即表达式的值
    return value;
}

总结

  这一篇文章主要介绍了表达式中的操作符、操作数在程序内部的表示方法、后缀表达式的相关知识以及后缀表达式求值的方法。在下一篇文章中将着重介绍如何将中缀表达式转换成后缀表达式,请关注《用C语言写解释器(三)》。