combine: マクロのいらないRustのパーサーコンビネーター

はじめに

Rustには有名なnomというパーサーコンビネーターライブラリがあるが、せっかく高級な型システムと最適化があるのにマクロで何とかしようとするのは勿体無いと思うので、マクロに深く依存しないcombineを使ってみた。

combineの主な特徴

• parsec リスペクトのパーサーコンビネーター
• コンビネーターはマクロではなく、 Parser traitを実装する値で表す
• バイトストリーム、文字(Unicodeコードポイント)ストリーム、トークンストリームの全てに対応
• メモリ上の文字列だけではなく、入力ストリームからの直接のパースにも対応

まだ計測はしていないが、 Box を多用していたりはしないので、速度的に大きく遅れをとるようなことはないのではないかと思う。

以下、parsecについて知っていたほうが読みやすい構成になっているので、必要ならparsecの資料を探して読むといいかもしれない。大雑把に言うと、1つの構文要素を1つの関数(現在位置を受け取って、成功/失敗と次の位置を返す)であらわす再帰下降パーサーというのがベースになっている。その構文解析関数を自力で書かなくても、既存の高階関数を組み合わせて手軽に書けるようにしたのがパーサーコンビネーターである。

基本的な使い方

Cargo.toml の中身

[dependencies]
combine = "2.2.2"
# これは必要なければ削除してもよい
combine-language = "2.0.0"

src/main.rs の中身

extern crate combine;

use combine::{Parser, many1};
use combine::char::digit;

fn main() {
    let mut parser = many1::<Vec<_>, _>(digit());
    println!("{:?}", parser.parse("123"));
    println!("{:?}", parser.parse("123ABC"));
    println!("{:?}", parser.parse("ABC123"));
}

実行結果

Ok((['1', '2', '3'], ""))
Ok((['1', '2', '3'], "ABC"))
Err(ParseError { position: 94191262981061, errors: [Unexpected(Token('A')), Expected(Borrowed("digit"))] })

成功した場合は、パース結果と、残り文字列が返される。

ポイント

次のようにしてパーサーを生成する。これは名前からわかるように数字の1個以上の並びを取得する。

let mut parser = many1(digit());

ここで、 digit() は関数呼び出しだが、ここではパーサーの生成が行われているだけで、この時点でパーサーが実行されているわけではない。

many1 は任意の FromIterator に変換できる。ここでは Vec<_> を使うため、それを明示している。

