トライ木主導の字句解析器の試行

プログラミング言語 Oberon-0 の字句解析をトライ木をメインに使うやりかたで書いてみました。

この言語は多数のキーワードが定義されていて、 トライ木はキーワードと記号にマッチするように作ってあります。 キーワードの途中で失敗したときに、 識別子として解析を続けるようにします。 コメント開始記号はトライ木でマッチした後にそれぞれ用の関数で解析を続けます。 この手の字句解析を決定性オートマトンで記述すると状態のほとんどがキーワードや記号のトライが食いつぶしてしまって、 無駄が増えてしまいます。 なので、 トライ部分はトライとしてダブル配列で扱い、 そうでない残りは関数で処理することにしたわけです。

トライ木のダブル配列は静的に作成したものを使っています。 テーブルの生成には Ruby で書いてあります。

トライが扱う文字のコード化で、 制御文字を空白へ、 数字をゼロへ英小文字を a へと縮退したものを使って、トライの条件分岐サイズを抑えてあります。

# excludes [\x00- 1-9b-z]
i = 2
codes = {}
('!'.ord .. '0'.ord).each{|c| codes[c.chr] = i; i += 1 }
(':'.ord .. 'a'.ord).each{|c| codes[c.chr] = i; i += 1 }
('{'.ord .. '~'.ord).each{|c| codes[c.chr] = i; i += 1 }

キーワードは Oberon-0 コンパイラに合わせて Oberon-07 のものも含めてあり、 Oberon-0 で使わないリザーブ・キーワードを見つけると警告を表示して無視する方針にしています。 トークンの番号は Oberon-0 コンパイラのものに合わせています。

symbols = {
  :null => 0, :times => 1, :div => 3, :mod => 4,
  :and => 5, :plus => 6, :minus => 7, :or => 8, :eql => 9,
  :neq => 10, :lss => 11, :leq => 12, :gtr => 13, :geq => 14,
  :period => 18, :char => 20, :int => 21, :false => 23, :true => 24,
  :not => 27, :lparen => 28, :lbrak => 29,
  :ident => 31, :if => 32, :while => 34, :repeat => 35,
  :comma => 40, :colon => 41, :becomes => 42, :rparen => 44,
  :rbrak => 45, :then => 47, :of => 48, :do => 49,
  :semicolon => 52, :end => 53,
  :else => 55, :elsif => 56, :until => 57,
  :array => 60, :record => 61, :const => 63, :type => 64,
  :var => 65, :procedure => 66, :begin => 67, :module => 69,
  :eof => 70
}
tokens = [
  [:neq, '#'], [:and, "&"], [:null, "(*"], [:lparen, "("], [:rparen, ")"],
  [:times, "*"], [:plus, "+"], [:comma, ","], [:minus, "-"], [:period, "."],
  [:null, "/"], [:becomes, ":="], [:colon, ":"], [:semicolon, ";"],
  [:lss, "<"], [:leq, "<="], [:eql, "="], [:gtr, ">"], [:geq, ">="],
  [:lbrak, "["], [:rbrak, "]"], [:not, "~"], [:array, "ARRAY"],
  [:begin, "BEGIN"], [:null, "BY"], [:const, "CONST"], [:div, "DIV"],
  [:do, "DO"], [:else, "ELSE"], [:elsif, "ELSIF"], [:end, "END"],
  [:false, "FALSE"], [:null, "FOR"], [:if, "IF"], [:null, "IMPORT"],
  [:null, "IN"], [:null, "IS"], [:mod, "MOD"], [:module, "MODULE"],
  [:null, "NIL"], [:of, "OF"], [:or, "OR"], [:null, "POINTER"],
  [:procedure, "PROCEDURE"], [:record, "RECORD"], [:repeat, "REPEAT"],
  [:null, "RETURN"], [:then, "THEN"], [:null, "TO"], [:true, "TRUE"],
  [:type, "TYPE"], [:until, "UNTIL"], [:var, "VAR"], [:while, "WHILE"],
]

tokens からトライ木を作成し、 さらにそれをダブル配列にします。 ここはセオリー通りでなんのひねりもありません。

