详解C++元编程之Parser Combinator

前言

Parser Combinator（解析器组合子）是一种把「解析器」当作普通值来组合的编程范式：最小的解析器只认识一个字符，复杂解析器由小解析器通过「顺序」「选择」「重复」「映射」等组合子拼出来。它在 Haskell 的 Parsec 库里被发扬光大，核心思想是解析器就是一阶函数，组合子就是高阶函数。这个思路天然适合泛型编程，也很适合拿来讲解 C++ 的模板元编程——因为同一套组合逻辑，既可以在运行期用std::function实现，也可以在编译期用类型和模板特化实现。

这里要先澄清一个常见误解：标题里的「元编程」不等于「必须在编译期完成解析」。C++ 模板元编程（template metaprogramming, TMP）指的是用模板在编译期进行计算；而 Parser Combinator 本身是一个通用的组合技术，运行期实现同样成立。把两者结合，指的是用 TMP 的视角去设计组合子的类型结构，或者直接把解析放到编译期。本文两条路都会讲：先给出一个可读性优先的 C++17 运行期实现，再讨论编译期版本的结构与代价。

本文不依赖任何第三方解析库。文中提到的 Boost.Spirit 只作为「已有的编译期解析库」举例，不展开其具体 API；如需使用，请以其官方文档为准。

一、Parser Combinator 的基本模型

一个解析器接受输入，返回两种结果之一：解析成功，产出值并消耗掉一部分输入；解析失败。把输入建模为std::string_view，把「剩余输入」也建模为std::string_view，就能得到最简模型：

Parser<T> ::= (string_view) -> optional<Result<T>>
Result<T> ::= { value: T, rest: string_view }

这个模型有三个重要性质。

第一，失败不消耗输入。因为解析器接受的是值传递的string_view，失败时直接返回std::nullopt，调用者手里的原始输入毫发无损。这天然实现了回溯（backtracking），不需要额外的「保存/恢复位置」逻辑。代价是某些文法会重复解析同一段文本。

第二，组合子是高阶函数。seq(a, b)接受两个解析器，返回一个新解析器；choice(a, b)同理；many(p)接受一个解析器，返回「重复零次或多次」的解析器。组合子的返回类型仍然是Parser<...>，所以可以无限嵌套。

第三，类型携带结果。Parser<int>产出int，Parser<std::vector<int>>产出整数列表。组合子的模板参数把「产出什么」编码进类型，编译器因此能在编译期检查组合是否合理。

最小解析器通常只需要两个：匹配任意字符，匹配指定字符。其余都可以由它们组合出来。

二、用 C++17 搭一个运行期框架

先定义结果类型与解析器别名。

// 适用于 C++17
#include <cctype>
#include <cstddef>
#include <functional>
#include <optional>
#include <string>
#include <string_view>
#include <type_traits>
#include <utility>
#include <vector>

template <typename T>
struct Result {
T value;
std::string_view rest;
};

template <typename T>
using Parser = std::function<std::optional<Result<T>>(std::string_view)>;

std::function让不同类型的 lambda 都能装进同一个Parser<T>，代价是一次类型擦除和可能的间接调用。对解析器这种「组合结构在构造期确定、调用期频繁执行」的场景，这个代价通常可以接受；若追求极致，可以把Parser改成模板参数化的具体类型，但那会让组合子的签名迅速膨胀。

接下来是两个原子解析器。

// 适用于 C++17
inline Parser<char> any_char() {
return [](std::string_view s) -> std::optional<Result<char>> {
if (s.empty()) return std::nullopt;
return Result<char>{s.front(), s.substr(1)};
};
}

inline Parser<char> literal(char c) {
return [c](std::string_view s) -> std::optional<Result<char>> {
if (!s.empty() && s.front() == c) {
return Result<char>{c, s.substr(1)};
}
return std::nullopt;
};
}

s.substr(1)在s非空时是安全的，返回的是同一个字符缓冲区上的视图，不发生拷贝。

组合子部分。先看「顺序」：先跑pa，成功后再用剩余的输入跑pb，把两个值打包成std::pair。

// 适用于 C++17
template <typename A, typename B>
Parser<std::pair<A, B>> seq(Parser<A> pa, Parser<B> pb) {
return [pa, pb](std::string_view s)
-> std::optional<Result<std::pair<A, B>>> {
auto ra = pa(s);
if (!ra) return std::nullopt;
auto rb = pb(ra->rest);
if (!rb) return std::nullopt;
return Result<std::pair<A, B>>{{ra->value, rb->value}, rb->rest};
};
}

「选择」按顺序尝试，第一个成功即返回：

// 适用于 C++17
template <typename T>
Parser<T> choice(std::vector<Parser<T>> parsers) {
return [parsers](std::string_view s) -> std::optional<Result<T>> {
for (const auto& p : parsers) {
if (auto r = p(s)) return r;
}
return std::nullopt;
};
}

