オートマトン

Programming language

S式のパーザを作っている。学生時代に習ったような気がする微かなオートマトンの記憶を元に字句解析は作ってみた。言語処理系の作成は古典的な話題なので、定石と言われる方法がある。自分のやり方でやるよりも、きっと定石に従った方が良いんじゃないだろうか。
さて、字句として

  • カッコ
  • コッカ
  • 整数（負数は除く）
  • 文字列（エスケープシーケンスはなし）
  • シンボル（数値で始まらなければ何でもOK）

を許すとすれば、

という状態遷移図を書ける。初期状態と受理状態はともにNeutral。WSはホワイトスペース、|はまたは、EOSはソースコーソの終わり（End Of Source code）、*は任意の文字、εは空文字。
この字句解析器で、例えば

(let ((n 42))
  (+ n 1))

というソースコードを読んで、

  • LeftParen
  • Identifier:let
  • LeftParen
  • LeftParen
  • Identifier:n
  • Integer:42
  • RightParen
  • RightParen
  • LeftParen
  • Identifier:+
  • Identifier:n
  • Integer:1
  • RightParen
  • RightParen

っていう字句の列を得たとする。この字句の列からコンスセルを作成するためのオートマトンは、字句解析のときのオートマトンとは何かが違うようだ。リストが再帰的な構造だからだろうか、字句解析のときの要領で状態遷移図を書けないんだよなー。
大学で勉強したこといろいろ忘れてる。オートマトンとコンパイラの教科書を引っ張りだして読んでみようかな。学生時代は言語処理系の講義なんてクソつまらなかったけど、なんで今頃になって興味が出てくるんだろう。