def create_trie(tokens, codes, symbols)
  rule = [[]]
  tokens.each do |tk, kw|
    state = 0
    kw.each_char do |c|
      state1 = rule[state][codes[c]]
      if state1.nil?
        state1 = rule.size
        rule << []
        rule[state][codes[c]] = state1
      end
      state = state1
    end
    rule[state][1] = symbols[tk]
  end
  rule
end

def compact_table(rule)
  base = [0, 0]
  check = [0, 0]
  modify_table(base, check, rule, 0, 1)
  check.each_index{|x| base[x] ||= 0; check[x] ||= 0 }
  offset = base.min
  if offset < 0
    base.each_index{|x| base[x] -= offset }
  end
  [base, check]
end

def modify_table(base, check, rule, rule_state, base_state)
  row = rule[rule_state]
  b = row.index{|x| not x.nil? }
  d = row.rindex{|x| not x.nil? }
  base[base_state] = -b
  until (b .. d).all?{|i| row[i].nil? or check[base[base_state] + i].nil? }
    base[base_state] += 1
  end
  (b .. d).each do |i|
    if row[i]
      base[base[base_state] + i] = 0
      check[base[base_state] + i] = base_state
    end
  end
  if rule[rule_state][1]
    base[base[base_state] + 1] = rule[rule_state][1]
  end
  (2 ... rule[rule_state].size).each do |c|
    if rule[rule_state][c]
      modify_table(base, check, rule, rule[rule_state][c], base[base_state] + c)
    end
  end
end

C++11 に作成した表を組み込んで使います。

static const long MAXINT = 2147483647L;

enum {
    TNULL      =  0, TTIMES     =  1, TDIV       =  3, TMOD       =  4,
    TAND       =  5, TPLUS      =  6, TMINUS     =  7, TOR        =  8,
    TEQL       =  9, TNEQ       = 10, TLSS       = 11, TLEQ       = 12,
    TGTR       = 13, TGEQ       = 14, TPERIOD    = 18, TCHAR      = 20,
    TINT       = 21, TFALSE     = 23, TTRUE      = 24, TNOT       = 27,
    TLPAREN    = 28, TLBRAKET   = 29, TIDENT     = 31, TIF        = 32,
    TWHILE     = 34, TREPEAT    = 35, TCOMMA     = 40, TCOLON     = 41,
    TBECOMES   = 42, TRPAREN    = 44, TRBRAKET   = 45, TTHEN      = 47,
    TOF        = 48, TDO        = 49, TSEMICOLON = 52, TEND       = 53,
    TELSE      = 55, TELSIF     = 56, TUNTIL     = 57, TARRAY     = 60,
    TRECORD    = 61, TCONST     = 63, TTYPE      = 64, TVAR       = 65,
    TPROCEDURE = 66, TBEGIN     = 67, TMODULE    = 69, TEOF       = 70,
};

