再帰上昇構文解析

再帰上昇構文解析はコールスタックを利用したLR法の実装方式です。この方式ではshiftやgotoに伴うスタックへのプッシュは関数呼び出しに、reduceに伴うスタックのポップは return に対応します。

再帰上昇構文解析における構文解析関数は同じ高さのスタックが行わなければならない操作の集合体です。したがって、構文解析関数が行わなければならないのは次の２つです。

• 関数呼び出し時に現在の状態と次の記号に対応するアクションを実行する
• 制御復帰時にreduceを継続するかまたはgotoを実行する

スタックの内容はプッシュとポップ以外では変化しないので、構文解析関数は状態ごとに分解することができます。

例

次の文脈自由文法によって生成される言語 $\lbrace a^n b^n \mid n \in \mathbf{N} \rbrace$ を受理する再帰上昇パーサーについて考えます。

\begin{aligned}
 & S \rightarrow a S b \\
 & S \rightarrow \epsilon
\end{aligned}

この文法から構築されるLALR(1)構文解析表は次の通りです。ここで $⊣$ は入力文字列の終了を表す記号です。

	$a$	$b$	$⊣$	$S$
1	s3		r2	2
2			acc
3	s3	r2		4
4		s5
5		r1	r1

この表をもとに次のような再帰上昇パーサーを書くことができます。

anbn.c

// gcc -std=c23 anbn.c

#include <setjmp.h>
#include <stdio.h>
#include <stdlib.h>

constexpr int PARSING_SUCCESS = 1;
constexpr int PARSING_FAIL = 2;

struct reduction
{
    char lhs;
    int count;
};

static struct reduction state1(char const **, jmp_buf *);
static struct reduction state2(char const **, jmp_buf *);
static struct reduction state3(char const **, jmp_buf *);
static struct reduction state4(char const **, jmp_buf *);
static struct reduction state5(char const **, jmp_buf *);

int main()
{
    constexpr size_t bufsize = 4000;
    char *buf = malloc(bufsize);

    auto c = fread(buf, 1, bufsize - 1, stdin);

    if (ferror(stdin))
    {
        fputs("io error.\n", stderr);
        goto fail;
    }

    if (!feof(stdin))
    {
        fputs("too big input.\n", stderr);
        goto fail;
    }

    buf[c] = '\0';

    char const *s = buf;
    jmp_buf ret;
    
    switch (setjmp(ret))
    {
    case PARSING_SUCCESS:
        puts("ACCEPT");
        break;

    case PARSING_FAIL:
        puts("REJECT");
        break;

    case 0:
        state1(&s, &ret);
        [[fallthrough]];

    default:
        fputs("something is wrong.\n", stderr);
        goto fail;
    }

    free(buf);
    return 0;

fail:

    free(buf);
    return 1;
}

// S' -> . S, ⊣
// S  -> . a S b, ⊣
// S  -> ., ⊣
static struct reduction state1(char const **s, jmp_buf *ret)
{
    struct reduction r;
    
    switch (**s)
    {
    case 'a':
        // shift 3
        ++*s;
        r = state3(s, ret);
        break;

    case '\0':
        // reduce S -> ε
        r = (struct reduction){ 'S', 0 };
        break;

    default:
        // reject
        longjmp(*ret, PARSING_FAIL);
    }

    while (true)
    {
        if (r.count > 0)
        {
            return (struct reduction){ r.lhs, r.count - 1 };
        }

        if (r.lhs == 'S')
        {
            // goto 2
            r = state2(s, ret);
        }
        else
        {
            // reject
            longjmp(*ret, PARSING_FAIL);
        }
    }
}

// S' -> S ., ⊣
static struct reduction state2(char const **s, jmp_buf *ret)
{
    if (**s == '\0')
    {
        // accept
        longjmp(*ret, PARSING_SUCCESS);
    }
    else
    {
        // reject
        longjmp(*ret, PARSING_FAIL);
    }
}

// S -> a . S b, ⊣
// S -> a . S b, b
// S -> . a S b, b
// S -> ., b
static struct reduction state3(char const **s, jmp_buf *ret)
{
    struct reduction r;

    switch (**s)
    {
    case 'a':
        // shift 3
        ++*s;
        r = state3(s, ret);
        break;

    case 'b':
        // reduce S -> ε
        r = (struct reduction){ 'S', 0 };
        break;

    default:
        // reject
        longjmp(*ret, PARSING_FAIL);
    }

    while (true)
    {
        if (r.count > 0)
        {
            return (struct reduction){ 'S', r.count - 1 };
        }

        if (r.lhs == 'S')
        {
            // goto 4
            r = state4(s, ret);
        }
        else
        {
            // reject
            longjmp(*ret, PARSING_FAIL);
        }
    }
}

// S -> a S . b, ⊣
// S -> a S . b, b
static struct reduction state4(char const **s, jmp_buf *ret)
{
    struct reduction r;

    if (**s == 'b')
    {
        // shift 5
        ++*s;
        r = state5(s, ret);
    }
    else
    {
        // reject
        longjmp(*ret, PARSING_FAIL);
    }

    if (r.count > 0)
    {
        return (struct reduction){ r.lhs, r.count - 1 };
    }

    // reject
    longjmp(*ret, PARSING_FAIL);
}

// S -> a S b ., ⊣
// S -> a S b ., b
static struct reduction state5(char const **s, jmp_buf *ret)
{
    switch (**s)
    {
    case 'b':
    case '\0':
        // reduce S -> a S b
        return (struct reduction){ 'S', 3 - 1 };

    default:
        // reject
        longjmp(*ret, PARSING_FAIL);
    }
}

構文解析関数 stateQ は switch 文と while 文からなります。ただし、到達不能コードの除去によってこの構造が暗黙的なものになっているものもあります (state2 など) 。 switch 文は関数呼び出し時の動作に対応し、 while 文は制御復帰時の動作に対応しています。

switch 文は先頭の記号を参照して行うべき動作を選択します。shiftが選択された場合は先頭の記号を除去してからshift先の状態に対応する関数を呼び出します。戻り値は while 文へ伝えられます。reduceが選択された場合は還元についての情報を while 文へ伝えます。acceptかrejectが選択された場合は longjmp を使って構文解析を終了します。

while 文ではまず、還元に伴うスタックフレームのポップが完了しているかどうかを判定します。完了していない場合は return し、完了している場合はgoto先の状態に対応する関数を呼び出します。戻った場合は同じことをもう一度行います。