Elm で構文解析しよう

Elm アドベントカレンダーの２日目です。

この記事では Elm のライブラリ elm-tools/parser を使って構文解析する方法を解説します。

構文解析（パース）とは

何らか文字列を入力として、その意味や構造を解釈することを言います。例えば、

"1 + 2 * a"

という四則演算を表す文字列は、次のような JSON で表すことができます（定義は適当です）。

{
  "type": "add",
  "left": {
    "type": "number",
    "value": 1
  },
  "right": {
    "type": "multiply",
    "left": {
      "type": "number",
      "value": 2
    },
    "right": {
      "type": "identifier",
      "value": "a"
    }
  }
}

Elm の文法（union type）を使うとより簡潔に表現できます。

Add (Number 1) (Multiply (Number 2) (Identifier "a"))

こうすることによって、生の文字列よりもプログラムで扱うことが簡単になります。
しかし、どうすればこの構造を得ることができるのでしょうか？少し考えてみましょう。

• split と trim で頑張る
• 正規表現で頑張る
• ループで頑張る

全部つらそうですね。

Elm の構文解析器（パーサー）

elm-tools/parser は、そんな構文解析を超シンプルな記述で実現してしまうライブラリです。Elm の作者である Evan 氏自身によって書かれています。

例として公式のサンプルを引用してみます。ここでは ( 3, 4 ) のような文字列を２次元の座標として解釈するパーサー point を定義しています。

import Parser exposing (Parser, (|.), (|=), succeed, symbol, float, ignore, zeroOrMore)


type alias Point =
  { x : Float
  , y : Float
  }

-- "( 3, 4 )" という文字列を { x = 3, y = 4 } のように解釈するパーサーの定義
point : Parser Point
point =
  succeed Point
    |. symbol "("  -- (
    |. spaces
    |= float       -- 3
    |. spaces      
    |. symbol ","  -- ,
    |. spaces
    |= float       -- 4
    |. spaces
    |. symbol ")"  -- )


spaces : Parser ()
spaces =
  ignore zeroOrMore (\c -> c == ' ')

色々書いてありますが、まずは細かいことは抜きにしてコメント部分に注目しましょう。今パースしたいのは
( 3, 4 ) という文字列です。これを分解すると、「(、 0 文字以上の空白、数値（Float）、 0 文字以上の空白、,、 0 文字以上の空白、数値（Float）、 0 文字以上の空白、)」から成っています。これを、そのまま順番に並べていくとそれだけでパーサーができてしまいます！

それだけではありません。一度作ったパーサーは再利用可能な部品になるのが大きな特長です。上の例では、 spaces （ 0 文字以上の空白をパースする）を point の中で再利用しています。このように部品を組み合わせていくことによって、四則演算から長大なプログラムまでありとあらゆる文字列をパースすることが可能になります。

このパーサーを使って実際に解析を実行するには次のようにします。

Parser.run point "(1,2)"  -- Ok { x = 1, y = 2 }

成功したら Ok 失敗したら Err が返ります。何となく使い方のイメージが湧いたでしょうか。

基本文法

それでは早速、パーサーの作り方を解説していきます。

上の例を見て「大体こんな感じかー」で作っていくこともできますが、基礎があやふやだとかえって遠回りになりがちです。まずは小さな部品からはじめて徐々にステップアップしていきましょう。

int / float

まず初めに一番「直感的にイメージしやすい」パーサーを紹介します。整数をパースする int と浮動小数点数をパースするfloat です。これらは最初から Parser モジュールで提供されています。

int   : Parser Int
float : Parser Float

Parser Int という型は「 Int 型の値を返すパーサー」であることを表しています。また一般的に、型 a を返すパーサーの型を Parser a で表します。

実行してみましょう。

Parser.run int "1234" -- Ok 1234
Parser.run int "Hello" -- Err ...

入力として数値を表す文字列（ここでは "1234"）を受け取ると成功して整数（ここでは 1234）を返し、それ以外では失敗してエラーを返します。同様に float : Parser Float は、浮動小数点数を表す文字列を受け取ると成功します。

ここではざっくり「整数」と言っていますが、より実践的には以下のようなことも考慮する必要があります。

• 頭に 0 をつけて 010とした場合は成功するのか？
• 上の場合は 10 進数なのか 8 進数なのか？
• 前後の空白は許可するのか？
• 全角文字 １２３４ も許可したい
• 1,000 などの表記も許可したい

というわけで、より細かく仕様を決めたいときは、もっと細かい部品を使って組み立てるのが良いでしょう。

以下では、もっとプリミティブな関数を見ていきます。

succeed / fail

succeed を使うと「必ず成功する」パーサーを作ることができます。

試しに何か作ってみましょう。

import Parser exposing (Parser, succeed)

