オレオレ字句解析器つくりました

Aizu Advent Calendar 2016(ADVENTAR版) 7日目です。

www.adventar.org

6日目がid:unamune, 8日目もid:upamune(!!!)です。

おつかれさまです。

はじめに

強い人は見ないで

もの

リポジトリはこちらです↓

github.com

はじめはScalaDSLの記事を書こうと思って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
  • たのしかったです(こなみ)