RustyLR

yacc 风格的 LR(1) 和 LALR(1) 确定性有限自动机 (DFA) 生成器，从上下文无关语法 (CFG) 生成。

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

features 在 Cargo.toml

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

示例

// 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 实现
• 可读的错误信息，包括语法构建和解析
• 从 CFG 在编译时构建 DFA
• 可自定义的减少操作
• 解决歧义语法的冲突
• 部分支持正则表达式模式
• 用于与 build.rs 集成的工具

内容

• 过程宏
• 与 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();

错误处理

feed() 函数返回两种错误类型

Invalid Terminal: *. Expected one of:  , (, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
>>> In:
	M -> M * • M
>>> Backtrace:
	M -> M • * M
>>> Backtrace:
	A -> A + • A
>>> Backtrace:
	A -> A • + A

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

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

NonTerminalName
    : Pattern1 Pattern2 ... PatternN { ReduceAction }
    | Pattern1 Pattern2 ... PatternN { ReduceAction }
   ...
    ;

%token one '1';
%token two '2';
...
%token zero '0';
%token nine '9';

struct MyType<T> {
    ...
}

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

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

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