当前位置：首页 > news >正文

使用组合子构建抽象语法树

news 2025/9/1 7:40:37

引言

组合子（Combinator）是一种函数式编程中的概念，它允许我们通过组合简单的函数来构建复杂的逻辑。在解析器和抽象语法树（AST）的构建中，组合子提供了一种简洁且模块化的方法。本文将介绍如何使用组合子来构建一个简单的表达式解析器，并生成对应的抽象语法树。

组合子基础

组合子的核心思想是通过函数的组合来表达复杂的逻辑，而不必显式地使用变量。在C++中，我们可以使用函数对象（Functor）来实现组合子。

基本组合子

以下是一些常见的组合子：

Sequence: 顺序执行两个解析器，并返回组合后的结果。
Choice: 尝试第一个解析器，如果失败则尝试第二个解析器。
Repeat: 重复执行一个解析器，直到无法匹配为止。

示例代码

#include <string>
#include <vector>
#include <functional>
#include <variant>using namespace std;// 定义一个结果类型，用于存储解析结果
template <typename T>
struct Result {bool success;T value;size_t position;Result(bool s, T v, size_t p) : success(s), value(v), position(p) {}
};// 定义一个解析器类型，输入为字符串，输出为结果
template <typename T>
using Parser = function<Result<T>(const string&, size_t)>;

构建解析器

基本解析器

数字解析器

Parser<int> number() {return [](const string& input, size_t pos) -> Result<int> {size_t end = pos;while (end < input.size() && isdigit(input[end])) {end++;}if (end == pos) {return {false, 0, pos};}int val = stoi(input.substr(pos, end - pos));return {true, val, end};};
}

操作符解析器

Parser<char> operator_parser() {return [](const string& input, size_t pos) -> Result<char> {if (pos < input.size() && (input[pos] == '+' || input[pos] == '-')) {return {true, input[pos], pos + 1};}return {false, ' ', pos};};
}

组合子实现

Sequence 组合子

template <typename A, typename B>
Parser<pair<A, B>> sequence(Parser<A> a, Parser<B> b) {return [=](const string& input, size_t pos) -> Result<pair<A, B>> {auto a_result = a(input, pos);if (!a_result.success) {return {false, {}, pos};}auto b_result = b(input, a_result.position);if (!b_result.success) {return {false, {}, pos};}return {true, {a_result.value, b_result.value}, b_result.position};};
}

Choice 组合子

template <typename T>
Parser<T> choice(Parser<T> a, Parser<T> b) {return [=](const string& input, size_t pos) -> Result<T> {auto a_result = a(input, pos);if (a_result.success) {return a_result;}return b(input, pos);};
}

Repeat 组合子

template <typename T>
Parser<vector<T>> repeat(Parser<T> p) {return [=](const string& input, size_t pos) -> Result<vector<T>> {vector<T> result;size_t current_pos = pos;while (true) {auto p_result = p(input, current_pos);if (p_result.success) {result.push_back(p_result.value);current_pos = p_result.position;} else {break;}}if (result.empty()) {return {false, {}, pos};}return {true, result, current_pos};};
}

生成抽象语法树

AST节点定义

struct ASTNode {virtual ~ASTNode() = default;virtual string toString() const = 0;
};struct NumberNode : ASTNode {int value;NumberNode(int v) : value(v) {}string toString() const override {return to_string(value);}
};struct BinaryOperationNode : ASTNode {char op;unique_ptr<ASTNode> left;unique_ptr<ASTNode> right;BinaryOperationNode(char o, unique_ptr<ASTNode> l, unique_ptr<ASTNode> r): op(o), left(move(l)), right(move(r)) {}string toString() const override {return "(" + left->toString() + " " + op + " " + right->toString() + ")";}
};

解析器与AST生成

表达式解析器

Parser<unique_ptr<ASTNode>> expression() {// 实现一个简单的表达式解析器，支持加减法auto term = number();auto operator_term = sequence(operator_parser(), term);auto expression_parser = sequence(term, repeat(operator_term));return [=](const string& input, size_t pos) -> Result<unique_ptr<ASTNode>> {auto expr_result = expression_parser(input, pos);if (!expr_result.success) {return {false, nullptr, pos};}auto& [term_result, operator_terms] = expr_result.value;unique_ptr<ASTNode> ast = make_unique<NumberNode>(term_result);for (auto& [op, operand] : operator_terms) {ast = make_unique<BinaryOperationNode>(op, move(ast), make_unique<NumberNode>(operand));}return {true, move(ast), expr_result.position};};
}

测试与示例

int main() {string input = "123+45-67";auto parser = expression();auto result = parser(input, 0);if (result.success) {cout << "Parsing successful!" << endl;cout << "AST: " << result.value->toString() << endl;} else {cout << "Parsing failed!" << endl;}return 0;
}