跳至主要内容

用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语言写解释器（四）》。

评论

发表评论

此博客中的热门博文

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就义正言辞地反对：“那怎么可以！己所不欲，勿施于人嘛。” 己所甚欲，勿施于人 易中天老师在《百家讲坛》讲解诸子百家...
发表评论
阅读全文