1个不稳定版本

0.1.0-alpha.1	2023年6月1日

#94 在解析工具

在 2 个crate中（通过 pag-parser）使用

MIT/Apache

4MB
1K SLoC

Paguroidea

crate	状态
`pag-lexer`
`pag-parser`
`pag-compiler`

Flap解析器在Rust中的重新实现（应用了我们的修改）！

🚧 施工中 🚧

此项目仍处于早期开发阶段。Paguroidea的语法可能会发生变化（见问题 #22）。解析生成器尚未经过彻底测试，可能偶尔还会出现一些错误。还有正在进行的工作以改进生成代码的质量。

介绍

Paguroidea是一个解析生成器（即编译器的编译器）。Paguroidea的理论基础建立在几篇论文的基础上

正则表达式派生的再审视介绍了一种根据语言派生直接生成词法分析器的DFA的方法。这种方法创建的DFA状态数接近最小值。
类型化、代数方法解析提供了一种方法来“类型检查”上下文无关文法，确保经过检查的语法可以在单字符先行符的情况下以线性时间解析。这在Flap/Paguroidea中非常有用，可以确保归一化的总正确性。
flap：具有融合词法分析的可确定性解析器发明了一种将上下文无关文法归一化到所谓的确定性Greibach正规形式（DGNF）的新方法，其中可以使用局部化的较小的词法分析器为每个单独的解析程序而不是使用包含所有标记正则表达式的词法分析器对整个输入进行词法分析。

我们通过扩展DGNF来修改flap的工作，其中包含树生成动作，类似于传统移位-归约解析器中的“归约”操作。

如何使用

注意：本节中使用的解析器定义的语法将在不久的将来更改。

很简单：只需定义您的语法并将其传递给我们的编译器。然后，Paguroidea将输出一个独立的解析器文件。

例如，一个简单的S表达式解析器可以定义如下

lexer {
    definition BLANK     = ' ';
    definition DIGIT     = '0' .. '9';
    definition ALPHA     = 'a' .. 'z' | 'A' .. 'Z';
    active token LPAREN     = '(';
    active token RPAREN     = ')';
    active token ATOM       = ALPHA ~ (ALPHA | DIGIT)*;
    silent token WHITESPACE = (BLANK | '\t' | '\n' | '\r')+;
}
parser sexpr {
    active fixpoint compound
        = LPAREN ~ (compound | atom) * ~ RPAREN;

    active definition atom
        = ATOM;

    active definition sexpr
        = compound | atom;
}

如何编写语法文件

您可以使用以下规则创建自己的语法

语法文件必须包含词法分析和解析器部分。
在词法分析器部分的一个 definition 是一个表示某些常用词法规则的 宏。定义本身不计算为标记，这类似于 ANTLR 中的 fragment。
词法分析器最多只能有一个 silent 标记。在解析过程中，silent 标记将被自动跳过。
在词法分析器部分定义的所有规则都必须全部大写。
您可以使用
- 空（'_'）
来组成您的正则表达式。注意，补码不是通常意义上的负向前瞻。相反，它代表与否定项互补的字符或语言。要求所有活动标记都不能是可空的。

解析器部分必须在头部指定入口点。字符串/字符/范围不能直接在解析器部分使用，但解析器可以引用词法分析器中定义的标记。解析器规则全部为小写。词法分析器部分的大多数组合器在解析器部分中也得到支持，除了补码。

对于更复杂的示例，可以查看 json.pag。

