寝る前にメモ。
PEG の欠点として左再帰が出来無い点があるけど、それってどういう事だろう。右と左ってそんなに大きな違いがあるのか?と考え出すと止まらなくなって、でも何となく自分なりに思いついたこと。
- 1 + 2 + 3 + 4 + 5 + 6 + 7
多分みんな左から右に目を動かしたはずだ。これが右再帰(嘘)。次は左再帰を混ぜた例。
- 10000000000 + 2000 + 3000000000 + 400 + 5000000000
もしこれを口に出して読もうとしたら、途中で目を右から左に動かして、一、十、百、千、と桁を数えたはずだ。ここが左再帰。
つまり、数字というのは右から左に桁を数えていかないと意味が確定しない構造になっている。ただ、意味の事を考えないで、ただ数字である事を知りたいだけなら右再帰でもいける。
ここで本質的なポイントは。
まとまらないけど、ばらばら続けます。数字を読み込む Haskell プログラムを書いてみました。
digitValue c = fromEnum c - fromEnum '0' str2int xs = str2int' 0 xs str2int' n "" = n str2int' n (x:xs) = str2int' (n * 10 + digitValue x) xs
これって、リストを逆にするプログラムと似ている!
myreverse xs = myreverse' [] xs myreverse' y [] = y myreverse' y (x:xs) = myreverse' (x:y) xs
という事で、数字を読むためには絶対リストを逆にしないといけないのではという発想が浮かんだのです。これだけ読んでもわけわからんと思うのでまた今度ちゃんと書きます。
追記
朝起きると、目を動かす方向で右再帰か左再帰か見るのはうまい考えのようで全然違うと分かった。
こういう事を考え出した動機を書いておくと、まず右再帰しか使えない PEG で数字をパースするだけのプログラムが結構難しいと分かった事。数字かどうか調べるだけなら Number+ で充分だけど、実際に桁を考えて数字を組み立てる作業でプログラム内にリバースを書かないといけない。一方で、右再帰しか行わないという PEG の戦略はかなりまっとうだと思う。左再帰も出来るようにしてやろうというエンジニアリング的努力も面白いけど、右再帰の追求の方に美的興味を感じる。
さて、これだけわけの分からない事を書いてるのも自分で分かっていないからで、それでも書いてるのは上の str2int の例にあるような、媒介変数を使ってデータを構築するという作業が、ただのプログラム技術以上の意味がある予感がしたから。もしも媒介変数を使う事が出来なかったら左再帰の解析は不可能で、だとすれば、(世界は状態のリストだと考えられるので)世界の意味は世界が終わるまで分からない事になってしまう。