正規LR法

計算機科学において、正規LR法、LR(1)法、正規LR構文解析器、LR(1)構文解析器とは、k=1の場合におけるLR(k)、すなわち、終端記号1つを先読みする構文解析手法/構文解析器である。この手法の特徴は、k>1であるすべてのLR(k)構文解析器がLR(1)構文解析器に変形できるということにある^[1]。そのため、LR(1)法はすべての決定性文脈自由言語を扱うことができる^[1]。かつてこのLR(k)法は巨大なメモリを必要とするために、LALR法やLL(1)法のようなLR(k)法ほど強力ではない代替手法が選ばれ、使用を避けられてきた。しかし、近年、空間計算量がLALR法ほどである「最小LR(1)法」がいくつかのパーサジェネレータで採用されてきている。

ほとんどの構文解析器と同様に、LR(1)構文解析器は、GNU Bison、MSTA、Menhir^[2]、HYACC^[3]、そして、LRSTAR^[4]のような、パーサジェネレータで自動生成することができる。

歴史

1965年、ドナルド・クヌースはLR(k)法（入力を左(Left)から右に読んでいき、右端導出 (Rightmost derivation) を行う構文解析手法）を考案した。これはshift-reduce構文解析の一種であり、既存の順位構文解析の一般化である。この手法はすべての決定性文脈自由言語を認識できる可能性があり、入力ファイルにおいて遭遇した文の左導出と右導出の両方を生成できる。クヌースはこの手法の言語認識能力がk=1で最大に達することを証明し、k>1のLR(k)文法をLR(1)文法に変形する手法を与えた^[1]。

正規LR(1)法は構文解析表の内部表現に膨大なメモリを必要とするという実用上の欠点を抱えている。1969年、Frank DeRemerはLR法についてLALR法およびSLR法と呼ばれる2種類の簡易版を提案した。これらの手法は正規LR(1)法よりも大幅に少ないメモリで解析できるが、言語認識能力はやや劣る^[5]。LALR(1)法はLR法の最も一般的な実装である。

しかし、1977年、新しい方式のLR(1)法（最小LR(1)法）が、メモリ要件がLALR(1)法に匹敵するLR(1)法を作成できることを示したDavid Pagerによって考案された^[6]。近年、最小LR(1)法を採用するパーサジェネレータも出てきているが、この手法はメモリ要件問題だけでなく、LALR(1)パーサジェネレータ特有の不可思議な衝突問題をも解決する。

概要

LR(1)法は決定性オートマトンを用いているが、オートマトンとしての動作は静的な状態遷移表に基づいている。状態遷移表はオートマトンが認識する言語の文法をコード化しており、概して「構文解析表」と呼ばれる。

LR(1)法の構文解析表は先読みと比較される終端記号によってパラメータ化される。単純な構文解析表（LR(0)法で用いられるようなもの）は以下の形式で文法規則を表現する。

A1 → A, B

これは、状態Aから状態Bに遷移したならば、次に状態A1に遷移することを意味する。このような規則を先読みによってパラメータ化すると、次を得る。

A1 → A, B, a

これは、先読みされた終端記号がaであったときのみ遷移が発生することを意味する。これによって、先読みされた文脈によって単純な規則が多様な意味をもつようなより豊かな言語を考慮できる。例えば、LR(1)文法では、同じ状態系列に基づいているにもかかわらず、以下のすべての規則が別の異なる状態へ遷移する。

A1 → A, B, a

A2 → A, B, b

A3 → A, B, c

A4 → A, B, d

先読みされた終端記号を考慮しなかった場合、同じことは当てはまらない。構文解析エラーについては、エラーとする規則を宣言することで構文解析器が入力全体を読み取ることなく識別できる。例えば、

E1 → B, C, d

は構文解析器の停止を引き起こすようなエラーであると宣言できる。これは以下の例のように、先読み情報もまたエラーを補足するために使用できることを意味する。

A1 → A, B, a

A1 → A, B, b

A1 → A, B, c

E1 → A, B, d

この場合、AおよびBは先読みされた終端記号がa、b、またはcならばA1に還元され、dの場合はエラーが報告される。

先読みはまた規則をいつ還元すべきかの決定にも役立つ。先読みは先読みされた記号が有効でない場合にその規則での還元の回避を支援できる。これは現在の状態を以前の状態ではなく次の状態と結合させるべきであるということをおそらく意味する。例えば、以下のような状況である。

状態系列: A, B, C
規則:

A1 → A, B

A2 → B, C

もし、構文解析器が状態Bに遷移した後の先読みが受理可能でなかった場合、つまり、遷移規則が存在しなかった場合、状態系列は

A1, C

ではなく、次のように還元される。

A, A2

なお、状態は次のように終端記号から直接生成できることに注意する必要がある。

X → y

これは出現する状態系列を考慮に入れる。

LR(1)法は個々の規則が完全なLR(1)の方法で表現される必要があるという要件がある。つまり、特定の先読みをもつ2つの状態からなる系列である。これによって、

X → y

