To tylko jedna z 2 stron tej notatki. Zaloguj się aby zobaczyć ten dokument.
Zobacz
całą notatkę
3.3. Algorytmy parsingu
Problem rozbioru gramatycznego jest próbą odpowiedzi na pytanie: czy dany ciąg symboli
terminalnych jest słowem należącym do języka L(G) generowanego przez daną gramatykę.
Aby odpowiedzieć na to pytanie stosujemy jeden z dwóch algorytmów:
a) algorytm wyprowadzający „top-down”
b) algorytm redukujący „bottom-up”
Rozważany ciąg symboli badany jest zawsze od lewej strony, w tym sensie oba algorytmy są
lewostronne.
Przykład:
E→E + T | T
T→T * F | F
F→(E) | id
Analizowane słowo: id + id * id
Bottom-up
Top-down
id + id * id
E
F + id * id
T + id * id
wywód lewostronny
E + T
T + T
E + T
F + T
id + T
T
T * F
F
F
id + T * F
id + F * F
id + id * F
E + id * id
E + F * id
E + T * id
id
E + T*F
id
id
E + T
id + id * id
od lewej do prawej
wywód prawostronny
E
E
kierunek analizy
od lewej do prawej
Metoda „top-down”
Symbol początkowy
gramatyki
Analizowane słowo
Rozpoczynamy od symbolu wyróżnionego gramatyki. W każdym kroku najbardziej lewy
symbol nieterminalny zastępujemy prawą stroną jakiejś produkcji. Jeśli w wyniku kolejnego
kroku otrzymamy symbol terminalny, to sprawdzamy, czy jest on identyczny z odpowiednim
symbolem analizowanego słowa. Jeśli nie, to „cofamy się” i próbujemy od nowa, korzystając
w ponownym wyprowadzeniu z jakiejś innej produkcji (lub innych produkcji). Jest to
algorytm z powrotami (mało efektywny).
Wynik: akceptacja słowa lub odrzucenie w wyniku przebadania wszystkich możliwości.
Problem: „jak uniknąć konieczności powrotów” może być pozytywnie rozstrzygnięty dla
pewnej klasy gramatyk bezkontekstrowych zwanych gramatykami LL (k). „Top-down”
odtwarza wyprowadzenie lewostronne”
Metoda „bottom-up”
Analizowane słowo
Symbol początkowy
gramatyki
Analizując słowo od lewej strony bierzemy symbol bądź grupę symboli i zastępujemy ją lewą
stroną jakiejś odpowiedniej produkcji. Postępujemy tak długo, aż dojdziemy do symbolu
wyróżnionego gramatyki, co jest równoznaczne z akceptacją słowa. W każdym kroku
powinna być redukowana osnowa, czyli najbardziej na lewo położona fraza prosta.
Problem: „jak znaleźć osnowę nie mając jeszcze drzewa rozbioru syntaktycznego i czym ją
zastąpić” może być pozytywnie rozstrzygnięty dla pewnych klas gramatyk
bezkontekstowych: gramatyk precedencyjnych, czy tzw. gramatyk LR(k). „Bottom=up”
odtwarza wyprowadzenie prawostronne.
... zobacz całą notatkę
Komentarze użytkowników (0)