masquerade0324のブログ

とある大学院生のメモ書き

SMLでML-Lexを使わずにlexerを書こう!

こんにちは、この記事はML Advent Calendar 2014 6日目の記事です。

いまどきどんな言語でも、字句解析器(lexser)と構文解析器(parser)を生成するためのツール(それぞれlexとyaccに準ずるもの)が提供されている場合が多いです。

Standard MLの各処理系でも、ML-LexとML-Yaccというツール(名前は各処理系によって違います)が提供されている場合が多いです。これらのツールを使えば、簡単に字句解析器と構文解析器を生成することができます(とは言っても、SMLの場合は日本語の記事が少ないのは間違いありません)。

もちろんこれらのツールを使えばよいのですが、SMLならツールを使わないでも比較的簡単にlexerとparserを書くことができます。

今回の記事では、ラムダ計算のためのlexerを書いていこうと思います。なお、この記事では愚直にコードを書いていて、処理効率などは一切考えていません。処理効率などを考えて改良しました!みたいな記事を誰かが書いてくださればうれしいです。

まずは、字句解析での最小単位となるトークンの定義をします。SMLなら代数的データ型を使って簡単に定義できます。

datatype token =
         ID of string
       | LAMBDA (* \ *)
       | LPAREN (* ( *)
       | RPAREN (* ) *)
       | DOT    (* . *)
       | SOMETHING of char
       | EOF

次に、空白文字をとばす処理をする関数skipSpacesを定義します。この関数は、入力ストリームを受け取り、空白文字でない文字にあたるまで入力(空白文字)を捨てます。

(* skipSpaces : TextIO.instream -> unit *)
fun skipSpaces inst =
    case TextIO.lookahead inst of 
        SOME c => if Char.isSpace c
                  then (TextIO.input1 inst; skipSpaces inst)
                  else ()
      | _      => ()

入力ストリームを1文字先読みして、その結果をパターンマッチで取り出して処理しています。ある文字が空白文字かどうかは、CharストラクチャのisSpace関数を使えば簡単です。

次に、先頭が英字とわかっている入力ストリームから識別子を読み出す関数readIDを定義します。識別子は、英字から始まり、英数字が0個以上続く列とします。

(* readId : TextIO.instream -> token *)
fun readId inst =
    let
        fun readId' str =
            case TextIO.lookahead inst of
                SOME c => if Char.isAlphaNum c
                          then readId' (str ^ TextIO.inputN (inst, 1))
                          else str
              | _      => str
    in
        ID (readId' "")
    end

実際の処理は、内部のreadId'関数で行っています。この関数は、識別子(の文字列)strを受け取り、入力ストリームを1文字先読みして英数字ならstrに連結し、そうでないならstrをそのまま返しています。

ここまでこれは、あとは字句解析を行うlex関数を定義するだけです(はやい!すごい!簡単!)。lex関数は、入力ストリームを受け取り、トークンを切り出す関数です。

fun lex inst =
    (skipSpaces inst;
     if TextIO.endOfStream inst then EOF
     else 
         let
             val c = valOf (TextIO.lookahead inst)
         in
             if Char.isAlpha c then readId inst
             else case valOf (TextIO.input1 inst) of
                     #"\\" => LAMBDA
                   | #"("  => LPAREN
                   | #")"  => RPAREN
                   | #"."  => DOT
                   | _     => SOMETHING c
         end)

これまでに書いてきた関数を組み合わせて、パターンマッチをしているだけです。

まず、入力ストリームから空白文字を捨て、ストリームの末尾に達していたらEOFトークンを返します。そうでない場合は1文字読みます(valOfを使っていて危険に見えますが、lookahead関数はストリームがEOFのときにNONEを返すので、今回は必ずSOMEを返し、valOfは失敗しません)。

先読み文字が英字の場合は識別子のため、readId関数を使います。そうでない場合は、1文字読み込んで、バックスラッシュならLAMBDA、左カッコならLPAREN、右カッコならRPAREN、ドットならDOT、それ以外の何かある文字ならSOMETHINGを返します。

これだけで、字句解析器が作れます。

試しに、

(\x.x y)(\x1.x1 x1)

という文字からなるファイルterm.txtを読み込んでみましょう。

そして、lexを何回も読みだせば、確かにトークンが読み出されていると思います。

これだけで簡単にlexerを書くことができます。みなさんもlexツールを使わずに書いてみてはどうですか?

明日は日本人で一番SMLのブログ記事を書いてるんじゃないかというeldeshさんです!

(この記事はML Advent Calendar 2014 6日目の記事です。)