1 Języki formalne i gramatyki(c) Jerzy Nawrocki TPI, Wykład 6 Teoretyczne podstawy informatyki Wykład 6 Języki formalne i gramatyki Copyright, 2004 © Jerzy R. Nawrocki Języki formalne i gramatyki

2 J.Nawrocki, Języki formalne i gramatykiUlepszenia Wyrażenia regularne a gramatyki J.Nawrocki, Języki formalne i gramatyki

3 Zastosowania języków formalnych(c) Jerzy Nawrocki Zastosowania języków formalnych TPI, Wykład 6 Kompilatory dla nowych języków programowania (C#, xSQL) Generowanie kodu na podstawie modeli (UML, HRT HOOD) Przypadki testowe (pokrycie, gen.) Szacowanie maksymalnego czasu wykonania programów Analiza łańcuchów DNA (wzorce) Przetwarzanie dokumentów XML J.Nawrocki, Języki formalne i gramatyki Języki formalne i gramatyki

4 J.Nawrocki, Języki formalne i gramatykiPlan wykładu Podstawowe pojęcia Klasyfikacja Chomsky’ego Zbiory FOLLOW i first Metoda zejść rekurencyjnych Atrybuty i translacja J.Nawrocki, Języki formalne i gramatyki

5 Środowisko czasu wykon.Fazy kompilacji Wyrażenia regularne Analiza leksykalna .pas Gramatyki Analiza składniowa Generacja kodu pośr. .exe Generacja kodu wynik. Środowisko czasu wykon. J.Nawrocki, Języki formalne i gramatyki

6 Pojęcia analizy składniowej??? Jaś szkoły idzie do Teraz OK. Jaś szkoły idzie do J.Nawrocki, Języki formalne i gramatyki

7 Pojęcia analizy składniowej??? 1 + * 2 3 Teraz OK. 1 + * 2 3 J.Nawrocki, Języki formalne i gramatyki

8 J.Nawrocki, Języki formalne i gramatykiWyrażenie będące sumą 4444 J.Nawrocki, Języki formalne i gramatyki

9 J.Nawrocki, Języki formalne i gramatykiWyrażenie będące sumą składnik J.Nawrocki, Języki formalne i gramatyki

10 J.Nawrocki, Języki formalne i gramatykiWyrażenie będące sumą składnik składnik + składnik J.Nawrocki, Języki formalne i gramatyki

11 J.Nawrocki, Języki formalne i gramatykiWyrażenie będące sumą składnik składnik + składnik składnik + składnik + składnik J.Nawrocki, Języki formalne i gramatyki

12 J.Nawrocki, Języki formalne i gramatykiWyrażenie będące sumą składnik składnik + składnik składnik + składnik + składnik składnik + składnik + składnik + składnik J.Nawrocki, Języki formalne i gramatyki

13 J.Nawrocki, Języki formalne i gramatykiWyrażenie będące sumą składnik 1 składnik + składnik 2 składnik + składnik + składnik 3 składnik + składnik + składnik + składnik wyrażenie: ( składnik + )* składnik J.Nawrocki, Języki formalne i gramatyki

14 Wyrażenie będące iloczynem (czyli składnik)1111 czynnik 1111 * 222 czynnik * czynnik 1111 * 222 * 33 czynnik * czynnik * czynnik 1111 * 222 * 33 * 4 czynnik * czynnik * czynnik * czynnik J.Nawrocki, Języki formalne i gramatyki

15 Wyrażenie będące iloczynem (czyli składnik)1111 czynnik 1111 * 222 czynnik * czynnik 1111 * 222 * 33 czynnik * czynnik * czynnik 1111 * 222 * 33 * 4 czynnik * czynnik * czynnik * czynnik składnik: ( czynnik * )* czynnik J.Nawrocki, Języki formalne i gramatyki

16 J.Nawrocki, Języki formalne i gramatykiCzynnik 1111 liczba ( ) ( * 33 ) ( wyrażenie ) czynnik: liczba | ( wyrażenie ) J.Nawrocki, Języki formalne i gramatyki

17 Pojęcia analizy składniowejGramatyka formalna: reguły budowy zdań T = zbiór symboli terminalnych + * ( ... N = zbiór symboli nieterminalnych Wyrażenie Składnik Czynnik P = zbiór produkcji gramatyki Składnik: Czynnik * Noam Chomsky S = symbol początkowy (S  N) Wyrażenie J.Nawrocki, Języki formalne i gramatyki

18 Pojęcia analizy składniowejWywód zdania Symbol początkowy Forma zdaniowa   Forma zdaniowa   Forma zdaniowa   Zdanie  Forma zdaniowa  (T  N)+ Zdanie  (T)+ J.Nawrocki, Języki formalne i gramatyki

19 Pojęcia analizy składniowejSpostrzeżenia Forma zdaniowa  (T  N)+ Zdanie  (T)+ Każde zdanie jest formą zdaniową ale nie na odwrót. Symbol początkowy gramatyki jest formą zdaniową. J.Nawrocki, Języki formalne i gramatyki

20 Pojęcia analizy składniowejProdukcja gramatyki (T  N)+     Jeśli w zbiorze gramatyki jest   , to x  y x  y  J.Nawrocki, Języki formalne i gramatyki

21 Wyrażenia arytmetyczneW + S   S + S  W  S W  W + S  C + S  C + S * C  3. S  C 4. S  S * C  C + C * C   L + C * C  L + L * C  5. C  L 6. C  ( W )  L + L * L   D + L * L  D + D * L  7. L  D 8. L  L D  D + D * D   1 + D * D  1 + 2 * D  9. D  1 10. D  2 11. D  3  1 + 2 * 3 Wywód lewo-/prawostronny J.Nawrocki, Języki formalne i gramatyki

22 Pojęcia analizy składniowejDomknięcie zwrotne relacji wywodu Forma 1  Forma 2  Forma k ... Forma 1 Forma k * Forma 1 * J.Nawrocki, Języki formalne i gramatyki

23 Pojęcia analizy składniowejJęzyk formalny L(G) = { x: S * x  x  T* } Symbol początkowy * Zdanie J.Nawrocki, Języki formalne i gramatyki

24 J.Nawrocki, Języki formalne i gramatykiPlan wykładu Podstawowe pojęcia Klasyfikacja Chomsky’ego Zbiory FOLLOW i first Metoda zejść rekurencyjnych Atrybuty i translacja J.Nawrocki, Języki formalne i gramatyki

25 Klasyfikacja Chomsky’egoGramatyki liniowe J.Nawrocki, Języki formalne i gramatyki

26 J.Nawrocki, Języki formalne i gramatykiGramatyki liniowe a+ b+ Prawoliniowa S  A B A  a A A  a B  b B B  b S  A B A  A a A  a B  B b B  b Lewoliniowa Twierdzenie. Dla każdego wyrażenia regularnego istnieje gramatyka lewoliniowa (prawoliniowa) opisująca ten sam język. J.Nawrocki, Języki formalne i gramatyki

27 Klasyfikacja Chomsky’egoGramatyki bezkontekstowe Gramatyki liniowe J.Nawrocki, Języki formalne i gramatyki

28 Gramatyka bezkontekstowaW  S W  W + S 3. S  C 4. S  S * C 5. C  L 6. C  ( W ) 7. L  1 8. L  2 9. L  3 Jeden nieterminal J.Nawrocki, Języki formalne i gramatyki

29 Klasyfikacja Chomsky’egoGramatyki kontekstowe Gramatyki bezkontekstowe Gramatyki liniowe J.Nawrocki, Języki formalne i gramatyki

30 Gramatyka kontekstowaS  a X Y S  a S X Y a X  a b b X  b b c X  c c b Y  b c c Y  c c J.Nawrocki, Języki formalne i gramatyki

31 Klasyfikacja Chomsky’egoS  a S  a S a  a b Gramatyki klasy 0 Gramatyki kontekstowe Gramatyki bezkontekstowe Gramatyki liniowe J.Nawrocki, Języki formalne i gramatyki

32 J.Nawrocki, Języki formalne i gramatykiPlan wykładu Podstawowe pojęcia Klasyfikacja Chomsky’ego Zbiory FOLLOW i first Metoda zejść rekurencyjnych Atrybuty i translacja J.Nawrocki, Języki formalne i gramatyki

33 J.Nawrocki, Języki formalne i gramatykiZbiór FOLLOW(X) follow (X) = {a  T: S *  X a } gdzie: S = symbol pocz. ,   (T  N)* S * .. X a .. J.Nawrocki, Języki formalne i gramatyki

34 J.Nawrocki, Języki formalne i gramatykiZbiór FOLLOW(X) FOLLOW(X) = {a  T  {$}: S $ *  X a } S * .. X a .. $ follow(B) = ? S  0 B B  1 $  FOLLOW(B) bowiem S $  0 B $ 1 J.Nawrocki, Języki formalne i gramatyki

35 J.Nawrocki, Języki formalne i gramatykiFOLLOW(X) FOLLOW(X) = {a  T  {$}: S $ *  X a } FOLLOW(S) = ? S  0 B B  1 $  FOLLOW(S) Twierdzenie F0 S $ * S $ J.Nawrocki, Języki formalne i gramatyki

36 J.Nawrocki, Języki formalne i gramatykiFOLLOW(X) FOLLOW(X) = {a  T  {$}: S $ *  X a } Jeśli Y   X, to FOLLOW(Y)  FOLLOW(X). Twierdzenie F1 Jeśli a  FOLLOW(Y), to S $ * .. Y a .. Jeśli Y   X, to .. Y a ..  ..  X a .. Zatem S $ * ..  X a .. Czyli a  FOLLOW(X) J.Nawrocki, Języki formalne i gramatyki

37 J.Nawrocki, Języki formalne i gramatykiFOLLOW(X) i first(Z) FOLLOW(X) = {a  T  {$}: S $ *  X a } Y   X Z Z  .. FOLLOW(X) = ? first(Z) = {b  T: Z * b } Jeśli Y   X Z, to first(Z)  FOLLOW(X). Twierdzenie F2 Jeśli S * .. Y .., to S * ..  X Z .. Jeśli b  first(Z), to Z * b  Czyli S $ * ..  X b  .. Zatem b  FOLLOW(X) J.Nawrocki, Języki formalne i gramatyki

38 J.Nawrocki, Języki formalne i gramatykiPodsumowanie FOLLOW(X) = {a  T  {$}: S $ *  X a } Y   X Z Z  .. first(Z) = {b  T: Z * b } Jeśli Y   X Z, to first(Z)  FOLLOW(X). Tw. F2 Jeśli Y   X, to FOLLOW(Y)  FOLLOW(X). Tw. F1 $  FOLLOW(S) Tw. F0 J.Nawrocki, Języki formalne i gramatyki

39 J.Nawrocki, Języki formalne i gramatykiPrzykład first(Z) = {bT: Z * b} Jeśli Y   X Z, to first(Z)  FOLLOW(X). Tw. F2’ Jeśli Y   X, to FOLLOW(Y)  FOLLOW(X). Tw. F1 $  FOLLOW(S) Tw. F0 S P K P  ‘0‘ P  ‘0’ P K  ‘e’ K  ‘f’ FOLLOW(S) J.Nawrocki, Języki formalne i gramatyki

40 J.Nawrocki, Języki formalne i gramatykiPrzykład first(Z) = {bT: Z * b} Jeśli Y   X Z, to first(Z)  FOLLOW(X). Tw. F2’ Jeśli Y   X, to FOLLOW(Y)  FOLLOW(X). Tw. F1 $  FOLLOW(S) Tw. F0 S P K P  ‘0‘ P  ‘0’ P K  ‘e’ K  ‘f’ $  FOLLOW(S) J.Nawrocki, Języki formalne i gramatyki

41 J.Nawrocki, Języki formalne i gramatykiPrzykład first(Z) = {bT: Z * b} Jeśli Y   X Z, to first(Z)  FOLLOW(X). Tw. F2’ Jeśli Y   X, to FOLLOW(Y)  FOLLOW(X). Tw. F1 $  FOLLOW(S) Tw. F0 S P K P  ‘0‘ P  ‘0’ P K  ‘e’ K  ‘f’ $  FOLLOW(S) FOLLOW(K) J.Nawrocki, Języki formalne i gramatyki

42 J.Nawrocki, Języki formalne i gramatykiPrzykład first(Z) = {bT: Z * b} Jeśli Y   X Z, to first(Z)  FOLLOW(X). Tw. F2’ Jeśli Y   X, to FOLLOW(Y)  FOLLOW(X). Tw. F1 $  FOLLOW(S) Tw. F0 S P K P  ‘0‘ P  ‘0’ P K  ‘e’ K  ‘f’ $  FOLLOW(S) FOLLOW(K) J.Nawrocki, Języki formalne i gramatyki

43 J.Nawrocki, Języki formalne i gramatykiPrzykład first(Z) = {bT: Z * b} Jeśli Y   X Z, to first(Z)  FOLLOW(X). Tw. F2’ Jeśli Y   X, to FOLLOW(Y)  FOLLOW(X). Tw. F1 $  FOLLOW(S) Tw. F0 S P K P  ‘0‘ P  ‘0’ P K  ‘e’ K  ‘f’ $  FOLLOW(S) $  FOLLOW(K) J.Nawrocki, Języki formalne i gramatyki

44 J.Nawrocki, Języki formalne i gramatykiPrzykład first(Z) = {bT: Z * b} Jeśli Y   X Z, to first(Z)  FOLLOW(X). Tw. F2’ Jeśli Y   X, to FOLLOW(Y)  FOLLOW(X). Tw. F1 $  FOLLOW(S) Tw. F0 S P K P  ‘0‘ P  ‘0’ P K  ‘e’ K  ‘f’ $  FOLLOW(S) $  FOLLOW(K) FOLLOW(P) J.Nawrocki, Języki formalne i gramatyki

45 J.Nawrocki, Języki formalne i gramatykiPrzykład first(Z) = {bT: Z * b} Jeśli Y   X Z, to first(Z)  FOLLOW(X). Tw. F2’ Jeśli Y   X, to FOLLOW(Y)  FOLLOW(X). Tw. F1 $  FOLLOW(S) Tw. F0 S P K P  ‘0‘ P  ‘0’ P K  ‘e’ K  ‘f’ $  FOLLOW(S) $  FOLLOW(K) FOLLOW(P) J.Nawrocki, Języki formalne i gramatyki

46 J.Nawrocki, Języki formalne i gramatykiPrzykład first(Z) = {bT: Z * b} Jeśli Y   X Z, to first(Z)  FOLLOW(X). Tw. F2’ Jeśli Y   X, to FOLLOW(Y)  FOLLOW(X). Tw. F1 $  FOLLOW(S) Tw. F0 S P K P  ‘0‘ P  ‘0’ P K  ‘e’ K  ‘f’ $  FOLLOW(S) $  FOLLOW(K) first(K)  FOLLOW(P) e,f  FOLLOW(P) first(K) = {e, f} J.Nawrocki, Języki formalne i gramatyki

47 J.Nawrocki, Języki formalne i gramatykiPrzykład first(Z) = {bT: Z * b} Jeśli Y   X Z, to first(Z)  FOLLOW(X). Tw. F2’ Jeśli Y   X, to FOLLOW(Y)  FOLLOW(X). Tw. F1 $  FOLLOW(S) Tw. F0 S P K P  ‘0‘ P  ‘0’ P K  ‘e’ K  ‘f’ $  FOLLOW(S) $  FOLLOW(K) first(K)  FOLLOW(P) e,f  FOLLOW(P) first(K) = {e, f} J.Nawrocki, Języki formalne i gramatyki

48 J.Nawrocki, Języki formalne i gramatykiPlan wykładu Podstawowe pojęcia Klasyfikacja Chomsky’ego Zbiory FOLLOW i first Metoda zejść rekurencyjnych Atrybuty i translacja J.Nawrocki, Języki formalne i gramatyki

49 Metoda zejść rekurencyjnych1 + 2 * 3 E  W = W  S W  S + W W  S – W S  C S  C * S C  L C  ( W ) L  D L  D L D  0 D  1 function Current: char; (* podgląd *) function CurrentIn(s: SetOfChar): Boolean; (* Czy Current należy do s? *) function Take(t: char): Boolean; (* Czy Curren = t ? Jeśli nie to sygnalizuj błąd. Następny Current *) procedure Next; (* Weź następny element z wejścia *) J.Nawrocki, Języki formalne i gramatyki

50 Metoda zejść rekurencyjnychE  W = W  S W  S + W W  S – W S  C S  C * S C  L C  ( W ) L  D L  D L D  0 D  1 function D: Boolean; begin if Current = ‘0’ then D:= Take(‘0’) else D:= Take(‘1’) end; J.Nawrocki, Języki formalne i gramatyki

51 Metoda zejść rekurencyjnychFOLLOW(L)= FOLLOW(C) = {*}  FOLLOW(S)= {*, -, +}  FOLLOW(W)= {*, -, +, ), =} first(L)= first(D)= {0, 1} E  W = W  S W  S + W W  S – W S  C S  C * S C  L C  ( W ) L  D L  D L D  0 D  1 function L: Boolean; var ok: Boolean; begin ok:= D; if CurrentIn(FollowL) then L:= ok else if CurrentIn(FirstL) then L:= ok and L else Expected("0, 1, *, +, - , ), =") end; J.Nawrocki, Języki formalne i gramatyki

52 Metoda zejść rekurencyjnychE  W = W  S W  S + W W  S – W S  C S  C * S C  L C  ( W ) L  D L  D L D  0 D  1 first(L)= first(D)= {0, 1} function C: Boolean; begin if CurrentIn(FirstL) then C:= L else if Curren = ‘(‘ then C:= Take(‘(‘) and W and Take(‘)’) else Expected("0, 1, (") end; J.Nawrocki, Języki formalne i gramatyki

53 J.Nawrocki, Języki formalne i gramatykiPlan wykładu Podstawowe pojęcia Klasyfikacja Chomsky’ego Zbiory FOLLOW i first Metoda zejść rekurencyjnych Atrybuty i translacja J.Nawrocki, Języki formalne i gramatyki

54 Metoda zejść rekurencyjnychfunction D(var v: integer): Boolean; begin if Current() = ‘0’ then D:= Take(‘0’); v:= 0 end else D:= Take(‘1’); v:= 1 end; E  W = W  S W  S + W W  S – W S  C S  C * S C  L C  ( W ) L  D L  D L D  0 D  1 D.v:= 0 D.v:= 1 J.Nawrocki, Języki formalne i gramatyki

55 Metoda zejść rekurencyjnychwriteln(W.v) E  W = W  S W1  S + W2 W1  S – W2 S  C S1  C * S2 C  L C  ( W ) L  D L1  D L2 D  0 function E: Boolean; var v: integer; begin if CurrentIn(FirstW) then E:= W(v); writeln(v) end end; D.v:= 0 J.Nawrocki, Języki formalne i gramatyki

56 Metoda zejść rekurencyjnychE  W = W  S W1  S + W2 W1  S – W2 S  C S1  C * S2 C  L C  ( W ) L  D L1  D L2 D  0 writeln(W.v) W.v:= S.v W1.v:= S.v + W2.v W1.v:= S.v – W2.v S.v:= C.v S1.v:= C.v * S2.v C.v:= L.v C.v:= W.v L.v:= D.v; L.r:=2 L1.v:= D.v*L2.r + L2.v; L1.r:= L2.r * 2 D.v:= 0 J.Nawrocki, Języki formalne i gramatyki

57 J.Nawrocki, Języki formalne i gramatykiPodsumowanie Gramatyka formalna Produkcje gramatyki Wywód zdania Klasyfikacja Chomsky’ego Zbiory FIRST i follow Metoda zejść rekurencyjnych Atrybuty Wreszcie! J.Nawrocki, Języki formalne i gramatyki

58 J.Nawrocki, Języki formalne i gramatykiLiteratura J. Cybulka, B. Jankowska, J. Nawrocki, Automatyczne przetwarzanie tekstów. AWK, Lex i YACC, Nakom, Poznań, 2002.  J.Nawrocki, Języki formalne i gramatyki

59 J.Nawrocki, Języki formalne i gramatykiOcena wykładu 1. Wrażenie ogólne? (1 - 6) 2. Zbyt wolno czy zbyt szybko? 3. Czy dowiedziałeś się czegoś ważnego? 4. Co poprawić i jak? J.Nawrocki, Języki formalne i gramatyki