AOJ 構文解析

簡単な文字列処理

構文解析器を書いたりする必要がないものたちです． STL の使い方の練習など．

簡単な構文解析

簡単な構文解析器を書く練習です． Python などの eval で殴れるレベルです．

簡単な構文解析 2

やること自体は単純ですが，ほんの少し面倒なものたちです． 適宜，構造体などを定義して実装するとよいかもしれません． 構文解析器の返り値は必ずしも整数値である必要はないことを覚えておきましょう． 

// {"|", "^", "&", "+-", "*/"} のように，二項演算子を優先度が高くなる順に並べます
std::vector<std::string> BIN_OPS = {"+-", "*/%"};
ResultType parse(const std::string& s, size_t& i, size_t p) {
  if (p == BIN_OPS.size()) {
    if (s[i] == '(') {
      res = parse(s, ++i, 0);
      assert(s[i] == ')');
      ++i;
    } else if (s[i] == '~') {
      // 前置の単項演算子があれば適当にやります
      res = ~parse(s, ++i, p);
    } else if (/* リテラル */) {
      // 数値なりを適当にパースします
    }
    // 後置の単項演算子があれば適当にやります
    // 適当おわり
    return res;
  }

  ResultType res = parse(s, i, p+1);
  while (i < s.length()) {
    bin_op = s[i];
    if (bin_op not in BIN_OPS[p]) break;
    ResultType tmp = parse(s, ++i, p+1);
    res.op_eq(op, tmp);
  }
  return res;
}

ここでいう簡単とは，定跡に沿って実装すればそのまま Accept される，程度の意味です．

一風変わった構文解析

全探索をする構文解析

与えられた入力に対して代入を行い，パースを何度も行うタイプの問題です．

Python で楽をするタイプの構文解析

C++ で頑張ろうとすると面倒そうに見えますが，Python で正規表現 (re) が使えたりすると殴りやすい問題です． この手の問題を見極められると嬉しいかもしれません．

難しめの構文解析

処理すべき文字列が，必ずしも与えられた文法に沿っていない場合，少々つらさが増します． 特に，与えられた文字列に自分で手を加えたものを処理する必要がある場合，バグを埋め込みやすいので注意です（適当に手を加えた文字列が正しい文法に沿っているかきちんと確認をしましょう）．

やや面倒な構文解析

構文解析以外に面倒な要素が含まれていて面倒ですが，落ち着いてやれば平気です．

面倒な構文解析

やりたくない．やらないことはないんですが．

面白い構文解析

やりたい．大変かもしれませんが苦痛ではないはずです．

難しい構文解析

知識が必要そうな問題です．天才にとってはそんなことないかもしれません．基本的には区間 DP です．

To-Do

えびちゃんの課題です．