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

[语法分析]算符优先分析的实现及独立测试

CC++C#数据结构 
阅读更多

    好了，现在来尝试把那些该未实现的注释给实现掉了。当然有两个地方在上一节中本应该实现，它们是代码块1中的

// 将一个左括号压入栈顶
// 实现为
opana->opStack->push(opana->opStack,
                         newOperator(LPARENT, 0x7fffffff, nullOperate));

 和代码块3中的

self->opStack->push(self->opStack,
                            newOperator(token->type,
                                        /* 未实现：对应的优先级数 */ -1,
                                        unaryOperate));
// 后来加入了优先数表，所以这里可以实现为
self->opStack->push(self->opStack,
                            newOperator(token->type,
                                        PRIORITY[token->type],
                                        unaryOperate));

// 将 MINUS 或 PLUS 作为一元运算符入栈
// 实现为
self->opStack->push(self->opStack,
                            newOperator(token->type, 0, unaryOperate));

// 正括号入栈
// 实现为
self->opStack->push(self->opStack, newOperator(token->type,
                                                       PRIORITY[token->type],
                                                       nullOperate));

 

    接下来，先为测试OperationAnalyser做准备，再将那些功能逐个实现。看起来这似乎不容易，不同的语法分析器之间耦合度较紧。不过这个问题可以这样解决：

struct FakeDefaultAnalyser {
    memberSyntaxAnalyser
};

struct FakeVariableAnalyser {
    memberSyntaxAnalyser
};

struct SyntaxAnalyser* newFakeDefaultAnalyser(void);
struct SyntaxAnalyser* newVariableAnalyser(void); // fake one.

void FakeDefaultAnalyser_ConsumeNT(void*, struct AbstractSyntaxNode*);
void FakeDefaultAnalyser_ConsumeT(void*, struct Token*);
void FakeVariableAnalyser_ConsumeT(void*, struct Token*);

    这些数据结构以及其对应的成员函数并不需要复杂的设计，即可帮助我们完成测试工作。首先，对于FakeVariableAnalyser，因为测试的目的在于检查OperationAnalyser在遇到标识符时会不会跳转到分析变量的分析器中，所以这个数据结构可以很简单地实现——我们可以假定它一旦读入一个标识符，就把这个标识符打包变成一个VariableNode然后返回给OperationAnalyser——而它的consumeNonTerminal函数甚至根本没必要实现；对应地，测试数据也没有必要太复杂，所以与之相关的函数可以这样实现：

struct SyntaxAnalyser* newVariableAnalyser(void)
{
    struct SyntaxAnalyser* varAna = (struct SyntaxAnalyser*)
                                  allocate(sizeof(struct FakeVariableAnalyser));
    varAna->consumeToken = FakeVariableAnalyser_ConsumeT;
    varAna->consumeNonTerminal = NULL;
    return varAna;
}

void FakeVariableAnalyser_ConsumeT(void* self, struct Token* tkn)
{
    if(IDENT != tkn->type) {
        fprintf(treeout, "incorrect token passed to variable analyser.\n");
        fprintf(treeout, "    token image:   %s\n", tkn->image);
        exit(1);
    }
    revert(analyserStack->pop(analyserStack));
    struct SyntaxAnalyser* analyser = (struct SyntaxAnalyser*)
                                      (analyserStack->peek(analyserStack));
    analyser->consumeNonTerminal(analyser, (struct AbstractSyntaxNode*)
                                                   newVariableNode(tkn->image));
}

而那个FakeDefaultAnalyser，则是常驻分析器栈栈底的默认分析器。考虑到当OperationAnalyser将自己弹出分析器栈并返回时会有两个动作：将得到的算术节点扔给FakeDefaultAnalyser的consumeNonTerminal函数、将最后一个传入的符号扔给FakeDefaultAnalyser的consumeToken函数，所以这两个成员函数都得实现。参考实现如下：

struct SyntaxAnalyser* newFakeDefaultAnalyser(void)
{
    struct SyntaxAnalyser* defAna = (struct SyntaxAnalyser*)
                                  allocate(sizeof(struct FakeDefaultAnalyser));
    defAna->consumeToken = FakeDefaultAnalyser_ConsumeT;
    defAna->consumeNonTerminal = FakeDefaultAnalyser_ConsumeNT;
    return defAna;
}

void FakeDefaultAnalyser_ConsumeNT(void* self, struct AbstractSyntaxNode* node)
{
    fprintf(treeout, "\noperation returned.\n");
    if(NULL == node) {
        fprintf(treeout, "NULL returned.\n");
    } else {
        node->printree(node, 1);
        node->delNode(node);
    }
}

