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

12

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?

— Deb
źródło

3

Co powiesz na wykorzystanie technik kanonicznych do wygenerowania tabel

i

i sprawdzenie, czy zawierają one konflikty?

i

są zwykle traktowane w dowolnym standardowym podręczniku na temat analizowania; z

i

techniki są trochę twardszy znaleźć, ale są również dobrze znane.

L L (k)

$LL(k)$

L R (k)

$LR(k)$

L L (1)

$LL(1)$

L R (1)

$LR(1)$

L L (k)

$LL(k)$

L R (k)

$LR(k)$

— Alex ten Brink

@AlextenBrink Brzmi to tak, jakbyś mógł dać odpowiedź! (Witaj ponownie, brakowało Ci!)

— Raphael

Wykorzystanie techniki kanonicznej do sprawdzenia, czy gramatyka to LL, czy LR ma rację, ale jest długa. Próbuję znaleźć mały sposób na znalezienie tego, co znalazłem w książce Kompilatorów Aho-Lam-Sethi-Ullmana.

— Deb

11

$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 ).

— Alex ten Brink
źródło

Czy wiesz, gdzie mogę znaleźć szczegóły algorytmu czasu wielomianowego do testowania, czy językiem jest LR (k) (oprócz zakupu podręcznika)?

— user541686

2

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:

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

— Deb
źródło