Gdzie mogę nauczyć się podstaw pisania leksera?

86

Chcę się nauczyć, jak napisać leksera. Mój kurs uniwersytecki miał zadanie, w którym musieliśmy napisać parser (i lekser, który się z tym zgadza), ale otrzymaliśmy to bez instrukcji ani informacji zwrotnej (poza oceną), więc tak naprawdę nie nauczyłem się z niego wiele.

Po wyszukaniu tego tematu mogę znaleźć tylko dość zaawansowane zapisy, które koncentrują się na obszarach, które moim zdaniem są o kilka kroków przed tym, w którym jestem. Chciałbym omówić podstawy pisania leksera do bardzo prostego języka, którego mogę użyć jako podstawy do badania tokenizacji bardziej złożonych języków.

Na tym etapie nie interesują mnie sprawdzone metody ani techniki optymalizacji, ale wolę skupić się na tym, co najważniejsze. Jakie są dobre zasoby, aby zacząć?

Rupert Madden-Abbott
źródło

Odpowiedzi:

73

Zasadniczo istnieją dwa główne podejścia do pisania leksera:

  1. Tworzenie odręcznego, w takim przypadku polecam ten mały tutorial .
  2. Korzystanie z niektórych narzędzi do generowania lekserów, takich jak lex . W takim przypadku polecam zapoznanie się z samouczkami do wybranego narzędzia.

Chciałbym również polecić samouczek Kalejdoskop z dokumentacji LLVM . Przebiega przez implementację prostego języka, aw szczególności pokazuje, jak napisać mały lekser. Istnieje wersja samouczka w języku C ++ i Objective Caml.

Klasycznym podręcznikiem na ten temat są Kompilatory: zasady, techniki i narzędzia, znane również jako Dragon Book. Jednak prawdopodobnie należy to do kategorii „dość zaawansowanych zapisów”.

vitaut
źródło
4
Samouczek Kalejdoskop był tą częścią, która naprawdę odpowiedziała mi na to pytanie.
Robert Byers,
Więcej informacji na temat ręcznego pisania parsera LL (1) znajduje się w tej odpowiedzi .
jchook
12

Smoka Książka jest prawdopodobnie najlepszy przewodnik na ten temat, choć może być nieco przytłaczające. Wzorce implementacji języka i pragmatyka języka programowania to również świetne zasoby.

Brandon Moretz
źródło
5
+1 w księdze smoka. Wiele się z tego nauczyłem na uniwersytecie. Tak, jest tam dużo, ale jeśli naprawdę interesujesz się projektowaniem i wdrażaniem kompilatorów, to jest to świetne źródło.
DarinH