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ą.

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

System typów

Wyróżniamy typy:

• arytmetyczne (całkowity - int, short; zmiennopozycyjny - float, double; znakowy - char) - obiekt bezpośreniej manipulacji procesora
• wskaźniki i referencje - wskaźniki i referencje to adresy w pamięci wskazujące na lokację innego elementu (np. tablicy, obiektu, liczby typu arytmetycznego).
• struktury, rekordy, krotki, obiekty - typy złożone; struktury i rekordy zawierają pola, z których każde może mieć własny typ. Obiekty mogą dodatkowo zawierać metody
• tablice - ciągły obszar pamięci zawierający kolejne instancje typu.
• funkcje

• cykle przy deklarowaniu typów (wskaźniki lub np. drzewa funkcyjne) (?)

sprawdzanie poprawności typów

Wyrażenia:

Dla każdego wyrażenia należy wyliczyć jego typ:

• zmienne: typ zmiennej
• wyr arytmetyczne: int + int -> int; double + int -> double. Więcej o tym w punkcie konwersja typów. Trzeba sprawdzić, czy operacje są przeprowadzane na poprawnym typie.
• wywołania funkcji: sprawdzić typy parametrów, wybrać funkcje (więcej w wyborze funkcji w punkcie przeciążanie funkcji'. Typem wyniku będzie typ zwracany przez funkcję
• odwołanie do pól obiektu, rekordu, krotki - znaleźć wpis w tablicy symboli i z tamtąd wziąć typ.

Równość typów

Przy sprawdzaniu poprawności typów trzeba sprawdzić, czy typ wyrażenia 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:

• strukturalna
• 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.

konwersja typów

typy arytmetyczne i proste (int->double, etc)

Przy operacjach arytmetycznych często występuje niejawna konwersja typów. Np. można dodać int i double i wynikiem będzie double (bo ma większą precyzję). Można też wywołać funkcję ,która oczekuje double z parametrem int. Kompilator (z niektórych językach) powienien uznać taką operację za poprawną i dokonać konwersji. Generalnie przyjmuje się zasadę, żę dozwolona jest konwersja z typu o mniejszej dokładności do typu o większej dokładności (uwaga: może być dozwolona konwerja z int do float, chociaż dokładności obu typów nie da się porównać). Przy konwersji w przeciwną stronę kompilator powienien wypisać ostrzeżenie lub tego zabronić.

obiekty polimorficzne - rzutowanie

W przypadku języków obiektowych wszędzie tam, gdzie oczekuje się obiektu pewnej klasy można użyć jej podklasy. Konwersja w drugą stronę nie jest dozwolona

jawne rzutowanie

Często trzeba wykonać jawne rzutowanie. Wtedy można przypisać liczbę zmiennopozycyjną do całkowitej, referencję do referencji podklasy (takie przypisanie może być sprawdzane jedynie dynamicznie). Często języki umożliwiają rzutowanie dowolnego typu na dowolny.

Przeciążanie funkcji

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
   1. podelem1
      1. podpodelem
         1. podpodpodelem