alwaysFive : Parser Int
alwaysFive =
  succeed 5

ここでは、必ず成功して 5 を返すパーサーを作っています。

実行してみましょう。

Parser.run alwaysFive "Hello!"  -- Ok 5

"Hello!" という文字列を与えていますが、"Hey!" だろうが "Bye!" だろうが無視して 5 を返します。ここでは返す型を Int にしていますが、文字列でもリストでも任意の型のパーサーを作ることができます。

また、 fail を使うと、必ず失敗するパーサーを作ることができます。

import Parser exposing (Parser, fail)

alwaysFail : Parser a
alwaysFail =
  fail "Sorry, I could not parse!"

fail の引数にはエラーメッセージとなる文字列を渡します。

Parser.run alwaysFail "Hello!"  -- Err "Sorry, I could not parse!"

今度は、どんな文字列が与えられようが 100% 失敗します。これが何の役に立つのかは、後の説明に譲りましょう。

symbol / keyword

symbol は , とか [ のような記号にマッチするパーサー、 keyword は let や var のような単語にマッチするパーサーを作る関数です。

横着して公式の例を持ってきます。

Parser.run (symbol "[") "[" == Ok ()
Parser.run (keyword "let") "let" == Ok ()

要するに、与えた文字列と同じなら成功します。
両方ともやっていることは同じですが、エラーメッセージの内容が変わるので区別した方がベターです。
戻り値 () は０個のタプル、つまり何も返すものがないことを表しています。

map

map はパースして得られた値を変換して別のパーサーを作る関数です。

map : (a -> b) -> Parser a -> Parser b

List.map : (a -> b) -> List a -> List b と似た型なので覚えやすいと思います。

Parser.run (map (\i -> i * 2) int) "5" -- Ok 10

andThen

andThen はパースして得られた値に応じて新しいパーサーを生み出す関数です。

andThen : (a -> Parser b) -> Parser a -> Parser b

こちらも List.andThen : (a -> List b) -> List a -> List b と同じ形をしています。

even : Parser Int
even =
  int
    |> andThen
      (\i ->
        if i % 2 == 0 then
          succeed i
        else
          fail "not an even number"
      )

Elm では上のようにパイプでつなぐことが多いので慣れておきましょう。（特に andThen はその方が文として読みやすくなります。）

oneOf

oneOf は、複数のパーサーのどれかにマッチするパーサーを作る関数です。

type FizzBuzz = Fizz | Buzz | FizzBuzz | Number Int

fizzBuzz : Parser FizzBuzz
fizzBuzz =
  oneOf
    [ map (\_ -> FizzBuzz) (keyword "FizzBuzz")
    , map (\_ -> Fizz) (keyword "Fizz")
    , map (\_ -> Buzz) (keyword "Buzz")
    , map Number int
    ]

リストで渡しているパーサーは上から順番に調べていくため、順序は重要です。

run fizzBuzz "Fizz" -- Ok Fizz
run fizzBuzz "5"    -- Ok (Number 5)
run fizzBuzz "hey"  -- Err ...

(|=) (|.)

(|=) と (|.) は複数のパーサーを直列につなぎ合わせるための演算子です。それぞれ次のような意味を持ちます。

• (|=) はパースした値を受け取ります
• (|.) はパースした値を捨てます

ここで、最初のパーサーを少し簡略化した例を見てみましょう。このパーサーは (1,2) のような文字列を Point 型の値としてパースします（空白は認めないものとします）。

type alias Point =
  { x : Float
  , y : Float
  }

point : Parser Point
point =
  succeed (\first second -> Point first second)
    |. symbol "("
    |= float
    |. symbol ","
    |= float
    |. symbol ")"

ラムダ式が受け取っている 2 つの値は、その直後にある 2 つの float がパースした結果で、それ以外のシンボル ( と , は無視されています。どうしてこんな書き方が出来るのか気になるかもしれませんが、考えるよりも succeed (\first second -> Point first second) |= ... はイディオムだと思って覚えるのが早いです。

それでも気になる方のために、型は以下のようになっています。

(|=) : Parser (a -> b) -> Parser a -> Parser b
(|.) : Parser keep -> Parser ignore -> Parser keep

再帰とコミット

ここまで最も基本的な文法を一通り解説しました。

裏でとても難しいことをしていそうですが、実際に実行時に行われていることは、ただ左から順に読んで調べているだけです。この事実を確かめるために、簡単な例を用意しましょう。

Parser.run int "5+3"    -- Ok (Number 5)

この例は、 5 の部分のみを Int 型で取り出しパースを終了しています。後ろに +3 が付いていますが、失敗することはありません。

一方、ぴったりそこで終わりであるという場合には、文字列の終端であることを表す end : Parser () を使います。

justAnInt : Parser Int
justAnInt =
  succeed identity
    |= int
    |. end

こちらはエラーになります。

Parser.run justAnInt "5+3"    -- Err ...

以降で登場する比較的複雑なパーサーを作るときには、この「左から読んでいる」ということを念頭に置いて実装する必要があります。

再帰的なパーサー

ここでは 1,2,3,4 のようにカンマで区切られた数値をパースすることを考えます。問題を簡単にするために、必ず1つ以上の値があり、空白は挟まっていないものとします。

ここで考えなければいけないことは 1,2,3,4 は再帰的な構造を持っているということです。全体を intValues、カンマから始まって最後までを intValuesTail とすると、次のように表すことができます。

1,2,3,4
^^^^^^^ intValues     [1,2,3,4]
 ^^^^^^ intValuesTail [2,3,4]
   ^^^^ intValuesTail [3,4]
     ^^ intValuesTail [4]
        intValuesTail []

このパーサーの実装は次のようになります。intValuesTail が再帰的に呼ばれていることに注意してください。

intValues : Parser (List Int)
intValues =
  succeed (::)
    |= int
    |= intValuesTail

intValuesTail : Parser (List Int)
intValuesTail =
  oneOf
    [ succeed (::)
        |. symbol ","
        |= int
        |= lazy (\_ -> intValuesTail)
    , succeed []
    ]

なお、再帰的なパーサーを書くときには lazy を使ってラムダ式で書く必要があります。これは Elm 0.18 のコンパイラが JavaScript を生成する際のバグを回避するためです。次のバージョン 0.19 で直る予定です。

keep / ignore / repeat

上の例のように繰り返す構造をパースするときに毎回再帰を書くのは骨が折れるので、ヘルパー関数が用意されています。

type Count
  = AtLeast Int
  | Exactly Int

zeroOrMore : Count -- same as (AtLeast 0)
oneOrMore  : Count -- same as (AtLeast 1)

keep   : Count -> (Char -> Bool) -> Parser String
ignore : Count -> (Char -> Bool) -> Parser ()
repeat : Count -> Parser a -> Parser (List a)

keep は条件を満たす文字を読み続け、最終的に文字列を返します。Count は読み取る文字数です。

capitalized : Parser String
capitalized =
  succeed (++)
    |= keep (Exactly 1) Char.isUpper
    |= keep zeroOrMore Char.isLower

ignore は条件を満たす文字を読み続け、最終的に無視します。 keep した後に無視すれば良い気もしますが、こちらは読んだ文字列分のメモリを確保しません。

spaces : Parser ()
spaces =
  ignore zeroOrMore (\c -> c == ' ')

repeat は任意のパーサーを与えて繰り返して得られた値のリストを返します。

delayedCommit

ここで、もう一つ押さえておくべき重要な関数 delayedCommit を紹介します。

次の例は、要素を1つ以上含む整数のリストのパーサーです。[ 1, 2, 3 ] のようなリストとして解釈します。今度は空白を含んでいるのがポイントです。

intList : Parser (List Int)
intList =
  succeed (::)
    |. symbol "["
    |. spaces
    |= int
    |= repeat zeroOrMore nextInt
    |. spaces
    |. symbol "]"

nextInt : Parser Int
nextInt =
  succeed identity
    |. spaces
    |. symbol ","
    |. spaces
    |= int

spaces : Parser ()
spaces =
  ignore zeroOrMore (\c -> c == ' ')

一見正しそうですが、次のような文字列をパースしようとすると失敗します。

Parser.run intList "[ 1, 2, 3 ]"

Err { row = 1, col = 11, source = "[ 1, 2, 3 ]", problem = ExpectingSymbol ",", context = [] }

もう少しわかりやすく書くと、ここです。

[ 1, 2, 3 ]
          ^ ExpectingSymbol ","

期待する動作としては、 3 をパースしたところで repeat zeroOrMore nextInt が終了し、残りをパースして完了、なのですが。実際には、nextInt が 3 の後のスペースまで読んでしまい、そこから戻れなく成ってしまいます。この「パースに成功したら次に進む」動作を コミット (commit) と言います。そして重要なことは、一度コミットすると分岐の前に後ることができないということです。

-- 悪い
nextInt =
  succeed identity
    |. spaces     -- ここが成功する
    |. symbol "," -- ここまで進む（失敗しても戻れない）
    |. spaces
    |= int

そこで、「ある地点に到達するまでコミットを遅らせる」のが delayedCommit です。

-- 良い
nextInt =
  delayedCommit spaces <|
    succeed identity
      |. symbol "," -- これが成功するまでコミットを遅らせる
      |. spaces
      |= int

これで、symbol "," が成功するまで spaces はコミットされません。パース成功です。やりましたね。これを理解していないとドツボにハマるので覚えておきましょう。

エラーとコンテクスト

このライブラリの README に「 Nice Error Messages 」と書いてありますが、実際に実行すると Err { row = 1, col = 11, source = "[ 1, 2, 3 ]", problem = ExpectingSymbol ",", context = [] } のようなレコードが帰ってきて「日本語でおk、いやせめて英語でおk」となります。
要するに「エラーメッセージを表示するのに十分な情報は用意した」けれどもフォーマッターは提供されていないのです（誰か作って欲しいです）。

失敗時に返される Error 型は次のような構造になっています。

type alias Error = 
  { row : Int               -- エラーの発生した行番号（１から）
  , col : Int               -- エラーの発生した列番号（１から）
  , source : String         -- パースした文字列
  , problem : Problem       -- エラーの内容
  , context : List Context  -- エラーに至った文脈
  }

Problem 型の定義は次の通りです。

type Problem
  = BadOneOf (List Problem)  -- oneOf の全てが失敗した
  | BadInt                   -- Int の形式が間違っていた
  | BadFloat                 -- Float の形式が間違っていた
  | BadRepeat                -- 無限ループ（同じ場所を調べ続けている）
  | ExpectingEnd             -- end を期待したが文字列が残っていた
  | ExpectingSymbol String   -- 期待したシンボルが来なかった
  | ExpectingKeyword String  -- 期待したキーワードが来なかった
  | ExpectingVariable        -- 変数を期待したが来なかった
  | ExpectingClosing String  -- 括弧などの終わりを期待したが来なかった
  | Fail String              -- fail で失敗した（ユーザーの定義した任意のエラー）

こんなに多くなくてもいい気がしますが、具体的なのは良いことです。

inContext

上の Problem 型だけでもだいたい分かりますが、もう少し親切な情報を提供するために文脈を提供することができます。inContext を使うと、今何をパースしているのかという文脈を挿入することができます。

例えば、先ほどの例（修正前）を inContext を使って書き直してみましょう。

intList : Parser (List Int)
intList =
  inContext "int list" <|
    succeed (::)
      |. symbol "["
      |. spaces
      |= int
      |= repeat zeroOrMore nextInt
      |. spaces
      |. symbol "]"


nextInt : Parser Int
nextInt =
  inContext "next int" <|
    succeed identity
      |. spaces
      |. symbol ","
      |. spaces
      |= int

関数の頭に一行ずつ inContext "文脈を示す文字列" を差し込んだだけです。これをパースすると失敗しますが、エラーメッセージが先ほどよりも詳細になります。

Err { row = 1, col = 11, source = "[ 1, 2, 3 ]", problem = ExpectingSymbol ",", context = [{ row = 1, col = 10, description = "next int" },{ row = 1, col = 1, description = "int list" }] }

噛み砕くと、

• (1,1) から始まる "int list" のパース中、
• (1,10) から始まる "next int" のパース中、
• (1,11) で ExpectingSymbol "," という問題が発生した

ということになります。デバッグ効率向上のために積極的に使っていきましょう。

その他の機能

Parser.LowLevel モジュールは、より低レベルな機能を提供します。
具体的には、行番号、列番号、インデントレベル、ソースなど内部で保持している状態を取得して使うことができたりします。特にインデントによって文法が変わる言語（Elm, Python, YAML, ...）の解析では重要なテクニックになります。

Parser.LanguageKit モジュールはリストや辞書などよくある文法をパースするためのユーティリティが用意されています。

既存のライブラリとの比較

このライブラリはいわゆる「左再帰下降パーサー」の仲間で、似たものでは Haskell の Parsec が有名です（ Scala など他の言語にもあります）。

作者の Evan 氏によると Parsec の使い勝手に不満があったので、 delayedCommit によって改善したとのことです。詳細は Comparison with Prior Work で説明されていますが、思いきって要約すると

• try を使うとそれより内側でコミットする地点の制御ができず、エラーメッセージが不親切になる
• lookAhead を使うとより緻密に制御できるが、内側のパーサーに文脈に関する情報が入り込んでしまい、コードのメンテナンス性が落ちる

length [1,,3]
       ^ `try (spaces >> term)` だとここでエラーが出る

一方、 delayedCommit を使うと「スペース時点では分からないが [ が来たらコミットして OK 」という制御ができるため、こちらの方がより良いプリミティブだと主張しています。

また、try が欲しければいつでも作ることができるので、表現力自体は落ちていません。

try : Parser a -> Parser a
try parser =
  delayedCommitMap always parser (succeed ())

とは言え、手に入れたら乱用してしまうのが人の性なのであえて提供していないのだそうです。

まとめ

elm-tools/parser を使うと、再利用可能な部品を使って複雑な文法を比較的容易にパースすることができます。慣れれば正規表現くらい気軽に使えるはずなので、武器の一つとして是非どうぞ！