写正确的语法吗？

Question

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

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

谢谢你的帮助查理。

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

编辑:还有，根据SK-逻辑，Parsec可以处理无限向前看(LL(k) ?) --但我想这个问题仍然代表着那种语法。

Answer 1

我不是这方面的专家，因为我只使用LR(0)解析器做了一个类似的小项目。我建议的一般做法是：

1. 让算术起作用。通过这个，为+, -, /, *等创建规则和派生，并确保解析器生成一个工作的抽象语法树。测试和评估树在不同的输入，以确保它做正确的算法。一步一步把事情做好。如果你遇到任何冲突，先解决它，然后再继续。
2. 使simper结构像if-then-else或case表达式一样工作。
3. 更进一步地讲，更多地取决于你编写语法所用的语言。

明确地检查其他编程语言语法作为参考(不幸的是，我在1分钟内没有找到任何在线语言的完整LL语法，但是LR语法也应该是有用的)。例如：

ANSI C文法

Python语法

当然，维基百科中也有一些关于LL语法维基百科LL Parser的小例子，您可能已经看过了。

我希望你能找到一些有用的东西

Answer 2

有两种算法来确定语法是否为LL(k)。解析器生成器实现它们。如果可能的话，也有将语法转换为LL(k)的启发式方法。

但是您不需要将简单的语言限制为LL(1)，因为大多数现代解析器生成器(JavaCC、反、勾股分析和其他)都可以处理LL(k)中的任何k。

更重要的是，您认为最适合您的语言的语法很可能需要一个介于2到4之间的k，因为有几个常见的编程结构是这样的。

Answer 3

所以首先，你不一定希望你的语法是LL(1)。它使编写解析器变得更简单，并可能提供更好的性能，但这确实意味着您的语言最终可能比常用的语言(通常不是LL(1))更冗长。

如果可以的话，下一步是从精神上通过语法，想象所有可能出现在这个点上的可能性，并检查它们是否可以通过它们的第一个标记来区分。

制定语法LL(1)有两条主要的经验法则

1. 如果多个选项可以出现在给定的点上，并且它们可以以相同的标记开始，那么在前面添加一个关键字，告诉您采取了哪种选择。
2. 如果您有一个可选的或重复的部分，请确保它后面跟着一个不能作为可选/重复部分的第一个令牌出现的结束标记。
3. 尽可能避免在生产开始时使用可选部件。这使得前两个步骤变得容易多了。