一種有效率的普遍式文法剖析演算法

Abstract

Earley的普遍式剖析演算法可以剖析所有的context-free文法，但是它需要O(nΛ2) 的時間來剖析LR(K) 文法。我們提出一種有效率的普遍式文法剖析演算法，它比 Earley的演算法還要有效率。首先，我們使用一種有效率的方法轉換context-free 文法到"非右遞迴"的文法。在這種轉換後，有很大部份的文法都可以在線性時間內剖 析完成。我們稱這一部份的文法為"Simple"文法。"Simple"文法比LR(K) 文法還大。 其它不能在線性時間內剖析完成的文法，我們稱為"RR"文法。最後我們提出"RR"文法 的型式和範例。