void FakeDefaultAnalyser_ConsumeT(void* self, struct Token* t)
{
    if(NULL == t->image) {
        printf("Token passed:  %2d / NULL image\n", t->type);
    } else {
        printf("Token passed:  %2d / %s\n", t->type, t->image);
    }
}

将节点信息输出到由treeout指向的日志文件中。

    数据结构有了，现在准备将词法分析模块包含进来以便测试。词法分析需要的接口函数可以这样弄：

struct Stack* analyserStack; // 分析器栈指针

char buffer[64];
struct Token token = {
    0, SKIP, NULL, buffer
}; // 存放词法分析得到的符号

// 下面变量将用来提供测试数据，在nextChar中会用到
char* testcase[];
int testsuit_nr = 0;
int ch_index = 0;

int nextChar(void)
{
    int ch = (int)testcase[testsuit_nr][ch_index++];
    if(0 == ch) {
        ch = -1;
        ch_index = 0;
        ++testsuit_nr;
    }
    return ch;
}

struct Token* firstToken(void)
{
    printf("Test case %2d\n", testsuit_nr);

    analyserStack->push(analyserStack, newOperationAnalyser());
    // 新建一个OperationAnalyser压到栈顶准备测试

    return &token;
}

struct Token* nextToken(void)
{
    if(SKIP != token.type) {
        struct SyntaxAnalyser* analyser = (struct SyntaxAnalyser*)
                                          (analyserStack->peek(analyserStack));
        analyser->consumeToken(analyser, &token);
    }
    return &token;
}

void eofToken(void)
{
    nextToken();
    struct SyntaxAnalyser* analyser = (struct SyntaxAnalyser*)
                                      (analyserStack->peek(analyserStack));
    struct Token endToken = {0, END, NULL, NULL};
    analyser->consumeToken(analyser, &endToken);
}

void error(int line, ErrMsg err)
{
    fprintf(stderr, "Line %d Error: %s\n", line, err);
}

最后弄个测试驱动器，一个main函数。你可以把这一大串都放到一个.c文件中，独立编译执行。

#include<stdio.h>

/* 引入COOL的MAD来调试内存泄漏 */
/* 请将COOL整个目录放在JerryCompiler所在的目录下 */
#ifndef _DEBUG_MODE
#define _DEBUG_MODE
#endif /* _DEBUG_MODE */
#include"COOL/MemoryAllocationDebugger.h"

#include"datastruct.h"
#include"syntax-node.h"
#include"syntax-analyser.h"
#include"dfa.h"
#include"dfa.c"

FILE* treeout; // 用以输出节点信息日志

// 变量和函数声明放这里，以免main中报错

int main()
{
    treeout = fopen("testout", "w"); // 这个文件随便你用什么名字
    analyserStack = newStack();
    // 分析器栈底常驻一个默认分析器，专门用来输出结果
    analyserStack->push(analyserStack, newFakeDefaultAnalyser());

    // testcase数组最后一项应该手动置为NULL
    while(NULL != testcase[testsuit_nr]) {
        tokenize();
//        showAlloc;
/* 如果最后的内存泄漏查看发现有没被释放的堆空间，那么取消这一块注释，以便查看每一轮测试中的未释放空间 */
    }

    printf("Test done.\n");
    revert(analyserStack->pop(analyserStack));
    analyserStack->finalize(analyserStack);
    showAlloc; // 查看内存泄漏
    fclose(treeout);
    return 0;
}

测试数据参考：

char* testcase[] = {
    "1+2 + 5 /6;", // 普通运算
    "(1 + 2*(2.4+5))", // 括号
    "-(0 == ((!5) < (9)) && 14 >= 100 - -3)", // 各种逻辑运算、负号
    "!4 == 7 || 4 == 8 && 4 <= 0 || 1 != 2",
    "i * s + d / k;", // 变量跳转
    "a = b = c", // 赋值运算的右结合

    ";", // 空语句

    "1+!s)", // 多余的右括号
    "1+k!)", // 不正确的表达式
    "1+)",
    "1+!",
    "(1+ m* 5", // 多余的左括号
    NULL
};

 

    在最后实现OperationAnalyser模块之前，为了避免整个项目中“名称用完”的情况发生，这里把一些成员函数的名字作特定包装，以免与其它函数不慎重名而导致莫名其妙的编译错误：

// 各个函数的名字用wrapname这个宏来处理一次
#define wrapname(name) name ## _OperationAnalyser
// 原 consumeToken_OpAna
static void wrapname(consumeToken)(void*, struct Token*);
// 原 consumeNonTerminal_OpAna
static void wrapname(consumeNonTerminal)(void*, struct AbstractSyntaxNode*);
// 原 consumeFactor
static void wrapname(consumeFactor)(struct OperationAnalyser*, struct Token*);
// 原 consumeOperator
static void wrapname(consumeOperator)(struct OperationAnalyser*, struct Token*);

