Teoretyczne porównanie gramatyk LL i LR

66

Ludzie często mówią, że parsery LR (k) są silniejsze niż parsery LL (k) . Te stwierdzenia są przez większość czasu niejasne; w szczególności, czy powinniśmy porównać klasy dla ustalonego k lub unii dla całego k ? Jak więc naprawdę wygląda sytuacja? W szczególności jestem zainteresowany tym, jak pasuje LL (*).

O ile mi wiadomo, odpowiednie zestawy gramatyk, które akceptują parsery LL i LR, są ortogonalne, więc porozmawiajmy o językach generowanych przez odpowiednie zestawy gramatyk. Niech oznacza klasę języków generowanych przez gramatykę, które mogą być analizowane przez parser L R ( k ) i podobne dla innych klas.L.R(k)L.R(k)

Interesują mnie następujące relacje:

  • L.L.(k)?L.R(k)
  • i=1LL(k)?i=1LR(k)
  • i=1LL(k)=?LL()
  • LL()?i=1LR(k)

Niektóre z nich są prawdopodobnie łatwe; moim celem jest zebranie „kompletnego” porównania. Referencje są mile widziane.

Raphael
źródło
2
Może to może ci pomóc! Obraz Hierarchia gramatyki
Andrea Tucci
1
@AndreaTucci: Tak, ale obejmuje to tylko gramatykę, a nie generowane języki.
Raphael

Odpowiedzi:

60

Istnieje wiele znanych pojemników. Niech oznacza ograniczenie i właściwe ograniczenie. Niech × oznacza nieporównywalność.×

Niech , L R = k L R ( k ) .L.L.=kL.L.(k)L.R=kL.R(k)

Poziom gramatyki

Dla LL

  • L.L.(0)L.L.(1)L.L.(2))L.L.(2))L.L.(k)L.L.L.L.()
  • S.L.L.(1)=L.L.(1),S.L.L.(k)L.L.(k),S.L.L.(k+1)×L.L.(k)

S.L.L.(k+1)×L.L.(k)L.L.()L.L.L.L.RL.L.L.L.()

Dla LR

  • L.R(0)S.L.R(1)L.ZAL.R(1)L.R(1)
  • S.L.R(k)L.ZAL.R(k)L.R(k)
  • S.L.R(1)S.L.R(2))S.L.R(k)
  • L.ZAL.R(1)L.ZAL.R(2))L.ZAL.R(k)
  • L.R(0)L.R(1)L.R(2))L.R(k)L.R

To są wszystkie proste ćwiczenia.

LL kontra LR

  • L.L.(k)L.R(k)
  • L.L.(k)×S.L.R(k),L.ZAL.R(k),L.R(k-1)
  • L.L.L.R
  • L.L.()×L.R

Poziom języka

Dla LL

  • L.L.(0)L.L.(1)L.L.(2))L.L.(k)L.L.L.L.()
  • S.L.L.(k)=L.L.(k)

L.L.(k)L.L.()L.L.L.L.RL.L.L.L.()

Dla LR

  • L.R(0)S.L.R(1)=L.ZAL.R(1)=L.R(1)=S.L.R(k)=L.ZAL.R(k)=L.R(k)=L.R

Niektóre z nich zostały udowodnione przez Knutha w jego artykule na temat tłumaczenia języków od lewej do prawej, w którym wprowadził LR (k), pozostałe zostały udowodnione w Transformacji gramatyki LR (k) do LR (1), SLR (1), oraz (1,1) Ograniczone gramatyki prawego kontekstu autorstwa Mickunas i in.

LL kontra LR

  • L.L.L.R(1){zajabjot|jajot}
  • L.L.()×L.R{zajabjot|jajot}
  • L.R(1)=redofaL.
Alex ten Brink
źródło
Doskonała odpowiedź, ale już głosowałem. Myślałem, że Frank deRemer udowodnił LALR <= LR w swoim oryginalnym artykule LALR? (1969?)
user207421
L.ZAL.R(k)L.R(k)L.ZAL.RL.R
1
@AlextenBrink Przeczytałem gazetę i uczył mnie Frank de Remer, ale to już ponad 30 lat temu ;-) Dzięki za wszystkie szczegóły.
user207421
Przydałoby się zebrać przykładowe gramatyki dla każdej nierówności.
o11c
1
@ o11c Myślę, że to przeciążałoby jedną odpowiedź. Mam wrażenie, że Alex w razie potrzeby dał dobre referencje; dla niektórych stwierdza „łatwe ćwiczenie”. Myślę, że jeśli czytelnik nie potrafi wymyślić gramatyki, może opublikować nowe pytanie z pytaniem o konkretny przypadek.
Raphael