構文解析の基礎

top-down parserとbottom-up parser

これまで、式のインタプリターでは構文解析にtopdown parserを使って解説し た。top down parserは再帰的下方構文解析の代表的な手法であり、次に何が 来るのかを推定しながら構文解析を進めていく方法である。比較的構成がわか りやすく、人手で書いていく場合などには適した方法とされている。

このほかにも構文解析には、 上方構文解析法 （bottom-up parser、上昇型ともいう） という方法がある。この方法は人手で直接実現するには向かない方法で あるが、理論的に構成されており、構文解析のプログラムを自動的に生成する ためには重要な方法になっている。今回は、この下向き構文解析法についてみ ていく。

簡単に説明するためにいつもの式の構文解析を考えてみる。文法は以下のもの を考える。F,T,Eは非終端記号であり、idは変数のようなシンボルを仮定する。 

(1) E := E + T 
(2) E := T
(3) T := T * F
(4) T := F
(5) F := ( E )
(6) F := id

上向き構文解析と還元

構文解析の重要な役割は、入力がこの文法にあっているかどうかを認識するこ とである。下方構文解析では、まず、Ｅであることを仮定して解析をはじめ、 それぞれの非終端記号に対応する関数を呼び出し、最終的に必要な終端記号列 になっているかを認識する方法であった。つまり、構文木という観点からみれ ば、構文木の根から葉に向かって解析を進めていく。（ここで、この文法は左 再帰で書いてあるため、そのままではtop-down parserができないことは以前 に説明したとおり）

これに対し、上方構文解析では葉すなわち終端記号から、根すなわち非終端記 号へ向かって文法を適用して、最終的にＥになっているかを認識する。例えば, a+c*dを考えてみる。これをtokenの列にしてみると、 

 id + id*id
さらに、(6)の文法を適用して、 
F+F*F　
(3)(4)の文法を適用して 
F+T*F  ⇒　T + T*F  ⇒　T + T
さらに、(1)(2) を適用して 
E + T ⇒　E
となって、認識される。 この適用して、非終端記号に置き換えていくことを 還元(reduction) と呼ぶ。 上方構文解析で、構文木を構成する過程は、文字列を 非終端記号に還元していく過程である。この例では、順番を考えずにできると ころから還元していったが、これをするためには入力を全部みてからやること になるため、あまり現実的ではない。

上向き構文解析では、入力を左から右に見ながら（つまり、一文字づつ入力し ながら）還元していく。入力の右側から適用できる構文規則を逆順にたどって 最終的に最後の構文規則まで還元できる部分列をhandle(把手)という。上方構 文解析はhandleを見つけて還元する過程とみなすことができる。

　　　　
右文形式　 handle 還元につかった規則
a + b * c a (6) (4) (2)
E + b * c b (6) (4)
E + T * c c (6)
E + T * F T*F (3)
E + T E+T (1)
　E --- ---

このような構文解析を（自動的に）構成するために、現在の構文解析の状態 を記憶するためのスタックと入力の動作として以下のものを考える。

  1. 移動(shift)：次の入力記号をスタックの上段に移動する。
  2. 還元(reduce)：handleの右の記号がスタックの一番上にあり、適用できる構文規則をみつけて、その非終端記号に置き換える。
  3. 受理(accept)：構文解析が終了
  4. エラー：適用できる構文規則がみつからず、誤りを発見。
これを図示すると以下のようになる。
スタックの状態 入力 動作
$
$a
$E
$E +
$E + b
$E + T
$E + T*
$E + T*c
$E + T*F
$E + T
$E 		a + b * c $
+ b * c $
+ b * c $
b * c $
* c $
* c $
c $
$
$
$
$ 		shift
(6)(4)(2)によるreduce
shift
shift
(6)(4)によるreduce
shift
shift
(6)によるreduce
(3)によるreduce
(1)によるreduce
accept

演算子順位構文解析法

さて、上方構文解析のためのアルゴリズムについて、考えていくことにしよう。 演算子順位構文解析法は、演算子順位文法(operator precedence grammar)に 対する簡単な上方構文解析法である。演算子文法とは、どの構文生成規則の右 辺も空ではなく、しかも、隣接する２つの非終端記号を持たないという文法で ある。つまり、算術式E := E + Tのように、必ず非終端記号の間には演算子 （終端記号）が入るものである。演算子順位文法とは、終端記号について、優 先度> < =が定義されている文法のことである。

  1. A:= ...st...または、A:= ...sBt..なる構文規則があれば、s=t
  2. A:= ...sB...なる構文規則があり、さらにB⇒tまたはB⇒Ctなる規則が導 かられるならば、s < t
  3. A:= ...Bt...なる構文規則があり、さらにB⇒...sまたはB⇒...sCなる規 則が導かれるならば、s > t

例についていえば括弧( 、 )に関しては=、E:= E+TとT:=T*Fにより、+<*である。 つまり、数式の直感的な優先度に対応している文法とおもえばよい。２，３の 規則は構文規則で、構文木を作ったとき下流にある演算子が強いことを示す。 このような関係にしたがって、構文規則より、演算子順位行列を作ることがで きる。

+ * ( ) id
+ ><<><
* >><><
( <<<= <
) >> > 
id >> > 

これを使って、以下のアルゴリズムをつかえばよい。

  1. スタックに空記号$をつんでおく
  2. 入力記号aをよむ
  3. スタック上の演算子sに対し、s > aであるかぎリ、還元する
  4. そうでなければ、aをスタック上につみ、２へ
  5. 全部認識されたら終わり。
最後のreductionのために、便宜的に優先度が一番低い最後の記号を導入する 必要がある。また、１項演算子を扱う場合には工夫が必要となる。

ＬＲ構文解析法

