从Token Stream解析表达式

Question

我正在尝试解析一个简单的脚本语言的表达式,但我很困惑.现在,只能将数字和字符串文字解析为表达式:

int x = 5;
double y = 3.4;
str t = "this is a string";

但是,我对解析更复杂的表达式很困惑:

int a = 5 + 9;
int x = (5 + a) - (a ^ 2);

我想我会像下面这样实现它:

do {
    // no clue what I would do here?        

    if (current token is a semi colon) break;
}
while (true);

任何帮助都会很棒,我不知道从哪里开始.谢谢.

编辑:我的解析器是递归下降解析器

我的表达"类"如下:

typedef struct s_Expression {
    char type;
    Token *value;

    struct s_Expression *leftHand;
    char operand;
    struct s_Expression *rightHand;
} ExpressionNode;

有人提到递归下降解析器能够解析表达式而不做中缀,而不是后缀.最好,我想要一个像这样的表达式:

例如:

int x = (5 + 5) - (a / b);

将被解析为:注意:这不是有效的C,这只是一些伪的ish代码来简单地得到我的观点:)

ExpressionNode lh;
lh.leftHand = new ExpressionNode(5);
lh.operand = '+'
lh.rightHand = new ExpressionNode(5);

ExpressionNode rh;
rh.leftHand = new ExpressionNode(a);
rh.operand = '/';
rh.rightHand = new ExpressionNode(b);

ExpressionNode res;
res.leftHand = lh;
res.operand = '-';
res.rightHand = rh;

我很晚才问这个问题,很抱歉,如果我不清楚,我完全忘记了我最初的目标.

Answer 1

我最终使用的方法是运算符优先级解析。

parse_expression_1 (lhs, min_precedence)
    lookahead := peek next token
    while lookahead is a binary operator whose precedence is >= min_precedence
        op := lookahead
        advance to next token
        rhs := parse_primary ()
        lookahead := peek next token
        while lookahead is a binary operator whose precedence is greater
                 than op's, or a right-associative operator
                 whose precedence is equal to op's
            rhs := parse_expression_1 (rhs, lookahead's precedence)
            lookahead := peek next token
        lhs := the result of applying op with operands lhs and rhs
    return lhs