IEICE Trans - LR文法族の非交さ性

LR文法族の非交さ性

大蒔　和仁丸岡　章木村　正行

誌名
電子情報通信学会論文誌 D Vol.J62-D No.11 pp.711-718
発行日: 1979/11/25
Online ISSN:
DOI:
Print ISSN: 0913-5713
論文種別: 論文
専門分野:
キーワード:

本文: PDF(597.1KB)>>

あらまし:
コンパイラ作成システムを用いてコンパイラを作成するとき，通常，言語の構文を文脈自由文法として，又，意味の記述を各生成規則に対応した発生すべきコードとして与える．これらのシステムでは受け入れ可能な文法の範囲が限定されていることが多く，与えた文法がその範囲外であるときそれを変更する必要がある．しかし，これに伴う意味記述の変更があまり大幅なものにならないことが望ましい．本論文では，文法間に“非交さ的”という関係を導入し，その関係を，二つの文法の生成する言語が等しく，且つ任意の語に対するそれぞれの文法の導出木において互いに交さする部分木が存在しないとき成立するもの，と定義する．非交さ的である二つの文法は，それらの意味記述が大幅に違わないと考えられる．この関係に基づいて文法間にも非交さ的という関係を定義し，LR（k），（m，k）BRC，SLR（k）の各文法族が互いに非交さ的であること，及び，LL（k），（m，k）BRC，SLR（k）の各文法族の中には，どんなLR（k－1）文法にも非交さ的ではない文法が存在することを示す．