parser は mut でないといけない。これは勿論 parse(&mut self, ... だからだが、これは突き詰めればステートフルなパーサーを書くためだと思われる。

色々組み合わせる

parsecの (>>=) と return はそれぞれ .then と value という名前になっている。

// 何も読まずに1を返す
let mut parser = value(1);
assert_eq!(parser.parse("123"), Ok((1, "123")));

// 同じ文字2つの並びを読む
let mut parser = letter().then(|c| token(c));
assert_eq!(parser.parse("aa"), Ok(('a', "")));
assert!(parser.parse("11").is_err());
assert!(parser.parse("ab").is_err());

単に、パースした結果を変換したい場合は、 .map を使う。(parsecでいうところの fmap, (<$>))

// 数字の1つ以上の並びをパースして、数値として返す
let mut parser = many1::<String, _>(digit()).map(|s| s.parse::<u32>().unwrap());
assert_eq!(parser.parse("123"), Ok((123, "")));

左を試して、失敗したら右を試すには、.or を使う。 (parsecの (<|>) と同様、左で1文字以上消費して失敗したら右は試さない。)

// 整数をパース
let mut parser =
    token('-')
    .with(many1::<String, _>(digit()).map(|s| -s.parse::<i32>().unwrap()))
    .or(many1::<String, _>(digit()).map(|s| s.parse::<i32>().unwrap()));
assert_eq!(parser.parse("123"), Ok((123, "")));
assert_eq!(parser.parse("-123"), Ok((-123, "")));

上で使われている .with は左の結果を捨てて続けて右を読む (parsecの (*>) ) 。逆に、右の結果を捨てる (parsecの (<*)) ときは .skip を使う。使い方はほぼ同じ。

ポイント

汎用のコンビネーターは combine::combinator にある。また、文字用と後述するバイト用のコンビネーターはそれぞれ combine::char と combine::byte にある。

combine::combinator にあるコンビネーターは以下の方法でも利用できる。

• combine の直下に同じものがuseされていることがある。
• combine::Parser にメソッドとして実装されていることがある。メソッドチェーンとして書くのにも使える。

combineのコンビネーターはparsecと同じような感覚で使えるようになっているが、大きな違いが1つある。parsecのパーサー ParsecT s u m a は型コンストラクタである。したがって、例えば「 [Char] を読んで Int を返すパーサー」なら、中身によらず同じ型 Parsec [Char] () Int をもつ。

一方、combineのパーサー Parser はtrait(型クラスのようなもの)である。同じ「 &str を読んで i32 を返すパーサー」でも、パーサーの実装ごとに異なる型をもつ。

異なる実装のパーサーを同じように扱いたいということがもしあるならば、trait objectを使って Box<Parser<Input=&'a str, Output=i32>> のように書くことは可能である。

再利用と再帰

再利用可能なパーサーを書くときは、慣習的には以下の手順を踏む。

1. そのパーサーをあらわす型を struct で作る。
2. その実装を impl で書く。
3. そのパーサーを生成する関数を fn で書く。

例えば、先ほど作成した非負整数パーサーは以下のように書く。

// 非負整数パーサーをあらわす型
struct Unsigned<I>(PhantomData<fn(I) -> I>);

// 非負整数パーサーの実装
impl<I> Parser for Unsigned<I> where I: Stream<Item=char> {
    type Input = I;
    type Output = u32;
    #[inline]
    fn parse_stream(&mut self, input: I) -> ParseResult<Self::Output, Self::Input> {
        // 基本的な書き方: ラップしたいパーサーをその場で生成し、parse_streamを移譲するだけ。
        let mut parser = many1::<String, _>(digit()).map(|s| s.parse::<u32>().unwrap());
        parser.parse_stream(input)
    }
}

// 非負整数パーサーを返す関数
fn unsigned<I>() -> Unsigned<I> where I: Stream<Item=char> {
    Unsigned(PhantomData)
}

これを使うと以下のように整数パーサーを書ける。

// 整数をパース
let mut parser =
    token('-').with(unsigned()).map(|x| -(x as i32))
    .or(unsigned().map(|x| x as i32));
assert_eq!(parser.parse("123"), Ok((123, "")));
assert_eq!(parser.parse("-123"), Ok((-123, "")));

上のような方法を使えば、再帰的なパーサーを書くこともできる。ただし、単に再帰的なパーサーがほしいだけなら、より簡単な方法がある。

parser 関数を使うと、関数やクロージャをパーサーに変換できる。これを使えば、例えば括弧の対応がとれている文字列をパースする以下のようなパーサーが書ける。

// 括弧の対応
fn paren<I>(input: I) -> ParseResult<(), I> where I: Stream<Item=char> {
    let mut parser =
        token('(').with(parser(paren::<I>)).skip(token(')'))
        .or(token('[').with(parser(paren::<I>)).skip(token(']')))
        .or(value(()));
    parser.parse_stream(input)
}

これは以下のように使える。

let mut parser = parser(paren);
assert_eq!(parser.parse("[()]"), Ok(((), "")));
assert!(parser.parse("[(])").is_err());

エラー処理

combineはparsecと似たバックトラック規則を採用している。つまり、

• 1文字も消費せずに失敗したら、バックトラックする。
• 1文字以上消費して失敗したら、バックトラックをせずに全体も失敗とする。

したがって以下は失敗する。

// 2AHのような16進数か、20Dのような十進数を受理しようとしている
let mut parser =
    many1::<String, _>(hex_digit()).skip(char('H'))
    .or(many1::<String, _>(digit()).skip(char('D')));
// バックトラックしないため、マッチしない
println!("{:?}", parser.parse("123D"));

Err(ParseError { position: 94623997271456, errors: [Unexpected(Borrowed("end of input")), Expected(Token('H'))] })

この規則の例外が必要な場合は、 try を使う。 try で包まれたパーサーは失敗した場合は1文字も消費しなかったことになる。

// 2AHのような16進数か、20Dのような十進数を受理する
let mut parser =
    try(many1::<String, _>(hex_digit()).skip(char('H')))
    .or(try(many1::<String, _>(digit()).skip(char('D'))));
println!("{:?}", parser.parse("123D"));

Ok(("123", ""))

.expected を使うと、バックトラック時に “Expected …” という形のエラーメッセージを付与できる。しばしば try と併用される (と思われる。)

// 2AHのような16進数か、20Dのような十進数を受理する
let mut parser =
    try(many1::<String, _>(hex_digit()).skip(char('H'))).expected("hexadecimal number")
    .or(try(many1::<String, _>(digit()).skip(char('D'))).expected("decimal number"));
println!("{:?}", parser.parse("123"));

Err(ParseError { position: 94647351694019, errors: [Unexpected(Borrowed("end of input")), Expected(Token('H')), Expected(Token('D')), Unexpected(Token('1')), Expected(Borrowed("hexadecimal number")), Expected(Borrowed("decimal number"))] })

当たり前だが try を増やせばバックトラックが増えるのでパフォーマンスが落ちる可能性がある。あくまで、できるだけ先読みのいらない形でパースするのが望ましいだろう。 try の典型的な利用方法の1つは、字句解析と構文解析がわかれているような言語における「字句」のパーサーであると考えられる。

バイトパーサー

ここまでは、Unicodeのコードポイントごとに処理をするパーサーを扱った。combineでは、文字に限らず、何かが並んでいればそれをパースすることができる。何かの並びは Stream というtraitであらわされる。文字の並びは Stream<Item=char>, バイトの並びは Stream<Item=u8> である。

例えば以下のように &[u8] に対して構文解析を実行できる。

let mut parser =
    many1::<Vec<_>, _>(combine::byte::digit());
assert_eq!(parser.parse(&b"123ABC"[..]), Ok((vec![49, 50, 51], &[65, 66, 67][..])));

ストリームパーサー

combineでは&[u8]ã‚„&strのように既に全体がメモリ上に読み込まれているもの以外にも、特定の入力ストリームから必要に応じてトークンを読み込むようなパーサーを書くことができる。それには Stream を実装する他の型を使えばよい。

例えば、標準入力のように Read を実装するものに対してバイト単位で構文解析をするには、from_read と BufferedStream を使うことができる。

let stdin = std::io::stdin();
let stdin = stdin.lock();
// 先読み10文字
let stdin_stream = BufferedStream::new(from_read(stdin), 10);
let stdin_stream = stdin_stream.as_stream();

// 英数字と空白以外がくるまで読み続ける
let mut parser = many1::<Vec<_>, _>(combine::byte::alpha_num().or(combine::byte::space()));
println!("{:?}", parser.parse(stdin_stream));

実行すると、英数字と空白(改行を含む)がくる間はストリームから読み続ける。それ以外の文字が来た時点で読み込みが停止される。

ポイント

Stream 自体は簡単で、インターフェースを見れば一目瞭然である。しかし実際のストリームパーサーの実装はもう少し複雑である。

まず、 Stream が単に StreamOnce + Clone であることに注意する。また StreamOnce は Iterator に位置記憶機能がついたものに過ぎない。

StreamOnce は Read をラップする (from_read) ことで簡単に実現できる。しかしこれでは Clone が足りない。 Clone が必要なのはもちろん、バックトラックのためである。

そのために、StreamOnce をラップして Stream を作成する一般的な仕組みが提供されている。それが BufferedStream である。

ストリーム本体はもちろん複製できないので、 BufferedStream はストリーム本体の特定位置を参照するだけの簡単なデータ構造としてふるまう。例えば、3つの BufferedStream が同じストリームの位置50, 位置80, 位置110を参照するといったことが考えられる。このとき、ストリーム本体は位置110まで読み込み済みの状態である。

このとき位置50のストリームから読み直したいということがありえる。そのために、ストリーム本体から読み出したデータは共有の先読みバッファに保存される。先読みバッファの自動解放をするにはより複雑な仕組みが必要なので、ここでは固定サイズのバッファを確保しておき、先読みバッファから溢れた部分を読み出そうとした場合はエラーとなる。

Read を使ってバイトストリームではなく文字ストリーム Stream<Item=char> を得るのは少し面倒そうだ。 Read::chars() を参考に自分で実装してしまうほうが楽かもしれない。

トークンパーサー

parsec同様、あまり真面目にサポートされているかというと微妙だが、一度字句解析器がトークン列を生成し、その後で構文解析器がトークン列を解析する、というような実装も可能である。

これも実装方法によって難易度が異なる。「トークン列を一度メモリ上に全部展開する」「位置情報を保持しない」という条件ならそれほど難しくない。

extern crate combine;

use combine::char::{char, digit, spaces};
use combine::{many, many1, Parser, eof, sep_by1, satisfy_map};

#[derive(Debug, Copy, Clone, PartialEq, Eq)]
enum Token {
    Number(u32),
    Plus,
}

fn lex(s: &str) -> Vec<Token> {
    let number = many1::<String, _>(digit()).map(|s| Token::Number(s.parse::<u32>().unwrap()));
    let plus = char('+').map(|_| Token::Plus);
    let mut parser =
        spaces().with(many(number.or(plus).skip(spaces()))).skip(eof());
    parser.parse(s).map(|x| x.0).unwrap()
}

fn eval(s: &str) -> u32 {
    let tokens = lex(s);

    let number = satisfy_map(|t| match t {
        Token::Number(x) => Some(x),
        _ => None,
    });
    let plus = satisfy_map(|t| match t {
        Token::Plus => Some(()),
        _ => None,
    });
    let mut parser = sep_by1::<Vec<_>, _, _>(number, plus).map(|v| v.iter().sum());
    parser.parse(&tokens[..]).unwrap().0
}

fn main() {
    println!("{:?}", lex("1"));
    println!("{:?}", lex(" 1 + 2 "));
    println!("{:?}", lex("100    +    200+323"));
    println!("{:?}", eval("1"));
    println!("{:?}", eval(" 1 + 2 "));
    println!("{:?}", eval("100    +    200+323"));
}

combine-language

combine-languageを使うと、典型的なプログラミング言語のlexerを自動で生成できる。これもparsecのText.Parsec.Tokenと似た機能を提供するものである。

combine-languageを使って簡易的な電卓プログラム(四則演算パーサー)を書くと以下のようになる。

extern crate combine;
extern crate combine_language;

use combine::char::{string, letter, alpha_num};
use combine::{Parser, satisfy, Stream, ParseResult, parser, chainl1};
use combine_language::{LanguageEnv, LanguageDef, Identifier};

#[derive(Debug, Clone, PartialEq, Eq)]
enum Expr {
    Number(i64),
    Plus(Box<Expr>, Box<Expr>),
    Minus(Box<Expr>, Box<Expr>),
    Times(Box<Expr>, Box<Expr>),
    Divides(Box<Expr>, Box<Expr>),
}

fn calc_env<'a, I>() -> LanguageEnv<'a, I> where I: Stream<Item=char>, I: 'a {
    LanguageEnv::new(LanguageDef {
        ident: Identifier {
            start: letter(),
            rest: alpha_num(),
            reserved: ["if", "then", "else", "let", "in", "type"].iter()
                                                                 .map(|x| (*x).into())
                                                                 .collect(),
        },
        op: Identifier {
            start: satisfy(|c| "+-*/".chars().any(|x| x == c)),
            rest: satisfy(|c| "+-*/".chars().any(|x| x == c)),
            reserved: ["+", "-", "*", "/"].iter().map(|x| (*x).into()).collect()
        },
        comment_start: string("/*").map(|_| ()),
        comment_end: string("*/").map(|_| ()),
        comment_line: string("//").map(|_| ()),
    })
}

