在Shift/Reduce解析器生成器中指定c++ 11语法动作函数

Question

我正在c++ 11中的shift/reduce解析器生成器上工作，我不确定如何指定输入产品和减少操作函数的接口类型，以便它们将保存我想要放入其中的信息。

我想静态地指定语法，但使用c++类型(而不是单独的构建工具)。

对于每个符号(终端和非终端)，用户提供一个字符串名称和类型。

然后每个产品指定一个头部符号名称和一个或多个主体符号名称。

对于每个产品，用户(硬部分)提供一个动作函数，该函数返回头部非终结类型，并具有与产品主体符号(其相应类型)相对应的参数。

主要问题是将这些动作函数的参数类型和返回类型静态地绑定到相应的符号类型

例如:

假设我们有非终端X, A, B, C

它们的名称/类型可能是:

"X" Foo
"A" string
"B" string
"C" int

在语法中可能有一个结果:

X -> A B C

用户将为该产品提供一个操作函数:

Foo f(string A, string B, int C)

如果产量减少，则应使用生产体参数调用函数f。f返回的值被存储起来，以备该符号在更上层的约简中使用。

因此，要向解析器生成器指定语法，我需要提供如下内容:

(我知道下面是无效的)

struct Symbol
{
    string name;
    type T;
}
struct Production
{
    string head;
    vector<string> body;
    function<head.T(body[0].T, body[1].T, ..., body[n].T)> action;
}
struct Grammar
{
    vector<Symbol> symbols;
    vector<Production> productions;
}

要指定前面的例子将是:

Grammar example =
{
    // symbols
    {
        { "X", Foo },
        { "A", string },
        { "B", string },
        { "C", int }
    },
    // productions
    {
        { 
            "X",
            { "A", "B", "C" },
            [](string A, string B, int C) { ... return Foo(...); }
        }
    }
}

这当然不行，你不能像这样把类型参数和运行时参数混在一起。

一个解决方案是有一些通用碱基:

struct SymbolBase
{
    ...
}
template<class SymbolType>
struct SymbolDerived<SymbolType> : SymbolBase
{
    SymbolType value;
}

然后使所有动作函数的类型为:

typedef function<SymbolBase(vector<SymbolBase>)> ActionFunction;

并在运行时对其进行排序。但是这使得使用更加困难，而且所有的cast都很慢。我宁愿在编译时检查函数签名，并对用户隐藏机制。

我如何重构符号、生产和语法类型来承载我试图在合法的c++ 11中传达的信息?

(是的，我看过Boost Spirit和朋友们，它是一个很好的框架，但它是递归下降，所以它可以在一次传递中处理的语言比LALR解析器少，因为它使用回溯，减少动作将被多次调用，等等)

Answer 1

我一直在研究这个问题。我一直在考虑的一种可能性(看起来应该可以工作)是使用一堆变量对象，可能是boost::variant或boost::any。由于每次缩减都知道它期望从堆栈中得到什么，因此访问将是类型安全的;不幸的是，类型检查将在运行时进行，但它应该非常便宜。这样做的好处是可以捕获bug:)，而且当对象从堆栈中弹出时，它也会正确地销毁对象。

我将一些示例代码作为PoC，可根据要求提供。编写约简规则的基本风格是这样的:

parse.reduce<Expression(Expression, _, Expression)>
  ( [](Expression left, Expression right){
      return BinaryOperation(Operator::Times, left, right);
  });

对应于以下规则:

expression: expression TIMES expression

这里，BinaryOperation是AST节点类型，必须转换为Expression;模板参数Expression(Expression, _, Expression)正好是结果的左边和右边，用类型表示。(因为第二个RHS类型是_，模板不需要费心将值提供给约简规则:使用适当的解析器生成器，实际上根本没有理由将标点符号推入堆栈。)我使用boost::variant实现了标记联合Expression和解析器堆栈的标记类型。如果您尝试这样做，值得知道的是，使用一个变体作为另一个变体的选项类型之一实际上不起作用。最后，将较小的union封装为struct是最简单的。您还必须阅读有关递归类型的部分。