Czy język wyrażeń regularnych wymaga automatycznych mechanizmów wypychania w celu jego parsowania?

Chcę przekonwertować wprowadzone przez użytkownika wyrażenie regularne na NFA, aby móc następnie uruchomić NFA dla łańcucha w celu dopasowania. Jakiej minimalnej maszyny można użyć do parsowania wyrażeń regularnych?

Zakładam, że musi to być automat push, ponieważ obecność nawiasów oznacza konieczność liczenia, a DFA / NFA nie może wykonać dowolnego liczenia. Czy to założenie jest prawidłowe? Na przykład wyrażenie a (bc *) d wymaga PDA, aby podwyrażenie w nawiasach było obsługiwane poprawnie.

— Phil Wright
źródło

Co dokładnie rozumiesz przez „parsowanie”? Czy masz na myśli sprawdzenie, czy dane wejściowe są tak naprawdę wyrażeniem regularnym, czy masz na myśli coś bardziej skomplikowanego, np. Komputer generujący opis odpowiedniego NFA? (jeśli nie masz pewności, czy dane wejściowe są tak naprawdę wyrażeniem regularnym i musisz je sprawdzić, musisz mieć możliwość sprawdzenia, czy nawiasy są poprawne, a to zwykle oznacza użycie stosu).

— Kaveh

Dla praktycznego odpowiedź, można spojrzeć na źródła grep Plan 9 dla grep.y .

— Bruce Ediger

Odpowiedzi:

Masz rację. Łatwo jest wykazać, że składnia wyrażeń regularnych nie jest regularna przy użyciu standardowych technik .

Jedną z możliwości jest użycie homomorfizmu (przed którym jest zamknięty), aby pozbyć się wszystkich symboli oprócz nawiasów, co pozostawia język Dyck, o którym wiadomo, że jest nieregularny. W razie wątpliwości użyj lematu Pompowanie na . $\mathrm{REG}$ $(^p)^p$

To powiedziawszy, prawdopodobnie nie chcesz ręcznie kodować PDA. Rozważ użycie generatora analizatora składni, takiego jak ANTLR lub byacc . Z drugiej strony, jeśli chcesz zbadać parsowanie języków przez samodzielne programowanie parserów, powinieneś przejść do innych podstawowych algorytmów parsowania, takich jak CYK , Earley , zejście rekurencyjne i LR .

— Raphael
źródło

dzięki. pisanie kodu do tych zadań zapewnia lepsze zrozumienie i nie jest tak skuteczne, jak istniejące narzędzia, takie jak lex, yacc, bizon itp.

— Phil Wright

@PhilWright: Rozumiem, miło! Zredagowałem w dalszej części tego przypadku.

— Raphael

W tym przypadku wolałbym ręcznie zakodowany parser rekurencyjny.

— Dave Clarke

Jeśli piszesz ręcznie parser w tym celu, albo zejście rekurencyjne (po faktoryzacji i masowaniu) jest opcją, parser LCC dla C < sites.google.com/site/lccretargetablecompiler > ma interesujące podejście do obsługi wielu operatorów. Ale być może najłatwiejszym do ręcznego budowania jest analiza pierwszeństwa.

— vonbrand

Proponuję również przeczytać przyjemną odpowiedź Jukki na pytanie „ Dopasowywanie wyrażeń regularnych za pomocą wyrażeń regularnych ” również w cstheory. Fragment:

Na przykład możemy zmodyfikować standardową notację w następujący sposób, aby uzyskać „skompresowane” wyrażenia regularne :

Możesz usunąć dowolny prefiks, który składa się z sekwencji (

Możesz usunąć dowolny przyrostek składający się z sekwencji)

Oznacza to, że ((a|b)*c)de(f|g)można to wyrazić w zapisie „skompresowanym”, stosując na przykład dowolną z następujących form: a|b)*c)de(f|glub ((a|b)*c)de(f|glub (a|b)*c)de(f|g).

[...]

Notacja „skompresowana” (wyrażenia regularnego) jest językiem regularnym.

To tylko link do interesującego (według mnie) „innego spojrzenia” na język wyrażeń regularnych; jak podkreślono w komentarzach poniżej, nie jest to przydatne do budowania drzewa składni. Jeśli chcesz ręcznie kodować swój parser, zasugeruję ci ten prosty artykuł na temat projektu kodowego „ Pisanie własnego parsera wyrażeń regularnych ”.

— Vor
źródło

Jukka zasadniczo usuwa wymóg, aby nawiasy były zrównoważone. Nie znam przypadku, w którym to się dzieje, ale warto zauważyć, że zmieniając semantykę, można „uprościć” składnię.

— Raphael

Ty (i Jukka) nie analizujesz wyrażeń regularnych, tylko je rozpoznajesz. „Tak, to jest (skompresowane) wyrażenie regularne.”

— Gilles „SO- przestań być zły”