Rozdiel medzi analýzou zhora nadol a zdola nahor
Share
kľúčový rozdiel medzi analýzou zhora nadol a zdola nahor je to zhora nadol syntaktická analýza vykonáva syntaktickú analýzu zo štartovacieho symbolu na vstupný reťazec, zatiaľ čo syntaktická analýza zdola dole vykonáva syntaktickú analýzu zo vstupného reťazca na počiatočný symbol. Ďalej je ďalším dôležitým rozdielom medzi syntaktickou analýzou zhora nadol a zdola nahor, že syntaktická analýza zhora nadol používa odvodenie najviac vľavo a syntaktická analýza zdola dole využíva najviac deriváciu..
Jazyky vysokej úrovne pomáhajú písať počítačové programy. Je ľahšie im porozumieť programátor, ale nie počítač. Preto program vysokej úrovne skonvertuje na strojový kód. Úlohou kompilátora je prevádzať ľudský čitateľný zdrojový kód na strojovo čitateľný strojový kód. Program prechádza niekoľkými krokmi na konverziu na strojový kód. Celý tento proces sa nazýva Systém spracovania jazykov. Jedným z nich je kompilácia. Analyzátor syntaxe alebo syntaktický analyzátor je v kompilátore a vykonáva úlohu syntaktického analyzovania.
OBSAH
1. Prehľad a kľúčový rozdiel
2. Čo je analýza zhora nadol
3. Čo je analýza zdola nahor
4. Porovnanie bok po boku - zhora nadol vs parsovanie zdola nahor v tabuľkovej forme
5. Zhrnutie
Čo je analýza zhora nadol?
Každý programovací jazyk má súbor pravidiel, ktoré tento jazyk predstavujú. Analyzátor syntaxe alebo analýza vezme vstupný reťazec a skontroluje, či je v súlade s gramatickými výrobami. Inými slovami, gramatika by mala produkovať tento reťazec pomocou stromu analýzy.
Pri parsovaní zhora nadol sa parsovanie uskutoční od počiatočného symbolu a dosiahne daný vstupný reťazec. Zvážte nasledujúce pravidlá výroby gramatiky. Vstupný reťazec (w) je cad.
S -> cAd
A -> ab / a
Analyzujúci strom po vykonaní analýzy zhora nadol je nasledujúci.
Obrázok 01: Analýza stromu 1 s analýzou zhora nadol
S produkuje c A d a A produkuje b. Reťazec je cabd. Nie je to požadovaný reťazec. Preto je potrebné urobiť spätné sledovanie, ktorým je použitie iných alternatív.
Podobne S produkuje c A d. Použitím druhej možnosti pre A získate a. Teraz poskytuje požadovaný reťazec. Analyzátor preto prijíma tento vstupný reťazec. Analyzujúci strom po vykonaní analýzy zhora nadol je nasledujúci.
Obrázok 02: Parsový strom 2 s analýzou zhora nadol
Keď je vstupný reťazec (w) abbcde
Zvážte nasledujúce pravidlá výroby gramatiky.
S -> aABe
A -> Abc / b
B -> d
V analýze zhora nadol,
S -> aABe (Náhrada A -> Abc)
S -> aAbcBe (Náhrada A -> b)
S -> abbcBe (Náhrada B -> d)
S -> abbcde
Substitúcia začína najskôr ľavou premennou a potom na nasledujúcu pravú pozíciu atď. Preto sa riadi metódou odvodenia najviac vľavo. Ďalej je dôležité rozhodnúť sa, ktoré výrobné pravidlo sa má zvoliť, keď existuje premenná.
Čo je analýza zdola nahor?
Pri analýze zdola nahor dochádza k inému spôsobu. K analýze dochádza od vstupného reťazca po počiatočný symbol. Zvážte nasledujúce pravidlá výroby gramatiky a nechajte vstupný reťazec w ɛ cad
S -> cAd
A -> ab / a
Analyzujúci strom po vykonaní analýzy zdola nahor je nasledujúci.
Obrázok 03: Analyzovať strom s analýzou zdola nahor
Daný reťazec je cad. A je vygenerovaný A. Kombinácie c, A a d získajú počiatočný symbol S.
Keď je vstupný reťazec (w) abbcde
Zvážte nasledujúce pravidlá výroby gramatiky.
S -> aABe
A -> Abc / b
B -> d
V analýze zdola nahor,
S -> aABe (Náhrada B -> d)
S -> aAde (Náhrada A -> Abc)
S -> aAbcde (Náhrada A -> b)
S -> abbcde
Substitúcia začína najskôr tou najpremennejšou premennou a potom sa presunie na nasledujúcu ľavú pozíciu a tak ďalej. Preto sa riadi metódou odvodenia ľavého motívu.
Aký je rozdiel medzi analýzou zhora nadol a zdola nahor?
Analýza zhora nadol je syntaktická analýza, ktorá sa najprv zameriava na najvyššiu úroveň stromu analýzy a potom analyzuje strom pomocou pravidiel formálnej gramatiky. Analýza zdola nahor je syntaktickou stratégiou, ktorá sa najprv zameriava na najnižšiu úroveň stromu analýzy a spracuje strom analýzy pomocou pravidiel formálnej gramatiky. K analýze dochádza od počiatočného symbolu po vstupný reťazec, v analýze zhora nadol. Na druhej strane k analýze dochádza od vstupného reťazca po počiatočný symbol, pri analýze zdola nahor.
Okrem toho hlavným rozhodnutím pri analýze zhora nadol je vybrať, ktoré výrobné pravidlo sa má použiť na zostavenie reťazca, zatiaľ čo hlavným rozhodnutím pri analýze zdola dole je vybrať, kedy sa použije výrobné pravidlo na zníženie reťazca, aby sa získal počiatočný symbol. Navyše, analýza zhora nadol používa najviac odvodenú deriváciu a analýza zdola dole používa naj pravú deriváciu.
Zhrnutie - zhora nadol proti analýze zdola nahor
Rozdiel medzi syntaktickou analýzou zhora nadol a zdola nahor spočíva v tom, že syntaktická analýza zhora nadol vykonáva syntaktickú analýzu zo začiatočného symbolu na vstupný reťazec, zatiaľ čo syntaktická analýza zdola dole vykonáva parsovanie od vstupného reťazca k počiatočnému symbolu..
referencie:
1. „Prednáška 5 o návrhu kompilátora - úvod do syntaktickej analýzy a analýzy LL (1).“ Prednáška kompilátora 5 - Úvod do syntaktického analyzátora a analýzy LL (1), Prednášky brán od Ravindrababu Ravula, 22. mája 2014. K dispozícii tu
