オレオレ字句解析器つくりました
Aizu Advent Calendar 2016(ADVENTAR版) 7日目です。
6日目がid:unamune, 8日目もid:upamune(!!!)です。
おつかれさまです。
はじめに
強い人は見ないで
もの
リポジトリはこちらです↓
はじめはScalaのDSLの記事を書こうと思ってDSLで書ける簡易的なパーサを書こうと思ったのですが、DSLの部分よりそれ以外のところが重くなったのでもうDSLの記事じゃなくていいか、と色々考えて字句解析器になりました。
Rustじゃなくてすみません。
なかみ
本体はここです↓
https://github.com/misoton665/simp/blob/master/src/main/scala/org/misoton/Lexer.scala
トークンと解析後のトークンツリーをつくって、LexerをInput => Outputな関数として関数合成で作れるようにしました。 パーサコンビネータはあるけどレクサーコンビネータと言えるのか...?
文字列と正規表現を暗黙的型変換でLexerに変換できます。
"hogehogepun" ← "hogehogepun"をトークンとして解析するLexer "([a-z]+)".r ← aからzで構成される1文字以上の文字列をトークンとして解析するLexer
演算子はこんな感じです。
"a" ~ "b" ← "ab"をそれぞれ別のトークンとして解析するLexer "a" / "b" ← "a"または"b"をトークンとして解析するLexer "a" ~ "b" <| ← "a"と"b"を持つトークンを子ノードとする親ノードとして解析するLexer
実はn文字先読みできます。
lookAhead(hoge) ← hogeで解析したものはなかったことに(先読み) hidden(hoge) ← hogeで解析した結果を消す(読み進めるだけ) $ ← 入力文字列の終端のみで成功
Main.scalaで、元の定義を遵守したPPAPと広義のPPAPの解析を行ってるので、見てみてください。
DSL
このDSLの仕組みは簡単です。Scalaは略記が色んなところでできるのでそれを利用しています。
// これは↓ a.hoge(b) // こう書ける↓ a hoge b
上で書きましたが、暗黙的型変換で文字列や正規表現をLexerに変換しているので、いちいち変換のための関数を呼ばなくてよくなります。
// 文字列からLexerの生成 implicit def string2lexer(str: String): Lexer = { lexerGen((input) => { val (inputStr, nodes) = input if (inputStr startsWith str) Right((inputStr substring str.length, nodes :+ TokenTreeNode[ConstToken](ConstToken(str), Nil))) else Left("\"" + inputStr + "\" cannot match with \"" + str + "\"") }) } // 正規表現からLexerの生成 implicit def regex2lexer(regex: Regex): Lexer = lexerGen{ (input) => val splitRegex: Regex = (regex.toString + """(.*)""").r val (inputStr, nodes) = input inputStr match { case splitRegex(str, left) => Right((left, nodes :+ TokenTreeNode[IDToken](IDToken(str), Nil))) case _ => Left("\"" + inputStr + "\" cannot match with \"" + regex.regex + "\"") } }
細々したものはここでやってるので、演算子とかは簡潔に書けます。
// Lexerの連結 def ~(that: Lexer): Lexer = lexerGen { (input) => this (input) match { case Right(output) => that(output) case err@Left(_) => err } }
ここで使ってるlexerGenもScalaの略記(というか糖衣構文?)で使ってます。元の定義は普通の関数です。
// 関数からLexerの生成 def lexerGen(f: Input => Output): Lexer = new Lexer { override def apply(input: Input): Output = f(input) }
// これは↓ a.hoge( b ) // こう書ける↓ a.hoge{ b }
おわりに
- 実用性があまりなくてつらい。字句解析と構文解析を一気にやる方法があるので、そうすればマシになりそう。
- 再帰的な定義ができなくてつらい。つらい。
- これを使いましょう: github.com
- たのしかったです(こなみ)