enum { NTOK_CHECK = 187 };
static const unsigned char TOK_BASE[NTOK_CHECK] = {
      2,   0,   4,  12,   7,   5,   2,  23,  16,  22,  30,  31,  34,  35,
     40,  46,  42,  48,  49,  53,  54,   3,  30,  15,  35,  32,  44,  49,
     68,   8,  42,  71,   7,   9,  20,  73,  86,  92,  86,   2, 113,  43,
    125, 134, 153, 149,  44,  54,  13, 185,  14, 186,  11,  15,  16,  16,
     34,  11,  61, 187,  62,  47,  34,  33,  29,  67,  69,   2,  51,  34,
     30,  30,  75,  55,  65,  32,  78,   5,  51,  53,  87,  79,  68,  38,
     59,  63,  57,  89,  58,  91,  55,  58,  52,  67,  96,  25,  98,   2,
     34,  99,  64,  62,  61, 105,   2,  56,  62, 109,   2,   2,  85, 114,
    110,   6,  88, 117,  71,  84, 120,   2, 122,  50,  10,  93,  89,  85,
     94, 101,  89, 131,   2, 108, 123, 107, 109,  93,  97, 111, 140,  68,
    116, 105, 103, 118, 146,  63, 124, 106, 150,  37, 111, 116, 154,   2,
    119, 129, 123,  80, 107, 161,  49,   2, 162, 137, 167, 120,  26, 141,
    170,  66, 129, 142, 129, 140, 176,  59, 137, 179,  67, 149, 147, 155,
    184,  36,  31,  47,  29,
};
static const unsigned char TOK_CHECK[NTOK_CHECK] = {
      0,   0,   1,   2,   5,   1,  32,   1,   1,   1,   1,   1,   1,   1,
      1,   8,   1,   1,   1,   1,   1,   9,   7,   1,   1,   1,   1,   1,
      1,  10,  11,   1,   7,  12,  13,   1,   1,   1,   1,  14,   1,  16,
      1,   1,   1,   1,  61,  17,  18,   1,  68,   1,  19,  20,  73,  23,
     55,  56,  57,   1,  58,  16,  24,  62,  63,  64,  65,  82,  18,  25,
     69,  70,  71,  20,  72,  26,  75,  76,  81,  83,  79,  26,  24,  27,
     79,  27,  80,  84,  87,  85,  89,  28,  91,  92,  93,  94, 105,  96,
     99,  31, 106, 100, 101, 102, 103,  28,  31,  31, 107, 112,  35, 110,
     31, 111, 157, 114, 115,  36, 117, 118,  37, 120, 132,  38, 123, 124,
     38, 125, 127, 128, 129, 126,  37, 131, 133, 134, 135, 136, 137, 138,
     40, 140, 141, 142, 143, 144, 154, 146, 147, 148, 158, 150, 151, 152,
    140,  42, 155, 111, 140, 156, 159, 162,  42, 165, 163,  42, 164, 172,
    167, 168,  43, 170,  42, 171, 173, 174,  44, 176, 177,  45, 179, 180,
    181, 182,  49,  51,  59,
};

Oberon-0 コンパイラと同じで、 字句解析部へエラー時のソースコード行表示機能をあわせ持たせます。

struct scanner_type {
public:
    int m_sym;
    long m_value;
    std::string m_id;
    std::string m_filename;

    explicit scanner_type (std::string const& str);
    void get (void);
    void report_error (char const* msg);
    int error_count (void);

private:
    void getch (void);
    void identifier (void);
    void number (void);
    void comment (void);

    std::string::const_iterator m_text;
    std::size_t m_size;
    std::size_t m_pos;
    int m_error_count;
    int m_ch;
    int m_line;
    int m_column;
};

字句解析オブジェクトは、 コンストラクタへソース・コード全体を文字列にして作成します。 コンパイラ作成例題用の簡易言語なので、 ソースコードが長くなることは、 おそらくないでしょうから文字列に全部いれても問題ないでしょう。

scanner_type::scanner_type (std::string const& str)
    : m_id (), m_filename (), m_text (str.cbegin ()), m_size (str.size ()), m_pos (0)
{
    m_error_count = 0;
    m_ch = 0;
    m_line = 1;
    m_column = 0;
    getch ();
}

字句解析の中心部分である get メンバ関数は字句を一つ切り出す働きをします。 まず空白を読み飛ばして字句が数字で始まるときは数値リテラルとして読み取ります。 また、 英小文字で始まるときに識別子として読み取ります。 他の場合は上のトライ木を使って記号とキーワードを読み取っていきます。 英大文字でキーワードを読み終わる前に失敗したときは識別子として読み取りを続けます。 またキーワードの読み取りが終わっても英数字が続くときはキーワードではなく識別子として読み取ります。

