跳至主要内容

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

评论

发表评论

此博客中的热门博文

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
发表评论
阅读全文

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 共享。
发表评论
阅读全文

Shell中同时读多个文件

Shell中同时读多个文件 redraiment, 2009-08-23 一个文件分割成多个文件 　　有时需要提取文件中的一个或多个列元素生成新的文件，这一操作在 Shell 里很容易实现。比如有一个数据文件 data，有三列信息：姓名、学号、班级。 redraiment 0612800134 0601 christine 0612800136 0601 zb 0612800229 0602 　　现在需要这个文件的第一列和第二列信息分别存到文件 f1 和 f2 中，可以用 awk 提取，也可以用下面这个简单 shell 程序： #!/bin/sh while read f1 f2 f3 do      echo $f1 >> f1      echo $f2 >> f2 done 多个文件合并成一个文件 　　如果想把多个文件重新合并成一个多列文件，而不是追加到文件尾处。例如把上列中生成的 f1 和 f2 重新组成 join.txt 。这时需要同时操作多个文件，就像 C 语言中用 fopen 同时打开多个文件，在 shell 里也是类似的。只是在 shell 里叫做“文件描述符”，用“0-9”十个数字表示。其中 0、1、2 分别是系统的标准输入、输出、错误。“3-9”则由用户只有使用。我们就可以任选两个来重定向输入。脚本如下： #!/bin/sh exec 3< f1 exec 4< f2 while read f1 < & 3 && read f2 < & 4 do      echo $f1 $f2 >> join.txt done
发表评论
阅读全文