Analiza LL



Informacje, które udało nam się zgromadzić na temat Analiza LL, zostały starannie sprawdzone i uporządkowane, aby były jak najbardziej przydatne. Prawdopodobnie trafiłeś tutaj, aby dowiedzieć się więcej na temat Analiza LL. W Internecie łatwo zgubić się w gąszczu stron, które mówią o Analiza LL, a jednocześnie nie podają tego, co chcemy wiedzieć o Analiza LL. Mamy nadzieję, że dasz nam znać w komentarzach, czy podoba Ci się to, co przeczytałeś o Analiza LL poniżej. Jeśli informacje o Analiza LL, które podajemy, nie są tym, czego szukałeś, daj nam znać, abyśmy mogli codziennie ulepszać tę stronę.

.

W informatyce , parsowanie LL jest top - down analizy skadniowej dla niektórych nie - kontekstowych gramatyk , zwany gramatyki LL . Analizuje si sowo wejciowe od strony lewej do prawej ( L EFT do prawej w jzyku angielskim) i konstruuje wyprowadzenie w lewo ( L eftmost derywacji w jzyku angielskim). Drzewo skadni jest budowane od korzenia, a nastpnie w dó do drzewa.

Analiza LL wykonuje pojedyncze przejcie na sowie wejciowym. Analiza LL nazywana jest analiz LL ( k ), gdy wykorzystuje okno k leksemów, aby zdecydowa, jak skonstruowa drzewo skadni sowa wejciowego.

Architektura analizatora LL

Poniej opisano analiz lewostronn z góry na dó w oparciu o tabel analityczn . Pojcie lewostronnej derywacji oznacza, e w procesie stosowania regu wybierany i przepisywany jest skrajny lewy nieterminal. Ten aspekt skutkuje zastosowaniem stosu w algorytmie analizatora.

Przypadek ogólny dla analizy LL (1)

Analizator skada si z:

  • Bufor wejciowy, zawierajcy cig znaków, które maj by analizowane, wyposaone w dwie operacje: odczyt biecej znak i przejcia do nastpnego znaku;
  • stos , na których mona umieci zaciski i s w zaciski gramatyki, które pozostaj do analizy;
  • stó analiza , która mówi, które rzdz uy (jeli istnieje) na podstawie symboli na wierzchu stosu i poniszego leksemu.

Parser stosuje regu znalezion w tabeli, dopasowujc wierzchoek stosu (wiersza) do biecego symbolu w buforze wejciowym (kolumnie).

Na pocztku analizy stos zawiera dwa symbole:

[ S, $ ]

Gdzie $ jest symbolem koca stosu i koca bufora wejciowego, a S jest aksjomatem gramatyki.
Parser spróbuje przepisa zawarto swojego stosu do tego, co widzi w buforze wejciowym. Jednak zachowuje na stosie tylko to, co naley przepisa.

Obliczanie tabeli analitycznej

Pozwoli jak algebraiczny gramatyki (gdzie V oznacza zbiór zmiennych nieterminalnych lub symboli, znaków alfabetu zacisk lub zestawu symboli kocowych P zestaw regu, s Aksjomat gramatyki która regua P). W celu obliczenia tabeli analizy , wprowadzamy funkcje , i .

Eps

Dla kadej wypowiedzi , to prawda, jeli mona rozwiza, co jest równoznaczne ze stwierdzeniem, czy jest prawd (wyraenie przepisuje do pustego acucha ) i false w przeciwnym wypadku. Obliczenia te odpowiadaj reguom , jak w przypadku konwersji do postaci normalnej Chomsky'ego .

Pierwszy

Dla kadego wyraenia definiujemy jako zbiór terminali, które mog rozpoczyna sowo pochodzce od . Bardziej formalnie:

.

Jeli tak .

nastpujcy

Dla kadego wyraenia definiujemy jako zbiór terminali, które prawdopodobnie nastpuj po sowie pochodzcym z . Bardziej formalnie:

