为什么 C + + 不能用 LR (1)解析器解析？

我在阅读有关解析器和解析器生成器的文章时，在维基百科的 LR 解析页面上发现了这样一句话:

许多编程语言可以使用 LR 解析器的一些变体进行解析。

为什么会这样? C + + 的什么特殊属性使得它不能用 LR 解析器进行解析？

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

33504 次浏览
小开
最佳答案

在 终极 Lambda上有一个有趣的线程讨论了 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));

(逗号分隔的表达式)。

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

小开

我觉得你已经很接近答案了。

LR (1)意味着从左到右的解析只需要一个标记来向前查找上下文，而 LR (& infin;)意味着无限的向前查找。也就是说，解析器必须知道将要发生的所有事情，以便找出它现在的位置。

小开

LR 解析器在设计上无法处理二义性文法规则。(早在20世纪70年代，当这些想法正在形成的时候，这个理论就变得更容易了)。

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 + + 。海湾合作委员会的人做了一段时间，但给了它 我想是因为他们想要 更好的错误诊断。

不过还有另一种方法，干净利落 不用任何符号表就可以很好地解析 C 和 C + + 黑客: GLR 解析器。 这些都是完全上下文无关解析器(实际上具有无限 GLR 解析器只接受 都有解析, 产生一棵“树”(实际上是一棵大部分像树的有向无环图) 表示模糊解析的。 解析后传递可以解决歧义。

我们在我们的 C 和 C + + 前端使用这种技术 DMS 软件再造工具包(截至2017年6月) 用 MS 和 GNU 方言处理完整的 C + + 17)。 它们已经被用来处理数百万条线路 大型 C 和 C + + 系统，具有完整、精确的解析器，生成具有完整源代码细节的 AST。(见 用于 C + + 最令人烦恼的解析的 AST。)

小开

正如您在我的 回答我中看到的，C + + 包含的语法不能被 LL 或 LR 解析器确定性地解析，因为类型解析阶段(通常是解析后)改变了 行动次序，因此改变了 AST 的基本形状(通常预期由第一阶段解析提供)。

小开

问题从来不是这样定义的，而应该是有趣的:

为了使“非上下文无关的”yacc 解析器能够完美地解析这种新语法，需要对 C + + 语法进行哪些最小的修改？(只使用一个‘ hack’: 类型名/标识符消歧，解析器通知 lexer 每个 typedef/class/struct)

我看到了几个:

  1. Type Type;是禁止的。声明为类型名的标识符不能成为非类型名标识符(请注意，struct Type Type不是模棱两可的，仍然可以使用)。

    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)将被禁止，以外的 #type指令 这将是向许多 C + + 标题

    9. 中出现的愚蠢的 sizeof int歧义迈出的一大步

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

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

小开

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 的人。)


提交答案