为预测分析转换语法

Question

下面的语法是否适合预测分析，或者它们是一种修改语法以使其适合预测分析的算法？

number = digit digit_or_sep* digit | digit
digit_or_sep = '0'..'9' | '_'
digit = '0'..'9'

其中*表示零个或多个，|划分不同的选择。

我写了一个回溯解析器，在上述语法上运行良好，但是我读到现在现代解析器大多是预测性解析器，很少使用回溯解析器。回溯解析器需要在回溯时倒回解析器的状态，这使得它们的性能不如预测解析器。

将上面的语法转化为：

number = digit (sep* digit+)*
sep = '_'
digit = '0'..'9'

其中 + 表示一个或多个。

将使预测解析工作，因为它避免 digit_or_sep* 在最终 digit 之前消耗过多的标记。但是我不确定是否有一种算法可以自动转换语法以使其工作。

编辑： 我在 google 上读到了关于左因式分解的文章，它可能是我需要理解的缺失部分。

经过一些左重构：

number = digit digit_or_sep* digit | digit
digit_or_sep = '0'..'9' | '_'
digit = '0'..'9'
let g = digit_or_sep g | empty
number = digit g digit | digit
let h = g digit | empty
number = digit h
h = g digit | empty
g = digit_or_sep g | empty
g = digit g | sep g | empty
h = (digit g | sep g | empty) digit | empty
h = digit g digit | sep g digit | digit | empty
h = digit h | sep g digit | empty

生成如下语法：

number = digit h
h = digit h | sep g digit | empty
g = digit g | sep g | empty

这应该适用于预测解析器。但是我还没有想出一个算法来自动完成它。

编辑： 详细介绍我正在尝试做的事情。上面的语法只是我想改造的语法的一个小例子。

我实际上是在解析 Kotlin： https://github.com/clinuxrulz/parse-bolt/blob/main/src/kotlin/parser.rs

它与回溯解析器一起工作正常，但存在性能问题。解析一个简单的函数类型签名“(a: String, b: String) -> String”需要 20 毫秒来解析，这对于这么小的输入来说太慢了。我可以在我知道的代码中做一些优化，但它比我预期的要慢。

另一方面，对于预测解析，我不能简单地按原样使用它们的语法。似乎首先需要对语法进行一些手动更改。在生成解析器之前，ANTLR 必须首先对其语法进行一些转换。

这个 Kotlin 语法文件的底部与上面的数字示例相同： https://github.com/Kotlin/kotlin-spec/blob/release/grammar/src/main/antlr/KotlinLexer.g4

我读过 ANTLR 可以在 1 秒内解析完整的 Java 标准库。我可能还有很长的路要走。

编辑：(29/04/2022) 经过更多研究，我发现初始语法（对于数字）对于预测解析器没有问题，我只是需要更多向前看。

Answer 1

我同意 rici 的评论，即没有算法可以保证任何语法的完全左分解。但是也有启发式搜索方法。

我会坚持使用 PEG 并在需要性能时修改我自己的语法。并尽可能优化我的回溯解析组合器，因为它可以处理更多类型的语法并且可能仍然有用。

为预测分析转换语法

Transforming grammar for predictive parsing

parsing

theory