pidgin

构建非递归语法

Pidgin 是一个 Rust 库，用于生成非递归语法，允许将字符串转换为解析树。

Pidgin 的语法在底层作为带有命名匹配组的正则表达式实现。Rust 的正则表达式引擎非常快，但它有一个限制，这使得解析具有重复组件的层次结构模式变得困难：您不能在模式中多次使用特定的匹配名称。这使得一个简单的语法，如

foo -> bar baz | baz bar
bar -> '1'
baz -> '2'

有问题的。规则 foo 两次使用 bar 和 baz。

Pidgin 允许您通过管理组重命名来绕过这个限制。

正则表达式的另一个缺点是，它们越有表现力，就越难阅读。Pidgin 允许您构建具有表现力的正则表达式，而不会模糊您的意图。

示例

#![recursion_limit="256"]
#[macro_use]
extern crate pidgin;

fn experiment() -> Result<(), Box<Error>> {
    let date = grammar!{
    
        // comments are legal in grammars
    
        (?ibB)   // default flags for all rules -- case insensitive and enforce leading and trailing word boundaries
    
        // the master rule; it has multiple alternates
        date -> <weekday> (",") <month> <monthday> (",") <year>
        date -> <month> <monthday> | <weekday> | <monthday> <month> <year>
        date -> <month> <monthday> (",") <year>
        date -> <numeric_date>
    
        // sub-rules
    
        numeric_date -> <year> ("/") <numeric_month> ("/") <numeric_day>
        numeric_date -> <year> ("-") <numeric_month> ("-") <numeric_day>
        numeric_date -> <numeric_month> ("/") <numeric_day> ("/") <year>
        numeric_date -> <numeric_month> ("-") <numeric_day> ("-") <year>
        numeric_date -> <numeric_day> ("/") <numeric_month> ("/") <year>
        numeric_date -> <numeric_day> ("-") <numeric_month> ("-") <year>
    
        year    => r(r"\b[12][0-9]{3}|[0-9]{2}\b")
        weekday => [
                "Sunday Monday Tuesday Wednesday Thursday Friday Saturday"
                    .split(" ")
                    .into_iter()
                    .flat_map(|s| vec![s, &s[0..2], &s[0..3]])
                    .collect::<Vec<_>>()
            ]
        weekday     => (?-i) [["M", "T", "W", "R", "F", "S", "U"]]
        monthday    => [(1..=31).into_iter().collect::<Vec<_>>()]
        numeric_day => [
                (1..=31)
                    .into_iter()
                    .flat_map(|i| vec![i.to_string(), format!("{:02}", i)])
                    .collect::<Vec<_>>()
            ]
        month => [
                vec![
                    "January",
                    "February",
                    "March",
                    "April",
                    "May",
                    "June",
                    "July",
                    "August",
                    "September",
                    "October",
                    "November",
                    "December",
                ].into_iter().flat_map(|s| vec![s, &s[0..3]]).collect::<Vec<_>>()
            ]
        numeric_month => [
                (1..=31)
                    .into_iter()
                    .flat_map(|i| vec![i.to_string(), format!("{:02}", i)])
                    .collect::<Vec<_>>()
            ]
    };

    // compile this into a matcher
    // (uncompiled grammar's can be used as elements of other grammars)
    let matcher = date.matcher()?;
    
    // we let whitespace vary
    assert!(matcher.is_match(" June   6,    1969 "));

    // we made it case-insensitive
    assert!(matcher.is_match("june 6, 1969"));

    // but we want to respect word boundaries
    assert!(!matcher.is_match("jejune 6, 1969"));

    // we can inspect the parse tree
    let m = matcher.parse("2018/10/6").unwrap();
    assert!(m.name("numeric_date").is_some());
    assert_eq!(m.name("year").unwrap().as_str(), "2018");

    let m = matcher.parse("Friday").unwrap();
    assert!(!m.name("numeric_date").is_some());
    assert!(m.name("weekday").is_some());

    // still more crazy things we allow
    assert!(matcher.is_match("F"));
    assert!(matcher.is_match("friday"));
    assert!(matcher.is_match("Fri"));

    // but we said single-letter days had to be capitalized
    assert!(!matcher.is_match("f"));

    Ok(())
}

局限性

递归

因为您必须在使用之前定义子语法，也因为 Rust 的正则表达式引擎和形式无法在任何情况下表示它，所以您不能在 Pidgin 中生成递归语法。类似这样的东西是不可能的

XP -> XP conj XP

正则表达式元素中的命名捕获

Pidgin 允许您向规则提供正则表达式元素。这样的元素是一个 Rust 表达式，可以通过 grammar! 宏体中的 r( 和 ) 转换为 String，通过 to_string 进行括号化，例如 r(r"\d+")。正则表达式元素允许您将正则表达式插入语法中，而语法形式本身不提供，如锚点和字符类。

Rust的正则表达式引擎不允许在命名捕获组中重复使用名称。然而，以下代码 (?<foo>bar) baz (?<foo>qux) 无法编译成一个可用的正则表达式，因为名称“foo”被重复使用。下面的语法产生了这种情况。

grammar!{
    TOP -> <foo> ("bar") <foo>
    foo => r("(?P<baz>foo)")
};

解决方案是在语法正则表达式元素中避免使用命名捕获组。语法本身将处理命名捕获，因此您永远不需要这样做。

基准测试

Pidgin背后的主要动机只是产生一个类似于抽象语法树的东西，可以用来更好地理解匹配的文本，但其[vec]元素生成的正则表达式通常与或优于以表达式交替表示的简单构造的正则表达式只要表达式是有界的。"有界"在这里意味着表达式必须匹配字符串的第一个字符到最后一个字符。一个无界表达式只需要在字符串的某个地方匹配。

// good
let rx = regex::Regex::new("\A(?:cat|camel|canteloupe)\z").unwrap();

// better!
let rx = grammar!{ TOP => r("\A") [["cat", "camel", "canteloupe"]] r("\z") }.rx().unwrap();

在无界的情况下，简单的正则表达式性能更好。

在benches/目录中包含了一个简单的基准测试套件，演示了这一点。该套件比较了形式为 foo|bar|baz 的"简单"正则表达式的匹配速度与Pidgin生成的正则表达式，后者不涉及回溯，在这个例子中，可能是 foo|ba[rz]。基准测试套件比较了非匹配与匹配以及有界与无界模式。这些8个案例的平均匹配/非匹配时间是

每对中较好的时间加粗显示。

运行以下命令可以生成完整报告

cargo bench

完整API

完整的Pidgin API可在https://docs.rs/pidgin/找到。

致谢

在撰写本文时，我得到了TurkeyMcMac的许多建议。