跳至主要内容

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

评论

发表评论

此博客中的热门博文

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