Forskel mellem top-down og bottom up-parsing
Share
Det vigtigste forskel mellem parsning ovenfra og ned og op er, at oppefra og ned parsing udfører parsning fra staringsymbolet til inputstrengen, mens bunden ned-parsing udfører parsing fra input string til startsymbolet. Endvidere er en anden vigtig forskel mellem parsing ovenfra og ned og ned, at parsing ovenfra og ned bruger mest afledning til venstre og nedenunder nedenstående parsing bruger højst afledning.
Sprog på højt niveau hjælper med at skrive computerprogrammer. De er lettere at forstå af programmereren, men ikke af computeren. Derfor konverteres det høje niveau til maskinkode. Kompilatorens 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 samlingen. Syntaksanalysatoren eller parseren findes i compileren, og den udfører parsingopgaven.
INDHOLD
1. Oversigt og nøgleforskel
2. Hvad er Top Down Parsing
3. Hvad er bottom up-parsing
4. Sammenligning side ved side - Top Down vs Bund Up Parsing i tabelform
5. Opsummering
Hvad er Top Down Parsing?
Hvert programmeringssprog har et sæt regler, der repræsenterer sproget. Syntaksanalysatoren eller analysen tager inputstrengen og kontrollerer, om den er i overensstemmelse med grammatikproduktionerne. Med andre ord skal grammatikken producere den streng ved hjælp af et parse-træ.
I top-down parsing sker parsningen fra startsymbolet og når den givne inputstreng. Overvej følgende grammatikproduktionsregler. Inputstrengen (w) er cad.
S -> cAd
A -> ab / a
Analysetræet efter udførelse af top-down-parsing er som følger.
Figur 01: Analyse af træ 1 med top-down-parsing
S producerer cAd og A producerer a b. Strengen er kabi. Det er ikke den krævede streng. Så det er nødvendigt at foretage backtracking, hvilket er at bruge de andre alternativer.
Tilsvarende producerer S cAd. Anvendelse af den anden mulighed for A giver en. Nu giver det den krævede streng. Derfor accepterer parseren denne inputstreng. Analysetræet efter udførelse af top-down-parsing er som følger.
Figur 02: Analyser træ 2 med parsning nedad og ned
Når inputstrengen (w) er abbcde
Overvej følgende grammatikproduktionsregler.
S -> aABe
A -> Abc / b
B -> d
I top down parsing,
S -> aABe (substituering af A -> Abc)
S -> aAbcBe (substituering af A -> b)
S -> abbcBe (substituering af B -> d)
S -> abbcde
Udskiftning starter med den mest variable venstre først og derefter til næste højre position og så videre. Derfor følger den en mest afledt metode. Derudover er det vigtigt at beslutte, hvilken produktionsregel man skal vælge, når der er en variabel.
Hvad er bottom up-parsing?
I bunden op foregår parsning på den anden måde. Analysering sker fra inputstrengen til startsymbolet. Overvej følgende grammatikproduktionsregler, og lad inputstrengen være w ɛ cad
S -> cAd
A -> ab / a
Analysetræet, efter at have udført parsing fra bunden op, er som følger.
Figur 03: Analysetræ med bund-op-parsning
Den givne streng er cad. A 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
Nedefra og op parsning,
S -> aABe (substituering af B -> d)
S -> aAde (substituering af A -> Abc)
S -> aAbcde (substitution A -> b)
S -> abbcde
Udskiftning starter med den højre variabel først og flytter derefter til næste venstre position og så videre. Derfor følger den en venstre mot-deriveringsmetode.
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 parse-træet og arbejder ned på parse-træet ved hjælp af reglerne for en formel grammatik. Bund-up-parsing er en analysestrategi, der først ser på det laveste niveau af parse-træet og arbejder op-analyseret træet ved hjælp af reglerne for en formel grammatik. Analysering sker fra startsymbolet til inputstrengen i top-down parsing. På den anden side foregår parsning fra inputstrengen til startsymbolet i bunden op-parsing.
Endvidere er hovedbeslutningen i parsing ovenfra og ned at vælge, hvilken produktionsregel der skal bruges til at konstruere strengen, mens hovedbeslutningen i parsing nedenfra og ned er at vælge, hvornår en produktionsregel skal bruges til at reducere strengen for at få startsymbolet. Desuden bruger parsing ovenfra og ned til venstre for de fleste afledninger og ved nederste ned-parsing bruger højre afledning.
Resume - Top Down vs Bottom Up Parsing
Forskellen mellem parsing ovenfra og ned og ned er, at parsing ovenfra og ned udfører parsningen fra staringsymbolet til inputstrengen, mens parsing nedefra og ned udfører parsingen fra inputstreng til startsymbolet.
Reference:
1. "Compiler Design Lecture 5 - Introduktion til parsere og LL (1) parsing." Compiler Design Forelæsning 5 - Introduktion til parsere og LL (1) Parsing, Gate-foredrag af Ravindrababu Ravula, den 22. maj 2014. Tilgængelig her
