単純LR法

単純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)は以下の方法で衝突の解決を試みる。
上記の操作中に、同じ記号についてのアクションが二重に決まるような場合、その状態では SLR(1) によって解決不可能な衝突が発生している。
一般に、SLR(1) の使用する Follow-set は文脈を全く考慮しないため、余計な記号を含んでいる。そのため、文脈を考慮する Lookahead-set を使用する LALR(1) や LR(1) に比べ、衝突が発生しやすい。