在实现parser前，我们要有几个数据容器。
STL的string在C++20前还不支持constexpr，所以我们要自己实现一个简单的string对象。
template <int N>
class fixed_string {
private:
char data[N] = {};
public:
constexpr fixed_string(const char (&str)[N]) {
for (int i = 0; i < N; i++) {
data[i] = str[i];
}
}
constexpr int size() const {
return N;
}
constexpr char operator[](int idx) const {
return data[idx];
}
};
// deduction guide
template <int N>
fixed_string(const char str[N]) -> fixed_string<N>;
具有constexpr constructor的对象，数据成员声明时要首先初始化，意思是char data[N]声明是不行的，需要加上= {}给它初始化。
最下面一行函数声明一样的语句很多人应该不知道是什么意思，这是C++的user defined deduction guide，用于帮助编译器推导模版参数类型。这里的用途是将其他类型的初始化参数导向到同一个constructor，也就是用const char (&)[N]和const char [N]初始化时使用同一个constructor。
Stack是一个类似tuple的容器，但是这个Stack只需要存储类型，而不需要存储对象。所以只需要通过模版参数实现即可。这里只需要学会paramter pack的使用，还挺简单的。
每个函数加了一句return {}是为了能够将返回值当实参使用，而不用decltype(top(s)){}这样去创建一个对象。使用实参是为了使用自动类型推导，而不用写模版参数。
template <typename... Ts>
class stack {};
struct stack_empty {};
template <typename... Ts, typename... OBJs>
constexpr auto push(stack<Ts...>, OBJs...) -> stack<OBJs..., Ts...> {
return {};
}
template <typename T, typename... Ts>
constexpr auto pop(stack<T, Ts...>) -> stack<Ts...> {
return {};
}
constexpr auto pop(stack<>) -> stack<> {
return {};
}
template <typename T, typename... Ts>
constexpr auto top(stack<T, Ts...>) -> T {
return {};
}
constexpr auto top(stack<>) -> stack_empty {
return {};
}
\( Grammar: \S \rightarrow E\ \$ \E \rightarrow ch \ mod \ seq \ alt \E \rightarrow ( \ alt0 \ )\ mod\ seq\ alt \E \rightarrow \epsilon \seq0 \rightarrow ch\ mod\ seq \seq0 \rightarrow (\ alt0\ )\ mod\ seq \seq \rightarrow (\ alt0\ )\ mod\ seq \seq \rightarrow ch\ mod\ seq \seq \rightarrow \epsilon \alt0 \rightarrow ch\ mod\ seq\ alt \alt0 \rightarrow (\ alt0\ )\ mod\ seq\ alt \alt \rightarrow |\ seq0\ alt \alt \rightarrow \epsilon \mod \rightarrow * \mod \rightarrow + \mod \rightarrow ? \mod \rightarrow \epsilon \\)
得到如下parse table
\(\epsilon\)表示空字符，或者无操作。
| ( | ) | * | + | ? | | | ch | \(\epsilon\) | |
|---|---|---|---|---|---|---|---|---|
| E | (alt0) mod seq alt | ch mod seq alt | \(\epsilon\) | |||||
| alt0 | (alt0) mod seq alt | ch mod seq alt | ||||||
| alt | \(\epsilon\) | | seq0 alt | \(\epsilon\) | |||||
| mod | \(\epsilon\) | \(\epsilon\) | * | + | ? | \(\epsilon\) | \(\epsilon\) | \(\epsilon\) |
| seq0 | (alt0) mod seq | ch mod seq | ||||||
| seq | (alt0) mod seq | \(\epsilon\) | \(\epsilon\) | ch mod seq | \(\epsilon\) |
parse_table使用重载规则表达，表格的行和列分别用函数的参数类型表示，表格中的内容则用函数的返回类型表示。
f(...)是从C语言延续下来的可变参数语法，这个参数类型的重载优先级最低。所以任何没有匹配到重载的参数类型都会被这个重载“接住”，这相当于表格中空的位置，到了这里就代表parse失败，要返回一个reject告诉parser拒绝输入。
另外这里using S = E的原因是，所有语法都有一个起始符号，但是不同语法符号定义不同，这样可以在parser中使用统一的起始符号。
不过这里有个问题，虽然这样可以接收正确的输入，但是由于template<char c>没有排除terminal字符，一些错误的输出没有被reject，比如")()"。这个问题下次再解决吧。
#include "stack.h"
// 因为重载是对参数类型进行的，所以需要用这个包装一下字符。
template <char C>
struct ch {};
struct epsilon {};
// operations
// 用于指示parser下一步进行什么操作
// parser遇到stack时就将所有元素推入parse stack中。
struct reject {};
struct accept {};
struct pass {};
struct pop_input {};
struct parse_table {
struct E {};
struct alt0 {};
struct alt {};
struct seq0 {};
struct seq {};
struct mod {};
// the starting symbol
using S = E;
//////
// if the same terminal, then pop 1 input char
// poping is handled by the parser itself
template <char C>
static auto f(ch<C>, ch<C>) -> pop_input;
//////
// E
static auto f(E, ch<‘(‘>) -> stack<ch<‘(‘>, alt0, ch<‘)‘>, mod, seq, alt>;
template <char C>
static auto f(E, ch<C>) -> stack<ch<C>, mod, seq, alt>;
static auto f(E, epsilon) -> pass;
// ...
//////
// accept & reject
static auto f(stack_empty, epsilon) -> accept;
static auto f(...) -> reject;
};
parser就简单了，只需要根据parse_table::f返回的指示进行相应的操作即可。注意输入需要加上一个EOF符号表示输入结束，这里用函数来取出fstr中的char，这样就可以访问到结尾时返回一个EOF符号。EOF直接用epsilon表示，不会有歧义。
另外由于parser_table中只有函数声明，没有函数定义，所以取出下一操作时需要这样创建一个临时对象：decltype(Grammar::f(top(st), fstr_at<IDX>())){}用于next_op的实参类型推导。
#include "fixed_string.h"
#include "parse_table.h"
#include "stack.h"
template <auto& fstr, typename Grammar>
struct parser {
// starting symbol
using S = typename Grammar::S;
// 开始时要在栈上放入一个起始符号
static constexpr bool result = parser::parse(stack<S>{});
// We need to add an EOF symbol to the end of the input string.
// It is ok to use epsilon as EOF.
template <int IDX>
static constexpr auto fstr_at() {
if constexpr (IDX < fstr.size())
return ch<fstr[IDX]>{};
else
return epsilon{};
}
// parser entrance
template <int IDX = 0, typename StackT>
static constexpr bool parse(StackT st) {
auto op = decltype(Grammar::f(top(st), fstr_at<IDX>())){};
return next_op<IDX>(op, pop(st));
}
// table entry: epsilon
template <int IDX, typename StackT>
static constexpr bool next_op(pass, StackT st) {
return parse<IDX>(st);
}
// table entry: terminals
template <int IDX, typename StackT>
static constexpr bool next_op(pop_input, StackT st) {
return parse<IDX + 1>(st);
}
// table entry: stuff to push
template <int IDX, typename StackT, typename... Ts>
static constexpr bool next_op(stack<Ts...>, StackT st) {
return parse<IDX>(push(st, Ts{}...));
}
// getting results
template <int IDX, typename StackT>
static constexpr bool next_op(accept, StackT) {
return true;
}
template <int IDX, typename StackT>
static constexpr bool next_op(reject, StackT) {
return false;
}
};
我用了一个一定会参数匹配错误的空函数来让编译器输出参数的类型：
template <typename>
void ctprint(void) {
return;
}
这个函数不影响模版推导，gcc仍然会进行模版类型推导，然后输出很多错误信息。将错误信息重定向到stdin，再grep过滤出error信息就能看到实参类型了：
gcc -std=c++17 main.cc 2>&1 | grep error(.*)ctprint
比如对输入"(a|b)*"，我们要观察parse stack的变化：
‘ctprint(stack<parse_table::E>&)’
‘ctprint(stack<ch<‘(‘>, parse_table::alt0, ch<‘)‘>, parse_table::mod, parse_table::seq, parse_table::alt>&)’
‘ctprint(stack<parse_table::alt0, ch<‘)‘>, parse_table::mod, parse_table::seq, parse_table::alt>&)’
‘ctprint(stack<ch<‘a‘>, parse_table::mod, parse_table::seq, parse_table::alt, ch<‘)‘>, parse_table::mod, parse_table::seq, parse_table::alt>&)’
‘ctprint(stack<parse_table::mod, parse_table::seq, parse_table::alt, ch<‘)‘>, parse_table::mod, parse_table::seq, parse_table::alt>&)’
‘ctprint(stack<parse_table::seq, parse_table::alt, ch<‘)‘>, parse_table::mod, parse_table::seq, parse_table::alt>&)’
‘ctprint(stack<parse_table::alt, ch<‘)‘>, parse_table::mod, parse_table::seq, parse_table::alt>&)’
‘ctprint(stack<ch<‘|‘>, parse_table::seq0, parse_table::alt, ch<‘)‘>, parse_table::mod, parse_table::seq, parse_table::alt>&)’
‘ctprint(stack<parse_table::seq0, parse_table::alt, ch<‘)‘>, parse_table::mod, parse_table::seq, parse_table::alt>&)’
‘ctprint(stack<ch<‘b‘>, parse_table::mod, parse_table::seq, parse_table::alt, ch<‘)‘>, parse_table::mod, parse_table::seq, parse_table::alt>&)’
‘ctprint(stack<parse_table::mod, parse_table::seq, parse_table::alt, ch<‘)‘>, parse_table::mod, parse_table::seq, parse_table::alt>&)’
‘ctprint(stack<parse_table::seq, parse_table::alt, ch<‘)‘>, parse_table::mod, parse_table::seq, parse_table::alt>&)’
‘ctprint(stack<parse_table::alt, ch<‘)‘>, parse_table::mod, parse_table::seq, parse_table::alt>&)’
‘ctprint(stack<ch<‘)‘>, parse_table::mod, parse_table::seq, parse_table::alt>&)’
‘ctprint(stack<parse_table::mod, parse_table::seq, parse_table::alt>&)’
‘ctprint(stack<ch<‘*‘>, parse_table::seq, parse_table::alt>&)’
‘ctprint(stack<parse_table::seq, parse_table::alt>&)’
‘ctprint(stack<ch<‘\000‘>, parse_table::mod, parse_table::seq, parse_table::alt>&)’
‘ctprint(stack<parse_table::mod, parse_table::seq, parse_table::alt>&)’
‘ctprint(stack<parse_table::seq, parse_table::alt>&)’
‘ctprint(stack<parse_table::alt>&)’
‘ctprint(stack<>&)’
parse_table的template<char c>重载没有排除terminal，parser会接受一些错误输入。原文：https://www.cnblogs.com/relaxdude/p/CTRE-02.html