パーサジェネレータでパーサを出力してみる
BNFを読み込んでパーサを出力し、実際にパースしASTの出力が確認できました。
パーサを出力するものはパーサジェネレータというと思うのですが、こちらはパーサコンビネータを使っています。パーサコンビネータはパーサのパーツを組み合わせてより複雑なパーサを出力できるもので、今回はパーサコンビネータの出力がParser[Parser[BnfParseResult]]のようになっています。これはBNFを読み込んだ結果としてParser[BnfParseResult]を出力し、さらにこれに対して文字列を読み込ませることでBnfParseResultを出力するというものになっています。
パーサコンビネータのライブラリとして以下を使用しました。
これは表現力のあるパーサコンビネータで、Jsonパーサのテストコードを見てみると80行程度でJsonのパーサを定義できており強力さが分かるかと思います。
scomb/JsonSpec.scala at master · kmizu/scomb · GitHub
BNFのパーサジェネレータの前にJsonパーサで使っている部品の方で確認してみると、文字列パーサは以下のようになっています。型としてはParser[String]なので文字列を読み込ませるとStringを出力するというものになっています。for式を見てみるとダブルクォートを読み飛ばし、エスケープありの文字列をcontentsに入れて、あとダブルクォートとスペースを呼び飛ばし、contentsの文字列をパースの出力結果としています。for式を使うとパーサコンビネータを組み合わせて使いやすいというのが分かるかと思います。
lazy val string: Parser[String] = rule{for {
_ <- $("\"")
contents <- ($("\\") ~ any ^^ { case _ ~ ch => escape(ch).toString} | except('"')).*
_ <- $("\"").l("double quote")
_ <- DefaultSpace.*
} yield contents.mkString}
それではBNFのパーサジェネレータの方に移ろうと思いますが、まずパース結果として以下のクラスを使っています。
sealed abstract class BnfParseResult {
}
case class ParsedStr(str: String) extends BnfParseResult {
override def toString = s"""\"${str}\""""
}
case class ParsedSymbol(symbol: String, list: List[BnfParseResult]) extends BnfParseResult {
override def toString = s"""{\"symbol\":\"${symbol}\", \"value\":[${list.map(_.toString).mkString(",")}]}"""
}
それからBNFのパーサジェネレータについては以下のようになりました。型がParser[Parser[BnfParseResult]]となっているのでBNFの定義を読み込んだ後にParser[BnfParseResult]を出力し、さらに文字列を読み込ませることでBnfParseResultを出力するというものになっています。
def bnf_parser: Parser[Parser[BnfParseResult]] = for {
_ <- DefaultSpace.*
symbol <- symbol
_ <- DefaultSpace.*
_ <- $("::=")
_ <- DefaultSpace.*
definition <- definition
_ <- DefaultSpace.*
} yield definition ^^ {
case (a: ParsedStr) => ParsedSymbol(symbol, List(a))
case (a: ParsedSymbol) => ParsedSymbol(symbol, a.list)
}
例えばBNFの定義が<root> ::= "abc"であればdefinitionがParsedStrとなるのでParsedSymbol(symbol, List(a)を出力という風になっています。<abc> ::= "abc"と<root> ::= <abc>を読み込んでrootのシンボルでパースするとdefinitionがParsedSymbolになるのでParsedSymbol(symbol, a.list)
を出力となります。
実際に確認すると以下のようにASTが出力が確認できました。
確認のコードは以下のようになっていましてBnfParser.apply(List(でBNFの定義を読み込み、読み込みに成功したらparser.parse(でパースしBnfParseResultを出力しています。
BnfParser.apply(List("<abc> ::= \"abc\"+", "<root> ::= \"root\" + <abc>")) match {
case Result.Success(parser) =>
parser.parse("rootrootabc")
}