「重复」需要注意零宽解析器：如果某个解析器成功但不消耗任何字符，many0会永远循环。加一道长度检查。

// 适用于 C++17
template <typename T>
Parser<std::vector<T>> many0(Parser<T> p) {
return [p](std::string_view s) -> std::optional<Result<std::vector<T>>> {
std::vector<T> out;
std::string_view cur = s;
while (true) {
auto r = p(cur);
if (!r) break;
if (r->rest.size() == cur.size()) break; // 零宽保护
out.push_back(std::move(r->value));
cur = r->rest;
}
return Result<std::vector<T>>{std::move(out), cur};
};
}

「映射」把解析结果转换成另一种类型，这是让组合子保持解耦的关键：解析层只负责识别结构，语义层负责构造 AST 或直接计算。

// 适用于 C++17
template <typename T, typename F>
auto map(Parser<T> p, F f)
-> Parser<std::decay_t<decltype(f(std::declval<T>()))>> {
using U = std::decay_t<decltype(f(std::declval<T>()))>;
return [p, f](std::string_view s) -> std::optional<Result<U>> {
auto r = p(s);
if (!r) return std::nullopt;
return Result<U>{f(std::move(r->value)), r->rest};
};
}

std::decay_t用于去掉 lambda 返回值可能带的引用，保证Result<U>存放的是值而不是悬垂引用。

三、组合出列表语法

有了上面五个构件，就可以拼出「中括号包裹、逗号分隔的整数列表」。先补两个实用解析器：空白和整数。

// 适用于 C++17
inline Parser<std::string> spaces() {
return [](std::string_view s) -> std::optional<Result<std::string>> {
std::size_t i = 0;
while (i < s.size() &&
std::isspace(static_cast<unsigned char>(s[i]))) {
++i;
}
return Result<std::string>{std::string(s.substr(0, i)), s.substr(i)};
};
}

inline Parser<int> integer() {
return [](std::string_view s) -> std::optional<Result<int>> {
std::size_t i = 0;
bool negative = false;
if (i < s.size() && s[i] == '-') {
negative = true;
++i;
}
std::size_t start = i;
int value = 0;
while (i < s.size() &&
std::isdigit(static_cast<unsigned char>(s[i]))) {
value = value * 10 + (s[i] - '0');
++i;
}
if (i == start) return std::nullopt;
return Result<int>{negative ? -value : value, s.substr(i)};
};
}

std::isspace与std::isdigit的参数必须是unsigned char提升后的值或EOF，直接传负的char是 UB，所以这里做了显式转换。

token解析器负责吃掉尾随空白，between负责匹配一对括号，sep_by1负责分隔列表：

// 适用于 C++17
template <typename T>
Parser<T> token(Parser<T> p) {
return map(seq(std::move(p), spaces()),
[](std::pair<T, std::string> v) { return std::move(v.first); });
}

template <typename Open, typename T, typename Close>
Parser<T> between(Parser<Open> open, Parser<T> p, Parser<Close> close) {
return map(
seq(seq(std::move(open), std::move(p)), std::move(close)),
[](std::pair<std::pair<Open, T>, Close> v) {
return std::move(v.first.second);
});
}

template <typename T>
Parser<std::vector<T>> sep_by1(Parser<T> item, Parser<char> sep) {
return map(
seq(item, many0(seq(sep, item))),
[](std::pair<T, std::vector<std::pair<char, T>>> v) {
std::vector<T> out;
out.push_back(std::move(v.first));
for (auto& pair : v.second) {
out.push_back(std::move(pair.second));
}
return out;
});
}

最后组装完整语法：

// 适用于 C++17
Parser<std::vector<int>> int_list() {
auto open = token(literal('['));
auto close = token(literal(']'));
auto comma = token(literal(','));
auto item = token(integer());

auto non_empty = between(open, sep_by1(item, comma), close);
auto empty = map(between(open, spaces(), close),
[](std::string) { return std::vector<int>{}; });

return choice<std::vector<int>>({non_empty, empty});
}

choice的两个分支都从同一个位置开始尝试：non_empty失败时不会消耗输入，因为所有解析器都是纯函数式地接收string_view，所以empty能重新从头匹配。这正是第一节说的「失败不消耗输入」带来的回溯能力。

调用方式：

// 适用于 C++17
#include <iostream>

int main() {
Parser<std::vector<int>> parser = int_list();
std::string_view input = "[1, 22, 333]";

if (auto r = parser(input)) {
for (int v : r->value) {
std::cout << v << '\n';
}
std::cout << "rest size: " << r->rest.size() << '\n';
} else {
std::cout << "parse failed\n";
}
return 0;
}

注意input的生命周期必须覆盖r的使用期：Result里存的是string_view，不是std::string。若把input换成临时std::string再取其视图，视图会在语句结束时悬垂。

四、从运行期到编译期：元编程视角

把同样的结构搬到编译期，核心变化是：值变成类型，函数变成类模板特化，失败变成「没有匹配的特化」或一个显式的失败类型。

