Flex - pierwsza praca domowa.

Lekser do przykładowego kompilatora wyrażeń arytmetycznych.

Żeby wykonać to ćwiczenie, będziesz potrzebować:

  1. Kodu przykładowego kompilatora wyrażeń arytmetycznych - do ściągnięcia ze strony przedmiotu techniki kompilacji na neo.
  2. Makefile'a, który skompiluje ten kompilator do postaci wykonywalnej (należy go napisać samemu. Nie wyjaśniam tutaj, jak to zrobić).
  3. Kompilatora języka C (ew. też C++).
  4. Narzędzia flex:P.

Praca polega na zastąpieniu pliku lexer.c znajdującego się w przykładowym kompilatorze swoim własnym, wygenerowanym przy pomocy flexa, tak, żeby całość działała poprawnie.

UWAGA: W tym poradniku nie będzie kodu źródłowego, jedynie algorytm, żeby nie było niezgodności z regulaminem laboratorium.

Ten poradnik będzie składał się z następujących punktów:

  1. Spojrzenie na kod pliku lexer.c i zrozumienie, co tam właściwie się dzieje.
  2. Wyodrębnienie z pliku lexer.c rodzajów symboli, dla których trzeba zaimplementować zachowanie.
  3. Analiza kodu pliku lexer.c pod kątem tego, co z obsługi symboli należy zostawić, a co wyrzucić.
  4. Przygotowanie schematu pliku lexa (bez konkretnej implementacji, żeby każdy mógł spokojnie napisać źródła po swojemu i żeby nie było posądzeń o plagiat).
  5. Zmiana innych plików przykładowego kompilatora tak, by współdziałały z nowym lekserem.

Zrozumienie kodu lexera - widok z lotu ptaka.

Jeśli spojrzymy na zawartość pliku lexer.c, to zauważymy, że umieszczona tam funkcja lexan() opiera się na pętli nieskończonej, której zadaniem jest pobieranie znaków z wejścia standardowego i reagowanie odpowiednio w zależności od tego, jakiego rodzaju jest pobrany właśnie znak. Po drodze są też jakieś odkładania z powrotem do strumienia i pobieranie w inny sposób itd.

Jeśli chwilkę pomyślimy, to dojdziemy do wniosku, że pliki wejściowe flexa (a konkretnie część poświęcona na akcje) są takimi bardziej wysokopoziomowymi instrukcjami if..else. Stąd wniosek, że jeśli wywalimy cały niskopoziomowy bałagan z pliku lexer.c, to resztę będzie można z tego pliku (z niewielkimi zmianami) przekleić do naszego pliku flexa.

Można też zauważyć, że funkcja ta operuje na zmiennej t, do której jest wczytywany aktualnie pobrany znak (potem się zastanowimy co z nią zrobić).

Wyodrębnienie z pliku lexer.c rodzajów symboli, na które mamy reagować.

W instrukcji warunkowej w pliku lexer.c można wyodrębnić następujące warunki:

//...
if (t == ' ' || t == '\t'); //znak biały (tzw. whitespace)
//...
else if (t == '\n') //znak nowej linii
//...
else if (isdigit (t)) //liczba (niby cyfra, ale tak naprawdę dalej w kodzie ta cyfra jest odłożona 
                      //i jest wywołany scanf("%d", &tokenval), który pobiera całą liczbę ze strumienia 
                      //i wpisuje do zmiennej tokenval
//...
else if (isalpha (t))
    //...
    while (isalnum (t)) //łącznie daje to identyfikator, który musi zaczynać się od litery,
                        // a potem mogą być dowolne litery i cyfry.
//...
else if (t == EOF) //znak końca pliku
//..
else //dowolny znak
//...

Podsumowując, mamy w tym kodzie następujący rodzaje symboli, które musimy obsłużyć:

Znak biały
jest to albo spacja (znak ' '), albo tab (znak '\t').
Znak nowej linii
jest to znak '\n'.
Liczba
jest to jedna lub więcej cyfr.
Identyfikator
jest to jedna litera, po których może następować zero lub więcej liter lub cyfr (czyli znaków alfanumerycznych).
Znak końca pliku
jest to konkretnie znak określony stałą EOF.
Dowolny inny znak
jest to dowolny znak (akcja dla tego symbolu powinna być jako ostatnia w pliku flexa, bo reguły są tam interpretowane tak, że wykonywana jest pierwsza pasująca. Oczywiście do dowolneo znaku pasuje wszystko:P, dlatego powinien być na końcu).

Teraz, kiedy już mamy odpowiednie symbole, możemy przyjrzeć się kodowi pliku lexer.c pod kątem obsługi tych symboli. Jak już wspomniałem, niskopoziomowe operacje na strumieniach trzeba będzie wywalić, a resztę przekleić z drobnymi zmianami. Trzeba będzie też wziąć pod uwagę, że w narzędziu flex nie będziemy operować na pojedynczym znaku zapisanym w zmiennej t, lecz na całym dopasowanym ciągu znaków, który jest za każdym razem zapisywany przez flexa w globalnym łańcuchu yytext.

