Języki programowania-przyjęte minimum

1. Języki programowania-przyjęte minimum

Języki programowaniaprzyjęte minimum
operowanie na zamiennych i strukturach
danych
wykonywanie instrukcji warunkowej
wykonywanie instrukcji iteracyjnej (ew.
poprzez definiowanie rekurencji)
Nie każdy język to ma (HTML, niektóre
skryptowe). Nie każdy ciąg instrukcji to
programowanie.

2. Składnia języków programowania

skupimy się na składni konkretnej tzn.
opisującej za pomocą tzw. gramatyk
bezkontekstowych jakie ciągi znaków tworzą
w danym języku poprawne konstrukcje
uzupełnieniem tego co wypływa z gramatyki
języka są jeszcze dodatkowe warunki
wpływające na jego składnie
podstawowe kategorie składniowe w każdym
języku programowania to stałe, zmienne,
wyrażenia i instrukcje.

3. Konstrukcja języka metodą gramatyk formalnych

gramatyki te stworzyły N.Chomsky
bezskutecznie próbując opisać nimi
bogactwo języka naturalnego
(angielskiego)- okazały się one natomiast
znakomitym narzędziem do opisu języków
programowania, zwłaszcza część teorii
Chomsky’ego dotycząca tzw. gramatyk
bezkontekstowych

4. Konstrukcja języka programowania

na zasadach wynikłych z teorii Chomskyego
buduje się definicje innych typów danych,
wyrażeń, a także konstrukcji programistycznych
instrukcji
cały taki zbiór z dbałością o jednoznaczność
gramatyk definiuje nam język programowania
poprawność tej definicji gwarantuje nam
uzupełnienie gramatyki o zbiór odpowiednich
reguł semantycznych jednoznacznie określających
interpretację (przyjmowane wartości) dla
poszczególnych symboli i wyrażeń

5. Przykład gramatyki definiujacej liczby całkowite

Przyjmujmy, że w dowolnym języku
programowania liczba całkowita to ciąg
cyfr poprzedzonych znakiem + lub –
Mamy wówczas:
G={ {S,Z,C,L}, {-,+,0,1,2,3,4,5,6,7,8,9},
{C::=0|1|2|3|4|5|6|7|8|9,S::=L|ZL,Z::=+|-,
L::=C|LC},S}

6. Reguły semantyczne-wybrane uwagi

gramatyka określa tylko zasady „produkowania” napisów
czyli języka (zbioru napisów)
napisy można jednak różnie interpretować, czy np. 12 to
liczba 12, czy też zapisany koło siebie układ cyfr 1 i 2
oznaczający np. liczbę w układzie trójkowym
jednoznaczność interpretacji języka wymaga
wprowadzenia reguł semantycznych dla każdej produkcji

7. Semantyka języka programowania

służy do zdefiniowania znaczenia fraz
składniowych (czyli znaczenia programów)
w szczególności mamy semantykę
operacyjną (jak obliczenia dają wynik),
semantykę denotacyjną (opisuje znaczenie
całych konstrukcji języka – jak prowadzą
do określonego działania) oraz semantykę
aksjomatyczną (własności konstrukcji
językowych)

8. Szczegółowe notacje używane do opisu gramatyk bezkontekstowych

notacja użyta przykładowo do opisu produkcji w
definicji wyrażenia całkowitoliczbowego nosi
nazwę notacji BNF (Backusa-Naura) i stanowi
właśnie zestaw reguł produkcji
używana do definicji składni języków
programowania, a także protokołów
komunikacyjnych
przy jej pomocy opisano składnię takich języków
programowania jak Fortran (Backus), czy Algol
(Naur)

9. BNF-przykład

<zero>::=0
<cyfra niezerowa>::=1|2|3|4|5|6|7|8|9
<cyfra>::=<zero>|<cyfra niezerowa>
<ciąg cyfr>::=<cyfra>|<cyfra><ciąg cyfr>
<liczba naturalna>::=<cyfra>|<cyfra
niezerowa><ciąg cyfr>

10. Diagramy syntaktyczne-graficzna postać reguł produkcji, liczba naturalna

zero
)0
cyfra niezerowa
1
2
.....9

11. Diagramy syntaktyczne-graficzna postać reguł produkcji, liczba naturalna

cyfra
zero
cyfra niezerowa
ciąg cyfr
cyfra
cyfra

12. Diagramy syntaktyczne-graficzna postać reguł produkcji, liczba naturalna

liczba naturalna
cyfra
cyfra niezerowa
ciąg cyfr

13. Typy instrukcji

Instrukcja pusta
Instrukcja złożona –jako zamknięty blok innych instrukcji
Instrukcja przypisania
a:=b (różne konwencje znaku
przypisania)
Instrukcja warunkowa np.
if (warunek, test logiczny) then
(instrukcje 1) else (instrukcje 2) –
niekiedy brak słów then lub else
Stosowane operatory porównań oraz logiczne
typu AND, OR lub NOT
Instrukcje iteracyjne (powtórzeń, pętli) – różne składni
zależnie od typu iteracji (znana liczba powtórzeń, liczbę
powtórzeń określa warunek)
Instrukcje wejścia-wyjścia
Instrukcje wywołania procedur lub funkcji

14. Przykład wykorzystania BNF do opisu składni instrukcji-instrukcja warunkowa

<instrukcja warunkowa>::=<instrukcja
warunkowa bez else>|<instrukcja
warunkowa z else>
<instrukcja warunkowa bez else>::= if
<wyrażenie logiczne> then <instrukcja>
<instrukcja warunkowa z else>::= if
<wyrażenie logiczne> then <instrukcja, ale
jeśli warunkowa to tylko z else> else
<instrukcja>.

15. Analiza leksykalna

analiza kodu na podstawie dostarczonych
reguł (czyli skaner dokonujący tego dla
kodu jest oprogramowany wcześniej)
następuje klasyfikacja poszczególnych
elementów łańcucha wejściowego i
tworzony jest jego tzw. rozbiór leksykalny
np. wyrażenie x+2*y jest rozbijane na stałe i
identyfikatory oraz osobno operatory

16. Analiza składniowa (syntaktyczna)

analizowany jest zbiór leksykalny w oparciu
o gramatyki bezkontekstowe dla danego
języka (parsowanie)
finałem jest tzw. drzewo wyprowadzeń
(drzewo parsowania)

17. Drzewo parsowania dla x+2*y

wyrażenie
wyrażenie
iden
operator
wyrażenie
wyrażenie operator
stała
+
iden
x
y
*
2

18. W tle odbywa się też analiza semantyczna

poddając znaczenie słów (wyrażenie,
identyfikator), symboli (operatory)
prowadzi do realizacji obliczeń
dodatkowo kontroluje zgodność typów
zmiennych (czy działanie ma sens w sensie
tych typów)