语法规则pri - Id | Num add - pri | add pri当存在一个表达式为: 2 3 4, 通过递归下降算法对表达式进行解析会出现左递归问题左递归与结合性问题234表达式 -先匹配add表达式再是号再是pri -先匹配add表达式再是号再是pri -先匹配add表达式再是号再是pri -无限递归...为了解决这个左递归问题可以先修改语法规则尝试倒着写add - pri | pri add那么就会先计算 3 4再跟 2 相加。会得到如下ASTadd pri 2 add pri 3 pri 4这样计算也不是不行但违背了加法运算的结合性的规定。为了彻底解决这个问题需要再对文法规则进行改造消除左递归问题原始文法规则add - mul | add mul mul - pri | mul * pri pri - Id | Num | (add)右递归文法add - mul | mul add mul - pri | pri * mul pri - Id | Num | (add)这个右递归文法这样的情况就不会存在死循环但会出现结合性问题再改造文法add - mul add add - mul add | ε mul - pri | mul * pri pri - Id | Num | (add)由于 add’的规则也是右递归的如果用标准的递归下降算又会出现运算符结合性的错误所以在第一步通过add推导之后按add’规则推导具体代码// 解决左递归 // 1. 先计算add规则 // 2. 接着计算add 规则 SimpleASTNode* SimpleCalculator::additive2(TokenReader *tokens) { SimpleASTNode *child1 multiplicative(tokens); // 应用add规则 SimpleASTNode *node child1; if (child1 ! NULL) { while (true) { Token *token tokens-peek(); // 循环应用add if (token ! NULL (token-getType() TokenType::Plus || token-getType() TokenType::Minus)) { token tokens-read(); // 读出加号 SimpleASTNode *child2 multiplicative(tokens); // 计算下级节点 node new SimpleASTNode(ASTNodeType::Additive, token-getText()); node-addChild(child1); node-addChild(child2); child1 node; } else { break; } } } return node; } // mul 规则 SimpleASTNode* SimpleCalculator::multiplicative(TokenReader *tokens) { SimpleASTNode *child1 primary(tokens); SimpleASTNode *node child1; Token *token tokens-peek(); if (child1 ! NULL token ! NULL) { if (token-getType() TokenType::Star || token-getType() TokenType::Slash) { token tokens-read(); SimpleASTNode *child2 multiplicative(tokens); if (child2 ! NULL) { node new SimpleASTNode(ASTNodeType::Multiplicative, token-getText()); node-addChild(child1); node-addChild(child2); } else { throw invalid mutiplicative expression, expecting the right part.; } } } return node; } // pri 规则 SimpleASTNode* SimpleCalculator::primary(TokenReader *tokens) { SimpleASTNode *node NULL; Token *token tokens-peek(); if (token ! NULL) { if (token-getType() TokenType::IntLiteral) { // 整型字面量 token tokens-read(); node new SimpleASTNode(ASTNodeType::IntLiteral, token-getText()); } else if (token-getType() TokenType::Identifier) { // 标识符 token tokens-read(); node new SimpleASTNode(ASTNodeType::Identifier, token-getText()); } else if (token-getType() TokenType::LeftParen) { // ( tokens-read(); node additive(tokens); if (node ! NULL) { token tokens-peek(); if (token ! NULL token-getType() TokenType::RightParen) { // ) tokens-read(); } else { throw expecting right parenthesis; } } else { throw expecting an additive expression inside parenthesis; } } } return node; // 这个方法也做了AST简化就是不用构造一个primary节点直接返回子节点。因为它只有一个节点 }最后得到的ASTadd add pri 2 pri 3