// 整数または括弧で括られた式
fn factor<I>(input: I) -> ParseResult<Box<Expr>, I> where I: Stream<Item=char> {
    let env = calc_env();
    let number = env.integer().map(|x| Box::new(Expr::Number(x)));
    let parenthesized = env.parens(parser(expr));
    number.or(parenthesized).parse_stream(input)
}

// 掛け算・割り算またはfactor
fn term<I>(input: I) -> ParseResult<Box<Expr>, I> where I: Stream<Item=char> {
    let env = calc_env();
    let op = env.reserved_op("*").or(env.reserved_op("/"))
        .map(|op| move |lhs, rhs| {
        if op == "*" {
            Box::new(Expr::Times(lhs, rhs))
        } else if op == "/" {
            Box::new(Expr::Divides(lhs, rhs))
        } else { unreachable!() }
    });
    chainl1(parser(factor), op)
        .parse_stream(input)
}

// 全ての式
fn expr<I>(input: I) -> ParseResult<Box<Expr>, I> where I: Stream<Item=char> {
    let env = calc_env();
    let op = env.reserved_op("+").or(env.reserved_op("-"))
        .map(|op| move |lhs, rhs| {
        if op == "+" {
            Box::new(Expr::Plus(lhs, rhs))
        } else if op == "-" {
            Box::new(Expr::Minus(lhs, rhs))
        } else { unreachable!() }
    });
    chainl1(parser(term), op)
        .parse_stream(input)
}

