Metody realizacji języków programowania/MRJP Wykład 3

Statyczna analiza semantyczna

Statyczna analiza semantyczna ma na celu częściowe sprawdzenie poprawności kodu źródłowego programu w czasie kompilacji. Na tym etapie zakładamy, że program źródłowy został już sparsowany i zostało zbudowane drzewo składniowe. Zakładamy również, że tablice symboli zostały już zbudowane. Założenia te nie zawsze są konieczne. Niektóre kompilatory mogą przeprowadzać analizę semantyczną już w czasie parsowania kodu lub w czasie budowy tablicy symboli. Jednak takie podejście pozwala łatwiej zrozumieć tę fazę działania kompilatora.

Głównym zadaniem w czasie analizy semantycznej jest sprawdzenie, czy program może być jednoznacznie skompilowany. Pewne konstrukcje, mimo że dopuszczalne przez gramatykę języka, mogą być niepoprawne. Na przykład:

• użycie zmiennej, która nie była zadeklarowana.
• niezgodność typów przy przypisaniu.
• wywołanie nieistniejącej metody obiektu.
• odwołanie do zmiennych klasy z metod statycznych.
• użycie instrukcji w niedozwolonych miejscach, np. this poza klasą, break poza pętlą.
• przypisanie do nie l-wartości (np. do wyniku zwracanego przez funkcję lub do wyniku dodawania - więcej o l-wartościach będzie napisane w FIXME).

Zakres analizy semantycznej zależy od języka programowania. Niektóre języki dopuszczają użycie niezadeklarowanych zmiennych, niektóre sprawdzają poprawność przypisania, czy wywołania metody, w czasie wykonywania programu. Pozostawienie sprawdzania poprawności na czas wykonywania programu można nazwać dynamiczną analizą semantyczną (lub częściej dynamicznym typowaniem, gdyż sprawdzanie typów jest znaczą częścią analizy semantycznej).

Ogólnie, im więcej jest sprawdzane w tej fazie statyczniej analizy semantycznej tym łatwiej pisać skomplikowane a jednocześnie poprawne programy. Dużą część błędów, które mogłyby powstać w czasie wykonywania programu, wykrywa się na etapie kompilacji. Dzięki temu można znacznie skrócić fazę testów oprogramowania i pisać kod z mniejszą liczbą błędów.

Z drugiej strony zaawansowana statyczna analiza semantyczna wymaga pewnego nakładu ze strony programisty i ogranicza możliwości języków programowania. Sama deklaracja każdej zmiennej zabiera czas programiście piszącego kod. Dlatego możliwość używania niezadeklarowanych zmiennych jest pożądana w językach skryptowych oraz używanych do szybkiego prototypowania. Języki z brakiem statycznego sprawdzania poprawności typów (w szczególności języki obiektowe, jak smalltalk czy python) są bardziej elastyczne. Pozwalają na skupienie się na samym zadaniu do rozwiązania, a nie na zmieszczeniu rozwiązania w ramach języka programowania. To z kolei ułatwia i przyspiesza projektowanie, zarówno w małych projektach jak i w dużych systemów informatycznych. Projektant języka programowania musi odpowiednio wyważyć zalety i wady statycznej analizy semantycznej.

W tym rozdziale zostaną opisane najistotniejsze elementy statycznej analizy semantycznej:

• kontrola typów,
• kontrola poprawności instrukcji,
• kontrola nazw.

Kontrola typów

Kontrola typów ma na celu sprawdzenie poprawności typów w takich konstrukcjach językowych jak:

• przypisania - typ wartości przypisywanej musi być zgodny z typem elementu do którego przypisujemy,
• operacje arytmetyczne - wartości, do których używany jest operator arytmetyczny, muszą zgadać się z rodzajem operatora.
• wywołania funkcji - typy parametrów funkcji przy jej wywyłaniu muszą zgadzać się z typami zadeklarowanymi,
• odwołania do pól rekordu - rekord, do którego się odwołujemy, musi mieć pole podanej nazwie,
• wywołania metod obiektu - obiekt musi być klasy, która zawiera metodę, która jest wywoływana.

