単純LR法
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2013/04/15 17:57 UTC 版)
単純LR法(SLR法,Simple LR法)とは、文脈自由文法のための構文解析手法である。先読み記号の数によってSLR(k)と表記するが、通常 k = 1 の SLR(1) を指す。以下ではSLR(1)について述べる。また、SLR(1) によって解析可能な文法を SLR(1) 文法と呼び、その範囲は LR(0) より大きく、LALR(1) や LR(1) より小さい。
概要
SLR(1) は、まず LR(0) アイテムを用いて全ての状態を求め、LR(0) 構文解析表の作成が可能な状態にする(LR法参照)。
その後 Follow-set (LL法参照)を用いて衝突の解決を試みる。この直後の時点で衝突がなければその文法は SLR(1) 文法である。LR(0) 文法は SLR(1) 文法に含まれるので、衝突がそもそも発生していない場合も SLR(1) 文法である。逆に、衝突が残っていればその文法は SLR(1) 文法ではなく、解析を行うにはより広い範囲の文法を扱える解析法を使わなければならない。
状態の数が少ないため効率は悪くないのだが、解析の可能な文法の範囲が狭いため、単純LR法は現在ではあまり使用されていない。単純LR法はボトムアップ構文解析に含まれるが、この種類の中ではLALR法がより多く使われている。
衝突解決のアルゴリズム
SLR(1)は以下の方法で衝突の解決を試みる。
- shift-reduce 衝突、または reduce-reduce 衝突が発生している状態を求める。
- 求めた状態について、reduce を含む規則の左辺、つまり A → B ... X • (ただし B および ... は空を含む)という形の LR(0) アイテムの非終端記号 A の Follow-set を求める。
- 求めた状態において、その Follow-set の全ての記号についてのアクションを(この LR(0) アイテムの規則で)reduce とする。
- 2.と3.を全ての reduce を含む規則について繰り返す。
- shift を含む規則については全て、その規則において、次に読み込まれる記号についてのアクションを shift とする。
- この操作を全ての状態について繰り返す。
上記の操作中に、同じ記号についてのアクションが二重に決まるような場合、その状態では SLR(1) によって解決不可能な衝突が発生している。
一般に、SLR(1) の使用する Follow-set は文脈を全く考慮しないため、余計な記号を含んでいる。そのため、文脈を考慮する Lookahead-set を使用する LALR(1) や LR(1) に比べ、衝突が発生しやすい。
関連項目
参考文献
- 中田育男、『コンパイラ』、産業図書株式会社＜コンピューターサイエンス・ライブラリー＞、1981。ISBN 4782850573
- 単純LR法のページへのリンク
