LR 解析器在设计上无法处理不明确的语法规则。 (在 20 世纪 70 年代,当这些想法被提出时,理论变得更容易了)。
C 和 C++ 都允许以下语句:
x * y ;
它有两种不同的解析:
- 它可以是 y 的声明,作为指向 x 类型的指针
- 它可以是 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。)