[语法分析]无需产生式的分析器

    算符优先分析用来处理表达式非常便捷，甚至你可以忘记算术运算相关的一切产生式。对于算符优先分析来说最重要的东西有三：运算符的优先级、元和结合方式。优先级在任务布置时已经讲过了；元很简单，一般运算符都是二元的，只有正号和负号是一元的；结合方式一般分两种，普通的运算都是左结合的，赋值和乘幂运算是右结合的，而Jerry不支持乘幂运算。简单的表达式求值算法可以参考这篇文章，文中相关实现也是基于该算法的。

 

    算符分析器需要两个栈，一个用来存放符号，一个用来存放操作数，因此该结构可以这样实现

/* datastruct.h */
struct OperationAnalyser {
    memberSyntaxAnalyser
    int needFactor;
    struct Stack* opStack;
    struct Stack* numStack;
};

而needFactor则表示该算符当前应该遭遇一个因子（needFactor == 1时）还是一个运算符（needFactor == 0时）。

 

    算符分析器的构造函数可以这样实现：

void consumeToken_OpAna(void* self, struct Token* token);
void consumeNonTerminal_OpAna(void* self, struct AbstractSyntaxNode* token);

struct OperationAnalyser* newOperationAnalyser(void)
{
    struct OperationAnalyser* opana = (struct OperationAnalyser*)
                                     allocate(sizeof(struct OperationAnalyser));
    opana->needFactor = 1;
    opana->numStack = newStack();
    opana->opStack = newStack();
    // 将一个左括号压入栈顶

    opana->consumeToken = consumeToken_OpAna;
    opana->consumeNonTerminal = consumeNonTerminal_OpAna;
    return opana;
}

    上一节数据结构中，在算符优先分析器结构中有个神秘的needFactor成员我并没有给出注释，现在补述一下：这个成员指出接下来一个词法分析得到的Token是否应该某个因子的一部分，特别是读入"+"或"-"，只有借助它来判别是正负号还是加减号。另外，它在算符优先分析中可以为错误处理提供强力帮助：由于一个算符优先分析器要么立即需要一个因子，要么立即需要一个运算符，所以词法分析获取一个Token传入该分析器以后，可以查询该Token的类型是否属于因子或者算符的First集合来判别当前Token类型是否正确。在这里

    First( 因子 ) = { PLUS, MINUS, INTEGER, REAL, LPARENT, IDENT }

    First( 算符 ) = { 各种运算符 }

当然不必担心两者交集不为空会导致什么故障发生，这里并不是先判断该符号属于哪个集合，而是先看needFactor再分开分析，即OperationAnalyser的consumeToken函数可以实现为一个中转函数：

void consumeToken_OpAna(void* self, struct Token* token)
{
    struct OperationAnalyser* opana = (struct OperationAnalyser*)self;
    if(opana->needFactor) {
       consumeFactor(opana, token);
    } else {
       consumeOperator(opana, token);
    }
}

不过，有一个例外，就是所有左置的一元运算符，如NOT，它们的出现也会打乱区分工作，因此它们都应该看作 First( 因子 ) 中的成员，如consumeFactor的一种实现方式：

void consumeFactor(struct OperationAnalyser* self,
                                    struct Token* token)
{
    if(NOT == token->type) {
        self->opStack->push(self->opStack,
                            newOperator(token->type,
                                        /* 未实现：对应的优先级数 */ -1,
                                        unaryOperate));
        self->needFactor = 1;
    } else if(MINUS == token->type || PLUS == token->type) {
        // 将 MINUS 或 PLUS 作为一元运算符入栈
        self->needFactor = 1;
    } else if(IDENT == token->type) {
        // 弄一个识别变量的分析器 varAna 扔到 分析器栈 栈顶
        // varAna->consumeToken(varAna, token);
        return;
    } 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->needFactor = 1;
    } else {
        // 报错
    }
} 