.

Tak wic . Dodajemy równie do wszystkich symbol $ , aby móc wskaza koniec kodu.

Wypenianie tabeli analitycznej

Tabela analizy to dwuwymiarowa macierz, której wiersze s indeksowane przez Non-terminale, a kolumny przez Terminals . Wypenienie odbywa si w ten sposób:

  Pour toute règle de la forme X 
     Pour tout aPremier()
        Ajouter X à la case d'indice (a,X)
     Si Eps() vaut vrai Alors
        Pour tout bSuivant() 
           Ajouter X à la case d'indice (b,X)
        Fin pour
     Fin pour
  Fin pour

Przykad bez reguy

Inicjalizacja

Aby wyjani, jak to dziaa, uyjemy nastpujcej gramatyki:

i przeanalizuj nastpny cig

(1 + 1)

Obliczamy EPS:

adna regua nie daje , wic adne Eps () nie jest zawsze faszywe.

Obliczamy Prime:

Premier(F) = { 1 }
Premier((S + F)) = { (}
Premier(1) = { 1 }


Obliczamy tabel analityczn:

On prend S  F, Premier(F) = { 1 } donc on ajoute '' à la case (S , 1).
On prend S  (S + F), Premier((S + F)) = { (} donc on ajoute '' à la case (S  , ().
On prend F  1, Premier(1)= { 1 } donc on ajoute '' à la case (F , 1).
( ) 1 + $
S - - -
fa - - - -
Analiza sów

Parser odczytuje pierwszy znak ( z bufora wejciowego i wierzchoka stosu (S). Patrzc na tabel, wie, e musi zastosowa regu ; musi teraz przepisa S w (S + F) na swoim stosie i zapisz regu zastosowan do wyniku. Stos staje si (szczyt stosu jest po lewej stronie, symbole s oddzielone przecinkami):

[ (, S, +, F, ), $ ]

Moemy zauway, e nieterminalne S zostanie usunite ze stosu, a zatem przepisane przed F. Jest to rzeczywicie ostatnia skrajna lewa strona w wyraeniu '(S + F)'. To ilustruje pojcie lewostronnego wyprowadzenia . W nastpnym kroku, poniewa zarówno wierzchoek stosu, jak i bufor przedstawiaj terminal '(', ten symbol jest zdejmowany i usuwany z bufora wejciowego. Stos staje si:

[ S, +, F, ), $ ]

Teraz bufor ma symbol 1, a szczyt stosu to S. Zgodnie z tabel parser stosuje regu , która umieszcza F na szczycie stosu. Analizator wywietla zastosowan regu na wyjciu. Stos staje si:

[ F, +, F, ), $ ]

Poniewa bufor zawsze ma symbol 1, regu do zastosowania zgodnie z tabel jest . Analizator wywietla zastosowan regu na wyjciu. Stos staje si:

[ 1, +, F, ), $ ]

Podczas nastpnych dwóch kroków (dla symboli 1 i +) symbol gowicy bufora odpowiada wierzchokowi stosu. Kady jest usuwany z bufora i rozkadany na stos. Stos staje si:

[ F, ), $ ]

W ostatnich 3 krokach F zostanie zastpione na stosie przez 1, dlatego na wyjciu zostanie zapisana regua . Nastpnie 1 i ) s usuwane z bufora wejciowego i stosu. Analiza koczy si zatem, poniewa na stosie i buforze wejciowym zostao tylko $. W tym przypadku parser akceptuje cig i wywietla list na wyjciu:

[ , , , ]

Co jest w rzeczywistoci wyprowadzeniem na lewo od acucha pocztkowego. Widzimy, e wyprowadzenie po lewej stronie acucha to:

S (S + F) (F + F) (1 + F) (1 + 1)

Uwagi