fn main() {
    let mut parser = parser(expr);
    println!("{:?}", parser.parse("1 + 2 * 3"));
}

行番号と列番号

行番号や列番号を取得するには、ステートフルな字句解析器を用意するという方法が考えられる。その他に、以下のようにして Stream に1枚噛ませても実装できる。

extern crate combine;

use combine::char::{string, letter, alpha_num, space};
use combine::{Parser, satisfy, Stream, ParseResult, parser, chainl1, StreamOnce, many1, eof};

#[derive(Debug, Clone)]
pub struct CRStream<I> {
    inner: I,
    rownum: usize,
    rowpos: usize,
}

impl<I> CRStream<I> where I: Stream<Item=char, Position=usize> {
    pub fn new(inner: I) -> Self {
        let rowpos = inner.position();
        CRStream {
            inner: inner,
            rownum: 0,
            rowpos: rowpos,
        }
    }
}

impl<I> StreamOnce for CRStream<I> where I: Stream<Item=char, Position=usize> {
    type Item = I::Item;
    type Range = I::Range;
    type Position = (usize, usize);
    fn uncons(&mut self) -> Result<Self::Item, combine::primitives::Error<Self::Item, Self::Range>> {
        let c = try!(self.inner.uncons());
        if c == '\n' {
            self.rownum += 1;
            self.rowpos = self.inner.position();
        }
        Ok(c)
    }
    fn position(&self) -> Self::Position {
        (self.rownum, self.inner.position() - self.rowpos)
    }
}

