LR(1)パーサジェネレータを自作して構文解析をする 第4回:かんたんLR(1)法入門

Category: dev

Tag: parsing parser generator parser lexer

前回で構文解析器を生成する際に必要となる準備を済ませたため、LR(1)法ベースのパーサジェネレータを作る用意が整いました。 ですが相変わらず本題のパーサジェネレータ作成には入らず、まずはLR(1)法のおおまかな理論的概略の紹介を行います。

第1回では構文解析全体の流れを解説しましたが、実際にどのような過程でパーサを、またパーサジェネレータを作成するかについては触れませんでした。 今回は、LR法による構文解析の流れを解説するとともに、これからどのような流れでパーサジェネレータを作成していくのかを紹介します。 今回は解説のみのためソースコードが載りません。

LR(1)構文解析の流れ

FOLLOW関数はSLR法などで使用する概念のため、LR(1)法を用いる今回の記事では用いません。忘れてください。

LR構文解析の流れは、以下の通りとなります。

  1. First関数を求める
  2. アイテム集合およびDFA(gotoグラフ)を作成する
  3. (LALR法のみ)DFAの先読み部分をマージし、より状態数が少なく軽量なDFAにする
  4. DFAをもとに構文解析表(LR表)を構築する
  5. 構文解析表を実行できるパーサを作成する

1.のFirst関数については、前回の記事で紹介を済ませているため割愛します。
LALR法のLR(1)法との相違点は3.のみで、他はLR(1)法と全く同じ処理を行います。

パーサジェネレータを作成して解析する構文を自由に決定できるようにする場合、4.の構文解析表までを与えられた構文に合わせて自動的に生成できるようにします。

アイテム集合とDFA

LR法による構文解析のためには、DFA(決定性有限オートマトン)の作成を行う必要があります。

LR法によって作られるDFAは、それぞれの状態(ノード)に、アイテム集合と呼ばれる情報と、他の状態への遷移ルールを示すトークンをラベルとした辺情報とを持ちます。 このLRアイテム集合は、構文解析表やDFA自身の構築のために必要な情報として使用されます。

アイテム集合は、文字通りアイテム(便宜的にLRアイテムと呼称します)からなる集合です。

LRアイテム

個別のLRアイテムは、以下のようなものです。

X -> A . B C [x,y,$]
Xは非終端記号
A,B,Cは終端記号または非終端記号
x,yは終端記号

一見するとX -> A B Cのような構文規則のルールのように見えますが、相違点があります。

まず、規則の右辺に.という記号が存在します。 これは終端記号でも非終端記号でもなく、「現在この部分まで解析した」ということを示すマーカーです。 上記の場合、Xという記号の解析の途中で既にAを読み終え、次はB Cが与えられることが期待されているということを意味します。

次に、規則の右辺のさらに右に、[x,y,$]という表記が存在します。 これはLR(1)法の(1)先読みのために用いる先読み記号の集合を表しています。 解析が進んでXの解析が終わった場合、つまり.の位置が右端まで移動した場合、その次にはx,y,$のいずれかの記号が来ることを意味します。 先読み記号は常に終端記号であることに注意してください。 また、$は「入力の終わり」を表す記号で、これは便宜的に終端記号として扱います(第2回で内部的に追加したSymbol(EOF)トークンのことです)。

DFAの構築

まず、DFAを最初の状態で初期化します。 このとき、DFAのノード数は一つのみであり、そのノードは、以下のようなLRアイテム一つのみを要素とするアイテム集合を持ちます。

S' -> . S [$]

ただし、Sは開始記号であり、S'は便宜的に追加した新しい非終端記号です。 便宜的には、S'について以下の規則が成り立つこととみなします。

S' -> S $

これを自己展開させることによって、構文解析のためのDFAを構築していきます。

クロージャー展開

まず、初期化時点で存在するこのDFAノードは、まだ完全な状態にはなっていません。 一定のルールに従い、アイテム集合を「クロージャー展開」する必要があります。

X -> α . Y β [x]
X,Yは非終端記号(X=Yであってもよい)
xは終端記号
α,βは任意の長さの終端記号または非終端記号の列

というLRアイテムが存在する場合、Yを左辺として.が右辺の左端にあるような新しいLRアイテムを、アイテムセットに追加します。 ただし、先読み記号はFirst(βx)で得られる記号全てとします。 つまり、

Y -> γ
γは任意の長さの終端記号または非終端記号の列

というような規則があった場合、

Y -> . γ [First(βx)]

というLRアイテムを新しく追加します。

これを、新しいアイテムが追加されなくなるまで繰り返します。

具体的に見て行きましょう。 以下の規則を仮定します。

S -> 0
S -> X 1
X -> 0
Sは開始記号
S,Xは非終端記号
0,1は終端記号

この場合、開始記号はSなので、最初のLRアイテムは以下のようになります。

S' -> . S [$]

