バイナリツリーの再帰下降バリデータ
自分の作っている言語は単に構文木を扱うだけって落ち込んだりしてました。
更にいうと、バイナリツリーを扱うだけの言語です。
LISPはConsセルを使ったリストを扱うだけの言語です。
名前付きセルを使ったバイナリツリーを扱うだけの言語を自分は作っているわけです。
名前は場合によって、演算子、型、メッセージ等と捕らえることが出来そうです。
そう考えたら、なんか自信が湧いてきました。
XMLのバリデータは一度2分木にしてからバリデーションするようなことをしていました。
しかし、Compactは最初から2分木です。2分木に変換する手間は省けます。
で、2分木であれば、LISPのように、再帰的にグルグルと回って、処理が楽なはずです。
でも、名前が付いてるのでチェックは必要です。
それはメンドクサイから、そのチェックを楽にする構文が欲しくなる気がします。
構文じゃなくて、関数で十分かなぁ?
これから、しばらく、バイナリツリーの性質をもっと調べていってみようと思います。
明日は仙台に行くので、ビューティフルコードの本、探してみます。売ってるといいなぁ。
<script> Array.prototype.toString=function(){return "["+this.join(",")+"]"} // 2分木の再帰下降バリデータ。 function valid(data) { return statement(data); } function statement(data) { if(data instanceof Array) switch (data[1]) { case "if": return v02(data, exp, elsef); case "C": return v02(data, valid, valid); default: return exp(data); } return exp(data); } function v02(data,f1,f2) { return f1(data[0]) && f2(data[2]); } function elsef(data) { if (data instanceof Array && data[1] == "else") return exp01(data); else return exp(data); } function exp01(data) { return v02(data,exp,exp); } function id(data) { if(data instanceof Array) return false; return true; } function assignLeft(data) { if(data instanceof Array) return arr(data); return id(data); } function arr(data) { if(data instanceof Array) { switch(data[1]){ case "[]": return v02(data, assignLeft, exp); } } return false; } function exp(data) { if (data instanceof Array) { switch (data[1]) { case "=": return v02(data, assignLeft, exp); case "+": case "*": return exp01(data); default: return false; } } else { return true; } } function p(d) { document.write("<b>"+d+"</b><br/>"); } function test(data) { var f = valid(data); if(!f) document.write("error "+data+"<br>"); } test([1,"+", [2, "*", 3]]); test([1,"*", [2, "+", 3]]); test([1,"if", [2, "else", 3]]); test([1,"if", [2, "els", 3]]); test([1,"if", [2, "else", [3,"else",4] ]]); test([1,"if", 3]); test([1,"C",[1,"if", 3]]); test([1,"else",2]); test(["a","=",2]); test([["a","=","b"],"=",2]); test(["a","=",["b","=",2]]); test([["a","[]",2],"=",2]); test([["a","[]",["a","=","b"]],"=",2]); </script>