Anti-XML を使ってみた

XMLを弄る用があったので、Anti-XMLを使ってみた。

scala.xml の代替を目指しているライブラリなので使い勝手は似ているが、SelectorやZipperなど、scala.xmlには無い機能がある。

基本

com.codecommit.antixml._ をインポートすると、scala.xmlのクラスをantixmlのクラスに置き換えることができる。

import com.codecommit.antixml._

// scala.xml.Elem を com.codecommit.antixml.Elem に変換
val xml = Stay hungry, don't eat..convert
// ドキュメントではconvertメソッドではなく、
// antiメソッドを読んでいるのだが見つからない。。

// Text, Groupなどはcom.codecommit.antixml のクラスに上書きされてる。
val textGroup = Group(Text("stealth marketing"))

Selector

SelectorはPartialFunctionを継承していて、ノードをマッチさせるために使うのだが、任意の戻り値に変換できる。StringとSymbolはSelector[Elem]に暗黙変換される。

val text: Selector[String] = Selector({
  case Text(str) => str
})

// Vector[String]が返ってくる。
xml \ text // => Vector[String]

// Selector[Elem]の場合はZipper[Elem]が返ってくる。
xml \ "string" // => Zipper[Elem]
xml \ 'symbol // => Zipper[Elem]

Zipper

ZipperはXMLツリーをimmutableに更新する機能。ノードを探索して取得したZipperを書き換えた後に、unselectメソッドを呼ぶと更新されたXML全体が取得できる。

val xml = Carol Bartz.convert

val updatedXml = (xml \ 'ceo).updated(0, Scott Thompson.convert).unselect
// => Scott Thompson

探索したあとのノードから親ノードを再構成できるのは割とうれしい。でもscala.xml使うよりはXMLの更新が楽にはなっているが、まだちょっと面倒。使い方が悪いのかもしれないから今後調べる必要がある。

ちなみに xml \ 'hoge \ 'fuga のように2段階で探索した場合は、unselectを2回呼ぶ必要がある。

一応gistに上げといた↓

Packrat Parserを使ってみた

新しくブログ作ってみました。
Advent Calendar遅くなってすいません…。

Akasaka Scalaで、Parserのバックトラッキングについて話していたときに、教えて頂いたPackratParsersを使ってみました。

PackratParsersを使うことによるメリットは、
解析結果をメモ化し、バックトラック時に無駄な再解析を防ぐことで、解析処理を線形時間で終了させられること
ですが、
メモ化のために、余計なメモリを使ってしまう
というデメリットもあります。

それでは普通のParsersとPackratParsersを使ってメモ化がされているかを確かめてみます。

import util.parsing.combinator.{PackratParsers, Parsers}
import util.parsing.input.CharSequenceReader


object Example {

 // 普通のParsersバージョン
 object NormalExample extends Parsers {

  type Elem = Char

  lazy val X = Y ~ 'b' | Y ~ 'c'

  lazy val Y = 
   elem("a", char => {
    println("Parsing a in packrat parser.")
    char == 'a'
   })

  def parseInput(in: String) = 
   X(new PackratReader(new CharSequenceReader(in)))
 }


 // PackratParsersバージョン
 object PackratExample extends PackratParsers {

  type Elem = Char

  lazy val X: PackratParser[Any] = Y ~ 'b' | Y ~'c'

  lazy val Y: PackratParser[Any] = 
   elem("a", char => {
    println("Parsing a in packrat parser.")
    char == 'a'
   })

  def parseInput(in: String) = 
   X(new PackratReader(new CharSequenceReader(in)))
 }

 // 実行
 def main(args: Array[String]): Unit = {

  println(NormalExample.parseInput("ac"))
  println("------------------------------------")
  println(PackratExample.parseInput("ac"))

 }

}

上記のNormalExampleとPackratExampleとは全く同じ文法を解析します。
パーサYは、文字'a'をパースし、その時に文字出力を行います。
パーサXは、文字'a'の解析にパーサYを使用し、"ab" または "ac" をパースします。

パーサXに"ac"という文字列を入力すると、

NormalExampleは

パーサYで解析 → 成功 →
文字'b'が来るか解析→ 失敗 →
最初に戻る →
パーサYで解析 → 成功 →
文字'c'が来るか解析 → 成功

となりパーサYの解析は2回行われますが、

PackratExampleは

パーサYで解析 → 成功 →
文字'b'が来るか解析→ 失敗 →
最初に戻る →
★パーサYで解析済み →
文字'c'が来るか解析 → 成功

となるので、パーサYの解析は1回しか行われません。

以下が実行結果になります。

Parsing a in normal parser.
Parsing a in normal parser.
[1.3] parsed: (a~c)
------------------------------------
Parsing a in packrat parser.
[1.3] parsed: (a~c)

PackratParsersを使用する場合に注意しなければいけないのは、
PackratParsersを継承したクラスで作成したパーサがすべてPackratParserになるのではない所です。
パーサに型を指定して暗黙変換してもらうか、memoメソッドによって明示的に変換する必要があります。

と、この辺で。