1282-Bug Hunt

デバッグ問題

問題概要

BNFに沿った形で式が与えられる．
配列外アクセスまたは未定義の変数の利用をしている式があったらその行を報告せよ

解法

構文解析．
=が含まれるときは代入文で，そうでないときは配列サイズ設定なのでそこで分岐する.
演算子が無いので楽．

実装(C++)

#include<map>
#include<iostream>
#include<cstdlib>
using namespace std;
#define REP(i,x) for(int i=0;i<(int)(x);i++)
#define dout(...) printf(__VA_ARGS__);fflush(stdout);
int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};
typedef pair<int,const char*> parsed;
map<int,int> var[256];
int varsize[256];
bool ans;
int parse(string in){
	if(isdigit(in[0]))
		return atoi(in.c_str());
	int arr=parse(in.substr(2,in.size()-3));
	int v=in[0];
	if(var[v].find(arr)==var[v].end()){
		ans=false;
	}
	return var[v][arr];
}
void parse2(const string& in){
	REP(i,in.size()){
		if(in[i]=='='){
			int lv=parse(in.substr(i+1));
			int arr=parse(in.substr(2,i-3));
			dout("%c(%d)=%d\n",in[0],arr,lv);
			if(arr>=varsize[(int)in[0]]){
				dout("out of array size\n");
				ans=false;
			}
			var[(int)in[0]][arr]=lv;
			return;
		}
	}
	string val=in.substr(2,in.size()-3);
	varsize[(int)in[0]]=atoi(val.c_str());
	dout("Dim %c(%d)\n",in[0],varsize[(int)in[0]]);
}
int main(){
	int start=false;
	for(string in;;){
		start=true;
		REP(i,256){
			var[i].clear();
			varsize[i]=0;
		}
		ans=true;
		bool back;
		for(int l=1;cin>>in;l++){
			if(in=="."&&start)return 0;
			if(in==".")break;
			start=false;
			if(!ans)continue;
			back=ans;
			parse2(in);
			if(back!=ans){
				cout<<l<<endl;
			}
		}
		if(ans)cout<<0<<endl;
	}
	return 0;
}