首先实现词法分析器将源码拆分为Token，接着设计AST节点表示数字与二元操作，再通过递归下降解析器按优先级构建表达式树，最终组合Lexer与Parser完成对“2 + 3 * 4”等算术表达式的AST解析。
实现一个简单的AST（抽象语法树）解析器，需要从词法分析开始，逐步构建语法结构。C++中可以通过手动编写递归下降解析器来完成这一过程。下面是一个简化但完整的流程，帮助你理解编译原理中的核心环节：词法分析、语法分析和AST构建。
词法分析器（Lexer）
词法分析器负责将源代码拆分为一个个有意义的“记号”（Token）。例如，表达式 2 + 3 * 4 可以被分解为数字、操作符等Token。
定义Token类型：
enum TokenType {
TOKEN_NUMBER,
TOKEN_PLUS,
TOKEN_MINUS,
TOKEN_STAR,
TOKEN_SLASH,
TOKEN_EOF
};
每个Token包含类型和可能的数值（如数字的值）：
struct Token {
TokenType type;
double value; // 仅用于数字
};
Lexer类读取输入字符串，逐字符扫描并生成Token序列：
立即学习“C++免费学习笔记（深入）”；
class Lexer {
public:
Lexer(const std::string& src) : source(src), pos(0) {}
Token nextToken() {
if (pos >= source.length()) return {TOKEN_EOF, 0};
char c = source[pos];
if (isdigit(c)) {
std::string num;
while (pos < source.length() && isdigit(source[pos])) {
num += source[pos++];
}
return {TOKEN_NUMBER, std::stod(num)};
}
if (c == '+') { pos++; return {TOKEN_PLUS, 0}; }
if (c == '-') { pos++; return {TOKEN_MINUS, 0}; }
if (c == '*') { pos++; return {TOKEN_STAR, 0}; }
if (c == '/') { pos++; return {TOKEN_SLASH, 0}; }
pos++; // 跳过未知字符
return nextToken();
}
private:
std::string source;
size_t pos;
};
AST节点设计
抽象语法树由不同类型的节点构成。常见的有数字节点和二元操作节点。
struct ASTNode {
virtual ~ASTNode() = default;
};
数字节点存储常量值：
struct NumberNode : ASTNode {
double value;
NumberNode(double v) : value(v) {}
};
二元操作节点保存左右子节点和操作符：
struct BinaryOpNode : ASTNode {
std::unique_ptr left;
std::unique_ptr right;
TokenType op;
BinaryOpNode(TokenType o, std::unique_ptr l, std::unique_ptr r)
: op(o), left(std::move(l)), right(std::move(r)) {}
};
递归下降解析器（Parser）
解析器根据语法规则从Token流构建AST。我们实现最简单的算术表达式解析，支持加减乘除，并遵循优先级。
语法大致如下：
- expr → term (('+' | '-') term)*
- term → factor (('*' | '/') factor)*
- factor → NUMBER
解析器代码：
class Parser {
public:
Parser(Lexer l) : lexer(std::move(l)) {
currentToken = lexer.nextToken();
}
std::unique_ptr parse() {
return parseExpr();
}
private:
Lexer lexer;
Token currentToken;
void consume(TokenType expected) {
if (currentToken.type == expected) {
currentToken = lexer.nextToken();
} else {
throw std::runtime_error("Unexpected token");
}
}
std::unique_ptr parseExpr() {
auto node = parseTerm();
while (currentToken.type == TOKEN_PLUS || currentToken.type == TOKEN_MINUS) {
TokenType op = currentToken.type;
consume(op);
auto rhs = parseTerm();
node = std::make_unique(op, std::move(node), std::move(rhs));
}
return node;
}
std::unique_ptr parseTerm() {
auto node = parseFactor();
while (currentToken.type == TOKEN_STAR || currentToken.type == TOKEN_SLASH) {
TokenType op = currentToken.type;
consume(op);
auto rhs = parseFactor();
node = std::make_unique(op, std::move(node), std::move(rhs));
}
return node;
}
std::unique_ptr parseFactor() {
if (currentToken.type == TOKEN_NUMBER) {
auto node = std::make_unique(currentToken.value);
consume(TOKEN_NUMBER);
return node;
}
throw std::runtime_error("Expected number");
} };
测试与使用
将各部分组合起来，测试一个简单表达式：
int main() {
std::string source = "2 + 3 * 4";
Lexer lexer(source);
Parser parser(std::move(lexer));
try {
auto ast = parser.parse();
// 这里可以添加遍历AST并求值的逻辑
std::cout << "AST parsed successfully.\n";
} catch (const std::exception& e) {
std::cerr << "Parse error: " << e.what() << '\n';
}
return 0;
}
你可以进一步扩展这个解析器，加入变量、函数调用、控制流等结构。关键在于分层处理：先分词，再按优先级解析语法，最后构造树形结构。
基本上就这些。不复杂但容易忽略细节，比如Token消费时机和内存管理（这里用了unique_ptr自动释放）。理解这个流程后，就能在此基础上实现更完整的语言前端。