Analiza kodu pliku lexer.c pod kątem tego, co z obsługi symboli należy zostawić, a co wyrzucić.

Przyjrzyjmy się temu, co jest robione w oryginalnym lekserze dla każdego z symboli:

Znak biały
nie jest robione nic - w obsłudze tego symbolu nie trzeba nic zmieniać:P.
Znak nowej linii
licznik linii jest zwiększany o 1. Także nie trzeba nic zmieniać.
Liczba
wczytany ciąg znaków jest konwertowany do liczby typu int, która następnie jest wpisywana do zmiennej tokenval i zwracana jest stała NUM. Jako że nie operujemy już na strumieniach, nie potrzebujemy instrukcji ungetc() oraz scanf(). Całą liczbę w postaci łąńcucha znaków mamy za to w zmiennej yytext, którą to należy przekonwertować do inta tak jak się to robi zazwyczaj w języku C, a następnie przypisać wynik do zmiennej tokenval i na końcu zwrócić NUM.
Identyfikator
tu jest cała masa niepotrzebnego już kodu. Oryginał robi tak, że używa tablicy pomocniczej lexbuf żeby wczytywać do niej następne znaki z nazwy identyfikatora. Jest tam też warunek na stałą BSIZE (która oznacza rozmiar tablicy), że jeśli długość nazwy identyfikatora będzie dłuższa niż przewidzana długość pomocniczego łańcucha lexbuf[], to jest błąd. Dalej jest wpisyway na odpowiednie miejsce łańcucha pomocniczego znak końca napisu (EOS) i jeśli ostatni wczytany znak nie jest końcem pliku, to jest odkładany z powrotem do strumienia (bo wczytujemy w pętli while zawsze o jeden znak więcej niż potrzeba, żeby sprawdzić, czy identyfikator już się skończył). Tych wszystkich instrukcji w ogóle nie potrzebujemy w naszym parserze, więc je wywalamy:D. Zauważmy, że to co w końcu znajdowało się w tablicy lexbuf[] my od razu mamy w zmiennej yytext. Dlatego też właściwie resztę instrukcji, począwszy od tej z wywołaniem lookup() (pamiętaj, żeby zadeklarować wcześniej tą zmienną p), a skończywszy na "return symtable[p].token;", można spokojnie przekleić zamieniając tylko wszędzie lexbuf na yytext.
Znak końca pliku
tu nic nie ruszamy - zwracamy DONE tak jak w oryginale.
Dowolny inny znak
tutaj zamieniamy tylko t w instrukcji return t; na pierwszy znak tablicy yytext (można to zrobić dwojako, albo przez yytext[0], albo przez *yytext).

Przygotowanie schematu pliku lexa.

Krótkie podsumowanie poprzedniego punktu:

Znak biały
Zignoruj.
Znak nowej linii
Zwiększ lineno o 1;
Liczba
Skonwertuj yytext do liczby typu int, wpisz rezultat do zmiennej tokenval oraz zwróć stałą NUM.
Identyfikator
Zadeklaruj zmienną p. Przypisz do niej rezultat wywołania funkcji lookup() z yytext zamiast lexbuf. Sprawdź, czy rezultat jest zerem i jeśli tak, to wywołaj funkcję insert z yytext zamiast lexbuf. Przypisz wartość p do tokenval. Zwróć symtable[p].token.
Znak końca pliku
zwróć DONE
Dowolny inny znak
Przypisz wartość stałej NONE do tokenval. zwróć pierwszy znak łańcucha yytext.

Tak powinna wyglądać część akcji pliku flexa.

Zmiana innych plików przykładowego kompilatora tak, by współdziałały z nowym lekserem.

Generalnie to co należy tutaj zrobić, to nadać plikowi wygenerowanemu przez lexa nazwę lexer.c zamiast lex.yy.c. Można to zrobić za pomocą przełącznika -o, np.

flex -o lexer.c lexer.l

Następnie wystarczy tylko w pliku parser.c zastąpić wywołania funkcji lexan() wywołaniami funkcji yylex() oraz w pliku global.h zamienić deklarację funkcji lexan() na deklaracje funkcji int yylex(void).

Następnie pozostaje zbudować całość, odpalić i sprawdzić, czy działa tak jak z poprzednim (oryginalnym) lekserem (UWAGA: żeby kompilator wypisał wszystkie znaki, trzeba podany mu wyrażenie arytmetyczne zakończyć średnikiem).

Aha, jeśli chcesz skompilować kod z opcją -Werror, a nie możesz ze względu na ostrzeżenie związane z niewykorzystaniem funkcji yyunput, powinieneś dodać w pliku fleksa linijkę:

%option nounput

Literatura:

Rozdział 7 dokumentacji flexa pomoże dobrać odpowiednie wyrażenia, żeby zaimplementować symbole.

astralastral i społeczność;)

O ile nie zaznaczono inaczej, treść tej strony objęta jest licencją Creative Commons Attribution-Share Alike 2.5 License.