Verschil tussen Top Down en Bottom Up Parsing

De belangrijk verschil tussen parseren van boven naar onder en van boven is dat ondersteboven parsing voert de parsing uit van het stersymbool naar de ingevoerde string terwijl de bottom-down parsing de parsing uitvoert van de invoertekenreeks naar het startsymbool. Verder is een ander belangrijk verschil tussen top-down en bottom-up parsing dat de top-down-parsering links de meeste afleiding gebruikt en bottom-down parsing de meest afleidende rechts-weg gebruikt.

Talen op hoog niveau helpen bij het schrijven van computerprogramma's. Ze zijn gemakkelijker te begrijpen door de programmeur, maar niet door de computer. Daarom wordt het programma op hoog niveau geconverteerd naar machinecode. De taak van de compiler is om de menselijk leesbare broncode te converteren naar machinaal leesbare machinecode. Een programma doorloopt verschillende stappen om naar machinecode te converteren. Dit hele proces wordt Taalverwerkingssysteem genoemd. Een daarvan is de compilatie. De syntaxisanalysator of de parser bevindt zich in de compiler en voert de ontleedtaak uit.

INHOUD

1. Overzicht en belangrijkste verschil
2. Wat is Top Down Parsing
3. Wat is Bottom Up Parsing
4. Side-by-side vergelijking - Top-down versus Bottom-up parseren in tabelvorm
5. Samenvatting

Wat is Top Down Parsing?

Elke programmeertaal heeft een aantal regels om de taal weer te geven. De syntaxisanalysator of de ontledingsprocedure neemt de invoerreeks en controleert of deze overeenkomt met de grammaticaproducties. Met andere woorden, de grammatica zou die string moeten produceren met behulp van een parse tree.

Bij parseren van boven naar beneden gebeurt de parsering vanuit het startsymbool en bereikt de gegeven invoerreeks. Overweeg de volgende grammaticale productieregels. De invoerreeks (w) is cad.

S -> cAd

A -> ab / a

De ontleed-tree na het uitvoeren van top-down parsen is als volgt.

Figuur 01: Ontleed boom 1 met Top Down-parsering

S produceren c A d en A produceert een b. De string is cabd. Het is niet de vereiste reeks. Het is dus noodzakelijk om backtracking te doen, dat wil zeggen om de andere alternatieven te gebruiken.

Evenzo produceert S c A d. Het toepassen van de andere optie voor A geeft een. Nu geeft het de vereiste string. Daarom accepteert de parser deze invoerreeks. De ontleed-tree na het uitvoeren van top-down parsen is als volgt.

Figuur 02: Parse Tree 2 met Top Down Parsing

Wanneer de invoerreeks (w) abbcde is

Overweeg de volgende grammaticale productieregels.

S -> AABe

A -> Abc / b

B -> d

In top-down parsen,

S -> AABe (Vervang A -> Abc)

S -> aAbcBe (Vervang A -> b)

S -> abbcBe (vervanger B -> d)

S -> abbcde

Vervanging begint met de meest linkse variabele eerst en vervolgens naar de volgende juiste positie enzovoorts. Daarom volgt het een meest linkse afleidingsmethode. Verder is het belangrijk om te beslissen welke productieregel moet worden gekozen wanneer er een variabele is.

Wat is Bottom Up Parsing?

In de bottom-up gebeurt parseren op de andere manier. Het parseren gebeurt van de invoerreeks naar het startsymbool. Overweeg de volgende grammaticale productieregels en laat de invoerreeks w ɛ cad zijn

S -> cAd

A -> ab / a

De ontleedstructuur na het uitvoeren van bottom-up parsering is als volgt.

Figuur 03: Ontleed de boom met Bottom Up Parsing

De gegeven reeks is cad. De a wordt gegenereerd door A. De c, A en d worden gecombineerd om het startsymbool S te krijgen.

Wanneer de invoerreeks (w) abbcde is

Overweeg de volgende grammaticale productieregels.

S -> AABe

A -> Abc / b

B -> d

Bij het parseren van onder naar boven,

S -> AABe (Vervang B -> d)

S -> aAde (Vervang A -> Abc)

S -> aAbcde (Substitutie A -> b)

S -> abbcde

Vervanging begint met de meest rechtse variabele eerst en dan naar de volgende linkerpositie enzovoort. Daarom volgt het een linker mot afleidingsmethode.

Wat is het verschil tussen Top Down en Bottom Up Parsing?

Top-down parsen is een ontleedstrategie die eerst naar het hoogste niveau van de ontleedboom kijkt en de ontleedboom doorspant met behulp van de regels van een formele grammatica. Bottom-up parsing is een ontleedstrategie die eerst naar het laagste niveau van de ontleedboom kijkt en de ontleedboom ophaalt met behulp van de regels van een formele grammatica. Het parseren vindt plaats van het startsymbool naar de invoertekenreeks, van boven naar beneden. Aan de andere kant vindt parsing plaats van de invoerreeks naar het startsymbool, van onder naar boven.

Verder is de belangrijkste beslissing in top-down parsen om te selecteren welke productieregel moet worden gebruikt om de reeks te construeren, terwijl de hoofdbeslissing in de bottom-up-parsing is om te selecteren wanneer een productieregel moet worden gebruikt om de tekenreeks voor het startsymbool te verkleinen. Bovendien gebruikt top-down parsing links de meeste afleiding en gebruikt onder-beneden parsen de juiste afleiding.

Samenvatting - Top-down versus Bottom-up parseren

Het verschil tussen top-down en bottom-up parsing is dat van boven naar beneden ontleden de parsing uitvoert van het stersymbool naar de invoerreeks, terwijl bottom-down parsing de parsering uitvoert van de invoertekenreeks naar het startsymbool.

Referentie:

1. "Compilerontwerp Lecture 5 - Inleiding tot Parsers en LL (1) Parsing." Compilerontwerp Lecture 5 - Inleiding tot Parsers en LL (1) Parsing, Poortlezingen door Ravindrababu Ravula, 22 mei 2014. Beschikbaar Hier