Czy jest jakiś sposób na rozróżnienie gramatyki LL (k) i LR (k)?

Ostatnio studiuję na temat projektowania kompilatorów. Dowiedziałem się o dwóch rodzajach gramatyki: jedna to gramatyka LL, a druga to gramatyka LR.

Znamy również fakty, że każda gramatyka LL jest LR, czyli gramatyka LL jest właściwym podzbiorem gramatyki LR. Pierwszy jest używany podczas analizy z góry na dół, a drugi jest używany podczas analizy z dołu do góry.

Ale czy jest jakiś sposób, abyśmy mogli powiedzieć, że dana gramatyka to LL lub LR?

$LL(k)$$LR(k)$$LL(k)$$LR(k)$, a ponieważ możemy wygenerować dla nich tabele (parsowanie tabel służy do parsowania ciągów wejściowych). Zauważ, że dla tych dwóch klas posiadanie parsowanej tabeli pozwala natychmiast sprawdzić, czy gramatyki są w klasach, ponieważ dzieje się tak wtedy i tylko wtedy, gdy tabele nie zawierają błędów. Tak, istnieją klasy gramatyki, które możemy skutecznie parsować, jeśli mamy tabelę parsowania, ale dla których nie możemy wygenerować tabeli, jeśli ona istnieje.

$LL(1)$$LR(1)$$SLR(1)$$LL(k)$$LR(k)$

$LL(k)$$LR(k)$$LL(1)$$k$$LL(k)$$LR(k)$lub nie działa w czasie wielomianowym (generowanie tabeli jest wykładnicze). Aby uzyskać szczegółowe informacje, przeczytaj powyższy podręcznik. Zauważ, że w wielu przypadkach stół ma rozsądną wielkość, więc test nie jest potrzebny.

$k$$k$$LL(k)$$LR(k)$$LR(k)$$k$$LL(c)$$c$$k$(szczegóły tutaj ).

Musimy tylko sprawdzić, czy gramatyka jest LL, czy nie, ponieważ każda gramatyka LL to LR, czyli LL, to właściwy podzbiór LR. Jeśli więc gramatyka to LL, to musi to być LR, ale każdy LR nie jest LL.

Gramatyka G jest w LL iff za każdym razem, gdy A-> C | D, należy spełnić następujący warunek:

1. Pierwszy (C) i Pierwszy (D) to zbiory rozłączne.
2. Jeśli puste jest w First (D), pierwsze (C) i Follow (A) są rozłącznymi zestawami, podobnie puste jest w First (C).