.の次にあるSを展開します。 先読み記号はFirst($)=[$]です。 以下のアイテムを追加します。

S -> . 0 [$]
S -> . X 1 [$]

さらに、新しく追加されたアイテムにも同様の処理を行うと、.の次にXがあるため、これを展開します。 0は終端記号のため、展開は行いません。 先読み記号は、First(1$)=[1]です(First関数は終端記号の列の左端の記号を得るので、ここでは1のみとなります)。

X -> . 0 [1]

上の規則では0は終端記号のため、ここで展開は終了します。

結果として、最初のDFAノードの持つアイテム集合は以下のようになります。

S' -> . S [$]
S -> . 0 [$]
S -> . X 1 [$]
X -> . 0 [1]

以上がクロージャー展開の処理です。 こうして展開したアイテム集合をもとに、新しいDFAノードを生成していきます。

新しいDFAノードの生成

クロージャー展開が完了したアイテム集合から、一定のルールのもとで新しいDFAノードを生成します。

X -> α . A β [x]
Xは非終端記号
Aは終端記号または非終端記号(X=Aであってもよい)
xは終端記号
α,βは任意の長さの終端記号または非終端記号の列

というLRアイテムが存在する場合、以下の新しいLRアイテムを生成します(そのDFAノードのアイテムセットには追加しません)。

X -> α A . β [x]

そのDFAノードの持つ全てのLRアイテムについてこの処理が終わったら、.の左隣の記号、つまりAの位置の記号ごとに新しいアイテム集合を作り、それを情報としてもつ新しいDFAノードを生成します。 そして既存のDFAノードから、Aをラベルとして新しいノードに対して辺を張ります。

具体的には、

S' -> . S [$]
S -> . 0 [$]
S -> . X 1 [$]
X -> . 0 [1]

というアイテム集合を持つDFAからは、

S' -> S . [$]
S -> 0 . [$]
S -> X . 1 [$]
X -> 0 . [1]

という4つのLRアイテムが生成され、これは以下の3つに分けられます。

1. ラベル: S
S' -> S . [$]

2. ラベル: 0
S -> 0 . [$]
X -> 0 . [1]

3. ラベル: X
S -> X . 1 [$]

このようにして新しく3つのDFAノードを生成し、もとのノードからそれぞれの記号をラベルとした辺を張ります。 あとは、新しいノード全てについて、同様にクロージャー展開を行い、さらに新しいDFAノードを生成していきます。 ただし、その過程で既存のノードと全く同じアイテム集合を持つDFAノードが作られた場合は、新しいノードとしてそこに辺を張るのではなく、かわりに重複する既存のノードに対して辺を張るものとします。

この処理を繰り返し、DFAノードが新しく生成されなくなればDFAの構築は終了です。

(LALR法のみ)先読み部分のマージ

LALR法では、この時点でDFAのサイズ縮小を行います。 そのアルゴリズムは、以下の通りです。

まず、DFAの持つアイテム集合から、それぞれのLRアイテムの先読み部分のみを除いた場合に、全く同じアイテム集合を持つようなDFAノードの組を見つけます。 そして、そのようなDFAノードの組において、LRアイテムの先読み部分をそれぞれの和集合とするような新しいDFAノードを作り、それらのノードに対して辺を張っていたノードがあれば、その辺を新しいノードに対して張り直します。

具体的に、以下のようなアイテム集合を持つ2つのDFAノードを考えます。

DFAノードA:
X -> .Y Z [x]
Y -> .V W [x,y]

DFAノードB:
X -> .Y Z [z]
Y -> .V W [y,z]

この2つのDFAノードは、先読み部分を除けば一致しているため、マージして次のDFAノードCを作ります。

DFAノードC:
X -> .Y Z [x,z]
Y -> .V W [x,y,z]

そして、DFAノードAまたはBに対して辺を張っているDFAノードが存在するならば、それらの辺をDFAノードCに向けたものに書き換えます。

構文解析表と構文解析器

DFAが完成したら、それをもとにして構文解析表を生成していきます。 構文解析表はそれ自体がステートマシンの動作仕様を表すものであり、構文解析表が完成してしまえば、それに沿ってステートマシンを動作させることで構文解析が可能となります。

構文解析を行うステートマシン

構文解析表には、ステートマシンの現在の状態、および次の入力に応じて、4種類の命令のいずれかが記述されます。 構文解析を行うステートマシンは、現在の状態を示すスタックと、構文解析の結果を保持するスタックの2つのスタックを持ちます。 また、入力を一文字だけ確認するか、入力を消費して一文字先に進めることができます。 (この仕様自体は変更の余地があります。)

ステートマシンは、構文解析表から(状態スタックの一番上にある状態, 現在見ている入力)の命令を実行します。 最初は(初期状態, 一文字目の入力)となります。

