単純LR法とは? わかりやすく解説

Weblio 辞書 > 辞書・百科事典 > 百科事典 > 単純LR法の意味・解説 

単純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)は以下の方法で衝突の解決を試みる。

  1. shift-reduce 衝突、または reduce-reduce 衝突が発生している状態を求める。
  2. 求めた状態について、reduce を含む規則の左辺、つまり A → B ... X • (ただし B および ... は空を含む)という形の LR(0) アイテムの非終端記号 A の Follow-set を求める。
  3. 求めた状態において、その Follow-set の全ての記号についてのアクションを(この LR(0) アイテムの規則で)reduce とする。
  4. 2.と3.を全ての reduce を含む規則について繰り返す。
  5. shift を含む規則については全て、その規則において、次に読み込まれる記号についてのアクションを shift とする。
  6. この操作を全ての状態について繰り返す。

上記の操作中に、同じ記号についてのアクションが二重に決まるような場合、その状態では SLR(1) によって解決不可能な衝突が発生している。

一般に、SLR(1) の使用する Follow-set は文脈を全く考慮しないため、余計な記号を含んでいる。そのため、文脈を考慮する Lookahead-set を使用する LALR(1) や LR(1) に比べ、衝突が発生しやすい。

関連項目

参考文献

  • 中田育男、『コンパイラ』、産業図書株式会社<コンピューターサイエンス・ライブラリー>、1981。ISBN 4782850573



英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「単純LR法」の関連用語

単純LR法のお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



単純LR法のページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアの単純LR法 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。

©2025 GRAS Group, Inc.RSS