数理解析研究所講究録1093 巻 1999 年 230-235

230

LC 文法とその構文解析法の拡張について
椎名$\Gamma \text{ム光^{}\uparrow}$,$\text{増山繁}\ddagger$\dag er 岡山理科大学〒 700-0005 岡山県岡山市理大町 1-J\d ag er 豊橋技術科学大学〒 441-8580 愛知県豊橋市天伯町雲雀

1.

はじめに

2

計算可能な–般の句構造言語を構文解析する
文法の構造上,場合,複数個の文法記号を親に持つ生成規則を含むため, 親が 1 っに限られない形態の構文解析木を持つ.

更に, 構文解析の実行構文解析木の候補者や複数の構文解析木生成も考慮しながら計算しなければならない.
そのため, 予測した構文解析木が誤っている場合
は, 訂正のためにバックトラック処理が必要になり, 解析時間が増大する. –方, 自然言語処理な$\gamma$

丘 1-1

準備

本章では, 準備として, LC 文法の定義, 及び,LC 構文解析法について, 簡単に述べる. なお,本論文における LC 文法の定義は,文献 [8] に準拠する.

においては,どにおいては, 文脈自由言語だけではなく,それより広いクラスに属する言語を処理する必要がある.

自然言語の文法は,しかしながら,部分的に文脈自由文法や句構造文法の生成規則が含まれほとんどの生成規則が文脈自由てはいるものの,文法の形式をしている. そのため, 構文解析時に最悪のケースのみに対応していると処理時間が遅そこで本研究では,コンパイラなどで利用されている構文解析法の中でも上昇型と下降型を組み合わせた混合型に分類される LC 構文解析法 [8]を拡張する. それによって, 予測した構文解析木を作成しないで処理する解析方法と LC 文法 [8] で生成される言語よりも広いクラスの言語を生成する文法を提案する.
なお, 文脈自由文法 $G=(N, T, P, s)$ , $N$ : 非終端記号の集合,: 終端記号の集合, $P$ : 生成規,則の集合,: 開始記号と入力文字列$T$

最左導出の過程で得られる文法記号列である左, $w\in T^{*}$ , $A\in N$ , $\delta\in(T\cup N)^{*}$ ,文形式
が, 生成規則の矢印の右側の先の最左位置の$wA\delta$$A$頭の文字でない時,左四でない非終端記号 $A$ という. 左隅出現でない左文形式 wA\mbox{\boldmath $\delta$}の非終端記号$A$ をと表す.
1憶$wA\delta$

$S$

2.2

LC 文法 [8]次の条件を満たす文脈自由文法 $G$ を $LC(k)$ 文法という. 左隅出現でない任意の非終端記号 ,と長さ k の先読み文字列 に対して,が高々 1 個存在
常に以下のような生成規則$a_{n}\in T$を与える.

また構文解析実行の便宜上, 入力文字列の最後に終りを示す特殊記
号$ $(\not\in N\cup T)$ を用意する.

$u$$S\Leftrightarrow \mathrm{c}wA\delta$$Barrow\alpha$

し,かつ,1(i)$A$$\alpha$4\rightarrow B\mbox{\boldmath $\gamma$}で次のいずれかが成り立つ.
$=$$C\beta,$$FIRS\tau_{k}(\beta\gamma\delta)$$FIRS\tau_{k}(\delta)$

2.

$C$

$\in$

$N$

, なら,

$C\in N$ ,なら,$FIRS\tau_{k}(\alpha\gamma\delta)$$w_{n}\in T$

は

$u$

は

$u$

はの要素でない.

\alpha が非終端記号で始まらないなら,ここで,$u$の要素である.

$C=A,$(ii) さらに,

$a_{1}a_{2}\ldots a_{n}$$S$$\ldots,$

左隅出現でない非終端記号$A$

くなってしまう.

$a_{1},$ $a_{2},$2.1の要素である.

