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

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

最佳答案

你能完成语法吗?从技术上讲,闭包函数定义在一组项上(这些项是一组生产,具有与每个生产相关联的位置)。
现在,您将询问如何显示语法的有效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/是您可以找到bison的源代码的地方,但这是一个LALR解析器生成器,我认为它没有实现LR(0)。

本文翻译自 https://stackoverflow.com/questions/5288260/

网站遵循 CC BY-SA 4.0 协议,转载或引用请注明出处。

标签 c++ compiler-theory lr


相关文章:

objective-c - 创建编程语言问题

c++ - 如何使Python运行时安全?

c# - 如何在C#中实现按名称调用?

c++ - 将类放在名称空间中

c - 将节点放到不应该存在的解析树中

python - Python lrparsing模块;无法解析简单的递归语法

c - Yacc / Flex中的Shift / Reduce冲突

algorithm - LL和LR解析之间有什么区别?

c# - .Net如何获取Web浏览器中单击元素的ID

c++ - 向量(插入然后排序)或设置速度更快的方法是哪种?