RustのパーサジェネレータLALRPOPに入門する(4. 重複するパタンのマッチをしたいときの問題点)

パーサジェネレータの続き。いろいろ試しているとこのツールの弱点を発見した。

• src/decimal_lalr.lalrpop

grammar;

pub PosInt: String = <p:r"[1-9][0-9]*"> => p.to_string();

pub Digit: String = <p:r"[0-9]*"> => p.to_string();

FIRRTLの文法の中に上記のようなものがる。これをテストすると生成するとどうなるだろうか。

processing file `/home/msyksphinz/work/training/program/rust/decimal_lalr/src/decimal_lalr.lalrpop`
/home/msyksphinz/work/training/program/rust/decimal_lalr/src/decimal_lalr.lalrpop:3:25: 3:38 error: ambiguity detected between the terminal `r#"[1-9][0-9]*"#` and the terminal `r#"[0-9]*"#`

--- stderr
  pub PosInt: String = <p:r"[1-9][0-9]*"> => p.to_string();
                          ~~~~~~~~~~~~~~

曖昧だと怒られてしまった。どうも、マッチ条件の中で別のルールに同じ条件を書いてしまうとこういうエラーになってしまうらしい。

これはLALRPOPのチュートリアルにも書いてある。

lalrpop.github.io

これをどう解決するかという話だが、これにはシンプルにmatch文を追加すればよいらしい。

match {
    r"[0-9]+"
} else {
    r"\w+",
    _
}

なので、上記のテストコードに対して書きのmatch文を追加した。

match {
  r"[1-9]",
} else {
  r"[0-9]",
  _
}

再度コンパイルしても、やはりエラーとなった。なんでだ？より詳細に書いてみる。

match {
  r"[1-9][0-9]*",
} else {
  r"[0-9]*",
  _
}

これならコンパイルが通った。テストを実行してみる。

• src/main.rs

#[macro_use] extern crate lalrpop_util;

lalrpop_mod!(pub decimal_lalr); // synthesized by LALRPOP

fn main() {
    println!("Hello, world!");
}


#[test]
fn decimal_lalr_test() {
    assert!(decimal_lalr::PosIntParser::new().parse("0").is_err());
    assert!(decimal_lalr::PosIntParser::new().parse("1").is_ok());
    assert!(decimal_lalr::PosIntParser::new().parse("10").is_ok());
    assert!(decimal_lalr::DigitParser::new().parse("0").is_ok());
    assert!(decimal_lalr::DigitParser::new().parse("1").is_ok());
    assert!(decimal_lalr::DigitParser::new().parse("10").is_ok());
}

$ cargo test

---- decimal_lalr_test stdout ----
thread 'decimal_lalr_test' panicked at 'assertion failed: decimal_lalr::DigitParser::new().parse("1").is_ok()', src/main.rs:16:5
note: Run with `RUST_BACKTRACE=1` for a backtrace.

うーん、これはダメだ。。。おそらく、match文のr"[1-9][0-9]"の方に先にマッチしてしまって、結局Digitのr"[0-9]"にはマッチしないということなのか。これは困った。

仕方がないので以下のように変えてみる。

pub PosInt: String = <p:r"[1-9]"><d:r"[0-9]*"> => p.to_string() + &d.string();
pub Digit: String = <p:r"[0-9]*"> => p.to_string();

これでもやはりr"[1-9]"とr"[0-9]"の曖昧性が解決できない。match文を突っ込んで強制的に解決させるとどうなるか。

pub PosInt: String = <p:r"[1-9]"><d:r"[0-9]*"> => p.to_string() + &d.string();
pub Digit: String = <p:r"[0-9]*"> => p.to_string();

match {
  r"[1-9]",
} else {
  r"[0-9]*",
  _
}

うぬぬ、やはりPassしない。

failures:

---- decimal_lalr_test stdout ----
thread 'decimal_lalr_test' panicked at 'assertion failed: decimal_lalr::PosIntParser::new().parse("1").is_ok()', src/main.rs:13:5
note: Run with `RUST_BACKTRACE=1` for a backtrace.

GitHub Issuesにもでているが、この問題はLALRPOPではよく登場する問題のようで、かなり工夫して書かないと駄目なようだ。どうしようかな、使い続けるかどうかは迷うところだ。

github.com