のような単純な規則は、先読みと比較される終端記号と状態のすべての可能な組み合わせを本質的に列挙する非常に多数の不自然な規則を要求する。類似の問題は

A1 → A, B

のような非先読み規則の実装にも現れ、すべての可能な先読みの列挙が必要となる。このため、LR(1)法は著しいメモリ最適化なしでは実用的な実装が不可能である^[6]。

LR(1)構文解析表の作成

LR(1)構文解析表は、各アイテムが先読みによって比較される終端記号を含むように変更することで、LR(0)構文解析表と同様の方法で作成できる。これは、LR(0)法と異なり、処理すべきアイテムの後に異なる終端記号が続く場合、異なるアクションが実行される可能性があることを意味する。

アイテム

言語の生成規則から始めて、まず、この言語のアイテム集合を決定する必要がある。わかりやすく言えば、アイテム集合とは生成規則のリストであり、各生成規則には現在処理されている記号が含まれている。集合内のアイテムが（次の記号とともに）どの状態遷移とアクションを適用すべきかを決定するために用いられている限り、アイテム集合は構文解析器の状態と1対1で対応している。各アイテムは目印を含んでおり、アイテムが表す規則内において現在処理されている記号が現れる位置を示すために用いられる。LR(1)法においては、各アイテムは先読みによって比較される終端記号に特有であり、したがって、その終端記号もまた各アイテムの内部に記録される。

例えば、終端記号としてn、'+'、'('、')'、非終端記号としてE、T、開始記号としてS、そして以下のような生成規則を含む言語を仮定する。

S → E

E → T

E → ( E )

T → n

T → + T

T → T + n

アイテム集合はLR(0)法の手続きに類似した方法で生成する。初期状態を表すアイテム集合0は開始規則から作成する。

[S → • E, $]

ドット•は規則内の現在の構文解析位置を示す目印である。この規則を適用するために先読みが予期された終端記号はコンマの後に示す。$記号は開始規則の場合のように入力の終わりが予期されたことを示す。

しかし、アイテム集合0はこれで完成ではない。各アイテム集合は「閉じる」必要がある。つまり、•に続く各非終端記号に対応するすべての生成規則は、そのようなすべての非終端記号が処理されるまで、アイテム集合に再帰的に含まれなければならない。結果として得られるアイテム集合は開始したアイテム集合の閉包と呼ばれる。

LR(1)では、各生成規則に対して、アイテムは生成規則に後続する可能な先読み終端記号のそれぞれに含まれなければならない。より複雑な言語では、これは一般に非常に大きなアイテム集合を結果としてもたらし、LR(1)法の大きなメモリ要件の原因となっている。

今回の例では、開始記号は非終端記号Eを要求し、さらにEはTを要求しているので、アイテム集合0にはすべての生成規則が含まれる。まず初めに、先読みを見つける問題を無視して単なるLR(0)の場合を見ていく。なお、LR(0)には先読みと比較される終端記号が含まれない。したがって、（先読みなしの）アイテム集合0は以下のようになる。

[S → • E]

[E → • T]

[E → • ( E )]

[T → • n]

[T → • + T]

[T → • T + n]

First集合とFollow集合

先読みと比較される終端記号を決定するには、いわゆるFirst集合とFollow集合を用いる。First(A)とは、非終端記号Aに合致する規則のあらゆる連鎖の最初の要素となりうる終端記号の集合である。アイテムI [A → α • B β, x] のFollow(I)とは、非終端記号Bの直後となりうる終端記号の集合であり、ここで、α, βは任意の記号列、xは任意の先読み終端記号である。アイテム集合kおよび非終端記号BのFollow(k,B)とは、•にBが続くようなkに含まれるすべてのアイテムのFollow集合の和集合である。First集合は言語のすべての非終端記号の閉包から直接決定できるが、Follow集合はFirst集合を使用してアイテムから決定される。

今回の例では、下記のアイテム集合の完全なリストから確認できるように、First集合は以下のようになる。

First(S) = { n, '+', '(' }

First(E) = { n, '+', '(' }

First(T) = { n, '+' }

先読み終端記号の決定

アイテム集合0からFollow集合が以下のように得られる。

Follow(0,S) = { $ }

Follow(0,E) = { $, ')'}

Follow(0,T) = { $, '+', ')' }

ここから、LR(1)法での完全なアイテム集合0は、LR(0)アイテム集合の各アイテムについて、左辺にある非終端記号のFollow集合内の各終端記号に対するコピーを作成することで作成できる。Follow集合の各要素は有効な先読み終端記号である。

[S → • E, $]

[E → • T, $]

[E → • T, )]

[E → • ( E ), $]

[E → • ( E ), )]

[T → • n, $]

[T → • n, +]

[T → • n, )]

[T → • + T, $]

[T → • + T, +]

[T → • + T, )]

[T → • T + n, $]

[T → • T + n, +]

[T → • T + n, )]

新しいアイテム集合の作成

残りのアイテム集合は以下のアルゴリズムで作成できる。

