Objaśnienie przedrostka viable

Question

Objaśnienie przedrostka viable

W Księdze kompilatorów Ullmana, w shift reduce parsing podana jest następująca definicja przedrostka:

" zbiór prefiksów prawych form sentencyjnych, które mogą pojawić się na stosie parsera shift-reduce, nazywa się realnymi prefiksami. Równoważna definicja realnego przedrostka jest taka, że jest to przedrostek prawej formy sentencyjnej, który nie przechodzi poza prawy koniec prawego uchwytu tej formy sentencyjnej. Zgodnie z tą definicją zawsze można dodać terminal symbole na końcu przedrostka w celu uzyskania właściwej formy sentencyjnej. W związku z tym nie ma widocznego błędu, o ile część wejścia widziana do danego punktu może być zredukowana do realnego prefiksu."

Nie rozumiem tej definicji. Czy ktoś mógłby wyjaśnić znaczenie przedrostka viable na przykładzie ?
W szczególności proszę wyjaśnić znaczenie
"Równoważna definicja przedrostka realnego jest taka, że jest to przedrostek właściwej formy sentencyjnej, który nie kontynuuje poza prawym końcem prawego uchwytu tego formularza sentential "

23

compiler-construction parsing

Author: Happy Mittal, 2010-11-17

Source

3 answers

Rozważ gramatykę podaną w książce (powtórzę ją tutaj)

E -> E+T | T
T -> T*F | F 
F -> (E) | id

Który jest rozszerzany przez dodanie w nim E' -> E

A teraz spójrz na to wyprowadzenie,

E' -> E
   -> E+T
   -> E+T*F

Twierdzenie E + T * jest przedrostkiem realnym

Argument: ta pochodna jest właściwą formą sentencyjną & E+ T * jest jej prefiksem. Handle currently is T * F (jako redukcja T*F do T możemy osiągnąć symbol startowy i stąd pomyślne parsowanie)

I stąd E + T * jest realnym prefiksem, ponieważ jest przedrostek right sentential form & nie rozszerza się poza prawy uchwyt dla tego sentential form. :)

Inny sposób zdefiniowania to:

The prefixes of right sentential forms that can appear on the stack of a shiftreduce
parser are called viable prefixes.

6

Author: ak2,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2013-02-19 07:22:53

Uznałem, że warto podać formalną definicję przydatnych przedrostków, na wszelki wypadek, jeśli ktoś uzna to za bardziej zrozumiałe(tak jak ja).

Biorąc pod uwagę gramatykę , mówimy, że jest realnym prefiksem z jeśli istnieje prawostronna pochodna

Takie, że .

Źródło .

1

Author: newbie,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2017-11-05 06:43:11

score 35 · Accepted Answer

Edytuj (a właściwie przepisuj): zdanie, o które prosiłeś o wyjaśnienie, jest wielką kulką włosów! Potrzebowałem trochę odświeżenia języka i automatyki, aby wybrać tę kulę włosów. Znalazłem te notatki z wykładów bardzo przydatne w tym zakresie.

Nie ułatwia to również tego, że terminy są definiowane jako ekspansja odgórna, podczas gdy pochodne prawe są zwykle używane z analizowaniem oddolnym!

Użyję następującego wyrażenia gramatyka do zilustrowania:

    expr -> expr + term | term
    term -> term * factor | factor
    factor -> NUMBER | ( expr )

A right-sentential form jest formą sentential, która może być osiągnięta przez wyprowadzenie z prawej strony, co jest innym sposobem opisania powtarzającego się rozszerzenia tylko z prawej strony symbolu nieterminalnego podczas przechodzenia z góry na dół. Jest to prawowierna pochodna, a wszystkie formy w niej są więc prawowiernymi formami: {]}

    expr -> expr + term
         -> expr + term * factor
         -> expr + term * NUMBER
         -> expr + factor * NUMBER
         -> expr + NUMBER * NUMBER
         -> expr + term + NUMBER * NUMBER
         -> expr + NUMBER + NUMBER * NUMBER
         -> term + NUMBER + NUMBER * NUMBER
         -> NUMBER + NUMBER + NUMBER * NUMBER

A prefiks postaci sentencyjnej (czy to prawej, czy innej) jest sekwencją danych wejściowych symbole, które zmniejszają się do zera lub więcej symboli wiodących danej postaci sentencyjnej. Pusta sekwencja jest trywialnie przedrostkiem każdej postaci sentencjalnej, a pełna sekwencja symboli tworzących formę sentencjalną jest trywialnie jej przedrostkiem.
Wyrażenie proste jest rozszerzeniem pojedynczego symbolu nieterminalnego, który zajmuje miejsce w formie sentencyjnej. Na przykład {[2] } jest prostą frazą, ponieważ jest rozszerzeniem term, a sama term występuje w trzech produkcje.
Uchwyt formularza sentencyjnego jest najbardziej prostą frazą po lewej stronie w tym formularzu. (Przyznaję, uważam, że termin "uchwyt" jest nieco mylący.) W wyprowadzeniu prostym, uchwyt jest łatwy do zidentyfikowania-jest to ciąg symboli, który wynikał z ostatnio rozszerzonego nieterminalu. Jeśli pracujesz oddolnie, tak jak robi to parser shift-reduce, uchwyt jest prostą frazą , która musi zostać zmniejszona dalej. (Czytaj powyższa tabela wyprowadzeń od dołu do góry, patrząc na to, które symbole zostały zredukowane, aby zobaczyć, co mam na myśli.)
Przedrostek realny formy prawosądowej jest przedrostkiem, który nie rozciąga się poza uchwyt tej formy-innymi słowy, ten przedrostek jest ważny i nie zawiera ograniczonych prostych zwrotów, z możliwym wyjątkiem samego uchwytu, jeśli prefiks rozciąga się dokładnie na koniec uchwytu.

Z punktu widzenia shift-reduce parsera, jako tak długo, jak masz realny prefiks na stosie, nie byłeś jeszcze zmuszony albo zmniejszyć (być może niekompletne) proste wyrażenie na szczycie stosu do nowego nieterminalu lub nie udało się parsować, jeśli nie można go zmniejszyć. Jeśli przesunięcie kolejnego symbolu spowodowałoby coś innego niż realny prefiks, musisz w tym momencie albo zmniejszyć, albo zawieść.

Jeśli analizujesz Język bez kontekstu, istnieje dość wygodna właściwość, która pomaga w budowaniu tabel shift-reduce parser: zbiór wszystkich realnych prefiksów języka bezkontekstowego sam w sobie jest językiem regularnym! można więc zbudować skończony automat, który rozpoznaje regularny język przedrostków i używa go do określenia, kiedy przesunąć, a kiedy zmniejszyć. Ta kombinacja stosu i skończonej maszyny stanowej jest zasadniczo automatem push-down, który jest dokładnie klasą automatu potrzebną do rozpoznania języka bez kontekstu.