此外还引入一个函数，它将在当前OperationAnalyser完成任务（无论成功或失败）时将它弹出分析器栈，释放它所占据的全部空间：

static void wrapname(cleanup)(struct OperationAnalyser* self)
{
    while(0 != self->opStack->getSize(self->opStack)) {
        revert(self->opStack->pop(self->opStack));
    }
    self->opStack->finalize(self->opStack);

    struct AbstractValueNode* node;
    while(0 != self->numStack->getSize(self->numStack)) {
        node = (struct AbstractValueNode*)(self->numStack->pop(self->numStack));
        node->delNode(node);
    }
    self->numStack->finalize(self->numStack);

    analyserStack->pop(analyserStack);

    revert(self);
}

    现在开始各个击破。先来弄遇到标识符跳转的那块分支，将一个VariableAnalyser加入栈顶并让它去分析：

    if(IDENT == token->type) {
        struct SyntaxAnalyser* analyser = newVariableAnalyser();
        analyserStack->push(analyserStack, analyser);
        analyser->consumeToken(analyser, token);
    }

紧接着是这一块代码中最后那个分支。其实这里也不一定是错误，比如刚才构造的测试数据中，如果直接读入分号，或者由于某种原因，OperationAnalyser得到的是一个空的运算，就不是一个错误。不过，假如得到的是空运算的话，那么当前OperationAnalyser的数栈和符号栈应该都处于刚刚初始化的状态，因此

    else {
        struct AbstractSyntaxNode* ret = (struct AbstractSyntaxNode*)
                                         (self->numStack->pop(self->numStack));
        if(NULL != ret || 1 != self->opStack->getSize(self->opStack)) {
            // 栈内容已经改变，出错
            printf("ERR #0\n"); // TODO
        }
        wrapname(cleanup)(self);
        struct SyntaxAnalyser* analyser = (struct SyntaxAnalyser*)
                                         (analyserStack->peek(analyserStack));
        analyser->consumeNonTerminal(analyser, ret);

        analyser = (struct SyntaxAnalyser*)
                                         (analyserStack->peek(analyserStack));
        analyser->consumeToken(analyser, token);
    }

这里错误处理并没有完结，语法分析的错误处理方式将放到以后去弄。

    最后两个是wrapname(consumeOperator)中最后两个分支中未实现的部分。其中当前符号为反括号的那一分支（条件为RPARENT == token->type）中，当反括号多1导致常驻栈底的那个正括号被配对的情况中（条件为0 == self->opStack->getSize(self->opStack)，右方还标出“注2”的那句），其实并不需要报错，而完全可以把这个多出来的反括号扔给下一个语法分析器去做：

        if(0 == self->opStack->getSize(self->opStack)) {
            struct AbstractSyntaxNode* ret = (struct AbstractSyntaxNode*)
                                          (self->numStack->pop(self->numStack));
            wrapname(cleanup)(self);
            struct SyntaxAnalyser* analyser = (struct SyntaxAnalyser*)
                                         (analyserStack->peek(analyserStack));
            analyser->consumeNonTerminal(analyser, ret);

            analyser = (struct SyntaxAnalyser*)
                                         (analyserStack->peek(analyserStack));
            analyser->consumeToken(analyser, token); // 多的反括号传递过去~
            return;
        }

而最后注释有终止的那一句，其实跟这个也差不多，先把代码贴出来：

    else {
        struct AbstractSyntaxNode* ret;
        struct Operator* topOp = (struct Operator*)
                                         (self->opStack->pop(self->opStack));
        while(LPARENT != topOp->op) {
            topOp->operate(topOp, self->numStack);
            topOp = (struct Operator*)(self->opStack->pop(self->opStack));
        }
        topOp->operate(topOp, NULL);
        ret = (struct AbstractSyntaxNode*)(self->numStack->pop(self->numStack));
        if(0 != self->opStack->getSize(self->opStack)) {
            printf("ERR #1\n"); // TODO
        }
        wrapname(cleanup)(self);
        struct SyntaxAnalyser* analyser = (struct SyntaxAnalyser*)
                                         (analyserStack->peek(analyserStack));
        analyser->consumeNonTerminal(analyser, ret);

        analyser = (struct SyntaxAnalyser*)
                   (analyserStack->peek(analyserStack));
        analyser->consumeToken(analyser, token);
    }

前面直到while循环是不断弹出操作符栈栈顶进行运算；后面那句

topOp->operate(topOp, NULL);

