Pracuję nad koncepcjami kompilatorów, ale jestem trochę zdezorientowany ... Wyszukiwanie w Google nie doprowadziło mnie do jednoznacznej odpowiedzi.
Czy parsery SLR i LR (0) są takie same? Jeśli nie, jaka jest różnica?
Pracuję nad koncepcjami kompilatorów, ale jestem trochę zdezorientowany ... Wyszukiwanie w Google nie doprowadziło mnie do jednoznacznej odpowiedzi.
Czy parsery SLR i LR (0) są takie same? Jeśli nie, jaka jest różnica?
Odpowiedzi:
Zarówno parsery LR (0), jak i SLR (1) są parserami oddolnymi , kierunkowymi i predykcyjnymi . To znaczy że
Zarówno LR (0), jak i SLR (1) są parserami przesuwania / redukcji , co oznacza, że przetwarzają tokeny strumienia wejściowego, umieszczając je na stosie i w każdym punkcie albo przesuwając token, wpychając go na stos lub zmniejszając niektóre sekwencja terminali i nieterminali na szczycie stosu z powrotem do jakiegoś nieterminalnego symbolu. Można wykazać, że każda gramatyka może być analizowana od dołu do góry za pomocą parsera przesunięcia / zmniejszenia, ale ten parser może nie być deterministyczny . Oznacza to, że parser może „zgadywać”, czy zastosować przesunięcie, czy redukcję, i może skończyć się koniecznością cofnięcia się, aby zdać sobie sprawę, że dokonał złego wyboru. Bez względu na to, jak potężny jest skonstruowany przez ciebie deterministyczny parser przesunięcia / redukcji, nigdy nie będzie on w stanie przeanalizować wszystkich gramatyk.
Kiedy deterministyczny parser przesunięcia / redukcji jest używany do analizowania gramatyki, której nie może obsłużyć, skutkuje to przesunięciem / redukcją konfliktów lub redukcją / redukcją konfliktów , w których parser może wejść w stan, w którym nie może powiedzieć, jaką akcję podjąć. W konflikcie przesuń / zredukuj nie jest w stanie stwierdzić, czy powinien dodać kolejny symbol do stosu, czy wykonać jakąś redukcję na wierzchnich symbolach stosu. W przypadku konfliktu redukuj / zmniejszaj parser wie, że musi zastąpić górne symbole stosu jakimś nieterminalem, ale nie może powiedzieć, jakiej redukcji użyć.
Przepraszam, jeśli jest to długa ekspozycja, ale potrzebujemy tego, aby móc rozwiązać różnicę między analizowaniem LR (0) i SLR (1). Parser LR (0) to parser przesunięcia / redukcji, który używa zerowych tokenów lookahead do określenia, jakie działanie ma podjąć (stąd 0). Oznacza to, że w dowolnej konfiguracji parsera parser musi mieć do wyboru jednoznaczną akcję - albo przesuwa określony symbol, albo stosuje określoną redukcję. Jeśli kiedykolwiek trzeba dokonać dwóch lub więcej wyborów, parser zawiedzie i mówimy, że gramatyka nie jest LR (0).
Przypomnij sobie, że dwa możliwe konflikty LR to przesunięcie / zmniejszenie i zmniejszenie / zmniejszenie. W obu tych przypadkach są co najmniej dwie akcje, które może wykonać automat LR (0) i nie jest on w stanie określić, którego z nich użyć. Ponieważ co najmniej jedną z sprzecznych akcji jest redukcja, rozsądną linią ataku byłaby próba nakłonienia analizatora składni do większej ostrożności podczas wykonywania określonej redukcji. Mówiąc dokładniej, załóżmy, że parser może spojrzeć na następny element wejściowy, aby określić, czy powinien on przesunąć, czy zmniejszyć. Jeśli pozwolimy parserowi na redukcję tylko wtedy, gdy "ma to sens" (dla jakiejś definicji "ma sens"), wtedy możemy być w stanie wyeliminować konflikt poprzez wybranie przez automat konkretnie wyboru przesunięcia lub zmniejszenia w konkretny krok.
W SLR (1) („Uproszczony LR (1)”) parser może patrzeć na jeden token wyprzedzenia przy podejmowaniu decyzji, czy powinien przesunąć, czy zmniejszyć. W szczególności, gdy parser chce spróbować zredukować coś w postaci A → w (dla nieterminala A i łańcucha w), sprawdza następny element wejściowy. Jeśli ten token mógłby legalnie pojawić się po nieterminale A w jakiejś derywacji, parser redukuje. W przeciwnym razie nie. Intuicja jest taka, że w niektórych przypadkach nie ma sensu próbować redukcji, ponieważ biorąc pod uwagę tokeny, które widzieliśmy do tej pory i nadchodzący token, nie ma możliwości, aby redukcja była kiedykolwiek poprawna.
Jedyną różnicą między LR (0) a SLR (1) jest ta dodatkowa zdolność pomagania w podejmowaniu decyzji, jakie działania należy podjąć w przypadku konfliktów. Z tego powodu każda gramatyka, która może być przeanalizowana przez parser LR (0), może zostać przeanalizowana przez parser SLR (1). Jednak parsery SLR (1) mogą analizować większą liczbę gramatyki niż LR (0).
W praktyce jednak SLR (1) jest nadal dość słabą metodą analizy. Częściej zobaczysz używane parsery LALR (1) ("Lookahead LR (1)"). One również działają, próbując rozwiązać konflikty w parserze LR (0), ale zasady, których używają do rozwiązywania konfliktów, są znacznie bardziej precyzyjne niż te używane w SLR (1), w związku z czym znacznie większa liczba gramatyk to LALR (1) niż SLR (1). Aby być bardziej szczegółowym, parsery SLR (1) próbują rozwiązywać konflikty, przyglądając się strukturze gramatyki, aby dowiedzieć się więcej o tym, kiedy zmienić, a kiedy zmniejszyć. Parsery LALR (1) sprawdzają zarówno gramatykę, jak i parser LR (0), aby uzyskać jeszcze bardziej szczegółowe informacje o tym, kiedy przesunąć, a kiedy zmniejszyć. Ponieważ LALR (1) może przyjrzeć się strukturze parsera LR (0), może dokładniej zidentyfikować, kiedy pewne konflikty są fałszywe.yacci bisondomyślnie produkuje parsery LALR (1).
Historycznie, parsery LALR (1) były zwykle konstruowane za pomocą innej metody, która opierała się na znacznie potężniejszym parserze LR (1), więc często będzie można zobaczyć LALR (1) opisywany w ten sposób. Aby to zrozumieć, musimy porozmawiać o parserach LR (1). W parserze LR (0) parser działa śledząc, gdzie może się znajdować w środku produkcji. Gdy stwierdzi, że osiągnął koniec produkcji, wie, że powinien spróbować zmniejszyć. Jednak parser może nie być w stanie stwierdzić, czy znajduje się na końcu jednej produkcji, a w środku innej, co prowadzi do konfliktu przesunięcia / redukcji, lub która z dwóch różnych produkcji osiągnął koniec (redukcja / zmniejszyć konflikt). W LR (0) natychmiast prowadzi to do konfliktu i parser zawodzi. W SLR (1) lub LALR (1),
W parserze LR (1) parser śledzi dodatkowe informacje podczas pracy. Oprócz śledzenia, jaka produkcja według analizatora składni jest używana, śledzi również możliwe tokeny, które mogą pojawić się po zakończeniu tej produkcji. Ponieważ parser śledzi te informacje na każdym kroku, a nie tylko wtedy, gdy musi podjąć decyzję, parser LR (1) jest znacznie potężniejszy i bardziej precyzyjny niż jakikolwiek inny LR (0), SLR (1) lub Parsery LALR (1), o których mówiliśmy do tej pory. LR (1) jest niezwykle potężną techniką parsowania i można wykazać za pomocą skomplikowanej matematyki, że każdy język, który może być analizowany deterministycznie przez dowolny parser shift / redukuj, ma pewną gramatykę, którą można przeanalizować za pomocą automatu LR (1). (Zwróć uwagę, że nie oznacza to, że wszystkie gramatykiktóre mogą być analizowane deterministycznie to LR (1); to tylko mówi, że język, który może być analizowany deterministycznie, ma pewną gramatykę LR (1)). Jednak ta moc ma swoją cenę, a wygenerowany parser LR (1) może wymagać tak dużej ilości informacji do działania, że nie można go wykorzystać w praktyce. Na przykład parser LR (1) dla prawdziwego języka programowania może wymagać dziesiątek do setek megabajtów dodatkowych informacji do prawidłowego działania. Z tego powodu LR (1) nie jest zwykle używany w praktyce, a zamiast niego używane są słabsze parsery, takie jak LALR (1) lub SLR (1).
Niedawno popularność zyskał nowy algorytm analizy składni o nazwie GLR (0) („Uogólniony LR (0)”). Zamiast próbować rozwiązać konflikty, które pojawiają się w parserze LR (0), parser GLR (0) działa zamiast tego, próbując równolegle wszystkich możliwych opcji. Używając sprytnych sztuczek, można to zrobić bardzo wydajnie w przypadku wielu gramatyk. Co więcej, GLR (0) może w ogóle parsować dowolną gramatykę bezkontekstową , nawet te gramatyki, których nie może przeanalizować parser LR (k) dla żadnego k. Inne parsery również są w stanie to zrobić (na przykład parser Earley lub parser CYK), chociaż GLR (0) jest w praktyce szybszy.
Jeśli chcesz dowiedzieć się więcej, tego lata poprowadziłem wstępny kurs kompilatorów i spędziłem niecałe dwa tygodnie na rozmowie o technikach parsowania. Jeśli chcesz uzyskać bardziej rygorystyczne wprowadzenie do LR (0), SLR (1) i wielu innych potężnych technik parsowania, możesz cieszyć się moimi slajdami z wykładów i zadaniami domowymi dotyczącymi analizowania. Wszystkie materiały szkoleniowe są dostępne tutaj, na mojej osobistej stronie .
Mam nadzieję że to pomoże!
Tego się nauczyłem. Zwykle parser LR (0) może mieć niejednoznaczność, tj. Jedno pole tabeli (wyprowadzone do utworzenia parsera) może mieć wiele wartości (lub), aby lepiej to ująć: parser prowadzi do dwóch końcowych stanów z tym samym wejściem. Więc parser SLR jest tworzony, aby usunąć tę niejednoznaczność. Aby go zbudować, znajdź wszystkie produkcje, które prowadzą do stanów goto, znajdź następujący symbol produkcji po lewej stronie i uwzględnij tylko te stany goto, które są obecne w następujących. Ta zmiana oznacza, że nie uwzględniasz produkcji, która nie jest możliwa przy użyciu oryginalnej gramatury (ponieważ ten stan nie znajduje się w następującym zestawie)