Scalaのパーサコンビネータにふれる

技術チームインターンの中村です。

内製化されたシステムを抱えた会社にいると，エンジニア以外の方のためにドメイン特化言語を構築するようなこともあるかと思います。
uzabaseの場合，アナリストがSPEEDAに載せる業界概要の記事を効率良く書けるようになるために，Markdownに似た軽量マークアップ言語が作られました。

作る言語が構文木が不要なほど小規模ならば，文字用ユーティリティだけで十分に言語実装が可能かと思います。
一方で，言語が大規模であったり効率の良いコンパイルが求められたりするのであれば，LexやYaccのようなパーサージェネレータが必要になるかもしれません。

今回はその間くらい，つまり単純な文字列処理では足りないものの，パーサージェネレータを使うほどでもないくらいの言語を構築するときに便利なScalaのパーサーコンビネータについて紹介します。

受け取った入力の結果を返す関数としてパーサーを組合せることで，目的のパーサーを高階関数（コンビネータ）として構築したものがパーサーコンビネータです。
パーサーは文法構造の連続，繰り返し，選択などを実現する関数で組み合わされます。
このとき，言語が関数あるいはメソッドの中置記法をサポートするなら，パーサーコンビネータの定義はEBNFの生成規則と似たものになります。
たとえば，論理式のEBNFとこれに従う論理式をパースするパーサーコンビネータの対応は以下のようになります。

EBNF
expr ::= termA {"|" termA}
termA ::= termN {"&" termN}
termN ::= factor | {"!" factor}
factor ::= "TRUE" | "FALSE" | "(" expr ")"
|は選択，{}は0以上の繰り返し

パーサーコンビネータ
def expr: Parser[Any] = termA~rep("|"~termA)
def termA: Parser[Any] = termN~rep("&"~termN)
def termN: Parser[Any] = factor | "!"~factor
def factor: Parser[Any] = "TRUE" | "FALSE" | "("~expr~")"
|は選択，~は連続，rep()は0回以上の繰り返し

|, ~, repをメソッドとして別のParserを引数にとり，より複雑な文字列を受理するようなParserを返す，この繰り返しによって論理式を受理するパーサを構築しています。
上の定義は宣言的なので，どのような計算がパース過程で行われるのか定義から読み取ることができません。
そこで，アトミックなパーサと，パーサ同士を逐次的に繋げた場合の計算がどのような行われるか見て行きたいと思います。

最小のパーサはsuccess, failureというメソッドです。
これらは入力をまったく消費しません。 2つのメソッドは以下のように定義されています。

def success[T](v: T) = Parser{ in => Success(v, in) }

def failure(msg: String) = Parser { in => Failure(msg, in) }

ヘルパーメソッド
def Parser[T](f: Input => ParseResult[T]): Parser[T] = new Parser[T]{
  def apply(in: Input) = f(in)
}

Parserというのが，|や~をメソッドに持つパーサーのクラスです。 Inputは，パーサーが生の文字列だけではなく，トークンのストリームも読めるようにするために，パース対象を抽象化するクラスです。 Success, FailureはParseResultの子クラスとして，それぞれ成功，失敗したパース結果と残りの入力をまとめるクラスです。これらのクラスの宣言は以下のように定義されています。

abstract class Parser[+T] extends (Input => ParseResult[T]) {..}

case class Success[+T](result: T, override val next: Input) extends ParseResult[T] {
  ..
}

case class Failure(override val msg: String, override val next: Input) 
  extends NoSuccess(msg, next) {..}

success, failureの次に仕事をするパーサが以下のelemです。これは，入力を適用すると，入力の先頭がeであれば，resultにe, nextに2番目以降の入力もつSuccessを返します。また，先頭がeでなければFailureを返します。

def elem(e: Elem): Parser[Elem] = accept(e)

ここまでで，Parserが入力(Input)を受けつけ，ヘルパーメソッドのfにinputを適用した結果(result)と入力の残り(next)を返す関数であるようなイメージを持って頂けたと思います。
次に逐次的にパーサ同士をつなげるメソッド~を見ていきます。 ~は以下のように定義されています。

