LL脳がscalaの勉強を始めたよ その112
Scalaコップ本の31章の続きをやっていきますよ(｀・ω・´)31章はパーサー・コンビネーターを使った言語内DSLの構築云々をテーマにやっております。
文字列リテラルと正規表現
前回までに取り扱ったパーサーは文字列リテラルと正規表現を使って単一の単語を解析するものでしたが、この役割をサポートしているのが次のようなRegexParsersトレイトみたいです。
// Parsersのサブトレイトとして定義されています trait RegexParsers extends Parsers {
このRegexPArsersトレイトは入力として、次のように定義された文字のシーケンスしか受け取らないみたいです
type Elem = Char
またRegexParsersは次のような2つのメソッドを持っているみたいですネ
// implicit修飾子がついているので自動的に適用されますね implicit def literal(s:String):Parser[String] = ... implicit def regex(r:Regex):Parser[String] = ...
上の2つのメソッドはStringやRegexが与えられてParserが必要とされるときに自動的に適用されるので、文字列リテラルや正規表現をラップせずに文法中に直接かけるようになっているみたいです。この自動適用のおかげで、例えば "("~expr~")" というパーサは自動的にliteral("(")~expr~literal(")") に展開されますね。
またRegexParsersトレイトは、リテラルや正規表現パーサを実行する前にhandleWhiteSpaceメソッドを呼び出すことでシンボル間の空白文字の処理もしてくれるみたいです。
handleWhiteSpaceメソッドはデフォルトで次のような空白正規表現にマッチする入力シーケンスを最大限読み飛ばすみたいです。
// RegexParsersの末尾に記述されているみたいです protected val whiteSpace = """\s+""".r
仮にRegexParsers適用時に空白文字の扱いを変えたい場合は、whiteSpaceフィールドをオーバーライドすることで実現出来るみたいです。例えば空白文字を一切読み飛ばしたくない場合には次のような定義になりますね
object MyParsers extends RegexParsers { // 空白として何も指定しません(´・ω・｀) override val whiteSpace = "".r ... }
字句解析と構文解析
構文解析を行う際には次の2つのフェーズに分割されることが多いみたいです
まあ、実際には字句解析も構文解析フェーズの一部としてみることもできるそうですが…(´・ω・｀)ちなみにParsersトレイトでは入力要素がElem抽象型に定義されているので、どちらのフェーズでも使えるらしく、構文解析フェーズではスキャナーが返してきたトークン型にElemを設定するみたいです。
なおScalaのパーサー・コンビネーターでは、字句解析や構文解析のためにいくつかのユーティリティクラスを提供していて、それらは次の2つのサブパッケージに含まれているみたいです。
//// それぞれ2つのフェーズに対応するみたいです // こちらが字句解析用みたいです scala.util.parsing.combinator.lexical // 構文解析用ですかね scala.util.parsing.combinator.syntactical
もしもパーサーを字句解析器と構文解析器に分割する場合には、上記パッケージのドキュメントを参照するのが良いみたいです。ただし、単純なパーサーなら前々回で取り扱った正規表現アプローチで十分みたいです(´・ω・｀)
エラー報告
次にパーサーが発行するエラーメッセージについて見ていきますよー。通常パーサーのエラー報告は複雑怪奇なのですが、一般的にパーサが入力を受け付けない状態に陥っている場合は多くの異なるエラーが発生しているみたいです。具体的にはパーサー内の全ての選択肢に失敗して、それが再帰的に続いているという悲惨な状態みたいです(´・ω・｀)
そこでScalaのパーサーライブラリーでは入力最後の位置で発生したエラーを返すことで、有効に解釈できるところまで入力を取り込んでみて、それ以上の解析が進められなかった理由を示すエラーメッセージを出力するみたいです。また、その位置で複数のエラーが発生した場合は最後に検出したエラーを選択するみたいですね(´・ω・｀)
エラー報告の具体例
それでは、エラー報告の具体例を見ていきますです。例えば次の行を先頭とする構文に誤りのあるアドレス帳をJSONパーサーにかけたケースを考えてみますです。
{ "name" : John,
まず、このフレーズのうち有効な構文の一部として解析できる部分は次の部分マデですね
{ "name" :
なのでJSONパーサーはJhonという単語のところでエラーを検出しますです。このJhonという表記は識別子であって値として扱えないので、この場合は次のようなエラーが出力されるみたいです
[1. 13] failure: "false" expected but identifier Jhon found { "name" : Jhon, ^
エラー的には「"false"を期待していたのに識別子が来たYO!(#ﾟДﾟ)」という内容なのですが、これはJSON文法の中で値の生成規則の最後の選択肢が"false"だったからみたいです。JSON文法の規則を知っていればあれですが、知らないと混乱しそうな感じですね(´・ω・｀)
エラーのキャッチ
上記のようにパーサーは生成規則の最後の選択肢をエラーのメッセージとして持ってくるので、生成規則の最後の選択肢として全てのエラーをキャッチするポイントを追加することでもう少しよいエラーメッセージが出力出来るようになりますね。
def value:Parser[Any] = obj | arr | stringLit | floatingPointNumber | "null" | // エラーメッセージ出力用の選択肢を追加しますデス "true" | "false" | failure("illegal start of value")
これで先程の混乱を招きそうなエラーメッセージは次のように改善できるみたいです
[1. 13] failure: illegal start of value { "name" : Jhon, ^
lastFailureフィールド
エラー出力時に「最後の選択肢」のような、できるだけ後のエラーを報告する仕組みはlastFailureフィールドを利用しているみたいです。このフィールドは入力のもっとも後ろの位置で発生したエラーをマークするためのもので、Parsersトレイトに次のような形式で含まれるみたいです。
val lastFailure:Option[Failure] = None
このフィールドは上記のようにNoneで初期化されて、エラーが発生するたびに次のようなFailureクラスのコンストラクターで更新されるみたいです
case class Failure(msg:String, in:Input) extends ParseResult[Nothing]{ // 新しいエラーが記録された中で一番後ろにあればlastFailureが更新されます if(lastFailure.isDefined && lastFailure.get.in.pos <= in.pos) lastFailure = Some(this) }
lastFailureフィールドはパーサーが失敗したときに最終的にエラーメッセージを生成する次のように定義されたphraseメソッドによって呼び出されるみたいです。
def pharase[T](p:Parser[T]) = new Parser[T]{ lastFailure = None def apply(in:Input) = p(in) match { // 入力パーサーpが成功した場合の処理です case s @ Success(out, in1) => // 入力を全て消費している場合は成功の結果値を返します if(in1.atEnd) s // 入力が完全に消費されていない場合は // 現在の入力位置とともにエラーを返します else Failure("end of input expected", in1) // 入力パーサーpが失敗した場合は // lastFailureに格納されたエラーを出力 case f:Failure => lastFailure } }
(´ε｀；)ｳｰﾝ…コップ本でも書いてあるのですがlastFailureの扱いが副作用的で関数型っぽくないですねぇ…関数型でも出来るみたいですが少々面倒なので効率のためにこういう実装にしたみたいです。
バックトラックとLL(1)
パーサー・コンビネーターは選択肢に含まれる異なるパーサーをえらぶために後戻りをするバックトラックを行っているみたいです。たとえばこんな感じみたいですね(´・ω・｀)
- P | Qという式でPが失敗
- Pと同じ入力に対してQを適用
- Pが失敗するまでにいくつかのトークン解析ができている場合も同様にQを適用
バックトラックの制約
バックトラックをしながら構文解析できる文法を作るには、基本的に左再帰を使った生成規則を避ける必要があるという制約があるみたいです。
例えば次のような左再帰をつかった生成規則を考えてみます
expr ::= expr "+" term | term.
この場合はexprがすぐに自分自身を呼び出して先に進めなくなってしまうで、スタックオーバーフローを発生して必ず失敗するみたいです。なんとか対処する方法はナキニシモアラズらしいですが、すごく高度でめんどくさいパーサー・コンビネーター・フレームワークが必要だとのことです(´・ω・｀)
また、バックトラックは同じ入力をなんども解析する場合があるのでコストがかかるみたいですね。例えばこんな生成規則を考えてみます。
expr ::= term "+" expr | term.
exprパーサがtermとして有効な(1 + 2) * 3のような入力に適用された場合は次のように処理されるみたいです。
- 最初の選択肢が試されて+記号をマッチさせようとしたところで失敗
- 第2の選択肢が試され成功
このように2回の構文解析が行われるので、ちょっぴりコストが高くなります。なので、こんな風に文法を作り替えることでバックトラックを回避できるみたいです。
expr ::= term [ "+" expr]. expr ::= term { "+" term}.
LL(1)文法
多くの言語ではLL(1)文法というのを認めているそうで、そういう文法からパーサー・コンビネーターをつくるとバックトラックが起きないみたいです。ちなみに31章で取り扱った算術式やJSONなんかはLL(1)で、これらのパース時にはバックトラックが置きないみたいですね(´・ω・｀)なおLL(1)文法については参考文献を参照みたいです。
Scalaパーサー・コンビネーター・フレームワークでは、~!という演算子を使うことで文法がLL(1)になっているということを明示的に示してバックトラックを行わせない事ができるみたいです。これによって既に解析した入力要素を「読まなかったことにする」というバックトラックを行わないことが出来ますです。
なお、~!演算子を使ったサンプルは次のようになりますね
//// 以前に構築した算術子パーサーの生成規則を書きなおしてみます //// 具体的には逐次演算子~を~!に書き換えてやる形ですね // 式の定義 def expr:Parser[Any] = term ~! rep("+" ~! term | "-" ~! term) // 項の定義 def term:Parser[Any] = factor ~! rep("*" ~! factor | "/" ~! factor) // 要素の定義 def factor:Parser[Any] = "(" ~! expr ~! ")" | floatingPointNumber
LL(1)文法を使うことで入力をシーケンシャルによむことができ、かつ読みだした入力要素を捨てることができるため処理を単純化できるようになりマス。なのでLL(1)パーサーがバックトラックパーサーよりも効率的になる理由の1つになるわけですね(´・ω・｀)
いじょー
写経全開の31章はこれでおわりです。31章ではScalaのパーサー・コンビネーターについてやってみました。
Scalaのパーサー・コンビネーターはココマデやってきたようにScalaライブラリとして提供されているので簡単に組み込むことができるわけです…がその反面yaccやbisonのような専用ツールが生成したパーサーに比べると効率が良くないみたいです。
その理由の1つはバックトラック方式が効率がよくないことで、2つ目の理由としてパーサーの構築と入力の分析を同じ演算子セットに混ぜ込んでいるため、パーサーは解析する入力ごとに新しく生成されてしまうことみたいです。
1つ目の理由については先ほど触れたとおりLL(1)方式の文法にしてバックトラック防止用の逐次合成演算子~!をつかうことで解決できますが、2つ目の方は新しいパーサー・コンビネーターフレームワークを作りなおさないとダメみたいです。
例えば最適化フレームワークのもとでパーサーが入力を解析結果に変換する関数ではなく、全ての構築ステップがケースクラスとして表現される木構造によって表現されるようにすることで効率を上げることが出来るみたいです。例えば逐次合成がSeq、選択はAlt等のケースクラスによって表現され、一番外側の定義であるphraseがパーサーのシンボリック表現をパラメータとして、標準的なパーサー・ジェネレーター・アルゴリズムを使って効率の高い解析表に変換することができるみたいです。
この方法を使うと、ユーザからは単純なパーサー・コンビネーターと何の違いもなくみえるので、これまでと同様にパーサーを書ける＆以前と同じように動作させるとこが出来るみたいです。
なお、上記方法を使うことで入力解析とパーサーの構築を分割できるようになるみたいです。例えば次のようなコードがあった場合、jSonParserは複数の異なる入力に対して適用できるので、jsonParserは入力を読み出すたびにつくるのではなく、最初に1度作ったものを再利用出来るようになるみたいです。
val jsonParser = phrase(value)
またパーサー生成でLALR(1)といった効率のよい解析アルゴリズムを使えるようになるため、バックトラック・パーサーよりもずっと高速なパーサーが作れるみたいです。
ただし、上記のようなパーサー・ジェネレーターはまだ作られていないので、誰か作ってね☆とのことです…まあ、仮にできたとしても理解しやすい現在のパーサー・コンビネーター・フレームワークも残るだろうけどね…だそうですが(´・ω・｀)
長くなりましたが、以上です。次回は32章のGUIプログラミングをやりたいと思います。あと2章…がんばりまっす(｀・ω・´)
