藻のブログ

日記,IT,学問(ジェンダー,人工知能など)について書かれることでしょう。

再帰とループの変換を習得した / 再帰下降構文解析を実装した

6月22日の日記。


この日は午後1時ころに起きた。あいかわらずひどいけど、昼間に寝るということはなかったので少しマシになった。


まず、前日からやっていた再帰下降構文解析に関連して、ループ再帰の変換(前提として、ループでも再帰でも表現力は変わらないことが知られている。)に興味があったので、再帰で実装されたクイックソートをループでの実装に変更するということをやっていた。

できた。

// 再帰版
var quick_sort_recursive = function(elements) {
    var quick = function(elements, left, right) {
        if (right - left > 1) {
            var middle = partition(elements, left, right);
            quick(elements, left, middle - 1);
            quick(elements, middle + 1, right);
        }
    };
    quick(elements, 0, elements.length - 1);
}


// ループ版
var quick_sort_loop = function(elements) {
    var stack = [];
    stack.push({left: 0, right: elements.length - 1});

    while (true) {
        if (stack.length > 0) {
            var context = stack.pop();
            if (context.right - context.left > 1) {
                var middle = partition(elements, context.left, context.right);
                stack.push({left: context.left, right: middle - 1});
                stack.push({left: middle + 1, right: context.right});
            }
        } else break;
    }
};

これらの2つの関数は、数値型からなるリストを渡して呼び出すことで、リストの要素をその場でソートする(ここでは、 partition 関数は省略している。)。

要するに、ループでは、再帰におけるコールスタックを自分で表現すれば良くて、それがわかればそこまでわかりにくくはない。

再帰とループでは構造は違うが、(ここで)表現しているプログラムは同じなので,(プログラム上の意味として)共通の要素が登場しているのだが、それぞれ別の形,別の場所で登場しているのが興味深い。

ループでは、再帰における引き数の渡しを、スタックで変数で表現している。スタックに追加されるのは、再帰における引き数のリストにあたるものだ。

ループでは、再帰における最初の呼び出しにあたることを、 stack の初期化直後に行なっている。実際、ここでは再帰の最初の呼び出しで渡している値と同じものをスタックに追加している。

while ループ内の最初の部分では、スタックに要素があればそれをポップしている。要素がポップされてから一回のループを終えることは、再帰で(ある)関数の呼び出しが終了することを表現している。

また、再帰版では、関数の再帰的な呼び出しを 2 回行なっている。これは、スタックに引き数の組を 2 回追加することで表現されている。

if (context.right - context.left > 1) という条件は、再帰についているかいないかの判断と同じである。この条件ブロックの直前にスタックをポップしているので、 if ブロックの中が実行されなければ、スタックはそのループにおいて減る。結果として、再帰において底につくことと同じことを意味している。

ループの最初の部分でスタックがないということは、再帰において最初の呼び出しが終わったことと同じである。再帰において最初の呼び出しが終わることを、 break で表現している。


前日に続き、再帰的下降構文解析の実装をやった。前日は、左再帰で苦しんだことで実装が途中になっていた。

まずは、やむをえず while ループで実装してみて、実際に構文解析を正しく行なうことができた。

f:id:ragion:20160623004157p:plain

そして、ループと再帰の変換の知識を生かし、 while ループではなく再帰を用いて実装しなおすことができた!

問題なのは、1つは、文法的に正しいトークン列が与えられたときに正しく抽象構文木を生成することはできるが、不正なトークン列が与えられたときになにが起きるかわかっていないこと(まあ、さすがに、なにごともなかったかのように(誤った)抽象構文木を生成するというようなことはないと思うけど……。)。

さらに、トークン列の解釈において文法的な不正が見いだされたときにどうするかということを考えなければならない。つまり、「予期されないトークンです: =」みたいなエラーを表現する仕組みを作らなければならないということだ。

そして、今回は文法規則に応じたメソッドを手書きで表現したけど、最終的には、文法規則さえ与えればそれに応じて自動的に構文解析を行なう、ということをできるようにしたい。まあ、それって、パーサジェネレータ(コンパイラコンパイラなんだけど……。


水曜日は「掲示板 / メーリングリスト サーバ構築」の日だが、なにもやってない。


魔法書認知療法の書籍『フィーリング Good ハンドブック』)を読むことになってたけど読んでない……。読まなければ……。

あしたは、失業手当のための一手を打とうと思う。