Het belangrijkste verschil tussen top-down en bottom-up-parsing is dat de top-down-parsing de parsering uitvoert van het starende symbool naar de invoertekenreeks, terwijl de bottom-down-parsing de ontleding uitvoert van de invoertekenreeks naar het startsymbool. Verder is een ander belangrijk verschil tussen top-down en bottom-up-parsing dat de top-down-parsing de meest linkse afleiding gebruikt en bottom-down-parsing de meest rechtse afleiding.
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 voor mensen leesbare broncode om te zetten in machineleesbare machinecode. Een programma doorloopt verschillende stappen om te converteren naar machinecode. Dit hele proces wordt Taalverwerkingssysteem genoemd. Een daarvan is de compilatie. De syntaxanalysator of de parser bevindt zich in de compiler en voert de parseertaak uit.
Wat is Top Down Parsing?
Elke programmeertaal heeft een set regels om de taal weer te geven. De syntaxanalysator of de parse neemt de invoerstring en controleert of deze in overeenstemming is met de grammaticale producties. Met andere woorden, de grammatica zou die string moeten produceren met behulp van een ontledingsboom.
Bij ontleden van bovenaf gebeurt het ontleden vanaf het startsymbool en zal het de gegeven invoerreeks bereiken. Overweeg de volgende regels voor grammaticaproductie. De invoerstring (w) is cad.
S -> cAd
A -> ab /a
De ontledingsboom na het uitvoeren van top-down ontleding is als volgt.
Figuur 01: Boom 1 ontleden met Top Down Parsing
S produceert c A d en A produceert a b. De snaar is cabd. Het is niet de vereiste string. Het is dus noodzakelijk om backtracking te doen, dat wil zeggen om de andere alternatieven te gebruiken.
Op dezelfde manier produceert S c A d. Het toepassen van de andere optie voor A geeft a. Nu geeft het de vereiste string. Daarom accepteert de parser deze invoerreeks. De ontledingsboom na het uitvoeren van top-down ontleding is als volgt.
Figuur 02: Tree 2 ontleden met Top Down Parsing
Als de invoertekenreeks (w) abcde is
Overweeg de volgende regels voor grammaticaproductie.
S -> aABe
A -> Abc/b
B -> d
In top-down ontleding, S -> aABe (vervangt A -> Abc)
S -> aAbcBe (vervanging van A -> b)
S -> abbcBe (vervangt B ->d)
S -> abcde
Vervanging begint met de meest linkse variabele eerst en dan naar de volgende rechtse positie enzovoort. Daarom volgt het een meest linkse afleidingsmethode. Verder is het belangrijk om te beslissen welke productieregel moet worden gekozen als er een variabele is.
Wat is bottom-up parsing?
In bottom-up gebeurt het ontleden op de andere manier. Het ontleden gebeurt vanaf de invoertekenreeks tot het startsymbool. Houd rekening met de volgende regels voor grammaticaproductie en laat de invoerreeks w ɛ cad zijn
S -> cAd
A -> ab /a
De ontledingsboom na het uitvoeren van bottom-up ontleding is als volgt.
Figuur 03: Boom ontleden met bottom-up parsing
De gegeven string is cad. De a wordt gegenereerd door A. De c, A en d vormen samen het startsymbool S.
Als de invoertekenreeks(w) abcde is
Overweeg de volgende regels voor grammaticaproductie.
S -> aABe
A -> Abc/b
B -> d
In bottom-up parsing, S -> aABe (vervangt B ->d)
S -> aAde (vervangt A -> Abc)
S -> aAbcde (vervanging van A -> b)
S -> abcde
Vervanging begint met de meest rechtse variabele eerst en gaat dan naar de volgende linkerpositie enzovoort. Daarom volgt het een linkse mot-afleidingsmethode.
Wat is het verschil tussen top-down en bottom-up parsing?
Top-down ontleden is een ontledingsstrategie die eerst naar het hoogste niveau van de ontledingsboom kijkt en de ontledingsboom doorwerkt met behulp van de regels van een formele grammatica. Bottom-up parsing is een parseerstrategie die eerst naar het laagste niveau van de parseerboom kijkt en de parseerboom opwerkt met behulp van de regels van een formele grammatica. De ontleding vindt plaats vanaf het startsymbool tot de invoertekenreeks, in top-down ontleding. Aan de andere kant vindt parsering plaats van de invoertekenreeks naar het startsymbool, in bottom-up parsing.
Bovendien is de belangrijkste beslissing bij het ontleden van bovenaf om te selecteren welke productieregel moet worden gebruikt om de tekenreeks te construeren, terwijl de belangrijkste beslissing bij het ontleden van beneden is om te selecteren wanneer een productieregel moet worden gebruikt om de tekenreeks te reduceren tot pak het startsymbool. Bovendien gebruikt top-down ontleding de meest linkse afleiding en bottom-down ontleding gebruikt de meest rechtse afleiding.
Samenvatting - Top-down versus bottom-up parsing
Het verschil tussen top-down en bottom-up-parsing is dat top-down-parsing de parsering uitvoert van het starende symbool naar de invoertekenreeks, terwijl bottom-down-parsing de parsering uitvoert van de invoertekenreeks naar het startsymbool.
