问题标签 [recursive-descent]

这是我正在使用的已解析 xml 文件的示例，该文件将其标记为树形

我希望这个输入不难理解。以下是不从 XML 文件解析时的正常外观：

ETC...

所有的赋值对（即一个值和一个变量）都将存储在一个 hashmap 中，以便该值可以通过它的变量查找并在以后的表达式中使用。我将使用递归下降评估器（我认为？）根据语法解决表达式。

在过去的 24 小时里，我在谷歌上搜索了各种各样的东西，并且已经看到了很多用于基本算术的树评估器（例如 2 + 3 * 8 等），但我无法看到它对我的具体情况有何影响树。

到目前为止，我编写的代码低至查找变量名称（a、b、c、d、e 等），但我无法开始考虑如何编写递归代码，这将为哈希图。

我的树的文档、节点和节点列表类是不寻常的，因为它们不允许使用我认为可以节省大量时间的“getChild”方法。有人知道这是为什么吗？

这里真的是随机问题，我希望它有意义。请让我详细说明任何不清楚的地方，我会尽力而为。我不是在寻找任何人来为我解决问题，而只是指导我如何决定如何编写这个递归算法。

编辑：另外，我在上面输入的第二个“输入”实际上是输出。应该是这样的：

我正在为我正在学习的编译器设计课程编写编译器，我目前正在语法分析中，我需要编写一个解析器。

我需要设置 FIRST 和 FOLLOW 来处理源文本中可能出现的任何错误。我已经为我的语法中的所有非终结符预先计算了 FIRST 和 FOLLOW 集，但是我无法决定我应该在程序中实际编码它们的位置。

我应该将它们放在关键是非终端名称的地图中吗？

任何意见将是有益的

这篇文章可能看起来有点不清楚，如果需要，我可以澄清任何问题。

这是我问过的上一个问题How to encode FIRST & FOLLOW sets inside a compiler的后续问题，但这个问题更多的是关于我的程序的设计。

我正在通过编写递归下降解析器来实现编译器的语法分析阶段。我需要能够利用 FIRST 和 FOLLOW 集，以便更有效地处理源程序语法中的错误。我已经为我的所有非终端计算了 FIRST 和 FOLLOW，但是我无法决定将它们逻辑地放置在我的程序中的哪个位置以及这样做的最佳数据结构是什么。

注意：所有代码都是伪代码

选项 1) 使用映射，并将所有非终端按其名称映射到包含其 FIRST 和 FOLLOW 集的两个集合：

这似乎是一个可行的选择，但是在我的解析器内部，我需要像这样的丑陋代码来检索 FIRST 和 FOLLOW 并传递给错误函数：

选项 2) 为每个非终端创建一个类并具有 FIRST 和 FOLLOW 属性：

这导致代码看起来更好一点：

这是我想到的两个选项，我很想听听任何其他关于如何编码这两个集合的建议，以及对我发布的两种方式的任何批评和补充都会有所帮助。谢谢

我也在这里发布了这个问题：http: //www.coderanch.com/t/570697/java/java/Encode-FIRST-FOLLOW-sets-recursive

我正在寻找编写一些递归下降解析器的伪代码。现在，我对这种类型的编码没有经验。我在网上阅读了一些示例，但它们仅适用于使用数学表达式的语法。这是我基于解析器的语法。

我必须编写方法S()，L()并E()返回一些错误消息，但是我在网上找到的教程并没有太大帮助。谁能指出我正确的方向并给我一些例子？

我想用 C# 或 Java 语法编写它，因为它更容易联系起来。

更新

我想为算术表达式创建一个明确的语法。现在求幂应该具有更高的优先级并与右侧相关联。所有其他操作都关联到左侧。这是我到目前为止所拥有的，但我不知道求幂是否正确

这一直在我的脑海里。我对递归下降解析器很感兴趣，并且想知道如何实现它。我想要的是一个简单的解析器，它可以理解简单的算术，例如“5+5”或“(5+5)*3”。

