Składnia i semantyka

Reprezentacja algorytmu wymaga użycia pewnej formy języka. Ludzie mogą wykorzystywać język naturalny (etniczny, np. polski, angielski, francuski,…) lub język obrazowy (np. algorytm składania ptaka z kwadratowego kawałka papieru [2]). Często komunikowanie się w języku naturalnym prowadzi do nieporozumień ze względu na wieloznaczność (np. słowo: „lalka”, „zamek”; zdanie: „Odwiedziny wnuków mogą być stresujące” - może oznaczać problemy, gdy nas odwiedzają, albo też, że wizyta u nich jest stresująca). Często pojawiają się także problemy dotyczące wymaganego poziomu (stopnia) szczegółowości (poziom szczegółowości należy dobierać w zależności od tego, do kogo jest adresowany algorytm, zależy od jego wiedzy, doświadczenia…). Oznacza to, że źródłem problemów jest brak precyzyjnej definicji języka (języka algorytmicznego) stosowanego do opisu algorytmu lub niewłaściwy poziom szczegółowości przekazywanej informacji [2].

W informatyce rozwiązywane są te problemy poprzez tworzenie dobrze określonego zestawu cegiełek, z których można konstruować reprezentacje algorytmów. Takie cegiełki nazywane są konstrukcjami pierwotnymi (primitives). Problemy niejednoznaczności usuwa się, przypisując pierwotnym konstrukcjom ścisłe definicje. Natomiast wymaganie, aby algorytmy opisywano za pomocą tych konstrukcji pierwotnych (cegiełek), ustanawia jednolity poziom szczegółowości [2].

Zestaw konstrukcji pierwotnych razem z zestawem reguł definiujących sposób ich łączenia ze sobą (w tym zestaw reguł budowy złożonych konstrukcji z pierwotnych konstrukcji) w celu reprezentacji bardziej złożonych obiektów składają się na język programowania [2].

Każdą konstrukcję pierwotną definiuje się za pomocą dwóch elementów [2]:

• Składni (syntax).

• Semantyki (semantics).

Składnia opisuje symboliczną reprezentację konstrukcji pierwotnej.

<Składnia>::= <opis symbolicznej reprezentacji konstrukcji pierwotnej>.

Semantyka jest znaczeniem konstrukcji pierwotnej, czyli pojęcie, które konstrukcja reprezentuje [2].

< Semantyka >::= < znaczenie konstrukcji pierwotnej, pojęcie, które konstrukcja reprezentuje>.

Na przykład, napis „powietrze”- składniowo jest ciągiem 9 symboli (liter alfabetu), a semantyką jest znaczenie tego słowa - jest to substancja lotna otaczająca kulę ziemską [2]. Zdanie „Ten kamień jest głupi” nie ma znaczenia w języku polskim (nie ma sensu).

Zestaw konstrukcji pierwotnych do reprezentacji algorytmów przeznaczonych do wykonania na komputerze można uzyskać na podstawie rozkazów maszynowych konkretnego komputera (z listy rozkazów mikroprocesora). Algorytm wyrażony na tym poziomie szczegółowości z całą pewnością pozwoliłby na otrzymanie programu, który można by wykonać na komputerze. Reprezentacja algorytmu na tym poziomie szczegółowości jest jednak żmudna (złożona) i podatna na błędy, dlatego też zwykle stosuje się pierwotne konstrukcje językowe „ z wyższego poziomu”. Każda z nich jest narzędziem abstrakcyjnym, które można zbudować, posługując się konstrukcjami pierwotnymi niższego poziomu dostępnymi w języku maszynowym komputera. Dzięki takiemu zabiegowi uzyskuje się formalny język programowania, w którym algorytmy można wyrażać na wyższym poziomie abstrakcji niż w języku maszynowym konkretnego komputera [2].

Składnia to zbiór reguł, opisujących jak wygląda poprawny program w danym języku, czyli np. [3]:

