TOML の文字列スキャナの BASE、SHIFT 配列ジェネレータ

昨日の文字列スキャナの BASE, SHIFT の配列を作るときに使ったジェネレータです。 shift_occupied 関数は、 shift 配列のずらし位置が占有済みなら真を返します。 これを使って pack_table 関数で、 table 表の各桁を横にずらして、 shift 配列の空き位置にはめ込めるかどうかを調べます。 はめ込めるずらし幅が求まったら、 base 配列にオフセットを書き込み、 shift 配列を埋めます。

//@<generate-base-shift.cpp@>=
#include <vector>

void pack_table (std::vector<std::vector<int> > const& table, std::vector<int>& base, std::vector<int>& shift);

static inline bool
shift_occupied (std::vector<int> const& shift, int const start, std::vector<int> const& codes)
{
    for (int c : codes) {
        int j = start + c - codes[0];
        if (j < shift.size () && shift[j] > 0)
            return true;
    }
    return false;
}

void
pack_table (std::vector<std::vector<int> > const& table, std::vector<int>& base, std::vector<int>& shift)
{
    base.resize (table.size (), 0);
    shift.push_back (0);
    for (std::size_t state = 1; state < table.size (); ++state) {
        std::vector<int> codes;
        for (std::size_t i = 0; i < table[state].size (); ++i)
            if ((table[state][i] >> 8) > 0)
                codes.push_back (static_cast<int> (i));
        for (int start = 1; true; ++start)
            if (! shift_occupied (shift, start, codes)) {
                base[state] = start - codes[0];
                break;
            }
        if (base[state] + codes.back () >= shift.size ())
            shift.resize (base[state] + codes.back () + 1, 0);
        for (int c : codes)
            shift[base[state] + c] = table[state][c];
    }
}

遷移表には、 SHIFT と同じ形式でビットパックした項目を並べます。 16 進数 5 桁で、 上位 1 桁がアクション番号、 中間 2 桁が遷移先状態番号、 下 2 桁が遷移元状態番号です。 SHIFT へ圧縮する都合で、 MATCH をゼロ以上の桁に置きたいので、 どこでも良いのですが最後の桁に書いておきます。

