rowl0:字句解析の実装

rowl

字句解析には状態遷移表に基づく方法(lexはこれ)と状態遷移図に基づく方法があります。
rowl0は後者を手作業で実装しました。

1. トークンの定義 (token.s)
解析対象のトークンにIDを振ります。単一文字のトークンはそのascii番号をトークンIDとします。
したがって複数文字トークンは256から始めます。

.equ TOK_INT,       256 /* integer literal */
.equ TOK_STRING,    257 /* string literal */
.equ TOK_IDENT,     258 /* identifier */
...
.equ TOK_GE,        279 /* >= */
.equ TOK_DARROW,    280 /* => */
.equ TOK_END,       281 /* end of token */

2. 正規表現化 (以下lex.s)

spaces     : [\n\r\t ]
letter     : [A-Za-z_]
digit      : [0-9]
integer    : 0|[1-9][0-9]*
identifier : {letter}({letter)|{digit})*
escape     : \\['"?\\abfnrtv0]
character  : \'({escape}|[^\\\'\n])\'
string     : \"({escape}|[^\\\"\n])*\"
commentline: #[^\n\0]*\n
symbol     : .

3. 文字のグループ化
正規表現内で区別がいらない文字をグループ化

CH_NULL      : \0
CH_INVALID   : invalid characters
CH_SPACES    : [\t\r ]
CH_ZERO      : 0
CH_NONZERO   : [1-9]
CH_NORMALCH  : [A-Za-z_]-[abfnrtv]
CH_SPECIALCH : [abfrtv]
...
.equ CH_NULL,       0
.equ CH_INVALID,    1
.equ CH_SPACES,     2
.equ CH_ZERO,       3
.equ CH_NONZERO,    4
...

asciiコードから文字グループへのテーブルも定義

.section .rodata
lex_chgroup:
    .long  0,  1,  1,  1,  1,  1,  1,  1,  1,  2, 13,  1,  1,  2,  1,  1
    .long  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1
    .long  2, 12,  9, 14, 12, 12, 12,  8, 12, 12, 12, 12, 12, 12, 12, 12
    .long  3,  4,  4,  4,  4,  4,  4,  4,  4,  4, 12, 12, 12, 12, 12, 11
    .long 12,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5
    .long  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5, 12, 10, 12, 12,  5
    .long 12,  6,  6,  5,  5,  5,  6,  5,  5,  5,  5,  5,  5,  5,  7,  5
    .long 15,  5,  6,  5,  6,  5,  6,  5, 15,  5,  5, 12, 12, 12, 12,  1

4. 正規表現から状態遷移図を作る
本当は教科書に従ってε-NFAを作ってDFAにするんだけど、簡単な正規表現なので適当に作った。
下の表は状態1とか状態2とかが受理状態になっているけど、実際には"00"とか"100ab"とか不適なパターンを弾く為にもう一回遷移があります。
表はDrawIt!で描いてます。

+---+
|@n | == accepting state
+---+

+---+    0      +---+
| 0 +--+------->|@1 |
+---+  |        +---+
       | [1-9]  +---+
       +------->|@2 +--+
       |        +---+  | [0-9]
       |          ^    |
       |          +----+
       | letter +---+    others        +---+
       +------->| 3 +--+-------------->|@17| (detect reserved words here)
       |        +---+  |               +---+
       |          ^    | letter|digit
       |          +----+

5: 状態遷移図に従ってコード化
分岐がたくさんある場合はテーブルジャンプにする

...
/*
 *              N   I   S   Z   N   N   S   N   S   D   B   Q   S   N   S   P 
 *              U   N   P   E   O   O   P   :   Q   Q   A   U   Y   L   H   _ 
 *              L   V   A   R   N   R   E   :   U   U   C   E   M   :   A   O 
 *              L   A   C   O   Z   M   C   :   O   O   K   S   B   :   R   R 
 *              :   L   E   :   E   A   I   :   T   T   S   T   O   :   P   _ 
 *              :   I   S   :   R   L   A   :   E   E   L   I   L   :   :   X 
 *              :   D   :   :   O   C   L   :   :   :   A   O   :   :   :   : 
 *              :   :   :   :   :   H   C   :   :   :   S   N   :   :   :   : 
 *              :   :   :   :   :   :   H   :   :   :   H   :   :   :   :   : 
 */
s0_next:  .long s14,s15,s13, s1, s2, s3, s3, s3, s4, s9,s15,s12,s12,s13,s18,s19
s1_next:  .long s16,s15,s16,s15,s15,s15,s15,s15,s16,s16,s16,s16,s16,s16,s16,s15
...

コード化

...
s0:
    movl    $0, token_len
    movl    $0, token_val
    call    _lex_lookahead           // 一文字先読み
    movl    s0_next(,%eax,4), %eax   // テーブルジャンプ
    jmp     *%eax
s1:
    call    _lex_consume             // 入力を消費
    call    _lex_lookahead
    movl    $TOK_INT, token_tag
    movl    $0, token_val            // 状態1では整数0を受理
    movl    s1_next(,%eax,4), %eax
    jmp     *%eax
...

こんな風に「先読み」→「ジャンプ」→「入力消費」のパターンで状態遷移を記述していきます。*1

また、必要に応じてアクションを記述します。
例えば以下の部分なら

  • 状態0 で token_val = 0
  • 状態2 で token_val = token_val * 10 + (入力数字)

という計算をすれば、入力整数値も同時に得られます。

+---+
| 0 +--+
+---+  |
       | [1-9]  +---+
       +------->|@2 +--+
                +---+  | [0-9]
                  ^    |
                  +----+

*1:このようにジャンプ命令でコーディングするのが状態遷移図ベースの方法。状態遷移表ベースの方法では代わりに表を持っておいて、コード自体は一つのwhileループになります。