トップ言語処理入門 > 構文解析

構文解析

コンパイル過程上の第2のフェーズである構文解析について説明する。 構文解析の方法は、大きくは下向き(top-down)解析法と上向き(bottom-up)解析法に分類される。

1.再帰的下向き構文解析

下向き(top-down)構文解析法は構文解析木の根から始めて下に向かう。 構文規則に素直に対応した解析法である。

再帰的下向き解析法(再帰降下法)は、構文規則上の各非終端記号について、 ひとつずつ再帰的な処理を対応させ、この手続きの集まりによって構文解析を行う。 解析プログラムは構文規則を書き下したものとなる。

演算子が*と+の構文規則は下(構文規則 A)のように表した場合、 それ自身を再び左から使って定義されている(左再帰的)。 これをそのままプログラム化すると、解析が無限ループに陥る。

構文規則 A.
  <式> ::= <式> + <項> | <項>
  <項> ::= <項> * <変数> | <変数>

次のような等価な構文規則に置き換えることにより、 無限ループの問題が回避できる。 ここで、{ X } は X が 0 個以上並んだものを表す。

構文規則 B.
  <式>   ::= <項>{ + <項> }     ・・・ (1)
  <項>   ::= <変数> { * <変数> }      ・・・ (2)
  <変数> ::= a | b | c                  ・・・ (3)

ここでは、参考までに構文規則 A. を示した。 規則 A. から規則 B. に変換するのではなく、最初から、規則 B. を考える方がいい。

例えば、 B * C + D / Eの場合、*、/ が +、- より優先順位が高いから B*C および D/E をひと塊として、 (B*C) + (D/E) のように捉える。 トップダウン的には <式> ::= <項> + <項> となる。

*、/ はあったとしても、+、− がないようなケースは <式> ::= <項> と書く。

+が二つの場合、<式> ::= <項> + <項> + <項> となる。

+の数は0個以上任意の数になるため、規則 B. の (1) のように書く。

構文規則は演算子の優先順位が低い順に書く。 このことから (2) は簡単に理解できる。+と*は共に2項演算のために、全く同じ形となる。

*よりも更に優先順位が高い <変数> は二項演算ではないため、書き方は変わる。


a + b * c の解析過程を説明する。 上の構文規則は演算子 * は演算子 + よりも優先順位が高いことを表している。

  1. 先頭トークン a の処理:<式>の手続きから始まる。 直ちに<項>の手続きに移り、 <項>では直ちに<変数>の手続きに移り、ここで、トークン a が合致する。 呼ばれた処理が終わり、<変数>の手続きに戻る。 次のトークンは*ではないので、<項>の手続きも終わり、 最初の<式>の手続きに戻る。
  2. トークン+の処理:<式>の処理が <項> + まで進む。
  3. トークンbの処理:<項>→<変数>→bと進む。
  4. トークン*の処理:<変数>に戻った段階で、次のトークンが*であるから、 <項>の処理が継続し、<変数> * まで進む。
  5. トークンcの処理:<変数>→cと進む。これでトークンは終わりであるから、 <項>の処理が終了し、呼び出し元の<式>に戻り、構文解析を完了する。

通常のコンパイラでは、この解析過程でツリー構造のデータ(構文解析木) を生成し、構文解析以降のフェーズである意味解析、コード生成で使用する。 プログラミング言語の仕様が限定的な場合、上述の構文解析のフェーズで、 併行して、意味解析、コード生成を行うことができるので、 ツリー構造のデータ生成は必須ではない。

2.上向き構文解析

構文解析木を、末端の葉に対応する入力トークン列から始まって、次々と上向きに 木の根の方に向かって作っていく方法が上向き(bottom-up)構文解析法である。 構文規則で言えば、右辺の記号列を左辺で置き換えながら(還元しながら)、 開始の非終端記号へと向かって処理をしていく。 以下、上向き構文解析法のひとつである演算子順位文法について説明する。