• Jak powinno się tworzyć poprawne polecenia i wyrażenia?

• Jaką postać powinny mieć struktury sterowania (if, while, for itp.)?

• Jak powinno się zapisywać deklaracje?

Jak widać z powyższego wyliczenia, jesteśmy tak bardzo przywiązani do języków imperatywnych i obiektowych, że chyba nie bardzo wyobrażamy sobie język bez poleceń, pętli while, zmiennych...

Semantyka to znaczenie wspomnianych wyżej form, czyli „co one robią”. Weźmy dla przykładu typową instrukcję warunkową [3]:

• Składnia może wyglądać tak: if "(" wyrażenie ")" instrukcja

• Semantyka jest następująca: sprawdź podane „wyrażenie” i jeśli jest prawdziwe, to wykonaj podaną instrukcję.

Powyższy opis semantyki instrukcji warunkowej jest, co prawda niezbyt formalny, ale zupełnie zrozumiały [3]:

• W ogólności byłoby dobrze, gdyby semantykę dało się łatwo odgadnąć, patrząc na składnię języka.

• Dla prostych konstrukcji tak zazwyczaj bywa; bardziej skomplikowane twory są niestety mniej oczywiste.

• Stąd potrzebne są ścisłe metody opisu i składni, i semantyki.

Na razie warto zrezygnować z wprowadzenia formalnego języka programowania. W miejsce jego można zdefiniować mniej formalny, bardziej intuicyjny system notacyjny, zwany pseudokodem.

<Pseudokod>::= <intuicyjny system notacyjny, w którym nieformalnie wyraża się koncepcje związane z opracowywanym algorytmem>.

Pseudokod można uzyskać, rozluźniając wymagania stawiane językowi formalnemu, w którym ma być wyrażona końcowa wersja algorytmu. Takie podejście stosuje się często, jeśli jest znany z góry docelowy język programowania. Pseudokod stosowany we wczesnych fazach tworzenia oprogramowania składa się ze struktur składniowo - semantycznych, które przypominają struktury występujące w docelowym języku programowania, lecz są mniej formalne.

Czym jest język i jak go opisać?

Pojęcie język jest rozumiane jako skończony zbiór symboli języka (alfabet) wraz ze zbiorem reguł łączenia (składania) poszczególnych symboli (liter /znaków alfabetu) w ciągi (słowa) i zbiorem reguł (semantycznych) nadających ciągom symboli znaczenie (sens) merytoryczne.

Język jest to, więc ogólna nazwa zdefiniowanego zbioru znaków oraz reguł lub konwencji określających sposoby i kolejności, w jakich znaki te mogą być łączone dla nadania im znaczenia w tym języku.

Język można traktować jako uporządkowaną czwórkę elementów [26]:

J = {A, W, D, Z},

gdzie: A jest alfabetem języka, W - zbiorem wyrażeń poprawnych, D - dziedzina języka, Z - znaczenie języka.

Alfabet języka jest to zbiór skończony znaków zwanych literami. Każdy ciąg skończony liter nazywamy napisem.

Zbiór wyrażeń poprawnych języka jest to pewien wyróżniony zbiór napisów w alfabecie tego języka. O tym, czy dany napis jest wyrażeniem poprawnym języka, czy też nim nie jest decydują reguły gramatyczne języka, które określają strukturę wyrażeń poprawnych. Spis tych reguł tworzy gramatykę języka (w szerokim sensie obejmuje również reguły morfologii języka). Wyrażeniem poprawnym jest, więc nie tylko zdanie ( w tym ujęciu), lecz także każdy poprawnie zbudowany wyraz. Od reguł gramatycznych nie wymaga się, aby określały sens wyrażeń, uznanych przez nie za poprawne.

Dziedzina języka jest zbiór wiadomości /informacji, którego elementy stanowią treść (sens) wyrażeń poprawnych języka. Inaczej mówiąc, dziedziną języka jest zbiór wszystkich wyrażalnych w tym języku wiadomości / informacji (może zawierać pojęcia nie wyrażalne w innych językach).

