ANALIZA METODĄ WSTĘPUJĄCĄ
ANALIZA WSTĘPUJĄCA Dla danej gramatyki G oraz S=>*, to wówczas: Jeśli zawiera terminale oraz nieterminale, lub same nieterminale, to nazywamy formą zdaniową; Wniosek Zdanie jest forma zdaniowa, która nie zawiera nieterminali;
ANALIZA WSTĘPUJĄCA W analizie zstępującej przetwarzanie rozpoczynamy od symbolu startowego a następnie stosujemy wyprowadzenie tak długo, aż otrzymamy zdanie wejściowe. Możliwe jest oczywiście, że zdania nie da się wygenerować. Wówczas otrzymamy taką informacje; W analizie wstępującej mamy odwrotny schemat działania. Zaczynamy tu pracę od analizowanego zdania i poprzez konsekwentne stosowanie redukcji próbujemy dojść do symbolu startowego gramatyki;
ANALIZA ZSTĘPUJĄCA Sprawdźmy, w jaki sposób działa metoda wstępująca na przykładzie z wcześniejszych wykładów. Dane jest zdanie
GRAMATYKA BEZKONTEKSTOWA gramatyka – reguły produkcji: Zdanie -> podmiot orzeczenie Podmiot -> przymiotnik rzeczownik Orzeczenie -> czasownik dopełnienie Dopełnienie -> rzeczownik Rzeczownik -> płot Przymiotnik -> szybki Czasownik -> przeskoczył Rzeczowniki -> pies
ANALIZA ZSTEPUJĄCA
ANALIZA WSTEPUJĄCA
Przykład Rozważmy gramatykę o następujących produkcjach: S-> aABe, A->Abc | b, B->d; Zastanówmy się nad zdaniem =abbcde;
PRAWE WYPROWADZENIE Niech G będzie gramatyką bezkontekstową. Niech 1=>2=>3=>...=>k, 1,2,...,k є (VU Σ)* będzie wyprowadzeniem w G. Wyprowadzenie to nazywamy prawym wyprowadzeniem, gdy każde pojedyncze wyprowadzenie i-1=>i w tym łańcuchu wyprowadzeń polega na zastosowaniu produkcji z G do pierwszej zmiennej w i-1 liczonych od prawej strony;
ANALIZA WSTĘPUJĄCA
ANALIZA WSTĘPUJĄCA
Przykład Rozważmy gramatykę o następujących produkcjach: S-> aABe, A->Abc | b, B->d;
PRZYCINANIE UCHWYTÓW Przycinanie uchwytów jest metodą dzięki której możemy uzyskać odwrotność prawostronnego wyprowadzenia; Załóżmy że mamy daną gramatykę i dane zdanie w, utworzone w tej gramatyce. Zatem w=n gdzie n jest n-tą prawostronną formą zdaniowa, w pewnym prawostronnym wyprowadzeniu;
PRZYCINANIE UCHWYTÓW W celu odtworzenia tego wyprowadzenia od końca, wyszukujemy uchwyt n w n i zastępujemy go lewą stroną produkcji A-> n. W ten sposób otrzymujemy (n-1) –szą prawostronną formę zdaniową; Wyszukujemy następnie uchwyt n-1 w n-1 i redukujemy ten uchwyt i otrzymujemy prawostronną formę n-2; Jeśli po skończonej ilości powtórzeń takiej czynności otrzymamy prawostronną formę zdaniową składającą się z symbolu startowego S, to kończymy analizę;
Przykład
Przykład
Przykład Rozważmy następująca gramatykę: E->E+E, E->E*E, E->(E), E->w;
IMPLEMANTACJA ANALIZY REDUKCYJNEJ Jeśli chcemy dokonywać analizy tekstów, za pomocą przycinania uchwytów, musimy pokonać dwa główne problemy:
Kolejnym istotnym pytaniem jest pytanie o rodzaj struktur danych, które będzie wygodnie używać, przy implementacji analizatora; Wygodna metodą jest użycie stosu do pamiętania symboli gramatyki, oraz bufora wejściowego do pamiętania tekstu w, przeznaczonego do analizy;
OPIS STOSU Na starcie na wejściu jest napis w, a stos jest pusty; Analizator przesuwa symbole z wejścia na stos, aż na wierzchołku znajdzie się uchwyt ; analizator redukuje do lewej strony odpowiedniej produkcji; Powtarza ten proceder, aż do wystąpienia błędu, lub sytuacji gdy na stosie będzie symbol startowy; Gdy na stosie będzie tylko symbol startowy analizator kończy pracę;
Operacje Mamy cztery operacje analizatora: Przesuniecie – powoduje wstawienie kolejnego symbolu z wejścia na wierzchołek stosu; Redukcja – analizator wie, że prawy koniec uchwytu jest na wierzchołku stosu, szuka na stosie lewy koniec uchwytu, i zastępuje uchwyt odpowiednim nieterminalem (sam decyduje, którym);
Operacje Pozostałe operacje analizatora: Akceptowanie – pomyślne zakończenie analizy; Błąd – oznacza, że wystąpił błąd składniowy i analizator wywołuje procedurę obsługi błędu;
Przykład
Przykład
Przykład
Przykład
Przykład
Przykład Wróćmy do naszego przykładu nr 2 z produkcjami: E->E+E, E->E*E, E_>(E), E->(w) Ponownie rozważamy zdanie =w+w*w Prześledźmy sekwencje operacji wykonywanych przez analizator:
Przykład
Przykład
PROBLEMY Problemy przy przycinaniu uchwytów: Znalezienie odpowiedniego uchwytu (w analizatorach redukujących zawsze jest na szczycie stosu); Wybranie odpowiedniej produkcji, jeśli może być wykorzystana więcej niż jedna (konstrukcja tablicy LR);
ANALIZATOT LR Wydajna metodą analizy wstępującej jest analiza LR(k), gdzie „L” oznacza przeglądanie wejścia od lewej do prawej, „R” (rightmost) oznacza budowę prawostronnego wyprowadzenia od końca, a k oznacza liczbę symboli podglądanych podczas podejmowania decyzji w trakcie analizy; Gdy pominiemy (k), przyjmujemy, że k=1;
ANALIZATOT LR Zalety analizatorów LR: Można zbudować analizatory LR do prawie wszystkich konstrukcji języków programowania, dla których można znaleźć gramatykę bezkontekstową; Metoda LR jest najogólniejszą nie wracającą metodą analizy redukującej. Analizatory działające tą metodą można zaimplementować tak wydajnie, jak działające innymi metodami redukcyjnymi;
ANALIZATOT LR Zalety analizatorów LR: Klasa gramatyk które można analizować, używając metody LR jest właściwym nadzbiorem klasy gramatyk, które można analizować analizatorami przewidującymi; Analizator LR może wykrywać błędy tak wcześnie, jak jest to możliwe podczas przeglądania wejścia, od lewej do prawej strony;
ANALIZATOR LR
ANALIZATOR LR Działanie analizatora LR: Program sterujący jest taki sam dla wszystkich analizatorów LR, różne są jedynie tablice analizatora; Program analizatora wczytuje pojedyncze symbole z bufora wejściowego;
ANALIZATOR LR Używa on stosu do zapamiętywania ciągu postaci s0 X1 s1 X2 s2 ...Xm na wierzchołku, gdzie każde Xi jest symbolem z gramatyki a si jest symbolem nazywanym stanem; Każdy symbol stanu podsumowuje informacje zawarte na stosie pod nim, a kombinacja symbolu stanu i aktualnego symbolu wejściowego jest używana do indeksowania tablicy analizatora oraz do podejmowania decyzji o przesunięciu lub redukcji;
Tablice analizatora zawierają wytyczne dla programu sterującego. Wytyczne te dotyczą między innymi tego w jakim stanie i pod wpływem jakich symboli ma wystąpić akcja (action lub przejście (goto); Tablice analizatora można tworzyć na różne sposoby; Metody tworzenia tablic decydują o sile analizatora (tzn. o liczbę przetwarzanych gramatyk);
TABLICA ANALIZATORA LR Metody konstrukcji tablicy analizatorów: SLR (prosty LR) – najłatwiejsza w implementacji ale najsłabsza, dla niektórych gramatyk dla których pozostałe zadziałają ta może nie dać rezultatów; Podglądający LR (LALR) – średnia pod względem możliwości, jak i kosztów; Metoda kanoniczna LR – najskuteczniejsza, ale też najdroższa;
TABLICA ANALIZATORA LR Tablica analizatora składa się z dwóch części : Funkcji wyznaczającej akcje, akcja; Funkcji wyznaczającej przejście, przejście; Funkcja przejście bierze jako argument stan i symbol z gramatyki, a zwraca stan;
ANALIZATOR LR Program analizatora LR sprawdza stan sm, stan leżący na wierzchołku stosu oraz aktualny symbol na wejściu ai; Odczytuje następnie wartość akcja[sm,ai] w tablicy analizatora dla stanu sm i wejścia ai; Wartość akcja[sm,ai] może być: przesuń s, gdzie s jest stanem; redukuj zgodnie z produkcja A->; akceptuj; błąd;
ANALIZATOR LR Konfiguracją analizatora LR nazywamy parę, której pierwszym elementem jest zawartość stosu, a drugim niewykorzystane wejście; (s0 X1 s1 X2 s2 ...Xm sm , ai ai+1 ...an$) Powyższa konfiguracja przedstawia formę zdaniowa: X1 X2 ...Xmai ai+1 ...an
ANALIZATOR LR Konfiguracje, które mogą wystąpić po każdym z czterech typów akcji: akcja[sm,ai]=przesuń s – analizator wykonuje przesunięcie przechodząc do konfiguracji: (s0 X1 s1 X2 s2 ...Xm smais, ai+1 ...an$) akcja[sm,ai]=redukuj wg A-> - analizator wykonuje redukcje przechodząc do konfiguracji: (s0 X1 s1 X2 s2 ...Xm-r sm-r A s, ai+1 ...an$), gdzie s=przejście[sm-r,A], a r jest długością ;
akcja[sm,ai]=redukuj wg A-> Analizator zdejmuje ze stosu 2r symboli (po r symboli stanu i gramatyki), odkrywając stan s. Następnie wstawia na stos A – lewa stronę użytej produkcji i s – wartość przejście[s, A]. Aktualny symbol wejściowy w wyniku redukcji nie jest zmieniany; akcja[sm,ai]=akceptuj – analiza jest zakończona; akcja[sm,ai]= błąd - analizator wykrył błąd i wywołuje procedurę obsługi błędu;
ANALIZA LR Podsumujmy krótko algorytm analizy LR: Wejście: ciąg wejściowy w i tablica analizatora LR z funkcjami akcja i przejście dla gramatyki G; Wyjście jeśli w jest w L(G) –występuje wyprowadzenie dla w, w przeciwnym przypadku – informacja o błędzie; Metoda: początkowo na stosie analizatora jest s0, czyli stan początkowy, a na wejściu jest w$. Dalsze kroki analizatora zaobserwujmy na przykładzie;
Przykład Rozważmy następującą gramatykę bezkontekstową, daną zbiorem produkcji: E -> E+T; E->T; T->T*F; T->F; F->(E); F->id;
Przykład W naszym algorytmie wprowadźmy następujące oznaczenia: si oznacza przesuniecie i wstawiany na stos stan i; rj oznacza redukcję według produkcji o numerze j; akc oznacza akceptuj; Puste miejsce oznacza błąd;...
Przykład
Przykład
DZIAŁANIA ANALIZATORA
KONIEC
Dostları ilə paylaş: |