作为有限状态机的通用语言解析器

Question

我为通用语言编写了性能非常低的下降递归解析器（开源，用于 EBNF 语法）。我想通过重写解析器来修复它的性能。

我阅读了词法分析、LL、LR、LALR 解析器和类似 LL(*) 的修改，我阅读了龙书的前 3 章（关于词法分析器和解析器），我探索了 ANTLR 等开源项目。

而且我想知道为什么没有描述这个算法。也许这是错误的方式，我不知道。或者也许我重新发明了轮子。

假设我们有语法（e：文件结尾）：

A: B? B 1? e
B: 0 | 1

变换后的语法：

A: B B 1 e | B B e | B e
B: 0 | 1

可能的场景：

[01] [01] [1] [e]
[01] [01] [e]
[01] [e]

我们可以构建类似 FSM 的东西：

Symbol #0:

[01]: continue

Symbol #1:

[01]: continue
[e]: parse as "B e"

Symbol #2:

[1]: parse as "B B 1 e"
[e]: parse as "B B e"

它将以 O(N) 的时间解析令牌流。对于真正的语法，它可以修改为不仅仅是简单的 FSM，但仍然是 O(N)。

所以我有这些问题：

这种方法能产生积极的结果吗？
和LL、LR等解析器有关系吗？目前我对那些算法还不够了解，没有尝试过。
对于正确的输入字符串，哪种解析算法更快？我只对解析正确的输入字符串感兴趣，因为我正在制作与 IDE 一起使用的代码生成工具，它可以自己报告错误。所以我需要最快的算法来完成这个非常具体的任务。

谢谢。

更新：

我最终得到了 ANTLRv4，我找到了适合我的语言的目标和运行时 (Swift)，我非常满意。

Answer 1

LALR(k) 的复杂度为 O(N)，如果将其简化为“状态中的令牌分支到下一个状态，堆叠令牌值”的机器代码，则可以快如闪电。（见本文：https://web.archive.org/web/20170809025652id_/http://www.genesishistory.org/content/ProfPapers/VF-LRParsing.pdf）

目前尚不清楚通过尝试发展您的想法您会获得什么；怎么会比这更快？

[最重要的不是解析；它通常是您可以构建词素的速度，尤其是。消除白色 space].

如果你真的想构建一个工具，你应该在工具上工作并采用你可以获得的最好的技术，这样你就不必发明它们。

如果您坚持要发明新技术，那么您最终将拥有 patch/enhance/tune 它们，而永远无法抽出时间来构建工具。也许你有一个好主意。你得投入更多的精力才能一探究竟。

只要确定您知道自己要实现的目标。

General language parser as a finite state machine