43 个版本 (17 个稳定版)

新功能 1.12.0	2024年8月24日
0.11.6	2024年8月7日
0.5.2	2024年7月29日

#7 in #bison

4,647 每月下载量
用于 rusty_lr

MIT 许可证

295KB
6K SLoC

RustyLR

Rust 的 GLR、LR(1) 和 LALR(1) 解析器生成器。

RustyLR 提供了用于生成 GLR、LR(1) 和 LALR(1) 解析器的过程宏和构建脚本工具。生成的解析器将完全是 Rust 代码，并且构建 DFA 的计算将在编译时完成。减少动作可以以 Rust 编写，并且错误信息是可读且详细的。对于大型和复杂的语法，建议使用构建脚本。

`features` in `Cargo.toml`

build : 启用构建脚本工具。
fxhash : 在解析器表中，将 std::collections::HashMap 替换为 rustc-hash 的 FxHashMap。

示例

// this define `EParser` struct
// where `E` is the start symbol
lr1! {
    %userdata i32;           // userdata type
    %tokentype char;         // token type
    %start E;                // start symbol
    %eof '\0';               // eof token

    // token definition
    %token zero '0';
    %token one '1';
    %token two '2';
    %token three '3';
    %token four '4';
    %token five '5';
    %token six '6';
    %token seven '7';
    %token eight '8';
    %token nine '9';
    %token plus '+';
    %token star '*';
    %token lparen '(';
    %token rparen ')';
    %token space ' ';

    // conflict resolving
    %left [plus star];                  // reduce first for token 'plus', 'star'

    // context-free grammars
    Digit(char): [zero-nine];           // character set '0' to '9'

    Number(i32)                         // type assigned to production rule `Number`
        : space* Digit+ space*          // regex pattern
    { Digit.into_iter().collect::<String>().parse().unwrap() }; 
    //    ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ this will be the value of `Number`
                                        // reduce action written in Rust code

    A(f32): A plus a2=A {
        *data += 1;                     // access userdata by `data`
        println!( "{:?} {:?} {:?}", A, plus, a2 );
        A + a2
    }
        | M
        ;

    M(f32): M star m2=M { M * m2 }
        | P
        ;

    P(f32): Number { Number as f32 }
        | space* lparen E rparen space* { E }
        ;

    E(f32) : A ;
}

let parser = EParser::new();         // generate `EParser`
let mut context = parser.begin();    // create context
let mut userdata: i32 = 0;           // define userdata

let input_sequence = "1 + 2 * ( 3 + 4 )";

// start feeding tokens
for token in input_sequence.chars() {
    match parser.feed(&mut context, token, &mut userdata) {
        //                          ^^^^^   ^^^^^^^^^^^^ userdata passed here as `&mut i32`
        //                          feed token
        Ok(_) => {}
        Err(e) => {
            match e {
                EParseError::InvalidTerminal(invalid_terminal) => {
                    ...
                }
                EParseError::ReduceAction(error_from_reduce_action) => {
                    ...
                }
            }
            println!("{}", e);
            // println!( "{}", e.long_message( &parser, &context ) );
            return;
        }
    }
}
parser.feed(&mut context, '\0', &mut userdata).unwrap();    // feed `eof` token

let res = context.accept();   // get the value of start symbol
println!("{}", res);
println!("userdata: {}", userdata);

可读的错误信息（带有 codespan）

images/error1.png images/error2.png

此错误信息由构建脚本工具生成，而不是过程宏。

特性

纯 Rust 实现
可读的错误信息，包括语法构建和解析
从 CFG 构建编译时的 DFA
可自定义的减少动作
解决歧义语法的冲突
部分支持正则表达式模式
与 build.rs 集成的工具

过程宏

以下提供了以下过程宏：

lr1! : 生成 LR(1) 解析器
lalr1! : 生成 LALR(1) 解析器

这些宏将生成结构体

Parser : 包含 DFA 表和产生式规则
ParseError : Error 类型别名的别名，由 feed() 返回
Context : 包含当前状态和数据堆栈
enum NonTerminals : 非终结符号的列表
Rule : 产生式规则的类型别名
State : DFA 状态的类型别名

以上所有结构都以前缀 <StartSymbol> 开头。在大多数情况下，您需要的是 Parser 和 ParseError 结构，其他则是内部使用的。

与 `build.rs` 集成

此构建脚本工具将提供比过程宏更详细、格式化的错误消息。如果您正在编写大型、复杂的语法，建议使用构建脚本而不是过程宏。生成的代码将包含与过程宏相同的结构和函数。在您的实际源代码中，您可以 include! 生成的文件。

