Der Hauptunterschied zwischen Top-Down- und Bottom-Up-Parsing besteht darin, dass das Top-Down-Parsing das Parsing vom Startsymbol zum Eingabestring durchführt, während das Bottom-Down-Parsing das Parsing vom Eingabestring zum Startsymbol durchführt. Darüber hinaus besteht ein weiterer wichtiger Unterschied zwischen Top-Down- und Bottom-Up-Parsing darin, dass das Top-Down-Parsing die Ableitung ganz links und das Bottom-Down-Parsing die Ableitung ganz rechts verwendet.
Hochsprachen helfen beim Schreiben von Computerprogrammen. Sie sind für den Programmierer leichter zu verstehen, aber nicht für den Computer. Daher wird das High-Level-Programm in Maschinencode umgewandelt. Die Aufgabe des Compilers besteht darin, den menschenlesbaren Quellcode in maschinenlesbaren Maschinencode umzuwandeln. Ein Programm durchläuft mehrere Schritte, um es in Maschinencode umzuwandeln. Dieser gesamte Prozess wird Sprachverarbeitungssystem genannt. Einer davon ist die Zusammenstellung. Der Syntaxanalysator oder Parser befindet sich im Compiler und führt die Parsing-Aufgabe aus.
Was ist Top-Down-Parsing?
Jede Programmiersprache hat eine Reihe von Regeln, um die Sprache darzustellen. Der Syntaxanalysator oder der Parser nimmt den Eingabestring und prüft, ob er den Grammatikproduktionen entspricht. Mit anderen Worten, die Grammatik sollte diesen String mit einem Parse-Baum erzeugen.
Beim Top-Down-Parsing erfolgt das Parsing ab dem Startsymbol und erreicht die angegebene Eingabezeichenfolge. Betrachten Sie die folgenden Grammatikproduktionsregeln. Die Eingabezeichenfolge (w) ist cad.
S -> cAd
A -> ab /a
Der Parsing-Baum nach dem Top-Down-Parsing sieht wie folgt aus.
Abbildung 01: Parse-Baum 1 mit Top-Down-Parsing
S erzeugt c A d und A erzeugt ein b. Die Saite ist Cabd. Es ist nicht die erforderliche Zeichenfolge. Es ist also notwendig, ein Backtracking durchzuführen, d. h. die anderen Alternativen zu verwenden.
In ähnlicher Weise erzeugen S c A d. Die Anwendung der anderen Option für A ergibt a. Jetzt gibt es die erforderliche Zeichenfolge. Daher akzeptiert der Parser diese Eingabezeichenfolge. Der Parsing-Baum nach dem Ausführen des Top-Down-Parsings sieht wie folgt aus.
Abbildung 02: Parse-Baum 2 mit Top-Down-Parsing
Wenn die Eingabezeichenfolge (w) abbcde ist
Berücksichtigen Sie die folgenden Grammatikproduktionsregeln.
S -> aABe
A -> Abc/b
B -> d
Beim Top-Down-Parsing
S -> aABe (ersetzt A -> Abc)
S -> aAbcBe (ersetzt A -> b)
S -> abbcBe (ersetzt B ->d)
S -> abbcde
Die Substitution beginnt zuerst mit der am weitesten links stehenden Variable und dann bis zur nächsten rechten Position und so weiter. Daher folgt es einem am weitesten links liegenden Ableitungsverfahren. Außerdem ist es wichtig zu entscheiden, welche Produktionsregel gewählt werden soll, wenn es eine Variable gibt.
Was ist Bottom-Up-Parsing?
Beim Bottom-up-Parsing geschieht dies umgekehrt. Die Analyse erfolgt von der Eingabezeichenfolge bis zum Startsymbol. Betrachten Sie die folgenden Grammatikproduktionsregeln und lassen Sie die Eingabezeichenfolge w ɛ cad sein
S -> cAd
A -> ab /a
Der Parse-Baum nach der Bottom-Up-Analyse sieht wie folgt aus.
Abbildung 03: Parse-Baum mit Bottom-Up-Parsing
Die angegebene Zeichenfolge ist cad. Das a wird von A generiert. Die Kombinationen c, A und d ergeben das Startsymbol S.
Wenn die Eingabezeichenfolge (w) abbcde ist
Berücksichtigen Sie die folgenden Grammatikproduktionsregeln.
S -> aABe
A -> Abc/b
B -> d
Beim Bottom-up-Parsing
S -> aABe (ersetzt B ->d)
S -> aAde (ersetzt A -> Abc)
S -> aAbcde (ersetzt A -> b)
S -> abbcde
Die Substitution beginnt zuerst mit der am weitesten rechts liegenden Variable und bewegt sich dann zur nächsten linken Position und so weiter. Daher folgt es einer linken Mot-Ableitungsmethode.
Was ist der Unterschied zwischen Top-Down- und Bottom-Up-Parsing?
Top-down-Parsing ist eine Parsing-Strategie, die zuerst auf der höchsten Ebene des Parsing-Baums nach unten arbeitet, indem sie die Regeln einer formalen Grammatik verwendet. Bottom-Up-Parsing ist eine Parsing-Strategie, die zuerst auf die unterste Ebene des Parsing-Baums schaut und den Parsing-Baum nach oben arbeitet, indem sie die Regeln einer formalen Grammatik verwendet. Das Parsen erfolgt vom Startsymbol bis zur Eingabezeichenfolge beim Top-Down-Parsing. Beim Bottom-up-Parsing hingegen erfolgt die Analyse von der Eingabezeichenfolge bis zum Startsymbol.
Darüber hinaus besteht die Hauptentscheidung beim Top-Down-Parsing darin, auszuwählen, welche Produktionsregel verwendet werden soll, um den String zu erstellen, während die Hauptentscheidung beim Bottom-Down-Parsing darin besteht, auszuwählen, wann eine Produktionsregel verwendet werden soll, um den String zu reduzieren erh alten Sie das Startsymbol. Darüber hinaus verwendet das Top-Down-Parsing die Ableitung ganz links und das Bottom-Down-Parsing die Ableitung ganz rechts.
Zusammenfassung – Parsing von oben nach unten vs. von unten nach oben
Der Unterschied zwischen Top-Down- und Bottom-Up-Parsing besteht darin, dass Top-Down-Parsing das Parsing vom Startsymbol zum Eingabestring durchführt, während Bottom-Down-Parsing das Parsing vom Eingabestring zum Startsymbol durchführt.
