1 Lingwistyka Matematycznawykład 3

2 Agenda Wyprowadzanie zdań Analiza zdań Gramatyki klasy LL(1)Podsumowanie Q&A Mgr inż. Michał Jaros

3 W gramatyce Chomsky’ego: Matematyczna definicja języka; Wyprowadzanie zdań W gramatyce Chomsky’ego: Matematyczna definicja języka; Wyprowadzanie ciągów symboli; Bezpośrednie wyprowadzanie ciągów symboli; Mgr inż. Michał Jaros

4 Przykładowa gramatyka:Wyprowadzanie zdań Praktyka Przykładowa gramatyka: S ::= A B A ::= a | b B ::= c | d Symbol początkowy: S Symbole pomocnicze: N = {S, A, B} Symbole końcowe (słownik): T = {a, b, c, d} Mgr inż. Michał Jaros

5 Wyprowadzanie zdań Gramatyka: Zdania z gramatyki: Wyprowadzanie zdańS ::= A B A ::= a | b B ::= c | d Zdania z gramatyki: ac ad bc bd Wyprowadzanie zdań S → AB → aB → ac S → AB → aB → ad S → AB → bB → bc S → AB → bB → bd Mgr inż. Michał Jaros

6 Wyprowadzenie zdania: Ciąg wyprowadzeń:Wyprowadzanie zdań Wyprowadzenie zdania: dc Ciąg wyprowadzeń: S → AB → Błąd ! Wyprowadzanie zdań – sprawdzanie poprawności. S ::= A B A ::= a | b B ::= c | d Mgr inż. Michał Jaros

7 Analiza polega na rozbiorze struktur zdaniowych i zdań; Analiza zdań Analiza polega na rozbiorze struktur zdaniowych i zdań; Celem rozbioru zdania jest sprawdzenie poprawności zdania; Zadaniem teorii analizy składniowej jest opracowywanie algorytmów rozbioru języka; Mgr inż. Michał Jaros

8 Rozbiór zstępujący (ang. Top-down); Analiza zdań Rozbiór zdania Rozbiór zstępujący (ang. Top-down); Rozbiór wstępujący (ang. Bottom-up); Mgr inż. Michał Jaros

9 Rozbiór zstępujący (Top-down): Wyjście z symbolu początkowego; Analiza zdań Rozbiór zstępujący (Top-down): Wyjście z symbolu początkowego; Dopasowywanie do symbolu z lewej strony zdania; Rozbiór z powrotami lub bez powrotów; Mgr inż. Michał Jaros

10 Rozbiór wstępujący (Bottom-up) (Shift-Reduce): Analiza zdań Rozbiór wstępujący (Bottom-up) (Shift-Reduce): Wychodzimy ze zdania i próbujemy otrzymać symbol początkowy; Odnajdywanie i zastępowanie najbardziej podstawowych elementów w zdaniu; Mgr inż. Michał Jaros

11 Analiza zdań – Top-downGramatyka: S ::= A B A ::= a | b B ::= c | d Czy zdanie ac należy do języka ? Rozbiór S A B a B B c -- a c Mgr inż. Michał Jaros

12 Zdania należące do gramatyki:Rekurencja Rekurencja (rekursja) – symbol pomocniczy powtarza się z lewej i prawej strony produkcji S::=xA A::=z|yA Zdania należące do gramatyki: xz xyz xyyz xyyyz … Mgr inż. Michał Jaros

13 Gramatyka dla liczb naturalnych:Rekurencja Gramatyka dla liczb naturalnych: S::=N N::=C|NC C::=0|1|2|3|4|5|6|7|8|9 Przykładowe zdanie: S → N → C → 5 S → N → NC → 15 S → N → NC → NCC → NCCC → CCCC → 1542 Mgr inż. Michał Jaros

14 Analiza zdań – Top-downGramatyka: S::=N N::=C|NC C::=0|1|2|3|4|5|6|7|8|9 Czy zdanie 15 należy do języka ? Rozbiór S N C 1 -- 1 5 5 Błąd ? Mgr inż. Michał Jaros

15 Podzbiór gramatyk bezkontekstowych; Gramatyki klasy LL(1) Podzbiór gramatyk bezkontekstowych; Rozbieralne analizatorami zstępującymi; Dwie reguły gramatyczne dla gramatyk klasy LL(1) Mgr inż. Michał Jaros

16 Gramatyki klasy LL(1) – Reguła 1Dla zadanej gramatyki zawierającej produkcję postaci zbiory symboli pierwszych które mogą być wyprowadzone z A muszą być rozłączne Mgr inż. Michał Jaros

17 Gramatyki klasy LL(1) – Reguła 2Dla każdego symbolu A  N, z którego można wyprowadzić pusty ciąg symboli zbiór jego pierwszych symboli musi być rozłączny ze zbiorem symboli, które mogą następować po dowolnym ciągu wyprowadzonym z A, tzn. Mgr inż. Michał Jaros

18 Zbiór symboli pierwszychGramatyki klasy LL(1) Zbiór symboli pierwszych pierw(ξ) – zbiór wszystkich symboli końcowych, które mogą wystąpić na pierwszej pozycji w zdaniach wyprowadzonych z ξ. Pierwszy symbol argumentu to symbol końcowy: pierw(aξ) = {a} Pierwszy symbol argumentu to symbol pomocniczy: A ::= α1 | α2 | α3 | … | αn pierw(Aξ) = pierw(α1)  pierw(α2)  pierw(α3)  …  pierw(αn) Mgr inż. Michał Jaros

19 Gramatyki klasy LL(1) Zbiór symboli następnych nast(A) – dla każdej produkcji postaci X ::= ξAη do zbioru nast(A) dołączamy zbiór pierw(η). Jeżeli z η można wyprowadzić pusty ciąg symboli to do nast(A) musimy dołączyć również nast(X). Mgr inż. Michał Jaros

20 Gramatyki klasy LL(1) Lewostronna faktoryzacja Produkcję postaci: A ::= αξ1 | αξ2 | αξ3 | … | αξn | β1 | β2 | β3 | … | βn Należy zastąpić produkcjami: A ::= αA’ | β1 | β2 | β3 | … | βn A’ ::= ξ1 | ξ2 | ξ3 | … | ξn Mgr inż. Michał Jaros

21 Gramatyki klasy LL(1) Przed poprawieniem Po poprawieniuS::=A+A|A-A|A|x A::=y|z Po poprawieniu S ::=AS’|x S’::=+A|-A|ε A ::=y|z Mgr inż. Michał Jaros

22 Gramatyki klasy LL(1) Eliminacja lewostronnej rekurencji Produkcję postaci: A ::= Aα1 | Aα2 | Aα3 | … | Aαn | β1 | β2 | β3 | … | βn Należy zastąpić produkcjami: A ::= β1A’ | β2A’ | β3A’ | … | βnA’ A’ ::= α1A’ | α2A’ | α3A’ | … | αnA’ | ε Mgr inż. Michał Jaros

23 Gramatyki klasy LL(1) Przed poprawieniem Po poprawieniu S::=N N::=C|NC Mgr inż. Michał Jaros

24 Podsumowanie Wyprowadzanie zdań Analiza zdań Gramatyki klasy LL(1) Mgr inż. Michał Jaros

25 Q&A Mgr inż. Michał Jaros

26 KONIEC Mgr inż. Michał Jaros