跳至主要内容

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

评论

发表评论

此博客中的热门博文

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

OmniGroup

前几天买了OmniGroup全家桶，强迫自己熟悉这些“效率工具”。现记录一些自己的理解。 为什么这些工具的功能看起来有重叠？ 我的理解是每一款应用都是面向特定领域的专业人士的，并不会真的有像我这么“变态”的人一下子买全家桶的。 每款工具各自的作用和区别？ OmniFocus：面向个人的GTD工具，。 OmniPlan：面向小组的项目管理工具。OmniFocus和它的区别：前者管理个人的行动；后者管理一组人的任务。 OmniOutline：它和OmniFocus的功能重叠度很高，但作为区分：Focus更专注于Action，即动词；Outline更专注于清单，即名词。 OmniGraffle：这款应用和其他三款区别最大，它是画图软件。它用起来不像我自己开发的KingYoung那么“流畅”，但的确很漂亮。我为了方便使用，还把积灰已久的鼠标拿出来。 OmniFocus 收件箱：灵光一闪，马上收集 项目：根据项目，纵向地将Action组织到一起。项目的特点是有始有终。例如具体看某一本书 上下文：类似于Spring的AOP概念，从横向/切面上看Action。例如读书，可以贯穿所有读书项目 透视：其实就是搜索功能
发表评论
阅读全文

人所不欲，勿施于人

谁说博客也要像论文一样结构清晰、有条理？！ 软件卸载 昨天整理自己的本本，卸载了 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就义正言辞地反对：“那怎么可以！己所不欲，勿施于人嘛。” 己所甚欲，勿施于人 易中天老师在《百家讲坛》讲解诸子百家...
发表评论
阅读全文