这里有个小问题，就是将MINUS或PLUS作为一元运算符入栈时，栈内存放的是什么？如果是一个Token*，那么一来信息太少，以后从栈中取出操作符时就无从知道它到底是一元操作符还是二元的，另外，对于提供Token*的函数，它必须知道这个Token*是否还能重用，比如如果压入的是数，那么重用是没问题的，因为Token*已经被变成了IntegerNode或RealNode，而符号就不一样，这样增加了词法的复杂度。因此，需要另一种数据结构。

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

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

 其中，op表示算符类型，priority表示算符优先级数，越小优先级越高，rightCombination表示是否右结合，operate成员函数则指出该算符应该如何进行运算，它应该是nullOperate（非运算），unaryOperate（一元运算），binaryOperate（二元运算）三者之一。newOperator则提供了一个构造函数。这些劳什子的可以这样实现：

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 = (ASSIGN == op); // ... 暂时就这么办吧
    oper->operate = operate;
    return oper;
}

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

void unaryOperate(struct Operator* oper, struct Stack* numStack)
{
    struct AbstractValueNode* value;
    if(MINUS == oper->op) {
        value = (struct AbstractValueNode*)(numStack->pop(numStack));
        numStack->push(numStack,
                       newOperationNode(oper->op,
                                   (struct AbstractValueNode*)newIntegerNode(0),
                                   value));
    }
    revert(oper);
}

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, newOperationNode(oper->op, left, right));
    revert(oper);
}

这样一来consumeFactor中某些分支可以这样写：

    if(MINUS == token->type || PLUS == token->type) {
        self->opStack->push(self->opStack,
                            newOperator(token->type, 0, unaryOperate));
        self->needFactor = 1;
    }
// ... ...
    if(LPARENT == token->type) {
        self->opStack->push(self->opStack, newOperator(token->type,
                                                       0x7fffffff, /* max integer */
                                                       nullOperate));
        self->needFactor = 1;
    }

 

接下来是consumeOperator的实现。为了不让优先级成为一个头痛的问题，这里弄一个优先级表，它的顺序对应于AcceptType中各符号：

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
};

这里面的0不是优先级最高的意思了（优先级数为0的正负号在构造时是手动设置的），而是表示不应该在这时出现这样的符号，当然有一个例外，就是反括号。consumeOperator可以这样部分地实现：

void 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) {
            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,
                                                       binaryOperate));
        self->needFactor = 1;
    } else if(RPARENT == token->type) {
        struct Operator* topOp = (struct Operator*)
                                         (self->opStack->pop(self->opStack));
        while(nullOperate != topOp->operate) { // 注1
            topOp->operate(topOp, self->numStack);
            topOp = (struct Operator*)(self->opStack->pop(self->opStack));
        }
        topOp->operate(topOp, self->numStack);
        if(0 == self->opStack->getSize(self->opStack)) { // 注2
            // 报错
        }
        self->needFactor = 0;
    } else {
        // 终止
    }
}

前面读到一般运算符时进行的分析，思路还算清晰；后面注出的两个条件，可能形式上不是很确切。

    注1：nullOperate != topOp->operate 实际上是在查看栈顶运算符是否是正括号，因为只有正括号的operate函数才为nullOperate

    注2：0 == self->opStack->getSize(self->opStack) 判断栈底默认压入的正括号是否被弹出，如果被弹出则说明正反括号实际上是不配对的（反括号多1）。

    此外，这个循环

        push |= (priority < topOp->priority);
        push |= (priority == topOp->priority && topOp->rightCombination);
        while(!push) {
            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);
        }

其实你可以把它当作一个for循环来理解，push这个量为1时，表示当前传入的这个运算符应该被压入栈中。

    最后，读到不正确的符号时，并不能说明分析出错，也很可能是因为一个表达式已经接近完成并应该返回给分析器栈次栈顶的分析器了。

 

    最后大致提一下consumeNonTerminal_OpAna这个函数，其实它非常简单，因为算符优先分析只会委托另一分析器为之提供一个VariableNode，因此只要该分析器正确返回，那么只需

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

就行了，而如果该分析器没有正常返回——就把错误处理给那个分析器做吧。

 

    这一篇文章中很多代码都是未完成的，因为分析器不是一个独立的结构，牵扯到很多控制结构和其他分析器。不过我会尽快给出一个方案让算符优先分析尽可能地独立出来进行测试，以减少语法分析模块整体的测试难度。

