Analiza metodą wstępująCĄ ANALIZA wstępująCA



Yüklə 445 b.
tarix22.05.2018
ölçüsü445 b.
#45344


ANALIZA METODĄ WSTĘPUJĄCĄ


ANALIZA WSTĘPUJĄCA

  • Dla danej gramatyki G oraz S=>*, to wówczas:

  • Jeśli  zawiera tylko terminale, to  nazywamy zdaniem;

  • 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:



IMPLEMENTACJA ANALIZY REDUKCYJNEJ

  • 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;



TABLICA ANALIZATORA LR

  • 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



DZIAŁANIA ANALIZATORA



KONIEC

  • KONIEC WYKŁADU SIÓDMEGO



Yüklə 445 b.

Dostları ilə paylaş:




Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©genderi.org 2024
rəhbərliyinə müraciət

    Ana səhifə