首页
学习
活动
专区
工具
TVP
发布
社区首页 >问答首页 >为什么不能用LR(1)解析器解析C++?

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

Stack Overflow用户
提问于 2008-10-28 13:49:52
回答 6查看 31.9K关注 0票数 157

我在阅读有关解析器和解析器生成器的文章时,在维基百科的LR解析-page中找到了这句话:

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

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

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

EN

回答 6

Stack Overflow用户

回答已采纳

发布于 2008-10-28 14:01:47

Lambda the Ultimate上有一个讨论LALR grammar for C++的有趣的帖子。

它包含一个指向PhD thesis的链接,其中包含对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));

(逗号分隔的表达式)。

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

票数 96
EN

Stack Overflow用户

发布于 2009-06-17 02:01:10

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

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

x * y ;

它有两种不同的解析:

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

现在,你可能会认为后者是愚蠢的,应该被忽略。大多数人会同意你的观点;然而,在某些情况下,它可能会有副作用(例如,如果multiply是重载的)。但这不是重点。关键是有两个不同的解析,因此一个程序可以有不同的含义,这取决于它应该如何被解析。

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

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

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

大多数真正的C/C++解析器通过使用某种确定性解析器来处理这个示例:它们将解析与符号表集合交织在一起……这样,当遇到"x“时,解析器就知道x是否是一个类型,因此可以在两个可能的解析之间进行选择。但是这样做的解析器不是上下文无关的,LR解析器(纯解析器,等等)(充其量)是上下文无关的。

人们可以作弊,并在to LR解析器中添加每个规则的缩减时间语义检查来进行这种消歧。(此代码通常并不简单)。大多数其他解析器类型都有一些方法,可以在解析过程中的不同点添加语义检查,这可以用来实现这一点。

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

不过,还有另一种方法:GLR parsers,它很好、很干净,可以很好地解析C和C++,而不需要任何符号表的麻烦。这些是完全上下文无关的解析器(具有有效的无限先行)。GLR解析器简单地接受这两种解析,生成一个“树”(实际上是一个主要类似于树的有向无环图)来表示不明确的解析。解析后传递可以解决多义性。

我们在我们的DMS软件再工程工具包的C和C++前端中使用了这项技术(从2017年6月起,这些工具包可以处理MS和GNU语中的完整C++17 )。它们已经被用于处理数以百万计的大型C和C++系统,通过完整、精确的语法分析生成具有完整源代码细节的AST。(参见the AST for C++'s most vexing parse.)

票数 241
EN

Stack Overflow用户

发布于 2013-02-13 19:37:38

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

为了让“非上下文无关”的C++解析器能够完美地解析这个新语法,需要对yacc语法进行最小限度的修改。(只使用了一个“hack”:typename/identifier消歧,解析器通知词法分析器每个类型定义/类/结构)

我看到了几个:

禁止使用

  1. Type Type;。声明为typename的标识符不能成为非typename标识符(请注意,struct Type Type不是模棱两可的,并且仍然可以被允许)。

names tokens有三种类型:

- `types` : builtin-type or because of a typedef/class/struct
- template-functions
- identifiers : functions/methods and variables/objects

将模板函数看作不同的标记,解决了func<的歧义问题。如果func是模板函数名,则<必须是模板参数列表的开头,否则func是函数指针,<是比较运算符。

  1. Type a(2);是一个对象实例化。prototypes.
  2. int (k);是完全禁止的函数,Type a();Type a(int)是完全禁止的,应该写int k;
  3. typedef int func_type();typedef int (func_type)();是禁止的。

函数类型定义函数必须是函数指针类型定义定义:typedef int (*func_ptr_type)();

  • template递归限制为1024,否则增加的最大值可能会作为选项传递给compiler.

  • 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*))

  • typedef int type, *type_ptr;是一致的,也可能被禁止:每个类型定义符占一行。因此,它将成为

typedef int type;

typedef int *type_ptr;

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

#type int : signed_integer(4)

并且unsigned_integer(4)将被禁止在该#type指令之外,这将是迈向愚蠢的sizeof int歧义的一大步,该歧义存在于如此多的C++ headers中

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

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

票数 15
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/243383

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档