157

我正在阅读解析器和解析器生成器，并在维基百科的 LR parsing -page 中找到了这个语句：

可以使用 LR 解析器的某些变体来解析许多编程语言。一个值得注意的例外是 C++。

为什么会这样？C++ 的哪些特殊属性导致无法使用 LR 解析器进行解析？

使用google，我只发现可以用LR（1）完美解析C，但C ++需要LR（∞）。

4

6 回答 6

241

LR 解析器在设计上无法处理模棱两可的语法规则。（早在 1970 年代，当想法被制定出来时，这个理论就变得更容易了）。

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

x * y ;

它有两种不同的解析：

  1. 它可以是 y 的声明，作为指向类型 x 的指针
  2. 它可以是 x 和 y 的乘积，丢弃答案。

现在，您可能会认为后者是愚蠢的，应该被忽略。大多数人会同意你的看法；但是，在某些情况下它可能会产生副作用（例如，如果乘法重载）。但这不是重点。关键是有两种不同的解析，因此一个程序可能意味着不同的东西，这取决于它应该如何被解析。

编译器必须在适当的情况下接受适当的一个，并且在没有任何其他信息（例如，x 的类型的知识）的情况下必须收集两者以便决定以后做什么。因此，语法必须允许这一点。这使得语法模棱两可。

因此纯 LR 解析无法处理这个问题。许多其他广泛可用的解析器生成器，例如 Antlr、JavaCC、YACC 或传统的 Bison，甚至 PEG 样式的解析器，也不能以“纯”方式使用。

还有很多更复杂的情况（解析模板语法需要任意前瞻，而 LALR(k) 最多可以前瞻 k 个标记），但只需要一个反例就可以击倒纯LR（或其他）解析。

大多数真正的 C/C++ 解析器通过使用某种确定性解析器和一个额外的技巧来处理这个示例：它们将解析与符号表集合交织在一起......所以当遇到“x”时，解析器知道 x 是否是一个类型或不，因此可以在两个潜在的解析之间进行选择。但是执行此操作的解析器不是上下文无关的，而 LR 解析器（纯解析器等）（充其量）是上下文无关的。

可以作弊，并在 LR 解析器中添加按规则缩减时间的语义检查来消除歧义。（此代码通常并不简单）。大多数其他解析器类型都有一些方法可以在解析的各个点添加语义检查，可以用来执行此操作。

如果你作弊得够多，你可以让 LR 解析器为 C 和 C++ 工作。GCC 家伙做了一段时间，但放弃了手动编码解析，我认为是因为他们想要更好的错误诊断。

不过，还有另一种方法，它既漂亮又干净，并且可以很好地解析 C 和 C++，而无需任何符号表骇客：GLR 解析器。这些是完全无上下文的解析器（具有有效的无限前瞻）。GLR 解析器简单地接受这两种解析，产生一个表示模糊解析的“树”（实际上是一个主要类似于树的有向无环图）。解析后传递可以解决歧义。

我们在 DMS Software Reengineering Tookit 的 C 和 C++ 前端使用了这种技术（截至 2017 年 6 月，这些工具在 MS 和 GNU 方言中处理完整的 C++17）。它们已被用于处理数百万行大型 C 和 C++ 系统，通过完整、精确的解析生成具有完整源代码详细信息的 AST。（请参阅AST 了解 C++ 最令人头疼的解析。）

于 2009-06-17T02:01:10.477 回答
96

Lambda the Ultimate上有一个有趣的线程，讨论了C++ 的 LALR 语法。

它包括一个博士论文的链接，其中包括对 C++ 解析的讨论，其中指出：

“C++ 语法是模棱两可的，依赖于上下文的，并且可能需要无限前瞻来解决一些歧义”。

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

例子是：

int(x), y, *const z;

意义

int x;
int y;
int *const z;

相比于：

int(x), y, new int;

意义

(int(x)), (y), (new int));

（逗号分隔的表达式）。

这两个标记序列具有相同的初始子序列，但解析树不同，这取决于最后一个元素。在消除歧义之前可以有任意多个标记。

于 2008-10-28T14:01:47.253 回答
15

