为什么 C++ 不能用 LR(1) 解析器解析?
-
04-07-2019 - |
题
我正在阅读有关解析器和解析器生成器的内容,并在维基百科的 LR 解析页面中找到了此声明:
许多编程语言都可以使用 LR 解析器的某些变体进行解析。一个值得注意的例外是 C++。
为什么会这样呢?C++ 的什么特殊属性导致它无法用 LR 解析器进行解析?
使用google,我只发现C可以用LR(1)完美解析,但C++需要LR(∞)。
解决方案
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));
(以逗号分隔的表达式)。
两个令牌序列具有相同的初始子序列但具有不同的解析树,这取决于最后一个元素。在消除歧义之前,可以有任意多个令牌。
其他提示
LR解析器无法通过设计处理模糊的语法规则。 (在20世纪70年代制定这些想法时,理论变得更容易了。)
C和C ++都允许以下语句:
x * y ;
它有两种不同的解析:
- 它可以是y的声明,作为指向x 的指针
- 它可以是x和y的乘法,丢掉了答案。 醇>
现在,您可能认为后者是愚蠢的,应该被忽略。 大多数人会同意你的意见;但是,有些情况可能会发生 有副作用(例如,如果乘法过载)。但这不是重点。 关键是是两个不同的解析,因此是一个程序 可能意味着不同的东西取决于应该如何解析。
编译器必须在适当的情况下接受适当的信息,并且在没有任何其他信息(例如,x的类型的知识)的情况下必须收集两者以便稍后决定做什么。因此语法必须允许这样。这使得语法含糊不清。
因此纯LR解析无法处理此问题。许多其他广泛可用的解析器生成器,例如Antlr,JavaCC,YACC或传统Bison,甚至PEG样式解析器,也不能用于<!>“pure <!>”;方式。
有许多更复杂的情况(解析模板语法需要任意前瞻,而LALR(k)可以向前看大多数k代币),但只有一个反例才能击落纯 LR(或其他)解析。
大多数真正的C / C ++解析器通过使用一些来处理这个例子 一种具有额外黑客攻击的确定性解析器:它们与符号表交织解析 集合...所以到时间<!>“x <!>”;遇到了, 解析器知道x是否是类型,因此可以 在两个潜在的解析之间做出选择。但解析器 这不是上下文,LR解析器 (纯粹的等等)(最好)没有上下文。
可以作弊,并添加每个规则缩减时间语义检查 到LR解析器做消除歧义。 (这段代码通常不简单)。大多数其他解析器类型 有一些方法可以在各个点添加语义检查 在解析中,可以用来做到这一点。
如果你作弊足够,你可以让LR解析器工作 C和C ++。海湾合作委员会的人做了一段时间,但给了它 手动编码解析,我认为因为他们想要 更好的错误诊断。
然而,还有另一种方法,它既干净又干净 并且在没有任何符号表的情况下解析C和C ++就好了 hackery: GLR解析器。 这些是完全无上下文解析器(实际上是无限的 展望)。 GLR解析器只接受两个解析, 产生<!>“树<!>”; (实际上是一个主要是树状的有向无环图) 这代表了模棱两可的解析。 解析后的传递可以解决歧义。
我们在C和C ++前端使用这种技术 DMS Software Reengineering Tookit(截至2017年6月 这些处理MS和GNU方言中的完整C ++ 17)。 它们已被用于处理数百万行 大型C和C ++系统,具有完整,精确的解析,生成具有完整源代码细节的AST。 (请参阅 AST for C ++最令人烦恼的解析。)
问题从来没有像这样定义过,但它应该很有趣:
为了让“非上下文无关”yacc 解析器可以完美地解析这个新语法,对 C++ 语法进行的最小修改集是什么?(仅使用一种“黑客”:类型名/标识符消歧,解析器通知词法分析器每个 typedef/类/结构)
我看到有几个:
Type Type;
是禁止的。声明为类型名的标识符不能成为非类型名标识符(请注意struct Type Type
是明确的,并且仍然可以被允许)。有3种类型
names tokens
:types
:内置类型或由于 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++ 源代码,实现重新语法的 C++ 的编译器将移动 source.cpp
太安 ambiguous_syntax
文件夹,并会自动创建一个明确的翻译 source.cpp
在编译之前。
如果您知道一些不明确的 C++ 语法,请添加!
正如您在我的在此处回答,C ++包含LL或LR解析器无法确定性解析的语法,因为类型解析阶段(通常是解析后)更改操作顺序,因此基本形状AST(通常预期由第一阶段解析提供)。
我认为你非常接近答案。
LR(1)意味着从左到右的解析只需要一个令牌来预测上下文,而LR(<!>#8734;)意味着无限前瞻。也就是说,解析器必须知道即将发生的所有事情,以便找出它现在的位置。
<!> quot; typedef <!> quot; C ++中的问题可以使用LALR(1)解析器进行解析,该解析器在解析时构建符号表(不是纯LALR解析器)。 <!>“模板<!>”;用这种方法可能无法解决问题。这种LALR(1)解析器的优点是语法(如下所示)是LALR(1)语法(没有歧义)。
/* C Typedef Solution. */
/* Terminal Declarations. */
<identifier> => lookup(); /* Symbol table lookup. */
/* Rules. */
Goal -> [Declaration]... <eof> +> goal_
Declaration -> Type... VarList ';' +> decl_
-> typedef Type... TypeVarList ';' +> typedecl_
VarList -> Var /','...
TypeVarList -> TypeVar /','...
Var -> [Ptr]... Identifier
TypeVar -> [Ptr]... TypeIdentifier
Identifier -> <identifier> +> identifier_(1)
TypeIdentifier -> <identifier> =+> typedefidentifier_(1,{typedef})
// The above line will assign {typedef} to the <identifier>,
// because {typedef} is the second argument of the action typeidentifier_().
// This handles the context-sensitive feature of the C++ language.
Ptr -> '*' +> ptr_
Type -> char +> type_(1)
-> int +> type_(1)
-> short +> type_(1)
-> unsigned +> type_(1)
-> {typedef} +> type_(1)
/* End Of Grammar. */
可以毫无问题地解析以下输入:
typedef int x;
x * y;
typedef unsigned int uint, *uintptr;
uint a, b, c;
uintptr p, q, r;
LRSTAR解析器生成器读取上述语法表示法并生成一个解析器,用于处理<!> quot; typedef < !> QUOT;在解析树或AST中没有歧义的问题。 (披露:我是创建LRSTAR的人。)