答案：文章介绍了在C++中构建简单抽象语法树（AST）的过程，涵盖节点基类定义、具体节点类型实现、变量环境管理、词法分析器与递归下降解析器的设计，并通过示例展示表达式解析与求值流程。
在C++中实现一个简单的抽象语法树（AST）是理解编译器或解释器工作原理的关键一步。AST 是源代码结构的树形表示，它忽略掉源码中的语法细节（如括号、分号），专注于程序的逻辑结构。下面我们将一步步构建一个极简的 AST，并结合词法分析和语法分析来解析简单表达式。
1. 定义AST节点基类
所有AST节点都应继承自一个公共基类。我们使用多态来处理不同类型的节点，比如数字、变量、二元操作等。
#include #include #include
2. 实现具体节点类型
根据常见表达式元素，定义几种基本节点：
数字节点：表示常量值二元操作节点：如加减乘除变量节点：表示标识符赋值节点：将值绑定到变量
立即学习“C++免费学习笔记（深入）”；
// 数字常量节点struct NumberExprAST : ExprAST { double val; explicit NumberExprAST(double v) : val(v) {} double evaluate() const override { return val; }};// 变量节点struct VariableExprAST : ExprAST {std::string name;explicit VariableExprAST(const std::string &n) : name(n) {}double evaluate() const override;};
// 二元操作节点（+、-、*、/）struct BinaryExprAST : ExprAST {char op;std::unique_ptr lhs, rhs;
BinaryExprAST(char o, std::unique_ptr l, std::unique_ptr r) : op(o), lhs(std::move(l)), rhs(std::move(r)) {}double evaluate() const override;
};
// 赋值节点struct AssignmentExprAST : ExprAST {std::string varName;std::unique_ptr expr;
AssignmentExprAST(const std::string &name, std::unique_ptr e) : varName(name), expr(std::move(e)) {}double evaluate() const override;
};
这些节点通过重写 evaluate 方法实现求值逻辑。变量和赋值需要访问一个全局变量环境。
3. 添加变量环境支持
我们需要一个地方存储变量值。使用一个简单的 map 即可。
static std::map variableValues;double VariableExprAST::evaluate() const {auto it = variableValues.find(name);if (it != variableValues.end()) return it->second;return 0.0; // 未定义变量默认为0}
double AssignmentExprAST::evaluate() const {double val = expr->evaluate();variableValues[varName] = val;return val;}
4. 简单的词法分析器（Tokenizer）
将输入字符串拆分为 token 流。这里只处理数字、字母、操作符和空格。
class Lexer { std::string input; size_t pos = 0;public:explicit Lexer(const std::string &src) : input(src) {}
int getNextToken() { while (pos = input.size()) return 0; // EOF if (isdigit(input[pos]) || input[pos] == '.') { std::string numStr; while (pos < input.size() && (isdigit(input[pos]) || input[pos] == '.')) numStr += input[pos++]; lastNum = stod(numStr); return 'n'; // number token } if (isalpha(input[pos])) { std::string name; while (pos < input.size() && isalnum(input[pos])) name += input[pos++]; lastIdentifier = name; return 'v'; // variable or identifier } if (input[pos] == '=') { pos++; return '='; // assignment } return input[pos++]; // operator or punctuation}double lastNum;std::string lastIdentifier;
};
5. 递归下降解析器
实现一个简单的递归下降解析器来构建AST。我们支持如下文法：
表达式 → 赋值表达式赋值表达式 → 标识符 '=' 表达式 | 加减表达式加减表达式 → 乘除表达式的序列（用 + 或 - 连接）乘除表达式 → 原子表达式的序列（用 * 或 / 连接）原子表达式 → 数字 | 变量 | (表达式)
立即学习“C++免费学习笔记（深入）”；
class Parser { Lexer lexer; int currentToken;void advance() { currentToken = lexer.getNextToken(); }std::unique_ptr parsePrimary();std::unique_ptr parseExpression();std::unique_ptr parseBinOpRHS(int precedence, std::unique_ptr lhs);std::unique_ptr parseAssignment();
public:explicit Parser(const std::string &src) : lexer(src) {advance(); // 初始化第一个token}
std::unique_ptr parse();
};
std::unique_ptr Parser::parse() {if (currentToken == 0) return nullptr;return parseAssignment();}
std::unique_ptr Parser::parseAssignment() {if (currentToken == 'v') {std::string idName = lexer.lastIdentifier;advance();if (currentToken == '=') {advance();auto expr = parseExpression();if (!expr) return nullptr;return std::make_unique(idName, std::move(expr));}// 不是赋值，则回退为普通变量使用return std::make_unique(idName);}return parseExpression();}
// 支持优先级的二元表达式解析std::unique_ptr Parser::parseExpression() {auto lhs = parsePrimary();if (!lhs) return nullptr;return parseBinOpRHS(0, std::move(lhs));}
int getOperatorPrecedence(char op) {switch (op) {case '+':case '-': return 1;case '*':case '/': return 2;default: return -1;}}
std::unique_ptr Parser::parseBinOpRHS(int precedence, std::unique_ptr lhs) {while (true) {int prec = getOperatorPrecedence(currentToken);if (prec
char op = currentToken; advance(); auto rhs = parsePrimary(); if (!rhs) return nullptr; int nextPrec = getOperatorPrecedence(currentToken); if (nextPrec > prec) { rhs = parseBinOpRHS(prec + 1, std::move(rhs)); if (!rhs) return nullptr; } lhs = std::make_unique(op, std::move(lhs), std::move(rhs));}
}
std::unique_ptr Parser::parsePrimary() {switch (currentToken) {case 'n': {auto result = std::make_unique(lexer.lastNum);advance();return result;}case 'v': {auto result = std::make_unique(lexer.lastIdentifier);advance();return result;}case '(': {advance(); // consume '('auto expr = parseExpression();if (currentToken != ')') {std::cerr
// 二元操作求值实现double BinaryExprAST::evaluate() const {double L = lhs->evaluate();double R = rhs->evaluate();switch (op) {case '+': return L + R;case '-': return L - R;case '': return L R;case '/': return L / R;default: return 0.0;}}
6. 使用示例
现在我们可以测试整个流程：
int main() { std::string input; std::cout << "Enter expression (e.g., a=3+4*2): "; std::getline(std::cin, input);Parser parser(input);auto ast = parser.parse();if (ast) { double result = ast->evaluate(); std::cout << "Result: " << result << "n"; std::cout << "Variables:n"; for (const auto& [name, val] : variableValues) { std::cout << " " << name << " = " << val << "n"; }} else { std::cerr << "Parse error.n";}return 0;
}
运行示例：
输入：a=3+4*2输出：Result: 11 Variables: a = 11
这个例子展示了如何从零开始构建一个可运行的 AST 系统。虽然功能简单，但它具备了真实编译器前端的核心组件：词法分析、语法分析、AST 构建与解释执行。
基本上就这些。你可以在此基础上扩展函数定义、控制流语句（if、while）、作用域管理等功能，逐步演化成一个完整的解释型语言前端。
以上就是C++如何实现一个简单的AST_使用C++构建抽象语法树并进行代码解析的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1486941.html
微信扫一扫 
支付宝扫一扫 