看起来很莫名其妙？想想这时topOp是什么。它必然是一个左括号，因此它进行运算仅仅是释放它自己的内存空间（不直接写成释放空间的原因是，考虑到代码的封装性，我们应该假设自己不知道这些Operator是怎么来的，只知道它们应该都被运算掉）；另外，加入输入是正确的，那么这个左括号应该是常驻栈顶的正括号，而它是被pop出来的，这也就意味着这样一来符号栈就应该是空的了，如果这是符号栈里面还有东西（if(0 != self->opStack->getSize(self->opStack))），那就意味着左括号数量多了，因此出错。

 

    现在就可以开始测试了。测试的结果有一些会从标准输出打印出来，如那些“ERR #”之类的信息，而语法树信息则会输出到treeout指向的文件中。Enjoy~

 

语法树信息的格式

    输出到文件里面的信息看起来不是那么友好。也许注意一下它们的缩进会有所帮助，如

    1 + 2 + 5 / 6

对应的输出为

 

operation returned.

   binary operation - operator : + ~~ left operand:

      binary operation - operator : + ~~ left operand:

         integer 1

      **  right operand:

         integer 2

   **  right operand:

      binary operation - operator : / ~~ left operand:

         integer 5

      **  right operand:

         integer 6

第一行“operation returned.”是在FakeDefaultAnalyser_ConsumeNT中输出的，而后面的那一串都是在printBinaryOperation中输出的。注意到第2行和第6行缩进相同，这表示它们是一个节点的两个部分。第2行之后缩进增加的那些部分是该BinaryOperationNode节点的leftOperand所指向的子树，而第6行之后那些部分则是其rightOperand指向的子树。所以这表示出来的是这样一棵树：

   +

  / \

 +   /  <---这个斜杠是除号

/ \ / \

1 2 5 6

此外还有UnaryOperationNode，它的形式如

unary operation - operator : %运算符% ~~ operand:

    运算数节点信息

 

See also:

    indent printBinaryOperationNode printUnaryOperationNode 函数，syntax-node.c 文件

附调试信息输出被注释掉的完整的代码：

/* syntax-analyser.h */
#ifndef _SYNTAX_ANALYSER_H
#define _SYNTAX_ANALYSER_H

#include"datastruct.h"

struct OperationAnalyser* newOperationAnalyser(void);

/* 暂时将.c文件用.h文件来包含，而不是用makefile */
#include"operation-analyser.c"

#endif /* _SYNTAX_ANALYSER_H */
/* operation-analyser.c */
#include<stdlib.h>
#include"datastruct.h"
#include"syntax-analyser.h"
#include"syntax-node.h"

#ifndef _DEBUG_MODE
#define _DEBUG_MODE
#endif /* _DEBUG_MODE */

#include"COOL/MemoryAllocationDebugger.h"
#include"COOL/Collection/Stack/Stack.h"

extern struct Stack* analyserStack;
extern struct SyntaxAnalyser* newVariableAnalyser(void);

struct Operator {
    void (*operate)(struct Operator*, struct Stack*);
    AcceptType op;
    int priority;
    int rightCombination;
};

static const int RIGHT_COMB[] = {
    0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0,
    0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0,
    0, 0, 0,
    0, 0, 1
};

static struct Operator* newOperator(AcceptType op, int priority,
                              void (*operate)(struct Operator*, struct Stack*));
static void nullOperate(struct Operator*, struct Stack*);
static void unaryOperate(struct Operator*, struct Stack*);
static void binaryOperate(struct Operator*, struct Stack*);

static struct Operator* newOperator(AcceptType op, int priority,
                               void (*operate)(struct Operator*, struct Stack*))
{
    struct Operator* oper = (struct Operator*)allocate(sizeof(struct Operator));
    oper->op = op;
    oper->priority = priority;
    oper->rightCombination = RIGHT_COMB[op];
    oper->operate = operate;
    return oper;
}

static void nullOperate(struct Operator* oper, struct Stack* numStack)
{
    revert(oper);
}

static void unaryOperate(struct Operator* oper, struct Stack* numStack)
{
    struct AbstractValueNode* value;
    value = (struct AbstractValueNode*)(numStack->pop(numStack));
    numStack->push(numStack, newUnaryOperationNode(oper->op, value));
    revert(oper);
}

static void binaryOperate(struct Operator* oper, struct Stack* numStack)
{
    struct AbstractValueNode* left,* right;
    right = (struct AbstractValueNode*)(numStack->pop(numStack));
    left = (struct AbstractValueNode*)(numStack->pop(numStack));
    numStack->push(numStack, newBinaryOperationNode(oper->op, left, right));
    revert(oper);
}

#define wrapname(name) name ## _OperationAnalyser
static void wrapname(consumeToken)(void*, struct Token*);
static void wrapname(consumeNonTerminal)(void*, struct AbstractSyntaxNode*);
static void wrapname(consumeFactor)(struct OperationAnalyser*, struct Token*);
static void wrapname(consumeOperator)(struct OperationAnalyser*, struct Token*);
static void wrapname(cleanup)(struct OperationAnalyser*);

