Sun Jun 26 21:16:15 JST 2016

参考

Rust でパーザコンビネータを書く

扱いやすさのために、入力となる文字列を全て Vec<char> と仮定する.
パーザは、 Vec<char> を入力として受け取り、消費した (読んだ) 分と、まだ読んでない分のペア (Vec<char>, Vec<char>) を返す関数である.
ただし、パースは常に成功するとは限らないので、それを更に Option で包む. この返す型を ParseResult とする.
したがって、パーザは Vec<char> を取って ParseResult を返す関数であるが、都合上、それを Box に包んでしかも Parser と名付けた struct で包む.

type ParseResult = Option<(Vec<char>, Vec<char>)>;
struct Parser(Box<Fn(&Vec<char>) -> ParseResult>);

関数型っぽく書く場合は、入力は参照 & 付けて読めば大体いい気がする.

基本パーザ

参考スライドにしたがって、1文字だけを読むパーザ (one_of) と頭の何文字化を読むパーザ (string) を実装する.

one_of

頭の一文字を与えて、消費させるパーザを作る.

fn one_of(c: char) -> Parser {
    Parser(Box::new(move |cs: &Vec<char>| {
        if cs.len() == 0 || cs[0] != c {
            None
        } else {
            Some((vec![c], cs[1..].to_owned()))
        }
    }))
}

文字 c を受け取って次のようなパーザ (Parser) を返す. パーザは文字列 cs を受け取って、頭の一文字が c と一致したら、それを消費して、残り (cs[1..]) を消費せずに返す. 頭が一致しないか、そもそも cs が長さ0の場合は頭が無いので失敗 None を返す.

パーザの適用

作ったパーザが正しく動作するかを確認したいので、先に、パーザを文字列に適用するメソッドを実装する.

impl Parser {
    fn call(&self, s: String) -> ParseResult {
        let Parser(ref f) = *self;
        let chars = s.chars().collect::<Vec<_>>();
        f(&chars)
    }
}

パーザ (self) の中身を let Parser(ref f) = ... の部分で f という名前を付けて取り出す. Boxに包んでるが、そのまま関数として使えば良い. わざわざ ref で関数を参照してるのは、parser を繰り返し何度も利用するため (借用のアレ).

先ほどの one_of を使ってみる.

    let parser = one_of('a');
    let s = String::from("abc");
    println!("{:?}", parser.call(s));

=>

Some((['a'], ['b', 'c']))

string

fn string(s: String) -> Parser {
    let ds: Vec<char> = s.chars().collect();
    Parser(Box::new(move |cs: &Vec<char>| {
        let n = ds.len();
        if cs.len() < n { return None }
        for i in 0..n {
            if ds[i] != cs[i] { return None }
        }
        Some((ds.to_owned(), cs[n..].to_owned()))
    }))
}

基本的に one_of と同じ.

合成コンビネータ

選択 choose /

2つのパーザを与えて、1つめを試して成功したらそれを返す. 失敗したら2つ目を返す、というパーザを生成するコンビネータを実装する.

先に使い方を述べると

    let parser = one_of('a') / one_of('b'); // 'a' を読む. 失敗したら、'b' を読む
    {
        let s = String::from("abc");
        println!("{:?}", parser.call(s));
    }
    {
        let s = String::from("bbc");
        println!("{:?}", parser.call(s));
    }
    {
        let s = String::from("cbc"); // fails
        println!("{:?}", parser.call(s));
    }

結果は順に

Some((['a'], ['b', 'c']))
Some((['b'], ['b', 'c']))
None

適用する関数を先に述べたので、それを使えばいいだけ. 1つめを適用して、 None を返したら2つめの適用した結果を返す. choose という名前の関数として実装する.

fn choice(p1: Parser, p2: Parser) -> Parser {
    let Parser(f1) = p1;
    let Parser(f2) = p2;
    Parser(Box::new(move |cs: &Vec<char>| {
        if let Some(a) = f1(&cs) {
            Some(a)
        } else {
            f2(&cs)
        }
    }))
}

ちょっと詰まりポイントとしては、f1(cs)cs があっちに行っちゃって使えなくなるので clone を渡す. てか普通に、入力を参照で受け取るようにパーザを定義すればよかったなぁ. 今更いっか.

演算子 / で書けたほうがちょっとかっこいいので、演算子オーバーロードする.

use std::ops::Div;
impl Div for Parser {
    type Output = Parser;
    fn div(self, rhs: Parser) -> Parser { choice(self, rhs) }
}

連接 then +

今度は、2つのパーザを順に適用するというパーザを生成する. どっちかでパースに失敗すれば、全体としても失敗とする.

choose をちょっと書き直すだけでいい.

fn then(p1: Parser, p2: Parser) -> Parser {
    let Parser(f1) = p1;
    let Parser(f2) = p2;
    Parser(Box::new(move |cs: &Vec<char>| {
        if let Some((xs, ys)) = f1(&cs) {
            if let Some((xs2, ys2)) = f2(&ys) {
                let mut mxs = xs.clone();
                let mut mxs2 = xs2.clone();
                mxs.append(&mut mxs2);
                return Some((mxs.to_owned(), ys2))
            }
        }
        None
    }))
}

use std::ops::Add;
impl Add for Parser {
    type Output = Parser;
    fn add(self, rhs: Parser) -> Parser { then(self, rhs) }
}

    let parser = (string(String::from("A")) / string(String::from("The"))) + one_of(' ') + string(String::from("cat"));
    {
        let s = String::from("My cat"); // fails
        println!("{:?}", parser.call(s));
    }
    {
        let s = String::from("The cat");
        println!("{:?}", parser.call(s));
    }
}
None
Some((['T', 'h', 'e', ' ', 'c', 'a', 't'], []))

ていうか毎回 String::from つけるのだるい.

src