1 Lingwistyka Matematycznawykład 4

2 Gramatyka z translacją Podsumowanie Q&AAgenda Kompilacja Drzewo wyprowadzeń Gramatyka z translacją Podsumowanie Q&A Mgr inż. Michał Jaros

3 W kompilacji zastosowanie mają:Kompilacja Kompilacja Tłumaczenie kodu napisane w jednym języku na drugi Sprawdzanie poprawności kodu W kompilacji zastosowanie mają: Lingwistyka matematyczna Języki formalne Mgr inż. Michał Jaros

4 Mgr inż. Michał Jaros

5 Kompilacja Przód kompilatora (z ang. „front end”) Analiza leksykalnaTokenizacja kodu źródłowego Utworzenie tablicy symboli Analiza Składniowa Utworzenie drzewa wyprowadzeń Sprawdzenie poprawności gramatycznej Analiza semantyczna Sprawdzanie sensu (sprawdzanie typów, ...) Uzupełnienie tablicy symboli Mgr inż. Michał Jaros

6 Środek kompilatora (z ang. „middle end”) Generacja kodu pośredniegoKompilacja Środek kompilatora (z ang. „middle end”) Generacja kodu pośredniego Ogólna optymalizacja Mgr inż. Michał Jaros

7 Tył kompilatora (z ang. „back end”) Optymalizacja kodu Kompilacja Tył kompilatora (z ang. „back end”) Optymalizacja kodu Generacja kodu wynikowego Mgr inż. Michał Jaros

8 Kompilacja Mgr inż. Michał Jaros

9 Kody pośrednie dla różnych językówKompilacja Kody pośrednie dla różnych języków Kod źródłowy Kod pośredni Pacal P-code Ada Diana Java JVM C# .NET CIL Mgr inż. Michał Jaros

10 Korzeń = Symbol początkowy Gałęzie = Symbole pomocnicze Drzewo wyprowadzeń Drzewo wyprowadzeń Hierarchiczna struktura graficznie reprezentująca wyprowadzenie zdania z gramatyki Korzeń = Symbol początkowy Gałęzie = Symbole pomocnicze Liście = Symbole końcowe Struktura gałęzi = Produkcje Mgr inż. Michał Jaros

11 Drzewo wyprowadzeń S::=SAB;|AB; A::=type B::=B,C|C C::=id 2008-04-13Mgr inż. Michał Jaros

12 Niejednoznaczność składni Drzewo wyprowadzeń Niejednoznaczność składni Zdanie ma więcej niż jedno drzewo wyprowadzeń. S::=E E::=E+E|E*E|(E)|id id+id*id Mgr inż. Michał Jaros

13 Drzewo wyprowadzeń id+id*id Mgr inż. Michał Jaros

14 S::=C C::=D+C|D D::=E*D|E E::=(C)|id id+id*idDrzewo wyprowadzeń S::=C C::=D+C|D D::=E*D|E E::=(C)|id id+id*id Mgr inż. Michał Jaros

15 Przypadek rzeczywisty Drzewo wyprowadzeń Przypadek rzeczywisty Niejednoznaczność instrukcji warunkowej if-else w językach C oraz Pascal S::=ε | stmt | if W then SL | if W then SL else SL SL::=SL;S | S Pascal Mgr inż. Michał Jaros

16 if W then if W then S else SDrzewo wyprowadzeń if W then if W then S else S Mgr inż. Michał Jaros

17 Problem Rozwiązanie Drzewo wyprowadzeń Niejednoznaczność if-elseJęzyki programowania Pascal i C Rozwiązanie Słowo kluczowe else jest kojarzone z najbliżej występującym słowem kluczowym if Mgr inż. Michał Jaros

18 Drzewo wyprowadzeń Eliminacja niejednoznaczności instrukcji warunkowej if-else w języku Modula-2. Analogiczne rozwiązanie w VisualBasic. S::=ε | stmt | if W then SL end | if W then SL else SL end SL::=SL;S | S Modula-2 Mgr inż. Michał Jaros

19 if W then if W then S else S Modula-2 Drzewo wyprowadzeń Pascal if W then if W then S else S Modula-2 if W then if W then S else S end end if W then if W then S end else S end Mgr inż. Michał Jaros

20 Gramatyka z translacjąTranslacja sterowana składnią Gramatyka bezkontekstowa Zbiór terminali uzupełniony dodatkowymi symbolami (symbole translacji) Symbole translacji generują dodatkowe słowo wyjściowe Mgr inż. Michał Jaros

21 Gramatyka z translacjąS ::= E E ::= T El El ::= +T El | -T El | ε T ::= F Tl Tl ::= * F Tl | / F Tl | ε F ::= - F | (E) | id id ::= w | x | y | z Mgr inż. Michał Jaros

22 Gramatyka z translacjąS ::= E E ::= T El El ::= +T {+} El | -T {-} El | ε T ::= F Tl Tl ::= * F {*} Tl | / F {/} Tl | ε F ::= - F {-} | (E) | id {id} id ::= w | x | y | z Mgr inż. Michał Jaros

23 Gramatyka z translacjąNotacja wrostkowa Notacja przyrostkowa (ONP) x+y xy+ (xy)+z xyz+ x (y+z) xyz+ x*(y+z)*w xyz+*w* Mgr inż. Michał Jaros

24 Gramatyka z translacjąPodsumowanie Kompilacja Drzewo wyprowadzeń Gramatyka z translacją Mgr inż. Michał Jaros

25 Q&A Mgr inż. Michał Jaros

26 KONIEC Mgr inż. Michał Jaros