ACM-ICPC

パーサー


まさか国内予選にパーサーの問題が出るとは予想外デース。もうそんな時代になったんですね。
ここは筆者の専門分野なんで、説明にも力が入ってしまいます。が、できるだけわかりやすく説明するように努めます。

構文解析

例えば次の数式を見てください。

5+7*4-6*2/3

これを、

のように解析します。これを構文解析(パース)といいます。パーサーとは、構文解析をするプログラムのことです。
式と書いてあるところは本当は加減式とするのが正しいのだと思いますが、省略します。

ここでは、このような式を計算するプログラムを作ってみましょう。

終端記号と非終端記号

5(数)や*(演算子)のように、これ以上分割されない記号を終端記号、乗除式や式のように分解されるものを非終端記号といいます。

BNF

BNFとは、文脈自由文法を定義するためのメタ言語と呼ばれるものです。ふーん、と。
例えばこんなの。

式 := 乗除式 | 乗除式 + 式 | 乗除式 − 式
乗除式 := 数 | 数 * 乗除式 | 数 / 乗除式
数 := 0 | 1 | 2 | ・・・ | 9

:=は(トンボみたいw)、左辺の非終端記号が右辺のように展開されますよ、ということ。|は選択で、左辺か右辺のどっちかですよ、ということ。

・・・はい、ゴメンナサイ、ウソつきました。これだと、10-2+5が(10-(2+5))になってしまいますね。
正しくはこうです。けっこうめんどい。

式 := 乗除式 | 式 式片
式片 := + 乗除式 | − 乗除式
乗除式  := 数 | 乗除式 乗除式片
乗除式片 := * 数 | / 数
数 := 0 | 1 | 2 | ・・・ | 9


スタック

一応、スタックについて復習を。
スタックは後入れ先出し(Last In First Out)のデータ構造で、取り出すときは最後に入れたものを取り出す、というものでした。

例えば、空のスタックに10,20,30の順にpushすると、
|10 20 30
となります。(|はスタックの底を表すものとします。)

ここで1回popすると、30を取り出して、
|10 20
となります。

さらに40をpushすると
|10 20 40
となります。

一応プログラムを書いておきますが、C++やJavaにはスタックを使うためのしくみが用意されているようです。なので、C言語の人向け。
#define StackSize 10000
int stack[StackSize], sp;

void init(void)
{
  sp = 0;
}
void push(int x)
{
  stack[sp++] = x;
}
int pop(void)
{
  return stack[--sp];
}
spはスタックポインタで、これからpushでデータを入れる場所を指しています。

より安全に書くとこうでしょうか。
void error(char *msg)
{
  fprintf(stderr, "error: %s\n", *msg);
  exit(1);
}
void push(int x)
{
  if(sp >= StackSize)
    error("stack is full.");
  stack[sp++] = x;
}
int pop(void)
{
  if(sp == 0)
    error("stack is empty.");
  return stack[--sp];
}


再帰下降法

非終端記号に該当する再帰関数を1つずつ用意します。が、式片とか作るのめんどいんで繰り返しで。
入力は標準入力とし、最後の文字のあとに改行マーク(\n)が来るものとします。
int ch;

void num(void)
{
  push(ch - '0');
  ch = getchar();
}
void mult_exp(void)
{
  int x, y;
  num();
  while(1) {
    if(ch == '*') {
      ch = getchar();
      num();
      push(pop() * pop());
    }
    else if(ch == '/') {
      ch = getchar();
      num();
      y = pop();
      x = pop();
      push(x / y);
    }
    else
      break;
  }
}
void expression(void)
{
  int x, y;
  num();
  while(1) {
    if(ch == '+') {
      ch = getchar();
      mult_exp();
      push(pop() + pop());
    }
    else if(ch == '-') {
      ch = getchar();
      mult_exp();
      y = pop();
      x = pop();
      push(x - y);
    }
    else
      break;
  }
}
int main(void)
{
  init();
  ch = getchar();
  expression();

  printf("answer: %d\n", pop());
}

なぜ、push(pop()*pop())としているのにpush(pop()/pop())としていないか(できないか)わかりますか?

実行例

1+2*3

で実行してみます。

まず式の解析。最初に数の解析で1をpushします。
|1
次の文字が+なのでその次の2を読み込んで乗除式の解析に入ります。
最初に数の解析で2をpush。
|1 2
次の文字が*なのでその次の3を読み込んで数の解析で3をpush。
|1 2 3
2回popしてその積をpushするので、
|1 6
こうなります。同様に和を計算すると、
|7
こうなり、mainに戻って答えを取り出すというわけです。

このプログラムでは、
1+*2
のような文法ミスは考慮していません。
また、ゼロ除算も気にしていません。