Wirth の表制御型構文解析法

N. Wirth 著 ALGORITHMS+DATA STRUCTURES=PROGRAMS (1976) の表制御型下向き構文解析プログラムを少しアレンジして仮想マシンにしてみました。 なお、 現在の版では、 この方式の説明は大幅に省略されているものの、 さわりを知ることができます。

https://www.inf.ethz.ch/personal/wirth/ compiler construction 4.2 Table driven Top-down Parsing

オリジナルの表形式では TERMINAL と NONTERMINAL の 2 種の命令の有向グラフへ EBNF から直訳して、 それを構文解析器で動かしていました。 Wirth 教授による Oberon 版から、 C++11 へ翻訳するとこんな感じになるのでしょう。 ただし、 いくつか翻訳にあたって修正しています。 非終端記号で別にエントリ・テーブルを設けて間接参照していたのを、 直接参照に変更しました。 また、 空記号は TERMINAL の特殊な symbol 値で表していたのを、 EMPTY 命令へ分離しました。

enum opcode_type { TERMINAL, NONTERMINAL, EMPTY };

struct node_type {
    opcode_type opcode;
    union {
        int symbol;         // TERMINAL    == opcode
        node_type* entry;   // NONTERMINAL == opcode
    };
    node_type* suc;
    node_type* alt;
};

bool
parse_loop (node_type* node, std::istream& input, bool matched)
{
    if (nullptr == node) {
        return matched;
    }
    else if (TERMINAL == node->opcode) {
        matched = (input.peek () == node->symbol);
        if (matched)
            input.get ();
        node = (matched) ? node->suc : node->alt;
        return parse_loop (node, input, matched);
    }
    else if (NONTERMINAL == node->opcode) {
        matched = parse_loop (node->entry, input, matched);
        node = (matched) ? node->suc : node->alt;
        return parse_loop (node, input, matched);        
    }
    else if (EMPTY == node->opcode) {
        matched = true;
        return parse_loop (node->suc, input, matched);
    }
    return false;
}

これの特徴は、 suc と alt のポインタで辿れる相手がある限り、 実行を続けることにあります。 成功時に suc、 失敗時は alt を辿ります。 失敗時にもポインタを辿ることによって、 構文の分岐と繰り返しを扱うわけです。 そのままではループを脱出したときに失敗状況のままなので、 alt につないでおいた EMPTY 命令で成功状況へ昇格させます。 分岐も同様に EMPTY で成功へと昇格させます。

Wirth 教授が同著で認めているとおり、 この解析器では非終端記号の FIRST 集合と空規則の FOLLOW 集合の先読みに対応しておらず、 そのままでは LL(1) 文法のサブセットしか扱えません。 この問題は、 TERMINAL 命令の変種としてスキャンポインタを進めない LOOKAHEAD 命令を追加するだけで解決します。

さて、 ここで、 union やポインタではソースコード中に初期化リストを書き込むのに向かないので、 仮想マシン・コードに降格します。 ついでに、 Yacc の波括弧のように合成属性を記述できるように YIELD 命令を追加します。 さらについでに、 合成属性の記述を楽にする目的で、 入力ストリームではなく string を直接解析するように変更します。 そうして、 必要な継続が一種類だけなのを良いことに、 再帰呼び出しをループに書き換えてしまいます。

template<class U>
bool
parse_loop (std::vector<unsigned long> const& yycode, int ctrl, std::string const& source, U& userdata)
{
    enum { NONTERMINAL = 1, EMPTY, TERMINAL, LOOKAHEAD, YIELD };
    std::vector<long> kont;
//@<合成属性の作業変数定義@>

    std::string::const_iterator scanpos = source.cbegin ();
    std::string::const_iterator const endstr = source.cend ();
    int match_octet = 0;
    int octet = (scanpos < endstr) ? static_cast<unsigned char> (*scanpos) : -1;
    bool matched = false;
    while (0 < ctrl && ctrl < yycode.size ()) {
        unsigned long const code = yycode[ctrl];
        int const opcode =  code >> 28;             // 3 bits
        int const symbol = (code >> 16) & 0x1ffUL;  // 9 bits
        int const suc    = (code >>  8) & 0xffUL;   // 8 bits
        int const alt    =  code & 0xffUL;          // 8 bits
        if (TERMINAL == opcode || LOOKAHEAD == opcode) {
//@<terminal のシンボルと octet を比較@>
            if (TERMINAL == opcode && matched) {
                if (scanpos < endstr)
                    ++scanpos;
                match_octet = octet;
                octet = (scanpos < endstr) ? static_cast<unsigned char> (*scanpos) : -1;
            }
        }
        else if (NONTERMINAL == opcode) {
            kont.push_back (ctrl);
            ctrl = symbol;
        }
        else if (EMPTY == opcode) {
            matched = true;
        }
        else if (YIELD == opcode) {
//@<合成属性の処理@>
        }
        if (NONTERMINAL != opcode)
            ctrl = (matched) ? suc : alt;
        while (0 == ctrl && ! kont.empty ()) {
            ctrl = kont.back ();
            kont.pop_back ();
            int const ksuc = (yycode[ctrl] >> 8) & 0xffUL;
            int const kalt =  yycode[ctrl] & 0xffUL;
            ctrl = (matched) ? ksuc : kalt;
        }
    }
//@<合成結果取り出し@>
    return matched;
}

