Erinevus ülalt alla ja alt üles parsimise vahel

võtme erinevus ülalt alla ja alt üles parsimise vahel on see, et ülevalt alla parsimine viib sõelumise tähisest sümbolist sisestusstringini, samas kui alt üles sõelumine parsib sisestusstringi stardisümboliks. Veel üks oluline erinevus ülalt alla ja alt üles parsimise vahel on see, et ülalt alla sõelumisel kasutatakse kõige vasakpoolset tuletust ja alt üles sõelumisel kasutatakse kõige paremat tuletust.

Kõrgetasemelised keeled aitavad arvutiprogramme kirjutada. Programmeerijal on neid lihtsam mõista, kuid mitte arvutis. Seetõttu teisendab kõrgetasemeline programm masinkoodiks. Kompilaatori ülesanne on teisendada inimloetav lähtekood masinloetavaks masinkoodiks. Masinkoodiks teisendamiseks läbib programm mitu sammu. Kogu seda protsessi nimetatakse keeletöötlussüsteemiks. Üks neist on koostamine. Süntaksianalüsaator või parser on kompilaatoris ja see täidab parsimisülesannet.

SISU

1. Ülevaade ja peamised erinevused
2. Mis on ülalt alla parsimine
3. Mis on alt üles parsimine
4. Kõrvuti võrdlus - ülalt alla vs alt üles parsimine tabelina
5. Kokkuvõte

Mis on ülalt alla parsimine?

Igal programmeerimiskeelel on keele esindamiseks reeglistik. Süntaksianalüsaator või pars võtab sisestusstringi ja kontrollib, kas see vastab grammatikaproduktidele. Teisisõnu, grammatika peaks selle stringi tootma parselduspuu abil.

Ülalt alla sõelumine toimub parsimisest alates sümbolist ja jõuab antud sisestusrida. Mõelge järgmistele grammatika koostamise reeglitele. Sisestusrida (w) on cad.

S -> cAd

A -> ab / a

Pärast ülalt alla sõelumist on parsimispuu järgmine.

Joonis 01: parsi puu 1 koos ülalt alla sõelumisega

S toodab c A d ja A annab b. Nöör on kabiinis. See pole vajalik string. Niisiis, tuleb teha tagantjärele, st kasutada teisi alternatiive.

Sarnaselt toodab S c A d. Teise variandi rakendamine A jaoks annab a. Nüüd annab see vajaliku stringi. Seetõttu aktsepteerib parser seda sisestusstringi. Pärast ülalt alla sõelumist on parsimispuu järgmine.

Joonis 02: Parsi puu 2 koos ülalt alla sõelumisega

Kui sisestusstring (w) on abbcde

Mõelge järgmistele grammatika koostamise reeglitele.

S -> aABe

A -> Abc / b

B -> d

Ülalt alla sõelumine,

S -> aABe (asendades A -> Abc)

S -> aAbcBe (asendades A -> b)

S -> abbcBe (asendades B -> d)

S -> abbcde

Asendamine algab kõigepealt kõige vasakpoolsema muutumisega ja seejärel järgmisse paremasse asendisse jne. Seetõttu järgib ta kõige vasakpoolsemat tuletusmeetodit. Lisaks on oluline otsustada, millist tootmisreeglit valida muutuja olemasolu korral.

Mis on alt üles parsimine?

Altpoolt üles sõelumine toimub muul viisil. Sõelumine toimub sisestusstringi juurest alustamissümbolini. Mõelge järgmistele grammatika koostamise reeglitele ja laske sisestussaadusel olla kaadriline

S -> cAd

A -> ab / a

Sõelumispuu pärast alt üles sõelumist on järgmine.

Joonis 03: Parema puu parsimine alt üles

Antud string on kadr. A genereerib A. c, A ja d ühendatakse, et saada algustäht S.

Kui sisestusstring (w) on abbcde

Mõelge järgmistele grammatika koostamise reeglitele.

S -> aABe

A -> Abc / b

B -> d

Alt üles sõelumine,

S -> aABe (asendades B -> d)

S -> aAde (asendades A -> Abc)

S -> aAbcde (alamlahendus A -> b)

S -> abbcde

Asendamine algab kõigepealt parempoolse kõige muutuvamaga ja liigub seejärel järgmisse vasakpoolsesse asendisse ja nii edasi. Seetõttu järgib see vasakpoolse motiivi tuletamise meetodit.

Mis vahe on ülalt alla ja alt üles sõelumisel??

Ülalt-alla sõelumine on parsimisstrateegia, mis vaatab kõigepealt parsimispuu kõrgeima taseme ja töötab parsimispuu allapoole, kasutades formaalse grammatika reegleid. Alumine üles sõelumine on parsimisstrateegia, mis vaatab kõigepealt parsimispuu madalaima taseme ja töötab parsimispuu üles, kasutades formaalse grammatika reegleid. Sõelumine toimub alates alustamissümbolist kuni sisestusstringini ülalt alla. Teisest küljest toimub parsimine sisendstringist lähte sümbolini, alt üles sõelumisega.

Pealegi on ülalt alla sõelumise peamine otsus valida, millist tootmisreeglit stringi konstrueerimiseks kasutada, samas kui alt üles sõelumise peamine otsus on valida, millal kasutada tootmisreeglit stringi vähendamiseks, et saada algustäht. Lisaks kasutab ülalt alla parsimine kõige vasakpoolset derivatsiooni ja alt üles sõelumist kõige paremat tuletust.

Kokkuvõte - ülalt alla vs alt üles parsimine

Ülalt alla ja alt üles parsimise erinevus seisneb selles, et ülalt alla sõelumine viib läbi tärnimise sümbolist sisestusstringi, samas kui alt üles sõelumine parsib sisestusstringi algus sümboliks..

Viide:

1. “Kompilaatori kujundamise loeng 5 - sissejuhatus parseritesse ja LL (1) parsimine.” Kompilaatori kujundamise loeng 5 - sissejuhatus parseritesse ja LL (1) parsimine, Ravindrababu Ravula väravaloengud, 22. mai 2014. Saadaval siin