Zgodność typów nie oznacza, że typy są identyczne, ale, że operacja może być zastosowana dla tych typów. W dalszej części tego rozdziału przedstawione będą rodzaje typów, ich zgodność oraz kontrola ich poprawności.

System typów

Różne języki programowania mają różne systemy typów. Nie wszystkie będą zawierały wszystkie z omówionych niżej typów, a niektóre będą miały system typów bardziej rozbudowany. Typy obejmują:

• typy arytmetyczne
• wskaźniki i referencje
• rekordy
• obiekty
• tablice
• funkcje

Typy arytmetyczne

Typy arytmetyczne są przeznaczone do bezpośrednich operacji przez procesor przez procesor lub maszynę wirtualną. Obejmują one liczby całkowite (1, 2, 4, 8 bajtów), zmiennopozycyjne (4, 8, 10 bajtów) i znaki (1 lub 2 bajty). Nie wszystkie języki programowania dopuszczają typy o wszystkich rozmiarach, a niektóre mogą dopuszczać nawet większe rozmiary. Procesor lub maszyna wirtulana posiada zwykle instrukcje do odczytywania tych wartości z pamięci, wykonywania na nich operacji (dodawanie, mnożenie, etc.) i zapisywanie w pamięci. Czasem jednak nie musi być to prawdą. Na przykład przy kompilacji na architektury bez możliwości obliczeń zmiennopozycyjnych dodawanie dwóch liczb zmiennopozycyjnych może być zamienione na wywołanie odpowiedniej metody.

Wskaźniki i referencje

Referencje to małe obiekty, które przechowują informację o dostępie do innej wartości (np. wartości zmiennej lub obiekt) - wskazują na nią. Dzięki referencji można mieć dostęp do wskazywanej wartości. Zwykle wystarczającą informacją o wskazywanej wartości jest jej adres w pamięci.

Wskaźniki są tym samym co referencje, ale tym razem zakłada się, że przechowują wyłącznie adres pamięci pod którym zapisana jest inna wartość. Niech, na przykład, pod adresem 0x11111111 będzie zapisana zmienna x. Niech x będzie równe 2. Jeśli zmienna w jest wskaźnikiem na x to jej wartość będzie równa 0x11111111. Mając dostęp do zmiennej w możemy odczytać wartość zmiennej x. Jeśli teraz dokonamy przypisania:

x = 3;

to korzystając z tej samej zmiennej w możemy odczytać nową wartość równą 3.

Wskaźniki (i referencje) mogą mieć różny typ: wskaźnik na liczbę całkowitą na liczbę zmiennopozycyjną, na obiekt, element tablicy.

Referencje i wskaźniki to różne nazwy na tą samą rzecz. Jedyna różnica jest taka, że mówiąc wskaźnik mamy na myśli tylko adres w pamięci, a mówiąc referencja, być może również jakiś inny rodzaj dostępu.

Niektóre języki programowania, na przykład C++ rozróżniają między wskaźnikami a referencjami i przypisują im nieco różną składnię i semantykę. Na przykład w C++ referencje są niezmienialne, tzn. nie można zmienić adresu na który wzkazuje zainicjalizowana referencja. W innych, jak Java jest tylko jeden rodzaj i nazywa się je referencjami (słowo wskaźnik nie jest używane wśród programistów Javy).

Rekordy

Rekordy (zwane także strukturami lub krotkami) to złożone typy, które zawierają pola o innych typach. Na przykład konstrukcja z języka C:

struct A {
   int I;
   double D;
};

definiuje typ rekordowy A, który zawiera dwa pola: liczbę całkowitą I oraz liczbę zmiennopozycyjną D.