応用として、 RFC 7159 JSON をこの仮想マシン・コードにハンド・アセンブルしてみましょう。 JSON の構文は字句解析を構文解析にまとめても LL(1) なので、 字句解析部を別に作らなくても構文解析することができます。 ほんの少し構文を緩めて、 オブジェクトと配列に末尾コンマを許すようにしてあります。 入力は UTF-8 エンコーディング文字列とします。 なお、 null や true 等は後の改訂に備えて、 構文ではなく、 合成属性で文字列チェックすることにします。 これらは名前 (name) として受理するようにしてあります。

static std::vector<unsigned long> const rfc7159plus_grammar = {
    0x20000000UL, // 0x00         EMPTY              0x00, 0x00  番兵
//@<json 規則@>
//@<value 規則@>
//@<name 規則@>
//@<number 規則@>
//@<array 規則@>
//@<object 規則@>
//@<string 規則@>
};

json 規則では、 最初に value 非終端記号を解析します。 失敗時は失敗のまま終わらせて、 成功時は 2 番地へ移ります。 2 番地 では空白を読み飛ばしています。2 番地は繰り返しなので、 本来なら 2 番地と 3 番地の間に EMPTY 命令が入るのですけど、 3 番地の文字列末尾のチェックで matched 変数を上書きしてしまうので、 EMPTY 命令はあってもなくてもかまわないので、 省きました。

//@<json 規則@>=
// json <- value space* endinput
    0x10040200UL, // 0x01 json:   NONTERMINAL value  0x02, 0x00
    0x31000203UL, // 0x02         TERMINAL space     0x02, 0x03
    0x31010000UL, // 0x03         TERMINAL eof       0x00, 0x00

value 規則では、 終端記号を先読みして非終端記号への分岐をおこなっています。 文字列は JSON の値になるときと、 object のキーになる場合の 2 通りがあるので、 string 規則の合成属性では生の std::string を作るだけにしておきます。 それを strval 合成属性で拾って JSON の値オブジェクトを組み立てるという処理の流れを念頭に置いています。 null 等も name 非終端記号で生の std::string を得て、 litval 合成属性で文字列をチェックして null オブジェクト等を作るものとしています。 他の場合は、 JSON オブジェクトを直接作るので、 末尾非終端記号に直接飛び込んでいきます。

//@<value 規則@>=
// value <- space* (string {strval} / number / name {litval} / object / array)
    0x31000405UL, // 0x04 value:  TERMINAL space     0x04, 0x05
    0x40220608UL, // 0x05         LOOKAHEAD '"'      0x06, val1
    0x10380700UL, // 0x06         NONTERMINAL string 0x07, 0x00
    0x50040000UL, // 0x07         YIELD strval       0x00, 0x00
    0x41021409UL, // 0x08 val1:   LOOKAHEAD digit  number, 0x09
    0x402d140aUL, // 0x09         LOOKAHEAD '-'    number, val2
    0x41030b0dUL, // 0x0a val2:   LOOKAHEAD nmfrst   0x0b, val3
    0x100f0c00UL, // 0x0b         NONTERMINAL name   0x0c, 0x00
    0x50020000UL, // 0x0c         YIELD litval       0x00, 0x00
    0x307b2c0eUL, // 0x0d val3:   TERMINAL '{'     object, val3
    0x305b2400UL, // 0x0e val4:   TERMINAL '['      array, 0x00

name 規則では、 0x11 番地の繰り返しを抜けたときに成功へ昇格しなければならないので、 0x12 番地に EMPTY 命令を置いてあります。 mark 合成属性はスキャン・ポインタの位置を記録しておき、 save 合成属性で記録しておいた位置からスキャン・ポインタが進んだ位置までの文字列を切り出すものとします。

