ブロック処理を決定性有限オートマトン(DFA)化した Text-Creolize-0.003 - Tociyuki::Diary「練習で書いてみたText-Creolize-0.001 - Tociyuki::Diary」では、とりあえずブロックの構文を LL(1) で記述し、構文解析表を使って動かしていました。コードを作るにはてっとり早くて楽ができる反面、プッシュ・ダウン・オートマトンとしてスタックへ後続記号をいちいちプッシュしつつループを回す分が余計なオーバーヘッドになっていました。 ところで、この構文解析表を変形しているとき、この構文が正規文法であることに気がつきました。つまり、block、paragraph などが、有限オートマトンの状態に相当し、状態 A で記号 S を受理したとき必ず他の状態 B へ遷移し、再帰することなく最後まで遷移を繰り返していくだけで記号列を解釈することができます。変形した記号表は下のとおりです。しかも、常にすべての状態で記号に対して一意に遷移する先の状態が一つ決まっていますので、
