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?
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 n 21 n | n ≥ 1} to LR (0), ale język nie jest regularny:
S -> E
E -> 0E1 | 2
Mam nadzieję że to pomoże!
(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.
źródło
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).