// 适用于 C++17
template <char... Cs>
struct char_list {};

template <typename P, typename Input>
struct parse_impl; // 主模板只声明，不定义

template <char C>
struct lit {};

template <char C, char... Rest>
struct parse_impl<lit<C>, char_list<C, Rest...>> {
using type = char_list<Rest...>; // 匹配成功，消耗一个字符
};

这里parse_impl<lit<'a'>, char_list<'a', 'b'>>::type就是char_list<'b'>。若输入首字符不匹配，没有对应的特化，实例化会失败——这是一种「硬失败」，不是运行期的std::nullopt。用模板做解析器组合子时，最麻烦的正是错误处理：编译错误会指向某个深层特化，可读性远不如运行期返回nullopt。

顺序组合子可以这样写：

// 适用于 C++17
template <typename A, typename B>
struct seq_parser {};

template <typename A, typename B, typename Input>
struct parse_impl<seq_parser<A, B>, Input> {
using first = typename parse_impl<A, Input>::type;
using type = typename parse_impl<B, first>::type;
};

这个写法要求A必须能在Input上成功，否则parse_impl<A, Input>不完整，编译直接报错。要在编译期实现「选择」，需要引入「尝试匹配、失败则走另一分支」的机制，通常用std::void_t做 SFINAE 探测，或者用if constexpr配合constexpr函数。这也是为什么纯 TMP 写解析器组合子比运行期版本复杂得多。

现代 C++ 提供了另一条更实用的路径：constexpr函数 +std::string_view。C++17 的constexpr已经支持循环、分支和局部变量，C++20 又加入了consteval与更完整的编译期字符串处理。用运行期那套Parser<T>的算法，把std::function换成函数指针或模板参数，把std::optional换成constexpr可用的返回结构，就能在编译期完成解析。代价是编译期计算有深度和步数限制，复杂文法会让编译时间显著上升，且出错信息依然不友好。

实际工程中的选择大致是：

方案	解析时机	优点	缺点

std::function组合子

运行期

易写易调试，错误可报告

类型擦除开销，回溯可能重复解析

模板参数化组合子

运行期

可内联、无类型擦除

类型签名复杂，编译膨胀

纯 TMP 特化

编译期

结果零运行期成本

错误信息差，文法受限

constexpr函数

编译期

写法接近运行期，可调试

受编译期步数限制

第三方库（如 Boost.Spirit）

编译期

功能完整

学习曲线陡，编译慢

常见坑点

1. 
   
2. ❌ 在递归文法里让 lambda 按引用捕获自身所在的std::function。
3. 
   

✅ 用std::shared_ptr持有解析器，或把递归规则拆成独立函数；悬垂引用会导致 UB。

1. 
   
2. ❌ 用many0包裹一个可能匹配空串的解析器。
3. 
   

✅ 加「零宽即停止」的保护，如比较前后rest.size()；否则死循环。

1. 
   
2. ❌ 写左递归文法，例如「表达式 = 表达式 + 项」。
3. 
   

✅ 递归下降解析器遇到左递归会无限展开；改写成右递归或循环形式。

1. 
   
2. ❌ 让Result持有指向临时std::string的string_view。
3. 
   

✅ 保证被指向的字符串生命周期覆盖解析结果；必要时在结果里存std::string。

1. 
   
2. ❌ 以为失败的分支已经「消耗」了输入，于是手动回退位置。
3. 
   

✅ 解析器按值接收string_view，失败不改变调用者的输入，天然可回溯。

1. 
   
2. ❌ 在integer解析里不做范围检查，长数字导致int溢出。
3. 
   

✅ 累加前判断是否超过INT_MAX / 10，或先用long long再检查范围。

1. 
   
2. ❌ 在编译期解析器里用大量特化，导致模板深度爆炸。
3. 
   

✅ 控制文法规模，优先用constexpr函数；关注编译时间和错误可读性。

1. 
   
2. ❌ 把std::function组合子当成零开销抽象。
3. 
   

✅ 它有一次类型擦除和间接调用；需要性能时改用模板参数化或函数指针。

总结

构件	作用	实现要点

原子解析器

识别单个字符

空输入返回失败

seq

顺序组合

用前一个的rest喂给后一个

choice

选择分支

按顺序尝试，失败不消耗输入

many0

重复零次以上

必须防零宽死循环

map

结果转换

用decay_t去掉引用

token/between/sep_by1

语法糖

由基础组合子拼出

Parser Combinator 的精髓是「用少量高阶函数覆盖大部分文法结构」，而 C++ 的模板恰好能把「解析器产出什么类型」编码进签名，让组合在编译期就被检查。运行期版本胜在可调试、错误可报告；编译期版本胜在零运行期开销，但要付出编译时间和错误信息的代价。理解两者的映射关系，比记住某个具体实现更重要：值对应类型，函数对应模板特化，optional对应 SFINAE 或显式的失败类型。掌握这层对应，再去看任何解析库的设计都不会觉得陌生。