显示有效的LR(0)项

Question

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

提前使用-Thanks

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。

现在，我刚刚读完了编译器一书中的解析一章，我对我的理解并不完全满意，所以要小心我所写的内容。

至于到真实代码的链接:bison的源代码可以在http://ftp.gnu.org/gnu/bison/中找到，但这是一个LALR解析器生成器，我不认为它实现了LR(0)。