DFAs vs Regexes przy wdrażaniu analizatora leksykalnego?

Question

(Po prostu uczę się pisać kompilator, więc proszę poprawić mnie, jeśli zgłaszam jakiekolwiek nieprawidłowe twierdzenia)

Dlaczego ktoś nadal będzie implementował DFA w kodzie (instrukcje goto, implementacje sterowane tabelą), skoro mogą po prostu używać wyrażeń regularnych? O ile mi wiadomo, analizatory leksykalne przyjmują ciąg znaków i tworzą listę tokenów, które w definicji gramatyki języków są terminalami, co umożliwia ich opisanie za pomocą wyrażenia regularnego. Czy nie byłoby łatwiej po prostu zapętlić kilka wyrażeń regularnych, wyłamując się z pętli, jeśli znajdzie dopasowanie?

Answer 1

Masz całkowitą rację, że łatwiej jest pisać wyrazy regularne niż DFA. Jednak dobrym pytaniem, które warto przemyśleć, jest:

Jak działają te narzędzia dopasowujące wyrażeń regularnych?

Większość bardzo szybkich implementacji masek wyrażeń regularnych polega na wewnętrznym kompilowaniu do pewnego rodzaju automatu (NFA lub minimalnego stanu DFA). Jeśli chcesz zbudować skaner, który pracowałby za pomocą wyrażeń regularnych, aby opisać, które tokeny pasują do siebie, a następnie zapętlić je wszystkie, możesz to zrobić całkowicie, ale wewnętrznie prawdopodobnie skompilowaliby się do DFA.

Bardzo rzadko zdarza się, aby ktokolwiek faktycznie zakodował DFA do skanowania lub analizy, ponieważ jest to tak skomplikowane. Dlatego istnieją narzędzia, takie jak lex lub flex, które pozwalają ci dopasować wyrażenia regularne, a następnie automatycznie skompilować je do DFA za kulisami. W ten sposób uzyskasz to, co najlepsze z obu światów - opisujesz, co należy dopasować, korzystając z ładniejszego frameworka dla wyrażeń regularnych, ale uzyskujesz szybkość i wydajność DFA za kulisami.

Jeszcze jeden ważny szczegół dotyczący budowy gigantycznego DFA polega na tym, że możliwe jest zbudowanie pojedynczego DFA, który próbuje równolegle dopasowywać wiele różnych wyrażeń regularnych. Zwiększa to efektywność, ponieważ możliwe jest uruchomienie pasującego DFA przez ciąg znaków w sposób, który będzie jednocześnie wyszukiwał wszystkie możliwe dopasowania regex.

Mam nadzieję, że to pomoże!