Znaczenie języka jest relacją wiążącą wyrażenia poprawne języka z elementami jego dziedziny.

Element dziedziny pozostający w tej relacji z pewnym wyrażeniem poprawnym języka nazywa się znaczeniem tego wyrażenia. Jedno wyrażenie może mieć wiele znaczeń, np. lalka, skok, zamek itp. Wiele wyrażeń może mieć to samo znaczenie, np. samochód, auto, pojazd dwuśladowy itp.; wyrażenia pozbawione sensu nie mają znaczeń. Reguły określające omawianą relację nazywamy regułami znaczeniowymi lub semantycznymi języka. Język, który jest stosowany do przedstawienia algorytmów, nosi nazwę języka algorytmicznego, a przy stosowaniu go do celów programowania, określany jest jako język programowania.

Algorytm przedstawiony w języku programowania nazywa się programem.

Programem nazywamy opis sposobu przetwarzania danych. Jest to uporządkowany zbiór (ciąg) rozkazów (instrukcji) i innych danych (struktur danych) związanych z rozkazami [36]. Program działa na podstawie algorytmu, który z kolei jest ściśle związany ze strukturami danych (obiekty proste, złożone), na których operuje tzn. [37]:

ALGORYTMY + STRUKTURY DANYCH = PROGRAMY.

Język to zbiór napisów utworzonych ze znaków z ustalonego alfabetu [3]:

• Przyjmujemy, że mamy ustalony alfabet; nazwijmy go np. Σ.

• Alfabet to skończony i niepusty zbiór liniowo uporządkowany; jego elementy nazywamy symbolami, znakami lub literami.

• Zbiór wszystkich napisów, jakie można utworzyć z symboli alfabetu Σ, oznaczamy przez Σ*.

• Każdy podzbiór zbioru Σ* to pewien język.

• Rzecz jasna, nie każdy język jest interesujący.

Mówiąc o językach programowania, chcemy takie właśnie języki móc precyzyjnie opisywać [3]:

• Jeśli za alfabet Σ przyjmiemy np. zbiór znaków ASCII, to języki programowania są pewnymi szczególnymi podzbiorami zbioru Σ*.

• Są to oczywiście nieskończone podzbiory, których nie sposób opisać przez wyliczenie elementów; potrzebne są gramatyki.

• Nas szczególnie interesują dwa rodzaje gramatyk: regularne i bezkontekstowe.

• Te pierwsze doskonale nadają się do opisu prostych elementów języka — jednostek leksykalnych, czyli rzeczy takich, jak liczby i identyfikatory.

• Te drugie są przydatne do definiowania „większych” elementów składni: różnych rodzajów instrukcji, deklaracji czy wreszcie całego programu.

• Gramatyka pozwala opisać składnię języka, jednak nic (lub prawie nic) nie mówi o jego semantyce.

• Do opisu semantyki istnieją takie narzędzia, jak gramatyki atrybutowane oraz semantyki operacyjne, aksjomatyczne i denotacyjne.

Jak zatem my będziemy opisywać języki programowania lub ich elementy?

• Składnię języków będziemy opisywali za pomocą powszechnie znanej notacji BNF, odpowiadającej gramatykom bezkontekstowym.

• Semantykę rozmaitych konstrukcji będziemy na ogół opisywali w sposób „naiwny”, czyli zwyczajnie, po polsku.

• Ironią losu jest to, że stworzone przez informatyków - teoretyków narzędzia opisu semantyki nie są zbyt chętnie stosowane w praktyce inżynierii oprogramowania...

Notacja BNF (Backus Naur Form) jest powszechnie używana właśnie do opisu składni języków programowania. Stworzona została w trakcie prac nad językami Fortran i Algol na przełomie lat pięćdziesiątych i sześćdziesiątych XX wieku