Jak wida, parser wykonuje trzy rodzaje kroków w zalenoci od szczytu stosu (nieterminalowe, terminalowe, symbol '$'):

  • jeli wierzchoek stosu jest symbolem nieterminalowym, to sprawdza w tablicy parsowania na podstawie tego symbolu nieterminalowego i symbolu w buforze wejciowym, której reguy uy do zastpienia go na stosie. Numer reguy jest zapisywany na wyjciu. Jeli tabela analizy mówi, e nie ma reguy dopasowania, generuje bd i zatrzymuje si;
  • jeli wierzchoek stosu jest symbolem terminala, porównuje go z symbolem w buforze wejciowym. Jeli s równe, usuwa je, w przeciwnym razie zgasza bd i zatrzymuje si;
  • jeli wierzchokiem stosu jest $, a bufor wejciowy równie zawiera $, wówczas parser mówi, e przeanalizowa acuch poprawnie, w przeciwnym razie zgasza bd. W obu przypadkach zatrzymuje si.

Te kroki s powtarzane do zatrzymania analizatora; albo poprawnie przeanalizuje acuch i zapisze pochodn po lewej stronie cigu na wyjciu, albo wywietli bd.

Przykad z regu

Inicjalizacja

Aby wyjani, jak to dziaa, uyjemy nastpujcej uproszczonej gramatyki LISP / Scheme:

i przeanalizuj nastpny cig

Obliczamy EPS:

Tylko L mona anulowa, wic jest prawdziwe i jest faszywe w pozostaych przypadkach.

Obliczamy Prime:

Premier(a) = { a }
Premier((L)) = { (}
Premier(SL) = { (, a }
Premier() = 

Obliczamy nastpujce:

Suivant(S) = { $, a, (, ) }
Suivant(L) = { ) }

Obliczamy tabel analityczn:

On prend S  (L), Premier((L)) = { (} donc on ajoute '' à la case (S , ().
On prend S  a, Premier(a) = { a } donc on ajoute '' à la case (S , a).
On prend L  SL, Premier(SL)={ (, a } donc on ajoute '' aux cases (L , () et (L, a). 
On prend L  , Premier() =  et Eps() = vrai et Suivant(L)={ ) }, donc on ajoute '' à la case (L ,)).
( ) w $
S - -
L -

Przypominamy, e analizator obsuguje stos i bufor wejciowy, który moe dostarczy symbole cigu znaków. Odczytanie bufora nie oznacza przejcia do nastpnego symbolu. Odczytanie bufora oznacza tylko dostp do aktualnego symbolu. Przechodzimy do nastpnego symbolu w buforze tylko wtedy, gdy symbol spitrzony jest terminalem równym aktualnemu symbolowi bufora. Ta równo przekada si na fakt, e na obecnym etapie odczytany napis jest zgodny z gramatyk. Postp w buforze nie jest odwracalny (analizator nigdy nie wraca w acuchu). Moe to by reprezentowane przez gowic odczytujc wyposaon w pami. Gdy ta gowica odczytu przesuwa si w buforze, pami przechowuje odczytany znak. Pami t mona przeglda dowoln liczb razy. Ta konsultacja odpowiada operacji odczytu bufora. Gowica odtwarzania moe przej do nastpujcego symbolu: co jest okrelane jako postp w buforze.

Analiza sów
[ S, $ ] 

Parser odczytuje pierwszy znak ( z bufora wejciowego i zdejmuje szczyt stosu (S). Patrzc na tabel, wie, e musi zastosowa regu 1; teraz musi przepisa S w '(L)' na swoim stosie, wic stos staje si:

[ (, L,), $ ] 

Na szczycie stosu znajduje si symbol terminala '('. Poniewa odpowiada on aktualnemu symbolowi bufora (a wic acuch poda w tej chwili za gramatyk), ten symbol jest zdejmowany i przechodzi do nastpnego symbolu w bufor, który jest 'a' Stos sta si:

[ L,), $ ]

Pojawia si L i czyta liter a, musi zastosowa regu 3; przepisuje L na SL:

[S, L,), $ ]

Pojawia si S i czyta liter a, musi zastosowa zasad 2; przepisuje S na a, a nastpnie w dodatkowym kroku usuwa a ze wzgldu na zgodno z wierzchokiem stosu. Nastpnie biecym symbolem bufora jest drugi '(', a stos sta si:

[ L,), $ ]

Teraz wyskakuje L i czyta liter (, przepisuje L na SL (regua 3), a nastpnie S na (L) (regua 1), dziki czemu mona usun '('. Biecy symbol jest pierwszym ')', a stos sta si:

[ L,), L,), $ ] 

