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）

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

特性

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

内容

• 过程宏
• 与build.rs集成
• 开始解析
• GLR解析器
• 语法

过程宏

以下提供了以下过程宏

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

这些宏将生成结构体

• Parser : 包含DFA表和产生式规则
• ParseError : Error的类型别名，从feed()返回
• Context : 包含当前状态和数据栈
• 枚举 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 标记的点）必须留下唯一的路径。

解决歧义

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

关于GLR解析器的说明

• 仍在开发中，尚未经过充分测试（欢迎提交补丁！）。
• 由于存在多个路径，reduce动作可能被多次调用，即使结果在将来会被丢弃。
  • 每个RuleType和Term都必须实现Clone特质。
• 用户必须注意shift/reduce或reduce/reduce冲突发生的位置。每当解析器发生分歧，计算成本都会增加。

语法

要开始编写上下文无关文法，首先需要定义必要的指令。这是过程宏的语法。

lr1! {
// %directives
// %directives
// ...
// %directives

// NonTerminalSymbol(RuleType): ProductionRules
// NonTerminalSymbol(RuleType): ProductionRules
// ...
}

lr1!宏将生成具有LR(1)有向图表的解析器结构。如果您想生成LALR(1)解析器，请使用lalr1!宏。宏中的每一行都必须遵循以下语法。

引导，扩展引导是理解语法和生成代码的好例子。这是用RustyLR本身编写的RustyLR语法解析器。

快速参考

• 产生式规则
• 正则表达式模式
• 规则类型
• Reduce动作
• 在Reduce动作中访问令牌数据
• 感叹号!
• %tokentype
• %令牌
• %起始
• %eof
• %用户数据
• %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 中访问令牌数据 部分。解析结束时，起始符号的值将是解析的结果。默认情况下，终结符号保留通过 feed() 函数传递的 %tokentype 的值。

struct MyType<T> {
    ...
}

E(MyType<i32>) : ... Patterns ... { <This will be new value of E> } ;

ReduceAction _^(可选)

reduce action 可以用 Rust 代码编写。在规则匹配并归约时执行。

• 如果为当前非终结符号定义了 RuleType，则 ReduceAction 本身必须是 RuleType 的值（即语句末尾没有分号）。

• 如果

  • RuleType 未定义，则可以省略 ReduceAction。
  • 生产规则中只保留一个令牌的值。

• Result<(),Error> 可以从 ReduceAction 返回。

  • 返回的 Error 将传递给 feed() 函数的调用者。
  • ErrorType 可以通过 %err 或 %error 指令定义。请参阅 错误类型 部分。

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): ... ;

在Reduce动作中访问令牌数据

可以在 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
};

E(i32) : A* {
    println!( "Value of A: {:?}", A ); // Vec<A>
};

E: digit=[zero-nine] {
    println!( "Value of digit: {:?}", digit ); // %tokentype
};

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> ;

enum MyTokenType<Generic> {
    Digit,
    Ident,
    ...
    VariantWithGeneric<Generic>
}

lr! {
...
%tokentype MyTokenType<i32>;
}

%token name <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 ;

%start E;
// this internally generate augmented rule <Augmented> -> E eof

E: ... ;

%eof <RustExpr> ;

%eof b'\0';
// you can access eof terminal symbol by 'eof' in the grammar
// without %token eof ...;

%userdata <RustType> ;

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] ;

// define tokens
%token plus '+';
%token hat '^';


// reduce first for token 'plus'
%left plus;

// shift first for token 'hat'
%right hat;

%err <RustType> ;
%error <RustType> ;

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
            }
            _ => {}
        }
    }
}

%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;