以下に、4つのそれぞれの命令の説明を記します。 とはいえ、ステートマシンの仕様なんざ読んでいて動きが分かるわけもなく楽しくも何ともないため、参考資料のLR parsingのスライドを確認していただくことをおすすめします。 ステートマシンの動きを視覚的に追いかけることができて非常にわかりやすいです。

shift命令

shift命令を受けると、ステートマシンは入力を一つ消費します。 shift命令には状態番号が付与されているので、ステートマシンは状態スタックにその数値を追加します。

reduce命令

reduce命令は文法idが付与されています。 ステートマシンがreduce命令を受けると、示された文法規則を確認し、その右辺の記号の数だけ状態スタックからポップして取り除きます。 さらに、結果スタックからも右辺の記号の数だけ取り除き、取り除いた結果すべてを現在見ている規則の左辺の記号を親とする木構造の子にして、そうしてできた木を結果スタックに追加します(または、取り除いた結果および文法idを引数として何らかのプログラムを実行し、その結果をスタックに追加する場合もあります)。

そしてその処理の終了後、構文解析表の(状態スタックの一番上にある状態、規則の左辺の記号)の位置にあるgoto命令を実行させます。

goto命令

goto命令は、reduce命令の直後に実行されることが期待されます。 goto命令には状態番号が付与されているので、ステートマシンは状態スタックにその数値を追加します。 shift命令と異なり、入力の消費は行いません。

accept命令

ステートマシンがaccept命令を受けると、それは構文解析が終了したことを意味します。 理想的な入力が与えられた場合、入力は全て消費され、結果スタックには最終的な構文解析結果のみが入っていることが期待されます。

構文解析器

構文解析器は、上記の仕様をなぞって構文解析表を読み取ることのできるステートマシンそのものです。 よって、構文解析表さえ個々の構文にあわせて生成することができれば、それを構文解析器に与えることによってさまざまな構文の解析が可能になります。

構文解析表の構築

完成したDFAをもとにして、構文解析表を生成することができます。

shiftおよびgotoオペレーションの登録

それぞれのDFAノードは、ステートマシンの状態と対応しています。 簡単のため、個々のDFAノードには一意なid(ステートマシンの状態番号)が割り振られているものとします。 すべてのDFAノードについて、そのノードから張られている辺を参照します。

その辺のラベルの記号が終端記号であるならば、構文解析表の(そのDFAノードのid, ラベルの記号)の部分にshift命令を書き込み、その辺の向かう対象となるDFAノードのidを付与します。

その辺のラベルの記号が非終端記号であるならば、同様にしてgoto命令を書き込みます。

acceptおよびreduceオペレーションの登録

すべてのDFAノードについて、そのアイテム集合の持つLRアイテム一つ一つを確認していきます。 もしも.の位置が右辺の末尾にある場合、そのLRアイテムの持つ先読み記号それぞれについて、以下の処理を行います。

構文解析表の(そのDFAノードのid, 先読み記号)の部分にreduce命令を書き込み、そのLRアイテムのもととなっている規則のidを付与。

ただし、その規則がS'に対応するものであった場合、かわりにaccept命令を書き込みます。

shift/reduceコンフリクト

shiftオペレーションおよびreduceオペレーションは、表の同じ位置に競合して書き込まれてしまうことがあります。 このような状況を、shift/reduceコンフリクトと呼びます。 なお、shift/reduceコンフリクトだけでなく、reduce/reduceコンフリクト、複数回競合しあった3つ以上の命令のコンフリクト等も発生する可能性があります(shift/shiftコンフリクトも発生する可能性があると聞きましたが、上記のアルゴリズムでshiftを登録している場合はDFAが壊れていない限り発生し得ない気がします)。

コンフリクトが発生してしまった場合の対処法は、大きく分けて二種類存在します。

まずひとつは、諦めることです。 コンフリクトが発生した時点でそれはLR(1)文法を逸脱しているため、もともと解析可能な構文ではありません。 構文規則を等価になるようにいろいろ書き換えるとうまくコンフリクトが消せる(かもしれない)ので、与える構文の見直しをします。

もうひとつは、規則ごとにオペレーションの優先度を設定し、コンフリクトが発生した場合は強制的にどちらかの命令を実行すると決めてしまうことです。 これは一般的に行われている方法であり、かなり乱暴ですが大抵の場合はまあなんとかなります。

参考資料

第1回で紹介したものを今回もそのまま参考資料としているため、基本的にはそちらをご覧ください。 今回紹介した内容の理解を深めるのに特に役立つと思われるおすすめの資料を抜粋しておきます。

今回でおおまかなLR(1)構文解析器作りの解説を済ませたので、次回からは実装をしていくだけです。 誰も他人のソースコードの解説なんて読む気は起きないでしょうし、これ以上続ける意味があるのか大いに疑問ではあります。

第1回:かんたん構文解析入門
前回:儀式の下準備 次回:LR(1)パーサジェネレータの実装