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:
EE + T | T
TT * F | F
F(E) | id
Analizowane słowo: id + id * id
Top-down Bottom-up
id + id * id
E
E
id * id
F +
E + T
T + id * id
E + T
T + T
E + id * id
F + T
T T * F
id
E + F * id
+ T
id E + T * id
+ T * F
id
F F
id + F * F
E + T * F
id + id * F
id id
E + T
id + id * id
E
kierunek analizy
od lewej do prawej od lewej do prawej
Metoda  top-down
Symbol początkowy
Analizowane słowo
gramatyki
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
wywód prawostronny
wywód lewostronny
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
Symbol początkowy
Analizowane słowo
gramatyki
Analizując słowo od lewej strony bierzemy symbol bądz
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 znalez
ć 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.