fn main() {
    // 英数字と空白のみからなる文字列を受理する
    let mut parser = many1::<Vec<_>, _>(alpha_num().or(space())).skip(eof());
    println!("{:?}", parser.parse("hoge"));
    println!("{:?}", parser.parse("hoge+fuga"));
    println!("{:?}", parser.parse("h\nge+fuga"));

    // 英数字と空白のみからなる文字列を受理する
    let mut parser = many1::<Vec<_>, _>(alpha_num().or(space())).skip(eof());
    println!("{:?}", parser.parse(CRStream::new("hoge")));
    println!("{:?}", parser.parse(CRStream::new("hoge+fuga")));
    println!("{:?}", parser.parse(CRStream::new("h\nge+fuga")));
}

Position は Ord を実装することに注意すること。ここでは (row, column) を返しているが、タプルの順序は辞書順であるため、この Ord 構造は構文解析の向きと整合している。

まとめ

combineは、parsecのような利便性・汎用性と、Rustのライブラリに求められるゼロ抽象化を両立しようとしている。Rustの強力な型システムをうまく活用することで、これらは十分に実現できているように思う。

一方で、parsecに比べて不便な点や、現時点で必要なインターフェースが不足している点も感じられた。また、型エラーの解決は決して簡単ではない。Rustの型システムに慣れていなければなおさら躓きやすいかもしれない。

個人的には、マクロを駆使している nom よりも好印象であった。