LL脳がscalaの勉強を始めたよ その111

scala


Scalaコップ本の31章の続きをやっていきますよ(｀・ω・´)31章はパーサー・コンビネーターでの言語内DSLについてやっておりますデス。前回まではScalaのパーサー・コンビネーター機能についてやってきましたが、今回は具体的なパーサー・コンビネーターの実装をを詳しく見ていきマス

パーサー・コンビネータの実装

それではパーサー・コンビネーターライブラリの中身を見ていきますデス(｀・ω・´)とりあえずコレに触れることでコンビネータDSLの設計原則を理解できるそうです

…と、その前にScala的パーサー・コンビネーターをはじめとするScala上での命名規則についてちょろっと。コップ本的には以下のようなガイドラインに従うのがオススメみたいです。

  • 既に広く確立された意味を持つ場合には記号名を使う
    • 例えばaddではなく+を利用
  • 一般的な読者でもコードを理解できるようにしたければ英字名を選択
  • 視認性の面でもはっきりとしたメリットがある上、しっかりとしたドメイン知識のない一般的な読者にはいずれにしてもコードがすぐには理解出来ないと予想される場合、ドメイン固有ライブラリーでは記号名を選ぶ場合もありえる

…とりあえず、パーサー・コンビネーターのような特定の人向けで一般的な読者向けではい領域などでは、エキスパートよりに実装ってことで記号名を使うのが妥当だよ！とのことです。なるほど(´・ω・｀)

では上記を踏まえてScalaのパーサー・コンビネーター・フレームワークの中核部分を覗いていきますが、こいつらはscala.util.parsing.combinator.Parsersトレイトに含まれているそうです。コードとしてはここらへんです

package scala.util.parsing.combinator
trait Parsers {
  // この部分にパーサー・コンビネーターの中核が格納されてるそうです
}

ついでにパーサー・コンビネーターで定義するParserは何らかの入力型を解析結果に変換する関数みたいなので、基本的につぎのようモノだと考えていいみたいです

type Parser[T] = Input => ParseResult[T]
パーサーに対する入力

パーサーは生の文字列のシーケンスだけでなく、トークンのストリームを読むこともあるらしいのですが、その場合はパーサーとは別のスキャナーを使って生のシーケンスをトークンストリームに変換するみたいです。そんなわけで、パーサーの入力型は次のように定義されるみたいです

type Input = Reader[Elem]

ここでReaderクラスはscala.util.parsing.inputパッケージに含まれているらしく、Streamと似た動作であるものの、読みだした要素の位置も管理しているみたいです。また、Elem型は個々の入力要素を表すParserトレイトの抽象型メンバーみたいです。Elem型の定義はこんな感じですね。

type Elem

ParserのサブクラスやサブトレイとはElemクラスのインスタンスとして解析された入力要素の型を指定しなければならないみたいです。ちなみに、前回取り扱ったRegexParsersやJavaTokenParsersなんかだとElemをCharで固定しているみたいですが、別個のスキャナーが返したトークンの型等のようにElemを他の型に固定しても良いそうです。

パーサーの結果値

パーサーは、入力次第で処理に成功したり失敗したりするのでParseResultクラスは次のような成功と失敗を表すサブクラスを持っているみたいです。

// パース結果用の抽象クラス
sealed abstract class ParseResult[+T]
// 成功の場合用のサブクラスです
case class Success[T](result:T, in:Input) extends ParseResult[T] 
// 成功の場合用のサブクラスです
case class Failure(msg:String, in:Input) extends ParseResult[Nothing]

