Bisakah semua tata bahasa yang tidak ambigu diurai dalam waktu linier?

Ketika bermain-main dengan parsing LR noncanonical, saya memikirkan metode parsing (dengan tabel berukuran tak terbatas, yang membuatnya agak tidak taktis ) yang mampu mengurai persis tata bahasa yang tidak ambigu dalam waktu , dan saya bertanya-tanya apakah mungkin untuk melakukan yang lebih baik :$O(n^2)$

Bisakah semua tata bahasa yang tidak ambigu diurai dalam waktu linier?

Saya cukup yakin saya membaca di suatu tempat bahwa ini adalah kasusnya, tetapi tidak muncul ketika mencari di internet. Pertanyaan yang sama ditanyakan di sini , tetapi tidak ada jawaban yang diberikan sejauh yang saya tahu.

$O(n^2)$ menggunakan algoritma Earley. Apakah ada algoritma penguraian yang bekerja dalam waktu linier pada semua tata bahasa bebas konteks yang jelas merupakan masalah terbuka. Salah satu pernyataan paling maju dari jenis ini adalah karena Leo [1991], yang menunjukkan bahwa varian Earley parsing bekerja dalam waktu linier untuk semua tata bahasa LRR.

$k$