static const int PRIORITY[] = {
    0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0,
    2, 2, 1, 1, 5, 3, 3, 3, 3, 3, 3,
    5, 6, 4,
    0, 0, 0x7fffffff, 0, 0, 0, 0, 0
};

static void (*OPER_FUNCS[])(struct Operator*, struct Stack*) = {
    NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
    NULL, NULL, NULL, NULL,
    binaryOperate, binaryOperate, binaryOperate, binaryOperate, binaryOperate,
                binaryOperate, binaryOperate, binaryOperate,
                binaryOperate, binaryOperate, binaryOperate,
    binaryOperate, binaryOperate, unaryOperate
};

struct OperationAnalyser* newOperationAnalyser(void)
{
    struct OperationAnalyser* opana = (struct OperationAnalyser*)
                                     allocate(sizeof(struct OperationAnalyser));
    opana->needFactor = 1;
    opana->numStack = newStack();
    opana->opStack = newStack();
    opana->opStack->push(opana->opStack,
                         newOperator(LPARENT, 0x7fffffff, nullOperate));
    opana->consumeToken = wrapname(consumeToken);
    opana->consumeNonTerminal = wrapname(consumeNonTerminal);
    return opana;
}

static void wrapname(consumeToken)(void* self, struct Token* token)
{
    struct OperationAnalyser* opana = (struct OperationAnalyser*)self;
    if(opana->needFactor) {
//        printf("... Passing Factor ... %s\n", token->image);
        wrapname(consumeFactor)(opana, token);
    } else {
//        printf("... Passing Operator ... %s\n", token->image);
        wrapname(consumeOperator)(opana, token);
    }
}

static void wrapname(consumeFactor)(struct OperationAnalyser* self,
                                    struct Token* token)
{
    if(NOT == token->type) {
        self->opStack->push(self->opStack,
                            newOperator(token->type,
                                        PRIORITY[token->type],
                                        unaryOperate));
        self->needFactor = 1;
    } else if(MINUS == token->type || PLUS == token->type) {
        self->opStack->push(self->opStack,
                            newOperator(token->type, 0, unaryOperate));
        self->needFactor = 1;
    } else if(IDENT == token->type) {
        struct SyntaxAnalyser* analyser = newVariableAnalyser();
        analyserStack->push(analyserStack, analyser);
        analyser->consumeToken(analyser, token);
    } else if(INTEGER == token->type) {
        self->numStack->push(self->numStack,
                             newIntegerNode(atoi(token->image)));
        self->needFactor = 0;
    } else if(REAL == token->type) {
        self->numStack->push(self->numStack, newRealNode(atof(token->image)));
        self->needFactor = 0;
    } else if(LPARENT == token->type) {
        self->opStack->push(self->opStack, newOperator(token->type,
                                                       0x7fffffff,
                                                       nullOperate));
        self->needFactor = 1;
    } else {
        struct AbstractSyntaxNode* ret = (struct AbstractSyntaxNode*)
                                         (self->numStack->pop(self->numStack));
        if(NULL != ret || 1 != self->opStack->getSize(self->opStack)) {
            printf("ERR #0\n");
        }
        wrapname(cleanup)(self);
        struct SyntaxAnalyser* analyser = (struct SyntaxAnalyser*)
                                         (analyserStack->peek(analyserStack));
        analyser->consumeNonTerminal(analyser, ret);

        analyser = (struct SyntaxAnalyser*)
                                         (analyserStack->peek(analyserStack));
        analyser->consumeToken(analyser, token);
    }
}