评论

7 楼 NeuronR 2009-01-27  

lwwin 写道

那取栈顶的代码是不是还没有^^？

        int push = 0;  
        struct Operator* topOp = (struct Operator*)  
                                         (self->opStack->getTop(self->opStack));  
        push |= (priority < topOp->priority);  
        push |= (priority == topOp->priority && topOp->rightCombination);  
        while(!push) {  
            topOp = (struct Operator*)(self->opStack->pop(self->opStack));
            topOp->operate(topOp, self->numStack);

            topOp = (struct Operator*)(self->opStack->getTop(self->opStack));  
            push |= (priority < topOp->priority);  
            push |= (priority == topOp->priority && topOp->rightCombination);  
        }  
        self->opStack->push(self->opStack, newOperator(token->type,  
                                                       priority,  
                                                       binaryOperate));

一切都在这个循环里面。
循环开头第一句
topOp = (struct Operator*)(self->opStack->pop(self->opStack));
弹出栈顶操作符，接着运算。而第三句取栈顶
topOp = (struct Operator*)(self->opStack->getTop(self->opStack));
但是不弹出它，这样做是为了确定push的值。

6 楼 lwwin 2009-01-24  

那取栈顶的代码是不是还没有^^？

5 楼 NeuronR 2009-01-24  

lwwin 写道

// 将一个左括号压入栈顶
这句话的意思明白了，提个建议，为实现的用类似于VC的//TODO：标记，这样不会费解^^，当时我把这句注释加了问，因为不解^^

第一个问题仔细看明白你!PUSH的意思了，应该是对高优先级的算符进行结合为非终结符并且被压入数字栈（才注意到有二个栈在操作）

现在只剩一个问题，就是超前看一位的呈现还不明朗，出现二元算符的时候，
例如 a + b * c，其中看到*的时候，根据优先级判断 push == 0
此时构造 binary ( MUL, b, c ) 但是c是不是还没有读入呢？

我再看看，这次修补的东西多了点^^

好，以后用 // TODO

至于运算符栈的操作，对于二元运算符，确实是在没有读入右侧操作数时就判定是否该进行运算。但是，这里的运算并不是指当前读入的符号，而是当前栈顶的符号，如你给的例子，在读入
a + b *
时，刚刚读入的 * 号还未入栈。即使判定此时应该运算，也不是建立一个binary ( MUL, b, c )，而是 binary ( ADD, a, b )

4 楼 lwwin 2009-01-23  

// 将一个左括号压入栈顶
这句话的意思明白了，提个建议，为实现的用类似于VC的//TODO：标记，这样不会费解^^，当时我把这句注释加了问，因为不解^^

第一个问题仔细看明白你!PUSH的意思了，应该是对高优先级的算符进行结合为非终结符并且被压入数字栈（才注意到有二个栈在操作）

现在只剩一个问题，就是超前看一位的呈现还不明朗，出现二元算符的时候，
例如 a + b * c，其中看到*的时候，根据优先级判断 push == 0
此时构造 binary ( MUL, b, c ) 但是c是不是还没有读入呢？

我再看看，这次修补的东西多了点^^

3 楼 NeuronR 2009-01-22  

lwwin 写道

