10分で書ける、お手軽パーザー

ちょっと前までパーザーに凝ってたので、 ICPCで出題されるようなパーザー系の問題をさっぱりと解く方法を書きます。コツがわかれば誰でも速く正確に作れるようになります。

方法

まずは方法を考えます。基本的に、

再帰的降下型/LL(1)文法構文解析
副作用を避ける
効率無視

このような感じで実装を行います(パーザーコンビネータに影響を受けてます)。

一つ目は手書きパーザーの大原則です。間違ってもLR構文解析を実装できるなんて思わないで。それだけで一日仕事になってしまいます。また、演算子優先順位構文解析も持ち出さないほうがいいでしょう。式にしか適用できない上にLLよりもややアルゴリズムがややこしいです。

二つ目はバグなしコードを一発で書くには結構重要なのではないかと思います。生粋のCプログラマだと副作用のある・なしを意識すること自体が少ないですが。最後のは、細かいところをけちけち考えているとコードを書くのが遅くなるというぐらいの意味です。

LL構文解析

LL構文解析はBNFであらわされた文法を普通にトップダウンで解析する方法で、手でパーザーを書くときはこれを普通に再帰的な関数呼び出しとして実装します。 BNFさえ書けてしまえば後はそれをコードにしていくだけです。

☆落とし穴

LL文法を実装する際に問題になるのは左再帰をどうなるかということと、 LL(1)に入らない文法をどうするかということ。

左再帰

実はBNFにて左再帰は結構な頻度で現れます。これを右再帰形に持っていかなければならないのだが、構文解析の教科書にはなにやらややこしいことが書いてあります。次ような文法があったとして、

A = A x | y

A  = y A'
A' = x A' | ε

再帰的降下型のパーザーを手で書くのだがら、何も形式的な変換を行う必要は無いわけで、個々のケースに応じてやりやすい方法で書けばよいのです。で、そのケースですが、実際のところほとんどは繰り返しだったりします。

A = A x | ε

E = E + T | T

A = { x }

E = T { + T }

LL(1)に入らない文法の場合

普通に再帰的に記述する場合、一つの先読みで次に呼び出す関数が決定できないといけません。たとえば、Cの文法を考えると、intという文字を読み込んだとき、次にfoo;と来れば変数宣言ですし、foo(){ ... } と来れば関数宣言です。つまりこの段階で次の文字を読み込んで呼び出すべき関数が決定できていないので Cの文法はLL(1)ではないということです。これは普通に再帰的降下型では解析できません。考えられる解決策としては先読み文字を増やす、バックトラックなどがあります。先読み文字を増やすばあい、たとえば先の例であればint fooまで読み込んでも構文要素を決定できませんが、次の文字が ( であれば関数宣言だとわかります。つまり、決定できないところに関して、決定できるまで記号を先読みすればよいということになります。ただし、この場合、入力を逐次読み込みながら構文解析するなどといったコードを書くのが難しくなりますし(今回書こうとするパーザーはそのようなものでは有りませんが…)、また、判定部分が煩雑になります。もっと強力な方法はバックトラックです。これは候補をすべて試すというだけなのですが、 Cだとコードを書くのがやや面倒ですし、速度にすこし不安があります。しかし、構文のクラスとしてはLL(∞)でこれはBNFで記述できうる構文のクラスに一致します(…と思う)。

いろいろと書いてきましたが、どちらにせよ面倒です。しかし安心してください。パーザー系の問題でLL(1)で間に合わないことはまず有りません。多分再帰降下で書くのが普通だからだと思うのですが。

実装

一般的には一文字づつ入力を読み込みながら解析するのが主流のような感じですが、ここでは読み込みを完全に解析の前に行います。それによって解析関数から副作用を排除します。副作用バリバリなコードよりも動作が把握しやすくなると思います。

そのような前提を元に関数の型を考えます。入力は文字列、出力は解析結果、に加えて解析し残した文字列を返すことにします。

pair<解析結果の型,char*> parse(char *p)
{
  ...
}

大体このような関数を書き並べることになります。返り値は

typedef pair<解析結果,char*> parsed;

などとしておけば(タイピングが)楽です。

例

構文解析の頻出、四則演算を実装してみます。まず、構文を定義します。

Expr = Expr + Term | Expr - Term | Term
Term = Term * Fact | Term / Fact | Fact
Fact = ( Expr ) | number

右再帰を含むので、次のように書き換えます。記法はかなり適当ですが。

Expr = Term { (+|-) Term }
Term = Fact { (*|/) Fact }
Fact = ( Expr ) | number

これをコードに落とします。

typedef pair<int,const char*> parsed;

parsed expr(const char *p);
parsed term(const char *p);
parsed fact(const char *p);

parsed expr(const char *p)
{
  parsed r=term(p);
  while(*r.second=='+'||*r.second=='-'){
    char op=*r.second;
    int tmp=r.first;
    r=term(r.second+1);
    if (op=='+') r.first=tmp+r.first;
    else r.first=tmp-r.first;
  }
  return r;
}

parsed term(const char *p)
{
  parsed r=fact(p);
  while(*r.second=='*'||*r.second=='/'){
    char op=*r.second;
    int tmp=r.first;
    r=fact(r.second+1);
    if (op=='*') r.first=tmp*r.first;
    else r.first=tmp/r.first;
  }
  return r;
}

parsed fact(const char *p)
{
  if (isdigit(*p)){
    int t=*(p++)-'0';
    while(isdigit(*p)) t=t*10+*(p++)-'0';
    return parsed(t,p);
  }
  else if (*p=='('){
    parsed r=expr(p+1);
    if (*r.second!=')') exit(0); // invalid input
    return parsed(r.first,r.second+1);
  }
  else
    exit(0); // invalid input
}

とにかく高速に書くことを目指しているので、字句解析や、構文解析木の作成などは行わず、全部パーズ中に行っています。これに入出力部分をつけるとひとまず完成です。たとえば、一ラインごとに式が入っているような入力だと、

int main()
{
  string str;
  while(cin>>str)
    cout<<expr(str.c_str()).first<<endl;
  return 0;
}

これでOKです。ちなみに、上のコード、char*にconst付け忘れた以外は間違わなかったです。はい。

エラー処理、空白の読み飛ばしなど、後は必要に応じて追加、個々の問題に対して解析関数を適当に作れば大丈夫。 10分で作れるか??

10分で書ける、お手軽パーザー

目次

方法

LL構文解析

☆落とし穴

実装

例