与过程宏不同，程序在输入文件中搜索 %%，而不是 lr1!、lalr1! 宏。在 %% 之前的内容将按原样复制到输出文件中。上下文无关语法必须跟在 %% 之后。

// parser.rs
use some_crate::some_module::SomeStruct;

enum SomeTypeDef {
    A,
    B,
    C,
}

%% // <-- input file splitted here

%tokentype u8;
%start E;
%eof b'\0';

%token a b'a';
%token lparen b'(';
%token rparen b')';

E: lparen E rparen
 | P
 ;

P: a;

您必须在构建脚本中使用功能 build。

[build-dependencies]
rusty_lr = { version = "...", features = ["build"] }

// build.rs
use rusty_lr::build;

fn main() {
    println!("cargo::rerun-if-changed=src/parser.rs");

    let output = format!("{}/parser.rs", std::env::var("OUT_DIR").unwrap());
    build::Builder::new()
        .file("src/parser.rs") // path to the input file
    //  .lalr()                // to generate LALR(1) parser
        .build(&output);       // path to the output file
}

在您的源代码中包含生成的文件。

include!(concat!(env!("OUT_DIR"), "/parser.rs"));

开始解析

Parser 结构有以下功能

new() : 创建新的解析器
begin(&self) : 创建新的上下文
feed(&self, &mut Context, TerminalType, &mut UserData) -> Result<(), ParseError> : 将令牌喂给解析器

请注意，如果未定义 %userdata，则省略参数 &mut UserData。您只需要调用 new() 生成解析器，并调用 begin() 创建上下文。然后，您可以使用 feed() 函数依次将输入序列喂入。一旦输入序列被喂入（包括 eof 令牌），如果没有错误，您可以通过调用 context.accept() 获取起始符号的值。

let parser = Parser::new();
let context = parser.begin();
for token in input_sequence {
    match parser.feed(&context, token) {
        Ok(_) => {}
        Err(e) => { // e: ParseError
            println!("{}", e);
            return;
        }
    }
}
let start_symbol_value = context.accept();

GLR 解析器

可以通过语法中的 %glr; 指令生成 GLR（广义 LR 解析器）。

// generate GLR parser;
// from now on, shift/reduce, reduce/reduce conflicts will not be treated as errors
%glr; 
...

GLR解析器可以处理LR(1)或LALR(1)解析器无法处理的歧义语法。当它遇到解析过程中任何类型的冲突时，解析器将发散到多个状态，并尝试所有路径直到失败。当然，在解析结束时必须留下唯一的一条路径（即您提供eof标记的点）。

解决歧义

您可以通过减少操作来解决歧义。简单地说，从减少操作中返回Result::Err(Error)将撤销当前路径。《Error》变体类型可以通过%err指令定义。

