31. Combinator Parsing
時々小規模の特定目的の言語(フォーマット)を扱う必要があるかもしれない。
ソフトのコンフィグファイル、Wiki記法、Markdo記法、JSON
XMLよりももっと簡単に読み書きしたい。
検索用の制御文字入りの文字列の解釈
構造を解析するためのパーサが必要。
オリジナルのパーサを自作する。
難しい。工数が掛かる。
既存のパーサジェネレータを使う。
沢山のパーサジェネレータがある。
C言語: Yacc、Bison
Java: ANTLR
スキャナージェネレータも一緒に使う事が多い。
Lex、Flex、JFlex
使い方を憶える必要がある。(曖昧なエラーメッセージを含む)
プログラムとの結合方法を調べて合わせる必要がある。
プログラミング言語や開発環境の制約も受けるかもしれない。
内部DSLを作成する。
Scalaでパーサを構成するためのコンビネータを定義する。
文脈自由文法の構成要素と一対一で対応させられるので分かりやすい。
本章で出てくる新しい言語仕様はaliasingのみ。
他はこれまで出てきた言語仕様を組み合わせて実現する。
parameterized types, abstract types, functions as objects, operator overloading, by-name parameters, and implicit conversions
本章はこれまでの章よりも難しい。
コンパイラに関するバックグランドがあると分かりやすい。
正規文法と文脈自由文法の予備知識が必要。
31.1 Example: Arithmetic expressions
文脈自由文法の記法
| 選択
\{ ... \} 0回以上の繰り返し。
[ ... ] オプション
算術計算の文脈自由文法の定義
expr ::= term \{"+" term | "-" term\}.
term ::= factor \{"*" factor | "/" factor\}.
factor ::= floatingPointNumber | "(" expr ")".
加減算と乗除算の優先度も組み込まれている。
Scalaのコンビネータパーサへの変換
単純な文字列置換で変換できる。
trait JavaTokenParsersを継承したクラスに含める。
floatingPointNumberはこのtraitに含まれている。
パーサはメソッドとして定義するので"def"をつける。
result typeを指定するために": Parser[Any] ="
シンボルの連続を表すためにシンボル間のスペースを"~"に変える。
"~"はoperatorなので前後にスペースを入れてもOK。
| => | のまま。
\{ ... \} => rep( ... )
[ ... ] => opt( ... )
算術計算のScalaのコンビネータパーサの定義
import scala.util.parsing.combinator._
class Arith extends JavaTokenParsers {
def expr: Parser[Any] = term~rep("+"~term | "-"~term)
def term: Parser[Any] = factor~rep("*"~factor | "/"~factor)
def factor: Parser[Any] = floatingPointNumber | "("~expr~")"
}
31.2 Running your parser
object ParseExpr extends Arith {
def main(args: Array[String]) {
println("input : "+ args(0))
println(parseAll(expr, args(0)))}}
上記でスクリプトの引数の文字列が文法に従っているか判定出来る。
parseAllの代わりにparseを使えば先頭から文法を満たしている部分までを解析。
$ scala ParseExpr "2 * (3 + 7)"
input: 2 * (3 + 7)
[1.12] parsed: ((2~List((*~(((~((3~List())~List((+
~(7~List())))))~)))))~List())
toStringメソッドが強力なので、Parseを見やすく出力出来ている。
1~12文字目までをparseした結果のleafに置き換えられている。
$ scala ParseExpr "2 * (3 + 7))"
input: 2 * (3 + 7))
[1.12] failure: `-' expected but `)' found
2 * (3 + 7))
^
失敗した場合の例。
toStringメソッドが強力なのでコマンドっぽく使えている。
31.3 Basic regular expression parsers
正規表現にマッチするパーサを作れる。
object MyParsers extends RegexParsers {
val ident: Parser[String] = """[a-zA-Z_]\w*""".r
}
上記はJavaの識別子にマッチするパーサ
継承関係
scala.util.parsing.combinator
RegexParsers
JavaTokenParsers
Arith
floatingPointNumber
31.4 Another example: JSON
JSON: JavaScript Object Notation
データをやり取りするのに良く使われるフォーマット
JSONの文脈自由文法の定義
value ::= obj | arr | stringLiteral |
floatingPointNumber |
"null" | "true" | "false".
obj ::= "{" [members] "}".
arr ::= "[" [values] "]".
members ::= member \{"," member\}.
member ::= stringLiteral ":" value.
values ::= value \{"," value\}.
JSONのパーサ
class JSON extends JavaTokenParsers {
def value : Parser[Any] = obj | arr |
stringLiteral |
floatingPointNumber |
"null" | "true" | "false"
def obj : Parser[Any] = "{"~repsep(member, ",")~"}"
def arr : Parser[Any] = "["~repsep(value, ",")~"]"
def member: Parser[Any] = stringLiteral~":"~value
}
repsep(member, ",")は0個以上のカンマ区切りのmemberの並び。
repsepもコンビネータ
?? 入力文字列の空白文字は自動的に区切り文字として扱われている ??
31.5 Parser output
パーサの戻り値のデフォルト動作
文字列: そのまま
正規表現: マッチした文字列そのまま
JavaTokenParsersを継承しているstringLiteral、floatingPointNumberも同じ。
正規表現パーサで実現しているから。
列挙P~Q: case class ~のインスタンス。~(P, Q)
列挙P~>Q: Q
列挙P<~Q: P
選択P | Q: パースが成功した方
繰り返しrep(P), repseq(P, Q): PのList
オプションopt(P): Some(R)かNone
デフォルトの戻り値では使いにくいの^^オペレータで変換する。
P ^^ f: Pのパース結果をRとすると、f(R)に変換して返す。
小数をDoubleに変換するパーサ
floatingPointNumber ^^ (_.toDouble)
文字列"true"をScalaのtrueに変換するパーサ
"true" ^^ (x => true)
パースした結果を使いやすくしたJSONのパーサ
class JSON1 extends JavaTokenParsers {
def obj: Parser[Map[String, Any]] =
"{"~> repsep(member, ",") <~"}" ^^ (Map() ++ _)
def arr: Parser[List[Any]] =
"["~> repsep(value, ",") <~"]"
def member: Parser[(String, Any)] =
stringLiteral~":"~value ^^
{ case name~":"~value => (name, value) }
def value: Parser[Any] = (
obj
| arr
| stringLiteral
| floatingPointNumber ^^ (_.toDouble)
| "null" ^^ (x => null)
| "true" ^^ (x => true)
| "false" ^^ (x => false)
)
}
Summary of parser combinators
"..." literal
"...".r regular expression
P~Q sequential composition
P <~ Q, P ~> Q sequential composition; keep left/right only
P | Q alternative
opt(P) option
rep(P) repetition
repsep(P, Q) interleaved repetition
P ^^ f result conversion
Turning off semicolon inference
下記の様に|を行末にすれば括弧が無くても問題ない。
def value: Parser[Any] =
obj |
arr |
stringLiteral |
...
パーサを書くときは|を行頭に書きたい事があるので、その場合は括弧が必要。
def value: Parser[Any] = (
obj
| arr
| stringLiteral
...
Section 4.2にあるように、括弧が無いと文末と解釈されてしまうから。
Symbolic versus alphanumeric names
パーサコンビネータをアルファベット表記にすべきか? 記号表記にすべきか?
記号表記のパーサコンビネータの利点
短い。
優先度と結合側を制御できる。
それなりの記号を考えて割り当てれば。
文法とコンビネータが見た目に分かりやすい。
記号表記のパーサコンビネータの欠点
憶える必要がある。知ってないと使えない。
そもそもうろ覚えでは使えないから、あまり欠点にならないはず?
Choosing between symbolic and alphabetic names
その記号を使うのが一般的なら記号を使う。
足し算にはaddではなくて+を使う。
casual readersにも分かりやすくしたかったらアルファベットを使う。
DSLには記号を使う。
DSLはアルファベットにしてもcasual readersには多分理解できない。
31.6 Implementing combinator parsers
以下の節ではこれまで述べたパーサの実装について解説する。
一般的なコンビーネータの設計原則について知ることが出来る。
以下の節では特に断らない限り下記を前提とする。
scala.util.parsing.combinator.Parsers traitの定義内での実装の話。
パーサの本質は、何らかのinput typeからparse resultへの関数。
type Parser[T] = Input => ParseResult[T]
Parser input
type Input = Reader[Elem]
Elemは抽象型であり、サブクラスのパーサで定義する必要がある。
ReaderはStreamと同様だが読み込まれた場所を記録している。
scala.util.parsing.input
ElemはCharの場合も多い。
RegexParsers、 JavaTokenParsers
Elemはseparate lexerで分割したtokensであっても良い。
Parser results
成功と失敗の二つのサブクラスをがある。
sealed abstract class ParseResult[+T]
case class Success[T](result: T, in: Input)
extends ParseResult[T]
case class Failure(msg: String, in: Input)
extends ParseResult[Nothing]
パーサをチェーンするために成功時にはInputも含まれている。
純粋関数的なアプローチでパースしている。
副作用無しでstreamの内容は変わらない。
パーサは処理しなかった残りの部分を次のパーサに渡す。
失敗するときにもInputを含めているがこれはエラーメッセージを出すため。
Tはcovariant(共変)
Stringを返すパーサはAnyRefを返すパーサと互換性があると言う事。
The Parser class
Parserクラスの実装
abstract class Parser[+T] extends (Input => ParseResult[T])
{ p =>
def apply(in: Input): ParseResult[T]
def ~ ...
def | ...
...
}
Parserは実際はfunction type Input => ParseResult[T]を継承したクラス。
scala.Function1[Input, ParseResult[T]]を継承している。
apply()を定義しているが、これはドキュメントで使うため。
Aliasing this
abstract class Parser[+T] extends (Input => ParseResult[T]) { p => ...
p => の部分はthisのaliasを宣言している。
id => で val id = this と同様な使い方が出来る。
Section 27.4のtraitのself typeと同様の使い方。
inner classからouter classのthisにアクセスしたいときに使う。
class Outer { outer =>
class Inner {
println(Outer.this eq outer) // prints: true
}
}
Outer.thisと同じ意味だが、短くて分かりやすい任意の名前を付ける事が出来る。
Single-token parsers
どんな単一のtokenにも適用できる一般的なパーサelemを定義している。
def elem(kind: String, p: Elem => Boolean) =
new Parser[Elem] {
def apply(in: Input) =
if (p(in.first)) Success(in.first, in.rest)
else Failure(kind +" expected", in)
}
pはパースするための関数。
kindはエラーメッセージ表示用のどんなtokenを期待しているのか示す文字列。
Sequential composition
列挙演算子~はParserクラスのメソッドとして実装されている。
abstract class Parser[+T] ... { p =>
...
def ~ [U](q: => Parser[U]) = new Parser[T~U] {
def apply(in: Input) = p(in) match {
case Success(x, in1) =>
q(in1) match {
case Success(y, in2) => Success(new ~(x, y), in2)
case failure => failure
}
case failure => failure
}
}
自身がパーサpで引数としてパーサqを取る。
そこから新しいpとqの列挙パーサをinner classとして生成して返す。
p(in)のpはパーサpのthisのalias
type T~Uはcase class ~のパラメタ化した~[T, U]と同じ意味。別表記。
p op qがop(p, q)の別表記であるのと同様。
<~、~>も~を使って定義出来る。
def <~ [U](q: => Parser[U]): Parser[T] = (p~q) ^^ { case x~y => x }
def ~> [U](q: => Parser[U]): Parser[U] = (p~q) ^^ { case x~y => y }
Alternative composition
選択演算子|もParserのメソッドとして実装されている。
def | (q: => Parser[T]) = new Parser[T] {
def apply(in: Input) = p(in) match {
case s1 @ Success(_, _) => s1
case failure => q(in)
}
}
自身がパーサpで引数としてパーサqを取る。
そこから新しいpとqの選択パーサをinner classとして生成して返す。
p(in)のpはパーサpのthisのalias
p(in)が成功したらpの結果を全体の結果とする。
qについては評価しない。short circuit
p(in)が成功したら同じ入力をqに適用する。
pが読んだ後の残りではなくて、巻き戻して適用する。
実際はpが読む前の入力を保持しているのでそれを適用する。
両方失敗した時はqのエラーメッセージを出力する。
この実装の良し悪しはSection 31.9で述べる。
Dealing with recursion
~や|の引数qはby-nameパラメタになっている。
実際にパラメタを演算に使うまで評価されない。
これで再帰的な定義が可能になる。
o def parens = floatingPointNumber | "("~parens~")"
通常のby-valueパラメタだったら無限呼び出しになってstack overflowになる。
Result conversion
result変換関数の適用もParserのメソッド。
def ^^ [U](f: T => U): Parser[U] = new Parser[U] {
def apply(in: Input) = p(in) match {
case Success(x, in1) => Success(f(x), in1)
case failure => failure
}
}
自身がパーサpで引数として変換関数fを取る。
そこから新しいresultを持つパーサをinner classとして生成して返す。
p(in)のpはパーサpのthisのalias
Parserクラスのメソッド定義はこれで終わり。
Parsers that don't read any input
Parsers traitの中に入力を消費しない二つのメソッドが定義されている。
Parserクラスの中ではないので注意。Parserクラスもtraitの中の定義の一つ。
def success[T](v: T) = new Parser[T] {
def apply(in: Input) = Success(v, in)
}
def failure(msg: String) = new Parser[Nothing] {
def apply(in: Input) = Failure(msg, in)
}
successはresultを取って入力を読まずに成功するパーサ。
failureはエラーメッセージを取って入力を読まずに失敗するパーサ。
Option and repetition
Parsers traitの中でオプションopt、繰り返しrep、repsepも定義されている。
列挙、選択、結果変換の組み合わせで実装出来る。
def opt[T](p: => Parser[T]): Parser[Option[T]] =
p ^^ Some(_) | success(None)
def rep[T](p: Parser[T]): Parser[List[T]] =
p~rep(p) ^^ { case x~xs => x :: xs } | success(List())
def repsep[T, U](p: Parser[T], q: Parser[U]): Parser[List[T]] =
p~rep(q~> p) ^^ { case r~rs => r :: rs } | success(List())
31.7 String literals and regular expressions
// 正規表現と文字列リテラルのパーサはParsers traitのsubtraitで定義されている。
trait RegexParsers extends Parsers {
// 入力を文字Charに特化したParsers
type Elem = Char
// implicitなのでStringやRegexをパーサに変換する必要があれば自動的に呼ばれる。
// 従って文法の定義の時の文に直接文字列や正規表現を書ける。
// "("~exp~")"はliteral("(")~exp~literal(")")に暗黙変換される。
implicit def literal(s: String): Parser[String] = ...
implicit def regex(r: Regex): Parser[String] = ...
// シンボル間の空白の扱いも定義している。
// デフォルトは全て読み飛ばす設定。
protected val whiteSpace = """\s+""".r
}
// シンボル間の空白の扱いを変えたいときはwhiteSpaceを上書きする。
// 下記にすれば空白を読み飛ばさずにそのままパースする設定になる。
object MyParsers extends RegexParsers {
override val whiteSpace = "".r
...
}
31.8 Lexing and parsing
文法(syntax)解析は字句(lexical)解析と構文(syntactical)解析に分けられる。
構文解析をパースと言う事も時々ある。
字句解析の問題をパースの問題と言う事もある。
ScalaのParsers traitは両方に使う事が出来る。
ElemをCharにすれば字句解析
Elemをtokenにすれば構文解析
字句解析用のコンビネータ scala.util.parsing.combinator.lexical
構文解析用のコンビネータ scala.util.parsing.combinator.syntactical
使うときはScaladocで調べる。
普通は正規表現ベースの字句、構文解析を両方行うパーサで十分。
31.9 Error reporting
エラーメッセージをどう出すかは難しい。black art
パースに失敗した時に沢山の違った失敗が発生している。
選択|の全部の選択肢が失敗してる場合。
再帰的にパーサが定義されている場合。
最後にパースした部分のエラーを表示するルールにしている。
再帰の一番深い部分のエラーメッセージ。longest match
選択の場合は最後の選択肢のエラーメッセージ。
JSONパーサのエラーメッセージ
[1.13] failure: "false" expected but identifier John found
{ "name": John,
^
これはJSONのvalueパーサのの最後の選択肢が"false"だから。
def value: Parser[Any] =
obj | arr | stringLit | floatingPointNumber | "null" | "true" | "false"
エラーメッセージ出力用のパーサを最後に追加すれば改善出来る。
def value: Parser[Any] =
obj | arr | stringLit | floatingPointNumber | "null" |
"true" | "false" | failure("illegal start of value")
[1.13] failure: illegal start of value
{ "name": John,
^
最後にパースエラーになったエラーをlastFailureに保存している。
可変変数に上書きで保存しているので、最後のエラーが残る。
varなので関数プログラミング的ではない。
valに作り替える事も出来が大変。
31.10 Backtracking versus LL(1)
選択P|Qを使うときにバックトラッキングが発生する。
Pでいくつかのtokenを読んだ後に失敗した時、QにPと同じtokenを再度与える。
バックトラッキングする際に左再帰は使えない。
無限ループになるから。
左再帰を使わない様に文法を変換する。
バックトラッキングしない様に文法を書き換える事が出来る場合もある。
LL(1)文法はバックトラッキングを必要としない。
多くの言語がLL(1)になっている。
JSONや四則演算もLL(1)
バックトラッキングが必要ない場合は列挙演算子~の代わりに~!を使う。
バックトラッキングをしなければ、処理した入力を捨てても大丈夫。
解析も線形計算量で完了できる。
?? LL(1)文法については良く理解できない。何でbacktrackingが不要になる ??
31.11 Conclusion
scalaのパーサコンビネータを使う事で少ないコードで自由文脈文法を扱える。
scalaのライブラリなのでscalaとシームレスに組み合わせる事が出来る。
簡単に作れるのに加えて拡張性も高い。
専用ツール(yacc, bison)に比べて性能が悪いと言う欠点がある。
バックトラッキングが効率的ではないから。
バックトラッキングの繰り返しが指数関数的な計算量になる場合もある。
LL(1)文法にして~!演算子を使う事で回避できる。
入力の解析とパーサの構築を混ぜて行っているから。
これを改善するには別の実装にする必要がある。
全てのパーサをcase classにして木構造にする。
これを効率の良いパーステーブルに変換する。
標準的なパーサジェネレータのアルゴリズムを使って。
この変更をしても文法の定義は変更する必要がない。
パーサの構築を解析とは分けて行えるので、一回構築すれば繰り返し解析できる。
LALRのような高速のアルゴリズムを使う事も出来る。
高性能パーサはやれば作れて、作ったらscalaのライブラリに簡単に入れられる。
高性能パーサを作った後でも今のパーサを残す意味はある。
簡単で理解しやすい。
入力が小さいときは効率は問題にならない。
0 件のコメント:
コメントを投稿