editor(4)

開発

メモ

lexical analyzer generator作成

wコマンドの実装しようとして検討していたら必要という結論になった。必要な情報を教科書（ドラゴンブック）から拾い読み。

正規表現から構文木を作り、そこからDFAを生成。そしてそれを基に遷移テーブルを生成。
そんなに高機能なものは作る予定ないのだけれど、基本的なことはやるかな。DFAの状態数最小化、遷移テーブル圧縮は使用したときのテーブルサイズをみてやるかやらないか判断する予定。メガ単位になったらやる。

正規表現の構文木はシンプルに作成予定。適当な感じになりそう。

教科書にでてきたnullableとかfirstposとか読んでて、なんかいろいろな記憶がよみがえってきた。一番古いのは大学院のプログラミング言語の授業。工学部棟のちっこい会議室で授業やったなぁ。フロー解析（だっけ？）とか懐かしい。

nullable, firstpos, lastpos

  • nullable(n)
    • empty leaf -> 真
    • pos i leaf -> 偽
    • or node -> nullable(c1) or nullable(c2)
    • cat node -> nullable(c1) and nullable(c2)
    • star node -> 真
  • firstpos(n)
    • empty leaf -> 0
    • pos i leaf -> {i}
    • or node -> firstpos(c1) ∪ firstpos(c2)
    • cat node -> if (nullable(c1)) { firstpos(c1) ∪ firstpos(c2) } else { firstpos(c1) }
    • star node -> firstpos(c1)

lastposはfirstposでのc1, c2を入れ替える。

followpos

  1. cat nodeの場合、lastpos(c1)に含まれるすべての位置 i について、firstpos(c2)に含まれるすべての位置はfollowpos(i)に含まれる。
  2. star nodeの場合、lastpos(n)に含まれる位置 i としたとき、firstpos(n)に含まれるすべての位置はfollowpos(i)に含まれる。

用語の詳細な解説がないからわかりにくいな。