Nøkkelforskjellen mellom topp-ned- og bunn-opp-parsing er at topp-ned-parsing utfører parsing fra stirrende symbol til input-strengen, mens bottom-down-parsing utfører parsing fra input-streng til startsymbol. Videre er en annen viktig forskjell mellom topp-ned- og bunn-opp-parsing at topp-ned-parsing bruker mest venstre derivasjon og bottom down-parsing bruker mest høyre derivering.
Språk på høyt nivå hjelper til med å skrive dataprogrammer. De er lettere å forstå av programmereren, men ikke av datamaskinen. Derfor konverterer høynivåprogrammet til maskinkode. Oppgaven til kompilatoren er å konvertere den menneskelige lesbare kildekoden til maskinlesbar maskinkode. Et program går gjennom flere trinn for å konvertere til maskinkode. Hele denne prosessen kalles språkbehandlingssystem. En av dem er samlingen. Syntaksanalysatoren eller parseren er i kompilatoren, og den utfører analyseoppgaven.
Hva er Top Down Parsing?
Hvert programmeringsspråk har et sett med regler for å representere språket. Syntaksanalysatoren eller parsen tar inndatastrengen og sjekker om den er i henhold til grammatikkproduksjonene. Med andre ord, grammatikken skal produsere den strengen ved å bruke et parse-tre.
I topp-ned-parsing skjer parsingen fra startsymbolet og vil nå den gitte inndatastrengen. Vurder følgende grammatikkproduksjonsregler. Inndatastrengen (w) er cad.
S -> cAd
A -> ab /a
Parsetreet etter å ha utført topp-ned-parsing er som følger.
Figur 01: Parse Tree 1 with Top Down Parsing
S produserer c A d og A produserer en b. Snoren er cabd. Det er ikke den nødvendige strengen. Så det er nødvendig å gjøre backtracking, som er å bruke de andre alternativene.
På samme måte produserer S c A d. Å bruke det andre alternativet for A vil gi en. Nå gir den den nødvendige strengen. Derfor aksepterer parseren denne inndatastrengen. Parsetreet etter å ha utført topp-ned-parsing er som følger.
Figur 02: Parse Tree 2 with Top Down Parsing
Når inndatastrengen (w) er abbcde
Vurder følgende grammatikkproduksjonsregler.
S -> aABe
A -> Abc/b
B -> d
I topp-ned-parsing, S -> aABe (erstatter A -> Abc)
S -> aAbcBe (erstatter A -> b)
S -> abbcBe (erstatter B ->d)
S -> abbcde
Substitusjon starter med den venstre variabelen først og deretter til neste høyre posisjon og så videre. Derfor følger den en avledningsmetode mest til venstre. Videre er det viktig å bestemme hvilken produksjonsregel du skal velge når det er en variabel.
Hva er Bottom Up Parsing?
Nedenfra og opp skjer parsing på den andre måten. Parsingen skjer fra inndatastrengen til startsymbolet. Vurder følgende grammatikkproduksjonsregler og la inndatastrengen være w ɛ cad
S -> cAd
A -> ab /a
Parsetreet etter å ha utført nedenfra og opp-parsing er som følger.
Figur 03: Parse tre med bunn-opp-parsing
Den oppgitte strengen er cad. a-en genereres av A. c, A og d kombineres for å få startsymbolet S.
Når inndatastrengen(w) er abbcde
Vurder følgende grammatikkproduksjonsregler.
S -> aABe
A -> Abc/b
B -> d
Nedenfra og opp-parsing, S -> aABe (erstatter B ->d)
S -> aAde (erstatter A -> Abc)
S -> aAbcde (Substuting A -> b)
S -> abbcde
Substitusjon starter med den høyre mest variable først og flytter deretter til neste venstre posisjon og så videre. Derfor følger den en venstremot-avledningsmetode.
Hva er forskjellen mellom Top Down og Bottom Up Parsing?
Topp-ned-parsing er en analysestrategi som først ser på det høyeste nivået av parsetreet og arbeider nedover i parsetreet ved å bruke reglene for en formell grammatikk. Bottom up parsing er en parsingstrategi som først ser på det laveste nivået av parsetreet og arbeider opp parsetreet ved å bruke reglene for en formell grammatikk. Parsingen skjer fra startsymbolet til inngangsstrengen, i topp-ned-parsing. På den annen side skjer parsing fra inndatastrengen til startsymbolet, i bottom up parsing.
I tillegg er hovedavgjørelsen i top-down-parsing å velge hvilken produksjonsregel som skal brukes for å konstruere strengen, mens hovedavgjørelsen i bottom-down-parsing er å velge når en produksjonsregel skal brukes for å redusere strengen til få startsymbolet. Dessuten bruker topp-ned-parsing mest derivasjon til venstre og bunn-ned-parsing bruker mest derivering til høyre.
Sammendrag – Top Down vs Bottom Up Parsing
Forskjellen mellom topp-ned- og bunn-opp-parsing er at topp-ned-parsing utfører parsing fra stjernesymbolet til inndatastrengen mens bottom-down-parsing utfører parsing fra input-streng til startsymbolet.
