1 Wstęp do programowania Wykład 9Gramatyki i języki formalne
2 Języki naturalne vs. języki formalneJęzyki naturalne, czyli języki którymi posługują się ludzie, są niejednoznaczne. Wiele pozostawiają interpretacji. Często dwie osoby różnie interpretują to samo zdanie. Komunikacja z komputerem jest o tyle trudniejsza, że nie pozostawia miejsca na interpretacje, czy domysły. Dlatego stworzono specjalne mechanizmy do tworzenia języków formalnych, którymi w szczególności są języki programowania.
3 Struktura języka formalnegoPodstawą każdego języka formalnego jest alfabet, którego elementy nazywane są symbolami. Cechą charakterystyczną języków, w szczególności języków formalnych, jest to, że pewne napisy (ciągi symboli) rozpoznawane są jako poprawne i dobrze zbudowane. O tych napisach mówimy, że należą do języka. O tym, czy dany napis należy do języka decyduje gramatyka tego języka. Gramatyka języka jest systemem formalnym, który w oparciu o pewne reguły pozwala wygenerować wszystkie napisy należące do języka.
4 Przykład gramatyki zdanie ―> podmiot orzeczenie podmiot ―> kotypodmiot ―> psy orzeczenie ―> jedzą orzeczenie ―>śpią Zdanie składa się z podmiotu i występującego po nim orzeczenia. Podmiot jest albo słowem „koty” albo słowem „psy”. Orzeczenie jest albo słowem „śpią” albo słowem „jedzą”. zdanie, podmiot i orzeczenie to symbole pomocnicze, koty, psy, jedzą i śpią to symbole końcowe.
5 Przykład gramatyki zdanie ―> podmiot orzeczenie podmiot ―> koty podmiot ―> psy orzeczenie ―> jedzą orzeczenie ―>śpią Każdy powyższy wiersz nazywamy produkcją lub regułą. zdanie to symbol początkowy, zwany też aksjomatem, gramatyki. Język gramatyki, to każdy ciąg symboli końcowych, które można wyprowadzić z symbolu początkowego stosując produkcje. Język generowany przez powyższą gramatykę: „koty jedzą”, koty śpią”, psy jedzą”, psy śpią.
6 Definicje Słowem nad alfabetem X nazywamy dowolny ciąg, którego elementy należą do X. Dopuszczamy słowo puste, czyli ciąg symboli o długości 0. Słowo puste oznaczamy przez ε. Zbiór wszystkich słów nad alfabetem X (łącznie ze słowem pustym) oznaczamy przez X*.
7 Formalna definicja gramatykiGramatyką formalną nazywamy czwórkę G=
8 Język generowany przez gramatykęSłowo s jest wyprowadzalne w gramatyce G=
9 Przykład L(G) ={a, aa, aaa,…} = {a}*\ {ε}.Niech G=
10 Klasyfikacja gramatyk (Chomsky)Wszystkie gramatyki można podzielić na kilka klas w zależności od warunków nałożonych na występujące w nich produkcje. Gramatyki klasy 0 Nie nakładamy żadnych specjalnych warunków na produkcje, tzn. każda produkcja jest postaci u ―> v gdzie u ϵ (TﮞN)*\{ε}, natomiast v ϵ (TﮞN)*.
11 Klasyfikacja gramatyk (Chomsky)Gramatyki klasy 1 (lub gramatyki kontekstowe) Produkcje mają postać uAw ―> ubw, gdzie u,w ϵ (TﮞN)*, A ϵ N, b ϵ (TﮞN)*\{ε}. Gramatyki klasy 2 (lub gramatyki bezkontekstowe) Produkcje mają postać A ―> b, gdzie A ϵ N, b ϵ (TﮞN)*\{ε}. Gramatyki klasy 3 (lub gramatyki regularne) Wszystkie produkcje mają postać A ―>bB (prawostronnie regularne) lub wszystkie produkcje mają postać A ―>Bb (lewostronnie regularne), gdzie A ϵ N, B ϵ Nﮞ{ε} oraz b ϵ T*\{ε}.
12 Relacje między klasami gramatykGramatyki klasy 0 Gramatyki kontekstowe Gramatyki regularne Gramatyki bezkontekstowe
13 Problem należenia Dla danej gramatyki G i słowa s stwierdzić, czy sϵ L(G). Powyższy problem jest rozstrzygalny dla języków klasy 1, 2 i 3. Nie jest rozstrzygalny dla języków klasy 0.
14 Notacja BNF (Backus-Naur Form)Służy do zapisu produkcji gramatyk bezkontekstowych. Została wprowadzona w latach 50 ubiegłego wieku przez Johna Backusa i była po raz pierwszy użyta do opisu języka programowania Algol 60 przez Petera Naura.
15 Notacja BNF Symbole pomocnicze (nieterminalne) są to dowolne napisy ujęte w nawiasy < oraz >. Symbole terminalne tonapisy nie ujęte w nawiasy < >. Symbol ―> występujący w produkcjach zastępujemy symbolem ::=. Symbol (pomocniczy) występujący w pierwszej produkcji jest symbolem początkowym (aksjomatem).
16 Przykład zdanie ―> podmiot orzeczenie podmiot ―> kotypodmiot ―> psy orzeczenie ―> jedzą orzeczenie ―>śpią
17 Notacje Zamiast
18 Przykład Identyfikator:ciąg liter i cyfr zaczynający się od litery (za literę uważamy również symbol _ ). Gramatyka:
19 Przykład Zdefiniować L={anbmanbm: n,m>0}.
20 Pojęcie wywodu Niech G=
21 Przykład Niech G=
22 Przykład (c.d.) P={S ―>ab, S ―>aSb}Jak pokazać, że L(G)={anbn: n≥1}? Dla każdego n≥1 można wyprowadzić an bn. Dowód: n-1 razy S ―>aSb i raz S ―>ab. Nic innego nie można wyprowadzić. Dowód: Jedyna możliwa sekwencja produkcji prowadząca do słowa składającego się z symboli terminalnych (a i b) to k razy produkcja S ―>aSb oraz raz produkcja S ―>ab.
23 Drzewo wywodu S ―>ab, S ―>aSb S a S b a S b a b
24 Niejednoznaczność (a*b) +c a* (b+c)
25 Języki regularne Języki regularne są to języki generowane przez gramatyki regularne. Każda gramatyka lewostronnie regularna może być przekształcona na równoważną jej gramatykę prawostronnie regularną i odwrotnie. Języki regularne mają wiele „dobrych” własności. W szczególności bardzo łatwo stwierdzić, czy dany napis należy do języka generowanego przez gramatykę regularną. Gramatyka regularna jest jednym ze sposobów definiowania języków regularnych. Innym sposobem są wyrażenia regularne .
26 Wyrażenia regularne Niech V będzie skończonym alfabetem. Wyrażenia regularne nad V tworzymy według następującego schematu: Ø i ε są wyrażeniami regularnymi. Każdy symbol alfabetu jest wyrażeniem regularnym. Jeśli A i B są wyrażeniami regularnymi, to A|B i AB są wyrażeniami regularnymi. Jeśli A jest wyrażeniem regularnym, to A* jest wyrażeniem regularnym. Żaden inny napis nie jest wyrażeniem regularnym.
27 Języki definiowane przez wyrażenia regularneØ reprezentuje język pusty. ε reprezentuje język {ε}. Symbol a z alfabetu reprezentuje język {a}. Jeśli A i B są wyrażeniami regularnymi reprezentującymi języki LA i LB, to A|B reprezentuje sumę LA ﮞLB , AB reprezentuje wszystkie ciągi znaków powstałe przez dopisanie do ciągu z LA ciągu z LB. Jeśli A jest wyrażeniem regularnym reprezentującym język LA, to A* reprezentuje zbiór ciągów znaków powstały przez wypisywanie dowolną liczbę razy elementów zbioru LA i dodatkowo słowo puste.
28 Przykłady V={a,b,c} Wyrażenie Język a {a} ab|bc {ab,bc}ab*c {ac, abc, abbc, abbbc,…} a(bc)*a {aa, abca, abcbca,… { "@context": "http://schema.org", "@type": "ImageObject", "contentUrl": "http://slideplayer.pl/9088516/27/images/28/Przyk%C5%82ady+V%3D%7Ba%2Cb%2Cc%7D+Wyra%C5%BCenie+J%C4%99zyk+a+%7Ba%7D+ab%7Cbc+%7Bab%2Cbc%7D.jpg", "name": "Przykłady V={a,b,c} Wyrażenie Język a {a} ab|bc {ab,bc}", "description": "ab*c {ac, abc, abbc, abbbc,…} a(bc)*a {aa, abca, abcbca,…", "width": "800" } 29 Problem Dane jest wyrażenie regularne A. Skonstruować algorytm rozstrzygający, czy dane słowo należy do języka reprezentowanego przez A. { "@context": "http://schema.org", "@type": "ImageObject", "contentUrl": "http://slideplayer.pl/9088516/27/images/29/Problem+Dane+jest+wyra%C5%BCenie+regularne+A..jpg", "name": "Problem Dane jest wyrażenie regularne A.", "description": "Skonstruować algorytm rozstrzygający, czy dane słowo należy do języka reprezentowanego przez A.", "width": "800" } 30 Diagramy Wyrażenie Diagram a a AB A B A A|B B A* A { "@context": "http://schema.org", "@type": "ImageObject", "contentUrl": "http://slideplayer.pl/9088516/27/images/30/Diagramy+Wyra%C5%BCenie+Diagram+a+a+AB+A+B+A+A%7CB+B+A%2A+A.jpg", "name": "Diagramy Wyrażenie Diagram a a AB A B A A|B B A* A", "description": "Diagramy Wyrażenie Diagram a a AB A B A A|B B A* A", "width": "800" } 31 Przykład {ab, aab, aaab,aaaab, …} aa*b a a b
32 Funkcja w C++ bool czy_nalezy(string wyr) { char ch: ch=wyr[0];if (ch!='a') return false; else i++; ch=wyr[i]; while (ch=='a'){i++; ch=wyr[i];} if (ch !='b') return false; else i++; if (i==wyr.length()) return false; else return true; }