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

scala

Scalaコップ本の31章に入っていきますよ(｀・ω・´)31章はパーサー・コンビネーターというタイトルで言語内DSLの実装についてやっていきますねー

サンプル:算術式

言語内DSLのサンプルとして浮動小数点や括弧、二項演算子の+、-、*、/から構成される算術式のパサーを作ることにしますデス。

はじめの一歩として解析される言語文法を定義してやりますよ(｀・ω・´)定義で利用する記号は次の3つです

  • |
    • 選択可能な生成規則の区切り
  • { ... }
    • 0回以上の繰り返し
  • [ ... ]
    • オプション

それでは、上記記号を利用して解析対象の算術式を定義してやります

// 全ての式(expr)は一つの項(term)であり、その後ろに+または-演算子と
// 別の項の組み合わせからなるシーケンスを続けたモノ
expr ::= term {"+" term | "-" term}.

// 項(term)は一つの因子(factor)であり、その後ろに*または/演算子と
// 別の因子を組み合わせたシーケンスが続いたモノ
term ::= factor {"*" factor | "/" factor}.

// 因子は数値リテラルか括弧で囲まれた式
factor ::= floatingPointNumber | "(" expr ")".

上記定義にはたとえば...*演算子がtermを生成するのに対して+演算はexprを生成するのだけども、exprはtermを含むことが出来る反面termは括弧に囲まれたexprしか含むことが出来ないので*は+よりも結合力が高い...というふうに、演算子の相対的な優先順位を織り込んでいるみたいです。(´ε｀；)ｳｰﾝ…ここの理論展開はうまく噛み砕けていないなぁ…適用範囲が広ければ広いほど結合力は低くなるってことかしら？

とりあえず定義した文法を機械的にテキストに置き換えてパーサに仕立て上げた例が次のようになるみたいです。

import scala.util.parsing.combinator._
// JavaTokenParsersトレイトを継承します
class Arith extends JavaTokenParsers {
  // 先ほどの文法定義を置き換えていくだけですね 
  def expr:Parser[Any] = term~rep("+"~term | "-"~term)
  def term:Parser[Any] = factor~rep("*"~factor | "-"~factor)
  def factor:Parser[Any] = floatingPointNumber | "("~expr~")"
}

JavaTokenParsersトレイトはパーサーを書くための基本メカニズムと識別子・文字列リテラル・数値といった語類を認識するプリミティブなパーサーを提供するみたいです。上の例だとfloatingPointNumberが語類に当てはまりますねー

上記の定義は先に出てきた文法定義式を次のように機械的に翻訳しただけデス

  • 全ての生成規則はメソッドになるので先頭にdefを付ける
  • 各メソッドの結果型はParser[Any]なので::=記号を: Parser[Any]に変更
  • ~演算子で逐次合成を表現する
  • 繰り返し{ ... }表現がある場合はrep( ... )で置き換える
  • オプション[ ... ]がある場合はopt( ... )に置き換える
  • 行末の.は削除。代わりに;をつけてもOK

パーサーの実行

それでは上記定義を実行してみますよー。とりあえず実行用に定義したArithクラスを継承したパース結果を出力するだけの小規模プログラムを利用しますデス。

object parserExpr extends Arith {
  def main(args:Array[String]){
    println("input: " + args(0))
    // パースの結果はpaeseAllで取得することが出来るみたいです
    // ここではパラメータに対してexprのパースを行いマス
    println(parseAll(expr, args(0)))
  }
}

本来はコンパイルしてゴニョゴニョするのですが、ちょっちめんどくさいので対話型コンソールで実行してやりますよ(´・ω・｀)

scala> parserExpr.main(Array("2 * (3 + 7)"))
input: 2 * (3 + 7)
// 第１行12列([1,12])の位置までの入力文字列を解析できたみたいです
[1.12] parsed: ((2~List((*~(((~((3~List())~List((+~(7~List())))))~)))))~List())

とりあえずパース結果の使い方なんかは後のほうでやるみたいなのでparsed:以降は放っておくことにします(｀・ω・´)一応ここではパースできた！という結果のみで満足しますデス

ちなみにパースする対象の文法が間違っている場合も試してみますね

scala> parserExpr.main(Array("2 * (3 + 7))"))
input: 2 * (3 + 7))
[1.12] failure: string matching regex `\z' expected but `)' found

2 * (3 + 7))
           ^


とりあえず文法エラーが検出されました(｀・ω・´)詳しいエラーの説明についても後ろの節でやるみたいなのでとりあえず放置しますよー

いじょー

時間切れのためココマデです。次回は基本正規表現パーサーからやりますです(｀・ω・´)