Unterschied zwischen Top Down- und Bottom Up-Analyse
Share
Das Hauptunterschied zwischen top down und bottom up parsing ist das von oben nach unten Das Parsing führt das Parsing vom Startsymbol zur Eingabezeichenfolge aus, während das Parsing von unten nach unten das Parsing von der Eingabezeichenfolge zum Startsymbol durchführt. Ein weiterer wichtiger Unterschied zwischen dem Top-Down- und dem Bottom-Up-Parsing besteht darin, dass das Top-Down-Parsing die linke Ableitung und die Bottom-Down-Analyse die rechte Ableitung verwendet.
Hochsprachen helfen beim Schreiben von Computerprogrammen. Sie sind für den Programmierer leichter zu verstehen, nicht jedoch für den Computer. Daher wird das übergeordnete Programm in Maschinencode konvertiert. Die Aufgabe des Compilers besteht darin, den vom Menschen lesbaren Quellcode in maschinenlesbaren Maschinencode umzuwandeln. Ein Programm durchläuft mehrere Schritte, um es in Maschinencode zu konvertieren. Dieser gesamte Vorgang wird Sprachverarbeitungssystem genannt. Eine davon ist die Zusammenstellung. Der Syntaxanalysator oder der Parser befindet sich im Compiler und führt die Parsing-Aufgabe aus.
INHALT
1. Übersicht und Schlüsseldifferenz
2. Was ist Top-Down-Analyse?
3. Was ist Bottom Up-Analyse?
4. Side-by-Side-Vergleich - Top-Down- und Bottom-Up-Analyse in tabellarischer Form
5. Zusammenfassung
Was ist Top-Down-Analyse??
Jede Programmiersprache hat eine Reihe von Regeln, um die Sprache darzustellen. Der Syntaxanalysator oder die Syntaxanalyse nimmt die Eingabezeichenfolge und prüft, ob sie den Grammatikproduktionen entspricht. Mit anderen Worten, die Grammatik sollte diese Zeichenfolge mithilfe eines Analysebaums erzeugen.
Beim Parsing von oben nach unten geschieht das Parsing vom Startsymbol und erreicht die angegebene Eingabezeichenfolge. Beachten Sie die folgenden Regeln zur Grammatikproduktion. Die Eingabezeichenfolge (w) lautet cad.
S -> cAd
A -> ab / a
Der Parser-Baum nach der Durchführung des Top-Down-Parsing sieht wie folgt aus.
Abbildung 01: Parse-Tree 1 mit Top-Down-Analyse
S produzieren c A d und A produziert a b. Die Saite ist cabd. Es ist nicht die erforderliche Zeichenfolge. Es ist also notwendig, eine Rückverfolgung durchzuführen, dh die anderen Alternativen zu verwenden.
In ähnlicher Weise erzeugt S c A d. Wenn Sie die andere Option für A anwenden, wird a angezeigt. Jetzt gibt es die erforderliche Zeichenfolge. Daher akzeptiert der Parser diese Eingabezeichenfolge. Der Parser-Baum nach der Durchführung des Top-Down-Parsing sieht wie folgt aus.
Abbildung 02: Parse Tree 2 mit Top Down-Analyse
Wenn die Eingabezeichenfolge (w) abbcde ist
Beachten Sie die folgenden Regeln zur Grammatikproduktion.
S -> aABe
A -> Abc / b
B -> d
Bei der Analyse von oben nach unten,
S -> aABe (Substitution von A -> Abc)
S -> aAbcBe (Ersetzen von A -> b)
S -> abbcBe (Ersetzen von B -> d)
S -> abbcde
Die Substitution beginnt mit der am weitesten links stehenden Variablen und dann an der nächsten rechten Position usw. Daher folgt die meist abgeleitete Ableitungsmethode. Außerdem ist es wichtig zu entscheiden, welche Produktionsregel gewählt wird, wenn eine Variable vorhanden ist.
Was ist Bottom Up-Analyse??
Beim Bottom-Up-Parsing geschieht dies auf die andere Weise. Die Analyse erfolgt von der Eingabezeichenfolge bis zum Startsymbol. Beachten Sie die folgenden Regeln zur Grammatikproduktion, und lassen Sie die Eingabezeichenfolge w ɛ cad sein
S -> cAd
A -> ab / a
Der Parser-Baum nach dem Bottom-Up-Parsing ist wie folgt.
Abbildung 03: Parse-Struktur mit Bottom-Up-Analyse
Die angegebene Zeichenfolge ist cad. Das a wird von A generiert. Das c, A und d werden kombiniert, um das Startsymbol S zu erhalten.
Wenn die Eingabezeichenfolge (w) abbcde ist
Beachten Sie die folgenden Regeln zur Grammatikproduktion.
S -> aABe
A -> Abc / b
B -> d
In Bottom-Up-Analyse,
S -> aABe (Substitution von B -> d)
S -> aAde (Ersetzung von A -> Abc)
S -> aAbcde (Substitution A -> b)
S -> abbcde
Die Ersetzung beginnt mit der am weitesten rechts stehenden Variablen und geht dann zur nächsten linken Position usw. Daher folgt eine Methode zur Ableitung der linken Motive.
Was ist der Unterschied zwischen Top Down und Bottom Up Parsing??
Das Top-Down-Parsing ist eine Parsing-Strategie, bei der zunächst die oberste Ebene des Parser-Baums betrachtet und der Parser-Baum nach den Regeln einer formalen Grammatik bearbeitet wird. Das Bottom-Up-Parsing ist eine Parsing-Strategie, die zuerst die unterste Ebene des Parser-Baums betrachtet und den Parser-Baum mithilfe der Regeln einer formalen Grammatik aufarbeitet. Die Analyse erfolgt vom Startsymbol bis zur Eingabezeichenfolge bei der Analyse von oben nach unten. Auf der anderen Seite erfolgt das Parsing von der Eingabezeichenfolge bis zum Startsymbol beim Bottom-Up-Parsing.
Darüber hinaus besteht die Hauptentscheidung beim Top-Down-Parsing darin, auszuwählen, welche Produktionsregel zum Erstellen der Zeichenfolge verwendet werden soll. Die Hauptentscheidung bei der Bottom-Down-Analyse besteht darin, festzulegen, wann eine Produktionsregel verwendet werden soll, um die Zeichenfolge zu reduzieren, um das Startsymbol zu erhalten. Darüber hinaus verwendet das Top-Down-Parsing die linke Ableitung und das Bottom-Down-Parsing die rechte Ableitung.
Zusammenfassung - Top Down vs Bottom Up Parsing
Der Unterschied zwischen dem Top-Down- und dem Bottom-Up-Parsing besteht darin, dass das Top-Down-Parsing das Parsing vom Startsymbol zur Eingabezeichenfolge ausführt, während das Parsing von unten nach unten das Parsing von der Eingabezeichenfolge zum Startsymbol durchführt.
Referenz:
1. "Compiler Design Lecture 5 - Einführung in Parser und LL (1) Parsing". Compiler Design Lecture 5 - Einführung in Parser und LL (1) Parsing, Gate Lectures von Ravindrababu Ravula, 22. Mai 2014. Hier verfügbar