//@<name 規則@>=
// name <- {mark} nmfst nmchar* {save}
    0x50001000UL, // 0x0f name:   YIELD mark         0x10, 0x00
    0x31031100UL, // 0x10         TERMINAL nmfst     0x11, 0x00
    0x31041112UL, // 0x11         TERMINAL nmchar    0x11, 0x12
    0x20001300UL, // 0x12         EMPTY              0x13, 0x00
    0x50010000UL, // 0x13         YIELD save         0x00, 0x00

number 規則では、 mark 合成属性でマークしておいた位置から、 スキャン・ポインタが進んだ位置までを切り出して numval 合成属性で数値へ変換するものとします。 0x15 番地と 0x1e 番地が省略可能なマイナス記号の扱い方の例で、 suc と alt に同じ番地が入っています。 0x1c 番地から 0x1d 番地が省略可能な複数選択肢への分岐の書き方の例になっており、 alt で選択肢を結んでいき、 最後に 0x22 番地の EMPTY 命令につなぎます。

//@<number 規則@>=
// number <- '-'?([0]/[1-9][0-9]*)([.][0-9]+)?([eE][-+]?[0-9]+)?
    0x50001500UL, // 0x14 number: YIELD mark         0x15, 0x00
    0x302d1616UL, // 0x15         TERMINAL '-'       0x16, 0x16
    0x30301917UL, // 0x16         TERMINAL '0'       num1, 0x17
    0x31021800UL, // 0x17         TERMINAL digit     0x18, 0x00
    0x31021819UL, // 0x18         TERMINAL digit     0x18, num1
    0x302e1a1cUL, // 0x19 num1:   TERMINAL '.'       0x1a, num2
    0x31021b00UL, // 0x1a         TERMINAL digit     0x1b, 0x00
    0x31021b1cUL, // 0x1b         TERMINAL digit     0x1b, num2
    0x30651e1dUL, // 0x1c num2:   TERMINAL 'e'       0x1e, 0x1d
    0x30451e22UL, // 0x1d         TERMINAL 'E'       0x1e, num3
    0x302d201fUL, // 0x1e         TERMINAL '-'       0x20, 0x1f
    0x302b2020UL, // 0x1f         TERMINAL '+'       0x20, 0x20
    0x31022100UL, // 0x20         TERMINAL digit     0x21, 0x00
    0x31022122UL, // 0x21         TERMINAL digit     0x21, num3
    0x20002300UL, // 0x22 num3:   EMPTY              0x23, 0x00
    0x50030000UL, // 0x23         YIELD numval       0x00, 0x00

array 規則は、 末尾コンマを許すコンマ区切りリストの書き方の例になっています。 0x26 番地の右角括弧は空リストの場合と末尾コンマの後の場合に対応しています。 0x2b 番地の右角括弧は value の後にコンマなしで閉じる場合に対応します。

//@<array 規則@>=
// array <- "[" {aryval} space* (value {aryitem} space*
//              ("," value {aryitem} space*)* ("," space*))? "]"
    0x50052500UL, // 0x24 array:  YIELD aryval       0x25, 0x00
    0x31002526UL, // 0x25 ary1:   TERMINAL space     0x25, 0x26
    0x305d0027UL, // 0x26         TERMINAL ']'       0x00, 0x27
    0x10042800UL, // 0x27         NONTERMINAL value  0x28, 0x00
    0x50062900UL, // 0x28         YIELD aryitem      0x29, 0x00
    0x3100292aUL, // 0x29         TERMINAL space     0x29, 0x2a
    0x302c252bUL, // 0x2a         TERMINAL ','       ary1, 0x2b
    0x305d0000UL, // 0x2b         TERMINAL ']'       0x00, 0x00

object 規則では、 裸の識別子をキーに使わないため、 先読みなしで string 非終端記号のチェックに入れます。 value 非終端記号の後は array 規則と同じで、 末尾コンマありのコンマ区切りリストになっています。