static void wrapname(consumeOperator)(struct OperationAnalyser* self,
                                      struct Token* token)
{
    int priority = PRIORITY[token->type];
    if(0 < priority && priority < PRIORITY[LPARENT]) {
        int push = 0;
        struct Operator* topOp = (struct Operator*)
                                         (self->opStack->peek(self->opStack));
        push |= (priority < topOp->priority);
        push |= (priority == topOp->priority && topOp->rightCombination);
        while(!push) {
//            printf("Operating ... %s\n", OPERATORS[topOp->op]);
            topOp = (struct Operator*)(self->opStack->pop(self->opStack));
            topOp->operate(topOp, self->numStack);
            topOp = (struct Operator*)(self->opStack->peek(self->opStack));
            push |= (priority < topOp->priority);
            push |= (priority == topOp->priority && topOp->rightCombination);
        }
        self->opStack->push(self->opStack, newOperator(token->type,
                                                  priority,
                                                  OPER_FUNCS[token->type]));
        self->needFactor = 1;
    } else if(RPARENT == token->type) {
        struct Operator* topOp = (struct Operator*)
                                         (self->opStack->pop(self->opStack));
        while(nullOperate != topOp->operate) {
//            printf("Operating ... %s\n", OPERATORS[topOp->op]);
            topOp->operate(topOp, self->numStack);
            topOp = (struct Operator*)(self->opStack->pop(self->opStack));
        }
        topOp->operate(topOp, self->numStack);
        self->needFactor = 0;
        if(0 == self->opStack->getSize(self->opStack)) {
            struct AbstractSyntaxNode* ret = (struct AbstractSyntaxNode*)
                                          (self->numStack->pop(self->numStack));
            wrapname(cleanup)(self);
            struct SyntaxAnalyser* analyser = (struct SyntaxAnalyser*)
                                         (analyserStack->peek(analyserStack));
            analyser->consumeNonTerminal(analyser, ret);

            analyser = (struct SyntaxAnalyser*)
                                         (analyserStack->peek(analyserStack));
            analyser->consumeToken(analyser, token);
            return;
        }
    } else {
        struct AbstractSyntaxNode* ret;
        struct Operator* topOp = (struct Operator*)
                                         (self->opStack->pop(self->opStack));
        while(LPARENT != topOp->op) {
            topOp->operate(topOp, self->numStack);
            topOp = (struct Operator*)(self->opStack->pop(self->opStack));
        }
        topOp->operate(topOp, NULL);
        ret = (struct AbstractSyntaxNode*)(self->numStack->pop(self->numStack));
        if(0 != self->opStack->getSize(self->opStack)) {
            printf("ERR #1\n");
        }
        wrapname(cleanup)(self);
        struct SyntaxAnalyser* analyser = (struct SyntaxAnalyser*)
                                         (analyserStack->peek(analyserStack));
        analyser->consumeNonTerminal(analyser, ret);

        analyser = (struct SyntaxAnalyser*)
                   (analyserStack->peek(analyserStack));
        analyser->consumeToken(analyser, token);
    }
}

static void wrapname(consumeNonTerminal)(void* self,
                                         struct AbstractSyntaxNode* node)
{
    struct OperationAnalyser* opana = (struct OperationAnalyser*)self;
    opana->numStack->push(opana->numStack, node);
    opana->needFactor = 0;
}

static void wrapname(cleanup)(struct OperationAnalyser* self)
{
    while(0 != self->opStack->getSize(self->opStack)) {
        revert(self->opStack->pop(self->opStack));
    }
    self->opStack->finalize(self->opStack);

    struct AbstractValueNode* node;
    while(0 != self->numStack->getSize(self->numStack)) {
        node = (struct AbstractValueNode*)(self->numStack->pop(self->numStack));
        node->delNode(node);
    }
    self->numStack->finalize(self->numStack);

    analyserStack->pop(analyserStack);

    revert(self);
}
#undef wrapname
/* test-op-ana.c */
#include<stdio.h>

#ifndef _DEBUG_MODE
#define _DEBUG_MODE
#endif /* _DEBUG_MODE */
#include"COOL/MemoryAllocationDebugger.h"

#include"datastruct.h"
#include"syntax-node.h"
#include"syntax-analyser.h"
#include"dfa.h"
#include"dfa.c"

FILE* treeout;

struct FakeDefaultAnalyser {
    memberSyntaxAnalyser
};

struct FakeVariableAnalyser {
    memberSyntaxAnalyser
};

struct SyntaxAnalyser* newFakeDefaultAnalyser(void);
struct SyntaxAnalyser* newVariableAnalyser(void); // fake one.

void FakeDefaultAnalyser_ConsumeNT(void*, struct AbstractSyntaxNode*);
void FakeDefaultAnalyser_ConsumeT(void*, struct Token*);
void FakeVariableAnalyser_ConsumeT(void*, struct Token*);

struct Stack* analyserStack;
int testsuit_nr = 0;
int ch_index = 0;
char buffer[64];
struct Token token = {
    0, SKIP, NULL, buffer
};

char* testcase[] = {
    "1+2 + 5 /6;", // 普通运算
    "(1 + 2*(2.4+5))", // 括号
    "-(0 == ((!5) < (9)) && 14 >= 100 - -3)", // 各种逻辑运算、负号
    "!4 == 7 || 4 == 8 && 4 <= 0 || 1 != 2",
    "i * s + d / k;", // 变量跳转
    "a = b = c", // 赋值运算的右结合

    ";", // 空语句

    "1+!s)", // 多余的右括号
    "1+k!)", // 不正确的表达式
    "1+)",
    "1+!",
    "(1+ m* 5", // 多余的左括号
    NULL
};

