Übersetzerbau Entwurf - Arten von Parsing

Syntax-Analysatoren folgen Produktionsregeln mit Hilfe von kontextfreien Grammatik definiert. Die Art, wie die Produktionsvorschriften durchgeführt werden (Ableitung) teilt Parsen in zwei Typen: Top-down-Parsing und Bottom-up-Analyse.

Top-down Parsing

Wenn der Parser startet Bau der Parse-Baum aus dem Startsymbol und dann versucht, das Startsymbol auf den Eingang zu verwandeln, spricht man von Top-down-Parsen.

• rekursive Abstieg Parsen: Es ist eine verbreitete Form von Top-Down-Parsing. Es heißt rekursiv, wie es verwendet rekursive Prozeduren, um die Eingabe zu verarbeiten. Rekursiven Abstiegs Parsing leidet Backtracking.

• Backtracking: Es bedeutet, wenn eine Ableitung einer Produktion ausfällt, Neustart der Syntax analysator den Vorgang mit unterschiedlichen Regeln der gleichen Produktion. Diese Technik kann die Eingabezeichenfolge mehr als einmal zu verarbeiten, um die richtige Produktion zu bestimmen.

Bottom-up Parsing

Wie der Name vermuten lässt, beginnt Bottom-up-Analyse mit den Eingangssymbolen und versucht, den Parsing-Baum bis zu dem Startsymbol zu konstruieren..

Beispiel:

Die Eingabezeichenfolge : a + b * c

Die Produktion Regeln:

S → E
E → E + T
E → E * T
E → T
T → id

Lassen Sie uns beginnen bottom-up Parsen

a + b * c

Lesen Sie die Eingabe und überprüfen, ob einer Produktion übereinstimmt mit der Eingabe:

a + b * c
T + b * c
E + b * c
E + T * c
E * c
E * T
E
S