Simple LR parserとは? わかりやすく解説

Weblio 辞書 > 辞書・百科事典 > 百科事典 > Simple LR parserの意味・解説 

単純LR法

(Simple LR parser から転送)

出典: フリー百科事典『ウィキペディア(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

「Simple LR parser」の例文・使い方・用例・文例

Weblio日本語例文用例辞書はプログラムで機械的に例文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。


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

辞書ショートカット

すべての辞書の索引

「Simple LR parser」の関連用語

Simple LR parserのお隣キーワード
検索ランキング

   

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



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

   
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアの単純LR法 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。
Tanaka Corpusのコンテンツは、特に明示されている場合を除いて、次のライセンスに従います:
 Creative Commons Attribution (CC-BY) 2.0 France.
この対訳データはCreative Commons Attribution 3.0 Unportedでライセンスされています。
浜島書店 Catch a Wave
Copyright © 1995-2025 Hamajima Shoten, Publishers. All rights reserved.
株式会社ベネッセコーポレーション株式会社ベネッセコーポレーション
Copyright © Benesse Holdings, Inc. All rights reserved.
研究社研究社
Copyright (c) 1995-2025 Kenkyusha Co., Ltd. All rights reserved.
日本語WordNet日本語WordNet
日本語ワードネット1.1版 (C) 情報通信研究機構, 2009-2010 License All rights reserved.
WordNet 3.0 Copyright 2006 by Princeton University. All rights reserved. License
日外アソシエーツ株式会社日外アソシエーツ株式会社
Copyright (C) 1994- Nichigai Associates, Inc., All rights reserved.
「斎藤和英大辞典」斎藤秀三郎著、日外アソシエーツ辞書編集部編
EDRDGEDRDG
This page uses the JMdict dictionary files. These files are the property of the Electronic Dictionary Research and Development Group, and are used in conformance with the Group's licence.

©2025 GRAS Group, Inc.RSS