`
NeuronR
  • 浏览: 59794 次
  • 性别: Icon_minigender_1
  • 来自: 武汉
社区版块
存档分类
最新评论

[语义分析]语法树节点波澜再起[编译时值及常数折叠]

 
阅读更多

    上一次构建语法树相关的节点，是在语法分析刚刚开始的时候，这一次又需要对它们动一动手脚，加入一些语义分析需要的成员函数。

    这一次添加的主要是针对AbstractValueNode 及其子类（以后还会讨论关于指令生成相关的函数），现在需要把它变成这个样子

#define memberAbstractValueNode        \
    memberAbstractSyntaxNode           \
    int (*staticInt)(void*, int*);     \
    int (*staticReal)(void*, double*); \
    AcceptType (*typeOf)(void*);
struct AbstractValueNode {
	memberAbstractValueNode
};

增加的函数中，前两个是用来在编译时确定该节点的整数或实数值的。它返回0时，表示可以取得编译时值，而后面的指针参数在返回后，指向的内存将存放该编译时值；否则返回1。在这里，我们认为VariableNode 不可以（即使刚刚赋过常数数值）在编译时确定其值，IntegerNode 及RealNode 可以确定编译时值，而BinaryOperationNode 和UnaryOperationNode 则看其子节点是否都能够确定编译时值。

    那么，对于VariableNode、 IntegerNode和 RealNode ，可以这样实现它们对应的成员函数

// VariableNode 什么都可以

int cantRetrieveStaticInt(void* self, int* value)
{
    return -1;
}

int cantRetrieveStaticReal(void* self, double* value)
{
    return -1;
}

// IntegerNode
int scanIntNode4Int(void* self, int* value)
{
    *value = ((struct IntegerNode*)self)->intValue;
    return 0;
}

int scanIntNode4Real(void* self, double* value)
{
    *value = (double)(((struct IntegerNode*)self)->intValue);
    return 0;
}

// RealNode
int scanRealNode4Int(void* self, int* value)
{
    *value = (int)(((struct RealNode*)self)->realValue);
    return 0;
}

int scanRealNode4Real(void* self, double* value)
{
    *value = ((struct RealNode*)self)->realValue;
    return 0;
}

记得在newXXXNode 系列函数中对这些函数进行绑定。剩下是运算节点，可能还好点，UnaryOperationNode 这样基本上能行：

int scanUnaryOp4Int(void* self, int* value)
{
    struct UnaryOperationNode* node = (struct UnaryOperationNode*)self;
    // 判断子节点
    if (0 != node->operand->staticInt(node->operand, value)) {
        return -1;
    }
    // 运算，PLUS省略
    if (MINUS == node->op) {
        *value = -*value;
    } else if (NOT == node->op) {
        *value = !*value;
    }
    return 0;
}

int scanUnaryOp4Real(void* self, double* value)
{
    struct UnaryOperationNode* node = (struct UnaryOperationNode*)self;
    // 判断子节点
    if (0 != node->operand->staticReal(node->operand, value)) {
        return -1;
    }
    // 运算，PLUS省略
    if (MINUS == node->op) {
        *value = -*value;
    } else if (NOT == node->op) {
        // 报错：实型数不能用来作为条件
    }
    return 0;
}

但是对于BinaryOperationNode ，情况就比较挫了，为每一个运算符准备一个条件分支，这种事情就像看中国足球，看个一场两场还没问题，多了会让人疯掉的。我们得找个好一点的方式。

    不妨先考虑一下这样一个函数指针

int (*intOperation)(int, int);

它计算两个整数（运算符不是其参数），返回它们的结果，如果我们有一堆这样的函数，将它们放在一个映射表里面，那么求BinaryOperationNode的 编译时值就好得多，如

int scanBinaryOp4Int(void* self, int* value)
{
    struct BinaryOperationNode* node = (struct BinaryOperationNode*)self;

    int leftVal, rightVal,
    leftRetrievable = node->leftOperand->staticInt(node->leftOperand,
                                                   &leftVal),
    rightRetrievable = node->rightOperand->staticInt(node->rightOperand,
                                                     &rightVal);
    if (0 == leftRetrievable && 0 == rightRetrievable) {
        // TODO: 在这里插入语句
        // 根据映射表，由 self->op 得到函数指针，调用运算并得到结果
        return 0;
    } else {
        return -1;
    }
}

而组织映射表最简单的方法是──数组。当然，数组就要很小心顺序了，这里我们对着AcceptType 的顺序来编写

typedef enum {
    END, IDENT, ELSE, IF, WHILE, READ, WRITE, BREAK,
    INTEGER_TYPE, REAL_TYPE,
    INTEGER,      REAL,
    PLUS, MINUS, MULTIPLY, DIVIDE, ASSIGN, LT, LE, EQ, NE, GT, GE,
    AND, OR, NOT,
    COMMA, EOS, LPARENT, RPARENT, LBRACKET, RBRACKET, LBRACE, RBRACE,
    SKIP
} AcceptType;
// 增加几个宏
// 测试运算符类型
#define isArithOperator(x) (PLUS <= (x) && (x) < ASSIGN)
#define isCompareOperator(x) (LT <= (x) && (x) <= GE)
#define isLogicOperator(x) (AND <= (x) && (x) <= NOT)
// 因为数组要从0开始，那么我们就用运算符减去这些 偏移量
#define ARITH_OPERATOR_OFFSET (PLUS)
#define COMPARE_OPERATOR_OFFSET (LT)
#define LOGIC_OPERATION_OFFSET (AND)

// 整数运算函数入口地址数组
int (*intOperations[])(int, int) = {
    intPlus, intMinus, intMult, intDiv, NULL,
    intLT, intLE, intEQ, intNE, intGT, intGE,
    logicAnd, logicOr
};

// 实型运算函数入口
// 算术运算
double (*realArith[])(double, double) = {
    realPlus, realMinus, realMult, realDiv
};
// 比较运算，因为比较运算的返回值是整数，所以得与算术运算分开
static int (*realCompare[])(double, double) = {
    realLT, realLE, realEQ, realNE, realGT, realGE
};

// 这些东西的实现很枯燥……见文章最后

那么之前那个代码块中的TODO就可以这样实现了

*value = intOperations[node->op - ARITH_OPERATOR_OFFSET](leftVal, rightVal);

当然，如果这么做，则可以规避显而易见的除0错误

if (DIVIDE == node->op && 0 == rightVal) {
    // 报错：除0错误
} else {
    *value = intOperations[node->op - ARITH_OPERATOR_OFFSET](leftVal, rightVal);
}

不过这还远远没有结束。在编译时确定一个运算节点的常数值，还得考虑到这个节点的类型，比如由

    4 * 2.3

得到的语法树节点，如果要求其编译时整数值，那么不可以取两个子节点的整数值再予以相乘（那样会得到8，而不是期望的9）。因此，在求值之前，得进行类型判断，必要时还得进行类型提升。以BinaryOperationNode 的staticInt 函数实现为例

int scanBinaryOp4Int(void* self, int* value)
{
    struct BinaryOperationNode* node = (struct BinaryOperationNode*)self;
    // 编译时不进行赋值操作
    if (ASSIGN == node->op) {
        return -1;
    }

    // 利用子节点的typeOf函数，求左右子节点的类型，typeOf函数以后再详述，现在假定已经实现
    AcceptType leftType = node->leftOperand->typeOf(node->leftOperand),
               rightType = node->rightOperand->typeOf(node->rightOperand);
    // 左右子节点是否获得求编译时值
    int leftRetrievable, rightRetrievable;

    if (INTEGER == leftType && INTEGER == rightType) {
        // 左右都是整数的情况
        int leftVal, rightVal;
        leftRetrievable = node->leftOperand->staticInt(node->leftOperand,
                                                       &leftVal);
        rightRetrievable = node->rightOperand->staticInt(node->rightOperand,
                                                         &rightVal);
        if (0 == leftRetrievable && 0 == rightRetrievable) {
            if (DIVIDE == node->op && 0 == rightVal) {
                semanticErr(div0Err, node->line);
            } else {
                *value = intOperations[node->op - ARITH_OPERATOR_OFFSET]
                                                  (leftVal, rightVal);
            }
            return 0;
        } else {
            return -1;
        }
    } else {
        // 如果有一边不是整数，那么
        // 首先看是不是逻辑运算，如果是，那么报错
        if (isLogicOperator(node->op)) {
            // 报错：实型不可以作为逻辑值
            return -1;
        }
        double leftVal, rightVal;
        leftRetrievable = node->leftOperand->staticReal(node->leftOperand,
                                                        &leftVal);
        rightRetrievable = node->rightOperand->staticReal(node->rightOperand,
                                                          &rightVal);
        if (0 == leftRetrievable && 0 == rightRetrievable) {
            if (isCompareOperator(node->op)) {
                // 如果是比较运算，那么调用比较运算数组中的对应函数
                *value = realCompare[node->op - COMPARE_OPERATOR_OFFSET]
                                            (leftVal, rightVal);
            } else {
                // 否则调用算术运算数组中的对应函数，并将结果转为整数赋予value指向的地址
                *value = (int)(realArith[node->op - ARITH_OPERATOR_OFFSET]
                                                  (leftVal, rightVal));
            }
            return 0;
        } else {
            return -1;
        }
    }
}

外层判断类型，内层进行运算。这里又提出另一个问题，就是类型如果多了怎么办？（也许需要Mixin）欢迎大家就此问题提出宝贵建议，谢谢。

    获取其实型值基本上照猫画虎就可以了

int scanBinaryOp4Real(void* self, double* value)
{
    struct BinaryOperationNode* node = (struct BinaryOperationNode*)self;
    if (ASSIGN == node->op) {
        return -1;
    }

    AcceptType leftType = node->leftOperand->typeOf(node->leftOperand),
               rightType = node->rightOperand->typeOf(node->rightOperand);
    int leftRetrievable, rightRetrievable;

    if (INTEGER == leftType && INTEGER == rightType) {
        // 都是整数的情况，没什么好说的
        int leftVal, rightVal;
        leftRetrievable = node->leftOperand->staticInt(node->leftOperand,
                                                       &leftVal);
        rightRetrievable = node->rightOperand->staticInt(node->rightOperand,
                                                         &rightVal);
        if (0 == leftRetrievable && 0 == rightRetrievable) {
            *value = (double)(intOperations[node->op - ARITH_OPERATOR_OFFSET]
                                                     (leftVal, rightVal));
            return 0;
        } else {
            return -1;
        }
    } else {
        if (isLogicOperator(node->op)) {
            semanticErr(takeRealAsCondition, node->line);
            return -1;
        }
        double leftVal, rightVal;
        leftRetrievable = node->leftOperand->staticReal(node->leftOperand,
                                                        &leftVal);
        rightRetrievable = node->rightOperand->staticReal(node->rightOperand,
                                                          &rightVal);
        if (0 == leftRetrievable && 0 == rightRetrievable) {
            if (isCompareOperator(node->op)) {
                // 现在是这里转型为实型
                *value = (double)(realCompare
                       [node->op - COMPARE_OPERATOR_OFFSET](leftVal, rightVal));
            } else {
                *value = realArith[node->op - ARITH_OPERATOR_OFFSET]
                                            (leftVal, rightVal);
            }
            return 0;
        } else {
            return -1;
        }
    }
}

附：运算函数实现

static int intPlus(int a, int b)
{
    return a + b;
}

static int intMinus(int a, int b)
{
    return a - b;
}

static int intMult(int a, int b)
{
    return a * b;
}

static int intDiv(int a, int b)
{
    return a / b;
}

static int intLT(int a, int b)
{
    return a < b;
}

static int intLE(int a, int b)
{
    return a <= b;
}

static int intEQ(int a, int b)
{
    return a == b;
}

static int intNE(int a, int b)
{
    return a != b;
}

static int intGT(int a, int b)
{
    return a > b;
}

static int intGE(int a, int b)
{
    return a >= b;
}

static int logicAnd(int a, int b)
{
    return a && b;
}

static int logicOr(int a, int b)
{
    return a || b;
}

static double realPlus(double a, double b)
{
    return a + b;
}

static double realMinus(double a, double b)
{
    return a - b;
}

static double realMult(double a, double b)
{
    return a * b;
}

static double realDiv(double a, double b)
{
    return a / b;
}

static int realLT(double a, double b)
{
    return a < b;
}

static int realLE(double a, double b)
{
    return a <= b;
}

static int realEQ(double a, double b)
{
    return a == b;
}

static int realNE(double a, double b)
{
    return a != b;
}

static int realGT(double a, double b)
{
    return a > b;
}

static int realGE(double a, double b)
{
    return a >= b;
}

判别除0错误也许放在intDiv 里面更好一些……

分享到：
| [符号表]加一层套
评论
2 楼 NeuronR 2009-06-13  
...
1 楼 lwwin 2009-06-13  
奇怪……刚才的发言不见了……

并且刚才并没有 代码框 出现，好奇怪

不过如果代码是COPY的话，还是那个方便，虽然不美观，但是很实用^^
发表评论

您还没有登录,请您登录后再发表评论

相关推荐

    编译原理 语法分析 语法树生成

    压缩包中的“编译原理语法树”文件可能包含了使用yacc和lex构建的C++语法分析器的示例，以及它分析C++源代码后生成的语法树的可视化表示。通过查看这些示例，开发者可以更深入地理解编译器的工作原理，学习如何构建...

    编译原理语法分析语义分析

    编译原理语法分析语义分析 语法分析（Syntax analysis或Parsing）和语法分析程序（Parser） 语法分析是编译过程的一个逻辑阶段。语法分析的任务是在词法分析的基础上将单词序列组合成各类语法短语，如“程序”，...

    编译原理实验报告，词法分析，语法分析，语义分析。

    语法分析阶段，也称作解析，是将词法分析产生的token流按照语言的语法规则进行组织，形成语法树。这个树状结构直观地表示了程序的结构和语法规则。C语言使用上下文无关文法（Context-Free Grammar，CFG）来定义其...

    编译原理词法分析，语法分析，语义分析（源代码和实验报告）

    这个阶段将词法分析产生的标记流转化为抽象语法树（AST），这是一种树形结构，表示了程序的语法结构。语法分析基于上下文无关文法（CFG）进行，通常由递归下降解析器或LR、LL、LALR等解析技术实现。如果源代码的词法...

    编译原理实验报告+语法分析++语义分析++词法分析+详细的源程序

    这份“编译原理实验报告”涵盖了编译器设计中的关键步骤，包括语法分析、语义分析和词法分析，这些都是构建编译器的核心部分。下面将详细解释这些概念及其重要性。 1. **词法分析**：这是编译过程的第一步，也称为...

    实验三_编译原理语义分析_语义分析_sectionnef_

    这可能包括创建一个自定义的词法分析器来识别标识符、关键字和运算符，接着设计一个解析器来构建抽象语法树（AST），最后实现语义分析器来检查和验证AST的语义。 6. **挑战与难点**：在实现语义分析时，常见的挑战...

    编译原理 词法分析-语法分析-语义分析

    ### 编译原理：词法分析-语法分析-语义分析 #### 一、词法分析（Lexical Analysis） 词法分析是编译过程的第一步，它的主要任务是从源程序中识别出一个个有意义的单词符号（Token）。在这个过程中，输入的是源程序...

    语义分析 语法分析 词法分析源代码

    编译原理 实验 课程设计语义分析 语法分析 词法分析源代码极为一体的源文件

    编译原理实验 词法、语法、语义分析

    实验可能涉及编写自定义的词法分析器、语法分析器和语义分析器，这将加深对编译原理的理解，同时提升实际编程技能。 总结，本实验项目“编译原理实验 词法、语法、语义分析”涵盖了编译器设计的核心内容，通过C语言...

    编译原理实验指导书-语义分析1

    《编译原理实验指导书-语义分析1》主要针对的是编译器设计中的一个重要阶段——语义分析。语义分析是编译器工作流程中的关键环节，它在语法分析之后，负责检查程序的语义正确性，确保代码符合语言规范，并生成相应的...

    北邮编译原理语义分析程序

    《编译原理：深入理解语义分析》 在计算机科学领域，编译原理是一门至关重要的课程，它探讨了如何将高级编程语言转化为机器可执行的指令。本资源是北京邮电大学大三学生的课程项目，专注于语义分析这一关键阶段。...

    《编译原理课程设计》-布尔表达式的语法分析及语义分析程序设计

    本课程设计主要涵盖了编译原理中的关键部分——布尔表达式的语法分析与语义分析。在编译原理中，布尔表达式是计算机语言中常见的一种表达形式，它涉及到逻辑运算符（如AND、OR、NOT）以及关系运算符（如==、!=、&lt;、&gt;...

    编译原理 语义分析 实验报告

    【编译原理 语义分析 实验报告】 实验的目的在于深入理解语法制导翻译的原理，这涉及到将解析器在语法分析阶段识别出的语法结构转换为中间代码的过程。语义分析是编译器设计中的关键步骤，它关注的是程序的意义而非...

    编译原理-语义分析器（C语言源码）

    在编译过程中，词法分析器将源代码分解为一个个符号，语法分析器则根据这些符号构造抽象语法树（AST）。当这两步完成后，语义分析器开始工作，它的主要任务包括： 1. **类型检查**：语义分析器会检查变量、常量和...

    编译原理 语法分析、语义分析综合实验

    这个“编译原理 语法分析、语义分析综合实验”涵盖了编译器设计中的两个核心步骤：语法分析和语义分析。通过这个实验，你将有机会深入理解这两者的工作原理，并通过实际操作来巩固理论知识。 语法分析是编译过程的...

    编译原理中用javacc实现MiniC的词法分析、语法分析、语义分析

    用Javacc实现MiniC的词法分析、语法分析、语义分析。在词法分析部分根据单词的构词规则分类，输出&lt;单词种别，单词自身值&gt;二元式；在语法分析部分利用Javacc实现LL(1)文法，判断源语言是否符合MiniC的语法，如果不...

    编译原理语义分析实验报告.doc

    在编译原理语义分析实验报告中，我们可以通过语义分析实验报告，来掌握将语法分析所识别的语法成分变换为中间代码的语义翻译方法。该实验报告的主要目标是通过递归下降语法制导翻译法，对算术表达式、赋值语句进行...

    语义分析器，编译原理课程设计，c++，c

    在实现语义分析器时，通常会定义一套抽象语法树（AST）来表示源代码的结构。AST是对源代码的结构化表示，每个节点代表代码的一个部分，如变量声明、函数调用或算术操作。通过遍历AST，语义分析器可以方便地检查代码...

Magicbox
Global site tag (gtag.js) - Google Analytics