我认为第一步是编写一个“标记器”，它将整个输入字符串分解为许多子字符串。这部分我已经完成了（我什至不得不在这里询问它。如果你不想的话，你不必点击链接，因为我在这里也发布了相关代码。）使用这个标记器我的，我最终得到一个vectorof strings 或令牌。现在，困难的部分：我想解析这些标记。

我已阅读有关递归下降解析器的 Wikipedia 文章。我确实了解整体概念，但与往常一样，实现有点令人困惑。在那篇文章中，有一个用于非常简单的编程语言的递归下降解析器的 C 实现，文章中也进行了讨论。我尽我所能研究了该代码，并尝试基本上编写相同的东西，但对于我的程序。下面是那个代码。

我真正困惑的是这个解析器做了什么。它似乎通过程序并“预期”语法的某些部分。但是一旦它到达那里，它会做什么？例如，这里有一个来自维基百科代码的函数，它应该解析一个“术语”：

这是为了解析这个语法：

这是有道理的。但它与实际术语有什么关系？假设该术语只是“6”，或者是“3 * 2”并且结果为6。它将如何将其合并到输入的其余部分中？不应该term()返回 adouble而不是void（返回 6）？还是以其他方式完成？

此外，让这样的解析器输出代码和立即对输入采取行动（即编译器与解释器）之间有什么区别？这两个（至少在这个例子中）理论上是用相同的方式实现的，还是根本不同？

欢迎任何意见。到目前为止，这是我的代码：

编辑：我应该提到我的代码总是ERROR: syntax error从factor()函数中打印：

我已将此问题移至代码审查

我在 bash 中编写了一个递归下降解析器。

我想知道你是否可以指出一些对我有帮助的东西。它支持反斜杠转义和带解析错误报告的引用字段。

该脚本cut在某些方面的工作方式类似于.. 从文件中获取输入或stdin允许用户选择他们想要打印的行和字段。分别使用选项-l和-f。可以打印字段列表，并且可以使用选项 --list '1 2 3 4 5' 和 --list-seperator $'\n' 指定该列表的自定义分隔符。

为了响应BASH 中的递归下降 CSV 解析器，我（两篇文章的原作者）尝试将其翻译成 AWK 脚本，以比较这些脚本语言的数据处理速度。由于一些缓解因素，翻译不是 1:1 翻译，但对于那些感兴趣的人来说，这种实现在字符串处理方面比其他实现更快。

最初，由于 Jonathan Leffler，我们有几个问题都被取消了。虽然标题是CSV，但我们已经更新了代码，DSV这意味着您可以将任何单个字符指定为字段分隔符，如果您认为有必要的话。

这段代码现在可以摊牌了。

基本功能

• 对输入长度、字段长度或字段计数没有强加限制
• 通过双引号的文字引用字段"
• 在第 1.1.2 ^{[1][2][3]节中}定义的ANSI C 转义序列
• 自定义输入分隔符：UNIX 编程艺术(DSV) ^[4]
• 自定义输出分隔符^[5]
• UCS-2 和 UCS-4 转义序列^[6]

^[1]引用的字段是文字内容，因此不会对引用的内容执行转义序列解释。然而，可以在单个字段中连接引号、纯文本和解释序列以实现所需的效果。例如：

是 CSV 的三字段行，其中第三字段相当于：

^[2]参考资料中描述为“特定于实现”或具有“未定义行为”的示例将不受支持，因为它们在定义上不可移植，或者过于模棱两可而不可靠。如果此处或参考资料中未定义转义序列，则反斜杠将被忽略，最后面的单个字符将被视为纯文本值。不支持整数值字符转义序列，这是一种不可靠的方法，不能很好地跨多个平台扩展，并且不必要地增加了通过验证代理解析的复杂性。

^[3]八进制字符转义必须是 3 位八进制格式。如果它不是 3 位八进制转义序列，则它是单个数字空转义序列。十六进制转义序列必须采用 2 位十六进制格式。如果转义序列标识符后面的前两个字符无效，则不会进行任何解释，并且将在标准错误上打印一条消息。任何剩余的十六进制数字都将被忽略。

