■
と思うようになったのは、昔DXFのパーサを書いたことがあって、正則言語でいけると思ったら、実はスタックが必要だったかスタックがあった方が楽にプログラミングできた、ということがあったからで。
んで、なんでスタックが必要か必要じゃないかわかんなくなってるのかしばらく考えたんだけど、例えば正則言語では
e = (e) | 1
みたいのは解析できないわけだが、これは括弧のネストの深さが有限じゃないからだということを思い出した。DXFの解析で、無限にネストする要素が出てきたかは覚えてないや。あれ、FSMで書けたのかなあ*1。
*1:とはいっても、VB6なのでLexer generatorとかあるわけでもないので、状態数の爆発の方が問題になるんだけど