void
scanner_type::get (void)
{
    int const base0 = TOK_BASE[0];
    do {
        while (0 <= m_ch && m_ch <= ' ')
            getch ();
        m_sym = TNULL;
        m_id.clear ();
        m_value = 0;
        if (m_ch < 0) {
            m_sym = TEOF;
        }
        else if (std::isdigit (m_ch)) {
            number ();
        }
        else if (std::islower (m_ch)) {
            identifier ();
        }
        else {
            int const alt = std::isupper (m_ch) ? TIDENT : TNULL;
            int next_state = 1;
            while (next_state > 0 && m_ch >= 0) {
                int const state = next_state;
                next_state = 0;
                int const code = m_ch > 'z' ? m_ch - ('{' - 58)
                               : m_ch > 'a' ? 'a'  - (':' - 18)
                               : m_ch > '9' ? m_ch - (':' - 18)
                               : m_ch > '0' ? '0'  - ('!' -  2)
                               : m_ch > ' ' ? m_ch - ('!' -  2)
                               : 0;
                int const i = TOK_BASE[state] - base0 + code;
                int const j = TOK_BASE[state] - base0 + 1;
                if (0 < i && i < NTOK_CHECK && TOK_CHECK[i] == state)
                    next_state = i;
                else if (alt == TIDENT && std::isalnum (m_ch))
                    identifier ();
                else if (0 < j && j < NTOK_CHECK && TOK_CHECK[j] == state)
                    m_sym = TOK_BASE[j] - base0;
                else
                    m_sym = alt;
                if (1 == state || next_state > 0) {
                    m_id.push_back (m_ch);
                    getch ();
                }
            }
            if (m_id == "(*")
                comment ();
            else if (m_sym == TNULL && alt == TIDENT)
                report_error ("reserved keyword");
            else if (m_sym == TNULL)
                report_error ("unrecognized symbol");
        }
    } while (m_sym == TNULL);
}

識別子は英数字列を読み取れるだけ読み取って、 長さリミットを越えていたらエラーを表示します。

void
scanner_type::identifier (void)
{
    m_sym = TIDENT;
    while (std::isalnum (m_ch)) {
        m_id.push_back (m_ch);
        getch ();
    }
    if (m_id.size () > 64)
        report_error ("too long identifier");
}

数字は 10 進数の符号なし整数しか実装しません。 長すぎたり数字の直後に空白をおかずに識別子が置いてあるときはエラーを発生するようにしています。 また 32 ビット符号整数の範囲を越えたときもエラーを投げます。

void
scanner_type::number (void)
{
    m_sym = TINT;
    int state = 1;
    while (std::isalnum (m_ch)) {
        if (1 != state)
            ;
        else if (m_ch > '9')
            state = 3;
        else if (m_value < (MAXINT - (m_ch - '0')) / 10)
            m_value = m_value * 10 + (m_ch - '0');
        else
            state = 2;
        m_id.push_back (m_ch);
        getch ();
    }
    if (1 != state)
        m_value = 0;
    if (2 == state)
        report_error ("too large number");
    else if (3 == state)
        report_error ("illegal digits");
    else if (m_id.size () > 64)
        report_error ("too long digits");
}

コメントに入れ子を許します。 カウンタを使って入れ子を追跡します。

void
scanner_type::comment (void)
{
    int level = 1;
    int state = 1;
    while (level > 0) {
        if (m_pos >= m_size) {
            report_error ("comment not closed");
            break;
        }
        if (2 == state && ')' == m_ch) {
            --level;
            state = 1;
        }
        else if (3 == state && '*' == m_ch) {
            ++level;
            state = 1;
        }
        else {
            state = '*' == m_ch ? 2 : '(' == m_ch ? 3 : 1;
        }
        getch ();
    }
}

getch はソースコードから一文字読み取ります。 単に読み取るだけでなく、 エラー表示に備えて行番号とカラム位置も合わせて更新していきます。

void
scanner_type::getch (void)
{
    if (m_pos >= m_size) {
        m_ch = -1;
    }
    else {
        if ('\n' == m_ch) {
            ++m_line;
            m_column = 0;
        }
        ++m_column;
        m_ch = m_text[m_pos++];
    }
}

エラーを表示します。 エラーのフォーマットは Clang のようにしておきました。

void
scanner_type::report_error (char const* msg)
{
    std::size_t const q = m_pos - 1;
    ++m_error_count;
    std::cerr << m_filename << ":" << m_line << ":" << m_column
        << ": error: " << msg << std::endl;
    for (std::size_t p = q - m_column + 1; p < m_size && '\n' != m_text[p]; ++p)
        std::cerr.put (m_text[p]);
    std::cerr << std::endl;
    for (std::size_t i = q - m_column + 1; i < q; ++i)
        std::cerr.put (' ');
    std::cerr << "^" << std::endl;
}