1 KONSTRUKCJA KOMPILATORÓW WYKŁAD WYKŁAD Robert Plebaniak Robert Plebaniak

2 PLATFORMA PROGRAMOWA LINUX (może nie zawierać LLgen, wówczas instalacja ze strony http://tack.sourceforge.net); http://tack.sourceforge.net WINDOWS (używa się wtedy programu Cygwin, można znaleźć http://www.cygwin.com); http://www.cygwin.com 2

3 Narzędzia potrzebne do ćwiczeń: Kompilator C Generator LLgen Generator LEX Generator YACC Edytor tekstowy 3

4 KOMPILATOR C W przypadku gdy korzystamy z systemu Linux lub Cygwin najlepiej korzystać z domyślnego w tych systemach kompilatora C – gcc lub C++ (g++). Gdy używamy systemu Windows można skorzystać z wierszowych wersji komercyjnych kompilatorów firm Borland i Microsoft (które są darmowe) lub środowiska Open Watcom (http://www.openwatcom.org) 4

5 GENERATOR LLGen Niektóre dystrybucje systemu LINUX Wersja źródłowa, w ramach pakietu ACK Oddzielny produkt, np. do pobrania pod adresem http://tack.sourceforge.net/ http://tack.sourceforge.net/ System operacyjny Minix http://www.minix3.org 5

6 GENERATORY LEX i YACC PCYACC - wersja komercyjna http://www.abxsoft.com http://www.abxsoft.com MKS LEX & YACC – wersja komercyjna http://www.mkssoftware.com http://www.mkssoftware.com Bumble-Bee Parser Generator – wersja komercyjna http://www.bumblebeesoftware.com 6

7 LITERATURA Kompilatory reguły, metody i narzędzia A. V. Aho, R. Sethi, J.D. Ullman, WNT 2002; Konstrukcja kompilatorów, W. M. Waite, G. Goos, WNT 1989; Automaty i języki formalne T. Krasiński UŁWM, 2005; http://www.gnu.org/software/bison/manualhttp://www.gnu.org/software/bison/manual - generator LEX i YACC; http://www.gnu.org/software/bison/manual http://tack.sourceforgen.net/doc/LLgen.htmlhttp://tack.sourceforgen.net/doc/LLgen.html - generator LLGen; http://tack.sourceforgen.net/doc/LLgen.htmlwww.wazniak.mimuw.edu.pl 7

8 O czym będzie na wykładzie? Pojęcie i modele kompilatora, interpretera; Poszczególne fazy działania kompilatora i etapy kompilacji; Elementy analizy leksykalnej i składniowej; Modele generatorów: LLgen, Lex, Yacc 8

9 Kompilatory Definicja 1. Kompilator jest programem, którego zadaniem jest przetworzenie kodu napisanego w jakimś języku programowania (C, Ada, Java) zwanym językiem źródłowym, na równoważny kod w innym języku, zwanym językiem wynikowym. 9

10 INTERPRETER Interpreter – jest programem, który działa podobnie jak kompilator, z tą różnicą, iż nie generuje kodu wynikowego, tylko od razu wykonuje instrukcje zawarte w kodzie źródłowym programu. 10

11 FAZY DZIAŁANIA KOMPILATORA Program źródłowy; Program źródłowy; Analiza; Analiza; Reprezentacja pośrednia; Reprezentacja pośrednia; Synteza; Synteza; Program wynikowy; Program wynikowy; 11

12 ETAPY KOMPILACJI Analiza – na tym etapie, kompilator rozkłada program źródłowy na części składowe, a następnie generuje tzw. reprezentację pośrednią. Również na tym etapie następuje także wykrywanie błędów i ewentualne informowanie o nich programistę. Również na tym etapie następuje także wykrywanie błędów i ewentualne informowanie o nich programistę. 12

13 ANALIZA Analiza leksykalna; Analiza składniowa; Analiza semantyczna; 13

14 ANALIZA LEKSYKALNA Analiza leksykalna zwana jest także skanowaniem lub analizą liniową. Głównym zadaniem analizy leksykalnej jest grupowanie znaków strumienia wejściowego w symbole leksykalne inaczej zwane token-ami. 14

15 ANALIZA LEKSYKALNA Tokeny to inaczej elementarne składniki języka źródłowego np.: liczby, słowa kluczowe, operatory i identyfikatory, nawiasy okragłe, itd.. 15

16 ANALIZA LEKSYKALNA Analiza leksykalna zwana jest także skanowaniem lub analizą liniową. Głównym zadaniem analizy leksykalnej jest grupowanie znaków strumienia wejściowego w symbole leksykalne inaczej zwane token-ami. 16

17 Przykład Dana jest funkcja w języku C++: int funkcja (int s) { return s+s; } 17

18 Przykład Tokeny to inaczej elementarne składniki języka źródłowego np.: liczby, słowa kluczowe, operatory i identyfikatory, nawiasy okragłe, itd.. 18

19 PRZYKŁAD Leksemy – są to ciągi znaków, które tworzą symbole leksykalne; Wzorzec – to przepis na konstrukcję tokena: może to być ciąg znaków podkreśleń, małych, dużych liter, a także cyfr; Atrybuty – czyli wartości leksykalne, które czasem pojawiają się przy tokenach. 19

20 PRZYKŁAD ))) s[ _a-zA-Z][ _a- zA-z0-9]* sIDENT int KWD_INT ((( funkcja[ _a-zA-Z][ _a- zA-z0-9]* funkcjaIDENT int KWD_INT ATRYB.WZORZECLEKSEM TOKEN 20

21 PRZYKŁAD s[_a-zA-Z][_a- zA-z0-9]* sIDENT s[ _a-zA-Z][ _a- zA-z0-9]* sIDENT ++OP_PLUS return KWD_RET {{{ ATRYB.WZORZECLEKSEM TOKEN 21

22 PRZYKŁAD }}} ;;; ATRYB.WZORZECLEKSEM TOKEN 22

23 ANALIZA Analiza leksykalna; Analiza składniowa; Analiza semantyczna; 23

24 ANALIZA SKŁADNIOWA Analiza składniowa jest zwana także analizą hierarchiczną lub synktatyczną. Zadaniem analizy składniowej jest zbadanie, czy jednostki leksyklane tworzą poprawne konstrukcje danego języka programowania (np.: czy zachowana jest odpowiednia kolejność leksemów). 24

25 Przykład Dana jest funkcja w języku C++: int (int s) funkcja { } + s ; s return 25

26 ANALIZA Analiza leksykalna; Analiza składniowa; Analiza semantyczna; 26

27 ANALIZA SEMANTYCZNA Analiza semantyczna ma następujące zadania: Sprawdzanie programu (programu źródłowego) pod względem semantycznej zgodności z definicją języka źródłowego, w jakim program jest napisany; Zbieranie informacji do generacji kodu pośredniego; 27

28 Analiza semantyczna Kontrola zgodności typów; Kontrola przepływu sterowania; Unikalność deklaracji - kontrola statyczna; Powtórzenia nazw - kontrola statyczna; 28

29 SYNTEZA Generacja kodu pośredniego; Optymalizacja kodu; Generacja kodu wynikowego; 29

30 KOD POŚREDNI Ostatnim etapem analizy jest generacja kodu pośredniego (tzw. języka pośredniego, czasem też reprezentacji pośredniej); Redukcja kosztów głównym celem generacji reprezentacji pośredniej; 30

31 Przykład Rozważmy program napisany w języku C++, mający za zadanie wypisać na ekran pierwszych n wyrazów ciągu arytmetycznego o różnicy 10;(10,20,30,…) Instrukcja wygląda następująco: for(i=1;i

32 Przykład Przyjrzyjmy się teraz kodowi pośredniemu naszej pętli: i:=1 @loop: if i>n goto @end s:=10*i cout

33 SYNTEZA Generacja kodu pośredniego; Optymalizacja kodu; Generacja kodu wynikowego; 33

34 OPTYMALIZACJA KODU Podstawowym celem optymalizacji jest poprawa efektywności kodu wynikowego. Może ona być wykonywana na wszystkich poziomach kodu, tzn. na poziomie kodu źródłowego, pośredniego a także i wynikowego. 34

35 Przykład A oto jak wygląda kod pośredni naszego przykładu po optymalizacji: i:=1 s:=10*i @loop: if i>n goto @end cout

36 SYNTEZA Generacja kodu pośredniego; Optymalizacja kodu; Generacja kodu wynikowego; 36

37 KOD WYNIKOWY Generacja kodu wynikowego jest ostatnią fazą kompilacji; Podstawowymi problemami rozważanymi na tym etapie kompilacji są: wybór rozkazów realizujących kod; wybór rozkazów realizujących kod; Przydział rejestrów; Przydział rejestrów; 37

38 KOD WYNIKOWY Blok podstawowy – fragment kodu wykonywany zawsze od pierwszej do ostatniej instrukcji; Graf przepływu – jest grafem dwudzielnym składającym się z węzłów i krawędzi. Jego węzłami są bloki podstawowe, zaś krawędzie pokazują w jaki sposób przemieszcza się sterowanie; 38

39 Przykład Stwórzmy graf przepływu dla matematycznej funkcji signum. 39

41 Przykład-graf przepływu funkcji signum x:=a If x0 goto A B: y:=-1 goto C y=0 goto C A: y:=1 goto C C: STOP

42 Środowisko czasu wykonania W środowisko czasu wykonania jest zaopatrzony każdy program wykonywalny. Środowisko to zapewnia: - obsługę wyjątków; - obsługę wyjątków; - dynamiczny przydział pamięci; - dynamiczny przydział pamięci; - przekazywanie parametrów do podprogramów; - przekazywanie parametrów do podprogramów; - zapewnienie dostępu do nazw nielokalnych; - zapewnienie dostępu do nazw nielokalnych; 42

43 Środowisko czasu wykonania- reguły widzialności Reguły widzialności określają sposób w jaki kompilator interpretuje odwołania w programie do nazw nielokalnych. Mamy dwie możliwości: reguły widzialności statycznej – analiza tekstu programu (C, Ada); reguły widzialności dynamicznej – w trakcie wykonywania programu (Snobol, Lisp, APN) 43

44 Przykład Przyjrzyjmy się fragmentowi kodu napisanemu w C++: int k=1; main() main() {cout

45 Przykład A oto co pojawi się na ekranie w wyniku działania programu: zmienna k wynosi 1 w bloku zmienna k wynosi teraz 30 w bloku zmienna k wynosi teraz 30 znów poza blokiem k wynosi 1 znów poza blokiem k wynosi 1 45

46 Przykład A oto w jaki sposób można się odwołać do zasłoniętej nazwy globalnej w C++ int k=1; main(){ cout

47 KONIEC KONIEC WYKŁADU PIERWSZEGO