単純LR法

単純LR法（SLR法）とは

単純LR法（SLR法, Simple LR法）は、文脈自由文法の構文解析に用いられる手法の一つです。特に、先読み記号を1つ用いるSLR(1)が広く知られています。SLR(k)と表記されることもありますが、通常はk=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)文法ではなく、より広い範囲の文法を扱える解析法が必要になります。

SLR(1)は状態数が少ないため効率は悪くないものの、解析可能な文法の範囲が比較的狭いため、現在ではあまり用いられていません。ボトムアップ構文解析に分類されますが、この分野ではより解析可能な文法の範囲が広いLALR法が主流となっています。

衝突解決のアルゴリズム

SLR(1)では、以下の手順で構文解析における衝突の解決を試みます。

1. 衝突状態の特定: shift-reduce衝突またはreduce-reduce衝突が発生している状態を特定します。
2. Follow-setの計算: 特定された状態において、reduce操作を含む規則の左辺（A → B ... X • の形式のLR(0)アイテムの非終端記号A）のFollow-setを計算します。
3. reduceアクションの設定: 計算されたFollow-setに含まれる全ての記号に対し、対応するLR(0)アイテムの規則でreduceアクションを設定します。
4. 全reduce規則に対する繰り返し: 上記2と3の手順を、reduce操作を含む全ての規則について繰り返します。
5. shiftアクションの設定: shift操作を含む規則については、次に読み込まれる記号に対してshiftアクションを設定します。
6. 全状態に対する繰り返し: 上記の操作を全ての状態について繰り返します。

もし上記の操作中に、同じ記号に対して複数のアクションが設定される場合、その状態ではSLR(1)では解決できない衝突が発生していると判断されます。一般に、SLR(1)が使用するFollow-setは文脈を考慮しないため、余計な記号が含まれてしまい、結果としてLALR(1)やLR(1)などの文脈を考慮する手法に比べて衝突が発生しやすくなります。

まとめ

SLR(1)はLR(0)をベースにしつつ、Follow-setを用いた衝突解決を取り入れた構文解析手法です。効率は良いものの、解析可能な文法の範囲が狭いため、より広い範囲を扱えるLALR(1)やLR(1)が現在の主流となっています。

関連項目

構文解析器

参考文献

中田育男, 『コンパイラ』, 産業図書株式会社, 1981, ISBN 4782850573

もう一度検索