第 12 回構文解析木(2)

本日の内容

12-1. 構文解析
12-2. 木の探索と表示

このドキュメントは http://edu.net.c.dendai.ac.jp/ 上で公開されています。

12-1. 構文解析

今回はコンパイラコンパイラなしで、文法からそれを解釈するプログラムを作る手法を学びます。なお、構文解析のことをparse、構文解析をするプログラムなどを parserといいます。

素朴な解析法

バッカス・ナウア記法の素朴な解析法として次のようなものがあります。例えば、 A→bCD で A,C,D が非終端記号、 b が終端記号だった時、関数 A を次のように作ります。


void A(){
   記号 b を読む;
   C();
   D();
}

そして非終端記号 C, D に対しても同様に関数を作ります。このようにすると構文木通りに関数が呼び出されて、与えられた記号列を処理できる場合があります。しかし、実際は一つの非終端記号から複数の導出規則が存在します。例えば、下の例では状態 S で文字 a を読み込んだ時、 A か B のどちらを導出するかはすぐには決められません。

S→A|B
A→ab
B→ac

素朴な方法としては、適当に導出規則を選び、途中で失敗したら別の導出規則を選ぶ方法が考えられます。これをバックトラックと言います。確かにこの方法でも構文解析できますが、しかし、キューを実装しているように、途中の入力を全て覚える必要があります。また、考え得る全ての構文木を一つ一つ生成しては比較するようなものなので、効率が悪いです。

例12-1


#include <stdio.h>
#define SIZE 100
int queue[SIZE];
int r=0,g=0;
int getletter(void){
  if(r==g){
    queue[(g=(g+1)% SIZE)]=getchar();
  }
  r=(r+1)% SIZE;
  return queue[r];
}
ungetletter(int c){
  queue[r]=c;
  r=(r+SIZE -1)%SIZE;
}
int S(void){
  if(A() || B()){ /* A がだめなら B */
   return 1;
  }else{
    return 0;
  }
}
int A(void){
  int c1,c2;
  c1=getletter();
  if(c1!='a'){
    ungetletter(c1);
    return 0;
  }
  c2=getletter();
  if(c2!='b'){
    ungetletter(c2);
    ungetletter(c1);
    return 0; /* A が適合しないなら読んだ文字をすべて返す */
  }
  return 1;
}
int B(void){
  int c1,c2;
  c1=getletter();
  if(c1!='a'){
    ungetletter(c1);
    return 0;
  }
  c2=getletter();
  if(c2!='c'){
    ungetletter(c2);
    ungetletter(c1);
    return 0;
  }
  return 1;
}
int main(void){
  if(S()){
    printf("Ok\n");
  }else{
    printf("NG\n");
  }
  return 0;
}

バックトラックを避け、効率良く構文解析するためにはどのようなことが考えられるでしょうか? 一つの考え方として、次に読み込む記号から必ず導出規則が一つ決定できるような文法であれば、文字を読み込みながら if 文でどちらの導出規則を選択できるため、バックトラックを行わずに済みます。そのような、どんな非終端記号に対しても、次の先頭の文字を読むだけで一意に導出が可能な文法を LL(1)文法と言います。

左再帰性の除去

さてここでは前回取り上げた足し算の文法を取り上げ、コンパイラコンパイラ無しで、文法をプログラムで表現する手法を考えます。まず、前回の足し算の文法は以下の通りです。

文法 G₁

=({和},{数, +}, P₁, 和)

\begin{matrix} 和 \to 和 + 数 \\ 和 \to 数 \end{matrix}

この文法はそのままでは上で述べたように、文字を読んでも次の導出規則を決めることはできません。入力列に対して $和 \to 和 + 数$ というルールを適応するには、その先頭部分が「和」の形になっているかどうかを調べる必要があります。そして、そのためにはその先頭部分が「和」の形になっているかどうかを調べる必要があります。このように左辺と同じ非終端記号が右辺の先頭に来ていると、入力列を順に読む構文解析ができなくなります。これを左再帰性と言います。この左再帰性は次のようにすれば除去できます。次のような左再帰性を持つ生成規則があったとします。

A \to A α | β

A は非終端記号で、α と β は非終端記号、終端記号からなる列を表し、β は A で始まらないとします。この時、次のように書き直すと左再帰性がなくなります。

\begin{matrix} A \to β A' \\ A' \to α A' | ε \end{matrix}

上の足し算を解釈する文法G₁の左再帰性を除去すると次のようになります。

文法 G₂