既存の各アイテム集合kにおいて•の後に現れる各記号Aについて、•の直後がAであるkのすべての規則を追加することで新しいアイテム集合mを作成する。ただし、mがステップ3以降ですでに存在しているアイテム集合と同じとならない場合に限る。
新しいアイテム集合内の各規則においてすべての•を記号1つ分右にシフトする
新しいアイテム集合の閉包を作成する
新しいアイテム集合が追加されなくなるまで、追加されたすべてのアイテム集合についてステップ1から繰り返す。

今回の例では、アイテム集合0からさらに5つのアイテム集合を得られる。

アイテム集合1（非終端記号E）

[S → E •, $]

アイテム集合2（非終端記号T）

[E → T •, $]

[T → T • + n, $]

[T → T • + n, +]

...

アイテム集合3（終端記号n）

[T → n •, $]

[T → n •, +]

[T → n •, )]

アイテム集合4（終端記号'+'）

[T → + • T, $]

[T → + • T, +]

[T → • n, $]

[T → • n, +]

[T → • + T, $]

[T → • + T, +]

[T → • T + n, $]

[T → • T + n, +]

...

アイテム集合5（終端記号'('）

[E → ( • E ), $]

[E → • T, )]

[E → • ( E ), )]

[T → • n, )]

[T → • n, +]

[T → • + T, )]

[T → • + T, +]

[T → • T + n, )]

[T → • T + n, +]

...

アイテム集合2、4および5からさらにいくつかのアイテム集合が作成される。完全なリストはかなり長いためここでは述べない。この文法の詳細なLR(k)での扱いは例えば[1]に示されている。

GOTO表

LR(1)アイテムの先読みはreduceアクション時（つまり、• の目印が右端にある場合）のみ直接使用される。

LR(1)アイテム [S → a A • B e, c] のコア (core) とは、LR(0)アイテム S → a A • B e のことである。異なるLR(1)アイテムが同じコアを共有する場合もある。

例えば、アイテム集合2では

[E → T •, $]

[T → T • + n, $]

[T → T • + n, +]

となり、構文解析器は次の記号が$ならば還元 [E → T] を要求されるが、次の記号が'+'ならばシフトを要求される。LR(0)構文解析器はアイテムのコアのみを考慮するためこの決定ができず、shift-reduce衝突を報告することに注意されたい。

[A → α • X β, a]を含む状態はラベルXで[A → α X • β, a]を含む状態に遷移する。

それぞれの状態はGOTO表にしたがう遷移をもつ。

shiftアクション

もし [A → α • b β, a] が状態I_kにあり、I_kがI_mにラベルbで遷移するならば、アクション表には

action[I_k, b] = "shift m"

を追加する。

reduceアクション

もし [A → α •, a] が状態I_kにあるならば、アクション表には

action[I_k, a] = "reduce A → α"

を追加する。

参考文献

^ ^a ^b ^c Knuth, D. E. (July 1965). “On the translation of languages from left to right”. Information and Control 8 (6): 607–639. doi:10.1016/S0019-9958(65)90426-2 2017年8月31日閲覧。.
^ “What is Menhir?”. INRIA, CRISTAL project. 2017年8月31日閲覧。
^ “HYACC, minimal LR(1) parser generator”. 2017年8月31日閲覧。
^ “LRSTAR, minimal LR(1) parser generator”. 2013年7月10日時点のオリジナルよりアーカイブ。2017年8月31日閲覧。
^ Franklin L. DeRemer (1969年). “Practical Translators for LR(k) languages”. MIT, PhD Dissertation. April 5, 2012時点のオリジナルよりアーカイブ。2017年8月31日閲覧。
^ ^a ^b Pager, D. (1977), “A Practical General Method for Constructing LR(k) Parsers”, Acta Informatica 7: pp. 249–268

外部リンク

Syntax Analysis PowerPointプレゼンテーション, Aggelos Kiayias, コネチカット大学
LR parsing PowerPointプレゼンテーション, Aggelos Kiayias, コネチカット大学
Practical LR(k) Parser Construction HTMLページ, David Tribble
First & Follow Sets Construction in Python (Narayana Chikkam)

[Knuth_1965-1] Knuth, D. E. (July 1965). “On the translation of languages from left to right”. Information and Control 8 (6): 607–639. doi:10.1016/S0019-9958(65)90426-2 2017年8月31日閲覧。.

[2] “What is Menhir?”. INRIA, CRISTAL project. 2017年8月31日閲覧。

[3] “HYACC, minimal LR(1) parser generator”. 2017年8月31日閲覧。

[4] “LRSTAR, minimal LR(1) parser generator”. 2013年7月10日時点のオリジナルよりアーカイブ。2017年8月31日閲覧。

[DeRemer_1969-5] Franklin L. DeRemer (1969年). “Practical Translators for LR(k) languages”. MIT, PhD Dissertation. April 5, 2012時点のオリジナルよりアーカイブ。2017年8月31日閲覧。

[Pager_1977-6] Pager, D. (1977), “A Practical General Method for Constructing LR(k) Parsers”, Acta Informatica 7: pp. 249–268

[1]

[2]

[3]

[4]

[5]

[6]