5

我正在使用 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;

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

如何重组 Symbol、Production 和 Grammar 类型以承载我试图在合法 C++11 中传达的信息？

（是的，我看过 Boost Spirit 和朋友，它是一个很好的框架，但它是递归下降的，因此它可以在单次传递中处理的语言少于 LALR 解析器，并且因为它使用回溯，所以会多次调用归约动作等）

4

1 回答 1

1

我一直在玩弄这个问题。我一直在研究的一种可能性（看起来应该可行）是使用一堆变体对象，也许是 boost::variant 或 boost::any。由于每个归约都知道它对堆栈的期望，因此访问将是类型安全的；不幸的是，类型检查将在运行时进行，但它应该非常便宜。这具有捕获错误的优势:) 并且它还会在对象从堆栈中弹出时正确地破坏它们。

我将一些示例代码放在一起作为 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 类型是 _，模板不会费心将值提供给归约规则：使用适当的解析器生成器，实际上甚至没有理由首先将标点符号推入堆栈。）使用 . 实现了解析器堆栈的标记联合Expression和标记类型boost::variant。如果您尝试此操作，则值得知道使用变体作为另一个变体的选项类型之一实际上并不起作用。最后，将较小的联合包装为struct. 您还必须阅读有关递归类型的部分。

于 2012-12-22T07:17:01.067 回答