=({和, 和'},{数, +}, P₂, 和)

\begin{matrix} 和 \to 数 和' \\ 和' \to + 数 和' | ε \end{matrix}

コンピュータで扱う時、数式の最後を明白にする記号として = を最後に入力するというルールを追加します。このルールを含めた文法 G₁, G₂ をそれぞれ G₁', G₂' とします。

文法 G₁'

=({和, 始},{数, +, =}, P₁', 始)

\begin{matrix} 始 \to 和 = \\ 和 \to 和 + 数 \\ 和 \to 数 \end{matrix}

文法 G₂'

=({和, 和'},{数, +, =}, P₂', 和)

\begin{matrix} 和 \to 数 和' = \\ 和' \to + 数 和' | ε \end{matrix}

再帰的下向き構文解析法

文法に対して、左辺から右辺への導出が、次の一文字を読むだけで決定できれば、その文法をLL(1) 文法と言います。次の一文字を読むだけで決定できるかどうかは次の計算を行うことで判定できます。なお次の一文字を読んでプログラムの次の動きを決めますので、入力文字が終ったことを示す特殊な文字を考えることがあります。

LL(1)文法は次のように形式化できます。 α は非終端記号、終端記号からなる列とします。また A は非終端記号とします。この時 First(α), Follow(A), Director(A,α) を次のように定義します。

First(α):: 導出ルールの右辺 α に対して、 α から導出可能な列の先頭になりうる終端記号の集合。もし、α から ε へ導出可能なら、ε も含めます。
Follow(A):: 非終端記号 A に対して、開始記号から導出をした時に、 A の直後になりうる終端記号の集合。
Director(A,α):: 各導出規則 A → α に対して、 Director(A,α) = First(α) 但し、 α から ε へ導出可能ならFollow(A) も含めます。

文法 G₂'についてこれらを計算すると次のようになります。

\begin{matrix} First (数 和' =) = \{数\} \\ First (+ 数 和') = \{+\} \\ Follow (和) = \{ε\} \\ Follow (和') = \{=\} \\ Director (和, 数 和' =) = \{数\} \\ Director (和', + 数 和') = \{+\} \\ Director (和', ε) = \{=\} \end{matrix}

このように各非終端記号に対して、その生成規則を示す Director 同士に共通部分がない文法を LL(1) 文法と言います。 G₂ は計算した Director に共通部分がないので LL(1) 文法です。

なお G₁' についても同様に計算すると次のようになります。

\begin{matrix} First (和 =) = \{数\} \\ First (和 + 数) = \{数\} \\ First (数) = \{数\} \\ Follow (始) = \{ε\} \\ Follow (和) = \{=\} \\ Director (始, 和 =) = \{数\} \\ Director (和, 数) = \{数\} \\ Director (和, 和 + 数) = \{数\} \end{matrix}

このように非終端記号和に対して、 Director(和, ・) に重複がありますので、 LL(1)文法ではありません。

LL(1) 文法は、先に示した素朴な関数呼出による構文解析に対して、次に来るものを判断して構文規則を変えることで構文解析ができるようになります。

各非終端記号に対応した関数を作ります。ここでは A とし、作る関数を A() とします。

Director(A,・)に応じてプログラムを書きます。 Director(A, α)={x}, Director(A, β)={y} の時、次のようになります。


#define Ok (1)
#define NG (0)
int A(void){
  if(文字 =='x'){
     if(αの処理){
       return Ok;
     }
  }else if(文字=='y'){
     if(βの処理){
       return Ok;
     }
  }
  return NG;
}

上の G₂ も同様に Director により次のように計算できます(わかりやすいように日本語を使ってますので、このままでは動きません)。


int 和(void){
   if(次==数){
      次を読む;
      if(和'()){
        return Ok;
      }
   }
   return NG;
}
int 和'(void){
   if(次=='='){ /* Director(和',ε) */
     return Ok;
   }else if(次=='+'){ /* Director(和',+数和') */
     次を読む;
     if(次==数){
       次を読む;
       if(和'()){
         return Ok;
       }
     }
   }
   return NG;
}  
int main(void){
  次を読む;
  if(和()){
    return Ok;
  }
  return NG;
}

なお Pascal というプログラミング言語は LL(1) 言語です。したがって、 LL(1) は制限がきついですが、そこそこ実用的な文法まで表現できます。

トークンの切り出し

例12-1 では getletter という関数を用意して、文字を読むことを考えました。今回のプログラムの前回までのプログラムは構造が異なっています。以下に構造を抽象的に示します。

前回までのプログラム


int main(void){
  前処理;
  while(文字を読みつづける){
    文字列の組み立て処理;
    文字列が完成したら出力;
  }
  後処理;
  return 0;
}

今回のプログラム


int 非終端記号1(void){
   文字列を読み込む;
   文字列に応じて他の非終端記号を呼び出す;
   return 1;
}
int 非終端記号2(void){
   文字列を読み込む;
   文字列に応じて他の非終端記号を呼び出す;
   return 1;
}
...
int main(void){
   開始記号を呼び出す;
   return 0;
}

プログラムの基本的なテクニックとして、入力、出力、処理を分割すると言う考え方があります。前回までの主プログラムに入力のループがあり、出力工程で作業を行うというのは、確かにプログラミングの定石の一つではありますが、今回のように関数的な処理を付加することができません。以前、オートマトンも主プログラムのループ内で処理してましたが、これを改め、呼び出すと字句が得られる関数を作ると便利です。字句を取り出す関数を getword と呼ぶことにします。これは Java の正規表現の group メソッドのような働きをするものです。また、さらに今回は、「演算子」「数字」など複数の種類の字句を一つの getword で取り出す必要があります。つまり、getword の返すものは字句の種類と、実際の字句を示す文字列であるとします。

字句の定義はそれぞれの種類で別々にオートマトンで定義できれば、開始状態からε遷移により分岐すれば一つにまとめられます。これで最長一致により入力から字句を取り出すことを考えます。このとき、主プログラム中の入力ループによる字句の取り出しとは違い、次のふたつの問題があります。

字句の終端をどう判定するか？
ファイルの終端の処理をどうするか？

字句の終端の判定は、基本的には字句に含まれない文字を読み込んだ時になります。ここで、関数としては値を返して処理を主プログラムに戻すことになるのですが、問題は「字句に含まれない文字」の取扱いです。この文字は次の字句に含まれる可能性があります。したがって、関数が終了しても、次に関数が呼び出されたときに処理できるよう、関数自体がオブジェクトのように記憶領域を持ちその文字から処理を開始できるようにします。なお、この考え方は、入力がキューである場合は、関数が記憶領域を持たなくても、読み過ぎた入力を元に戻すという操作で実現できます。

次にファイルの終端の処理です。ファイルの終端を検出した場合、入力処理は終了ですが、そこで字句の検出も終了し、関数としては返すべき値があることも考えられます。つまり、ファイルの終端に達しても、関数は字句を戻すことがありえます。この場合も、関数がファイルの終端を記憶しながら、字句を返し、次の呼出で、字句を返せないことを示せばよいです。

このように、字句解析では、最長一致をするために、字句に含まれない次の文字を読んだ後、次の呼出でもう一度読み出す必要があります。 C++ や Java のようなオブジェクト指向言語であればオブジェクトを作ることで、容易に実現できます。一方、 C 言語では、グローバル変数を使う他に、そのために用意されている static キーワードを使うこともできます。次のようにすると、（外部からアクセスできない）ローカル変数でありながら、プログラムの実行中は値を保持しつづけます。


#include <stdio.h>
int count(void){
  static int c=0;
  return c++;
}
int main(void){
  int i;
  for(i=0;i<10;i++){
    printf("%d\n",count());
  }
  return 0;
}

構文解析の意味付け

構文解析の手続きにおいて、出力を考えます。これは構文に意味を与えることになります。

ここでは、数式から構文解析木を作り、実際に数式の値を計算することを考えます。始めに G₁ を考えます。各ルールで、次のように木が作られます。

ルール	機械的な構文解析木	数式の構造
$和 \to 和 + 数$
$和 \to 数$

和の部分を考えると、導出により木の下の方に移動していくので、上から下へ木を作っていく一方 G₂ は次のように木が作られます。

ルール	機械的な構文解析木	数式の構造
$和 \to 数和'$
$和' \to + 数和'$
$和' \to ε$	そのまま

G₂は左側に終端記号が来ます。文字列は左から読むのでこれはどんどん木に対して終端記号を対応づけていくことになります。つまり G₂では、下から上へ木を作ることになります。これを上に示したプログラムを利用して、次のように生成させるます。


typedef struct tr {
  char *item ;
  struct tr *left,*right;
} TREE;
TREE *root=NULL;
#define Ok (1)
#define NG (0)
int 和(void){
  if(次==数){   
    数を読み込む;
     if((root=(TREE *)malloc(sizeof(TREE)))==NULL){
       return NG;
     }
     root->item=数;
     root->left=NULL;
     root->right=NULL;
     if(和'()){
       return Ok;
     }
  }
  return NG;
}
int 和'(void){
   TREE *op,*num;
   if(次=='='){ /* Director(和',ε) */
     return Ok;
   }else if(次=='+'){ /* Director(和',+数和') */
     op=(TREE *)malloc(sizeof(TREE));
     op->item="+";
     op->left=root;
     次を読む;
     if(次==数){
      if((num=(TREE *)malloc(sizeof(TREE)))==NULL){
        return NG;
      }
      num->item=数;
      num->left=NULL;
      num->right=NULL;
      op->right=num;
      root=op;
      if(和'()){
        return Ok;
      }
    }
  }
  return NG;
}  
int main(void){
  次を読む;
  if(和()){
    return Ok;
  }
  return NG;
}

12-2. 木の探索と表示

木の内部を検索、表示する際に、順序を複数決めることができます。以前は「木の左側を処理」、「注目頂点を表示」、「木の右側を処理」と、もっとも深い頂点から順に表示される表示法を紹介しました。これを深さ優先探索と言います。一方、同じ深さごとに探索、表示することもあります。これを幅優先探索と言います。

また、深さ優先探索に関しても「木の左側を処理」、「注目頂点を表示」、「木の右側を処理」の他にも、これらの出力の順番を変える方法が考えられます。ここで、例えば、次のような構文解析木が得られたとします。

その時「木の左側を処理」、「注目頂点を表示」、「木の右側を処理」とすれば中置記法の表示と一致します。一方「木の左側を処理」、「木の右側を処理」、「注目頂点を表示」とすると後置記法(逆ポーランド記法)と一致します。

演習12-1

以上の議論により、数式(足し算のみ)を逆ポーランド記法に変換するプログラムを作りなさい。

完全な数式処理

ここまでは足し算のみの数式を使って、文法、構文解析、構文解析による計算の手法を紹介しました。ここでは、完全な数式の文法を与えます。

まず、かけ算を考えます。かけ算だけの式の場合は計算の順序などは足し算と同様です。したがって、かけ算だけのルールを考えると次のようになります。

\begin{matrix} 積 \to 積 * 数 \\ 積 \to 数 \end{matrix}

ここで、積と和の優先順位を考えます。積の方が優先されますので、積を計算した後、和を計算します。これを実現させるには、和の計算で「数」という終端記号を計算の対象にしましたが、積を計算の対象に変更します。変更した後のルールは次のようになります。

\begin{matrix} 和 \to 和 + 積 \\ 和 \to 積 \\ 積 \to 積 * 数 \\ 積 \to 数 \end{matrix}

さらに括弧の処理を考えます。括弧の中にはどんな式も入ります。一方括弧はその中の値を計算したら、計算の対象となる値として数と同じように扱われます。今まで「数」という終端記号を使ってきましたが、ここで「値」という非終端記号を導入します。すると、値に関するルールは次のようになります。

\begin{matrix} 値 \to (和) \\ 値 \to 数 \end{matrix}

これらをすべてまとめると完全な数式処理の文法 G₃を定義できます。

文法 G₃

=({和, 積, 値},{数, +, *, (, )}, P₃, 和)

\begin{matrix} 和 \to 和 + 積 \\ 和 \to 積 \\ 積 \to 積 * 値 \\ 積 \to 値 \\ 値 \to (和) \\ 値 \to 数 \end{matrix}

拡張バッカス・ナウア記法

拡張バッカス・ナウア記法は、バッカス・ナウア記法に中括弧による繰返しの記法を付け加えたものです。また、丸括弧の中に | を使うことで、括弧内を選択できます。例えば、拡張バッカス・ナウア記法を使うと、上の足し算は「+ 数」を任意の回数繰返したものとして次のように書くことができます。

和 \to 数 {+ 数}

演習12-2

次の数式に対するG₃の構文解析木を書きなさい。

1 + 2 + 3
1 * 2 + 3
1 + 2 * 3
(1 + 2) * 3
1 * (2 + 3)

演習12-3

G₃ を拡張バッカス・ナウア記法で書きなさい

演習12-4

G₃ の左再帰性を取り除いた文法 G₄ を求めなさい。

演習12-5

G₄ の各導出規則に対して Director を求め、 LL(1)文法であることを確かめなさい。

演習12-6

中置記法で書かれた数式を逆ポーランド記法に変換するプログラムを書きなさい。

演習12-7

数式を計算するプログラムを書きなさい。

坂本直志 <sakamoto@c.dendai.ac.jp>
東京電機大学工学部情報通信工学科

第 12 回 構文解析木(2)