RustyLR

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

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

features 在 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() 返回
• 上下文 : 包含当前状态和数据堆栈
• 枚举 NonTerminals : 非终结符号列表
• 规则 : 生成式规则的类型别名
• 状态 : 有向自动机（DFA）状态的类型别名

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

集成 build.rs

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

与过程宏不同，程序在输入文件中搜索 %%，而不是 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)将撤销当前路径。错误变体类型可以由%err指令定义。

关于GLR解析器的说明

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

语法

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

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

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

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

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

快速参考

• 生产规则
• 正则表达式模式
• RuleType
• 减少动作
• 在减少动作中访问标记数据
• 感叹号 !
• %tokentype
• %token
• %start
• %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 通过 feed() 函数传递的值。

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

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

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

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;