def ~[U](q: => Parser[U]): Parser[~[T, U]] = { lazy val = p = q
  (for {
    a<- this
    b<-p
  } yield new ~(a, b)).named("~")
}

new ~(a, b)は繋げられた2つのパーサーの結果をひとつにまとめるためケースクラス~のインスタンスです。また，for式に必要なflatMap, mapの定義は以下になります。

def flatMap[U](f: T => Parser[U]): Parser[U] = Parser{ in => 
  this(in) flatMapWithNext(f) 
}

def map[U](f: T => U): Parser[U]  = Parser{ in => this(in) map(f)}
  
上の定義で使われるSuccessにおけるflatMapWithNextとmapは以下のようになります。

def flatMapWithNext[U](f: T => Input => ParserResult[U]): ParseResult[U] =
   f(result)(next)

def map[U](f: T => U) = Success(f(result), next)

そして，これらを用いてfor式を地道に展開していくと例えば次のように書き直せます。

new Parser[T~U] {
  def apply(in: Input) = Parser.this(in) match {
    case Success(r, n) => p(n) match {
      case Success(r1, n1) => Success(new ~(r, r1), n1)
      case Failure(msg, next) => Failure(msg, next)
    }
    case Failure(msg, next) => Failure(msg, next)
  }
}

最初のパーサーが返すParseResultにある残りの入力が次のパーサに渡されることで，計算が進めるようです。上の定義を見ると，はじめのパーサが失敗すれば計算は終了。成功すれば，次のパーサpに残りの入力(n)を渡す。そこで失敗すれば後続する計算がなされず全体の計算が終了。成功すれば両パーサの計算結果としてケースクラスの~が返されています。

ここまでで，パーサーコンビネータの実体が引数をパース対象として受付け，関数適用の結果と残りのパース対象の組を返す関数のように振舞うことがなんとなく伝わったかと思います。

さらに詳しく知りたい方はこちらを参考にパーサーコンビネータそのものを自作してみるとよいかもしれません。リンク先の資料ではパーサコンビネータがモナド値であることを踏まえた上で実装方法を紹介しています。事実，ScalaのParserやParseResultはモナド値となっています。資料ではParserが次のように定義されています。

newtype Parser a = Parser (String -> [(a,String)])

InputがString, ParseResultが[(a, String)]とそれぞれ対応しています。空リストがFailureを意味します。最後に上のpdfの実装をScalaで試すときに，モナド則の確認やfor式の記述に最低限必要な定義を残しておくので，ご参考にしていただければと思います。

trait Parsers {
  def Parser[A](f: String => List[(A, String)]): Parser[A] = new Parser[A]{
    def apply(input: String) = f(input)
  }

  def success[A](v: A): Parser[A] = Parser{ input => List((v, input)) }

  def failure[A]: Parser[A] = Parser { input => List() }

  trait Parser[A] extends (String => List[(A, String)]) {
    def apply(input: String): List[(A, String)]

    def flatMap[B](f: A => Parser[B]) = Parser{ (input: String) =>
      for {
        (a, input2) <- this(input)
        b <- f(a)(input2)
      } yield b
    }

    def withFilter(pred: A => Boolean): Parser[A] = Parser { input: String =>
      for {
        elm <- this(input) if pred(elm._1)
      } yield elm
    }

    def map[B](f: A => B) = Parser {input =>
      for {
        a <- this(input)
      } yield(f(a._1), a._2)
    }
  }
}
  
付録, for式の展開過程

this.flatMap {
  a => p.map(b => new ~(a, b))
}

Parser {
  in => Parser.this(in) match {
    case Success(r, n) => ((a: T) => p.map(b => new ~(a, b)))(r)(n)
    case Failure(msg, next) => Failure(msg, next)
  }
}

Parser { in =>
  Parser.this(in) match {
    case Success(r, n) => Parser { in => p(in).map(b => new ~(r, b)) }(n)
    case Failure(msg, next) => Failure(msg, next)
  }
}

Parser { in =>
  Parser.this(in) match {
    case Success(r, n) => p(n) match {
      case Success(r1, n1) => Success(new ~(r, r1), n1)
      case Failure(msg, next) => Failure(msg, next)
    }
    case Failure(msg, next) => Failure(msg, next)
  }
}