Kluczowa różnica między parsowaniem odgórnym i oddolnym polega na tym, że parsowanie odgórne wykonuje parsowanie od symbolu początkowego do ciągu wejściowego, podczas gdy parsowanie oddolne wykonuje parsowanie od ciągu wejściowego do symbolu początkowego. Co więcej, kolejną ważną różnicą między parsowaniem zstępującym i oddolnym jest to, że parsowanie zstępujące wykorzystuje najbardziej wyprowadzone po lewej stronie, a parsowanie oddolne wykorzystuje najbardziej wyprowadzone po prawej stronie.
Języki wysokiego poziomu pomagają pisać programy komputerowe. Łatwiej je zrozumieć programiście, ale nie komputerowi. Dlatego program wysokiego poziomu konwertuje się na kod maszynowy. Zadaniem kompilatora jest przekształcenie czytelnego dla człowieka kodu źródłowego w czytelny dla komputera kod maszynowy. Program przechodzi przez kilka kroków, aby przekonwertować na kod maszynowy. Cały ten proces nazywa się systemem przetwarzania języka. Jednym z nich jest kompilacja. Analizator składni lub parser znajduje się w kompilatorze i wykonuje zadanie analizowania.
Co to jest parsowanie odgórne?
Każdy język programowania ma zestaw reguł reprezentujących język. Analizator składni lub parsowanie pobiera ciąg wejściowy i sprawdza, czy jest on zgodny z produkcjami gramatycznymi. Innymi słowy, gramatyka powinna wygenerować ten ciąg przy użyciu drzewa analizy.
W parsowaniu zstępującym, parsowanie odbywa się od symbolu początkowego i dociera do podanego ciągu wejściowego. Rozważ następujące zasady tworzenia gramatyki. Ciąg wejściowy (w) to cad.
S -> cAd
A -> ab /a
Drzewo parsowania po wykonaniu parsowania zstępującego wygląda następująco.
Rysunek 01: Analiza drzewa 1 z analizowaniem odgórnym
S tworzy c A d i A tworzy a b. Ciąg to cabd. Nie jest to wymagany ciąg znaków. Tak więc konieczne jest cofanie się, czyli korzystanie z innych alternatyw.
Podobnie, S produkuje c A d. Zastosowanie drugiej opcji dla A da a. Teraz daje wymagany ciąg. Dlatego parser akceptuje ten ciąg wejściowy. Drzewo parsowania po wykonaniu parsowania z góry na dół wygląda następująco.
Rysunek 02: Parsowanie drzewa 2 z analizowaniem odgórnym
Gdy ciąg wejściowy (w) to abbcde
Rozważ następujące zasady tworzenia gramatyki.
S -> aABe
A -> Abc/b
B-> d
W analizowaniu z góry na dół, S -> aABe (zastępuje A-> Abc)
S -> aAbcBe (zastępując A-> b)
S -> abbcBe (zastępuje B ->d)
S-> abbcde
Podstawianie zaczyna się od skrajnie lewej zmiennej, a następnie do następnej prawej pozycji i tak dalej. W związku z tym wynika z najbardziej lewej metody wyprowadzania. Ponadto ważne jest, aby zdecydować, jaką regułę produkcji wybrać, gdy istnieje zmienna.
Co to jest analiza oddolna?
Oddolne parsowanie odbywa się w odwrotny sposób. Parsowanie odbywa się od ciągu wejściowego do symbolu początkowego. Rozważ następujące zasady tworzenia gramatyki i niech ciąg wejściowy będzie w ɛ cad
S -> cAd
A -> ab /a
Drzewo parsowania po wykonaniu analizy oddolnej wygląda następująco.
Rysunek 03: Parsowanie drzewa z analizą oddolną
Podany ciąg to cad. A jest generowane przez A. c, A i d łączą się, aby uzyskać symbol początkowy S.
Gdy ciąg wejściowy (w) to abbcde
Rozważ następujące zasady tworzenia gramatyki.
S -> aABe
A -> Abc/b
B-> d
W analizie oddolnej
S -> aABe (zastępując B->d)
S -> aAde (zastępuje A-> Abc)
S -> aAbcde (Podmiana A -> b)
S-> abbcde
Podstawianie zaczyna się od najbardziej prawej zmiennej, a następnie przechodzi do następnej lewej pozycji i tak dalej. W związku z tym jest to metoda lewostronnego wyprowadzania.
Jaka jest różnica między analizowaniem odgórnym a oddolnym?
Przetwarzanie zstępujące to strategia analizowania, która najpierw sprawdza najwyższy poziom drzewa analizowania i działa w dół drzewa analizowania przy użyciu reguł gramatyki formalnej. Analiza oddolna to strategia analizowania, która najpierw sprawdza najniższy poziom drzewa analizowania i działa w górę drzewa analizowania przy użyciu reguł gramatyki formalnej. Parsowanie odbywa się od symbolu początkowego do ciągu wejściowego, w analizie zstępującej. Z drugiej strony parsowanie odbywa się od ciągu wejściowego do symbolu początkowego, w analizie oddolnej.
Ponadto główną decyzją w parsowaniu zstępującym jest wybór reguły produkcyjnej, która ma być użyta w celu skonstruowania łańcucha, podczas gdy główną decyzją w parsowaniu zstępującym jest wybór, kiedy użyć reguły produkcyjnej, aby zredukować łańcuch do uzyskać symbol początkowy. Co więcej, parsowanie zstępujące wykorzystuje najbardziej wyprowadzone z lewej strony, a analizowanie z dołu w dół wykorzystuje wyprowadzenie z prawej strony.
Podsumowanie – Parsowanie odgórne i oddolne
Różnica między parsowaniem odgórnym a oddolnym polega na tym, że parsowanie odgórne wykonuje parsowanie od symbolu początkowego do ciągu wejściowego, podczas gdy parsowanie oddolne wykonuje parsowanie od ciągu wejściowego do symbolu początkowego.
