Nøgleforskellen mellem top down og bottom up parsing er, at top down parsing udfører parsing fra stirrende symbol til input strengen, mens bottom down parsing udfører parsing fra input streng til start symbol. Desuden er en anden vigtig forskel mellem top down og bottom up parsing, at top down parsing bruger mest venstre afledning og bottom down parsing bruger højre mest afledning.
Sprog på højt niveau hjælper med at skrive computerprogrammer. De er lettere at forstå af programmøren, men ikke af computeren. Derfor konverterer højniveauprogrammet til maskinkode. Compilerens opgave er at konvertere den menneskelige læsbare kildekode til maskinlæsbar maskinkode. Et program gennemgår flere trin for at konvertere til maskinkode. Hele denne proces kaldes sprogbehandlingssystem. En af dem er opsamlingen. Syntaksanalysatoren eller parseren er i compileren, og den udfører parsingopgaven.
Hvad er Top Down Parsing?
Hvert programmeringssprog har et sæt regler, der repræsenterer sproget. Syntaksanalysatoren eller parsen tager inputstrengen og kontrollerer, om den er i overensstemmelse med grammatikproduktionerne. Med andre ord skal grammatikken producere den streng ved hjælp af et parsetræ.
I top-down parsing sker parsingen fra startsymbolet og vil nå den givne inputstreng. Overvej følgende grammatikproduktionsregler. Indtastningsstrengen (w) er cad.
S -> cAd
A -> ab /a
Fortolkningstræet efter at have udført top-down-parsing er som følger.
Figur 01: Parse Træ 1 med Top Down Parsing
S producerer c A d og A producerer en b. Snoren er cabd. Det er ikke den påkrævede streng. Så det er nødvendigt at lave backtracking, hvilket er at bruge de andre alternativer.
På samme måde producerer S c A d. Anvendelse af den anden mulighed for A vil give en. Nu giver den den nødvendige streng. Derfor accepterer parseren denne inputstreng. Parsetræet efter at have udført top down parsing er som følger.
Figur 02: Parse Træ 2 med Top Down Parsing
Når inputstrengen (w) er abbcde
Overvej følgende grammatikproduktionsregler.
S -> aABe
A -> Abc/b
B -> d
I top-down parsing, S -> aABe (erstatter A -> Abc)
S -> aAbcBe (erstatter A -> b)
S -> abbcBe (erstatter B ->d)
S -> abbcde
Udskiftning starter med den venstre mest variable først og derefter til den næste højre position og så videre. Derfor følger den en afledningsmetode mest til venstre. Desuden er det vigtigt at beslutte, hvilken produktionsregel man skal vælge, når der er en variabel.
Hvad er Bottom Up Parsing?
I bottom-up-parsing sker på den anden måde. Parsingen sker fra inputstrengen til startsymbolet. Overvej følgende grammatikproduktionsregler og lad inputstrengen være w ɛ cad
S -> cAd
A -> ab /a
Fortolkningstræet efter at have udført bottom-up-parsing er som følger.
Figur 03: Parse Træ med Bottom Up Parsing
Den givne streng er cad. a'et genereres af A. c, A og d kombineres for at få startsymbolet S.
Når inputstrengen(w) er abbcde
Overvej følgende grammatikproduktionsregler.
S -> aABe
A -> Abc/b
B -> d
I bottom-up-parsing, S -> aABe (erstatter B ->d)
S -> aAde (erstatter A -> Abc)
S -> aAbcde (Substuting A -> b)
S -> abbcde
Udskiftning starter med den mest højre variabel først og flytter derefter til den næste venstre position og så videre. Derfor følger den en venstre mot-afledningsmetode.
Hvad er forskellen mellem Top Down og Bottom Up Parsing?
Top-down parsing er en parsingstrategi, der først ser på det højeste niveau af parsetræet og arbejder ned ad parsetræet ved at bruge reglerne for en formel grammatik. Bottom up parsing er en parsingstrategi, der først ser på det laveste niveau af parsetræet og arbejder op i parsetræet ved at bruge reglerne for en formel grammatik. Parsingen sker fra startsymbolet til inputstrengen, i top down parsing. På den anden side sker parsing fra inputstrengen til startsymbolet, i bottom up parsing.
Ydermere er hovedbeslutningen i top down parsing at vælge hvilken produktionsregel der skal bruges til at konstruere strengen, mens hovedbeslutningen i bottom down parsing er at vælge hvornår en produktionsregel skal bruges til at reducere strengen til få startsymbolet. Desuden bruger top-down-parsing mest venstre-afledning og bottom-down-parsing bruger højre-mest afledning.
Opsummering – Top Down vs Bottom Up Parsing
Forskellen mellem top down og bottom up parsing er, at top down parsing udfører parsing fra det stirrende symbol til inputstrengen, mens bottom down parsing udfører parsing fra input streng til startsymbolet.
