パーサジェネレータでパーサを出力してみる
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") }