Różnica między analizą z góry na dół i z dołu do góry

The kluczowa różnica pomiędzy analizą z góry na dół i z dołu do góry jest to, że z góry na dół parsowanie wykonuje parsowanie od symbolu początkowego do ciągu wejściowego, podczas gdy parsowanie od dołu wykonuje parsowanie od ciągu wejściowego do symbolu początkowego. Ponadto kolejną ważną różnicą między analizowaniem z góry na dół i z dołu do góry jest to, że podczas analizowania z góry na dół używa się lewej pochodnej najbardziej, a podczas analizy z dołu na dół używa najbardziej pochodnej.

Języki wysokiego poziomu pomagają pisać programy komputerowe. Są łatwiejsze do zrozumienia dla programisty, ale nie dla komputera. Dlatego program wysokiego poziomu konwertuje na kod maszynowy. Zadaniem kompilatora jest konwersja kodu źródłowego czytelnego dla człowieka na kod maszynowy do odczytu maszynowego. Program przechodzi kilka kroków w celu konwersji na kod maszynowy. Cały ten proces nazywa się systemem przetwarzania języka. Jednym z nich jest kompilacja. Analizator składni lub analizator składni znajduje się w kompilatorze i wykonuje zadanie analizowania.

ZAWARTOŚĆ

1. Przegląd i kluczowa różnica
2. Co to jest parsowanie z góry na dół
3. Co to jest parsowanie od dołu do góry
4. Porównanie obok siebie - parsowanie z góry na dół vs z dołu do góry w formie tabelarycznej
5. Podsumowanie

Co to jest parsowanie z góry na dół?

Każdy język programowania ma zestaw zasad reprezentujących ten język. Analizator składni lub parsowanie pobiera ciąg wejściowy i sprawdza, czy jest zgodny z produkcjami gramatycznymi. Innymi słowy, gramatyka powinna wytwarzać ten ciąg przy użyciu drzewa analizy.

Podczas parsowania z góry na dół parsowanie odbywa się od symbolu początkowego i osiąga podany ciąg wejściowy. Rozważ następujące zasady produkcji gramatyki. Łańcuch wejściowy (w) to cad.

S -> cAd

A -> ab / a

Drzewo parsowania po parsowaniu z góry na dół wygląda następująco.

Rysunek 01: Analiza drzewa 1 z analizą z góry na dół

S produkuje c A d, a A wytwarza a b. Sznurek jest cabd. To nie jest wymagany ciąg. Tak więc konieczne jest wykonanie backtrackingu, który polega na użyciu innych alternatyw.

Podobnie S wytwarza c A d. Zastosowanie innej opcji dla A da. Teraz daje wymagany ciąg. Dlatego analizator składni akceptuje ten ciąg wejściowy. Drzewo parsowania po parsowaniu z góry na dół wygląda następująco.

Rysunek 02: Analiza drzewa 2 z analizą z góry na dół

Gdy ciąg wejściowy (w) jest abbcde

Rozważ następujące zasady produkcji gramatyki.

S -> aABe

A -> Abc / b

B -> d

Podczas analizy z góry na dół,

S -> aABe (Podstawienie A -> Abc)

S -> aAbcBe (Zastępowanie A -> b)

S -> abbcBe (Podstawienie B -> d)

S -> abbcde

Podstawienie zaczyna się od lewej najbardziej zmiennej, a następnie do następnej prawej pozycji i tak dalej. Dlatego stosuje się metodę wyprowadzania najbardziej na lewo. Ponadto ważne jest, aby zdecydować, którą regułę produkcji wybrać, gdy istnieje zmienna.

Co to jest analizowanie od dołu do góry?

W oddolnej analizie odbywa się w inny sposób. Analiza odbywa się od ciągu wejściowego do symbolu początkowego. Rozważ następujące reguły produkcji gramatyki i pozwól, aby łańcuch wejściowy był w ɛ cad

S -> cAd

A -> ab / a

Drzewo parsowania po wykonaniu analizy typu bottom up jest następujące.

Rysunek 03: Analiza drzewa z analizą od dołu do góry

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) jest abbcde

Rozważ następujące zasady produkcji gramatyki.

S -> aABe

A -> Abc / b

B -> d

W analizie oddolnej,

S -> aABe (Podstawienie B -> d)

S -> aAde (Podstawienie A -> Abc)

S -> aAbcde (Podstawienie A -> b)

S -> abbcde

Podstawianie rozpoczyna się od prawej najbardziej zmiennej, a następnie przechodzi do następnej lewej pozycji i tak dalej. Dlatego stosuje się metodę wyprowadzenia lewego mota.

Jaka jest różnica między analizą z góry na dół i z dołu do góry?

Parsowanie z góry na dół jest strategią parsowania, która najpierw sprawdza najwyższy poziom parsowanego drzewa i pracuje nad parsowanym drzewem przy użyciu reguł gramatyki formalnej. Parsowanie od dołu to strategia analizowania, która najpierw sprawdza najniższy poziom drzewa analizy i rozwija drzewo analizy przy użyciu reguł gramatyki formalnej. Analiza odbywa się od symbolu początkowego do ciągu wejściowego, w analizie z góry na dół. Z drugiej strony parsowanie odbywa się od ciągu wejściowego do symbolu początkowego, w parsowaniu od dołu do góry.

Ponadto główną decyzją w analizie z góry na dół jest wybór reguły produkcji, która ma zostać użyta do zbudowania łańcucha, podczas gdy główną decyzją przy analizie z dołu do góry jest wybranie, kiedy należy użyć reguły produkcji, aby zmniejszyć ciąg, aby uzyskać symbol początkowy. Ponadto parsowanie z góry na dół wykorzystuje pochodzenie najbardziej z lewej strony, a parsowanie z dołu na dół wykorzystuje pochodzenie z prawej strony.

Podsumowanie - parsowanie z góry na dół vs z dołu do góry

Różnica między parsowaniem z góry na dół i z dołu do góry polega na tym, że parsowanie z góry na dół wykonuje parsowanie od symbolu oznaczającego do ciągu wejściowego, podczas gdy parsowanie od dołu do dołu wykonuje parsowanie od ciągu wejściowego do symbolu początkowego.

Odniesienie:

1. „Projekt kompilatora Wykład 5 - Wprowadzenie do parserów i analizowania LL (1)”. Projektowanie kompilatorów Wykład 5 - Wprowadzenie do parserów i analizowania LL (1), Wykłady wrota Ravindrababu Ravula, 22 maja 2014 r. Dostępne tutaj