我有一个用于语法的 BNF 和 EBNF。BNF 显然更冗长。就使用 BNF 构建递归下降解析器而言，我有一个相当不错的主意；有很多资源。我无法找到将 EBNF 转换为递归下降解析器的资源。是因为难度更大吗？我记得在我的 CS 理论课程中，我们学习了 EBNF，但我们没有将它们转换为递归下降解析器。我们确实将 BNF 转换为递归下降解析器。
我问的原因是因为 EBNF 更紧凑。
从总体上看 EBNF，我注意到包含在{和之间的术语}可以转换为while循环。是否有其他指导方针或规则？
2898 次
3 回答
8
您应该研究所谓的元编译器，它本质上将 EBNF 编译为递归下降解析器。他们如何做到这一点正是您的问题的答案。（它非常简单，但很好理解细节）。
Val Schorre 的“MetaII”论文是一篇非常棒的论文。这是 1964 年老实说的元编译器技术。在 10 页中，他向您展示了如何构建元编译器，并且不仅提供了元编译器，还提供了另一个编译器以及两者的输出！。如果你去构建其中的一个，你也会来一个令人惊讶的时刻，在那里你意识到元编译器是如何使用自己的语法编译自己的。大约在 1970 年，当我第一次被这篇论文绊倒时，这一刻让我迷上了编译器。这是软件行业的每个人都应该阅读的计算机科学论文之一。
James Neighbors（软件工程中“领域”一词的发明者，第一个程序转换系统 [基于这些元编译器] 的构建者）有一个很棒的在线MetaII 教程，适合那些不想动手做的人从头开始的经验。（除了我和邻居是本科生之外，我与此无关）。
这两种方式都是了解元编译器和从 EBNF 生成解析器的好方法。
关键思想是，规则的左侧创建了一个函数，该函数解析该非终结符并在匹配时返回 true 并推进输入流；如果没有匹配并且输入流没有前进，则返回 false。函数的内容由右手边决定。文字标记直接匹配。非终结符导致调用为其他规则生成的其他函数。Kleene* 映射到 while 循环，alternation 映射到条件分支。EBNF 没有解决的问题，而元编译器解决了，除了说“匹配”或不说“匹配”之外，解析如何做任何事情？秘诀是将输出操作编织到 EBNF 中。MetaII 论文让这一切变得一清二楚。
于 2010-11-08T04:33:01.620 回答
4
两者都不比另一个难。这确实是迭代实现某些东西和递归实现某些东西之间的区别。在 BNF 中，一切都是递归的。在 EBNF 中，一些递归是迭代表示的。EBNF 语法有不同的变化，所以我将只使用英语......“零或更多”是一个简单的 while 循环，正如您所发现的。“一个或多个”与一个后跟“零个或多个”相同。“零或一次”是一个简单的 if 语句。这应该涵盖大多数情况。
于 2010-03-24T18:09:41.357 回答
1
早期的元编译器 META II 和 TREEMETA 以及它们的同类并不完全是递归的体面解析器。它们被声明为使用递归函数。这只是意味着他们可以称自己为自己。
我们不称 C 为递归语言。AC 或 C++ 函数是递归的，就像早期的元编译器是递归的一样。
可以使用递归。他们是编程语言。递归通常仅在分析下一个语言结构时使用。例如带括号的表达式和下一个块。
更多的是 LR 递归的体面组合。CWIC 最后记录的一个具有广泛的回溯和前瞻功能。'-' not 运算符可以匹配任何语言结构。并颠倒它的成功或失败。例如，如果一个术语匹配，-term 将失败。输入永远不会提前。这 '？' 向前看并匹配任何语言构造 ?expr 例如会尝试解析 expr。展望未来'？不保留匹配的构造或输入是高级的。
于 2014-10-25T17:26:31.423 回答