Analiza leksykalna bez wyrażeń regularnych

9

Patrzyłem na kilka leksykonów w różnych językach wyższego poziomu ( między innymi Python , PHP , JavaScript ) i wszystkie wydają się używać wyrażeń regularnych w takiej czy innej formie. Chociaż jestem pewien, że wyrażenia regularne są prawdopodobnie najlepszym sposobem na zrobienie tego, zastanawiałem się, czy istnieje jakiś sposób na uzyskanie podstawowego leksykalizacji bez wyrażeń regularnych, może jakieś bezpośrednie parsowanie ciągów lub coś takiego.

Więc tak, czy można zaimplementować jakieś podstawowe leksykacje w języku wyższego poziomu * bez użycia wyrażeń regularnych w jakiejkolwiek formie?

* Języki wyższego poziomu, takie jak Perl / PHP / Python / JavaScript itp. Jestem pewien, że istnieje sposób, aby to zrobić w C

theory regular-expressions lexer Plama
źródło
2
Wydaje się, że „czy jest książka o rachunku różniczkowym i całkowym, która nie używa wszystkich greckich liter i dziwnych zawiłych rzeczy?”
kevin cline
@kevincline Dlaczego ludzie wiosłują przez Atlantyk, skoro na niebie są doskonale dobre samoloty?
Smudge
1
wiosłowanie i jazda mają różne skutki uboczne.
kevin cline

Odpowiedzi:

3

Po pierwsze, istnieją biblioteki wyrażeń regularnych dla języka C, zanim jeszcze wynaleziono języki „wyższego poziomu”. Mówiąc wprost, programy C nie są tak podunkowe, jak niektórzy ludzie myślą.

W przypadku większości gramatyk leksykalny polega na wyszukiwaniu spacji i kilku innych znaków, takich jak () [] {}; podzielić słowa, a następnie dopasować do listy słów kluczowych, aby sprawdzić, czy pasują do siebie.

Karl Bielefeldt
źródło
1
Nie miałem na myśli, że C nie może robić wyrażeń regularnych, miałem na myśli, że ma bardziej zaawansowane funkcje do robienia takich rzeczy. Wyobrażam sobie, że łatwiej jest zbudować zaawansowany i wydajny leksykon w języku C niż język wyższego poziomu.
Smudge
1
@sam złożoność i wydajność leksera lub parsera jest bardziej funkcją złożoności analizowanego języka niż języków, w których parser jest zaimplementowany, więc nie.
jk.
+1. Lexer jest niezwykle prosty; potrzebujesz tylko ciągu, typu danych dla swoich tokenów i tabeli predefiniowanych słów kluczowych. Najtrudniejsza część dotyczy białych znaków i komentarzy: P
Mason Wheeler
2

Możesz być zainteresowany „parserami bez skanera”, które nie mają osobnego kroku tokenizacji. Jedno wyjaśnienie korzyści z parserów bez skanera znajduje się na początku tego dokumentu: Filtry ujednoznaczniające dla skanerów uogólnionych parserów LR . (Są jednak także wady).

(PEG, które zostały wspomniane w innych odpowiedziach, można również wykorzystać do budowy parserów bez skanera).

Ryan Culpepper
źródło
1

W wyrażeniach regularnych nie ma nic konkretnego. Są one po prostu krótsze, co pozwala znacznie łatwiej wygenerować kod, a implementacje są zwykle wysyłane. Zasadniczo lekserzy to FSM, a wyrażenia regularne to tylko jeden ze sposobów osiągnięcia tego celu.

DeadMG
źródło
0

Oczywiście możesz używać innych parserów, ponieważ każdy zwykły język jest również pozbawiony kontekstu. Pytanie naprawdę sprowadza się do tego, dlaczego chcesz.

Nie ma nic prostszego niż wyrażenia regularne (jak możesz poprawić O (N)?), A próba uproszczenia nie pomoże. Zawsze możesz użyć prostego cofania, jak zauważył Jetti, chociaż zalecam unikanie go, jeśli to możliwe.

Jeśli zamierzasz używać bardziej zaawansowanego parsera do leksykalizacji, prawdopodobnie nie potrzebujesz wcale fazy leksykalnej. W rzeczywistości powodem, dla którego mamy fazę leksykalną, jest to, że szybciej parsuje tokeny leksykalne niż parsuje postacie, a także znacznie upraszcza nasz etap analizy. Używając bardziej zaawansowanego parsera, po prostu tracisz wszystkie zalety leksykalizacji.

Pubby
źródło
Jak więc robi to wyrażenie regularne? Czy nadal nie musiałby iść znak po znaku (przynajmniej w przypadku większości wzorów używanych w leksykach)?
Jetti
@Jetti Tak, oczywiście.
Pubby
Równie łatwo byłoby odczytać każdą postać, a następnie cofnąć się w razie potrzeby, aby wyciągnąć token. Byłoby to więcej kodu, ale nie trudniejsze.
Jetti
@Jetti Nie widzę, jak lepsze jest naiwne nawracanie.
Pubby
Nigdy nie powiedziałem lepiej. Ale OP zapytał, czy istnieją inne sposoby i jest to inny sposób, który nie jest zaawansowanym parserem.
Jetti
0

Sensowne jest albo wykonanie analizy leksykalnej przy użyciu wyrażeń regularnych, albo pominięcie tego przejścia i wykonanie znacznie bardziej elastycznego i wydajnego bezszeregowego analizowania za pomocą PEG lub GLR.

Logika SK
źródło