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

2023-11-26

我正在阅读有关解析器和解析器生成器的内容,并在维基百科的 LR 解析页面中找到了此声明:

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

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

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


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

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

x * y ;

它有两种不同的解析:

  1. 它可以是 y 的声明,作为指向 x 类型的指针
  2. 它可以是 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。)

本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)

为什么 C++ 不能用 LR(1) 解析器解析? 的相关文章

  • MVC 重定向到没有控制器的视图

    希望应该是一个简单的 我创建了一个通用错误视图 当整个站点的操作方法内发生异常时 我想显示该视图 我创建了一个部分页面 所有导航都位于其中 因此我不需要在此视图上使用控制器 那么如何从控制器内的操作方法重定向到它 像这样的东西 HttpPo
  • 必须打开存储才能执行此操作 - System.IO.Packaging.Package

    我正在使用 System IO Packaing Package 类来压缩文件 我的应用程序的多个实例可以同时运行 并读取和保存文件 当处理小文件时 一切似乎都很好 但是当涉及大文件时 如果应用程序的两个实例同时保存 我会收到一个异常 消息
  • 切换图片框可见性 C#

    为什么图片框控件的可见性属性在这里不起作用 我最初将它们设置为 false 以便在屏幕加载时它们不可见 但后来我想切换这个 我已完成以下操作 但似乎不起作用 这是一个 Windows 窗体应用程序 private void Action w
  • WebClient读取错误页面的内容

    我有一个加载页面内容的应用程序 我使用 WebClient 类 即使服务器返回 404 500 等错误 我也需要检索内容 我需要这样的东西 WebClient wc new WebClient string pageContent try
  • 为什么派生类不使用基类的operator=(赋值运算符)?

    以下是实际问题的简化版本 而不是打电话Base operator int 代码似乎生成了一个临时的Derived对象并复制它 既然函数签名似乎完美匹配 为什么不使用基本赋值运算符 这个简化的示例没有显示任何不良影响 但原始代码在析构函数中有
  • 返回 int& 的函数[重复]

    这个问题在这里已经有答案了 我在网上查了一下发现一篇试图解释的文章std move和右值 http thbecker net articles rvalue references section 01 html并发现了一些我实在无法掌握的东
  • C# 中附加/分离事件处理程序的不同方式有什么区别

    我的问题有两个部分 首先 我们可以通过以下两种方式附加事件处理程序 myObject MyEvent new EventHandler MyHandler myObject MyEvent MyHandler 据我了解 这两者是等价的 在第
  • 将 C# 反射代码移植到 Metro-Ui

    我正在尝试移植使用反射的现有 C 类 通用工厂 但我无法编译这段代码 Type types Assembly GetAssembly typeof TProduct GetTypes foreach Type type in types i
  • F10键没被抓住

    I have a Windows Form and there overriden ProcessCmdKey However this works with all of the F Keys except for F10 I am tr
  • .net Framework (.net 4.0) 中定义 Base 3 数字的类

    我正在寻找一些可以用来定义 3 基数 三进制数 的类 有什么我可以在 net 框架中使用的东西或者我需要写一些东西吗 谢谢你的帮助 您可以使用解析Convert ToInt32 s base http msdn microsoft com
  • 用 C# 制作 Vista 风格的应用程序

    我正在运行 Windows Vista 并且希望外观看起来像常规 Vista 程序 有没有关于如何构建 Vista 风格应用程序的真正好的教程 文章 我还想学习如何使用本机代码并将其转换为 C 如this http bartdesmet n
  • 导出到 CSV 时 Gridview 出现空行

    这个问题是由进一步讨论引发的这个问题 https stackoverflow com questions 6674555 export gridview data into csv file 6674589 noredirect 1 com
  • 抽象类或接口。哪种方式是正确的?

    有两种方法可以选择抽象类或接口 微软解决方案和Oracle解决方案 微软 设计指南 请使用抽象 在 Visual Basic 中为 MustInherit 类而不是接口来将协定与实现分离 http msdn microsoft com en
  • 在“using”语句中使用各种类型 (C#)

    自从C usingstatements只是try finally dispose 的语法糖 为什么它接受多个对象仅当它们属于同一类型时 我不明白 因为它们需要的只是 IDisposable 如果它们都实现 IDisposable 应该没问题
  • 线程安全的 C++ 堆栈

    我是 C 新手 正在编写一个多线程应用程序 不同的编写者将对象推入堆栈 读者将它们从堆栈中拉出 或至少将指针推入对象 C 中是否有任何内置结构可以在不添加锁定代码等的情况下处理此问题 如果没有 那么 Boost 库呢 EDIT 你好 感谢您
  • C++ 标准中短语“构造函数没有名称”的含义

    在尝试理解 C 标准中的 构造函数没有名称 这句话时 我似乎在 clang 中发现了一个错误 有人可以证实这一点吗 VS2015 and gcc rejects this code and I think they it are is co
  • 程序退出后,TcpListener Socket 仍处于活动状态

    当我的程序退出时 我试图停止 TCP 侦听器 我不关心套接字或任何活动客户端套接字上当前活动的任何数据 套接字清理代码本质上是 try myServer Server Shutdown SocketShutdown Both catch E
  • 在何处将 CFLAG(例如 -std=gnu99)添加到 (Eclipse CDT) 自动工具项目中

    我有一个简单的 Autotools C 项目 不是 C 其框架是由 Eclipse CDT Juno 为我创建的 CFLAG 通过检查 似乎是 g O2 我希望所有生成的 make 文件也具有 std gnu99附加到 CFLAG 因为我使
  • 将文本从文本文件添加到 PDF 文件[重复]

    这个问题在这里已经有答案了 这是我的代码 using FileStream msReport new FileStream pdfPath FileMode Create step 1 using Document pdfDoc new D
  • 搜索引擎如何找到相关内容? [关闭]

    Closed 这个问题正在寻求书籍 工具 软件库等的推荐 不满足堆栈溢出指南 help closed questions 目前不接受答案 Google 在解析网络时如何找到相关内容 例如 Google 使用 PHP 原生 DOM 库来解析内

随机推荐