とうとう1986年の本を引っ張り出してくることに

先日来、パターンの話をひきずっていて、そもそも正規表現(正則表現ということばはまだ使われているだろうか)ってどういうもんだったけというのを思い出すべくコンパイラ 情報処理シリーズ(7)まで引っ張り出してしまった。

コンパイラ 情報処理シリーズ(7)

コンパイラ 情報処理シリーズ(7)

この本を買った当時、本当はドラゴンブックを読みたかったが、これを読み終われなかったっけ(読み終わっても、高くて厚くて買う気がおきなかったかもだが)
で、この本のp.78あたりの正規表現の定義では、

  • (R)|(S) :or
  • (R)・(S) : concatenation
  • (R)* :repetition (再帰的定義)

が基本である。
で、正規表現を直接表現するのがNFA(non-deterministic finite automaton)である。
たとえば(a|b)*abb とかは、aaaaaa...とaが続くかぎり、どの状態に遷移するかが決定できない。
DFA(deterministic finite automaton)は、状態遷移が単なる(有限の)表引きであるから、実装が簡単だが、NFAはそうはいかない。では、どうするかというと、NFAをDFAに変換する部分集合構成法というアルゴリズムが紹介されている(コンパイラ 情報処理シリーズ(7)のp.84)
(Perlで書いてみた方もいらっしゃるようだ)
ところで、手持ちの詳説 正規表現 第2版(現在は詳説 正規表現 第3版)を読み返してみると、NFAとDFAの中身までは踏みこんでおらず、NFAを利用したエンジンはバックトラックする、という話になっていた。ふーん。

最近のコンパイラ事情

ところで、コンパイラ 情報処理シリーズ(7)は、1980年代の本だからしょうがないのかもしれないが、CPSやSSAという技法については何も書いてない(自分がみつけられないだけかもだが)。2006-10-03 -を読んで思い出したけれども、そういや、こんな文献を読んで(いや、プリントアウトして持って歩いて)いたっけ(←Pure imperative programming | Lambda the Ultimateより)
このあたりをまとめた本って、どれかな、調べる暇が欲しい。