AOJ 2643 AI
問題文
ロボットのいる盤面と, 以下のEBNF(Extended BNF) で表されるプログラムが与えられる.
ロボットがこのプログラムに従って動作する時, ゴールまでのステップ数を出力せよ(到達不可能ならば-1). (プログラムの詳細, 注意事項は元の問題文参照)
プログラム:= {文};
文:= if 文|while 文|動作文;
if 文:= "[", 条件, プログラム, "]";
while 文:= "{", 条件, プログラム, "}";
動作文:= "^"|"v"|"<"|">";
条件:= ["~"], "N"|"E"|"S"|"W"|"C"|"T";
解法
ひたすらパーサーを書く.
無限ループを検出するには while文開始時に現在と同じ (位置, 向き, 命令のインデックス) を経由したことがあるかを確認すればよい.
while文, if文で cond が False だったときはその statement の終了位置まで読み進める必要があるが, これは括弧の対応関係を見れば終端が分かる.
感想
終了or無限ループ判定は例外を使うべきだった気がする.
構文解析でバグった時はどうすればいいんですかね…