• Definicja języka w notacji BNF to zbiór reguł.

• Poszczególne reguły mają postać <symbol>  ::= <definicja symbolu>

• Sens takiej reguły jest następujący: symbol występujący po lewej stronie znaku ::= można zastąpić tym, co pojawia się po prawej stronie.

• Innymi słowy, stwierdzamy, że to, co stoi po lewej stronie, może wyglądać jak to, co stoi po prawej.

• Symbole pojawiające się po lewej stronie reguł zwane są symbolami nieterminalnymi.

• Symbole pojawiające się wyłącznie po prawej stronie to symbole terminalne.

• Generalnie symbole terminalne to symbole z alfabetu definiowanego języka, a zatem „docelowe”; symbole nieterminalne spełniają natomiast rolę pomocniczą przy jego definiowaniu.

• BNF to, zatem w istocie sposób zapisywania produkcji gramatyk bezkontekstowych.

Często stosuje się dodatkowe symbole i konwencje, upraszczające zapis

• Pionowa kreska | oznacza alternatywne warianty reguły, np.

typ ::= char | int | float | double

• Nawiasy kwadratowe [...] oznaczają opcjonalną część reguły, np.

instr_warunkowa ::= if wyr_logiczne then instr [ else instr ]

• Nawiasy klamrowe {...} oznaczają fragment, który może być powtórzony dowolnie wiele razy (być może zero razy, czyli pominięty), np.

lista_arg ::= arg { "," arg }

• Zwykłych nawiasów okrągłych (...) używa się do grupowania alternatywnych fragmentów definicji, np.

liczba_ze_znakiem ::= ("+" | "-") liczba_bez_znaku

• Jednoznakowe symbole terminalne umieszcza się w cudzysłowie, dla odróżnienia ich od symboli samej notacji BNF.

• Symbole terminalne pisze się czcionką wytłuszczoną; nie jest wówczas konieczne pisanie nawiasów kątowych wokół symboli nieterminalnych.

Chcąc opisać powtarzające się elementy, możemy stworzyć definicję rekurencyjną lub wykorzystać nawiasy klamrowe:

• Zdefiniujmy dla przykładu niepustą listę identyfikatorów, rozdzielonych przecinkami:

lista_identyfikatorów  ::= identyfikator

| lista_identyfikatorów "," identyfikator

• Alternatywnie piszemy:

lista_identyfikatorów  ::= identyfikator { "," identyfikator }

Klasyczny przykład użycia notacji BNF to opis składni notacji BNF:

składnia ::= { reguła }

reguła ::= identyfikator "::=" wyrażenie

wyrażenie ::= składnik { "|" składnik }

składnik ::= czynnik { czynnik }

czynnik ::= identyfikator

| symbol_zacytowany

| "(" wyrażenie ")"

| "[" wyrażenie "]"

| "{" wyrażenie "}"

identyfikator ::= litera { litera | cyfra }

symbol_zacytowany ::= """ { dowolny_znak } """

Zauważmy, że niektóre symbole, formalnie terminalne, są właściwie niedodefiniowanymi symbolami nieterminalnymi. Gwoli ścisłości powinniśmy, zatem dopisać:

litera ::= "A" | "B" | "C" | ...

cyfra ::= "0" | "1" | ... | "9"

dowolny_znak ::= ...

Jak widać, użyliśmy kolejnego niedodefiniowanego symbolu, a mianowicie wielokropka. Nie brnijmy jednak dalej w formalizowanie rzeczy jasnych i znanych...

Na pewno wszyscy wiedzą, jak uruchomić program napisany np. w języku C++. Dla naszych rozważań istotne jest to, że program taki musi zostać przetłumaczony na język wewnętrzny maszyny, na której program zamierzamy uruchomić. Owo tłumaczenie może być dokonane na jeden z dwóch sposobów:

• Kompilacja to przetłumaczenie całego programu „za jednym zamachem”. Otrzymujemy kod wynikowy, który (po konsolidacji, zwanej wulgarnie linkowaniem) wykonuje się bezpośrednio na maszynie docelowej.

• Interpretacja to tłumaczenie i wykonywanie programu instrukcja po instrukcji, cały czas za pomocą programu zwanego interpreterem.

• Są także formy pośrednie: kompilacja do kodu pośredniego, który jest następnie interpretowany lub ponownie kompilowany „w ostatniej chwili”. Taka forma jest bardzo często stosowana w przypadku języka Java. Daje nam to dobry kompromis między efektywnością a przenośnością kodu na różne komputery.

Nie zamierzamy zagłębiać się tu w tajniki budowy kompilatorów, czyli programów tłumaczących

• To jest temat na oddzielny wykład.

• Ponieważ jednak chcemy mówić o implementacji rozważanych mechanizmów językowych, będziemy musieli wspominać o konsekwencjach dla kompilatora (lub ewentualnie interpretera) związanych z tymi mechanizmami.

• Nie będziemy stronili od pewnych pomysłów na implementację, np. jak kompilator może przygotować wywołania polimorficzne.

• Jak już wspominaliśmy, rola kompilatora bywa trudna: musi on przetłumaczyć program napisany według jakiegoś paradygmatu na program w języku wewnętrznym komputera, czyli na raczej „toporny” program imperatywny.

Dlaczego w takim razie chcemy mówić o implementacji?

• To zdecydowanie ułatwia zrozumienie omawianych mechanizmów.

• Implementacja języka programowania, czyli, praktycznie rzecz biorąc, stworzenie kompilatora to moment, gdy semantyka języka staje się namacalna i bezwzględnie obowiązująca.

• Jeśli twórca kompilatora źle ją zrozumiał, to powstanie kompilator nieco innego języka...

Przykład

• Ten przykład pokazuje, jaki wpływ na efektywność programu może mieć (nie)znajomość semantyki języka programowania

• Rozważmy pętlę for w Pascalu i w C:

for i := 1 to length(s) do ...

for (i = 1; i <= strlen(s); ++i) ...

• Na pierwszy rzut oka pętle te powinny zachowywać się tak samo.

• Jest jednak bardzo istotna różnica: w Pascalu długość napisu s zostanie policzona tylko raz, natomiast w języku C będzie ona liczona przy każdym obiegu pętli.

• To prowadzi do fatalnego pogorszenia złożoności obliczeniowej: zamiast liniowej, mamy kwadratową zależność od długości napisu s (przy założeniu, że operacje w pętli są niezależne od tej długości).

• Nie ma, co liczyć na optymalizację wykonaną przez kompilator, gdyż ten na ogół nie może zbyt wiele zakładać o wywoływanych funkcjach.

• A zatem trzeba po prostu wiedzieć, co i gdzie można napisać, by nie trwonić czasu...

Uwagi bibliograficzne

Pisząc wykłady omawiające kwestie implementacyjne (2-4) oraz wykłady przeglądowe (5-7) korzystaliśmy z ciekawie opracowanej, rozległej tematycznie książki Sebesty „Concepts of Programming Languages”.

Wykład o rachunku lambda bazuje na „Wybranych zagadnieniach z teorii rekursji”, zaś wykład o rachunku sigma — na „A Theory of Objects” Abadiego i Cardellego. Wiele informacji do wykładów o Haskellu zaczerpnęliśmy z „Introduction to Functional Programming using Haskell” Birda, zaś do wykładów o Prologu — z „Logic, Programming and Prolog” Nilssona i Małuszyńskiego. Pozostałe pozycje ze spisu literatury również stanowiły cenne źródło informacji.

Wykaz literatury podstawowej:

1. Bertrand M. Programowanie zorientowane obiektowo, Helion, Gliwice 2005

2. Brookshear J. G. Informatyka w ogólnym zarysie. WNT, Warszawa 2003

3. http://wazniak.mimuw.edu.pl/

