c++ - 显示有效的 LR(0) 项

Question

我必须创建一个 C++ 程序来显示编译器设计中 SLR 解析中的有效 LR(0) 项。到目前为止，我能够将语法作为用户的输入并找到它的闭包。但我无法在 SLR 中进一步实现 goto。谁能给我提供有关如何显示语法的有效 LR(0) 项的链接或代码。
-提前致谢

Answer 1

你能接受语法的封闭吗？从技术上讲，闭包函数是在项目集（它们是具有与每个产品相关联的位置的产品集）上定义的。

现在，您询问如何显示语法的有效 LR(0) 项。您的意思要么是显示所有项目，如上一段中定义的那样，要么是显示 LR(0) 自动机的所有状态。第一个是微不足道的，因为所有可能的项目都是有效的，所以我猜你想要所有状态。这就是你所做的（直接来自龙书）。

SetOfItems getValidStates(Grammar G) {
    // S' -> S is the "first" production of G (which must be augmented)
    SetOfItems C = {[S' -> *S]};
    do {
      bool added = false;
      for (Item I : C) {
        for (Symbol X : G) {
          L = GOTO(I, X);
          if (L.size() > 0 && !C.contains(L)) {
            added = true;
            C.add(L);
          }
        }
      }
    } while (added);
    return C;
}

唯一的问题是如何实现 GOTO(SetOfItems, Symbol)。

所以，

SetOfItems GOTO(SetOfItems S, Symbol X) {
  SetOfItems ret = {}
  for (Item I : S)
    if (I.nextSymbol().equals(X))
      ret.add(I.moveDotByOne())
  return closure(ret);
}

集合中的每一项都有 [A -> a*Yb] 的形式，其中 A 是某个产生式的头部，aXb 是产生式的主体（a 和 b 只是一串语法符号，Y 是单个符号）。'*' 只是我提到的位置 - 它不在语法中，并且 [A->a*Yb].nextSymbol() 是 Y。基本上，Item.nextSymbol() 只返回右侧的任何符号点。[A->a*Yb].moveDotByOne() 返回 [A->aY*b]。

现在，我刚刚完成了编译器书中的解析章节，我对自己的理解并不完全满意，所以要小心我写的东西。

至于真实代码的链接：http: //ftp.gnu.org/gnu/bison/是你可以找到野牛源代码的地方，但那是一个 LALR 解析器生成器，我认为它没有实现 LR(0) .