Rekord grupuje wartości różnych typów i pozwala na przechowywanie tych wartości w pojedynczej zmiennej. Odwołanie do poszczególnych pól rekordu jest wykonywane przez podanie nazwy pola (czasem numeru pola), np. a.I w języku C oznacza wzięcie pola I ze zmiennej a, która jest typu rekordowego.

Rekordy mogą zawierać pola o dowolnych typach. Szczegóły są uzależnione od języka programowania.

Obiekty

Obiekty są jak rekordy, ale mogą przechowywać funkcje (zwane metodami). Z wnątrza takiej funkcji jest dostęp do pól obiektu, z którego funkcja została wywołana. Główną techą obiektów jest to, że ich typy - klasy - mogą dziedziczyć po innych klasach.

Tablice

Tablice to ciągły obszar pamięci zawierający kolejne instancje typu tablicy. Na przykład tablica 100 liczb całkowitych to obszar pamięci zawierający kolejno 100 liczb całkowitych. Mogą być tablice obiektów, referencji, tablic.

Funkcje

Niekóre języki dopuszczają typy funkcyjne, czyli przypisywanie funkcji do zmiennej.

Konwersja typów

Wartości niektórych typów mogą w pewnych sytuacjach być konwertowane do wartości innego typu. Na przykład jeśli oczekujemy liczby całkowitej 4-bajtowej, a mamy 2 bajtową to możemy rozszerzyć ją o brakujące dwa bajty nie gubiąc przy tym żadnej informacji.

Taka niejawna konwersja typów zależy od kompilatora. Często obejmuje ona:

• konwersję liczb całkowitych do zmiennoprzecinkowych
• konwersja liczb całkowitych do liczb całkowitych o większej precyzji
• konwersja liczb zmiennoprzecinkowych do zmiennoprzecinkowych o większej precyzji
• konwersja typu obiektu do nadklasy (gdyż podklasa może być użyta wszędzie tak, gdzie oczekujemy nadklasy

Dobrze zaprojektowany język powinien zabraniać niejawnej konwersji przy której może wystąpić utrata informacji.

Przy sprawdzaniu typów, przed zgłoszeniem błędu niezgodności typów kompilator powienien zawsze sprawdzić, czy podany typ może być poddany konwersji niejawnej. Może również zajść sytuacja, w której konwersja jest możliwa na dwa różne sposoby. Wtedy semantyka dobrze zaprojektowanego języka powinna określać priorytety konwersji typów lub określać, że taka niejednoznaczność jest błędem.

Oprócz niejawnej konwersji typów języki programowania często pozwalają programiście na jawną zmianę typu elementu. W przypadku konwersji zmiennej rzeczywistej na całkowitą oznacza to utratę precyzji (ale zaakceptowaną przez programistę, gdyż jawnie zaznaczył ją w programie). W przypadku konwersji typów obiektów (zwane rzutowaniem) może to prowadzić do błędów, gdy konwertujemy typ obiektu na klasę całkowiecie nie związaną z poprzednią klasą. Takie błędy nie są możliwe do wykrycia na etapie kompilacji. Projektant języka ma możliwość sprawdzenia takiego rzutowania w czasie wykonania programu. Takie podejście zostało zastosowane w języku Java. Pomaga to w wykryciu błędów, ale jednocześnie spowalnia nieco wykonanie programu. Z kolei w C++ poprawność takiego rzutowania nie jest sprawdzana. Dzięki temu kod jest szybszy, ale istnieje ryzyko pojawienia się trudnych do lokalizacji błędów.

Sprawdzanie poprawności typów

Sprawdzanie poprawności typów polega na przejściu drzewa składniowego, sprawdzeniu w każdym węźle, czy jego operacja może być zastosowana do typów dzieci tego węzła i w końcu określeniu typu samego węzła. Przy przechodzeniu drzewa korzysta się z tablicy symboli do określenia typów zmiennych, funkcji, pól rekordów, etc.

Aby lepiej zrozumieć analizę semantyczną spójrzmy na prosty przykład. Chcemy sprawdzić fragment drzewa odpowiadający instrukcji

x = y + 5;

W tablicy zaczynamy od liści drzewa składniowego. Dla zmiennych x i y typy sprawdzamy w tablicy symboli. Jeśli x lub y nie zostało zadeklarowane to zgłaszamy błąd niezadeklarowanej zmiennej. Przypuśćmy, że typem x jest double, czyli liczba zmiennoprzecinkowa podwójnej precyzji, a typem y jest int, czyli liczba całkowita. Typem węzła odpowiadającego stałej 5 jest również int. Sprawdzamy węzeł '+': typami dzieci tego węzła są int oraz int, więc operacja dodawania może być przeprowadzona. Wynikiem jest int. Sprawdzamy węzeł '=' (przypisanie): typem lewej strony jest double, a prawej int. Zakładamy, że nasz kompilator pozwala na przypisanie zmiennej całkowitej do zmiennoprzecinkowej więc całą instrukcję uznajemy za poprawną. Jako typ całości bierzemy double, czyli typ zmiennej na którą przypisujemy (jest to semantyka wzięta z języka C, który dopuszcza przypisania w postaci x = y = 1; alternatywnie moglibyśmy takich przypisań zabronić i jako typ wyniku wziąć void - specjalny typ, który nie niesie żadnej wartości).

Na powyższym przykładzie widzimy, że analiza semantyczna jest dość skomplikowana, ale można ją rozbić na małe fragmenty - każdy odpowiada pojedynczemu węzłowi w drzewi składniowym.

W podpunktach niżej omówione zostaną reguły odpowiadające pewnym węzłom w drzewie składniowym.

Przypisania

Przy przypisaniach typ wartości, którą przypisujemy musi być zgodny z typem elementu do kórego przypisujemy. Zgodność w tym przypadku może być ścisła - ten sam typ, lub może być dozwolona niejawna konwersja typów. Konwersja pozwala na przypisanie na przykład wartości całkowitej na liczbę zmiennopozycyjną, wartości całkowitej na ciąg znaków (dostaniemy liczbę zapisaną w kodzie ASCII) lub obiektu na zmienną o typie będącym nadklasą typu obiektu (w językach obiektowych wszędzie, gdzie można użyć pewnej klasy, można użyć też jej podklasy, więc takie przypisanie ma sens

Operacje arytmetyczne

W operacjach arytmentycznych wartości, do których używany jest operator arytmetyczny, muszą pasować do rodzaju operatora. Na przykład pomnożenie dwóch liczb całkowitych jest dozwolone, a pomnożenie dwóch stałych napisowych nie.

Wywołania funkcji

Przy wywołaniach funkcji typy parametrów muszą zgadzać się z typami określonymi w deklaracji funkcji. Jako wynik wywołania funkcji bierze się typ zwracany przez funkcję.

Odwołania do pól rekordu

Przy odwołaniach do pól rekordu należy przede wszystkim sprawdzić, czy element, do którego pola się odwołujemy jest na prawdę rekordem (jeśli jest on np. liczbą całkowitą to takie odwołanie jest błędne) oraz, czy taki rekord rzeczywiście zawiera pole o tej nazwie. Nazwy pól rekordów są dostępne w tablicy symboli.

Wywołania metod obiektu

Analiza jest taka jak w przypadku odwołania do pól rekordu oraz wywołaniu funkcji.

Równość typów FIXME

Przy sprawdzaniu poprawności typów trzeba sprawdzić, czy typ węzła jest taki jak oczekujemy (np. taki sam jak typ parametru funkcji, która jest wołana na wyrażeniu). Trzeba więc porównać typy. W przypadku typów arytmetycznych wystarczy sprawdzić, czy nazwa typu jest taka sama. W przypadku typów rekordowych są dwie możliwości:

• równoważność strukturalna
• równoważność przez nazwę

Równoważność strukturalna sprowadza się do porównania, czy rekordy mają takie same pola. Równoważność przez nazwę występuje gdy możemy robić aliasy dla typów. Takie aliasy, przy równoważności przez nazwę, będą oznaczały różne typy. Aby zbadać równoważność strukturalną trzeba rekurencyjnie sprawdzić wszystkie pola (kolejność deklaracji pól też jest ważna). Rekurencyjnie, bo rekord może mieć pola także typu rekordowego.

Przeciążanie funkcji FIXME

Funkcje o tej samej nazwie lecz różnych typach parametrów to funkcje przeciążone. Przykład: operator + działający na intach lub double lub float lub char, .... Przeciążać czasem można też typ wartości zwracanej z funkcji.

W przypadku przeciążania typów parametrów wystarczy przy wywołaniu sprawdzić jakie konwersje typów są dozwolone i która z funkcji może być wywyłana przy minimalnej liczbie konwersji.

Jeśli przeciążamy wartość zwracaną to zamiast typów wyrażeń wyliczamy zbiory możliwych typów (możemy mieć np funkcję Date date() i int date()). Następnie kontynuujemy analizę semantyczną. Jeśli natrafimy na użycie wartości, dla którego niektóre typy są niepoprawne (np date() + 4 nie będzie działać z typem string) to zaznaczamy te niepoprawne typy. Na końcu przechodzimy drzewo składniowe jeszcze raz, eliminując niepoprawne użycia. Jeśli na końcu wyjdzie, że w pewnym miejscu możemy użyć dwóch z możliwych funkcji to zgłaszamy błąd bądź wybieramy jedną z nich na podstawie jakichś reguł.

szablony (c++) i generyki (java)

???

Języki funkcyjne i wnioskowanie typów

• Zmienne typów;
• unifikacja, etc.

reszta

Kontrola przepływu sterowania

• break - sprawdzamy, czy break jest wewnątrz bloku switch, for, while, itp.
• goto - sprawdzamy, czy etykieta jest zadeklarowana
• this - tylko w klasie

kontrola nazw (unikalności nazw identyfikatorów, bloków, etc.)

• czy ta sama nazwa nie została użyta w różnych kontekstach (np. jako nazwa funkcji i nazwa typu rekordowego - niektóre języki wszak dopuszczają takie użycia)
• słowa kluczowe - czy jako identyfikatory nie zostały wzięte słowa kluczowe (niektóre języki wszak to dopuszczają)
• etykiety dla goto, case - czy etykiety dla goto i case są unikalne

kontrola dostępu

Sprawdza się użycie zmiennych klasowych.

• próby czytania zmiennych prywatnych spoza klasy
• próby czytania zmiennych chronionych spoza podklas lub pakietu

• próby zapisywania zmiennych tylko do odczytu (finalnych)

L-wartości

Przpisania mogą być wykonane tylko do L-wartości (L-wartością nie jest np. wartość zwracana z funkcji. Przekazywanie paraemtru przez zmienną może dotyczyć tylko L-wartości.

inne pomysły

• Czy przy tworzeniu nowego obiektu typu tablicowego został podany rozmiar.
• czy klasa tworzona nie jest abstrakcyjna
• czy nie ma cykli w hierarchii klas
• czy nadklasa nie jest finalna
• czy w nadklasie są metody, które się przedefiniowuje. czy są wirtualne, czy zwracany typ jest taki sam
• czy typ przy return zgadza się z typem funkcji

test wiki

tabela

Uzupelnij tytul

a1	b1	c1
a2	b2	c2

podrozdz1

podrozdz

Przykład:

x = y
a = x + y
b = a + x

link martwym kodem.

Lista punktowana

• ala ma kota
  • aaa

adsf$\alpha +\sqrt{(\frac{4}{b})}$bold Italic

internal link

[external link]

Plik:An image

No wiki formating

--Mbiskup 10:41, 22 lip 2006 (CEST)Mój podpis

i = 0 
do { 
  j = 4 * i
  i = i + 1 
} while (i < 20)

Bibliografia

1. elem2