Czy wyrażenia regularne

Jeśli mam gramatykę typu 3, można ją przedstawić na automacie wypychania (bez wykonywania żadnych operacji na stosie), dzięki czemu mogę reprezentować wyrażenia regularne przy użyciu języków bezkontekstowych. Ale czy mogę wiedzieć, czy gramatyka typu 3 to , , itd. Bez konstruowania jakichkolwiek tabel analizy składni? $LR(1)$ $LL(1)$ $SLR(1)$

— Andrea Tucci
źródło

Odpowiedzi:

Wszystkie zwykłe języki mają gramatykę LL (1). Aby uzyskać taką gramatykę, weź dowolny DFA dla języka regularnego (być może wykonując konstrukcję podzbioru na NFA uzyskanym z wyrażenia regularnego), a następnie przekonwertuj go na prawą rekurencyjną gramatykę regularną. Gramatyka ta to LL (1), ponieważ każda para produkcji dla tego samego nieterminala albo zaczyna się od różnych symboli, albo produkuje ε i ma $ jako token wyprzedzający. W związku z tym wszystkie zwykłe języki są również LR (1), ponieważ każda gramatyka LL (1) to LR (1). Dodatkowo, korzystając z ważnego wyniku z tego artykułu , możesz pokazać, że każdy język LR (1) ma gramatykę SLR (1), co oznacza, że każdy zwykły język ma gramatykę SLR (1).

Jednak zwykłe języki to nie wszystkie LR (0). Języki LR (0) mają bardzo specyficzne właściwości - w szczególności muszą być wolne od prefiksów. Zatem językiem regularnym {a, aa} nie jest LR (0), chociaż jest on wyraźnie regularny (regex a | (aa)). Jednak języki LR (0) nie są poprawnie zawarte w zwykłych językach; ta gramatyka dla {0 ⁿ 21 ⁿ | n ≥ 1} to LR (0), ale język nie jest regularny:

S -> E
E -> 0E1 | 2

Mam nadzieję że to pomoże!

— templatetypedef
źródło

Fakt, że prawidłowa gramatyka akceptuje dokładnie zestaw zwykłych języków, zwykle odbywa się na zajęciach (a nawet ćwiczeniach), więc odpowiedź jest o wiele bardziej bezpośrednia.

— Raphael

(Zwykły stary) składnia wyrażeń regularnych (mówiłeś, że „reprezentacja”) to LR (0). Nie potrzebujesz żadnego spojrzenia w przód, aby przeanalizować ciąg reprezentujący wyrażenie regularne. Możesz łatwo o tym zadecydować, uruchamiając generator parsera w gramatyce wyrażeń regularnych: -} Możesz również z łatwością zakodować prosty parser rekurencyjnego zapisu (LL (0)) dla wyrażeń regularnych; wszystko, co jest LL (0), to LR (0).

Nie wiem, czy składnia bardziej skomplikowanych tak zwanych „wyrażeń regularnych”, takich jak Perl, jest taka; ale wyrażenia regularne Perla są silniejsze niż wyrażenia regularne, więc nie są zwykłymi wyrażeniami regularnymi.

Aby ustalić, czy gramatyka ma jakąś właściwość, musisz uruchomić jakiś predykat. Aby ustalić, czy jest to (S) LR (k), musisz uruchomić predykat, który może sprawdzić tę właściwość. W efekcie każdy taki predykat musi w efekcie budować tabele analizowania, ze względu na sposób ich zdefiniowania.

— Ira Baxter
źródło

Wyrażenia regularne Perla działają na NFA

Pytanie nie dotyczyło sposobu działania wyrażeń regularnych Perla. Chodziło o to, czy niektóre wyrażenia regularne (Perl?) Można analizować za pomocą niektórych technologii. Wierzę, że wyrażenia regularne Perla używają NFA do ich dopasowania, podobnie jak inne przechwytywanie danych kontekstowych, ale nie widzę związku z tym pytaniem.

-1 Wyrażenia regularne nie są LR (0). Języki LR (0) muszą być wolne od prefiksów, ale wyrażenie regularne a|(aa)opisuje język, który nie jest bez prefiksów. Ponadto języki LR (0) nie obsługują gramatyki z produkcjami epsilon, więc zwykły język {epsilon, a} nie jest LR (0). Jednak językami zwykłymi są LL (1), ponieważ można je pisać jako zwykłe gramatyki, a zatem wszystkie są LR (1). Ponieważ każdy język LR (1) ma gramatykę SLR (1), oznacza to, że wszystkie zwykłe języki to SLR (1).

— templatetypedef

Jeśli chodzi o LL (0), jest na odwrót: języki LL (0) są właściwym podzbiorem zwykłych języków. Zauważ, że LL (0) oznacza, że nie używasz lookahead do decydowania między różnymi pochodnymi - co w zasadzie oznacza, że nie ma żadnych decyzji, a język składa się z jednego słowa. Natomiast LR (0) jest użyteczną klasą - ponownie nie używasz lookahead do decydowania (tutaj dla redukcji), ale nadal istnieje pewna różnorodność ze względu na fakt, że przesunięcie może rozróżniać różne produkcje.

@ IraBaxter - Składnia wyrażeń regularnych nie jest LR (0), ponieważ wyrażenia regularne nie są wolne od prefiksów. Nie są to również LL (0), ponieważ języki LL (0) mogą zawierać tylko jeden ciąg (lub żadnych ciągów).

— templatetypedef