$w\mathrm{g}_{\Rightarrow}$とするとき,$w_{1}w_{2}\ldots w_{n}$,$w_{1},$ $w_{2},$定義する.
$FIRST_{k}(w)=\{$$\ldots$,$FIRS\tau_{k}(w)$ は次のように$w_{1}w_{2}\ldots w_{k}$$w_{1}w_{2}\ldots w_{n}$, if $n\geq k$ ,, if $n<k$ .

231

23

LC 構文解析法 [8]LC 構文解析は, 上昇型と下降型を組み合わせた混合型に分類される構文解析法である. その解析の実行においては, 木の第 1 部分木は下から上, 第 2 部分木から最右部分木まではそれぞれ上$\sim$から下への走査を, 再帰的に行ないながら構文解析木を決定する (図 1). 以下に, LC 構文解析の動作を示す.

1. T が葉のみの場合,
・訪問 (根 $(T)$ )..
.
.

図 2: LC 構文解析の例

2. T が葉のみでない場合,$\bullet$

LC 走査 (第 1 部分木 (I));

3

訪問 (根 $(T)$ );
出力 (根 $(T)$ );LC 走査 (第 2 部分木 (I));

LC 構文解析の拡張 (ELC 構文解析)
文脈自由言語以下のクラスの言語の場合,

生

成規則の矢印の左側が複数の文字列である生成規則\alpha \rightarrow \beta \in $P$ , $|\alpha|>1$ , $|\beta|>0$ の適用を含まないため, 構文解析木の兄弟は同じ入力文字を子供とすることはない. そのため, それぞれの文LC 走査 (最右部分木 (I)).

法記号から生成される部分文字列は文法の構造から決定できる.

方, 文脈自由言語より大きいクラスの言語に対する構文解析木には,矢印の左側が複数文字列である生成規則の適用がされ, 構文解析木中に図3 に示すような交差をもつ (図 3, $ABarrow CDE$ ).
そのため,構文解析木の兄弟が同じ入力文字の先祖となる場合が存在する.
例えば, 図 3 の C から生成される部分文字列と D から生成される部分文宇列とは重複する部分

図 1: LC 走査があり,$C$

よって,

例えば,

$LC(1)$ 文法の例 $G=(N, T, P, S)$ ,$N=\{S, A, B\}$ ,$T=\{a, b, c\},$の先祖である.

を決定した時点で $D$ を決定するた

めにの先頭に引き戻す処理方法や $E$ を決定した
後 $D$ と $C$ を決定する処理方法 [10] をとらなければ$P=\{Sarrow AC$ ,この時,$C$$a$$D$ならない.

$Carrow CB,$ $Carrow B,$ $Aarrow a,$ $Barrow b,$ $Barrow c\}$ に対して入力文字列を I=ab 赫とする.と D は入力文字

これらのいずれの処理方法もバックトラック$LC$

構文解析は,(1) $Aarrow a,$ (2) $Sarrow AC,$ (3) $Barrow b$ ,(4) $Carrow B,$ (5) $Barrow b,$ (6) $Carrow CB,$ (7) $Carrow CB$ ,(8) $Barrow b$ の順に生成規則を当てはめて構文解析木を作成する (図 2). 特に, (2) の S\rightarrow AC の後に (3) の $Barrow b$ を当てはめるのが LC 構文解析の本研究では先読み文字列の定義を拡張し, 更部分文字列の有効範囲を定義することによって, 構文解析の左隅を決定するだけで生成規則が決定できる拡張 LC 構文解析 (以下 ELC 構文解析)特徴である.

および $ELC(k)$ 文法を提案する.の回数が多い.

そこでバックトラックを避けるた

め,に,

2

232

また,

$0$

$\dot{A}\Rightarrow.\dot{\gamma}$,回以上の展開の繰り返しをと表す.

$\gamma\in(^{\tau\cup}N)^{*}$

すべての展開に対して,$A$

文形式中の文法記号から最左導出によって展開し,$A$から生成された文字列の直後の k 個の文字列を $FIRST_{k}’$ で定義する.

$FIRST_{k()}\prime$\alpha_{2}=$A,$

図 3: 構文解析木の交差$\{head_{k()}\gamma_{2}|\gamma_{1},\dot{\beta}\gamma_{1}s\mathrm{a}\mathrm{e}\alpha_{1},\alpha 2,\beta\in(\tau\cup\cdot N\gamma\in\tau\gamma_{2}2\alpha_{1}\lrcorner\dot{4}*\alpha 2\Rightarrow)^{*}\}$

3.1

文法定義の準備

先に,32$ELC(k)$ 文法を定義するのに必要な用語を第 311 節と第 312 節で定義する.

3.1.1

文法の定義

$E^{\neg}LC(k)$$ELC(k)$ 文法は生成規則の矢印の右側の始めの文字 (木の左隅) が決定されると, その生成規則が最左導出適用される文法である.

文形式中任意の非終端記号 $A\in N$ ,の最も左側に位置する非終端記号を書き換える導さ k の先読み $u\in T^{*}$ に対して,

文脈自由文法における最左導出は,出であったが,本稿では,規則\alpha 1\rightarrow \alpha 2’

非終端記号の代わりに1 個存在し,書き換えられる文法記号列に変更する. そして,この最左導出の過程で得られる文法記号列であるの左隅出現でない左文形式 wA\mbox{\boldmath $\delta$}の左文形式$S\neq_{\mathrm{C}}\text{ }$$(\gamma\in(T\cup N)^{*})$$A\preceq\Rightarrow\alpha_{1}\gamma$と長以下のような生成$(\alpha_{1}\alpha_{2}\in(T\cup.N)^{*})$

かつ$wA\delta$,が常に高々,で次のいずれかが成り立つ.

,$wA\delta$

非終端記号 $A$ を$S*_{\mathrm{c}}\text{冷}$$wA\delta$

1. (i)と表す.

$u$

3.1.2

$\alpha_{2}=C\beta,$$\beta\in(T\cup N)^{*}$

なら,は $FIRsT_{k}^{J}(C, \beta\gamma\delta)$ の要素である.

(ii) さらに,生成される文字列の範囲$C\in N$ ,$C=A,$$C\in N$ ,

なら,

$u$

は

$u$

は

$FIRST_{k}’(A, \delta)$ の要素でない.

非終端記号 $A$ から生成される文字列を定義す

2.

文脈自由文法では生成規則の矢印の左側は 1る.

つの文法記号であるので,$A$から生成される文字列は文形式の $A$ の両側の文字に影響されない.
かし,し生成する言語が文脈自由文法より広いクラ号.

$\Rightarrow$.の$A$( $FIRST_{k}$ は,22 の定義参照).
$Aarrow a$ の

3. は構文解析において, 終端記号の取り扱い手順を簡単にするための制約であり,$ELC(k)$ 文法から生成される言語の大きさに関して本質的な制約ではない.

次のように表す.

.

$.3$\cdot$$\cdot$$\alpha_{1}\beta_{1}\dot{A}\beta_{2}\alpha 2\Rightarrow$$\alpha_{1}\dot{\beta}_{3}\dot{B}\dot{c}\dot{D}\dot{\beta}4\alpha 2$$\beta_{1}A\beta_{2}arrow\beta_{3}BCD\beta 4\in P$$\alpha_{1},$の要素である

ただし,に関する展開を調べたい時は, 記を用いて,$FIRST_{k}(\alpha\gamma\delta)$

形式だけである.

文形式の両側の文字に影響される. そこで, 始めに非終端記号の上にをつけて, 元々始めにのついていた非終端記号から展開された文字列を明らかにする. 例えば,
$a_{1}\beta_{1}\lrcorner\dot{4}\beta_{2}\alpha_{2}$が非終端記号で始まらないなら,3. 終端記号を生成規則中に持つのは,スに属する場合は生成規則の左側に複数の文字列がくる可能性があるので,$\alpha_{2}$,,$\alpha_{2},\beta_{1},\beta 2,\beta_{3},\beta_{4}\in(T\cup N)^{*}$

解析表 $ELC$

構文解析を進めていく上で, 次に適用する生成規則を決定するのに,.

3

先頭記号と現在処理してい233

4る文法記号と先読み文字列の 3 つの引数が必要と$ELC(k)$ 構文解析の手順なる.

それを表の形でまとめたのが解析表 $ELC$である. 解析表 ELC は次の手順で作成する.

LC 構文解析器は,テープ), 左隅文字を積むスタックと解析が終了した位置を表すために生成規則にをつけた項 (以下,[解析表 ELC の作成]

(i)C\beta の場合,$\alpha_{2}=$の要素で$wA\delta$,$A\Rightarrow$”“$\alpha_{1}arrow\alpha_{2}$とする場合,要素で,.

$LC(A, a, u):=$$wA\delta$,“力として用いる.

その終端記号を入力テープの代わりとなる入力スタックと左隅文そのため,ancestor-stack, closure-stack) から構成される. 以
下にそれぞれのデータ構造を定義する. なお, $LC$
項は,, $\alpha_{3}\in(T\cup N)^{*}$ で定義され, LC 項の集合をとする.とする.

