该C++ AST解释器通过三步实现：词法分析（隐式跳过空格）、递归下降语法分析（parseExpr/parseTerm/parseFactor处理优先级）、虚函数AST求值，支持整数、四则运算和括号，代码精简可运行。
用 C++ 实现一个简单的 AST 解释器，核心是三步：词法分析（Tokenizer）→ 语法分析（Parser，生成 AST）→ 解释执行（Evaluator）。下面是一个可运行的入门级实现，支持加减乘除、括号和整数，代码精简、结构清晰，适合编译原理初学者理解流程。
1. 定义 AST 节点类型
先设计抽象语法树的节点基类和具体表达式节点，用 std::variant 或虚函数均可；这里采用虚函数 + 继承，更直观易懂：
// ast.hpp #include#include #include struct AstNode { virtual ~AstNode() = default; virtual int eval() const = 0; };
struct NumberNode : AstNode { int value; NumberNode(int v) : value(v) {} int eval() const override { return value; } };
struct BinaryOpNode : AstNode { char op; std::unique_ptr left; std::unique_ptr right; BinaryOpNode(char o, std::unique_ptr l, std::unique_ptr r) : op(o), left(std::move(l)), right(std::move(r)) {} int eval() const override { int l = left->eval(); int r = right->eval(); switch (op) { case '+': return l + r; case '-': return l - r; case '': return l r; case '/': return r != 0 ? l / r : throw std::runtime_error("div by zero"); default: throw std::runtime_error("unknown op"); } } };
2. 手写递归下降 Parser（生成 AST）
不依赖外部库，用字符串索引+递归下降实现。支持优先级：乘除 > 加减 > 括号。关键技巧是提取 parseExpr（处理 +−）、parseTerm（处理 *⁄）、parseFactor（处理数字/括号）：
// parser.hpp #include#include #include "ast.hpp" class Parser { std::string input; size_t pos = 0;
void skipSpace() { while (pos < input.size() && isspace(input[pos])) ++pos; } int parseNumber() { skipSpace(); int start = pos; while (pos < input.size() && isdigit(input[pos])) ++pos; if (start == pos) throw std::runtime_error("expected number"); return std::stoi(input.substr(start, pos - start)); } std::unique_ptr parseFactor() { skipSpace(); if (pos < input.size() && input[pos] == '(') { ++pos; // '(' auto expr = parseExpr(); skipSpace(); if (pos < input.size() && input[pos] == ')') ++pos; else throw std::runtime_error("expected ')'"); return expr; } return std::make_unique(parseNumber()); } std::unique_ptr parseTerm() { auto left = parseFactor(); while (true) { skipSpace(); if (pos < input.size() && (input[pos] == '*' || input[pos] == '/')) { char op = input[pos++]; auto right = parseFactor(); left = std::make_unique (op, std::move(left), std::move(right)); } else break; } return left; } std::unique_ptr parseExpr() { auto left = parseTerm(); while (true) { skipSpace(); if (pos < input.size() && (input[pos] == '+' || input[pos] == '-')) { char op = input[pos++]; auto right = parseTerm(); left = std::make_unique (op, std::move(left), std::move(right)); } else break; } return left; } public: Parser(const std::string& s) : input(s) {} std::unique_ptr parse() { return parseExpr(); } };
3. 主程序：读取、解析、求值
一行输入，一次解析，一
次求值。加入基础错误处理，便于调试：
// main.cpp #include#include #include "parser.hpp" int main() { std::string line; std::cout << "AST Interpreter (enter 'quit' to exit):\n"; while (std::getline(std::cin, line)) { if (line == "quit") break; try { Parser p(line); auto ast = p.parse(); std::cout << "= " << ast->eval() << "\n"; } catch (const std::exception& e) { std::cerr << "Error: " << e.what() << "\n"; } } return 0; }
4. 编译与运行
使用 C++17 或更新标准（需 std::unique_ptr 和 structured binding 支持）：
- 保存为
ast.hpp、parser.hpp、main.cpp - 编译命令：
g++ -std=c++17 -o calc main.cpp - 运行：
./calc，然后输入如3 + 4 * 2→ 输出= 11
这个解释器虽小，但已覆盖编译前端核心环节：Token 不显式建结构（简化版“隐式 token”），Parser 是纯手工递归下降，AST 节点可轻松扩展（比如加变量、赋值、if）。下一步可引入符号表支持变量，或改造成字节码生成器——本质上就是编译器的雏形。
基本上就这些。不复杂但容易忽略细节，比如运算符优先级顺序、括号匹配、空格跳过和错误位置提示。把 parser 的每个函数对应到语法产生式（如 Expr → Term { (+|−) Term }），你就真正跨进编译原理的门了。