int main()
{
    treeout = fopen("testout", "w");
    analyserStack = newStack();
    analyserStack->push(analyserStack, newFakeDefaultAnalyser());

    while(NULL != testcase[testsuit_nr]) {
        tokenize();
//        showAlloc;
    }

    printf("Test done.\n");
    revert(analyserStack->pop(analyserStack));
    analyserStack->finalize(analyserStack);
    showAlloc;
    fclose(treeout);
    return 0;
}

struct SyntaxAnalyser* newFakeDefaultAnalyser(void)
{
    struct SyntaxAnalyser* defAna = (struct SyntaxAnalyser*)
                                  allocate(sizeof(struct FakeDefaultAnalyser));
    defAna->consumeToken = FakeDefaultAnalyser_ConsumeT;
    defAna->consumeNonTerminal = FakeDefaultAnalyser_ConsumeNT;
    return defAna;
}

struct SyntaxAnalyser* newVariableAnalyser(void)
{
    struct SyntaxAnalyser* varAna = (struct SyntaxAnalyser*)
                                  allocate(sizeof(struct FakeVariableAnalyser));
    varAna->consumeToken = FakeVariableAnalyser_ConsumeT;
    varAna->consumeNonTerminal = NULL;
    return varAna;
}

void FakeDefaultAnalyser_ConsumeNT(void* self, struct AbstractSyntaxNode* node)
{
    fprintf(treeout, "\noperation returned.\n");
    if(NULL == node) {
        fprintf(treeout, "NULL returned.\n");
    } else {
        node->printree(node, 1);
        node->delNode(node);
    }
}

void FakeVariableAnalyser_ConsumeT(void* self, struct Token* tkn)
{
    if(IDENT != tkn->type) {
        fprintf(treeout, "incorrect token passed to variable analyser.\n");
        fprintf(treeout, "    token image:   %s\n", tkn->image);
        exit(1);
    }
    revert(analyserStack->pop(analyserStack));
    struct SyntaxAnalyser* analyser = (struct SyntaxAnalyser*)
                                      (analyserStack->peek(analyserStack));
    analyser->consumeNonTerminal(analyser, (struct AbstractSyntaxNode*)
                                                   newVariableNode(tkn->image));
}

void FakeDefaultAnalyser_ConsumeT(void* self, struct Token* t)
{
    if(NULL == t->image) {
        printf("Token passed:  %2d / NULL image\n", t->type);
    } else {
        printf("Token passed:  %2d / %s\n", t->type, t->image);
    }
}

int nextChar(void)
{
    int ch = (int)testcase[testsuit_nr][ch_index++];
    if(0 == ch) {
        ch = -1;
        ch_index = 0;
        ++testsuit_nr;
    }
    return ch;
}

struct Token* firstToken(void)
{
    printf("Test case %2d\n", testsuit_nr);
    analyserStack->push(analyserStack, newOperationAnalyser());
    return &token;
}

struct Token* nextToken(void)
{
    if(SKIP != token.type) {
        struct SyntaxAnalyser* analyser = (struct SyntaxAnalyser*)
                                          (analyserStack->peek(analyserStack));
        analyser->consumeToken(analyser, &token);
    }
    return &token;
}

void eofToken(void)
{
    nextToken();
    struct SyntaxAnalyser* analyser = (struct SyntaxAnalyser*)
                                      (analyserStack->peek(analyserStack));
    struct Token endToken = {0, END, NULL, NULL};
    analyser->consumeToken(analyser, &endToken);
}

 

分享到：
| [语法分析]无需产生式的分析器
评论
4 楼 lwwin 2009-02-07  
改好，编译通过，测试运行正常
不过因为目前的变动多，毕竟不是直接的COPY，所以不是很放心^^