$[\alpha_{1}arrow\alpha_{2}\cdot\alpha_{3}],$(iii)$\alpha_{2}$の先頭が終端記号で,とする場合,$\mathrm{F}\mathrm{c}wA\delta$,$u$

その終端記号をは $FIRS\tau_{k}(\delta)$ の要素で,$A\Rightarrow\alpha_{1}\gamma$

なら,$a$$B,$$C,$$D\},$$\alpha_{2}$$S$

1. inputstack は, 入力堅字列及び生成規則の左$LC(A, a, u)$ を側の文字列を積むスタック.

文法 $G=\{N, T, P, s\}$ ,$T=\{a, b, c\}$ ,input-stack $=(T\cup N)\cross(T\cup N)\mathrm{x}\cdots\cross(T\mathrm{U}$$N=\{S,$ $A$ ,$N)$$P=\{Sarrow ASCD$ ,$ELC(1)$ 文法である.

.

2. ancestor-stack は,$Sarrow ABD,$ $DCarrow CD,$ $BCarrow BB,$ $Aarrow a$ ,$Barrow b,$ $Darrow c\}$ は,$\alpha_{1}$$I_{LC}$

未定義とする.
例えば,

ELC 構文解析器は,字と LC 項を積む 3 種類のスタック (input-stack,

A\Rightarrow \alpha l\mbox{\boldmath $\gamma$}なら,”$\alpha_{1}arrow\alpha_{2}$

本稿で示す ELC 構文解析では,生成した生成規則の矢印の左側の文字列を再び入[は $FIRsT_{k}^{J}(A, \beta\gamma\delta)$ の$u$$S\mathrm{F}_{\mathrm{c}}$それに対して,$\beta\gamma\delta$とする.

(ii) \alpha 2 の先頭が終端記号で,$a$

LC 鳴を積むスタックの 3 種類から構成される.

)\alpha 1\mbox{\boldmath $\gam a$}ならは $FIRST_{k(}\prime c,$$u$$S\mathrm{F}_{\mathrm{c}}$$LC(A, c_{u},):=$

入力文字列をテープ (入力左隅と予測される文法記号を積むスタック. ancestorstack $=N\cross N\cross$

この...

文法に対する解析表 $ELC$ を表 1 に示す.

$\cross N$.

3. closure-stack は, LC 項を積むスタック.
closure-stack.

表 1: 解析表 ELC の例$=I_{LC}\cross I_{LC}\cross\ldots\cross I_{LC}$“$ELC(S, A, a)=$ $Sarrow ASCD$“$ELC(s, A, b)=$$Sarrow ABD$

$ELC(S, a, b)=u_{A}arrow a$$ELC(s, a, a)=$“$ELC(s, b, b)=$“$ELC(B, b, b)=$“$ELC(B, b, c)=$“””$Barrow b$$Barrow b$”

Step 2(終端記号処理):$\mathrm{i}\mathrm{n}\mathrm{p}\mathrm{U}\mathrm{t}s\mathrm{t}\mathrm{a}\mathrm{C}\mathrm{k}$”先読みが $a_{i+1}\ldots ai+k+1$ ’“$BCarrow BB$$ELC(D, C, c)=$“$DCarrow CD$“

Step 1(初期設定): ancestor-stack に開始記号 $S$を積む.

”$ELC(B, B, b)=$$ELC(D, c, c)=$

次に構文解析の手順を示す.

”$Aarrow a$$Barrow b$”$Darrow c$の先頭が$a_{i}$,ancestor-stack の”

先頭を $H$ とする.
”

Step 2.1: もし $ELC(H,a_{i}, ai+1\cdots ai+k+1)$=“A\rightarrow aI’ なら,”

$ELC(D, C,$ =“D\rightarrow c’’

Step 21.1: inputstack から$a_{i}$を降ろす.

Step 212: “A\rightarrow ai’’ を出力する.
Step 21.3:$A$を input stack に積む.

Step 3(非終端記号処理): input-stack の先頭を
非終端記号 , 先読みを $ai+1\cdots ai+k+1$ ’an$A$

cestor-stack の先頭を $H$ とする.

4

234

Step 31(LC 項処理):
もし closure-stack の先頭が$[\alpha_{1}arrow\alpha_{2}\cdot AB\alpha \mathrm{a}]$なら,Step 311: closure-stack の先頭$[\alpha_{1}arrow\alpha_{2}\cdot AB\alpha_{3}]$を$[\alpha_{1}arrow\alpha_{2}A\cdot B\alpha_{3}]$に入れ換える.

Step 3.1 .2: ancestor-stack に $B$ を積む.
Step 3.1.3: input-stack から

Step3.2(生成規則出力):
もし closure-stack の先頭が$A$を降ろす.

$[\alpha]arrow\alpha_{2}\cdot A]$

なら,Step 3.2.1:$\alpha_{1}arrow\alpha_{2}A$を出力する.

Step 3.2.2: closure-stack の先頭を降ろす.

図 4: 入力 $I=$ aabbcc に対する構文解析木$[\alpha_{1}arrow\alpha_{2}\cdot A]$

6

Step 3.2.3: inputstack から $A$ を降ろし,の逆順で積む.

本研究では, 構文解析木の文法記号が支配する$\alpha_{1}$Step 3.2.4: ancestorBtack から先頭の $H$ を1 っ降ろす.

は,“\alpha 1\rightarrow A\alpha 2’’ なら,$\}_{\llcorner}^{}[\alpha_{1}arrow A\cdot\alpha_{2}]$Step 34(エラー処理): それ以外はエラーを出力して終了する.

Step 4(終了処理):
Step 2 から Step 3 を繰り返す. input-stackの内容が S$,tack が空であるなら,$\mathrm{c}1_{0}\mathrm{s}\mathrm{u}\mathrm{r}\mathrm{e}-S$accept”を出力して終了する.

ELC 構文解析の動作例

5

入力を $I=aabbcC$ とした時の構文解析の動作を表 2 に,み文字列の定義を拡張した.

法に拡張し, また $ELC(k)$ 文法を提案した.

Step 3.3.2: ancestor-stack に\alpha 2 の先頭の文字を積む.

“先読LC 構

それにより,スに属する言語も構文解析ができる ELC 構文解析

もし $ELC(H, A, a_{i+1}ai+2\cdots ai+k+1)$

Step 3.3.1: closurestackを積む.

文字列の記号の範囲を定義することにより,文解析法を文脈自由言語のクラスより大きいクラStep 3.3(LC 項の新規追加):
$=$

むすび

また作成される構文解析木を図 4 に示す.

5

今後

$ELC(k)$ 文法の性質を調査する予定である.

235

参考文献
, Generalized $LR$ parsing,[7] M. Tomita
Kluwer Academic Publisher, 1991.

[1] S. Y. Kuroda, Classes of languages andlinear-bounded automata. Inform. Control,
7, pp207-223, 1967.

$\mathrm{e}\mathrm{d}$[8] 徳田雄洋, 言語の構文解析, 共立出版, 1995.

[2] J. Earley, An efficient context-free parsing
algorithm, Commun. ACM, 13, 2, pp94-102,[9] K. Sikkel, Parsing Schemata, Springer,

1997.

1970.

[10] H. Shiina and S. Masuyama, Proposal of theunrestricted $LR(k)$ grammar and its parser,
Mathematica Japonica, 46, 1, pp129-142,[3] J. Loeckx, The parsing for general phrasestructure grammars, Inform. Control, 16,
pp443-464, 1970.

1997.

[4] G. Sh. Vold’man, A parsing algorithm forcontext-sensiteve grammars, Program. Comput. Software, 7, pp302-307, 1981.
[5]. Harris, $SLR(l)$ and LALR $(l)$ parsing
for unrestricted grammar, Acta Inform., 24,
pp191-209, 1987.
$\mathrm{L}.\mathrm{A}$An Efficient Augmented
Context-Free Parsing Algorithm, Computational Linguistics, 13,1-2, pp31-46, 1987.

[6] M. Tomita,-6