Jakie są dobre zasoby na temat pisania lekcji w C ++ (książki, samouczki, dokumenty), jakie są dobre techniki i praktyki?
Szukałem w Internecie i wszyscy mówią, aby używać generatora leksykalnego, takiego jak Lex. Nie chcę tego robić, chcę ręcznie napisać leksykon.
Odpowiedzi:
Należy pamiętać, że każda skończona maszyna stanu odpowiada wyrażeniu regularnemu, które odpowiada programowi strukturalnemu używającemu
if
iwhile
instrukcji.Na przykład, aby rozpoznać liczby całkowite, możesz mieć maszynę stanu:
lub wyrażenie regularne:
lub kod strukturalny:
Osobiście zawsze piszę leksykon przy użyciu tego drugiego, ponieważ IMHO jest nie mniej jasne i nie ma nic szybszego.
źródło
*pc
, prawda? Jakwhile(isdigit(*pc)) { value += pc; pc++; }
. Następnie po}
przekształceniu wartości na liczbę i przypisaniu jej do tokena.n = n * 10 + (*pc++ - '0');
. Robi się nieco bardziej skomplikowany dla zapisu zmiennoprzecinkowego i „e”, ale nie jest źle. Jestem pewien, że mógłbym zapisać trochę kodu, umieszczając znaki w buforze i wywołującatof
lub cokolwiek innego. Nie będzie działać szybciej.Lexery to skończone maszyny stanowe. Dlatego mogą być konstruowane przez dowolną bibliotekę FSM ogólnego przeznaczenia. Jednak dla własnej edukacji napisałem własną, używając szablonów wyrażeń. Oto mój leksykon:
Jest on wspierany przez iteratorową, skończoną bibliotekę maszyn skończonych o śledzeniu wstecznym, która ma długość ~ 400 linii. Jednak, to łatwo zauważyć, że wszystko, co musiałem zrobić, to konstrukt proste operacje logiczne, jak
and
,or
inot
, i kilku operatorów regex stylu jak*
na zero lub-więcej,eps
oznacza „match niczego” iopt
oznacza „meczu cokolwiek, ale go nie konsumuj ". Biblioteka jest w pełni ogólna i oparta na iteratorach. MakeEquality to prosty test na równość*it
i przekazywaną wartość, a MakeRange jest prosty<= >=
test.W końcu planuję przejść od powrotu do przewidywania.
źródło
MakeEquality
fragment kodu ? W szczególności obiekt zwrócony przez tę funkcję. Wygląda bardzo interesująco.Przede wszystkim dzieją się tutaj różne rzeczy:
Ogólnie rzecz biorąc, oczekujemy, że leksykon wykona wszystkie 3 kroki za jednym razem, jednak ten ostatni jest z natury trudniejszy i istnieją pewne problemy z automatyzacją (więcej na ten temat później).
Najbardziej niesamowitym lekserem, jakiego znam, jest Boost.Spirit.Qi . Używa szablonów wyrażeń do generowania wyrażeń leksykalnych, a po przyzwyczajeniu się do składni kod wydaje się naprawdę fajny. Kompiluje się jednak bardzo powoli (ciężkie szablony), dlatego najlepiej jest izolować różne części w dedykowanych plikach, aby uniknąć ich ponownej kompilacji, gdy nie zostały dotknięte.
Występują pewne pułapki w wydajności, a autor kompilatora Epoch wyjaśnia, w jaki sposób uzyskał przyspieszenie 1000x poprzez intensywne profilowanie i badanie działania Qi w artykule .
Na koniec generowany jest również kod przez narzędzia zewnętrzne (Yacc, Bison, ...).
Ale obiecałem napisać o tym, co było nie tak z automatyzacją weryfikacji gramatycznej.
Jeśli na przykład sprawdzisz Clanga, zdasz sobie sprawę, że zamiast używać wygenerowanego parsera i czegoś takiego jak Boost.Spirit, zamiast tego postanowili ręcznie zweryfikować gramatykę za pomocą ogólnej techniki analizy zstępującej. Z pewnością wydaje się to zacofane?
W rzeczywistości istnieje bardzo prosty powód: odzyskiwanie po błędzie .
Typowy przykład w C ++:
Zauważ błąd? Brakujący średnik bezpośrednio po deklaracji
Foo
.Jest to częsty błąd, a Clang odzyskuje sprawnie, uświadamiając sobie, że po prostu go brakuje i
void
nie jest przykładem,Foo
ale częścią kolejnej deklaracji. Pozwala to uniknąć trudnych do zdiagnozowania komunikatów o błędach.Większość zautomatyzowanych narzędzi nie ma (przynajmniej oczywistych) sposobów określania tych prawdopodobnych błędów i sposobu ich naprawienia. Często odzyskiwanie wymaga niewielkiej analizy składniowej, więc nie jest to oczywiste.
Korzystanie z zautomatyzowanego narzędzia wiąże się z kompromisem: szybko otrzymujesz parser, ale jest on mniej przyjazny dla użytkownika.
źródło
Ponieważ chcesz dowiedzieć się, jak działają leksykony, zakładam, że tak naprawdę chcesz wiedzieć, jak działają generatory leksykalne.
Generator leksykalny pobiera specyfikację leksykalną, która jest listą reguł (pary wyrażenia regularnego-token), i generuje leksyk. Ten wynikowy leksyk może następnie przekształcić łańcuch wejściowy (znakowy) w łańcuch tokena zgodnie z tą listą reguł.
Najczęściej stosowana metoda polega głównie na przekształceniu wyrażenia regularnego w deterministyczne automaty skończone (DFA) za pomocą niedeterministycznych automatów (NFA) oraz kilku szczegółów.
Szczegółowy przewodnik wykonywania tej transformacji można znaleźć tutaj . Pamiętaj, że sam tego nie przeczytałem, ale wygląda całkiem dobrze. Ponadto, prawie każda książka o budowie kompilatora będzie zawierała tę transformację w kilku pierwszych rozdziałach.
Jeśli interesują Cię wykłady z wykładów na ten temat, bez wątpienia jest ich nieskończona ilość z kursów na temat budowy kompilatora. Z mojej uczelni możesz znaleźć takie slajdy tutaj i tutaj .
Jest jeszcze kilka rzeczy, które nie są powszechnie używane w leksykach lub traktowane w tekstach, ale mimo to są całkiem przydatne:
Po pierwsze, obsługa Unicode nie jest łatwa. Problem polega na tym, że wejście ASCII ma tylko 8 bitów szerokości, co oznacza, że możesz łatwo mieć tabelę przejścia dla każdego stanu w DFA, ponieważ mają one tylko 256 wpisów. Jednak Unicode, mający szerokość 16 bitów (jeśli używasz UTF-16), wymaga 64k tabel dla każdego wpisu w DFA. Jeśli masz złożoną gramatykę, może to zająć sporo miejsca. Wypełnianie tych tabel również zajmuje sporo czasu.
Alternatywnie możesz wygenerować drzewa interwałów. Drzewo zakresu może zawierać na przykład krotki („a”, „z”), („A”, „Z”), co jest o wiele bardziej wydajne pod względem pamięci niż posiadanie pełnej tabeli. Jeśli zachowasz nie nakładające się interwały, możesz w tym celu użyć dowolnego zbalansowanego drzewa binarnego. Czas działania jest liniowy w liczbie bitów potrzebnej dla każdego znaku, więc O (16) w przypadku Unicode. Jednak w najlepszym przypadku zwykle będzie to nieco mniej.
Kolejną kwestią jest to, że tak często generowane leksykony mają w najgorszym przypadku kwadratową wydajność. Chociaż to najgorsze zachowanie nie jest często spotykane, może cię ugryźć. Jeśli napotkasz problem i chcesz go rozwiązać, możesz znaleźć tutaj artykuł opisujący, jak osiągnąć czas liniowy .
Prawdopodobnie będziesz chciał móc opisywać wyrażenia regularne w postaci ciągów, tak jak zwykle się pojawiają. Jednak parsowanie tych opisów wyrażeń regularnych na NFA (lub prawdopodobnie najpierw rekurencyjną strukturę pośrednią) jest trochę problemem z jajkiem kurzym. Do analizowania opisów wyrażeń regularnych bardzo odpowiedni jest algorytm Shunting Yard. Wydaje się, że Wikipedia ma obszerną stronę dotyczącą algorytmu .
źródło