问题标签 [recursive-descent]

我正在为 C++ 中的 SQL select 语句编写（手写）递归下降解析器，我需要知道我创建的解析树是否正确。我想检查一下，但我没有得到很好的 sql 解析树来源。我的方法是 - 为每个产品编写一个函数，并在该函数中将结果添加到根树中。谁能帮我？提前致谢。

我目前正在上系统软件开发课程。我们正在为虚构机器的汇编语言编写两遍汇编程序。我们已经实现了标记器，我们需要抽象地表示这个程序的所有类——剩下的（除了在后面的阶段实现代码生成器）就是解析标记。这是我遇到一个主要问题的地方。我选择将其实现为递归下降解析器，因为这是我目前拥有的唯一技术……但我们不允许在语法错误时停止汇编。例如，如果用户给出了一个语法无效的加载字指令，我们将用 NOP 替换它。如果用户给出了错误的标签，我们将直接忽略它。如果用户将未知字符放在一行中，我们会丢弃它们。

一方面，这听起来很容易——但是，实现它会导致我打破（我理解的）递归下降解析器的重要规则之一。我的每个函数在调用另一个函数之前都会提取多个标记，因为我需要考虑所有可能的可修复语法错误。鉴于我无法停止组装，并且我必须有足够的关于我当前上下文的信息来智能地确定用户打算做什么，我必须在一个函数中处理很多事情。

这将程序从真正的递归下降解析器转变为更多的半有限状态机。我觉得我做得很糟糕，但我不确定如何实现这一点。有没有人有任何建议/想法？

顺便说一句 - 我不允许使用像 ANTLR 或任何其他解析器生成器这样的工具。

谢谢。

我目前正在尝试为编程语言编写一个（非常）小的解释器/编译器。我已经设置了语言的语法，现在我需要写下语言的语法。我打算使用 LL(1) 解析器，因为经过一番研究，它似乎是最容易使用的。

我是这个领域的新手，但根据我收集到的信息，强烈建议使用 BNF 或 EBNF 形式化语法。然而，似乎并非所有语法都适合使用 LL(1) 解析器来实现。因此，我想知道以 LL(1) 形式编写语法的正确（或推荐）方法是什么。

谢谢你的帮助，查理。

PS：我打算使用 Haskell 的 Parsec 库编写解析器。

编辑：另外，根据 SK 逻辑，Parsec 可以处理无限前瞻（LL(k) ？） - 但我想这个问题仍然代表这种类型的语法。

我知道词法分析器和解析器的典型配置，其中词法分析器读取源代码并生成标记，然后将其定向到解析器，解析器将它们用作其语法产生中的终端符号。在典型的递归下降解析器中，您首先调用一些表示起始非终结符的顶级函数，该函数调用其他函数并从词法分析器中逐个标记读取。

但是如果我在同一个词法分析器上需要两个不同的解析器怎么办？

我的意思是，他们都从同一个地方读取，因为我不想多次读取同一个源，即不允许多次传递，以避免在词法分析器中进行不必要的重复工作。我只希望当序列中的下一个标记刚刚生成时，两个解析器同时使用它。

但是我只能在这些解析器之一中调用一个顶级函数；不能同时调用两者：/

有没有办法以某种步进模式运行这些解析器？也就是说，当我有一个新的标记时，我想将它一个接一个地传递给两个解析器，但只是将它们推进那个标记，尽可能地更新它们的内部状态和数据结构，然后立即返回等待另一个令牌。

我以前从未见过任何这种配置。是否有可能以这种方式构建解析器？是否有一些关于如何在代码中构造这种解析器的材料？它有名字吗？

编辑 1： 我不想使用任何解析器生成器工具，而是自己编写代码，因为我想了解这种东西在内部是​​如何工作的。

我有一个带有导航的表，它使用 ParentId 重新连接它自己。我正在尝试计算每条记录有多少后代，我知道我需要在递归中增加一个计数器，我只是不知道该怎么做！

任何帮助将不胜感激！

编辑添加级别并以递归方式递增：

关于如何编写递归下降解析器，我有两个问题：

第一个是当你有一个非终结符可以匹配几个不同的非终结符之一时怎么办？你如何检查哪种方式是正确的？

其次，如何构建 AST？使用 YACC，我可以只编写一段代码来为非终结符的每个实例执行，它具有引用规则“值”的特殊变量。你如何在递归下降解析器中做类似的事情？

我正在尝试在 PHP 中为以下 EBNF 编写递归下降解析器：

我按照我看到的类似问题推荐的本指南进行操作。（发帖前我搜索过）

在大多数情况下，我知道它是如何工作的并且我理解语法。我认为问题出在我的语法之内。我是 PHP 新手，所以我一直在参考W3Schools。我目前的代码出现以下错误：

我试图查找此错误，但运气不佳。我阅读了一些关于人们输入错误参数的帖子，但我没有为该函数设置任何参数。我在这里缺少关于 PHP 的东西吗？

下面是我的代码，我认为逻辑是正确的，因为我基于语法的解析树。$input 将来自 HTML 页面上的表单框。当我发现 PHP4 没有内置 str_split 函数时，我还从另一篇文章中选择了它。

所以基本上我想知道是什么导致了这个错误，为什么我在创建这个解析器方面是正确的。

我感谢任何意见、建议、批评、水气球和西红柿。感谢您花时间阅读我的帖子。有一个美好的白天/夜晚。

我正在硬编码一个递归体面的解析器，主要是为了学习目的，我遇到了一些麻烦。

我将使用 CSS3 语法的简短摘录作为示例：

首先，我没有意识到它是andnamespace_prefix中的一个可选部分。这导致在输入输入时总是失败，因为它被盲目地考虑用于匹配生产的任何输入。type_selectoruniversaltype_selector*|*namespace_prefix

递归体面很简单，但我对它的理解是，在确定生产之前，我需要做很多（因为没有更好的词）探索性递归。所以我改变了我的作品的签名以返回布尔值。通过这种方式，我可以很容易地判断一个特定的制作是否成功。

我使用链表数据结构来支持任意前瞻，并且可以轻松地对该列表进行切片以尝试生成，然后如果生成不成功则返回我的起点。然而，在尝试制作时，我传递了可变状态，试图构建一个文档对象模型。这并没有真正奏效，因为我无法知道制作是否会成功。如果制作不成功，我需要以某种方式撤消所做的任何更改。

我的问题是这个。我应该使用抽象语法树作为中间表示然后从那里开始吗？这是您通常会做的事情来解决这个问题吗？因为问题似乎主要在于文档对象模型不是适合递归的树数据结构。

我有这个语法：

我部分地写了一个递归下降解析器：

但是我不知道在某些部分该怎么做，例如 expr 可以是左值的方式，其第一项可以是 expr。

对于许多建立在递归下降解析基础上的解析器生成器来说，左递归似乎是一个大问题。我正在寻找一个支持它的基于 PEG 的解析器生成器 - 使用任何语言。