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

2023-11-26

我正在阅读有关解析器和解析器生成器的内容,并在维基百科的 LR 解析页面中找到了此声明:

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

为什么会这样呢? C++ 的什么特殊属性导致它无法用 LR 解析器进行解析?

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


LR 解析器在设计上无法处理不明确的语法规则。 (在 20 世纪 70 年代,当这些想法被提出时,理论变得更容易了)。

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

x * y ;

它有两种不同的解析:

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

现在,您可能认为后者很愚蠢,应该被忽略。 大多数人都会同意你的观点;然而,在某些情况下可能会 有副作用(例如,如果乘法过载)。但这不是重点。 重点就在那里are两个不同的解析,因此是一个程序 可能意味着不同的事情,具体取决于它的方式should已被解析。

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

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

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

大多数真正的 C/C++ 解析器通过使用一些 一种具有额外技巧的确定性解析器:它们将解析与符号表交织在一起 集合...这样当遇到“x”时, 解析器知道 x 是否是类型,因此可以 在两个潜在的解析之间进行选择。但是一个解析器 这样做不是上下文无关的,LR 解析器 (纯粹的等)(充其量)是上下文无关的。

人们可以作弊,并在 LR 解析器来消除歧义。 (此代码通常并不简单)。大多数其他解析器类型 有一些方法可以在各个点添加语义检查 在解析中,可以用来做到这一点。

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

不过,还有另一种方法,既漂亮又干净 无需任何符号表即可很好地解析 C 和 C++ 黑客行为:GLR 解析器。 这些是完整的上下文无关解析器(实际上具有无限的 展望)。 GLR 解析器简单地接受both解析, 生成一棵“树”(实际上是一个主要类似于树的有向无环图) 这代表了不明确的解析。 后解析过程可以解决歧义。

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

本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)

为什么 C++ 不能用 LR(1) 解析器解析? 的相关文章

随机推荐