Successケースクラスは型がまちまちなパース結果を受け取るのでパラメータTをとっております。ます第2パラメーターとしてパーサーが処理した次の入力を参照するみたいです。このフィールドはパーサーを次々と実行するパーサー連鎖を実現するために必要みたいです。このパーサー連鎖という仕組みは構文解析に対する純粋関数型アプローチになっているそうです(´・ω・｀)入力を受け取って処理→また入力を受け取って(ryを副作用を使わずに処理できるのだとか、なるほど

もう一方の失敗を表すFailureクラスは解析に失敗したメッセージと、Successと同様の第2パラメータを取るみたいです。この第2パラメータの用途としては、解析に失敗したパーサーは処理を続行しないので、エラーメッセージを入力ストリームの適切な位置に合わせるために利用されるみたいです。

ちなみに解析結果ParseResultは、例えば結果値としてStringを返すパーサーがAnyRefを返すパーサーに対して互換性を持てるように、Tと共変として定義されているみたいです。

Parserクラス

パーサーは最初のほうで触れたように入力を解析結果に変換する役割をもつのですが、その他にも2つのパーサーを逐次合成したり選択的合成をしたりするので、ソレに応じたメソッドをもっているみたいです。またパーサーは関数なのでapplyメソッドも持っているですね。イメージとしては次のような実装になるみたいです。

abstract class Parser[+T] extends (Input => ParseResult[T])
{ p =>
  // 関数としてのパーサーの動作を定義する抽象メソッド
  def apply(in:Input):ParseResult[T]
  // 2つのパーサーを逐次合成
  def ~ ...
  // 2つのパーサーを選択適合性
  def | ...
  ...
}

ParserではInput => parseResult[T]というscala.Function1[Input, ParseResult[T]]型の略記法である関数型を継承していますネ(｀・ω・´)また実際に関数的動作を行うapplyメソッドは個別のパーサーで定義するような形になりますね

thisの別名

先程も出てきたParserの前段部には{ p =>という不思議な定義があるのですが、これはthisの別名としてpが使えるようになるという定義みたいです。

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

上記定義ではクラス本体で次のように書いたのと同じになるみたいです

val p = this

ただし、{ p =>のような別名を使った場合は上記定義と違ってコンパイラが別名として認識するので例えば上記定義ではエラーになるような非公開メンバーmに対するp.mというアクセスが可能になるみたいです。（単純な代入だと非公開メンバーにアクセスできないですね）

上記のような別名記法は27章でもやったように次のようにトレイトに自分型を与えるためにも使えるみたいです

// thisの別名としてouterを定義
class Outer { outer =>
  class Inner {
    println(Outer.this eq outer)　// どちらも同じ意味なので結果はtrue
  }
}

別名を使うことで簡潔で明快なコードがかけるYO!とはコップ本の弁です(´・ω・｀)

シングルトークンパーサー

Parsersクラスでは任意の１個のトークンを解析するために使えるelemというジェネリックパーサーを定義しているみたいです。コードはつぎのようになりますね

// 解析対象のトークンを記述した文字列と
// Elem型の述語関数をパラメータとしてとります
def elem(kind:String, p:Elem => Boolean) = 
  new Parser[Elem]{
      // パーサー処理です
      def apply(in:Input) =
        // 入力ストリームの先頭からpによってテストして
        // 結果に応じた処理を行います
        if(p(in.first)) Success(in.first, in.rest)
        else Failure(kind + " expected", in)
  }
逐次合成

先ほどとりあげたelemパーサーでは1個の要素しか処理できないので、更に複雑な解析をするには逐次合成演算子~で複数のパーサーを連結してやりますデス。前回やったとおりP~Qという逐次合成ではPが成功したらPが処理しなかった入力に対してQパーサーを適用しますです。

~コンビネータは次のようなメソッドとしてParserクラスに定義されているみたいです。

// pはParserクラスのthisの別名になるので
// 具体的にはp~qを処理するメソッドです
def ~ [U](q: => Parser[U]) = new Parser[T~U]{
  // まずは最初のパーサーを適用します
  def apply(in:Input) = p(in) match {
    case Success(x, in1) =>
      // 成功したら残った入力に次のパーサーを適用しますね
      q(in1) match {
        case Success(y, in2) => Success(new ~(x, y), in2)
        case failuer => failure
      }
    case failuer => failure
  }
}

~の結果型は、T型とU型の要素をとるケースクラス~のインスタンスを返すパーサーでもあるみたいです。ここで、T~Uという型式は~[T, U]というパラメータ化された型の略記法みたいです。

また<~と~>の逐次合成演算子は~の結果値の計算方法に修正を加えることで、次のように定義できるみたいです。

def <~[U](q: => Parser[U]):Parser[T] =
  // 変換を使って左の結果のみを取り出します
  (p~q) ^^ { case x~y => x }
def ~>[U](q: => Parser[U]):Parser[U] =
  // 変換を使って右の結果のみを取り出します
  (p~q) ^^ { case x~y => y}
選択適合成

選択適合性のP | Qは与えられた入力に対してPかQを適用するので、まずPを試して成功しなかった場合はPと同じ入力でQを試すような処理になりますね。具体的にはこんな感じですかね

// pはParserクラスのthisの別名になるので
// 具体的にはp~qを処理するメソッドです
def | (q: => Parser[T]) = new Parser[T] {
  def apply(in:Input) = p(in) match {
    case s1 @ Success(_, _) => s1
    // 先のパーサーが失敗した場合のみ次のパーサーに処理が移ります
    case failure => q(in)
  }
}

PとQの両方失敗した場合のエラー処理はQによって決定するみたいですねー

再帰の取り扱い

~や |メソッドのqパラメータは型の前に=>がつけられた名前渡しパラメータになっているので、パーサーの実際の引数はqが適用されたあとに評価されるみたいです。なのでコレを応用することで任意の個数の括弧で囲まれた数値を解析する再帰パーサーを掛けるみたいですネ

// floatingPointNumberが出てくるまで再帰的に処理し続けマス
def parens = floatingPointNumber | "("~parens~")"
結果の変換

Parserクラスの最後のメソッドはパーサーの結果値を変換するので、P ^^ fパーサーが成功末うのはPが成功するときになりますデス。なので、P ^^ fはPの結果値に関数fを適用した結果を返すことになりますね

// Parserの末尾に定義されます
def ^^ [U](f:Y => U):Parser[U] = new Parser[U]{
  def apply(in:Input) = p(in) match {
    case Success(x, in1) => Success(f(x), in1)
    case failure => failure
  }
}
何も読まないパーサー

Parsersトレイトに実装されたトレイとの中で、入力を何も消費しないパーサーとしてsuccessとfailureの2つがありますです。success(result)パーサーはパラメータのresultを開けして必ず成功して、failure(msg)パーサーは、エラーメッセージのmsgを表示して必ず失敗するものみたいです。コードは次のようになりますです。

// 必ず成功パーサー
def success[T](v:T) = new parser[T]{
  def apply(in:Input) = Success(v, in)
}
// 必ず失敗パーサー
def failure(msg:String) = new Parser[Nothing]{
  def apply(in:Input) = Failure(msg, in)
}

ちなみにこいつらをふくんでいるParsersトレイトは外側としてParserトレイトも含んでおりますね。

オプションと繰り返し

Parsersトレイトはオプションや繰り返しコンビネーターとしてopt, rep, repsepなんかも定義しているのですが、これらは逐次合成、選択、結果値変換を使って次のように実装されるみたいですね

//// これらはParsersの末尾に実装されるみたいですね

// Option型への変換(opt)の実装です
def opt[T](p: => Parser[T]):Parser[Option[T]] = (
  p ^^ Some(_)
  | success(List())
)

// 繰り返し(rep)の実装です
def rep[T](p:Parser[T]): Parser[List[T]] = (
  p~rep(p) ^^ { case x~xs => x :: xs }
  | success(List())
)

// 区切り文字付き繰り返し(repsep)の実装です
def repsep[T, U](p:Parser[T], q:Parser[U]): Parser[List[T]] = (
  // 区切り文字の右側を切り出すことで反復処理擦る感じですかね？
  p~rep(q~>p) ^^ { case r~rs => r :: rs }
  | success(List())
)

とりあえずざざっと羅列してみました(´・ω・｀)

いじょー

写経全開の今回分はここまでです(´・ω・｀)次回は文字リテラルと正規表現からやっていきますよー