Marwes/combine: A parser combinator library for Rust
Parsecに影響を受けて作られたパーサコンビネータだそうです。
Rustでパーサコンビネータといえばnomといった風潮ですが、combineはトレイトを中心にしたRustらしい実装であり、マクロでパーサを記述するnomと違ってRustのシンタックスで書けます。
この記事では設定ファイル記述言語であるTOMLで定義されているリテラル数値・文字列の文法を例にパーサを書いてみます。
なお、以下のようなものを自力で実装する必要はあまり無くて、言語実装に必要なパーサはcombine-languageというクレートでもっと網羅的に提供されています。
Parserトレイト
combineでは、パーサはParserトレイトを実装した型として表され、コンビネータでParserを組み合わせていくことで大きなパーサを作っていくことができます。Parserトレイトは入力、出力の型を関連型として持っており、parseメソッドに入力を渡すとOk((出力, 入力の残り))あるいはErr(パースエラー)が返るようになっています。
例えば数値のパーサなら、"123"という文字列をparseメソッドに渡すとOk((123, ""))を返すわけです。
pub trait Parser {
type Input: Stream;
type Output;
// fn (入力) -> Result<(出力, 入力の残り), パースエラー>
fn parse(&mut self, input: Self::Input)
-> Result<(Self::Output, Self::Input), ParseError<Self::Input>>;
// 他のparse_*はここでは気にしない
// コンビネータやエラー処理のためのメソッドが続く
// and, or, map, with, skip, ...
// message, expected, ...
...
}
このParserトレイトを中心に、処理の組み合わせをMap Andなどのアダプタ型で表す、IteratorやFutureなどと同じようなデザインです。
パーサの入力型として使えるものは文字列&strやスライス&[T]、IteratorStreamなどです。また文字列(あるいはバイト列&[u8])をStateでラップしたものも入力として使え、オーバーヘッドが増える代わりにパーサ内から行・桁(バイト列の場合はバイトオフセット)の取得が可能になり、エラー発生時にはエラー位置がそれで表示されるようになります。
整数リテラルをパースしてみる
TOMLの整数リテラルは符号付き64bit整数だそうです。文字列を入力するとi64を出力するパーサを作ります。
ここでは分かりやすいように個別にインポートしていますが、普通にuse combine::*;してしまえば良いかと思います。
符号
まずは数字の前に付く符号のパーサから。combine::tokenは引数で与えられた1要素にマッチして、それをそのまま出力するパーサです。文字列を入力とするパーサでは1要素=1文字(char)です。
また、+と-の2通りの可能性をParser::orで振り分けます。orは「このパーサが失敗したら別のパーサを試す」というパーサを返します。
当然ですが、両方のパーサの出力が同じ型である必要があります。
use combine::{Parser, token};
let sign = token('+').or(token('-'));
// Output = char
これで+か-にマッチし、マッチした文字を返すというパーサになっています。
orは以下のような感じで繋げていけば、1が失敗したら2、2も失敗したら3というパーサを作ることができます。
parser1.or(parser2).or(prser3)
任意の数のパーサから選択したい場合は、パーサの配列を受け取るcombine::choiceが使えます。
注意点
ここで注意が必要なのが、パフォーマンスの向上をはかるため、LL(1)でない、つまり1文字以上の先読みが必要な文法をパースするにはtryコンビネータ1が必要となっている点です。a.or(b)などとしていてaが複数の文字を読んでから失敗すると、失敗した時点で残っている入力が後続のパーサに渡されることになります。try(a).or(b)のようにtryで包めばよしなにしてくれます。
数字列
次に数字列のパーサ。
use combine::{Parser, many1};
use combine::char::digit;
let number = many1::<Vec<char>, _>(digit())
// Output = Vec<char>
many1に型引数を与えていますが(他の箇所から推論できるなら不要)、これはmany1に渡したパーサを複数回適用した結果を格納するためのコレクション型です。FromIterator<char>を実装していれば何でも構わないので、Vec<char>、String、HashSet<char>などが使えます。イテレータの.collect()と同じですね。
次に、各桁の数字が入ったVec<char>をi64に変換する関数をmapします。これで符号のない整数のパーサができました。
let number = many1::<Vec<char>, _>(digit())
.map(|ds| {
ds.into_iter()
.map(|c| c.to_digit(10).unwrap() as i64)
.fold(0, |acc, x| acc * 10 + x)
});
// Output = i64
この2つのパーサを合体して、符号付き整数のパーサを作ります。符号は省略できるので、optionalを適用しておきましょう。パーサがパースに失敗する場合でも、optionalで包めば失敗する代わりにNoneが出力されます。
use combine::optional;
(optional(sign), number)
// Output = (Option<char>, i64)
Parserトレイトはパーサのタプルに対しても実装されています。各要素のパーサを順番に適用し、それぞれの結果をまたタプルにして返すパーサになります。
Parser::andを使うこともできます(2要素のタプルと同じです)。
optional(sign).and(number)
// Output = (Option<char>, i64)
あとは、符号Option<char>を見てi64の符号を反転させる関数をmapすればおしまい。
use combine::optional;
let signed_number = (optional(sign), number)
.map(|(s, num)| {
match s {
None | Some('+') => num,
Some('-') => -num,
_ => unreachable!(),
}
});
試してみる
ここまでで作った符号付き整数パーサを試してみましょう。
extern crate combine;
use combine::{Parser, token, optional, many1};
use combine::char::digit;
fn main() {
let sign = optional(token('+').or(token('-')));
let number = many1::<Vec<char>, _>(digit())
.map(|ds| {
ds.into_iter()
.map(|c| c.to_digit(10).unwrap() as i64)
.fold(0, |acc, x| acc * 10 + x)
});
let mut signed_number = (sign, number)
.map(|(s, num)| {
match s {
None | Some('+') => num,
Some('-') => -num,
_ => unreachable!(),
}
});
println!("{:?}", signed_number.parse("-1024"));
}
Parser::parseを呼ぶにはmutでなくてはならないことに注意してください。普通はパーサの状態は変化しませんが、エラー処理に必要だったり、状態を持つパーサを作りたい場合があったりするためです(ドキュメントにstring interiningを行う例が載っています)。
Ok((-1024, ""))
パースに成功して、結果と残りの文字列が出てきました。次は、わざとパースエラーを発生させてみましょう。ParseErrorはDisplayを実装しているので、unwrap_errでエラーを取り出して表示してみます。
println!("{}", signed_number.parse("abc").unwrap_err());
Parse error at 94543405371245
Unexpected `a`
Expected `digit`
なんとポインタでエラー発生位置が表示されました。前述したStateを使えば実行時コストと引き換えに行・桁でエラー位置を教えてもらうことができます。
println!("{}", signed_number.parse(State::new("abc")).unwrap_err());
Parse error at line: 1, column: 1
Unexpected `a`
Expected `digit`
1_234_567
TOMLでは、長い数値リテラルをわかりやすくするため桁の間に_を挿入することを許しています。ただし_が連続してはいけません。これをcombineで実装してみます。
正規表現で考えると\d+(_\d+)*という感じでしょうか。これをcombineのコンビネータで表現すれば
use combine::{Parser, many1, many};
use combine::char::{char, digit};
use std::iter;
many1(digit())
.and(many(token('_').with(many1(digit()))))
// Output = (Vec<char>, Vec<Vec<char>>)
となります。Parser::withメソッドはそのパーサの結果を捨て、引数にとったパーサの出力を最終的な出力とするパーサを返します。
この結果を数値に変換する関数をmapして完成です。
let number = many1(digit())
.and(many(token('_').with(many1(digit()))))
.map(|(a, b): (Vec<_>, Vec<Vec<_>>)| {
a.into_iter()
.chain(b.into_iter().flat_map(|x| x))
.map(|x: char| x.to_digit(10).unwrap() as i64)
.fold(0, |acc, x| acc * 10 + x)
});
.flat_map(|x| x)はVec<Vec<char>>と二重になったものからフラットなイテレータ(Iterator<Item=char>)を作るために使っています。
よく使う処理なので、わざわざid関数を渡すのが面倒な人は、itertoolsクレートが追加するflattenメソッドを使うとよいです。
文字列リテラルをパースしてみる
文字列のパースは結構複雑になりそうです。
パースしたいものが何かの間に挟まっていることを確認できるbetween、
要素をクロージャ受け取ってマッチするか否かを決められるsatisfyを使えば、
ダブルクオーテーションの中身を取り出すパーサはbetween(token('"'), token('"'), many::<String, _>(satisfy(|c| c != '"'))と書けます。
しかし、文字列リテラルにおいてはエスケープシーケンスなどを考慮する必要があるため、これでは不十分です。
またTOMLでは文字列リテラルが数種類あり、
"he\"llo"
"he\"\
llo"
"""
h\
e"llo"""
'he"llo'
'''
he"llo'''
以上は全てhe"lloという等しい文字列リテラルとして解釈しなければなりません。
エスケープシーケンス処理
between(token('"'), token('"'), *ここ*)に、\が来たら余分に1文字読み込んでエスケープシーケンスを処理するというパーサを書けばいけそうです。
標準のコンビネータでは処理しきれない細かい動作ですが、
Parser::thenを使うとパーサ出力に応じて次に行う動作を変えることができます。
thenに渡すクロージャはパーサ出力を受け取りパーサを返す必要があります。
カスタムパーサを作る手っ取り早い方法はcombine::parser関数です。これは入力を受け取りParserResultを返す関数をParserに変換する関数です。
エスケープシーケンスが始まったら、これに渡す関数のなかでさらにパースを1文字進めます。
use combine::{Parser, any, satisfy, parser};
use combine::primitives::Consumed;
satisfy(|c| c != '"')
.then(|c| {
parser(move |input| {
if c == '\\' {
any()
.map(|d| match d {
'\\' => '\\',
'"' => '"',
'n' => '\n',
_ => unimplemented!(),
})
.parse_stream(input)
} else {
Ok((c, Consumed::Empty(input)))
}
})
})
ParserResultを返すのはParser::parse_streamなのですが、今まで使ってきたParser::parseの返り値と異なって「パーサが入力を消費したか」という情報が含まれています。この情報が必要となるパース処理の途中に使われるものだと思われます(今ひとつよく分かってません)。
実際に文字列リテラルをパースしてみます。
extern crate combine;
use combine::{Parser, any, token, between, many, satisfy, parser};
use combine::primitives::Consumed;
fn main() {
let quoted = many::<String, _>(satisfy(|s| s != '"').then(|c| {
parser(move |input| if c == '\\' {
any()
.map(|d| match d {
'\\' => '\\',
'"' => '"',
'n' => '\n',
_ => unimplemented!(),
})
.parse_stream(input)
} else {
Ok((c, Consumed::Empty(input)))
})
}));
let mut string = between(token('"'), token('"'), quoted);
assert_eq!(string.parse("\"hello\"").unwrap().0, "hello");
assert_eq!(string.parse("\"he\\\"llo\"").unwrap().0, "he\"llo");
}
combineのドキュメントには別のやり方も書かれています。
こちらは作るパーサにsatisfyを含めている例ですね。
数値リテラルに_が含まれている場合のパースは単純なので既存のコンビネータを使って実装しましたが、同じようにthenを使って読み飛ばす実装でも出来そうです。
複数行文字列(""")
TOMLにおける複数行文字列はこんな感じです。
"""
he\
llo"""
# => "\"hello\""
-
\および制御文字のみエスケープが要る、"はそのまま書ける("""という並びが出来ると文字列が閉じられるので、その場合はエスケープする) - 開始側
"""直後の改行は無視される -
\+改行 以降のホワイトスペース(改行含む)が無視される
というものです。
エスケープ処理は前節と同様です。クオーテーションが"""と3文字あるため先読みを行う必要があります。
use combine::{Parser, any, parser, not_followed_by, many};
use combine::char::string;
use combine::primitives::Consumed;
// クオート内の各文字のパーサ
let maybe_escaped = any().then(|c| {
parser(move |input| if c == '\\' {
any()
.map(|d| match d {
'\\' => '\\',
'"' => '"',
_ => unimplemented!(),
})
.parse_stream(input)
} else {
Ok((c, Consumed::Empty(input)))
})
});
// Output = char
// クオート内のパーサ
let quoted = many::<String, _>(try(
not_followed_by(string("\"\"\"")).with(maybe_escaped)
));
// Output = String
not_followed_byは与えられたパーサがパースに成功しなかった場合にのみ成功するパーサです。tryと同様、任意の長さの先読みが可能です。
ここに、\\+改行+空白を無視する(s/\\\n\s*//)という処理を追加します。まず、このパターンにマッチするパーサを書きます。
use combine::{Parser, token, skip_many, satisfy};
use combine::char::newline;
let space_skip = (token('\\'), newline(), skip_many(satisfy(|c| c == ' ' || c == '\t' || c == '\n' || c == '\r')));
このパーサが失敗しても文字列のパース自体が失敗する必要はないのでoptionalで包みます。また、このパーサは先読みが必要(\の次に改行が来るか否かを判定する必要がある)ためtryを使います。以上でできたものをParser::skipで飛ばします。
let quoted = optional(newline()).with(many::<String, _>(try(not_followed_by(string("\"\"\""))
.skip(optional(try(space_skip)))
.with(maybe_escaped))));
// Output = String
let mut multiline_string = between(string(r#"""""#), string(r#"""""#), inquote);
// Output = String
assert_eq!(string.parse(State::new(r#""""
h""e\\ll\
o""""#)).unwrap().0,
r#"h""e\llo"#);
複数行文字列のパーサが出来ました!
リテラル文字列 (')
リテラル文字列('で囲ったもの)はエスケープが無いため、between(token('\''), token('\''), satisfy(|c| c != '\''))で済みますね。リテラル複数行文字列もエスケープと行末\による空白のスキップが無いだけで同様です。
パーサを返す関数を作る
ここまではコンビネータで作ったパーサをletで変数に束縛していましたが、実際に使うときはパーサを返す関数を用意しておく(combineの組み込みパーサがそうなっているように)と便利そうですね。
struct IntegerLiteral<I>(PhantomData<fn(I) -> I>);
impl<I: Stream<Item = char>> Parser for IntegerLiteral<I> {
type Input = I;
type Output = i64;
fn parse_stream(&mut self, input: I) -> ParseResult<i64, I> {
let sign = optional(token('+').or(token('-')));
let number = many1::<Vec<char>, _>(digit())
.map(|ds| {
ds.into_iter()
.map(|c| c.to_digit(10).unwrap() as i64)
.fold(0, |acc, x| acc * 10 + x)
});
let mut signed_number = (sign, number)
.map(|(s, num)| {
match s {
None | Some('+') => num,
Some('-') => -num,
_ => unreachable!(),
}
});
signed_number.parse_stream(input)
}
}
fn integer_literal<I: Stream<Item=char>>() -> IntegerLiteral<I> {
IntegerLiteral(PhantomData)
}
パーサ型を定義して、Parserを実装しています。いちいち型を定義するのが面倒だという場合は、作ったパーサをそのまま返す関数を作ることもできます。
fn integer_literal<I: 'static + Stream<Item=char>>() -> Box<Parser<Input = I, Output = i64>> {
let sign = optional(token('+').or(token('-')));
let number = many1::<Vec<char>, _>(digit())
.map(|ds| {
ds.into_iter()
.map(|c| c.to_digit(10).unwrap() as i64)
.fold(0, |acc, x| acc * 10 + x)
});
let signed_number = (sign, number)
.map(|(s, num)| {
match s {
None | Some('+') => num,
Some('-') => -num,
_ => unreachable!(),
}
});
Box::new(signed_number)
}
パーサを返すにはイテレータを返す際と同種の問題があります。パーサの型は複雑で2、型を書くのが大変です。しかもこの場合mapによるクロージャを含んでいるため記述できないのでBox化するかimpl Traitを使う必要があります。
Parser::parse_stream相当の関数を単体で用意することでもパーサを表現することもできます。使うときは文字列のパースで使ったparser関数を通すことでParserになります。
fn main() {
assert_eq!(parser(integer_literal).parse("1234").unwrap(),
1234);
}
fn integer_literal<I: Stream<Item=char>>(input: I) -> ParseResult<i64, I> {
...
(sign, number)
.map(|(s, num)| {
match s {
None | Some('+') => num,
Some('-') => -num,
_ => unreachable!(),
}
}).parse_stream(input)
}
おわりに
combineはデザインも綺麗で個人的にはけっこう好きなライブラリです。ドキュメントが充実しているのも有り難いです。
-
標準ライブラリのtryマクロとは別物です。マクロと関数は名前空間が分かれているので衝突することはありません。 ↩
-
signed_numberの型はcombine::combinator::Map<(combine::combinator::Optional<combine::combinator::Or<combine::combinator::Token<I>, combine::combinator::Token<I>>>, combine::combinator::Map<combine::combinator::Many1<std::vec::Vec<char>, combine::char::Digit<I>>, [closure@src/main.rs:41:14: 45:10]>), [closure@src/main.rs:48:14: 54:6]>となっています。 ↩