为什么不能用LR(1)parsing器分析C ++?

我正在阅读关于parsing器和parsing器生成器,并发现这个声明在维基百科的LRparsing页:

许多编程语言可以使用LRparsing器的一些变体来parsing。 一个明显的例外是C ++。

为什么这样? C ++的特殊属性是不可能用LRparsing器parsing的?

使用谷歌,我只发现C可以用LR(1)完美parsing,但C ++需要LR(∞)。

在Lambda Ultimate上有一个有趣的线索,讨论了C ++的LALR语法 。

它包含一个博士论文的链接,其中包括对C ++parsing的讨论,其中指出:

“C ++语法是不明确的,依赖于上下文的,可能需要无限的前瞻来解决一些歧义”。

它继续给出了一些例子(见pdf的第147页)。

LR语法分析器不能处理模糊的语法规则。 (在20世纪70年代,当理念被制定出来的时候,这个理论变得更容易了)。

C和C ++都允许以下语句:

x * y ; 

它有两个不同的parsing:

  1. 它可以是y的声明,作为指向x的指针
  2. 它可以是x和y的乘数,扔掉答案。

现在,你可能会认为后者是愚蠢的,应该被忽略。 大多数人会同意你的看法。 然而,有些情况下可能会有副作用(例如,如果乘法超载)。 但这不是重点。 关键是有两个不同的parsing,因此程序可能意味着不同的事情取决于应该如何parsing。

编译器必须在适当的情况下接受适当的信息,并且在没有任何其他信息的情况下(例如,知道x的types)必须收集这两者,以便稍后决定要做什么。 因此一个语法必须允许这个。 这使得语法模糊。

因此,纯粹的LRparsing不能处理这个问题。 许多其他广泛使用的parsing器生成器,如Antlr,JavaCC,YACC或传统的Bison,甚至PEG风格的parsing器也不能用于“纯”的方式。

有很多更复杂的情况(parsing模板语法需要任意的向前看,而LALR(k)可以看到最多k个令牌),但只有一个反例才能击倒纯粹的 LR(或其他)parsing。

大多数真正的C / C ++parsing器通过使用某种确定性分析器来处理这个例子,它们带有额外的黑客攻击:它们与符号表集合交织在一起…因此,当遇到“x”时,parsing器知道x是否是一个types或者不可以,因此可以在两个潜在的parsing之间进行select。 但是,这样做的parsing器不是上下文无关的,而LRparsing器(纯粹的parsing器等)是(最好的)上下文自由的。

人们可以作弊,并在LRparsing器中添加每规则缩短时间语义检查来做这种消除歧义。 (这段代码通常并不简单)。 大多数其他parsing器types都有一些方法来在parsing中的各个点添加语义检查,可以用来执行此操作。

如果你足够的作弊,你可以让LRparsing器为C和C ++工作。 海湾合作委员会的人做了一段时间,但放弃了手动编码parsing,我想,因为他们想要更好的错误诊断。

还有另外一种方法,它很好,很干净,并且可以很好地parsingC和C ++,而且不需要任何符号表hackery: GLRparsing器 。 这些是完全的上下文自由分析器(具有无限的前瞻性)。 GLRparsing器只接受两个parsing,产生一个表示模糊parsing的“树”(实际上是一个定向的非循环图,主要是树)。 parsing后传递可以解决歧义。

我们在C和C ++前端为我们的DMS Software Reengineering Tookit(截至2017年6月这些句柄在MS和GNU方言中处理完整的C ++ 17)使用这种技术。 它们已被用于处理数百万行大型C和C ++系统,完整,精确地parsing生成AST,并提供源代码的完整细节。 (请参阅AST for C ++最令人头疼的parsing。 )

问题从来没有像这样定义,而应该是有趣的:

C ++语法的最小修改是什么,这样就可以通过“非上下文无关”的yaccparsing器完全parsing这个新的语法? (只使用一个'hack':typename / identifier消歧,parsing器通知每个typedef / class / struct的词法分析器)

我看到几个:

  1. Type Type; 是禁止的。 声明为struct Type Type标识符不能成为非struct Type Type标识符(请注意, struct Type Type不是不明确的,仍然可以)。

    有三种types的names tokens

    • types :内buildtypes或由于typedef /类/结构
    • 模板function
    • 标识符:函数/方法和variables/对象

    考虑到模板函数作为不同的令牌解决了func< ambiguity。 如果func是模板函数名称,那么<必须是模板参数列表的开头,否则func是函数指针,而<是比较运算符。

  2. Type a(2); 是一个对象实例。 Type a();Type a(int)是函数原型。

  3. int (k); 是完全禁止的,应该写成int k;

  4. typedef int func_type();typedef int (func_type)(); 是禁止的。

    一个函数typedef必须是一个函数指针typedef: typedef int (*func_ptr_type)();

  5. 模板recursion被限制为1024,否则增加的最大值可以作为选项传递给编译器。

  6. int a,b,c[9],*d,(*f)(), (*g)()[9], h(char); 也可以被禁止,取而代之的是int a,b,c[9],*d; int (*f)();

    int (*g)()[9];

    int h(char);

    每个函数原型或函数指针声明一行。

    一个非常喜欢的替代方法是改变糟糕的函数指针语法,

    int (MyClass::*MethodPtr)(char*);

    被重新合成为:

    int (MyClass::*)(char*) MethodPtr;

    这与cast操作符(int (MyClass::*)(char*))

  7. typedef int type, *type_ptr; 也可能被禁止:每typedef一行。 因此,它会成为

    typedef int type;

    typedef int *type_ptr;

  8. sizeof intsizeof charsizeof long long和co。 可以在每个源文件中声明。 因此,每个使用inttypes的源文件都应该以

    #type int : signed_integer(4)

    unsigned_integer(4)将被禁止在#type指令之外,这将是很多C ++头文件中存在的愚蠢的sizeof int歧义sizeof int一大步

如果遇到使用模糊语法的C ++源代码,实现C ++语言的编译器会将source.cpp也移到ambiguous_syntax文件夹中,并在编译之前自动创build一个明确的翻译源代码。

如果你知道一些,请添加你模糊的C ++语法!

正如你在我的答案中可以看到的那样,C ++包含的语法不能由LL或LRparsing器确定性地parsing,因为typesparsing阶段(通常是parsing后)改变了操作顺序 ,因此AST的基本形状通常预期由第一阶段parsing提供)。

我觉得你很接近答案。

LR(1)意味着从左到右的parsing仅需要一个令牌来预测上下文,而LR(∞)则意味着无限的先行。 也就是说,parsing器必须知道所有即将到来的东西,以便找出它现在的位置。