关于GLR解析器的说明仍在开发中，尚未充分测试（欢迎补丁！）。由于存在多条路径，减少操作可能需要多次调用，即使未来的结果将被丢弃。每个RuleType和Term都必须实现Clone特质。用户必须意识到位移/减少或减少/减少冲突发生的位置。每次解析器发散，计算成本都会增加。语法要开始编写上下文无关语法，首先需要定义必要的指令。这是过程宏的语法。 lr1! { // %directives // %directives // ... // %directives // NonTerminalSymbol(RuleType): ProductionRules // NonTerminalSymbol(RuleType): ProductionRules // ... } lr1!宏将生成具有LR(1) DFA表的解析器结构。如果您想生成LALR(1)解析器，请使用lalr1!宏。宏中的每一行都必须遵循以下语法。引导，扩展引导是理解语法和生成代码的好例子。这是用RustyLR编写的RustyLR语法解析器。快速参考生产规则正则表达式模式 RuleType 减少操作在减少操作中访问标记数据感叹号 ! %tokentype %token %开始 %eof %userdata %left，%right %err，%error %derive %derive %glr 生产规则每个生产规则都有基本形式 NonTerminalName : Pattern1 Pattern2 ... PatternN { ReduceAction } | Pattern1 Pattern2 ... PatternN { ReduceAction } ... ; 每个Pattern都遵循以下语法 name：语法中定义的非终结符或终端符号name。 [term1 term_start-term_last]，[^term1 term_start-term_last]：终端符号的集合。《eof》将自动从终端集合中删除。 P*：零个或多个P的重复。 P+：一个或多个P的重复。 P?：零个或一个P的重复。 (P1 P2 P3)：模式的分组。 P / term，P / [term1 term_start-term_last]，P / [^term1 term_start-term_last]：前瞻；P后跟给定的终结符集合中的一个。前瞻不会被消耗。注意当使用范围模式 [first-last] 时，范围是通过 %token 指令的顺序构建的，而不是通过实际值。如果您按照以下顺序定义标记 %token one '1'; %token two '2'; ... %token zero '0'; %token nine '9'; 范围 [zero-nine] 将是 ['0', '9']，而不是 ['0'-'9']。 RuleType _^(可选) 可以为每个非终结符号分配一个值。在 reduce action 中，可以访问每个模式保持的值，并可以为新当前非终结符号分配新值。请参阅下面的 ReduceAction 和在 ReduceAction 中访问标记数据部分。在解析结束时，起始符号的值将是解析的结果。默认情况下，终结符号保留由 %tokentype 函数传递的值的 %tokentype。 struct MyType<T> { ... } E(MyType<i32>) : ... Patterns ... { <This will be new value of E> } ; ReduceAction _^(可选) Reduce action 可以用 Rust 代码编写。它在规则匹配并归约时执行。如果为当前非终结符号定义了 RuleType，则 ReduceAction 本身必须是 RuleType 的值（即语句末尾没有分号）。如果 RuleType 未定义，则可以省略 ReduceAction。生产规则中只有一个标记持有值。可以从 ReduceAction 返回 Result<(),Error>。返回的 Error 将传递给 feed() 函数的调用者。可以通过 %err 或 %error 指令定义 ErrorType。请参阅错误类型部分。 NoRuleType: ... ; RuleTypeI32(i32): ... { 0 } ; // RuleTypeI32 will be chosen E(i32): NoRuleType NoRuleType RuleTypeI32 NoRuleType; // set Err variant type to String %err String; %token div '/'; E(i32): A div a2=A { if a2 == 0 { return Err("Division by zero".to_string()); } A / a2 }; A(i32): ... ; 在减少操作中访问标记数据可以在 ReduceAction 中使用预定义变量。 data ( &mut UserData ) : 传递给 feed() 函数的用户数据。 lookahead ( &Term ) : 导致还原动作的预览令牌。要访问每个令牌的数据，可以直接使用令牌的名称作为变量。对于非终结符，变量的类型是 RuleType。对于终结符，变量的类型是 %tokentype。如果定义了多个同名的变量，将使用最前面的变量。您可以通过使用 = 操作符来重命名变量。 E(i32) : A plus a2=A { println!("Value of A: {:?}", A); println!("Value of plus: {:?}", plus); println!("Value of a2: {:?}", a2); A + a2 // new value of E }; 对于某些正则表达式模式，变量的类型将按如下方式修改 P* : Vec<P> P+ : Vec<P> P? : Option<P> 您仍然可以通过使用模式的基名来访问 Vec 或 Option。 E(i32) : A* { println!( "Value of A: {:?}", A ); // Vec<A> }; 对于终结符集 [term1 term_start-term_end]，[^term1 term_start-term_end]，没有预定义的变量名。您必须显式定义变量名。 E: digit=[zero-nine] { println!( "Value of digit: {:?}", digit ); // %tokentype }; 对于组 (P1 P2 P3) 如果没有任何模式持有值，该组本身将不持有任何值。如果只有一个模式持有值，该组将持有该模式的值。变量名将与模式相同。（即，如果 P1 持有值，而其他不持有，则 (P1 P2 P3) 将持有 P1 的值，并且可以通过名称 P1 访问）如果有多个模式持有值，该组将持有值的 Tuple。组没有默认变量名，您必须通过 = 操作符显式定义变量名。 NoRuleType: ... ; I(i32): ... ; // I will be chosen A: (NoRuleType I NoRuleType) { println!( "Value of I: {:?}", I ); // can access by 'I' I }; // ( i32, i32 ) B: i2=( I NoRuleType I ) { println!( "Value of I: {:?}", i2 ); // must explicitly define the variable name }; 感叹号 ! 可以在令牌后面直接使用感叹号 ! 来忽略令牌的值。该令牌将被视为不持有任何值。 A(i32) : ... ; // A in the middle will be chosen, since other A's are ignored E(i32) : A! A A!; 令牌类型 _{^{(必须定义)}} %tokentype <RustType> ; 定义终结符的类型。必须可以在宏调用点访问 <RustType>。 enum MyTokenType<Generic> { Digit, Ident, ... VariantWithGeneric<Generic> } lr! { ... %tokentype MyTokenType<i32>; } 令牌定义 _{^{(必须定义)}} %token name <RustExpr> ; 将映射终端符号 name 映射到实际值 <RustExpr>。在调用宏的位置，<RustExpr> 必须可访问。 %tokentype u8; %token zero b'0'; %token one b'1'; ... // 'zero' and 'one' will be replaced by b'0' and b'1' respectively E: zero one; 起始符号 _{^{(必须定义)}} %start NonTerminalName ; 将语法中的起始符号设置为 NonTerminalName。 %start E; // this internally generate augmented rule <Augmented> -> E eof E: ... ; Eof 符号 _{^{(必须定义)}} %eof <RustExpr> ; 定义终端符号 eof。在调用宏的位置，<RustExpr> 必须可访问。'eof' 终端符号将被自动添加到语法中。 %eof b'\0'; // you can access eof terminal symbol by 'eof' in the grammar // without %token eof ...; 用户数据类型 _^(可选) %userdata <RustType> ; 为 feed() 函数定义用户数据的类型。 struct MyUserData { ... } ... %userdata MyUserData; ... fn main() { ... let mut userdata = MyUserData { ... }; parser.feed( ..., token, &mut userdata); // <-- userdata feed here } 缩减类型 _^(可选) // reduce first %left term1 ; %left [term1 term_start-term_last] ; // shift first %right term1 ; %right [term1 term_start-term_last] ; 设置终端符号的移位/缩减优先级。 %left 可以缩写为 %reduce 或 %l，而 %right 可以缩写为 %shift 或 %r。 // define tokens %token plus '+'; %token hat '^'; // reduce first for token 'plus' %left plus; // shift first for token 'hat' %right hat; 错误类型 _^(可选) %err <RustType> ; %error <RustType> ; 为从 ReduceAction 返回的 Result<(), Err> 返回的错误定义类型。如果没有定义，将使用 DefaultReduceActionError。 enum MyErrorType<T> { ErrVar1, ErrVar2, ErrVar3(T), } ... %err MyErrorType<GenericType> ; ... match parser.feed( ... ) { Ok(_) => {} Err(err) => { match err { ParseError::ReduceAction( err ) => { // do something with err } _ => {} } } } 派生 _^(可选) 指定生成 Context 结构的派生属性。默认情况下，生成的 Context 不实现任何特质。但在某些情况下，您可能希望派生特质如 Clone、Debug 或 Serialize、Deserialize of serde。在这种情况下，用户必须确保 Context 的每个成员都必须实现该特质。目前，Context 正在持有堆栈数据，这是状态堆栈的 Vec<usize> 和语法中每个 RuleType 的 Vec<T>。 %derive Clone, Debug, serde::Serialize ; // here, #[derive(Clone,Debug)] will be added to the generated `Context` struct %derive Clone, Debug; ... let mut context = parser.begin(); // do something with context... println!( "{:?}", context ); // debug-print context let cloned_context = context.clone(); // clone context, you can re-feed the input sequence using cloned context GLR 解析器生成 %glr; 切换到 GLR 解析器生成。如果您想生成 GLR 解析器，在语法中添加 %glr; 指令。使用此指令，任何移位/缩减、缩减/缩减冲突都不会被视为错误。有关详细信息，请参阅 GLR 解析器部分。

依赖关系 ~195KB proc-macro2 rusty_lr_parser

宏 rusty_lr_derive

43 个版本 (17 个稳定版)

RustyLR

`features` in `Cargo.toml`

示例

可读的错误信息（带有 codespan）

特性

内容

过程宏

与 `build.rs` 集成

开始解析

GLR 解析器

解决歧义

关于GLR解析器的说明

语法

快速参考

生产规则

注意

RuleType _^(可选)

ReduceAction _^(可选)

在减少操作中访问标记数据

感叹号 `!`

令牌类型 _{^{(必须定义)}}

令牌定义 _{^{(必须定义)}}

起始符号 _{^{(必须定义)}}

Eof 符号 _{^{(必须定义)}}

用户数据类型 _^(可选)

缩减类型 _^(可选)

错误类型 _^(可选)

派生 _^(可选)

GLR 解析器生成

依赖关系

43 个版本 (17 个稳定版)

RustyLR

features in Cargo.toml

示例

可读的错误信息（带有 codespan）

特性

内容

过程宏

与 build.rs 集成

开始解析

GLR 解析器

解决歧义

关于GLR解析器的说明

语法

快速参考

生产规则

注意

RuleType (可选)

ReduceAction (可选)

在减少操作中访问标记数据

感叹号 !

令牌类型 (必须定义)

令牌定义 (必须定义)

起始符号 (必须定义)

Eof 符号 (必须定义)

用户数据类型 (可选)

缩减类型 (可选)

错误类型 (可选)

派生 (可选)

GLR 解析器生成

依赖关系

`features` in `Cargo.toml`

与 `build.rs` 集成

RuleType _^(可选)

ReduceAction _^(可选)

感叹号 `!`

令牌类型 _{^{(必须定义)}}

令牌定义 _{^{(必须定义)}}

起始符号 _{^{(必须定义)}}

Eof 符号 _{^{(必须定义)}}

用户数据类型 _^(可选)

缩减类型 _^(可选)

错误类型 _^(可选)

派生 _^(可选)