使用EBNF或BNF编写递归下降解析器会更容易吗？

Question

我有一个语法的BNF和EBNF。 BNF显然比较冗长。就使用BNF构建递归下降解析器而言，我有一个相当不错的主意;有很多这方面的资源。我无法找到资源将EBNF转换为递归下降解析器。这是因为它更难吗？我回想起我的CS理论课，我们讨论了EBNF，但我们没有将它们转换成递归下降解析器。我们做去BNF的转换为递归下降解析器。

我问的原因是因为EBNF更紧凑。

从查看EBNF的一般情况来看，我注意到在{和}之间的术语可以转换为while循环。还有其他的指导方针或规则吗？

Answer 1

两者都不比其他更难。迭代实现和递归实现的区别实际上是不同的。在BNF中，一切都是递归的。在EBNF中，一些递归是迭代表达的。 EBNF语法有不同的变化，所以我只会使用英语......“零个或多个”是一个简单的while循环，就像你发现的那样。 “一个或多个”与“零个或多个”后跟一个相同。 “零次或一次”是一个简单的if语句。这应该涵盖大部分情况。

Answer 2

您应该调查所谓的metacompilers，它实质上是将EBNF编译为递归下降解析器。他们如何做到这一点正是你的问题的答案。 （它很漂亮，但很好理解细节）。

一篇非常精彩的论文是Val Schorre的“MetaII”论文。这是从诚实到神的1964年的元编译器技术。在10页中，他向您展示了如何构建一个meta编译器，并且提供了不仅如此，而且还提供了另一个编译器以及两者的输出！有一个惊人的时刻，如果你去构建其中一个，你会发现如何使用自己的语法编译自己的元编译器。这一刻让我想起了1970年代当我第一次翻阅这篇论文的时候，编译器已经迷上了编译器。这是那些计算机科学论文之一，每个人在软件业务应该阅读。

James Neighbors（软件工程中术语“域”的发明者，以及第一个程序转换系统的构建者[基于这些元编译器]有一个伟大的在线MetaII tutorial，对于那些不想做的人-IT-从划伤的经验。（我什么都没有做这个，除了邻居和我在大学时）。

这两种方法都了解从EBNF metacompilers和生成语法分析器的好方法。

关键的想法是，规则的左侧创建一个函数来分析非终结符，如果匹配并推进输入流，则返回true;如果不匹配，则返回false并且输入流不前进。 该功能的内容由右侧确定。文字标记直接匹配。 非终结者会调用为其他规则生成的其他函数。 Kleene *映射到while循环，变换映射到条件分支。 EBNF没有解决的问题是， 和元编译器是做什么的，除了说“匹配”还是没有，解析是如何做的？ 秘诀在于将输出操作编织到EBNF中。 MetaII纸使所有这些晶莹剔透。

Answer 3

早期的meta编译器META II和TREEMETA及其亲属并不完全是递归体面的解析器。他们被描述为使用递归函数。这意味着他们可以称他们为自己。

我们不称C为递归语言。 C或C++函数是递归的，就像早期的元编译器递归一样。

可以使用递归。他们是编程语言。递归通常只在分析nexted语言结构时使用。例如加括号的表达式和nexted块。

更多的LR递归体面组合。 CWIC最后记录的一个有广泛的回溯和展望功能。 ' - '不是操作符可以匹配任何语言结构。并将其倒置成功或失败。例如，如果一个术语匹配，则该术语失败。输入永远不会提前。 '？'向前看并匹配任何语言结构？例如，expr会尝试解析expr。展望未来'？'匹配的结构不被保留或者是输入先进的。