scalaでパーザーコンビネーターを書いてみた
パーザーコンビネータとは
パーザを部品として、より複雑なパーザを構築する手法。例えば文字列の一致など基本的なパーサーを作っていおいて、それを組み合わせることで数式のパーサーを作ったりする。
なぜパーザーコンビネータ？
基本的な文法を覚えた後の次のステップにちょうど良い規模(小さすぎず、大きすぎず) 言語の機能を幅広く使うことができる
Javaでのパーザコンビネータの実装としてこの記事が参考になりましたので、これをもとに自分なりにScalaで書いてみたいと思います。
基本的なパーザの実装
まずパース結果を表せるようにします。ParseOkはパース成功時に使うクラスになり、valueはパースして得られ値で型はパラメータで渡しています。nextはパースに成功したテキスト以降の文字列になります。それからParseNgがパース失敗時に使うクラスでmessageはパース失敗の内容を保持させるのに使います。
trait ParseResult[T] {
}
case class ParseOk[T](value: T, next: String) extends ParseResult[T] {
override def toString(): String = "Success(" + value + ", " + next + ")"
}
case class ParseNg[T](message: String, next: String) extends ParseResult[T] {
override def toString(): String = "Failure(" + message + ", " + next + ")"
}
文字列判定のパーサー
文字列をパースするクラスは以下のようになります。単純にクラス初期化時に渡した文字列と一致した場合はParseOkでそれ以外はParseNgを返すようにしています。
class StringParser(literal: String) extends Parser[String] {
override def parse(input: String): ParseResult[String] = {
input.startsWith(literal) match {
case true => ParseOk(this.literal, input.substring(literal.length))
case false => ParseNg("expect: " + this.literal, input)
}
}
}
例えばhelloという文字列に一致するかどうかを判定するパーサーのインスタンスを生成する場合は以下のようにParser.string("hello")とできるようにしておきます。
trait Parser[T] {
def parse(input: String): ParseResult[T] = ???
def string(literal: String):Parser[String] = new StringParser(literal)
}
object Parser extends Parser[Any] {}
このパーサーのテストコードは以下のようになります。
class StringParserTest extends FlatSpec {
"parse" should "successt" in {
val parse = Parser.string("Hello")
val result1 = parse.parse("Hello, world")
assert(result1.isInstanceOf[ParseOk[_]])
assert(result1.asInstanceOf[ParseOk[_]].next.equals(", world"))
}
"parse" should "failer" in {
val parse = Parser.string("Hello")
val result1 = parse.parse("hello, world")
assert(result1.isInstanceOf[ParseNg[_]])
}
}
0回以上の繰り返しを判定するパーサー
次に0回以上の繰り返しを判定するパーサーになります。0回以上のためインスタンス生成時の引数として任意のパーサーを受け取るようにしているのでパース結果の値として型パラメータをうけとれるようにしています。
class ManyParser[T](parser: Parser[T]) extends Parser[List[T]] {
override def parse(input: String): ParseResult[List[T]] = {
var next = input
var values = List.empty[T]
var isContinue = true
while(isContinue) {
val result = parser.parse(next)
if(result.isInstanceOf[ParseOk[_]]) {
values = values :+ result.asInstanceOf[ParseOk[T]].value
next = result.asInstanceOf[ParseOk[T]].next
} else {
isContinue = false
}
}
ParseOk(values, next)
}
}
文字列判定のパーサーと同様にインスタンス生成を生成できるようにParserトレイトを以下のように修正します。
trait Parser[T] {
def parse(input: String): ParseResult[T] = ???
def many(): Parser[List[T]] = new ManyParser[T](this)
def string(literal: String):Parser[String] = new StringParser(literal)
}
object Parser extends Parser[Any] {}
1回以上の繰り返しを判定するパーサー
1回以上の繰り返しの場合はパース成功結果を保持するりすとのlengthが0の場合は失敗で、1以上の場合は成功にしています。
class PlusParser[T](parser: Parser[T]) extends Parser[List[T]] {
override def parse(input: String): ParseResult[List[T]] = {
var next = input
var values = List.empty[T]
var isContinue = true
var result: ParseResult[T] = null
while(isContinue) {
result = parser.parse(next)
if(result.isInstanceOf[ParseOk[_]]) {
values = values :+ result.asInstanceOf[ParseOk[T]].value
next = result.asInstanceOf[ParseOk[T]].next
} else {
isContinue = false
}
}
values.length match {
case 0 => ParseNg(result.asInstanceOf[ParseNg[_]].message, input)
case _ => ParseOk(values, next)
}
}
}
オプショナルなパースを行う
省略可能な文字列の判定などに使うためのオプショナルなパーサーですが、インスタンス生成時の引数として受け取ったパーサーでパースを行いその結果に限らずパース成功として結果を返すようにします。オプショナルなパーサーのため型パラメータとして受け取った型をOptionalでくるんで返すようにしており、パース成功時はSome(result.value)で失敗時はNoneをParseOkにセットしています。
class OptionalParser[T](parser: Parser[T]) extends Parser[Option[T]] {
override def parse(input: String): ParseResult[Option[T]] = {
parser.parse(input) match {
case result: ParseOk[T] => ParseOk(Some(result.value), result.next)
case result: ParseNg[_] => ParseOk(None, input)
}
}
}
2つのパーサーを候補として片方で成功したら成功とするパーサー
インスタンス生成時に受け取った2つのパーサーでor条件とするパーサーです。インスタンス生成時の引数として受け取るがたパラメータは別々で分けれた方が良いと思うのですが、パース結果の型をうまいこと分ける方法が思いつかなかったので同じものにしています。
class OrParser[T](lps: Parser[T], rps: Parser[T]) extends Parser[T] {
override def parse(input: String): ParseResult[T] = {
lps.parse(input) match {
case lResult: ParseOk[T] => ParseOk(lResult.value, lResult.next)
case lResult: ParseNg[_] => {
rps.parse(input) match {
case rResult: ParseOk[T] => ParseOk(rResult.value, rResult.next)
case rResult: ParseNg[_] => ParseNg(rResult.message, rResult.next)
}
}
}
}
}
2つのパーサーの繰り返し
2つのパーサーをインスタンスの引数とし、パース結果としてインスタンス引数で受け取った2つのパーサーの結果をタプルにして返すようにします。
class Pair2[T,U](lps: Parser[T], rps: Parser[U]) extends Parser[(T,U)] {
override def parse(input: String): ParseResult[(T, U)] = {
lps.parse(input) match {
case lResult: ParseOk[T] => {
rps.parse(lResult.next) match {
case rResult: ParseOk[U] => ParseOk((lResult.value, rResult.value), rResult.next)
case rResult: ParseNg[_] => ParseNg(rResult.message, rResult.next)
}
}
case lResult: ParseNg[_] => ParseNg(lResult.message, lResult.next)
}
}
}
3つのパーサーの繰り返し
今度は3つのパーサーをインスタンス引数として同様に処理します。2つのパーサーの繰り返しを組み合わせても使えるのですが、パース結果を扱いやすくするために用意しています。
class Pair3[T,U,V](lps: Parser[T], cps: Parser[U], rps: Parser[V]) extends Parser[(T,U,V)] {
override def parse(input: String): ParseResult[(T,U,V)] = {
lps.parse(input) match {
case lResult: ParseOk[T] => {
cps.parse(lResult.next) match {
case cResult: ParseOk[U] => {
rps.parse(cResult.next) match {
case rResult: ParseOk[V] => ParseOk((lResult.value, cResult.value, rResult.value), rResult.next)
case rResult: ParseNg[_] => ParseNg(rResult.message, rResult.next)
}
}
case cResult: ParseNg[_] => ParseNg(cResult.message, cResult.next)
}
}
case lResult: ParseNg[_] => ParseNg(lResult.message, lResult.next)
}
}
}
終端判定のパーサー
終端の判定も必要になるので用意しておきます。今回はクラスとして定義していますがインスタンス生成時の引数もないのでobjectとして定義しておいてもよさそうです。
class EOFParser() extends Parser[String] {
override def parse(input: String): ParseResult[String] = {
input.length == 0 match {
case true => ParseOk("", "")
case false => ParseNg("expect EOF:, actual " + input, input)
}
}
}
ストップッワードによる文字列判定
ダブルクォーテーションで囲まれた文字列を判定するときなどに使えるようにストップワードによる文字列判定を行えるようにしたいと思います。ただストップワードをダブルクォーテーションにした場合であっても文字列内にダブルクォーテーションを使いたいことがあるのでエスケープできるように引数として受け取ります。
class StopWithEscape(stop: String, escapes: Map[String, String]) extends Parser[String] {
assert(stop.length > 0)
override def parse(input: String): ParseResult[String] = {
var next = input
var continueFlg = true
var ret = ""
while(continueFlg) {
escapes.foreach{case (key, value) => {
if(next.startsWith(key)) {
ret += value
next = next.substring(key.length)
}
}}
if(next.length > 0 && !next.startsWith(stop)) {
ret += next(0)
next = next.substring(1)
} else {
continueFlg = false
}
}
ParseOk(ret, next)
}
}
基本のパーサーとしてこれだけ準備しておきます。インスタンス生成用のParserトレイトを以下のようにしておきます。
trait Parser[T] {
def parse(input: String): ParseResult[T] = ???
def many(): Parser[List[T]] = new ManyParser[T](this)
def plus(): Parser[List[T]] = new PlusParser[T](this)
def pair2[U](rps: Parser[U]): Parser[(T,U)] = new Pair2(this, rps)
def pair3[U,V](cps: Parser[U], rps: Parser[V]): Parser[(T,U,V)] = new Pair3(this, cps, rps)
def or(p: Parser[T]): Parser[T] = new OrParser(this, p)
def option(): Parser[Option[T]] = new OptionalParser[T](this)
def eof:Parser[String] = new EOFParser()
def string(literal: String):Parser[String] = new StringParser(literal)
def stop(stop: String, escapes: Map[String, String]):Parser[String] = new StopWithEscape(stop, escapes)
}
object Parser extends Parser[Any] {}
Jsonをパースできるようにする
基本のパーサーは実装できたので今度はそれを組み合わせて使ってみたいと思います。 JSONのパーサーは構文定義をみると練習の規模として丁度よさそうです。
まずパース結果の値としてstring, number, object, array, bool, nullとあるのでそれらを表せるためのクラスを用意します。この時classのequalsメソッドはoverrideしておきます。
trait JValue
case class JString(value: String) extends JValue {
override def equals(obj: Any): Boolean = {
obj.isInstanceOf[JString] && value.equals(obj.asInstanceOf[JString].value)
}
}
case class JNumber(value: Int, decimal: Int, base: Int) extends JValue {
override def equals(obj: Any): Boolean = {
obj match {
case obj: JNumber => value == obj.value && decimal == obj.decimal && base == obj.base
case _ => false
}
}
}
case class JObject(map: Map[JString, JValue]) extends JValue {
def getMap = map
override def equals(obj: Any): Boolean = {
obj match {
case obj: JObject => {
(map.size == obj.getMap.size) && map.find(kv => !kv._2.equals(obj.getMap.get(kv._1).get)).isEmpty
}
case _ => false
}
}
}
case class JArray(value: List[JValue]) extends JValue {
def getVal = value
override def equals(obj: Any): Boolean = {
obj match {
case obj: JArray => value.length == obj.getVal.length &&
value.zipWithIndex.find{case (v, index) => !obj.getVal(index).equals(v)}.isEmpty
case _ => false
}
}
}
case class JBool(value: Boolean) extends JValue {
override def equals(obj: Any): Boolean = obj.isInstanceOf[JBool] && value.equals(obj.asInstanceOf[JBool].value)
}
case class JNull() extends JValue {
override def equals(obj: Any): Boolean = obj.isInstanceOf[JNull]
}
それからJsonパーサーとしてParserを拡張したJParserを定義します。
trait JParser[T <: JValue] extends Parser[T] {
}
object JParser extends JParser[JValue]
JSONの文字列判定
JSONの文字列判定ですがダブルクォーテーションに囲まれたものになるのでストップワードのパーサーを使って以下のように定義します。
object JStringParser extends JParser[JString] {
override def parse(input: String): ParseResult[JString] = {
val parser = new Pair3(Parser.string("\""), Parser.stop("\"", Map("\\\"" -> "\"")), Parser.string("\""))
parser.parse(input) match {
case result: ParseOk[(String, String, String)] => ParseOk(JString(result.value._2), result.next)
case result: ParseNg[_] => ParseNg(result.message, result.next)
}
}
}
JSONの数値判定
数値の判定ですが少数や指数を指定できるようにすると以下のように結構ボリュームのあるパーサーになりました。何をやっているのかわかりづらく、対象の構文定義と照らし合わせていかないと読みづらいかと思います。 先に構文定義
number
integer fraction exponent
integer
digit
onenine digits
'-' digit
'-' onenine digits
digits
digit
digit digits
digit
'0'
onenine
onenine
'1' . '9'
fraction
""
'.' digits
exponent
""
'E' sign digits
'e' sign digits
sign
""
'+'
'-'
それから、コードは以下のようになりました。
object JNumberParser extends JParser[JNumber] {
lazy val signP = Parser.string("+").or(Parser.string("-")).option()
lazy val baseP = Parser.string("E").or(Parser.string("e"))
lazy val ztonP = Parser.string("0").or(Parser.string("1")).or(Parser.string("2")).or(Parser.string("3")).
or(Parser.string("4")).or(Parser.string("5")).or(Parser.string("6")).
or(Parser.string("7")).or(Parser.string("8")).or(Parser.string("9"))
lazy val parser1 = new Pair2(new Pair2(signP, ztonP.plus()), (new Pair2(Parser.string("."), ztonP.plus())).option())
lazy val parser2 = (new Pair3(baseP, signP, ztonP.plus())).option()
override def parse(input: String): ParseResult[JNumber] = {
parser1.parse(input) match {
case result1: ParseOk[((Option[String], List[String]), Option[(String, List[String])])] => {
parser2.parse(result1.next) match {
case result2: ParseOk[Option[(String, Option[String], List[String])]] => {
var value = 0
var deci = 0
var base = 0
val valueStr = result1.value._1._2.foldLeft(result1.value._1._1.getOrElse(""))((acc, cur) => {
acc + cur
})
value = Integer.valueOf(valueStr)
if(result1.value._2.isDefined) {
val decStr = result1.value._2.get._2.foldLeft("")((acc, cur) => {
acc + cur
})
deci = Integer.valueOf(decStr)
}
if(result2.value.isDefined) {
val baseStr = result2.value.get._3.foldLeft(result2.value.get._2.getOrElse(""))((acc, cur) => {
acc + cur
})
base = Integer.valueOf(baseStr)
}
ParseOk(JNumber(value, deci, base), result2.next)
}
case result2: ParseNg[_] => ParseNg(result2.message, result2.next)
}
}
case result1: ParseNg[_] => ParseNg(result1.message, result1.next)
}
}
}
この時のテストコード配下になります。
class JNumberParserTest extends FlatSpec{
"parse" should "successt" in {
val parser = JNumberParser
val result1 = parser.parse("123.456e-234")
assert(result1.isInstanceOf[ParseOk[_]])
assert(result1.asInstanceOf[ParseOk[JNumber]].value.equals(JNumber(123,456, -234)))
val result2 = parser.parse("0.5")
assert(result2.isInstanceOf[ParseOk[_]])
assert(result2.asInstanceOf[ParseOk[JNumber]].value.equals(JNumber(0,5, 0)))
val result3 = parser.parse("123.+456e-234")
assert(result3.isInstanceOf[ParseOk[_]])
assert(result3.asInstanceOf[ParseOk[JNumber]].value.equals(JNumber(123,0, 0)))
}
}
JSONのbool判定
true, falseのどちらか判定できれば良いので以下のようになります。
object JBoolParser extends JParser[JBool] {
override def parse(input: String): ParseResult[JBool] = {
val parser = Parser.string("true").or(Parser.string("false"))
parser.parse(input) match {
case result: ParseOk[String] => ParseOk(JBool(result.value.equals("true")), result.next)
case result: ParseNg[_] => ParseNg(result.message, result.next)
}
}
}
JSONのnull判定
null判定は以下になります。
object JNullParser extends JParser[JNull] {
override def parse(input: String): ParseResult[JNull] = {
val parser = Parser.string("null")
parser.parse(input) match {
case result: ParseOk[String] => ParseOk(JNull(), result.next)
case result: ParseNg[_] => ParseNg(result.message, result.next)
}
}
}
JSONのvalue判定
JSONの構文定義を見てみるとobject, array, string, number, "true", "false", "null"がvalueとなっています。object, arrayはまだ未定義なのですが先にvalueのパーサーを実装しておきます。 まずJSONのパーサーから複数選べるようにできなければいけないのでJSON用のOrパーサーを準備します。基本パーサーのOrパーサーが使えればそちらにしようかと思ったのですがJParserを拡張した形にしたかったので分けています。
class JOrParser[T <: JValue,U <: JValue](parser1: JParser[T], parser2: JParser[U]) extends JParser[JValue] {
override def parse(input: String): ParseResult[JValue] = {
parser1.parse(input) match {
case result1: ParseOk[T] => ParseOk(result1.value, result1.next)
case result1: ParseNg[_] => {
parser2.parse(input) match {
case result2: ParseOk[U] => ParseOk(result2.value, result2.next)
case result2: ParseNg[_] => ParseNg(result2.message, input)
}
}
}
}
}
インスタンス生成用のトレイトを以下のように修正します。
trait JParser[T <: JValue] extends Parser[T] {
def jor[T <: JValue](parser: JParser[T]): JParser[JValue] = new JOrParser(this, parser)
}
object JParser extends JParser[JValue]
object JValueParser extends JParser[JValue] {
lazy val parser = JNullParser.jor(JBoolParser).jor(JStringParser).jor(JNumberParser).jor(JArrayParser).jor(JObjectParser)
override def parse(input: String): ParseResult[JValue] = parser.parse(input)
}
JSONのobject判定
次にobject判定のパーサーです。jsonのデータ構造では入れ子にすることができるのでobjectのkeyとvalueのうちvalueの方をパースするのに先ほど定義したJValueParserを使います。ただJValueParser内でもJObjectParserを使っていて循環参照になっているのですが、scalaではうまいこと初期化することができてエラーにはならないようです。
object JObjectParser extends JParser[JObject] {
lazy val sp = Parser.string(" ").many()
lazy val leftP = new Pair3(sp, Parser.string("{"), sp)
lazy val rightP = new Pair3(sp, Parser.string("}"), sp)
lazy val kvP = new Pair3(new Pair3(sp, JStringParser, sp), Parser.string(":"), new Pair3(sp, JValueParser, sp))
lazy val kvsP = new Pair2(Parser.string(","), kvP)
lazy val parser = (new Pair2(kvP, kvsP.many())).option()
override def parse(input: String): ParseResult[JObject] = {
leftP.parse(input) match {
case leftResult: ParseOk[(List[String], String, List[String])] => {
parser.parse(leftResult.next) match {
case result: ParseOk[Option[(((List[String], JString, List[String]), String, (List[String], JValue, List[String])),
List[((String, ((List[String], JString, List[String]), String, (List[String], JValue, List[String]))))])]] => {
rightP.parse(result.next) match {
case rightResult: ParseOk[(List[String], String, List[String])] => {
var map: Map[JString, JValue] = Map()
if(result.value.isDefined) {
map += result.value.get._1._1._2 -> result.value.get._1._3._2
result.value.get._2.foreach(a => {
map += a._2._1._2 -> a._2._3._2
})
}
ParseOk(JObject(map), rightResult.next)
}
case rightResult: ParseNg[_] => ParseNg(rightResult.message, rightResult.next)
}
}
case result: ParseNg[_] => ParseNg(result.message, result.next)
}
}
case leftResult: ParseNg[_] => ParseNg(leftResult.message, leftResult.next)
}
}
}
JSONの配列判定
次に配列の判定です。ここでもobjectのパーサーと同様にJValueParserと循環参照的になっていますがうまいこと初期化できているようです。
object JArrayParser extends JParser[JArray] {
lazy val sp = Parser.string(" ").many()
lazy val leftP = new Pair3(sp, Parser.string("["), sp)
lazy val rightP = new Pair3(sp, Parser.string("]"), sp)
lazy val parser = (new Pair2(new Pair3(sp, JValueParser, sp), (new Pair2(Parser.string(","), (new Pair3(sp, JValueParser, sp)))).many())).option()
override def parse(input: String): ParseResult[JArray] = {
leftP.parse(input) match {
case leftResult: ParseOk[(List[String], String, List[String])] => {
parser.parse(leftResult.next) match {
case result: ParseOk[Option[((List[String], JValue, List[String]), List[(String, (List[String], JValue, List[String]))])]] => {
rightP.parse(result.next) match {
case rightResult: ParseOk[(List[String], String, List[String])] => {
var value = List.empty[JValue]
if(result.value.isDefined) {
value = value :+ result.value.get._1._2
result.value.get._2.foreach(a => {
value = value :+ a._2._2
})
}
ParseOk(JArray(value), rightResult.next)
}
case rightResult: ParseNg[_] => ParseNg(rightResult.message, rightResult.next)
}
}
case result: ParseNg[_] => ParseNg(result.message, result.next)
}
}
case leftResult: ParseNg[_] => ParseNg(leftResult.message, leftResult.next)
}
}
}
JSON判定のパーサー
最後にJSONを判定するためのパーサーです。
object JsonParser extends JParser[JValue]{
lazy val parser = new Pair2(JObjectParser.jor(JArrayParser), Parser.eof)
override def parse(input: String): ParseResult[JValue] = {
parser.parse(input) match {
case result: ParseOk[(JValue, String)] => ParseOk(result.value._1, result.next)
case result: ParseNg[_] => ParseNg(result.message, result.next)
}
}
}
テストコードを実行しても大丈夫だったのでJSONはパースできてそうです。
class JsonParserTest extends FlatSpec {
"parse" should "successt" in {
val parser = JsonParser
val result1 = parser.parse(" {\"a\": [ [1, 2, 3,4], {} ]} ")
assert(result1.isInstanceOf[ParseOk[JValue]])
assert(result1.asInstanceOf[ParseOk[JValue]].value.equals(JObject(
Map(JString("a") -> JArray(List(JArray(List(JNumber(1, 0, 0), JNumber(2, 0, 0), JNumber(3, 0, 0), JNumber(4, 0, 0))), JObject(Map.empty[JString, JValue]))))
)))
val result2 = parser.parse(" [ [1, 2, 3,4], {} ] ")
assert(result2.isInstanceOf[ParseOk[JValue]])
assert(result2.asInstanceOf[ParseOk[JValue]].value.equals(JArray(
List(JArray(List(JNumber(1, 0, 0), JNumber(2, 0, 0), JNumber(3, 0, 0), JNumber(4, 0, 0))), JObject(Map.empty[JString, JValue]))
)))
}
"parse" should "fail" in {
val parser = JsonParser
val result1 = parser.parse(" {\"a\": [ [1, 2, 3,4], {} ]}, {}")
assert(result1.isInstanceOf[ParseNg[_]])
}
}
今回使ったソースは以下にあげております。
https://github.com/teruuuuuu/parsers/tree/master/scala/parsers
