Czy wszystkie jednoznaczne gramatyki można analizować w czasie liniowym?

Podczas majstrowania przy niekanonicznym analizowaniu LR wymyśliłem metodę analizy (z tabelami o nieskończonych rozmiarach, co czyni ją nieco niepraktyczną ), która jest w stanie przeanalizować dokładnie jednoznaczne gramatyki w czasie , i zastanawiałem się, czy można to zrobić lepiej :$O(n^2)$

Czy wszystkie jednoznaczne gramatyki można analizować w czasie liniowym?

Jestem pewien, że gdzieś przeczytałem, że tak jest, ale nie pojawia się podczas wyszukiwania w Internecie. To samo pytanie zadano tutaj , ale nie dano odpowiedź o ile wiem.

Jednoznaczne bezkontekstowe parsowanie odbywa się w przy użyciu algorytmu Earleya. To, czy istnieje algorytm analizujący działający w czasie liniowym na wszystkich jednoznacznych gramatykach bezkontekstowych, stanowi otwarty problem. Jedno z najbardziej zaawansowanych stwierdzeń tego rodzaju wynika z Leo [1991], który wykazał, że wariant parsowania Earleya działa w czasie liniowym dla wszystkich gramatyk LRR.$O(n^2)$

[Leo 1991] Joop MIM Leo. Ogólny bezkontekstowy algorytm analizujący działający w czasie liniowym na każdej gramatyce LR ( ) bez korzystania z wyprzedzenia, Theoretical Computer Science 82 (1): 165--176. doi: 10.1016 / 0304-3975 (91) 90180-A$k$