Mongrel2のコードリーディング……、と関係なく正規文法についてメモ

c algorithm

Mongrel2のコードを眺めていてRagelという有限オートマトンを一般的なプログラミング言語にコンパイルするツールのことが気になった。Ragelのユーザーガイドの冒頭に、rationale的なことが書いてある。それとか、Wikipediaで読み漁ったところを勉強メモとしてまとめておこう。嘘も一杯書いてあるかも。

  • 言語学やコンピュータサイエンスでは「言語」が数理的に定義され、解析されている
  • 解析対象となるのは型式言語と呼ばれ、それは「アルファベット」（Σ）と呼ぶ任意の文字の集合によって作られる「ワード/シンボル/トークン」の並びからなる集合
  • で、このとき、有限個、無限個の生成ルールによって定義される形式言語はチョムスキー階層と呼ばれる、いくつかのクラスに分類される
  • それぞれのクラスに属する形式言語をパースできる最低限のオートマトンというのがある
  • 一番大きいクラスはType-0で、Unrestricted、つまり終端記号、非終端記号の並びについて制約がなく、もっとも自由な文法。これを扱えるオートマトンはチューリングマシン
  • 終端記号、非終端記号（terminal symbols/nonterminal symbols）というのは、、、、あれ、わからん。非終端記号というのは終端記号と違って、文法的な作用素のようなもので、制約ルールや文法の生成ルールを記述するためのもので、最終的な文には現れないもの、という理解でいいのかしら。うーん。
  • 次に大きいのはType-1の文脈依存文法（Context-sensitive grammar）。Wikipediaにある形式的な定義は、「αAβ → αγβ」。うーん。文脈依存文法は、プログラミング言語などの人工言語が相当する
  • Type-2の文脈自由文法（Context-free grammar）は、生成ルールが「V → w」で、任意の非終端記号から、前後の文脈に依存せずに、終端文字と非終端記号から構成される文字列が生成される、ということか。
  • Type-3は正規文法。ここがRagelのような有限ステートマシン、決定性有限オートマトン（DFA）で扱えるもの。正規表現も、この範疇。Type-3の正規文法は必ず対応するDFAが存在する、というか等価なのかしら
  • で、Ragelは正規表現をリテラルで書くのとどう違うかというと、正規表現というのはつまるところ有限オートマトンの状態遷移を表現したものだけど、一般的なプログラミング言語の中では、そのエンジンはブラックボックスで、受理されるかどうかだけが見える。Ragelは正規表現中の任意の状態に対して任意のコードを埋め込める。抽象度の高い正規表現を使ってステートマシンを書くことで、それが通常の言語にコンパイルされる。
  • Ragelは状態遷移のための記法を持っている、一種のDSL。一般にパーサは手で書くのが困難だからRagelのようなツールがある
  • Sed、Awk、Perlなんかで正規表現リテラルを使うことの難点は、正規表現と一般コードをスイッチしながらロジックを書き下さないといけないことで、Ragelを使えば、その両方をスッキリ記述できる
  • 正規表現の「*」は、Kleene StarとかKleene Closure（クリーネ閉包）という、集合の言葉を使った定義が与えられている演算子だった！ と、正規表現のよって立つ理論的背景を少し知って、かすかな知的興奮を覚えた
  • そうか、非終端記号って正規表現でいえば、つまり*とか[とか{とか全部だな。で、正規文法の理論上は正規表現の範囲ではないけれども、非終端記号に引数を持たせた拡張正規表現というのが世にあるegrepとかeというやつか？
  • POSIXの世界ではIEEE 1003.2dあたりで正規表現と拡張正規表現が定義されている
  • Perl由来のPCREと拡張正規表現の関係がよく分からない。拡張正規表現は、正規文法超える範囲のプラクティカルな個々の実装の総称かしら。
  • あれ、正規表現の後方参照って……、と思ったらやっぱり正規文法の範囲を超えた一種の拡張らしい
  • スキャナ生成という点でRagelとLexと比較すると、処理のモデルがまず異なる。Lexは文字列を最後まで読み込むので、そもそもバッファリングが必要だし、前方から最長一致でトークンを切り出して消費する。Ragelはトークンを構成する文字単位で処理をエンベッドできるので自由度が高い。Lexは長期に証明された有用なソフトウェアではるものの、LexよりもRagelが向く場合もあるんだよ
  • RubyにはRaccというパーサジェネレータがあり、これはLALRパーサと呼ばれる種類のもの。LALRは「Look ahead LR」のことで、LRは左から右にということ。右だろうと左だろうとどっちでもいいんだろうけど、まあ左から一方向ということか。で、LALRってなんだろうか……
  • JSONのパースぐらいなら、Ruby標準のstrscanでも簡単に書ける

文字列のパースというジャンルは、コンピュータサイエンス的に結構大きな世界であることが漠然と分かった。

Mongrel2を読んでみようと思ったけど全体像からすると数％でスタックしている印象。この調子で深さ優先探索的に関連事項を調べだすと、全体像が分かるまでに1年ぐらいかかるんじゃないだろうか。