1 个不稳定版本

0.1.0-alpha.1	2023年6月1日

#273 in 解析工具

MIT/Apache

8MB
3K SLoC

Paguroidea

仓库	状态
`pag-lexer`
`pag-parser`
`pag-compiler`

Flap解析器在Rust中的重写（添加了我们的修改）！

🚧 施工中 🚧

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

简介

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

正则表达式导数再考察介绍了一种直接基于语言导数生成词法分析器的DFAs的方法。这种方法创建的DFAs状态数接近最小。
解析的代数和类型化方法提供了一种对上下文无关文法进行“类型检查”的方法，以确保检查过的语法可以在线性时间内以单标记前瞻进行解析。这在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标记将被自动跳过。
在词法分析器部分定义的所有规则都必须全部为大写。
您可以使用
- 空字符串（'_'）
- 字符（'a', '\x12', '😊'）
- 字符串（"你好", "Rust"）
- 范围（'A' .. 'Z'）
- 序列（'a' ~ 'b'），
- 可选（'a' | 'b'）
- 可选（'a'?）
- 零次或多次（'a'*）
- 一次或多次（'a'+）
- 补码（!'a'）
来构建您的正则表达式。注意，补码在常规意义上不是负向前瞻。相反，它代表的是被否定字符或语言的补集。要求所有活动标记均不能为空。
解析器部分必须在头文件中指定入口点。
字符串、字符和范围不能直接在解析器部分使用，但解析器可以引用词法分析器中定义的标记。
解析器规则全部使用小写。
词法分析器部分的大部分组合器也支持在解析器部分中，除了补码。

对于更复杂的示例，可以参考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: 
  ────╯

还有其他关于未定义引用、词法分析器中的可空标记、字符格式错误等的诊断信息。

依赖关系

~8MB
~73K SLoC