flex-lexer - 是否有任何论文描述了为什么 flex 比 lex 快？

Question

flex 被称为“快速”词法分析器，但我找不到任何文档解释为什么它比 lex 快。flex 有一本手册，但它专注于它的使用而不是它的内部。请问有这方面的专家可以帮忙吗？欢迎提供有关 flex 性能改进的解释或链接。

Answer 1

补充一下 Vern 的说法，flex在表压缩方面做得更好，提供了几种不同的空间/时间权衡，而且它的内部循环也比lex 的.

根据 van Jacobsen 在 1980 年代的一篇（Usenet？）论文，lex主要由 AT&T 实习生编写。VJ 描述了它的内部循环如何从几十个指令减少到大约三个。

Vern Paxon 编写了flex，当时他将其描述为世界上最快的数据采集应用程序。不知道我是否应该在这里详细介绍。

我有幸帮助 Vern 开发 8 位版本，因为当时我从事的编译器必须扫描汉字和片假名。

Answer 2

这个答案来自 Vern Paxson，他允许在这里分享。

唉，这将花费相当多的时间来绘制任何有用的细节，因为有许多技术有助于其性能。很久以前（80 年代中期！）我写了一篇关于它的论文，但没有它的副本。显然，您可以从以下位置购买它：

    http://www.ntis.gov/search/product.aspx?ABBR=DE85000703

很抱歉没有提供更多帮助...

Answer 3

我不太确定flex它是否比 AT&T 版本快得多lex。这两个程序都是独立开发的，为了避免与官方版本混淆，作者flex可能选择了一个略有不同的名称。他们可能打算生成更快的扫描仪，这也是一些用空间换时间的选项所建议的。他们还鼓励%option yylineno使用生成的扫描仪的速度来选择（和一些其他功能）。

这种扫描仪在速度上的细微差别是否仍然相关是值得商榷的。我也找不到关于名称选择的任何官方声明，所以我想你得问问原作者Jef Poskanzer和/或Vern Paxson。如果您找到它们并得到答案，请在此处告知我们。软件的历史很有趣，您仍然可以直接获得答案。