我在阅读有关解析器和解析器生成器的文章时,在维基百科的LR解析-page中找到了这句话:
许多编程语言都可以使用LR解析器的某些变体进行解析。一个值得注意的例外是C++。
为甚麽呢?C++的什么特殊属性导致它无法使用LR解析器进行解析?
使用谷歌,我只发现C可以完美地解析为LR(1),但C++需要LR(∞)。
发布于 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));
(逗号分隔的表达式)。
这两个令牌序列具有相同的初始子序列,但不同的解析树依赖于最后一个元素。在消除歧义的标记之前可以有任意多个标记。
发布于 2009-06-17 02:01:10
LR解析器在设计上不能处理歧义的语法规则。(在20世纪70年代,当想法被提出时,理论变得更容易了)。
C和C++都允许使用以下语句:
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.)
发布于 2013-02-13 19:37:38
问题从来不是这样定义的,而它应该是有趣的:
为了让“非上下文无关”的C++解析器能够完美地解析这个新语法,需要对yacc语法进行最小限度的修改。(只使用了一个“hack”:typename/identifier消歧,解析器通知词法分析器每个类型定义/类/结构)
我看到了几个:
禁止使用
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
是函数指针,<
是比较运算符。
Type a(2);
是一个对象实例化。prototypes.int (k);
是完全禁止的函数,Type a();
和Type a(int)
是完全禁止的,应该写int k;
typedef int func_type();
和typedef int (func_type)();
是禁止的。函数类型定义函数必须是函数指针类型定义定义:typedef int (*func_ptr_type)();
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 int
,sizeof char
,sizeof 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++语法!
https://stackoverflow.com/questions/243383
复制相似问题