自作JSONパーサ in Scala
はじめに
自作JSONパーサを作る記事ではパーサコンビネータを定義してそれを利用していくという説明がよくなされる。しかし、自作パーサ初心者にはコンビネータをどのように作り上げていくかわからない。
そこでJSONパーサを作りながら必要に応じて基本的なパーサやパーサの合成方法を定義していき、最終的にJSONパーサとそれなりのコンビネータを作り上げることを目的とする。
JSONの仕様についてはどんな要素で構成されているかがパッと見でわかりやすいためこちらを参考にした。このページの右側の一番下のwsからパーサを定義していく。
パーサの型定義
パーサは文字列を入力してパース結果を返す関数であると考えられるので下記のように定義する。
type Parser[T] = String => ParseResult[T]
パースに成功した場合、パース結果と残りの文字列を返却する。残りの文字列は後続のパーサの入力となる。パースに失敗した場合、どこで失敗したかがわからないとデバッグが辛いので残りの文字列を持たせておく。
sealed trait ParseResult[+T]
case class Success[T](value: T, next: String) extends ParseResult[T]
case class Failure(next: String) extends ParseResult[Nothing]
Tを任意の型としてParseResult[T]にFailureを入れられるように型パラメータTは共変にする。
wsの定義
JSONで空白扱いされる文字が定義されている。
ws
""
'0020' ws
'000A' ws
'000D' ws
'0009' ws
wsのパーサを定義するにはまず特定の文字をパースできる必要がある。指定の1文字だけをパースするパーサがあると便利そうである。
def char(c: Char): Parser[Char] = input =>
if (input.nonEmpty && input.head == c) { Success(c, input.drop(1)) }
else { Failure(input) }
また空白扱いされる文字は「' 'または'\n'または'\r'または'\t'」であるので、「または」を表すパーサの合成方法を定義する。パーサの合成はParser[T]のメソッドとして定義する。
// 以後、extension[T](p1: Parser[T])は省略する
extension[T](p1: Parser[T]) {
def or[U >: T](p2: => Parser[U]): Parser[U] = input =>
p1(input) match {
case result @ Success(_, _) => result
case Failure(_) => p2(input)
}
}
wsは空白扱いする文字の0回以上の繰り返しである。これを表現するためにパーサを0回以上の繰り返しに変換するメソッドを定義する。
def many: Parser[List[T]] = {
@tailrec
def loop(input: String, acc: List[T]): (List[T], String) =
p1(input) match {
case Success(v, next) => loop(next, acc ++ List(v))
case Failure(_) => (acc, input)
}
input =>
val (result, next) = loop(input, Nil)
Success(result, next)
}
wsはこれらを使用して下記のように定義できる。
def ws: Parser[List[Char]] =
(char(' ') or char('\n') or char('\r') or char('\t')).many
onenineの定義
1から9までの数値を表す。
onenine
'1' . '9'
「1から9までのうちのいずれか」を表現するために、文字のリストのうちのいずれか一致するものをパースするパーサを作れると便利そうである。
def oneOf(chars: Set[Char]): Parser[Char] = input =>
if (input.nonEmpty && chars.contains(input.head)) {
Success(input.head, input.drop(1))
} else { Failure(input) }
onenineはこれを使用して下記のように定義できる。
def onenine: Parser[Char] =
oneOf(Set('1', '2', '3', '4', '5', '6', '7', '8', '9'))
digitの定義
0から9までの数値を表す
digit
'0'
onenine
digitはorを使用して下記のように定義できる。
def digit: Parser[Char] =
char('0') or onenine
digitsの定義
0〜9が1つ以上並ぶ数値列を表す。
digits
digit
digit digits
「xxが1つ以上並ぶ」を表現するためにパーサを1回以上の繰り返しに変換するメソッドを定義する。
まずxxをパースして成功したらyyをパースするという逐次実行を表現する合成方法を定義する。
def combine[U](p2: => Parser[U]): Parser[(T, U)] = input =>
p1(input) match {
case Success(v1, next1) =>
p2(next1) match {
case Success(v2, next2) => Success((v1, v2), next2)
case Failure(_) => Failure(next1)
}
case Failure(_) => Failure(input)
}
次にcombineの結果はタプルなのでリストに変換する必要がある。これを実現するため、結果を変換するメソッドを定義する。
def map[U](f: T => U): Parser[U] = input =>
p1(input) match {
case Success(v, next) => Success(f(v), next)
case Failure(_) => Failure(input)
}
combineとmapを使うことで1回以上の繰り返しを表現できる。
def many1: Parser[List[T]] =
p1.combine(p1.many).map { case (v, vs) => v :: vs }
many1を使うとdigitsは下記のように定義できる。
def digits: Parser[List[Char]] =
digit.many1
flatMapを使う
flatMapを定義するとcombineとmapはflatMapを使って表現できる。
def flatMap[U](f: T => Parser[U]): Parser[U] = input =>
p1(input) match {
case Success(v, next) => f(v)(next)
case Failure(_) => Failure(input)
}
def map[U](f: T => U): Parser[U] =
p1.flatMap(t => input => Success(f(t), input))
def combine[U](p2: => Parser[U]): Parser[(T, U)] =
p1.flatMap(v1 => p2.map(v2 => (v1, v2)))
integerの定義
整数の表現が定義されている。
integer
digit
onenine digits
'-' digit
'-' onenine digits
定義通りにdigitを先にパースするとdigitが成功した時、次の数字をパースせずにintegerが終了してしまうので先にonenine digitsをパースするように定義をする。
def integer: Parser[Int] =
(onenine.combine(digits).map { case (d, ds) => d :: ds } or
digit.map(d => List(d)) or
char('-')
.combine(onenine.combine(digits))
.map { case (sign, (d, ds)) => sign :: d :: ds } or
char('-').combine(digit).map { case (sign, d) => List(sign, d) })
.map(_.mkString.toInt)
signの定義
数値の指数表記の符号が定義されている。
sign
""
'+'
'-'
符号は+または-であり、省略可能である。省略された場合の定義はここからは読み取れないので既存の実装の振る舞いを調べて今回の振る舞いもそれに合わせることにする。ChromeのdevツールでJSON.parse('1e100')を実行したところ1e+100と返却されたので今回は省略されたら+扱いとする。省略された値を補うことを実現するために指定の値をパース結果として返却するだけのパーサがあると便利そうである。
def succeeded[T](v: T): Parser[T] = input => Success(v, input)
これを使うことでsignは下記のように定義できる。
def sign: Parser[Char] =
char('+') or char('-') or succeeded('+')
exponentの定義
数値の指数表現の指数部が定義されている。
exponent
""
'E' sign digits
'e' sign digits```
指数部は省略可能なので下記のように定義する。
def exponent: Parser[List[Char]] =
(char('E') or char('e'))
.combine(sign)
.combine(digits)
.map { case ((e, s), d) => e :: s :: d } or succeeded(Nil)
fractionの定義
数値の小数部が定義されている。
fraction
""
'.' digits
小数部は省略可能なので下記のように定義する。
def fraction: Parser[List[Char]] =
char('.')
.combine(digits)
.map { case (dot, digits) => dot :: digits } or succeeded(Nil)
numberの定義
JSONで扱える数値表現が定義されている。
number
integer fraction exponent
この数値表現を扱うために適当な型を定義しておく。
case class Number(int: Int, faction: List[Char], exponent: List[Char]) {
override def toString: String = s"$int${faction.mkString}${exponent.mkString}"
}
この型を使ってnumberを定義する。
def number: Parser[Number] =
integer
.combine(fraction)
.combine(exponent)
.map { case ((i, frac), exp) => Number(i, frac, exp) }
hexの定義
16進数のリテラルが定義されている。
hex
digit
'A' . 'F'
'a' . 'f'
orとoneOfを使って簡単に定義できる。
def hex: Parser[Char] =
digit or
oneOf(Set('A', 'B', 'C', 'D', 'E', 'F')) or
oneOf(Set('a', 'b', 'c', 'd', 'e', 'f'))
escapeの定義
バックスラッシュと組み合わせてエスケープシーケンスになる文字/文字列が定義されている。
escape
'"'
'\'
'/'
'b'
'f'
'n'
'r'
't'
'u' hex hex hex hex
flatMapを定義することでfor式を使ってスッキリと記述できるがここでは愚直にcombineを利用する。
def escape: Parser[List[Char]] =
oneOf(Set('"', '\\', '/', 'b', 'f', 'n', 'r', 't'))
.map(c => List(c)) or
char('u')
.combine(hex)
.combine(hex)
.combine(hex)
.combine(hex)
.map { case ((((u, h1), h2), h3), h4) => List(u, h1, h2, h3, h4) }
characterの定義
JSONで扱える文字が定義されている。
character
'0020' . '10FFFF' - '"' - '\'
'\' escape
文字として利用できる条件として範囲指定と除外条件の2つが含まれているので、1文字取ってきてその文字が条件に合致しているかを判定して合致してれば成功、そうでなければ失敗という処理が書ければ範囲も除外も実現できそうである。まずは先頭の1文字を返すパーサchar1を定義する。
def char1: Parser[Char] = input =>
if (input.nonEmpty) Success(input.head, input.drop(1))
else { Failure(input) }
次にパース結果が条件を満たしているときのみ成功とするfilterを定義する。除外条件をシンプルに書けるようにfilterNotも定義しておく。
def filter(f: T => Boolean): Parser[T] = input =>
p1(input) match {
case Success(v, next) if f(v) => Success(v, next)
case Success(_, _) | Failure(_) => Failure(input)
}
def filterNot(f: T => Boolean): Parser[T] =
p1.filter(t => !f(t))
エスケープシーケンスを1文字にしてパース結果として返すためにエスケープシーケンスのList[Char]をOption[Char]にして返す処理を用意する。
def toEscapeSequence(escapes: List[Char]): Option[Char] =
escapes match {
case List('\\', '"') => Some('"')
case List('\\', '\\') => Some('\\')
case List('\\', '/') => Some('/')
case List('\\', 'b') => Some('\b')
case List('\\', 'f') => Some('\f')
case List('\\', 'n') => Some('\n')
case List('\\', 'r') => Some('\r')
case List('\\', 't') => Some('\t')
case List('\\', 'u', a, b, c, d) =>
val hex = List(a, b, c, d).mkString
Try(Integer.parseInt(hex, 16)).toOption.map(_.toChar)
case _ => None
}
これをパース結果に適用するだけだとParser[Option[Char]になってしまうので、1文字への変換に成功した時だけ結果を取り出してパース結果としたい。フィルタと変換を同時に行うcollectがあると便利そうである。
def collect[U](pf: PartialFunction[T, U]): Parser[U] = input =>
p1(input) match {
case Success(v1, next) =>
pf.lift(v1) match {
case Some(v2) => Success(v2, next)
case None => Failure(input)
}
case Failure(_) => Failure(input)
}
これらを用いてcharacterは下記のように定義できる。
def character: Parser[Char] =
char1
.filter(c => c.toInt >= 0x0020 && c.toInt <= 0x10ffff)
.filterNot(c => Set('"', '\\').contains(c)) or
char('\\')
.combine(escape)
.map { case (c, l) => toEscapeSequence(c :: l) }
.collect { case Some(v) => v }
charactersの定義
文字の列が定義されている。
characters
""
character characters
characterの0回以上の繰り返しである。
def characters: Parser[List[Char]] =
character.many
stringの定義
JSONにおける文字列の表現が定義されている。
string
'"' characters '"'
文字の列がダブルクォートで囲われているだけである。
def string: Parser[String] =
char('"')
.combine(characters)
.combine(char('"'))
.map { case ((_, cs), _) => cs.mkString }
booleanの定義
JSONにおける真偽値としてbooleanが定義されているわけではないが、あると便利なのでvalueの定義から抜き出して勝手に定義する。
boolean
"true"
"false"
特定の文字列をパースするためにcharとcombineを何度も適用するのは辛いのでcharの文字列版として指定の文字列をパースできるstrを用意しておくと便利そうである。
def str(literal: String): Parser[String] = input =>
if (input.startsWith(literal)) {
Success(literal, input.substring(literal.length))
} else { Failure(input) }
strを使ってbooleanを定義する。
def boolean: Parser[Boolean] =
str("true").map(_ => true) or
str("false").map(_ => false)
nullの定義
JSONにおけるnull値としてnullというパーサーが定義されているわけではないが、あると便利なのでboolean同様にvalueの定義から抜き出して勝手に定義する。
null
"null"
null値は下記のように定義できる。
def `null`: Parser[Null] =
str("null").map(_ => null)
valueの定義
JSONにおける値が定義されている。
value
object
array
string
number
"true"
"false"
"null"
objectとarrayは定義にvalueが含まれており、現時点ではまだ定義してないのでここではobjectをarrayを除いたvalueを定義する。
JSONの値として複数の型を扱うのでJSONの値を表す型を定義する。
sealed trait JsonValue
case object JsonNull extends JsonValue
case class JsonBoolean(value: Boolean) extends JsonValue
case class JsonNumber(value: Number) extends JsonValue
case class JsonString(value: String) extends JsonValue
case class JsonArray(value: List[JsonValue]) extends JsonValue
case class JsonObject(value: ListMap[String, JsonValue]) extends JsonValue
JsonValueを使ってobjectをarrayを除いたvalueを定義する
def value: Parser[JsonValue] =
`null`.map(_ => JsonNull) or
boolean.map(b => JsonBoolean(b)) or
number.map(n => JsonNumber(n)) or
string.map(s => JsonString(s))
elementの定義
valueの前後にはwhitespaceの存在が許容されることを意味する。
element
ws value ws
whitespaceは値として利用しないのでvalueの値だけをパース結果として返却する。
def element: Parser[JsonValue] =
ws.combine(value)
.combine(ws)
.map { case ((_, v), _) => v }
elementsの定義
複数の値の記法が定義されている。
elements
element
element ',' elements
最初のelementの後はカンマとelementの0回以上の繰り返しとして表現できる。
def elements: Parser[List[JsonValue]] =
element
.combine(char(',').combine(element).map(_._2).many)
.map { case (v, vs) => v :: vs }
arrayの定義
JSONにおける配列が定義されている。
array
'[' ws ']'
'[' elements ']'
[と]でwhitespaceかelementsが囲われているので下記のように定義できる。
def array: Parser[JsonArray] =
char('[')
.combine(ws)
.combine(char(']'))
.map(_ => JsonArray(List.empty)) or
char('[')
.combine(elements)
.combine(char(']'))
.map { case ((_, es), _) => JsonArray(es) }
memberの定義
JSONにおけるkey-valueの組の表現が定義されている。
member
ws string ws ':' element
memberは下記のように定義できる。
def member: Parser[(String, JsonValue)] =
ws.combine(string)
.combine(ws)
.map { case ((_, key), _) => key }
.combine(char(':'))
.combine(element)
.map { case ((k, _), v) => (k, v) }
membersの定義
key-valueが複数ある時の記法が定義されている。
members
member
member ',' members
elementsと同様にカンマ区切りのフォーマットのなので下記のように定義できる。
def members: Parser[List[(String, JsonValue)]] =
member
.combine(char(',').combine(member).map(_._2).many)
.map { case (v, vs) => v :: vs }
objectの定義
JSONにおけるobjectが定義されている。
object
'{' ws '}'
'{' members '}'
whitespaceかmembersが{と}で囲われている。
def `object`: Parser[JsonObject] =
char('{')
.combine(ws)
.combine(char('}'))
.map(_ => JsonObject(ListMap.empty)) or
char('{')
.combine(members)
.combine(char('}'))
.map { case ((_, ms), _) => JsonObject(ListMap.from(ms)) }
valueの定義
objectとarrayの定義ができたのでvalueに追加する。
def value: Parser[JsonValue] =
`null`.map(_ => JsonNull) or
boolean.map(b => JsonBoolean(b)) or
number.map(n => JsonNumber(n)) or
string.map(s => JsonString(s)) or
array or `object`
jsonの定義
JSONが定義されている。
json
element
elementを使用して簡易的なJSONのパース処理を定義する。
def parse(input: String): JsonValue =
element(input) match {
case Success(json, _) => json
case Failure(next) =>
throw new IllegalArgumentException(s"パーズに失敗しました next: $next")
}
まとめ
下記のパーサとメソッドを用意することでJSONパーサを作れることがわかった。下記の他にも空白や区切り文字などはパース結果として利用することがないのでパース結果を読み飛ばすskipなど適宜便利そうなパーサやメソッドを追加してコンビネータを充実させるのがよさそうである。
パーサ
char, succeeded, oneOf, char1, str
メソッド
or, many, many1, combine, map, filter, filterNot, collect
補足
合成メソッドの引数に渡すパーサのうち、メソッド内部で必ず実行されるもの以外はp2: => Parser[U]のようにして遅延評価にしている。これはパーサの定義が循環した時にスタックオーバーフローが起きづらくすることを目的としている。
def p1: Parser[Char] = char('a') or p1
極端な例だが上記のp1は入力文字列の先頭が'a'だった場合はパースに成功する。もしorの引数が正格評価だった場合、p1の定義が循環しているのでorの引数のp1を評価するために繰り返し呼び出しが行われてchar('a')の実行前にスタックオーバーフローになる。
参考資料
- Introducing JSON
- McKeeman Form
- https://www.crockford.com/mckeeman.html
- 本文中のJSONの仕様の定義はこちらから抜粋させていただいている
- N予備校Scala講座
- Scala関数型デザイン&プログラミング ―Scalazコントリビューターによる関数型徹底ガイド
Discussion