另外主要是新的Stack的getSize被替换了height，这里没有更新，于是我担心是否还有变动呢^^？
3 楼 lwwin 2009-02-01  
两句是一个意思拉， 就是说为什么不把
self->needFactor = 0;
放在
else if(IDENT == token->type) {
这个里面而是放在
consumeNonTerminal里面

只是感觉放那里比较直观，不过兴许有别的好处
2 楼 NeuronR 2009-01-28  
lwwin 写道

上次忘了说了，在最开头的两个分析例程中，为什么要把算符分析的设置NEEDFACTOR重置为1的代码放在cosume-non-token里面？

我觉得在cusumeFactor那个函数里面的对具体的每个结束分析之后都一律调用设置0/1会比较直观一些^^或许有其中的必要性？


consumeNonTerminal这个函数并不是一个“重置”函数，因为只有在遇到变量时（确切的说，是在遇到IDENT时），OperationAnalyser才会调用另一分析器来获取一个变量，因此当这个分析器返回时，调用OperationAnalyser的consumeNonTerminal函数时传入的一定是一个VariableNode，所以此时跟遇到INTEGER或REAL一样，要将needFactor置0

后面一句不太明白你想表达什么。
1 楼 lwwin 2009-01-28  
上次忘了说了，在最开头的两个分析例程中，为什么要把算符分析的设置NEEDFACTOR重置为1的代码放在cosume-non-token里面？

我觉得在cusumeFactor那个函数里面的对具体的每个结束分析之后都一律调用设置0/1会比较直观一些^^或许有其中的必要性？
发表评论

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

相关推荐

    编译原理课程设计算符优先算法

    - **易理解性**：相对于其他复杂的语法分析方法，算符优先算法的实现更为简单直观。 #### 三、案例分析 根据题目描述，本次课程设计要求学生独立完成一系列任务，包括需求分析、系统设计、编码与调试等。具体来说...

    编译原理 算符优先

    实验"OperatorFirstAnalyser"可能包含实现这些概念的代码示例，包括词法分析器（用于生成记号流）、解析器（执行算符优先解析）以及可能的测试用例，以验证编译器的正确性。通过这个实验，你可以深入理解编译器的...

    采用算符优先分析法对表达式进行分析

    接着，我们需要编写一个独立的语法分析程序，它能够根据算符优先关系对词法分析的结果进行处理。 算符优先关系表是实现这一方法的关键。这个表包含了所有运算符的优先级和结合性信息。表中的每个运算符都与其他...

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

    布尔表达式的语法分析及语义分析是编译原理课程设计中的一个重要主题，它涉及了编译器构造的基础概念和技术。在编译原理中，布尔表达式是编程语言中用于逻辑运算的基本元素，常用于条件判断和控制流程。课程设计的...

    编译原理 课程设计报告

    这个课程设计报告详细介绍了如何使用算符优先文法进行编译器的语法和语义分析，涉及到了编译原理的重要概念，如词法分析、语法分析和语义分析。通过实际操作，学生能够深入理解编译器的工作原理，并提升编程能力。

    2011秋本科生可视化编译器实验指导书.pdf

    4. 算符优先语法分析：支持优先分析表的生成和firstVT-followVT集的计算。 实验内容以小组形式展开，每个小组有4名成员，要求每位成员独立负责特定任务，并通过团队协作共同提高。实验包括已有的功能测试，例如： ...

    编译原理答案 课后习题答案 课后习题答案

    算符优先分析程序的设计主要内容为：对教材 P110 中的上下文无关文法，实现它的算符优先分析程序，给出符号串 i+i 的分析过程。设计任务要求深入理解所学的《编译原理》相关知识，按照软件工程的设计方法进行简要的...

    秋本科生可视化编译器实验指导书.pdf

    测试内容包括但不限于文件操作、词法文法分析、词法分析、LR(0)文法分析、LR(0)语法分析、算符优先文法分析和算符优先语法分析等环节。在这些环节中，学生需对各项功能的正确性进行验证，例如文件的新建和打开、文法...

    编译原理实验指导书

    2. **算符优先分析表构造：** 根据文法构造分析表，以便能够对算术表达式和赋值语句进行语法分析。 3. **中间代码生成：** 为每个基本操作生成四元式表示，实现语法语义分析。 通过这些实验，学生不仅能够深入理解...

    小型编译系统课程设计说明书 - 副本.doc

    - 应用LL(1)文法或算符优先文法进行语法分析，这两种方法都能有效地处理程序的结构。 - 实现可视化界面，以图形方式展示编译过程，增强用户体验。 总结，小型编译系统的实现是一个全面的软件工程实践，涵盖了编程...

    2001年度程序员级上午试题

    算符优先分析法是一种典型的自底向上分析方法，它的特殊之处在于根据“句柄”进行归约。自顶向下分析方法从文法的开始符号出发，判断其能否推导出输入符号串。然而，采用自顶向下分析方法时，要求文法不含有直接左...

    大学编译原理考研辅导

    - 自底向上解析(例如算符优先解析、LR解析) - **示例**：根据上下文无关文法，可以构建出一棵表示程序结构的语法树。 ##### 3. 语义分析 - **定义**：语义分析的主要任务是检查源程序是否有语义错误，并收集类型...

    自制编程语言-样章1

    因此，书中详细探讨了自上而下的算符优先解析技术，这是一种常见的解析方法，它有助于优化编译器的性能和处理复杂表达式的解析。 除了编译器前端的知识，虚拟机作为编程语言的一个重要组成部分，其设计和实现是书中...

    蘑菇街2017校园招聘笔试题及答案.pdf

    6. **自底向上分析方法**：算符优先分析法是一种自底向上的语法分析方法，用于解析编程语言的语法结构。 7. **曼彻斯特编码**：曼彻斯特编码是数字信号的一种编码方式，每个比特的中间有一次电平翻转，用于同步。在...

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