next up previous contents index
: 参考文献 : 構文解析 : プログラム minicomp.rr   目次   索引

LR パーサ

前の節で説明した構文解析の方法を再帰降下法とよぶ. この方法は終端記号, 非終端記号に対応した関数を用意したら, あとは 構文図に従いこれらの関数を呼び出していけばよい.

この方法より効率のよい構文解析の方法が LR パーサである. この話題は上級の話題なので再帰降下で十分という方は読み飛ばされたい.

さて, この節ではこの構文解析法の原理を簡略に説明する. 詳しくは, Aho, Ullman の本 コンパイラを御覧いただきたい [1]. LR パーサではつぎのように構文解析する.

  1. 文法 (構文図) から, オートマトンを生成する.
  2. 入力をそのオートマトンで解析する.

SLR (simple LR) 構文解析法の説明を例を用いて説明する. 次の文法(生成規則)に対するSLR パーサを作ろう. この文法は [1] の 例 6.1 でとりあげられている文法である.

\begin{eqnarray*}
(1)\ E &\rightarrow& E + F \\
(2)\ E &\rightarrow& F \\
(3)\...
...\rightarrow& (E) \\
(6)\ T &\rightarrow& id\ \ (identifier) \\
\end{eqnarray*}

これは

\begin{eqnarray*}
E &\rightarrow& E + F \ \vert\ F \\
F &\rightarrow& F * T \ \vert\ T \\
T &\rightarrow& (E) \ \vert\ id \\
\end{eqnarray*}

と書いてもよい.

E は expression, F は factor, T は term の略である. id (identifier) は数である. したがって, $ 2+3*5$ とか $ (2+3)*5 $ とかは この文法をみたしている. なお$ +2 $ は満たしていないことを注意しておく.

SLR 法では文法より次のような構文解析表をつくって それを用いたオートマトンで構文解析をする.

状態 id     +     *     (     )     ; E      T      F     
0 s5     s4     s1 s2 s3
1   s6       OK      
2   r2 s7   r2 r2      
3   r4 f4   r4 r4      
4 s5     s4     s8 s2 s3
5   r6 r6   r6 r6      
6 s5     s4       s9 s3
7 s5     s4         s10
8   s6     s11        
9   r1 s7   r1 r1      
10   r1 s7   r1 r1      
11   r5 r5   r5 r5      

この構文解析表をもちいてどの様に構文解析をやるか 説明しよう. エラーの処理とOK(受理)の処理は省略してある.


driver:= 

00: push(0); (* 状態0をスタックへ積んで置く.*)
01: c = ipop();
02: state = peek();
03: action = actionTable[state,c];
04: If action == 移動(s) then
05:         push(c);
06: push(nextStateTable[state,c]);
07: else (* 還元する. *)
08: rule = nextStateTable(state,c);
09: rule 分 pop() する;
10: ipush(c);
11: ipush( rule の左辺 );
12: endif
14: Goto[1];

各関数の働きはいかのとおり.

  1. stack - スタック.
  2. push(c) - スタック(stack)にc を積む.
  3. pop() - スタックからデータをえる.
  4. peek() - スタックのデータを得る, がスタックからとりだしはしない.
  5. inputStack - 入力データが入っているスタック.
  6. ipush(c) - c を入力スタック(inputStack)へ積む.
  7. nextStateTable - 構文解析表. 移動のときは1から11を戻す. 還元のときは文法規則の番号を戻す.
  8. actionTable - 構文解析表.移動(s), 還元(r), 受理(OK), 駄目のどれ を戻す.

03: を終了した時点での各変数の様子を次の入力データ 2+3*5; に対して見てみよう.


    c     state action stack, inputStack 

$I_0$ s { $I_0$ } , { +,3,*,5,; }
+ $I_5$ r { $I_0, id, I_5$ }, { 3,*,5,; }
F $I_0$ s { $I_0$ }, { +,3,*,4,; }

次にどの様にして文法より構文解析表を作るのか説明しよう. 状態の集合, nextStateTable および Following[非終端記号]の 三つのデータを計算すれば構文解析表ができる.

まず, 状態の集合の計算法を示そう. 生成規則の右辺に $\cdot$ を含む生成規則を項 (item) とよぶ. たとえば生成規則

\begin{displaymath}E \rightarrow E + F \end{displaymath}

からは

\begin{displaymath}E \rightarrow \cdot E + F,\
E \rightarrow E \cdot + F
\end{displaymath}


\begin{displaymath}E \rightarrow E + \cdot F,\
E \rightarrow E + F \cdot
\end{displaymath}

の四つの項ができる. 直感的には生成規則のどこまでをすでに読み込んだのかを項は示している.

$I$ を項とする. Closure(I) とは$I$を含む項の集合であり, 次の性質を満たすものとする.

\begin{displaymath}A \rightarrow \alpha \cdot B \beta \in {\tt Closere(I)} \end{displaymath}

かつ $ B \rightarrow \gamma $ なる生成規則があれば,

\begin{displaymath}B \rightarrow \cdot \gamma \in {\tt Closure(I)} \end{displaymath}

である.

たとえば $E' \rightarrow \cdot E$ の Closure を計算すると

\begin{eqnarray*}
E' \rightarrow \cdot E \\
E &\rightarrow& \cdot E + F \\
E &...
...T \\
T &\rightarrow& \cdot (E) \\
T &\rightarrow& \cdot id \\
\end{eqnarray*}

となる. これが上の構文解析表の状態0 ($I_0$) に対応する. 次に id が読まれたとすると状態は

\begin{displaymath}T \rightarrow id \cdot \end{displaymath}

となるはずである. $\cdot$ の後ろになにもないのでこの状態の Closure はこの ままである. この状態の集合は5 ($I_5$) に対応する. この状態では Follow(F)に属する終端記号が次に待っていれば $ F \rightarrow id$ の還元をおこなう. 以下, 省略.

状態 $I_k$ が項

\begin{displaymath}A \rightarrow \alpha \cdot \beta \gamma \end{displaymath}

を含むとする. nextStateTable[ $I_k$, $\beta$]

\begin{displaymath}{\tt Closure}( A \rightarrow \alpha \beta \cdot \gamma ) \end{displaymath}

である.

例として, nextStateTable[ $I_0$, $($ ] を計算してみよう.

\begin{displaymath}T \rightarrow \cdot (E) \ \in I_0 \end{displaymath}

だから

\begin{displaymath}T \rightarrow ( \cdot E ) \end{displaymath}

の Closure が求めるものである. Closure は

\begin{eqnarray*}
T &\rightarrow& (\cdot E ) \\
E &\rightarrow& \cdot E + F \\ ...
...T \\
T &\rightarrow& \cdot (E) \\
T &\rightarrow& \cdot id \\
\end{eqnarray*}

である. この状態を $I_4$ となずける.

状態 $I_k$

\begin{displaymath}A \rightarrow \alpha \cdot \end{displaymath}

を含むとする. 次の入力記号が Follow(A) ならルール

\begin{displaymath}A \rightarrow \alpha \end{displaymath}

で還元(r) する.

状態 $I_k$

\begin{displaymath}E' \rightarrow E \cdot \end{displaymath}

を含むとする. 次の入力記号が ; (終わりマーク) ならば 受理(OK).

問題 17.1        次の生成規則に対する構文解析表を作れ.

\begin{eqnarray*}
E &\rightarrow& E+F\ \vert\ F \\
F &\rightarrow& (E)\ \vert\ id \\
\end{eqnarray*}


next up previous contents index
: 参考文献 : 構文解析 : プログラム minicomp.rr   目次   索引
Nobuki Takayama 平成15年9月12日