Nyckelskillnaden mellan parsning uppifrån och ner och nedifrån och upp är att parsningen uppifrån och ner utför analysen från den stirrande symbolen till inmatningssträngen medan den nedre nedåttolkningen utför analysen från inmatningssträngen till startsymbolen. En annan viktig skillnad mellan parsning uppifrån och ner och nedifrån och upp är att uppifrån och ned-parsning använder vänster-mest härledning och bottom-down-parsing använder höger mest härledning.
Språk på hög nivå hjälper till att skriva datorprogram. De är lättare att förstå av programmeraren men inte av datorn. Därför konverterar högnivåprogrammet till maskinkod. Kompilatorns uppgift är att konvertera den mänskliga läsbara källkoden till maskinläsbar maskinkod. Ett program går igenom flera steg för att konvertera till maskinkod. Hela denna process kallas språkbehandlingssystem. En av dem är sammanställningen. Syntaxanalysatorn eller parsern finns i kompilatorn och den utför analysuppgiften.
Vad är Top Down Parsing?
Varje programmeringsspråk har en uppsättning regler som representerar språket. Syntaxanalysatorn eller analysen tar indatasträngen och kontrollerar om den är enligt grammatikproduktionerna. Med andra ord, grammatiken bör producera den strängen med hjälp av ett analysträd.
I parsning uppifrån och ned sker analysen från startsymbolen och kommer att nå den givna inmatningssträngen. Tänk på följande grammatikproduktionsregler. Inmatningssträngen (w) är cad.
S -> cAd
A -> ab /a
Parseträdet efter att ha utfört top-down-analys är följande.
Figur 01: Analysera träd 1 med top-down parsing
S producerar c A d och A producerar ett b. Snöret är cabd. Det är inte den obligatoriska strängen. Så det är nödvändigt att göra backtracking, vilket är att använda de andra alternativen.
På liknande sätt producerar S c A d. Att använda det andra alternativet för A ger en. Nu ger den den önskade strängen. Därför accepterar parsern denna inmatningssträng. Analysträdet efter att ha utfört uppifrån och ned-analys är följande.
Figur 02: Analysera träd 2 med uppifrån och ned-analys
När inmatningssträngen (w) är abbcde
Tänk på följande grammatikproduktionsregler.
S -> aABe
A -> Abc/b
B -> d
I uppifrån och ned-analys, S -> aABe (ersätter A -> Abc)
S -> aAbcBe (ersätter A -> b)
S -> abbcBe (ersätter B ->d)
S -> abbcde
Substitution börjar med den vänstra mest variabeln först och sedan till nästa högra position och så vidare. Därför följer den en härledningsmetod längst till vänster. Dessutom är det viktigt att bestämma vilken produktionsregel man ska välja när det finns en variabel.
Vad är Bottom Up Parsing?
Nedifrån och upp-parsning sker på andra sätt. Parsningen sker från inmatningssträngen till startsymbolen. Tänk på följande grammatikproduktionsregler och låt inmatningssträngen vara w ɛ cad
S -> cAd
A -> ab /a
Parseträdet efter att ha utfört nedifrån och upp-parsning är som följer.
Figur 03: Parse Tree with Bottom Up Parsing
Den givna strängen är cad. a-et genereras av A. c, A och d kombineras för att få startsymbolen S.
När inmatningssträngen(w) är abbcde
Tänk på följande grammatikproduktionsregler.
S -> aABe
A -> Abc/b
B -> d
I bottom-up-analys, S -> aABe (ersätter B ->d)
S -> aAde (ersätter A -> Abc)
S -> aAbcde (ersätter A -> b)
S -> abbcde
Substitution börjar med den högra variabeln först och flyttar sedan till nästa vänstra position och så vidare. Därför följer den en vänstermot-derivationsmetod.
Vad är skillnaden mellan Top Down och Bottom Up Parsing?
Top-down parsing är en analysstrategi som först tittar på den högsta nivån av analysträdet och arbetar nedåt i analysträdet genom att använda reglerna för en formell grammatik. Bottom up parsing är en analysstrategi som först tittar på den lägsta nivån av parseträdet och arbetar upp parseträdet genom att använda reglerna för en formell grammatik. Parsningen sker från startsymbolen till inmatningssträngen, i top-down parsing. Å andra sidan sker parsning från inmatningssträngen till startsymbolen, i bottom up parsing.
Dessutom är huvudbeslutet vid parsning uppifrån och ned att välja vilken produktionsregel som ska användas för att konstruera strängen medan huvudbeslutet vid parsning nedifrån är att välja när en produktionsregel ska användas för att reducera strängen till få startsymbolen. Dessutom använder parsning uppifrån och ned högst vänster härledning och nedifrån och ner används högst höger härledning.
Sammanfattning – Top Down vs Bottom Up Parsing
Skillnaden mellan parsning uppifrån och ner är att parsning uppifrån och ned utför analysen från den stirrande symbolen till inmatningssträngen medan parsing nedifrån utför analysen från indatasträngen till startsymbolen.