Wbija L i odczytuje liter ), wic moe usun L za pomoc reguy 4, a nastpnie moe usun ). Biecy symbol to drugi znak ), a stos sta si:

[ L,), $ ]

W taki sam sposób jak wczeniej, regua 4 pozwala mu usun L, a nastpnie moe usun ). Stos sta si pusty:

[ $ ] 

Algorytm zatem wnioskuje pozytywnie i stosujc sekwencj lewej pochodnej:

.

Generatory parserów LL ( k )

Uwagi i odniesienia

  1. Romain Legendre i François Schwarzentruber, Kompilacja: analiza leksykalna i syntaktyczna - od tekstu do jego struktury w informatyce , Pary, elipsy ,, 312  pkt. ( ISBN  978-2-340-00366-8 ).

Powizane artykuy

Mamy nadzieję, że informacje, które zgromadziliśmy na temat Analiza LL, były dla Ciebie przydatne. Jeśli tak, nie zapomnij polecić nas swoim przyjaciołom i rodzinie oraz pamiętaj, że zawsze możesz się z nami skontaktować, jeśli będziesz nas potrzebować. Jeśli mimo naszych starań uznasz, że informacje podane na temat _title nie są całkowicie poprawne lub że powinniśmy coś dodać lub poprawić, będziemy wdzięczni za poinformowanie nas o tym. Dostarczanie najlepszych i najbardziej wyczerpujących informacji na temat Analiza LL i każdego innego tematu jest istotą tej strony internetowej; kierujemy się tym samym duchem, który inspirował twórców Encyclopedia Project, i z tego powodu mamy nadzieję, że to, co znalazłeś o Analiza LL na tej stronie pomogło Ci poszerzyć swoją wiedzę.

Opiniones de nuestros usuarios

Anita Wawrzyniak

Mój tata rzucił mi wyzwanie, abym odrobił pracę domową bez używania czegokolwiek z Wikipedii. Powiedziałem mu, że mogę to zrobić, przeszukując wiele innych witryn. Na szczęście znalazłem tę witrynę, a ten artykuł o zmiennej Analiza LL pomógł mi odrobić pracę domową. wpadłem w pokusę pójścia na Wikipedię, bo nie mogłem znaleźć nic o zmiennej _, ale na szczęście znalazłem ją tutaj, bo wtedy mój tata sprawdził historię przeglądania, żeby zobaczyć, gdzie był. przejdź do Wikipedii? Mam szczęście, że znalazłem tę stronę i artykuł o Analiza LL tutaj. Dlatego daję ci moje pięć gwiazdek.

Ala Borkowski

Minęło trochę czasu odkąd widziałem artykuł o zmiennej napisany w tak dydaktyczny sposób. Podoba mi się.

Zbigniew Orzechowski

Ten wpis o Analiza LL był właśnie tym, co chciałem znaleźć.

Elzbieta Piekarski

Uznałem, że informacje, które znalazłem na temat zmiennej Analiza LL, są bardzo przydatne i przyjemne. Gdybym musiał umieścić 'ale', może to oznaczać, że nie jest wystarczająco wyczerpujące w swoim sformułowaniu, ale poza tym jest świetne.