PASCAL 系数式用演算子優先度構文解析器

発端は 1976 年に発表された 8080 プロセッサ用 Palo Alto Tiny Basic アセンブリ・出力リストを見つけて読んでいたときに、 これの数式の構文が PASCAL 系言語と同じだと気がついたときに遡ります。 再帰下降型の数式解析器ではポピュラーな構文で、 上向き解析の数式解析器で良く使われている構文とは異なり単項の符号演算子を使わず、 多項式の先頭の項の前に符号を持たせる形式です。 この構文を等価な左再帰へ変換したものは現代でも、 Oberon-07 の数式の構文になっています。

/* PALO ALTO TINY BASIC の数式構文 */

assignment : LETTER "=" expression
           | "@" "(" expression ")" "=" expression;   /* 代入 */

expression : smpl_expr "="  smpl_expr   /* 比較結果の真は 1、偽はゼロ */
           | smpl_expr "#"  smpl_expr   /* 不等号 */
           | smpl_expr "<"  smpl_expr
           | smpl_expr "<=" smpl_expr
           | smpl_expr ">"  smpl_expr
           | smpl_expr "<=" smpl_expr
           | smpl_expr;

smpl_expr  : smpl_expr "+" term
           | smpl_expr "-" term
           | "+" term
           | "-" term
           | term;

term       : term "*" factor
           | term "/" factor
           | factor;

factor     : NUMBER                     /* 符号なし整数リテラル 0〜32767 */
           | LETTER                     /* 英字 1 文字 */
           | "@" "(" expression ")"     /* 配列、 添字はゼロから */
           | "ABS" "(" expression ")"
           | "RND" "(" expression ")"   /* RND(n) は 1 以上 n 以下を生成 */
           | "(" expression ")";

この構文を演算子優先度構文解析器にしてみます。 先頭項に符号がついているときは、 仮のゼロの項を前へ補うことで計算をおこなうやりかたにします。 さらに、 先頭項の符号を比較演算子の左辺と右辺の両方で利用できるようにするために、 比較演算子と加減演算子の間の優先度に一つ空きをつくってあるのが、 今回の工夫点です。

static const int PRECMIN = 1;
static const int PRECMAX = 999;

int
tinybasic_type::prec (int op)
{
    switch (op) {
    case '=': case '#': case '<': case '>': case LEQ: case GEQ: return PRECMIN;
    case '+': case '-': return PRECMIN + 2;
    case '*': case '/': return PRECMIN + 3;
    default:            return 0;
    }
}

丸括弧で囲む式の解析と右辺の解析を再帰呼び出しでおこなう手抜きをし、 先頭項にだけ符号を許すために優先度でガードして、 次のようになりました。

static const long NaNUM = -32768L;  // 整数演算エラー値

long
tinybasic_type::error (char const* errstr)
{
    // errstr とエラー発生箇所を表示
    return NaNUM;
}

long
tinybasic_type::expression (int pr)
{
    int la, op;
    long x, y;

    // 先頭項に符号がついているときは、 仮のゼロの項を前へ補う
    if (pr < PRECMIN + 2 && prec (m_token.sym) == PRECMIN + 2) {
        x = 0;
    }
    else if ('0' == m_token.sym) {  // 数値リテラル
        x = m_token.value;
        next_token ();
    }
    else if ('x' == m_token.sym) {  // 英字変数
        x = m_global_data[m_token.value];
        next_token ();
    }
    else if ('(' == m_token.sym) {  // "(" 式 ")"
        next_token ();
        x = expression (0);
        if (')' != m_token.sym)
            return error ("RIGHT PAREN?");
        next_token ();
    }
    else if ('@' == m_token.sym) {  // 配列
        next_token ();
        if ('(' != m_token.sym)
            return error ("LEFT PAREN?");
        x = expression (PRECMAX);
        if (x < 0 || m_global_data.size () < x + 26)
            return error ("RANGE!");
        x = m_global_data[x + 26];
    }
    else if (ABS == m_token.sym || RND == m_token.sym) {  // 組み込み手続き
        op = m_token.sym;
        next_token ();
        if ('(' != m_token.sym)
            return error ("LEFT PAREN?");
        x = apply (op, expression (PRECMAX), 0);
    }
    else {
        return error ("WHAT?");
    }
    if (NaNUM == x)
        return x;
    // 演算子先読みによる優先度解析器
    while ((la = prec (m_token.sym)) > 0 && la >= pr) {
        op = m_token.sym;
        next_token ();
        y = expression (la + 1);            // 右辺の値
        x = apply (op, x, y);
        if (la == PRECMIN || x == NaNUM)    // 比較演算子は右辺で打ち切り
            break;
    }
    return x;
}

apply で計算をおこなうとき、 引数のいずれかが NaNUM なら、 計算せずに NaNUM を直ちに返すようにします。

long
tinybasic_type::apply (int op, long x, long y)
{
    if (x == NaNUM || y == NaNUM) return NaNUM;
    switch (op) {
    case '=': return x == y;
    case '#': return x != y;
    case '<': return x <  y;
    case '>': return x >  y;
    case LEQ: return x <= y;
    case GEQ: return x >= y;
    case '+': return check_overflow (x + y);
    case '-': return check_overflow (x - y);
    case '*': return check_overflow (x * y);
    case '/': return y == 0 ? error ("DIV/0!") : check_overflow (x / y);
    case ABS: return abs (x);
    case RND: return x == 0 ? 0 : (random () >> 16) % abs (x) + 1;
    default: return NaNUM;
    }
}

long
tinybasic_type::check_overflow (long x)
{
    return (x < -32767L || 32767L < x) ? error ("OVERFLOW!") : x;
}

通常、 右辺値を求めるときは、 優先度をゼロに指定して呼び出します。 左辺値の配列添字を求めるときは、 代入と等号に同じ記号を使っているため、 等号とみなさないようにする目的で、 優先度を最高に指定します。

long
tinybasic_type::variable_left_value (void)
{
    if ('x' == m_token.sym) {
        long varaddr = m_token.value;
        next_token ();
        return varaddr;
    }
    else if ('@' == m_token.sym) {
        next_token ();
        if ('(' != m_token.sym)
            return error ("LEFT PAREN?");
        long idx = expression (PRECMAX);    // 優先度最高
        if (idx < 0 || m_global_data.size () < idx + 26)
            return error ("OUT OF RANGE!");
        return idx + 26;
    }
    return error ("VARIABLE?");
}

これで代入と右辺内の等号を区別するようになります。

long
tinybasic_type::fail (char const* errstr)
{
    error (errstr);
    return STATE_FAIL;
}

int
tinybasic_type::assignment (void)
{
    long left_value, value;
    if (LET == m_token.sym)
        next_token ();
    if ((left_value = variable_left_value ()) == NaNUM)
        return STATE_FAIL;
    if ('=' != m_token.sym)
        return fail ("EQUAL?");
    next_token ();
    if ((value = expression (0)) == NaNUM)
        return STATE_FAIL;
    m_global_data[left_value] = value;
    return STATE_SEMIS;
}