Rust でパーサコンビネータを作ってみる (後編)

「Rust でパーサコンビネータを作ってみる (前編)」 の続きです (前編を投稿してから一ヶ月以上経ってしまった…)。

後編では、前編で作ったパーサコンビネータを使って JSON パーサーを作っていきます。JSON の文法は json.org に書いてあるので、これを忠実に実装します。

json::Value

パーサーの作成に入る前に JSON の値を表す struct を定義しておきましょう。

#[derive(Debug, Clone, PartialEq)]
pub enum Value {
    Null,
    False,
    True,
    Number(f64),
    String(String),
    Array(Vec<Value>),
    Object(HashMap<String, Value>),
}

Rust には強力な enum があるので極めて自然に定義できますね。

便利関数の定義

JSON パーサーの実装には lexeme(string(..)) や lexeme(character(..)) が何度も出てくるので、これらを先に関数化しておきましょう。

fn lstring(target: &'static str) -> impl parsers::Parser<()> {
    parsers::lexeme(parsers::string(target))
}

fn lcharacter(c: char) -> impl parsers::Parser<()> {
    parsers::lexeme(parsers::character(c))
}

ここで parsers というモジュールは前編で定義したパーサコンビネータを格納しているモジュールです。

null, false, true

それでは JSON パーサーの作成を始めましょう。パーサコンビネータの流儀に従い、単純なパーサーを作って合成していく方針で行きます。

まずは null, false, true のパーサーから始めましょう。これらは単なるキーワードなので lstring でパースできます。そして結果の値に変換するために parsers::map すればOKです。

fn null(s: &str) -> Option<(Value, &str)> {
    let p = lstring("null");
    let p = parsers::map(p, |_| Value::Null);
    p(s)
}

fn false_(s: &str) -> Option<(Value, &str)> {
    let p = lstring("false");
    let p = parsers::map(p, |_| Value::False);
    p(s)
}

fn true_(s: &str) -> Option<(Value, &str)> {
    let p = lstring("true");
    let p = parsers::map(p, |_| Value::True);
    p(s)
}

number

次は number です。JSON の number は意外と複雑な仕様になっていて、普通にパースするのは大変そうですが、我々には regex! があるので一撃でパースできます。

fn number(s: &str) -> Option<(Value, &str)> {
    const PATTERN: &str = r"^-?(0|[1-9][0-9]*)(\.[0-9]+)?([eE][+-]?[0-9]+)?";
    let p = crate::regex!(PATTERN, |s| s.parse::<f64>().ok());
    let p = parsers::lexeme(p);
    let p = parsers::map(p, |x| Value::Number(x));
    p(s)
}

正規表現は偉大ですね。

String

文字列もパースは結構大変です。普通の文字とエスケープされた文字があり、エスケープもバックスラッシュ + 特定の一文字のものとバックスラッシュのあとに 'u' + 4桁の hex が続くものがあります。また、コントロール文字は文字列リテラルの中に書けません。

実装は以下のようになりました。ちょっと長いですが、仕様とコードができるだけ一対一対応するように書いてみました。

fn json_string(s: &str) -> Option<(Value, &str)> {
    parsers::map(json_string_raw, Value::String)(s)
}

fn json_string_raw(s: &str) -> Option<(String, &str)> {
    // string = '"' character* '"'
    let p = crate::join![
        parsers::character('"'),
        parsers::many(json_character),
        parsers::character('"')
    ];
    let p = parsers::lexeme(p);
    let p = parsers::map(p, |((_, chars), _)| {
        chars.into_iter().collect()
    });
    p(s)
}

fn json_character(s: &str) -> Option<(char, &str)> {
    // character = <Any codepoint except " or \ or control characters>
    //           | '\u' <4 hex digits>
    //           | '\"' | '\\' | '\/' | '\b' | '\f' | '\n' | '\r' | '\t'
    crate::choice![
        crate::regex!(r#"^[^"\\[:cntrl:]]"#, |s| s.chars().next()),
        crate::regex!(r#"^\\u[0-9a-fA-F]{4}"#, hex_code),
        crate::regex!(r#"^\\."#, escape)
    ](s)
}

fn hex_code(code: &str) -> Option<char> {
    code.strip_prefix(r"\u").and_then(|hex|
        u32::from_str_radix(hex, 16).ok().and_then(|cp|
            char::from_u32(cp)
        )
    )
}

fn escape(s: &str) -> Option<char> {
    match s {
        "\\\"" => Some('"'),
        "\\\\" => Some('\\'),
        "\\/" => Some('/'),
        "\\b" => Some('\x08'),
        "\\f" => Some('\x0C'),
        "\\n" => Some('\n'),
        "\\r" => Some('\r'),
        "\\t" => Some('\t'),
        _ => None // undefined escape sequence
    }
}

json_string と json_string_raw をわざわざ分けているのは、後で Object のパースで再利用したいからです。

Array

Array は String と比べると簡単です。

fn array(s: &str) -> Option<(Value, &str)> {
    let p = crate::join![
        lcharacter('['),
        parsers::separated(json_value, lcharacter(',')),
        lcharacter(']')
    ];
    let p = parsers::map(p, |((_, values), _)| Value::Array(values));
    p(s)
}

この実装に出てくる json_value というパーサーは任意の JSON 値をパースできるパーサーです。これは最後に定義します。

Object

Object も Array と似たような感じで定義できます。

fn object(s: &str) -> Option<(Value, &str)> {
    let p = crate::join![
        lcharacter('{'),
        parsers::separated(key_value, lcharacter(',')),
        lcharacter('}')
    ];
    let p = parsers::map(p, |((_, key_values), _)| {
        let h = HashMap::from_iter(key_values.into_iter());
        Value::Object(h)
    });
    p(s)
}

fn key_value(s: &str) -> Option<((String, Value), &str)> {
    // key_value = string ':' json_value
    let p = crate::join![
        json_string_raw,
        lcharacter(':'),
        json_value
    ];
    let p = parsers::map(p, |((key, _), value)| (key, value));
    p(s)
}

全部まとめる

最後に、今まで定義してきたパーサーを choice! で一つのパーサーにまとめてやれば JSON パーサーの完成です！

fn json_value(s: &str) -> Option<(Value, &str)> {
    crate::choice![
        null,
        false_,
        true_,
        number,
        json_string,
        array,
        object
    ](s)
}

json_value をそのまま公開してもよいですが、Option<(Value, &str)> という戻り値は普通の用途では微妙なので、ここでは Option<Value> を返す関数で wrap して公開することにします。ただし、rest の部分にゴミが残っていると JSON として不正なのでその場合はエラーにします。

pub fn parse(s: &str) -> Option<Value> {
    json_value(s).and_then(|(value, rest)| {
        if rest.chars().all(|c| c.is_ascii_whitespace()) {
            Some(value)
        } else {
            None
        }
    })
}

JSON パーサーの実装は以上です。

おわりに

いかがだったでしょうか？ パーサーを合成していくことで複雑なパーサーを作り上げることができるパーサコンビネータの強力さを実感いただけたのではないでしょうか (半分ぐらい正規表現のパワーという気もしますが)。