2.1 演算子順位文法

演算子間の関係

・ a = b
右辺で ab が隣り合っているか,または一つの非終端記号を挟む場合
例: <因子> ::= ( <式> ) ・・・  () の優先順位は同じ。 即ち ( = )
・ a < b
a の右隣に非終端記号 A が現れ,A が,最初の終端記号が b である文字列を導出できる
例: <式> ::= <式> + <項>
   <項> ::= <因子> * <項>
この場合 + < *
・ a > b
b の左隣に非終端記号 A が現れ,A が,最後の終端記号が a である文字列を導出できる
例: <因子> ::= ( <式> )
   <式> ::= <式> + <項>
このとき + > )
演算子の関係(まとめ)
・ a = b : A → …ab… または A → …aBb…
・ a < b : B → …aA…という生成規則が存在し,A → b… または A → Cb…
・ a > b : B → …Ab…という生成規則が存在し,A → …a または A → …aC
           ただし,小文字は終端記号,大文字は非終端記号
演算子順位行列
・式を$と$で囲む。$ の順位も必要。
・本来は「数字」「識別子」にも順位は存在
(後で述べるアルゴリズムでは不要)


演算子順位法による構文解析手順
識別子・数値用の stack[0]
演算子用の stack[1]

演算子順位法はシンプルだが、一般的な言語の構文解析には向かない。

LR(left-to-right scanning right most derivation)構文解析法

LR法は入力を左から右へ走査し、最右の規則を導く。 LR構文解析は入力とスタック、構文解析表からなる。

構文解析表の作り方はここでは省略する。 例えば 参考文献[3]に述べられている。

入力は1記号ずつ左から右に読む。スタックには、

 s0 X1 s1 X2 s2 X3 s3.... Xm sm
という記号列を積む。sは状態に対応した記号である。 Xは文法記号で、実際は必要ないが説明のために加えてある。 構文解析表は構文解析動作関数ACTION と行き先関数GOTOの2つの部分からなる。 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

数式の文法

    (1) Expr → Expr '+' Term
    (2) Expr → Term
    (3) Term → Term '*' Factor
    (4) Term → Factor
    (5) Factor → '(' Expr ')'
    (6) Factor → identifier
の構文解析表は次のようになる。 a * b + c とか (2 + 3)*4 はこの文法を満たしている。

SLR(simple LR)法では、文法より、次のような構文解析表を作り、 それを用いたオートマトンで構文解析をする。

 
ACTION GOTO
(非終端記号)
stateid+*()$ETF
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 は状態 i をスタックに積む動作(sfift)を意味する。 また、rj は文法 j によるreduce動作を意味する。ここで、 a*b+c$ を入力として考えてみよ。
  1. まず、はじめの状態は 0 から始まる。
  2. state 0で、id が入力されると s5 となっているので、shift。 入力記号 id と状態 5 をつむ。
  3. 次に * が入力になるが、state 5で、*の欄は、r6 である。 これは文法(6)によるreduce操作である。 スタックの上にある id 5 のペアを取り除き、 最上段が 0 になるので、state 0 と F を GOTO で引き、3となっているため、 F と 3 がスタックに積まれる。
  4. 入力記号はそのままである。state 3において、入力が * であれば、r4 である。 文法規則(4)でのreduceをする。 T となり、state 0 と T で GOTO を引き 2 となるため、T 2を積む。
  5. state 2で、入力が * の時には s7 となる。したがって、*と7をつみ、次の入力に移る。
  6. 以下、省略。

C言語による構文解析プログラムを以下に示す。実行結果を下の右に示す。