4. Kluźniak F., Szpakowicz S. Prolog, WNT, Warszawa 1983

5. Oficjalna strona języka CLIPS: http://www.ghg.net/clips/CLIPS.html

6. Prata S. Szkoła Programowania. Język C. Wyd. V, Helion, Gliwice 2006

7. Prata S. Szkoła Programowania. Język C++. Wyd. V, Helion, Gliwice 2006

8. Sebesta R., Concepts of Programming Languages, Addison Wesley, 2005

9. Ullman L., Liyanage M. Programowanie w języku C. Szybki startEdytuj. Błyskawiczny kurs programowania w języku C. HELION, Gliwice 2005

10. Ullman L., Singel A. Szybki start. Programowanie w języku C++. Błyskawiczny kurs tworzenia aplikacji w jednym z najpopularniejszych języków programowania. HELION, Gliwice 2007

Wykaz literatury uzupełniającej:

11. Daniluk A. C++ Builder Borland Developer Studio 2006. Helion, Gliwice 2006

12. Garbacz B., Koronkiewicz P., Grażyński A. Programowanie, koncepcje, techniki i modele. Helion, Gliwice 2005

13. Grębosz J.: Symfonia C++ standard, Edition 2000, 2005

14. Grębosz J.: Pasja C++, Oficyna Kallimach, Kraków, 2003

15. Eckel B.: Thinking in Java. Edycja polska. Wydanie IV, Helion 2006

16. Kochan S. G. Język C. Wprowadzenie do programowania. Helion 2005

17. Liberty J. C++ księga eksperta. Helion, Gliwice 1999

18. Liberty J. C++ dla każdego. Helion, Gliwice 2002

19. Liberty J., MacDonald B.: C# 2005. Wprowadzenie, Helion 2007

20. Neibauer A. R. Języki C i C++”. HELP Warszawa 1995, Wyd. IV, 2005

21. Nilsson U., Małuszyński J., Logic, Programming and Prolog, John Wiley & Sons, 1995

22. Savitch W. W tonacji C++. RM, Warszawa 2005

23. Solter N. A., Kleper S. J. C++. Zaawansowane programowanie. Helion, Gliwice 2006

24. Stasiewicz A. Wkrocz w świat programowania w C ++. Ćwiczenia praktyczne C++. Wyd. II, Helion, Gliwice 2006

25. Thinking in C++ Edycja polska BRUCE ECKEL (tłumaczenie: Imiela P.). HELION, Gliwice 2002

Wykaz literatury dodatkowej:

26. Borowiec J. i inni pod red. R. Marczyńskiego. Problemy przetwarzania informacji. WNT, Warszawa, 1970

27. Jankowscy J. i M.: Przegląd metod i algorytmów numerycznych. Część 1, WNT, Warszawa 1988

28. Majgier D. Kurs XHTML / HTML/CSS http://algorytmy.pl/doc/xhtml/

29. Maguire S. Niezawodność oprogramowania. Helion, Gliwice 2002

30. Myers G. J. Projektowanie niezawodnego oprogramowania. WNT, Warszawa 1980

31. Myers G. J.,Sandler C., Badgett T., Thomas T. M. Sztuka testowania oprogramowania. Helion, Gliwice 2005

32. Nabajyoti Brkakati. Biblia Turbo C++. Oficyna Wydawnicza LT&P

33. Oualline S. Jak nie programować w C++, czyli 111 programów z błędami i 3 działające. MIKOM, Warszawa 2003

34. Sysło M. Algorytmy. Wyd. Szkolne i Pedagogiczne, Warszawa 1997

35. Tanenbaum A. S. Organizacja maszyn cyfrowych w ujęciu strukturalnym. WNT, Warszawa 1980

36. Turski W. M. Propedeutyka informatyki. PWN, Warszawa 1989

37. Wirth N. Algorytmy + struktury danych = programy. WNT, Warszawa 1980

2

---