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

我正在阅读解析器和解析器生成器,并在维基百科的LR解析页面中找到了这个语句:

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

为什么会这样？C++的哪个特定属性导致无法使用LR解析器进行解析？

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

1> Ira Baxter..：

---

LR解析器无法通过设计处理模糊的语法规则.(在20世纪70年代制定这些想法时,理论变得更容易了).

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

x * y ;

它有两个不同的解析:

它可以是y的声明,作为指向x的指针

它可以是x和y的乘法,从而丢掉了答案.

现在,您可能认为后者是愚蠢的,应该被忽略.大多数人会同意你的意见; 但是,有些情况下可能会产生副作用(例如,如果乘法过载).但这不是重点.问题的关键是有有两种不同的解析,因此程序可以根据如何表达不同的意思应该已经被解析.

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

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

有许多更复杂的情况(解析模板语法需要任意前瞻,而LALR(k)可以向前看大多数k个令牌),但只有一个反例才能击落纯 LR(或其他)解析.

大多数真正的C/C++解析器通过使用某种具有额外hack的确定性解析器来处理此示例:它们与符号表集合交织解析...以便在遇到"x"时,解析器知道x是否是类型是否可以在两个潜在的解析之间进行选择.但是执行此操作的解析器不是上下文无关的,并且LR解析器(纯粹的解析器等)(最多)是无上下文的.

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

如果你作弊足够,你可以使LR解析器适用于C和C++.海湾合作委员会成员做了一段时间,但放弃了手动编码解析,我认为因为他们想要更好的错误诊断.

还有另一种方法,它很好,干净,解析C和C++就好了,没有任何符号表hackery:GLR解析器.这些是完全无上下文解析器(具有有效的无限前瞻).GLR解析器只接受两个解析,产生一个"树"(实际上是一个主要是树状的有向非循环图),代表模糊解析.解析后的传递可以解决歧义.

我们在C++和C++前端使用这种技术来实现我们的DMS软件再造Tookit(截至2017年6月,它们处理MS和GNU方言中的完整C++ 17).它们已被用于处理数百万行大型C和C++系统,完整,精确的解析生成AST,并提供源代码的完整细节.(参见AST for C++最令人烦恼的解析.)

---

@altie当然没有人会使位移运算符重载以使其将大多数变量类型写入流中,对吧？

---

我的回答者已经发现C有同样的问题,我想你错过了.不,出于同样的原因,LR(1)无法对其进行解析.呃,你的意思是'y'可以是一个typedef？也许你的意思是'x'？这不会改变任何事情.

---

虽然'x*y'示例很有趣,但在C中也可能发生('y'可以是typedef或变量).但是C可以由LR(1)解析器解析,那么与C++的区别是什么？

---

我看着`x*y`并轻笑 - 很奇怪,很少有人会想到这样漂亮的小模糊.

---

Parse 2在C++中不一定是愚蠢的,因为*可以被覆盖以产生副作用.

---

问题是关于C和C++之间的区别 - 可以用LALR(1)和lexer hack(你描述的)来解析C,而看起来(从其他答案),即使对于C++也是如此.

---

@Blaisorblad:你没有太多选择.如果您的解析器接受"太少",您可能会拒绝真正的程序.除非您的解析器具有图灵功能,否则您无法使解析器接受*确切*一个有效的字符串.因此,您构建了一个上下文无关的解析器,它接受了太多,并且破坏了它接受的多余内容.

2> Rob Walker..：

---

Lambda the Ultimate上有一个有趣的线程,讨论了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));

(以逗号分隔的表达式).

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

---

在本页面上对页面147进行一些总结会很酷.我打算读那个页面.(1)

---

例子是:int(x),y​​,*const z; //意思是:int x; int y; int*const z; (一系列声明)int(x),y​​,new int; //含义:(int(x)),(y),(new int)); (以逗号分隔的表达式)两个标记序列具有相同的初始子序列但具有不同的分析树,这取决于最后一个元素.在消除歧义之前可以有任意多个令牌.

---

那么,在那种情况下,∞意味着"任意多",因为前瞻总是受输入长度的限制.

3> reuns..：

---

问题永远不会像这样定义,而应该是有趣的:

什么是修改的最小设置为C++的语法让这个新的语法可以通过"非上下文无关"的yacc解析器解析完美,这将是必要的吗？(仅使用一个'hack':typename/identifier disambiguation,解析器通知每个typedef/class/struct的词法分析器)

我看到几个:

Type Type;禁止.声明为typename的标识符不能成为非类型名称标识符(请注意,这struct Type Type不是模糊的,可能仍然允许).

有3种类型names tokens:

types :builtin-type或者因为typedef/class/struct

模板功能

标识符:函数/方法和变量/对象

将模板函数视为不同的标记可以解决func<模糊问题.如果func是模板函数名称,则<必须是模板参数列表的开头,否则func是函数指针并且<是比较运算符.

Type a(2);是一个对象实例化. Type a();并且Type a(int)是功能原型.

int (k); 是完全禁止的,应该写 int k;

typedef int func_type(); 并被 typedef int (func_type)();禁止.

函数typedef必须是函数指针typedef: typedef int (*func_ptr_type)();

模板递归限制为1024,否则增加的最大值可以作为选项传递给编译器.

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一行.因此它会成为

typedef int type;

typedef int *type_ptr;

sizeof int,sizeof char,sizeof long long和合作.可以在每个源文件中声明.因此,使用该类型的每个源文件int都应该以

#type int : signed_integer(4)

并且unsigned_integer(4)会被禁止在该#type 指令之外,这将是sizeof int这么多C++标题中存在的愚蠢歧义的重要一步

如果遇到使用模糊语法的C++源代码,那么实现resyntaxed C++的编译器会移动source.cpp一个ambiguous_syntax文件夹,并source.cpp在编译之前自动创建一个明确的翻译.

如果您了解一些,请添加模糊的C++语法!

---

C++太过根深蒂固了.在实践中没有人会这样做.构建前端的那些人(比如我们)只是咬紧牙关并进行工程设计以使解析器工作.并且,只要该语言中存在模板,您就不会获得纯粹的无上下文解析器.

4> Sam Harwell..：

---

正如您在此处的答案中所看到的,C++包含的语法无法通过LL或LR解析器进行确定性解析,因为类型解析阶段(通常是后解析)会更改操作的顺序,因此也会导致AST的基本形状(通常预期由第一阶段解析提供).

---

处理歧义的解析技术只会在解析时生成*两个*AST变体,并根据类型信息简单地消除不正确的变体.

5> casademora..：

---

我认为你非常接近答案.

LR(1)意味着从左到右的解析只需要一个令牌来预测上下文,而LR(∞)意味着无限的前瞻.也就是说,解析器必须知道即将发生的所有事情,以便找出它现在的位置.

---

不,n和无穷大之间存在无法通行的山峰.

---

实际上,通过我对模式LR(n) - > LR(1)的模糊*回忆,它涉及创建新的中间状态,因此运行时是'n'的一些非常数函数.翻译LR(inf) - > LR(1)将花费无限时间.

---

"不是答案:是的,给予无限的时间？" - 否:短语"给予无限的时间"只是一种非感性的,简短的说法"无论在任何有限的时间内都无法完成".当你看到"无限"时,想一想:"不是有限的".

---

我记得我的编译器类中n> 0的LR(n)在数学上可以简化为LR(1).对于n =无穷大,这是不是真的？

---

不是答案:是的,给予无限的时间？:)