如何编译和使用语法文件要编译您的语法文件，推荐的方式是将 pag-compiler 添加为您的构建依赖项。使用 pag-compiler，解析器文件可以在构建脚本中轻松生成，如下所示 fn main() { pag_compiler::compile("csv.pag", "src/parser.rs"); println!("cargo:rerun-if-changed=csv.pag"); } 由于某些原因（主要是性能问题），目前仅支持 nightly rust（1.71+）。还要求包含解析器文件的 crate 应该带有以下注释 #![feature(portable_simd)] #![feature(core_intrinsics)] #![feature(array_chunks)] 性能我们正在持续改进生成的解析器质量。目前，在 CSV/JSON 工作负载上，性能接近甚至优于那些专用解析器。 === Random Generated CSV === throughput/pag time: [635.88 µs 637.64 µs 639.46 µs] thrpt: [622.63 MiB/s 624.41 MiB/s 626.14 MiB/s] throughput/csv time: [528.36 µs 541.72 µs 559.54 µs] thrpt: [711.56 MiB/s 734.97 MiB/s 753.55 MiB/s] throughput/pest time: [3.7278 ms 3.7364 ms 3.7460 ms] thrpt: [106.29 MiB/s 106.56 MiB/s 106.80 MiB/s] === Random Generated JSON === random-json/pag-json time: [22.634 ns 22.650 ns 22.666 ns] thrpt: [84.149 MiB/s 84.209 MiB/s 84.271 MiB/s] random-json/serde-json time: [12.493 ns 12.587 ns 12.694 ns] thrpt: [150.26 MiB/s 151.54 MiB/s 152.67 MiB/s] random-json/pest-json time: [177.38 ns 178.17 ns 179.17 ns] thrpt: [10.645 MiB/s 10.705 MiB/s 10.753 MiB/s] === twitter.json === twitter-json/pag-json time: [1.0923 ms 1.0941 ms 1.0961 ms] thrpt: [667.24 MiB/s 668.46 MiB/s 669.59 MiB/s] twitter-json/serde-json time: [1.2281 ms 1.2295 ms 1.2312 ms] thrpt: [594.02 MiB/s 594.88 MiB/s 595.54 MiB/s] twitter-json/pest-json time: [5.2977 ms 5.3055 ms 5.3148 ms] thrpt: [137.61 MiB/s 137.85 MiB/s 138.06 MiB/s] 为什么它速度快以及如何使我的语法更快感谢 Flap 解析器的努力工作，我们可以将词法分析和解析器合并在一起，使得词法分析器可以实现本地化。我们显式地应用了尾调用优化。要利用此功能，默认使用 *、+ 或尽可能将规则标记为静默规则。我们使用 SIMD 或查找表应用批量前瞻策略。此优化适用于重复简单字符集的情况（例如，(BLANK | '\t' | '\n' | '\r')+）。我们正在努力内联/减少更多涉及状态转换和词法分析器-解析器通信的操作。诊断语法错误检查我们为语法定义中的“类型错误”提供诊断信息。以下是一些示例左递归 Error: Unguarded fixpoint ╭─[json.pag:39:5] │ 39 │ active fixpoint json = json ~ value; │ ─────────────────┬───────────────── │ ╰─────────────────── fixpoint rule json is not guarded -- your grammar is left-recursive ────╯ 序列歧义说明：根据语法定义将序列分为两部分时可能存在歧义 Error: When type checking a sequence of rules, the following rules are ambiguous ╭─[json.pag:39:28] │ 39 │ active fixpoint test = NUMBER+ ~ NUMBER+; │ ───┬─── ───┬─── │ ╰─────────────── type info for left-hand side: nullable: false, first set: {NUMBER}, follow set: {NUMBER} │ │ │ ╰───── type info for right-hand side: nullable: false, first set: {NUMBER}, follow set: {NUMBER} ────╯ 选择歧义说明：在选择两个规则的交替匹配中可能存在歧义。 Error: When type checking an alternation of rules, the following rules are ambiguous ╭─[json.pag:39:28] │ 39 │ active fixpoint test = NUMBER+ | NUMBER; │ ───┬─── ───┬── │ ╰────────────── type info for left-hand side: nullable false, first set: NUMBER, follow set: NUMBER │ │ │ ╰──── type info for right-hand side: nullable false, first set: NUMBER, follow set: ────╯ 还有其他诊断信息，如未定义的引用、词法分析器中的可空标记、字符格式错误等。

依赖项 proc-macro2 quote smallvec