这个问题从来没有像这样定义，而它应该很有趣：

为了让“非上下文无关”的 yacc 解析器能够完美解析这个新语法，对 C++ 语法进行的最小修改是什么？（仅使用一个“hack”：类型名/标识符消歧，解析器通知每个 typedef/class/struct 的词法分析器）

我看到几个：

  1. Type Type;禁止。声明为类型名的标识符不能成为非类型名标识符（请注意，这struct Type Type不是模棱两可的，仍然可以允许）。

    有 3 种类型names tokens：

    • types: 内置类型或由于 typedef/class/struct
    • 模板函数
    • 标识符：函数/方法和变量/对象

    将模板函数视为不同的标记解决了func<歧义。如果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. 模板递归限制为 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;

    这与演员表操作员一致 (int (MyClass::*)(char*))

  7. typedef int type, *type_ptr; 也可能被禁止：每个 typedef 一行。这样就会变成

    typedef int type;

    typedef int *type_ptr;

  8. sizeof int, sizeof char,sizeof long long和公司。可以在每个源文件中声明。因此，每个使用该类型的源文件int都应该以

    #type int : signed_integer(4)

    并且unsigned_integer(4)在该指令之外将被禁止，这将是向许多 C++ 头文件中存在#type 的愚蠢歧义迈出的一大步sizeof int

如果遇到使用歧义语法的 C++ 源代码，实现重新语法化的 C++ 的编译器将移动source.cpp一个ambiguous_syntax文件夹，并source.cpp在编译之前自动创建一个明确的翻译。

如果您知道一些，请添加您的模棱两可的 C++ 语法！

于 2013-02-13T11:37:38.247 回答
9

正如您在我的回答中看到的，C++ 包含无法由 LL 或 LR 解析器确定性解析的语法，因为类型解析阶段（通常是解析后）改变了操作的顺序，因此 AST 的基本形状（通常期望由第一阶段解析提供）。

于 2009-09-02T02:05:41.423 回答
6

我认为你非常接近答案。

LR(1) 意味着从左到右的解析只需要一个标记来预测上下文，而 LR(∞) 意味着无限的前瞻。也就是说，解析器必须知道即将到来的所有内容才能确定它现在在哪里。

于 2008-10-28T14:05:08.370 回答
5

C++ 中的“typedef”问题可以使用 LALR(1) 解析器进行解析，该解析器在解析时构建符号表（不是纯 LALR 解析器）。“模板”问题可能无法用这种方法解决。这种 LALR(1) 解析器的优点是语法（如下所示）是 LALR(1) 语法（没有歧义）。

/* C Typedef Solution. */

/* Terminal Declarations. */

   <identifier> => lookup();  /* Symbol table lookup. */

/* Rules. */

   Goal        -> [Declaration]... <eof>               +> goal_

   Declaration -> Type... VarList ';'                  +> decl_
               -> typedef Type... TypeVarList ';'      +> typedecl_

   VarList     -> Var /','...     
   TypeVarList -> TypeVar /','...

   Var         -> [Ptr]... Identifier 
   TypeVar     -> [Ptr]... TypeIdentifier                               

   Identifier     -> <identifier>       +> identifier_(1)      
   TypeIdentifier -> <identifier>      =+> typedefidentifier_(1,{typedef})

// The above line will assign {typedef} to the <identifier>,  
// because {typedef} is the second argument of the action typeidentifier_(). 
// This handles the context-sensitive feature of the C++ language.

   Ptr          -> '*'                  +> ptr_

   Type         -> char                 +> type_(1)
                -> int                  +> type_(1)
                -> short                +> type_(1)
                -> unsigned             +> type_(1)
                -> {typedef}            +> type_(1)

/* End Of Grammar. */

可以毫无问题地解析以下输入：

 typedef int x;
 x * y;

 typedef unsigned int uint, *uintptr;
 uint    a, b, c;
 uintptr p, q, r;

LRSTAR解析器生成器读取上述语法符号并生成一个解析器，该解析器可以处理“typedef”问题，而不会在解析树或 AST 中产生歧义。（披露：我是创建 LRSTAR 的人。）

于 2018-08-17T14:59:10.853 回答