Lib.rs

› 解析工具
#parser-generator #grammar #cfg #parser

pag-parser

解析器-词法分析器融合生成器（解析生成器）

由 Schrodinger ZHU Yifan，QuarticCat 编写

1 个不稳定版本

0.1.0-alpha.12023年6月1日

#170 在 解析工具


用于 pag-compiler

MIT/Apache

8MB
4.5K SLoC

hermit-crab
Paguroidea

GITHUB-BADGE

包 状态
pag-lexer crates.io
pag-parser crates.io
pag-compiler crates.io

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

🚧 施工中 🚧

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

简介

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

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

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

如何使用

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

很简单：只需定义您的语法并将其传递给我们的编译器。然后，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: 
  ────╯

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

依赖项