Pushdown-Automaten & Parsing

Das Parsen wird verwendet, um eine Zeichenfolge unter Verwendung der Produktionsregeln einer Grammatik abzuleiten. Es wird verwendet, um die Akzeptanz einer Zeichenfolge zu überprüfen. Der Compiler wird verwendet, um zu überprüfen, ob eine Zeichenfolge syntaktisch korrekt ist oder nicht. Ein Parser nimmt die Eingaben entgegen und erstellt einen Analysebaum.

Es gibt zwei Arten von Parser:

Top-Down Parser - Die Analyse von oben nach unten beginnt von oben mit dem Startsymbol und leitet eine Zeichenfolge mithilfe eines Analysebaums ab.
Bottom-Up Parser - Die Analyse von unten nach oben beginnt von unten mit der Zeichenfolge und gelangt mithilfe eines Analysebaums zum Startsymbol.

Design des Top-Down-Parsers

Für die Analyse von oben nach unten verfügt ein PDA über die folgenden vier Arten von Übergängen:

Pop das Nicht-Terminal auf der linken Seite der Produktion oben auf dem Stapel und schieben Sie die rechte Schnur.
Wenn das obere Symbol des Stapels mit dem gelesenen Eingabesymbol übereinstimmt, platzieren Sie es.
Schieben Sie das Startsymbol 'S' in den Stapel.
Wenn die Eingabezeichenfolge vollständig gelesen und der Stapel leer ist, wechseln Sie in den Endzustand 'F'.

Beispiel

Entwerfen Sie einen Top-Down-Parser für den Ausdruck "x + y * z" für die Grammatik G mit den folgenden Produktionsregeln:

P: S → S + X | X, X → X * Y | Y, Y → (S) | Ich würde

Solution

Wenn der PDA (Q, ∑, S, δ, q ₀ , I, F) ist, dann ist die Top-Down-Analyse -

(x + y * z, I) ⊢ (x + y * z, SI) ⊢ (x + y * z, S + XI) ⊢ (x + y * z, X + XI)

X (x + y * z, Y + XI) ⊢ (x + y * z, x + XI) ⊢ (+ y * z, + XI) ⊢ (y * z, XI)

Y (y * z, X * YI) ⊢ (y * z, y * YI) Y (* z, * YI) ⊢ (z, YI) ⊢ (z, zI) ⊢ (ε, I)

Design eines Bottom-Up-Parsers

Für die Bottom-up-Analyse verfügt ein PDA über die folgenden vier Arten von Übergängen:

Schieben Sie das aktuelle Eingabesymbol in den Stapel.
Ersetzen Sie die rechte Seite einer Produktion oben im Stapel durch die linke Seite.
Wenn die Oberseite des Stapelelements mit dem aktuellen Eingabesymbol übereinstimmt, platzieren Sie es.
Wenn die Eingabezeichenfolge vollständig gelesen ist und das Startsymbol 'S' nur im Stapel verbleibt, legen Sie es ab und wechseln Sie in den Endzustand 'F'.