【D言語?】ctpgの実装について【ctpg】

D言語erの皆さん、こんにちは。今回は、D言語で書かれたパーサジェネレータである、ctpgの実装についてちょっと話していきます。

内部で使っているアルゴリズム

ctpgはパーサジェネレータなので、規則に従ってパーサを生成することができます。生成されたパーサは、後戻り構文解析というアルゴリズムを使って構文解析を行います。この後戻り構文解析、トップダウンな構文解析なのですが、LL(1)やLL(k)と違って、とても遅いです。

後戻り構文解析とは

後戻り構文解析とは、LL法と違い、字句を先読みせず、規則が失敗したら戻って別の規則を試すというアルゴリズムです。


import std.stdio;

bool hoge_piyo(string input){ // "hoge" または "piyo" にマッチする規則
    if(hoge(input){
        return true; // hogeが成功したらhoge_piyoも成功
    }else if(piyo(input)){
        return true; // hogeが失敗したら、別の規則であるpiyoを試し、piyoが成功したらhoge_piyoも成功
    }else{
        return false; // hogeもpiyoも失敗したら、hoge_piyoも失敗
    }
}

bool hoge(string input){
    return input.length >= 4 && input[0..4] == "hoge";
}

bool piyo(string input){
    return input.length >= 4 && input[0..4] == "piyo";
}

void main(){
    hoge_piyo("hoge").writeln(); // true
    hoge_piyo("piyo").writeln(); // true
    hoge_piyo("fuga").writeln(): // false
}

しかし遅い

LL(k)のように、先読み集合を予め計算して、それに基づいて規則を分けるという事をしないので、そのぶんLL(k)よりは遅くなります。そこは仕方ないとして、それでも、遅くなる要因があります。それは、同じ入力位置で同じ規則が複数回呼ばれる可能性があることです。しかし、実際に規則を試してみて、ダメだったら戻るというアルゴリズムの性質上、仕方ない様にも見えます。

そこでメモ化ですよ

規則ごとに、入力の位置で結果をメモしておけば、無駄をなくせます。 D言語には、連想配列が言語仕様に含まれているので、簡単に実装できます。


bool hoge_piyo(string input){
    static bool[string] memo;
    if(input in memo){
        return memo[input];
    }else{
        〜〜〜〜
    }
}

実は、この後戻り構文解析にメモ化を追加したアルゴリズムには名前がついていて、 Packrat Parsingと言います。 ctpgは、メモ化された後戻り構文解析、つまりPackrat Parsingを構文解析のアルゴリズムとして使っています。

まとめ

ctpgは内部でPackrat Parsingを使っているよという話でした。現状では規則単位でメモ化していますが、これの粒度を荒くしたり、細かくしたりすれば、速度やメモリの消費量などが変わってくると考えられます。そのへんの最適化、とても面白そうですね。

担当：美馬（parsingは、パーシングよりパージングと発音した方が格好いい事に気づいた）