演算子文法に関しては比較的簡単なアルゴリズムで構成することができたが、 一般の文法には使えない。ここで説明する方法は入力を左から右へ走査し、最 右の規則を導くので、 LR(left-to-right scanning right most derivation)構文解析法 と呼ばれるものである。

LR構文解析は入力とスタック、構文解析表からなる。入力は１記号ずつ左から 右に読む。スタックには、 

　s0 X1 s1 X2 s2 X3 s3.... Xm sm
という記号列を積む。ｓは状態に対応した記号である。Ｘは文法記号で、実際 は必要ないが説明のために加えてある。構文解析表は構文解析動作関数ACTION と行き先関数GOTOの２つの部分からなる。LR構文解析のプログラムは現在のス タックの最上段の状態smと入力記号aiをもちいて、ACTION[sm, ai]を引いて、 以下の動作のどれかをとる。
  1. shift s: 入力記号aiとGOTO[sm,ai]で求めた次の状態sをスタックに積む。 次の入力に進む。
  2. reduce A := b: 文法規則A:=bで還元する。すなわち、最上段にあるXの 列がbであるはずなので、これに対応するXsのペアをスタックから取り除き、 最後の状態smとAで、GOTO[sm,A]=sを次の状態とし、Asをスタックに積む。還 元の動作は現在の入力記号は変わらない。
  3. accept
  4. error
例に挙げた数式の文法について番号をつける。 構文解析表は次のようになる。
 
ACTION GOTO
(非終端記号)
state  id    +     *     (     )     $    E T F
0s5    s4    123
1  s6      acc   
2  r2s7  r2r2   
3  r4r4  r4r4   
4s5    s4   823
5  r6r6  r6r6   
6s5    s4    93
7s5    s4     10
8 s6    s11    
9 r1s7  r1r1   
10 r3r3  r3r3   
11 r5r5  r5r5   
ここで、siはshiftで状態iをスタックに積む動 作を意味する。また、rjは文法jによるreduce動作を意味する。ここで、 a*b+c$を入力として考えてみよ。
  1. まず、はじめの状態は０から始まる。
  2. state 0で、idが入力されるとs5となっているので、shift。入力記号id と状態５をつむ。
  3. 次に*が入力になるが、state 5で、*の欄は、r6である。これは文法（６） によるreduce操作である。スタックの上にあるid 5のペアを取り除き、最上段 が0になるので、state０とＦをGOTOで引き、3となっているため、Ｆと３がス タックに積まれる。
  4. 入力記号はそのままである。state3において、入力が*であれば、r4であ る。文法規則(4)でのreduceをする。Tとなり、state 0とＴでGOTOを引き2とな るため、T 2を積む。
  5. state 2で、入力が*の時にはs7となる。したがって、*と７をつみ、次の入力に移る。
  6. 以下、省略。
スタック 入力 
(1)
(2)
(3)
(4)
(5)
(6)
(7)
(8)
(9)
(10)
(11)
(12)
(13)
(14)

0
0 id 5
0 F 3
0 T 2
0 T 2 * 7
0 T 2 * 7 id 5
0 T 2 * 7 id F 10
0 T 2 
0 E 1
0 E 1 + 6
0 E 1 + 6 id 5
0 E 1 + 6 F 3
0 E 1 + 6 T 9
0 E 1

id*id+id $
*id+id$
*id+id$
*id+id$
id+id$
+id$
+id$
+id$
+id$
id$
$
$
$
$
このような表を作ることによって、ＬＲ構文解析ができる。この表の作りかたについてはこの講義では説明しないが、重要な点は字句解析のところでオートマトンから字句解析を自動的に生成できると同様に、この表を自動的に作る方法があり、構文解析ルーチンを自動的に生成できることである。

構文解析生成プログラムyacc

LR構文解析ルーチンを自動生成するプログラムの一つがyaccである。実際、 構文解析ルーチンはtop-down parserで書くことがあるが、複雑になると手に 負えなくなるため、yaccのような自動生成プログラムを使う。（linuxのフリー な構文解析は実際bisonというプログラムであるが、yaccというコマンドになっ ている）実際の場面ではyaccの使い方を習得しておくことが重要になる。

yaccは、LR構文解析に一文字の先読み機能を付け加えたLALR(Look-ahead　 LR)という文法のクラスを扱うことができる。yaccの入力（文法の定義）は、 例として以下のように書く。 


%token NUM　/* yylexから返すtokenの定義、文字を直接返してもよい*/
%token SYM
%token STRING
%{
#include 　/*Ｃのプログラムのヘッダー、なんでもかける*/
%}
%start expression /* yyparseで何の認識をするかの指定*/
%% /* 文法の定義の始まり*/
expression: term
        | expression '+' term
        ;
term: factor
        | term '*' factor
        ;
factor: NUM | SYM ; 
%% /* 文法の定義の終わり*/

#include "lex.c" /* ここからは何のＣのプログラムをかいてもいい*/
tokenで定義されているものは、defineされるので、lex.cのなかでそのまま使 うことができる。lex.cでは、これまででやった字句解析のルーチンが定義す る。構文解析から呼び出される字句解析のルーチンは、yylexという名前で定 義しなくてはならない。これは、lexを使っても生成できる。

このプログラムをexpression.yとすると、 

% yacc expression.y
で、構文解析プログラムがy.tab.cという名前で生成される。このプログラム には、構文解析ルーチンyyparseが含まれており、、mainプログラムを以下の ようにして、リンクすればよい。 
main()
{
     yyparse();　
     printf("ok\n");
}

void yyerror()
{　
     printf("syntax error!\n"); 
     exit(1); 
}
yyerrorは構文解析でエラーになったときに呼び出される関数で、ユーザが与える。