スタック 入力
(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 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$
$
$
$
$

( 1) input=id state= 0 action= 5: shift           push( 5)
( 2) input= * state= 5 action=-6: reduce LR[0][8] push( 3)
( 3) input= * state= 3 action=-4: reduce LR[0][7] push( 2)
( 4) input= * state= 2 action= 7: shift           push( 7)
( 5) input=id state= 7 action= 5: shift           push( 5)
( 6) input= + state= 5 action=-6: reduce LR[7][8] push(10)
( 7) input= + state=10 action=-3: reduce LR[0][7] push( 2)
( 8) input= + state= 2 action=-2: reduce LR[0][6] push( 1)
( 9) input= + state= 1 action= 6: shift           push( 6)
(10) input=id state= 6 action= 5: shift           push( 5)
(11) input= $ state= 5 action=-6: reduce LR[6][8] push( 3)
(12) input= $ state= 3 action=-4: reduce LR[6][7] push( 9)
(13) input= $ state= 9 action=-1: reduce LR[0][6] push( 1)
(14) input= $ state= 1 action=9999: 受理!
[slr01.c]
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define  x  9998
#define  A  9999	// 受理

char *token[] = { "id", "+", "*", "(", ")", "$" };

int LR[][] = {
   // 0  1  2  3  4  5   6  7  8
   // id +  *  (  )  $   E  T  F
    { 5, x, x, 4, x, x,  1, 2, 3 },    // 0
    { x, 6, x, x, x, A,  x, x, x },    // 1
    { x,-2, 7, x,-2,-2,  x, x, x },    // 2
    { x,-4,-4, x,-4,-4,  x, x, x },    // 3
    { 5, x, x, 4, x, x,  8, 2, 3 },    // 4
    { x,-6,-6, x,-6,-6,  x, x, x },    // 5
    { 5, x, x, 4, x, x,  x, 9, 3 },    // 6
    { 5, x, x, 4, x, x,  x, x,10 },    // 7
    { x, 6, x, x,11, x,  x, x, x },    // 8
    { x,-1, 7, x,-1,-1,  x, x, x },    // 9
    { x,-3,-3, x,-3,-3,  x, x, x },    // 10
    { x,-5,-5, x,-5,-5,  x, x, x },    // 11
};

int  r2n[]  = { 6, 6, 7, 7, 8, 8 }; // rule番号→LR表の列番号
int  pops[] = { 3, 1, 3, 1, 3, 1 };
int  stack[100];
int  sp = 0;

void push(int s) { stack[sp++] = s; }
int  peek() { return sp > 0 ? stack[sp-1] : x; }
int  pop()  { return sp > 0 ? stack[--sp] : x; }

int tokenNumber(char *str) {
    int n;
    for (n = 1; n < sizeof(token)/sizeof(char*); n++)
        if (strcmp(str, token[n]) == 0) return n;
    return 0;	// identifier or number
}

void main() {
    //char *input[] = { "(", "2", "+", "3", ")", "*", "5", "$" };
    char *input[] = { "a", "*", "b", "+", "c", "$" };
    int  ix, c, n, step, state, action;

    ix = 0;
    c = tokenNumber(input[ix++]);
    push(0);         	// 初期状態をプッシュ
    for (step = 1;;step++) {
        state = peek();
        action = LR[state][c];
        printf("(%2d) input=%2s state=%2d action=%2d: ", step, token[c], state, action);
        if (action == x) {
            exit(1);    // エラー終了
        } else if (action == A) {
            printf("受理!\n");
	    exit(0);
        } else if (action >= 0) {  // shift: 次の状態をスタックに積む
            push(action);
            printf("shift %9s push(%2d)\n", "", action);
            c = tokenNumber(input[ix++]);
        } else {    // action < 0  // reduce: 
            for (n = pops[-action-1]; n-- > 0; ) pop();
            state = LR[peek()][r2n[-action-1]];
            printf("reduce LR[%d][%d] push(%2d)\n", peek(), r2n[-action-1], state);
            push(state);
        }
    }
}

参考文献

[1] 白鳥・高橋・神長:ソフトウェア工学の基礎知識[昭晃堂]
[2] 構文解析の基礎
[3] LR法