//@<圧縮前の遷移表@>=
std::vector<std::vector<int> > TABLE { // (0xATTSS) SS: cls TT {action A}
//          UF0      UE0      UC0      U80      U00      HEX      [U]      [u]    [\t ]     [\\]      [']      ["]     [\n]    MATCH
    {0,       0,       0,       0,       0,       0,       0,       0,       0,       0,       0,       0,       0,       0,       0},
    {0,       0,       0,       0,       0,       0,       0,       0,       0,       0,       0, 0x02401, 0x00201,       0,       0},
    {0, 0x10902, 0x10a02, 0x10b02,       0, 0x30c02, 0x30c02, 0x30c02, 0x30c02, 0x30c02, 0x00d02, 0x30c02, 0x00302,       0,       0},
    {0,       0,       0,       0,       0,       0,       0,       0,       0,       0,       0,       0, 0x00403,       0, 0x00103},
    {0, 0x11604, 0x11704, 0x11804,       0, 0x31904, 0x31904, 0x31904, 0x31904, 0x31904, 0x01a04, 0x31904, 0x30504, 0x01904,       0},
    {0, 0x11605, 0x11705, 0x11805,       0, 0x31905, 0x31905, 0x31905, 0x31905, 0x31905, 0x01a05, 0x31905, 0x30605, 0x31905,       0},
    {0, 0x11606, 0x11706, 0x11806,       0, 0x31906, 0x31906, 0x31906, 0x31906, 0x31906, 0x01a06, 0x31906, 0x40706, 0x31906,       0},
    {0,       0,       0,       0,       0,       0,       0,       0,       0,       0,       0,       0,       0,       0, 0x00107},
    {0,       0,       0,       0,       0,       0,       0,       0,       0,       0,       0,       0,       0,       0, 0x00208},
    {0,       0,       0,       0, 0x10a09,       0,       0,       0,       0,       0,       0,       0,       0,       0,       0},
    {0,       0,       0,       0, 0x10b0a,       0,       0,       0,       0,       0,       0,       0,       0,       0,       0},
    {0,       0,       0,       0, 0x20c0b,       0,       0,       0,       0,       0,       0,       0,       0,       0,       0},
    {0, 0x1090c, 0x10a0c, 0x10b0c,       0, 0x30c0c, 0x30c0c, 0x30c0c, 0x30c0c, 0x30c0c, 0x00d0c, 0x30c0c, 0x0080c,       0,       0},
    {0,       0,       0,       0,       0, 0x50c0d, 0x50c0d, 0x00e0d, 0x0120d, 0x50c0d, 0x50c0d, 0x50c0d, 0x50c0d,       0,       0},
    {0,       0,       0,       0,       0,       0, 0x60f0e,       0,       0,       0,       0,       0,       0,       0,       0},
    {0,       0,       0,       0,       0,       0, 0x6100f,       0,       0,       0,       0,       0,       0,       0,       0},
    {0,       0,       0,       0,       0,       0, 0x61110,       0,       0,       0,       0,       0,       0,       0,       0},
    {0,       0,       0,       0,       0,       0, 0x61211,       0,       0,       0,       0,       0,       0,       0,       0},
    {0,       0,       0,       0,       0,       0, 0x61312,       0,       0,       0,       0,       0,       0,       0,       0},
    {0,       0,       0,       0,       0,       0, 0x61413,       0,       0,       0,       0,       0,       0,       0,       0},
    {0,       0,       0,       0,       0,       0, 0x61514,       0,       0,       0,       0,       0,       0,       0,       0},
    {0,       0,       0,       0,       0,       0, 0x70c15,       0,       0,       0,       0,       0,       0,       0,       0},
    {0,       0,       0,       0, 0x11716,       0,       0,       0,       0,       0,       0,       0,       0,       0,       0},
    {0,       0,       0,       0, 0x11817,       0,       0,       0,       0,       0,       0,       0,       0,       0,       0},
    {0,       0,       0,       0, 0x21918,       0,       0,       0,       0,       0,       0,       0,       0,       0,       0},
    {0, 0x11619, 0x11719, 0x11819,       0, 0x31919, 0x31919, 0x31919, 0x31919, 0x31919, 0x01a19, 0x31919, 0x30519, 0x31919,       0},
    {0,       0,       0,       0,       0, 0x5191a, 0x5191a, 0x01b1a, 0x01f1a, 0x5191a, 0x5191a, 0x5191a, 0x5191a, 0x0231a,       0},
    {0,       0,       0,       0,       0,       0, 0x61c1b,       0,       0,       0,       0,       0,       0,       0,       0},
    {0,       0,       0,       0,       0,       0, 0x61d1c,       0,       0,       0,       0,       0,       0,       0,       0},
    {0,       0,       0,       0,       0,       0, 0x61e1d,       0,       0,       0,       0,       0,       0,       0,       0},
    {0,       0,       0,       0,       0,       0, 0x61f1e,       0,       0,       0,       0,       0,       0,       0,       0},
    {0,       0,       0,       0,       0,       0, 0x6201f,       0,       0,       0,       0,       0,       0,       0,       0},
    {0,       0,       0,       0,       0,       0, 0x62120,       0,       0,       0,       0,       0,       0,       0,       0},
    {0,       0,       0,       0,       0,       0, 0x62221,       0,       0,       0,       0,       0,       0,       0,       0},
    {0,       0,       0,       0,       0,       0, 0x71922,       0,       0,       0,       0,       0,       0,       0,       0},
    {0, 0x11623, 0x11723, 0x11823,       0, 0x31923, 0x31923, 0x31923, 0x31923, 0x02323, 0x01a23, 0x31923, 0x30523, 0x02323,       0},
    {0, 0x12924, 0x12a24, 0x12b24,       0, 0x32c24, 0x32c24, 0x32c24, 0x32c24, 0x32c24, 0x32c24, 0x02524, 0x32c24,       0,       0},
    {0,       0,       0,       0,       0,       0,       0,       0,       0,       0,       0, 0x02625,       0,       0, 0x00125},
    {0, 0x12d26, 0x12e26, 0x12f26,       0, 0x33026, 0x33026, 0x33026, 0x33026, 0x33026, 0x33026, 0x32726, 0x33026, 0x03026,       0},
    {0, 0x12d27, 0x12e27, 0x12f27,       0, 0x33027, 0x33027, 0x33027, 0x33027, 0x33027, 0x33027, 0x32827, 0x33027, 0x33027,       0},
    {0, 0x12d28, 0x12e28, 0x12f28,       0, 0x33028, 0x33028, 0x33028, 0x33028, 0x33028, 0x33028, 0x40728, 0x33028, 0x33028,       0},
    {0,       0,       0,       0, 0x12a29,       0,       0,       0,       0,       0,       0,       0,       0,       0,       0},
    {0,       0,       0,       0, 0x12b2a,       0,       0,       0,       0,       0,       0,       0,       0,       0,       0},
    {0,       0,       0,       0, 0x22c2b,       0,       0,       0,       0,       0,       0,       0,       0,       0,       0},
    {0, 0x1292c, 0x12a2c, 0x12b2c,       0, 0x32c2c, 0x32c2c, 0x32c2c, 0x32c2c, 0x32c2c, 0x32c2c, 0x0072c, 0x32c2c,       0,       0},
    {0,       0,       0,       0, 0x12e2d,       0,       0,       0,       0,       0,       0,       0,       0,       0,       0},
    {0,       0,       0,       0, 0x12f2e,       0,       0,       0,       0,       0,       0,       0,       0,       0,       0},
    {0,       0,       0,       0, 0x2302f,       0,       0,       0,       0,       0,       0,       0,       0,       0,       0},
    {0, 0x12d30, 0x12e30, 0x12f30,       0, 0x33030, 0x33030, 0x33030, 0x33030, 0x33030, 0x33030, 0x32730, 0x33030, 0x33030,       0},
};