yacc/lex还是手写代码？

Question

我正在开发一种新的编程语言，但我一直被所有人都在使用yaxx / lex解析代码的事实所困扰，而我没有。

我的编译器（已经可以工作）是用C ++ / STL手写的，我不能说它很复杂或花费了太多时间。它既有某种类型的词法分析器又有解析器，但它们不是自动生成的。

早些时候，我以同样的方式编写了一个C编译器（不是完整规范），它能够在1个通路中编译程序，并解决所有这些反向引用和预处理 - 这绝对无法使用yacc / lex实现。

我就是无法说服自己放弃这一切，开始深入研究可能需要相当大的工作量来实现并可能引入某些语法限制的yaxx / lex。

如果我不使用yacc / lex，我会错过什么吗？ 我做了什么邪恶的事吗？

- BarsMonster

---

这取决于你如何进行。我正在使用无上下文表达式 - 这种形式直到2010年代末和2020年代初才被出版。例如，C-BC的解析器是通过上下文无关表达式手动计算代数学得的。https://github.com/RockBrentwood/CBC ... 正则表达式语法在这里 https://github.com/RockBrentwood/RegEx 中也是如此，但仅用于此处的AutoMath的复活版本的词汇部分 https://github.com/RockBrentwood/AutoMath，但尚未用于解析器。语法仍然在yacc中。 - NinjaDarth

Answer 1

使用任何类型的词法/语法分析器生成器的主要优点是，如果您的语言发展了，它会给您带来更多的灵活性。在手工编写的词法/语法分析器中（特别是如果您在单个传递中混合了大量功能！），语言的更改很快变得复杂，而使用分析器生成器，您可以进行更改，重新运行生成器，然后继续生活。当然，总是手写所有东西并没有固有的技术限制，但我认为自动化掉无聊部分的可演进性和可维护性是值得的！

- Gian

---

良好的模块化设计（例如，分词器和词法分析器应完全分离）可以减少这个问题。但仍然很重要。 - user395760

Answer 2

Yacc在某些方面是不灵活的：

• 良好的错误处理很难（基本上，它的算法仅定义为正确解析一个字符串，否则，一切都无法保证；这是GCC转向手写解析器的原因之一）
• 上下文依赖性很难表达，而使用手写递归下降解析器，您可以简单地向函数添加参数

此外，我注意到lex/yacc对象代码通常比手写递归下降解析器更大（源代码倾向于相反）。

我没有使用ANTLR，因此无法确定它在这些方面是否更好。

- jilles

Answer 3

使用生成器的另一个巨大优势是，它们保证仅处理您在语法中指定的语言。手写代码不能做到这一点。 LR / LALR 变体也保证为 O (N)，这也不是任何手写代码可以断言的，至少不需要大量构造证明。

我曾经编写过手写代码和使用生成器，并且再也不会手写代码了。我之前只是因为当时平台上没有 yacc。

- user207421

---

我不需要数学证明来知道我的代码有多快 - 通常很明显它在O(N)或O(N*LogN)的某个地方。 - BarsMonster

我并没有提到“快”。我在谈论算法复杂度，你需要一个证明。 - user207421

当我编写代码时，我总是知道它的复杂性。如果有工具可以为我编写代码，那么我肯定需要一个证明。 - BarsMonster

你的理解有误。1965年Don Knuth证明了LR分析算法的O（N）时间复杂度，1969年Frank deRemer亦证明了LALR分析算法同样具有O（N）时间复杂度。你在哪里得到你的结论呢？你不能仅凭直觉就知道手写编译器这种复杂任务的算法复杂度。 - user207421

好的，那他不确定又怎样呢？“以O(n)编译”并不是很具有卖点。如果它对于普通项目来说“足够快”，那么没有人会关心。 - user395760

如果这是一次营销讨论，那对我来说是个新闻。我在这里讨论的是编译器生成器的优势，这也是OP所问的。无论您能否直接将其营销出去，接受完全正确的语言和O(1)复杂度都很重要，就像沉没成本、可维护性、可扩展性和上市时间一样，尽管您也不会将它们营销出去。否则，Don Knuth和Frank de Remer到底在做什么？ - user207421

Answer 4

也许你错过了ANTLR，它非常适合使用递归下降解析策略定义的语言。

使用Yacc/Lex可能有一些优势，但不是必须使用它们。使用Yacc/Lex也有一些缺点，但通常优点大于缺点。特别是，使用Yacc驱动的语法通常比手工编码的语法更容易维护，并且您可以从Yacc提供的自动化中受益。

然而，从头开始编写自己的解析器并不是一件坏事。这可能会使未来的维护更加困难，但也可能会更容易。

- Jonathan Leffler

Answer 5

这当然取决于你的语言语法的复杂性。简单的语法意味着易于实现，你可以自己完成。

让我们看看可能是最糟糕的例子：C++ :) （除了自然语言之外，还有哪种语言更难以正确解析？）即使使用像Antlr这样的工具，也很难做到完全正确，但它是可管理的。而另一方面，尽管更难，似乎一些最好的C++解析器（例如GCC和LLVM）也大多是手写的。

如果你不需要太多的灵活性，并且你的语言不太琐碎，那么使用Antlr肯定会节省一些工作/时间。

- Albert

---

我的编程语言的复杂度仅略低于C++。 - BarsMonster

经典的Fortran语言很难解析：赋值"DO10I=12.43"和循环"DO10I=12,43"甚至在分割单词时也无法准确区分逗号和句点。（第一个涉及浮点变量DO10I，第二个涉及整数变量I和标签10：DO 10 I = 12, 43。）这往往使它变得相当困难！ - Jonathan Leffler

“比C++少一点” - 这是一种自我限制的示例，这基本上回答了你的问题。选择手动编写代码将您限制在某种复杂度的阈值内，而其他使用自动化生成解析器的人则不受此限制。我更感兴趣的是看到您提高一下并尝试手工编写C++解析器。一个原始版本（包括yacc）是：“cfront”的E版转录https://www.softwarepreservation.org/projects/c_plus_plus/cfront/release_e，我们可能稍后会在GitHub上发布它。 - NinjaDarth