2007年アジア予選H問題（Bug Hunt）(2007/11/14(水) 00:05:05)

2007年アジア予選H問題を解いてみた。

以下のBNFのプログラムのインタプリタを作成し、何行目にバグがあるかを見つける問題。

<program> ::= <declaration> | <program><declaration> | <program><assignment>
<declaration> ::= <array name>[<number>]<new line>
<assignment> ::= <array name>[<expression>]=<expression><new line>
<expression> ::= <number> | <array name>[<expression>]
<number> ::= <digit> | <digit positive><digit string>
<digit string> ::= <digit> | <digit><digit string>
<digit positive> ::= 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
<digit> ::= 0 | <digit positive>
<array name> ::= a | b | c | d | e | f | g | h | i | j | k | l | m | 
                 n | o | p | q | r | s | t | u | v | w | x | y | z | 
                 A | B | C | D | E | F | G | H | I | J | K | L | M |
                 N | O | P | Q | R | S | T | U | V | W | X | Y | Z

問題のプログラムの仕様

次のプログラムは、『大きさが10の配列aの宣言』を意味する。
（配列のインデックスは、C言語と同じでNの大きさの配列では0〜N-1となる）

a[10]

また、次のプログラムは、『変数a[1]にa[2]を代入』を意味する。
代入は、宣言された変数及び有効なインデックス内でないとエラー（バグ）となる。
参照は、正常な配列を指定していても、配列の値を参照する場合は、既に代入された配列のインデックスでないとエラー（バグ）となる。

a[1]=a[2]

解法

配列の宣言のための構造体DEFINEと代入された値を保存するための構造体VALUEを用意する。
1行を読み込んだ時に、"="が含まれる行は『代入』、含まれない行は『宣言』の行として処理する。
新しい配列宣言が来るとDEFINEに追加し、代入が来るとVALUEに追加する。
基本的に1文字ずつ解析し、配列のインデックスの参照では再帰的に呼び出して実現している。
また、2重ポインタにしているのは、再帰先で解析された続きを解析するため。

ソース

（目標40分以内）

#include <iostream>
#include <vector>
using namespace std;

typedef struct DEFINE{
    char n;
    int  l;
    DEFINE(char n0, int l0){
        n = n0;l = l0;
    }
}DEFINE;

typedef struct VALUE{
    char n;
    int  i;
    int  v;
    VALUE(char n0, int i0, int v0){
        n = n0;i = i0;v = v0;
    }
}VALUE;

vector<DEFINE> define;
vector<VALUE> value;

int isDefine(char n, int index){
    for(int i = 0; i < define.size(); i++){
        if(define[i].n == n && define[i].l > index)return 1;
    }
    return 0;
}

int setValue(char n, int index, int v){
    if(isDefine(n, index) == 0)return 0;

    int i;
    for(i = 0; i < value.size(); i++){
        if(value[i].n == n && value[i].i == index){
            value[i].v = v;//更新
            break;
        }
    }
    if(i == value.size())value.push_back(VALUE(n, index, v));//新たに代入
    return 1;
}

int getValue(char n, int index){
    for(int i = 0; i < value.size(); i++){
        if(value[i].n == n && value[i].i == index)return value[i].v;
    }
    if(isDefine(n, index) == 1)return -1;//未代入
    return -2;//未定義
}

int getValue(VALUE v){
    if(isalpha(v.n))return getValue(v.n, v.i);//変数値
    if(v.i == 0)return v.v;//値
    return -3;//エラー
}

VALUE check(char **pp){
    char *p = *pp;
    if(isalpha(*p)){
        char name = *p++;
        if(*p == '['){
            p++;
            VALUE v = check(&p);
            int val = getValue(v);
            if(*p != ']' || val < 0)return VALUE(0, -1, -1);//構文エラー||未定義
            *pp = p;
            return VALUE(name, val, -1);
        }
        return VALUE(0, -1, -1);//構文エラー
    }
    if(isdigit(*p)){
        int sum = 0;
        for(; isdigit(*p); p++)sum = sum * 10 + *p - '0';
        *pp = p;
        return VALUE(0, 0, sum);
    }
    return VALUE(0, -1, -1);
}

int main(){
    char l[128];
    int line = 0, error = 0, dot = 0;

    while(1){
        line++;
        gets(l);
        if(l[0] == '.'){
            if(dot)break;
            cout << error << endl;//行数表示
            dot++;
            line = error = 0;
            define.clear();
            value.clear();
        }
        else if(error == 0){
            dot = 0;
            if(strchr(l, '=') != NULL){
                char *p1 = strtok(l, "=");
                char *p2 = strtok(NULL, "=");
                VALUE v1 = check(&p1);
                VALUE v2 = check(&p2);
                if(isDefine(v1.n, v1.i) == 0)error = line;//未定義
                else if(getValue(v2) < 0)error = line;//未定義 or 未代入
                else if(setValue(v1.n, v1.i, getValue(v2)) == 0)error = line;//代入エラー
            }
            else{
                char *p = l;
                VALUE v = check(&p);
                if(isalpha(v.n))define.push_back(DEFINE(v.n, v.i));//宣言
                else error = line;//宣言エラー
            }
        }
    }
    return 0;
}