//@<object 規則@>=
// object <- "{" {objval} space* (member {objmem} space*
//               ("," member {objmem} space*)* ("," space*))? "}"
// member <- space* string {strkey} space* ':' value
    0x50072d00UL, // 0x2c object: YIELD objval       0x2d, 0x00
    0x31002d2eUL, // 0x2d obj1:   TERMINAL space     0x2d, 0x2e
    0x307d002fUL, // 0x2e         TERMINAL '}'       0x00, 0x2f
    0x10383000UL, // 0x2f         NONTERMINAL string 0x30, 0x00
    0x50083100UL, // 0x30         YIELD strkey       0x31, 0x00
    0x31003132UL, // 0x31         TERMINAL space     0x31, 0x32
    0x303a3300UL, // 0x32         TERMINAL ':'       0x33, 0x00
    0x10043400UL, // 0x33         NONTERMINAL value  0x34, 0x00
    0x50093500UL, // 0x34         YIELD objmem       0x35, 0x00
    0x31003536UL, // 0x35         TERMINAL space     0x35, 0x36
    0x302c2d37UL, // 0x36         TERMINAL ','       obj1, 0x37
    0x307d0000UL, // 0x37         TERMINAL '}'       0x00, 0x00

string 規則では合成属性で UTF-8 のコード・ポイント範囲チェックをしたかったので、 UTF-8 のシーケンスを辿るようにしてあります。

//@<string 規則@>=
// string <- ["] {strlit}
//           ( "\\" ( "u" xdigit xdigit xdigit xdigit {stre16}
//                  / [\\/"bfnrt] {strsng} )
//           / u00 {stra7}
//           / uc0 u80 {stru8}
//           / ue0 u80 u80 {stru8}
//           / uf0 u80 u80 u80 {stru8} )* ["]
    0x30223900UL, // 0x38 string: TERMINAL '"'       0x39, 0x00
    0x500a3a00UL, // 0x39         YIELD strlit       0x3a, 0x00
    0x3022003bUL, // 0x3a str1:   TERMINAL '"'       0x00, 0x3b
    0x305c453cUL, // 0x3b         TERMINAL '\\'      esc1, 0x3c
    0x31053d3eUL, // 0x3c         TERMINAL u00       0x3d, 0x3e
    0x500b3a00UL, // 0x3d         YIELD stra7        str1, 0x00
    0x3107433fUL, // 0x3e         TERMINAL uc0       0x43, 0x3f
    0x31084240UL, // 0x3f         TERMINAL ue0       0x42, 0x40
    0x31094100UL, // 0x40         TERMINAL uf0       0x41, 0x00
    0x31064200UL, // 0x41         TERMINAL u80       0x42, 0x00
    0x31064300UL, // 0x42         TERMINAL u80       0x43, 0x00
    0x31064400UL, // 0x43         TERMINAL u80       0x44, 0x00
    0x500c3a00UL, // 0x44         YIELD stru8        str1, 0x00
    0x3075464bUL, // 0x45 esc1:   TERMINAL 'u'       0x46, esc2
    0x310a4700UL, // 0x46         TERMINAL xdigit    0x47, 0x00
    0x310a4800UL, // 0x47         TERMINAL xdigit    0x48, 0x00
    0x310a4900UL, // 0x48         TERMINAL xdigit    0x49, 0x00
    0x310a4a00UL, // 0x49         TERMINAL xdigit    0x4a, 0x00
    0x500d3a00UL, // 0x4a         YIELD stre16       str1, 0x00
    0x310b4c00UL, // 0x4b esc2:   TERMINAL esc00     0x4c, 0x00
    0x500e3a00UL  // 0x4c         YIELD strsng       str1, 0x00

とりあえず、 構文チェックをするだけなら、 次のように終端記号との比較を記述しておきます。 octet は入力文字列の先読みしているオクテットです。

//@<terminal のシンボルと octet を比較@>=
            switch (symbol) {
            case 0x100: matched = std::isspace (octet) && '\v' != octet; break;  // space
            case 0x101: matched = (octet < 0); break;                            // eof
            case 0x102: matched = std::isdigit (octet); break;                   // digit
            case 0x103: matched = (std::isalpha (octet) || '_' == octet); break; // nmfst
            case 0x104: matched = (std::isalnum (octet) || '_' == octet); break; // nmchar
            case 0x105: matched = (0x20 <= octet && octet <  0x7f); break;       // u00
            case 0x106: matched = (0x80 <= octet && octet <= 0xbf); break;       // u80
            case 0x107: matched = (0xc0 <= octet && octet <= 0xdf); break;       // uc0
            case 0x108: matched = (0xe0 <= octet && octet <= 0xef); break;       // ue0
            case 0x109: matched = (0xf0 <= octet && octet <= 0xf7); break;       // uf0
            case 0x10a: matched = std::isxdigit (octet); break;                  // xdigit
            case 0x10b: // esc00
                matched = (0x20 <= octet && octet < 0x7f && 'U' != octet && 'x' != octet);
                break;
            default:    matched = (symbol == octet); break;
            }