1

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

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

谢谢你的帮助，查理。

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

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

4

3 回答 3

3

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

  1. 让算术工作。通过这种方式，为 etc 制定规则和派生，+, -, /, *并确保解析器生成一个有效的抽象语法树。在不同的输入上测试和评估树，以确保它正确地执行算术。一步一步做事。如果您遇到任何冲突，请在继续之前先解决它。

  2. 让更简单的构造像if-then-else或case表达式一样工作。

  3. 更进一步取决于您编写语法的语言。

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

ANSI C 语法

Python 语法

当然还有一些维基百科中关于 LL 语法Wikipedia LL Parser的小例子，你可能已经检查过了。

我希望你发现其中一些有用的东西

于 2011-02-18T14:11:52.400 回答
2

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

但是您不需要将简单语言限制为 LL(1)，因为大多数现代解析器生成器（JavaCC、ANTLR、Pyparsing等）都可以处理 LL(k) 中的任何 k。

更重要的是，您认为最适合您的语言的语法很可能需要k2 到 4 之间的值，因为几种常见的编程结构都需要。

于 2011-02-27T17:53:54.337 回答
1

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

如果没问题，下一步就是在脑海中逐步完成语法，想象此时可能出现的所有可能性，并检查它们是否可以通过它们的第一个标记来区分。

制作文法 LL(1) 有两个主要的经验法则

  1. 如果多个选项可以出现在给定点并且它们可以以相同的标记开头，请在前面添加一个关键字，告诉您选择了哪个选项。
  2. 如果您有可选或重复部分，请确保其后跟一个不能作为可选/重复部分的第一个标记出现的结束标记。
  3. 尽可能避免在生产开始时使用可选部件。它使前两个步骤变得容易得多。
于 2015-12-04T15:38:46.307 回答