LL(k)文法に対するより直接的な等価性判定法

富田 悦次  

誌名
電子情報通信学会論文誌 D   Vol.J63-D   No.9   pp.755-762
発行日: 1980/09/25
Online ISSN: 
DOI: 
Print ISSN: 0913-5713
論文種別: 論文
専門分野: 
キーワード: 


本文: PDF(660.1KB)>>
論文を購入




あらまし: 
LL(k)文法の等価性判定法として,最近,OlshanskyとPnueliは文法そのものに対する直接的アルゴリズムを発表した.これは,単純決定性文法(ε-規則なしLL(1)文法)の等価性判定に対するKorenjakとHopcroftの分岐アルゴリズムを基礎としているが,その有限終端性のための鍵としてもKorenjakらのtype B replacementと同様の手法が採られており,そのため,十分に簡明なアルゴリズムとはいい難い.そこで本論文では,一方がε-動作なしである空スタック受理式の決定性プッシュダウンオートマトンに対する等価性判定法として先に提唱した新しい分岐アルゴリズムを基礎とし,type B replacementの概念を完全に排除した,より直接的で簡潔なLL(k)文法の等価性判定アルゴリズムを与える.ここでは,分岐のチェックをすべき対象としては,通常の等価式を考える代りにOlshanskyらが定義したprefix部分の限定条件付きの等価式(等価式)を用い,LL(k)文法における最左導出過程を先の決定性プッシュダウンオートマトンにおける推移過程とほぼ同様に扱えるようにしている.但し,入力記号列の先読みに関して,更に新たな考慮を払っている.