还有一个，不知道算法分析例程是单个( )括号处理还是多个，感觉可以支持多个的
就是(a + (b + c))的情况，但是这句我(注2那句)
if(0 == self->opStack->getSize(self->opStack)) {
的意思是只支持单个配对么？

注意到第一块代码中有一行注释：压入一个正括号到栈顶。实际上表达式不会总被正括号包起来——没哪个程序员会有这样的风格而且甚至在Java里面这样会被认为是语法错误。

压入一个正括号是一种策略，首先，因为有一个正括号“垫底”，那么不必每次传入运算符时都去判断符号栈是否为空；第二，当程序书写发生错误时，特别是多出一个反括号时，它会与这个虚假的正括号匹配，这时符号栈为空，就认为错误发生了。

支持括号嵌套是必须的，这一点要坚持不动摇。我想你是不是在问这一点在哪里实现。其实，当出现反括号时，符号栈里面的符号会顺序弹出，依次运算，直到遇到一个正括号为止，但是，词法分析一次只会返回一个符号，即使反括号连续出现，一次也只会匹配一个正括号。如你给的例子
(a + (b + c))
输入到
(a + (b + c
时，符号栈（第一个左括号是垫底左括号）和数栈情况如下：
( ( + ( +
a b c
这时读入第一个反括号，于是弹出栈顶加法进行运算，结果假设为x，压回栈顶，再弹出一个符号，发现它是左括号，于是运算终止，算符分析函数返回，栈里变成这样：
( ( +
a x
这时读入第二个反括号，于是又弹出加号，运算一次(设结果为y)，再弹出正括号，又一次匹配结束返回：
(
y
这时加入后面紧跟了一个反括号（也就是多余的反括号），它会匹配掉栈底的正括号。
注意，准确地说，这时仍然没有错误产生，因为if语句或者while语句的条件有一个反括号结尾，如

if( a == b )

这个额外的反括号实际上不应该让算符优先分析器来处理，因此接下来不应该是简单的报错，而应该这样：
-  弹出分析器栈栈顶（就是该算符优先分析器本身）
-  将算符优先分析器此时数栈栈顶元素 num 传递给现在的分析器栈栈顶的 consumeNonTerminal 函数
-  将反括号传递给现在的分析器栈顶的 consumeToken 函数

lwwin 写道

感觉用OBJC看起来还是比较吃力啊= =不如C++的VIRTUAL来的轻松

另外：比如分析 a + b - c的-的时候，应该是优先级相同且左结合的时候应该归并，
于是可能是：
priority == topOp->priority && !topOp->rightCombination
而不是
priority == topOp->priority && topOp->rightCombination
吧？

well... push为1的意思是把当前符号压入栈，或许你理解错了以为是让栈顶符号进行运算？

很感谢你对我的支持，同时很抱歉，最近的两篇文章——这一篇，以及之前的那一篇[语法分析]语法树及分析器数据结构——里面有一些错误，它们是：
*  这一篇文章中的优先级表

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,
    4, 4, 4,
    0, 0, 0x7fffffff, 0, 0, 0, 0, 0
};

与或非对应的优先数曾经是一样的，现在它们已经被修改正确了。
*  这一篇文章中的

consumeFactor

曾经的实现中并没有提到将NOT（即符号 ! ）也考虑为因子的开头，现在这一情况已经被加入了（这样多出一个if-else分支，导致代码变得更加狰狞了:-(），此外对应的文字说明也有了修改。
*  上一篇文章中，由于我贴的代码是我曾经的一个很蹩脚的代码版本（sorry, 我写这玩意时没有用版本控制，导致现在手头上代码版本只有3个：词法分析完成版，全部完成版，以及刚才说的那个错误版本），而导致有两个数据结构被遗忘了，它们是
BinaryOperationNode
UnaryOperationNode
而那个错误的就是
OperationNode
实际上这三个数据结构之间并不构成任何继承关系，现在最后那个已经被删除并被前两个替代了。对应了，那些实现代码也都改变了。

如果你在我的代码中还看到任何有问题的地方或含糊不清的地方（我写注释很懒的），请及时回复我，或者发送邮件联系我。
lene13 @ gmail . com

2 楼 lwwin 2009-01-22  

还有一个，不知道算法分析例程是单个( )括号处理还是多个，感觉可以支持多个的
就是(a + (b + c))的情况，但是这句我(注2那句)
if(0 == self->opStack->getSize(self->opStack)) {
的意思是只支持单个配对么？

1 楼 lwwin 2009-01-22  

感觉用OBJC看起来还是比较吃力啊= =不如C++的VIRTUAL来的轻松

另外：比如分析 a + b - c的-的时候，应该是优先级相同且左结合的时候应该归并，
于是可能是：
priority == topOp->priority && !topOp->rightCombination
而不是
priority == topOp->priority && topOp->rightCombination
吧？