^[4]自定义输入分隔符iDelimiter必须是单个字符。不支持多行记录，并且应始终不赞成使用这种矛盾。这降低了数据记录的可移植性，使其特定于位置和来源（在该文件中）可能未知的文件。例如，grep为内容生成文件可能会返回不完整的记录，因为内容可能从任何前一行开始，从而将数据获取限制为对数据库进行完全自上而下的解析。

^[5]自定义输出分隔符oDelimiter可以是任何所需的字符串值。脚本输出总是由一个换行符终止。这是正确终端应用程序输出的一个特征。否则，您解析的 CSV 输出和终端提示将使用同一行，从而造成混乱的情况。此外，大多数解释器（如控制台）都是基于行的设备，它们希望换行符表示 I/O 记录的结束。如果您发现尾随换行符不受欢迎，请将其剪掉。

^[6] 16 位 Unicode 转义序列可通过以下符号获得：

和 32 位 Unicode 转义序列通过以下方式支持：

特别感谢 SO 社区的所有成员，他们的经验、时间和投入使我创建了这样一个非常有用的信息处理工具。

代码清单：dsv.awk

如果您需要一些自定义输出控制分隔符但不确定使用什么，您可以参考这个方便的 ASCII 图表

未来的计划：

• C 库实现
• C 控制台应用程序实现
• 向互联网工程任务组提交可能的标准化

哲学

转义序列应始终用于在基于行的数据库中创建多行字段数据，并且应始终使用引用来保留和连接记录字段内容。这是实现这种类型的记录解析器的最简单（因此也是最有效）的方法。我鼓励所有软件开发人员和教育机构接受并表明这一方向，以确保可移植性和精确获取基于行的分隔符分隔的记录。

CSV 没有除RFC 4180之外的官方规范，也没有定义任何有用的可移植记录类型。作为一名拥有超过 15 年经验的开发人员，我希望这将成为官方认可的便携式 CSV/DSV 记录标准。

我是语法和解析领域的新手。

我正在尝试编写一个递归下降解析器来评估这样的字符串：

((3 == 5 AND 4 == 5) OR (6 == 6))

在我开始处理嵌套括号之前，一切对我来说都很好。本质上，我发现我过早地到达目标字符串的末尾。

我认为问题是由于当我遇到像“6”或倒数第二个括号这样的标记时，我评估它然后移动到下一个标记。我会删除前进到下一个令牌的代码，但是我不确定我如何前进。

我的语法，例如，看起来像这样（“=>”符号是我自己对规则“翻译”的符号）：

测试：If CompoundSentence Then CompoundSentence | 复合句

CompoundSentence : ( CompoundSentence ) PCSopt |CompoundSentence 连词 |

句子 =>

CompoundSentence = (CompoundSentence) PCSopt | 句子 CSOpt

PCSOpt = Paren连词复合句 PCSOpt| 厄普西隆

CSOpt = 连词 CSOpt| 厄普西隆

Paren连词：And|Or

连词：和|或

句子：主语动词前缀

主题：主题中缀值 | 价值 =>

主题 = 值 SubjectOpt

SubjectOpt = 中缀值 SubjectOpt | 厄普西隆

动词：==|!=|>|<

谓词：谓词中缀值 | 价值 =>

谓词 = 值 PredicateOpt

PredicateOpt = 中缀值 PredicateOpt | 厄普西隆

中缀：+、-、*、/

我的复合句代码如下：

正如我所说，我是这个领域的新手，所以我可能不了解一些非常基本的东西。

如果有人能引导我朝着正确的方向前进，我将不胜感激。

我有以下作品

所以很明显有左递归

据说使用以下规则可以避免左递归

这里如何避免左递归？函数A'中仍然存在递归。任何人都可以解释一下。我是这个主题的初学者吗？