Forskjell mellom topp ned og bunn opp parsing
Share
De nøkkelforskjell mellom toppen ned og bunn opp parsing er det topp ned parsing utfører parsing fra stjernesymbolet til inngangsstrengen mens den nedre nedparsing utfører parsing fra inngangsstrengen til startsymbolet. Videre er en annen viktig forskjell mellom topp ned og bunn opp parsing at topp ned parsing bruker left most derivation og bottom down parsing bruker rett mest derivasjon.
Språk på høyt nivå bidrar til å skrive dataprogrammer. De er lettere å forstå av programmereren, men ikke av datamaskinen. Derfor konverterer programmet på høyt nivå 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 Language Processing System. En av dem er samlingen. Syntaksanalysatoren eller parseren er i kompilatoren, og den utfører parsing oppgaven.
INNHOLD
1. Oversikt og nøkkelforskjell
2. Hva er Top Down Parsing
3. Hva er Bottom Up Parsing
4. Sammenligning ved siden av siden - Top Down vs Bottom Up Parsing i tabellform
5. Sammendrag
Hva er Top Down Parsing?
Hvert programmeringsspråk har et sett med regler for å representere språket. Syntaxanalysatoren eller parsen tar inntastingsstrengen og kontrollerer om den er i henhold til grammatikkproduksjonene. Med andre ord, grammatikken skal produsere den strengen ved hjelp av et parsetre.
I topp ned parsing skjer parsing fra startsymbolet og vil nå den angitte inntastingsstrengen. Vurder følgende grammatikkproduksjonsregler. Inngangstrengen (w) er cad.
S -> cAd
A -> ab / a
Parse-treet etter å ha utført topp nedsparing er som følger.
Figur 01: Parse Tree 1 med Top Down Parsing
S produserer c A d og A produserer en b. Strengen er cabd. Det er ikke nødvendig streng. Så, det er nødvendig å gjøre backtracking, som er å bruke de andre alternativene.
På samme måte produserer S c a d. Bruk av det andre alternativet for A vil gi en. Nå gir den ønsket streng. Derfor aksepterer parseren denne inntastingsstrengen. Parse-treet etter å ha utført topp nedsparing er som følger.
Figur 02: Parse Tree 2 med Top Down Parsing
Når inngangsstrengen (w) er abbcde
Vurder følgende grammatikkproduksjonsregler.
S -> aABe
A -> Abc / b
B -> d
I topp ned parsing,
S -> aABe (Bytter A -> Abc)
S -> aAbcBe (Bytter A -> b)
S -> abbcBe (Bytter B -> d)
S -> abbcde
Bytte begynner med venstre mest variable først og deretter til neste høyre posisjon og så videre. Derfor følger det en venstre mest avledningsmetode. Videre er det viktig å bestemme hvilken produksjonsregel som skal velges når det er en variabel.
Hva er Bottom Up Parsing?
I bunnen opptrer parsing i den andre veien. Parsing skjer fra inngangsstrengen til startsymbolet. Vurder følgende grammatikkproduksjonsregler og la inngangsstrengen være w ɛ cad
S -> cAd
A -> ab / a
Parsetræret etter å ha analysert undersiden, er som følger.
Figur 03: Parse Tree med Parsing opp ned
Gitt streng er cad. A er generert av A. c, a og d kombinerer for å få startsymbolet S.
Når inngangsstrengen (w) er abbcde
Vurder følgende grammatikkproduksjonsregler.
S -> aABe
A -> Abc / b
B -> d
I bunnen oppsparsing,
S -> aABe (Bytter B -> d)
S -> aAde (Bytter A -> Abc)
S -> aAbcde (Substuting A -> b)
S -> abbcde
Substitusjon starter med den høyeste variabelen først og deretter flyttes til neste venstre posisjon og så videre. Derfor følger det en venstre mot-derivasjonsmetode.
Hva er forskjellen mellom Top Down og Bottom Up Parsing?
Top-down-parsing er en parsingstrategi som først ser på høyeste nivå av parse-treet og arbeider ned i parsetreet ved å bruke reglene for en formell grammatikk. Bottom up parsing er en parsing strategi som først ser på det laveste nivået av parse treet og arbeider opp parse treet ved hjelp av reglene i en formell grammatikk. Parsingen skjer fra start-symbolet til inngangsstrengen, i øverste nedeparsing. På den annen side oppstår parsing fra inntastingsstrengen til startsymbolet, i oppgradering under bunnen.
Videre er hovedbeslutningen i topp nedparsing å velge hvilken produksjonsregel som skal brukes for å konstruere strengen, mens hovedavgjørelsen i nedre parsing er å velge når å bruke en produksjonsregel for å redusere strengen for å få startsymbolet. Videre bruker topp ned parsing venstre mest derivasjon og nederst ned parsing bruker riktig mest avledning.
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 inngangsstrengen mens bunn ned parsing utfører parsing fra inngangsstrengen til startsymbolet.
Henvisning:
1. "Compiler Design Lecture 5 - Introduksjon til Parsers og LL (1) Parsing." Compiler Design Lecture 5 - Introduksjon til Parsers og LL (1) Parsing, Gateforelesninger av Ravindrababu Ravula, 22. mai 2014. Tilgjengelig her
