In diesem Artikel besprechen wir den Bottom-Up-Parser.
Bottom-Up-Parser / Shift-Reduce-Parser
Bauen den Parse-Baum von den Blättern bis zur Wurzel auf. Bottom-up-Parsing kann als ein Versuch definiert werden, die Eingabezeichenfolge w auf das Startsymbol der Grammatik zu reduzieren, indem die Ableitungen von w ganz rechts in umgekehrter Reihenfolge verfolgt werden.
Z.B.

Klassifikation von Bottom-up-Parsern

Ein allgemeines Shift-Reduce-Parsing ist das LR-Parsing. Das L steht für das Scannen der Eingabe von links nach rechts und das R steht für das Konstruieren einer Ableitung ganz rechts in umgekehrter Richtung.
Vorteile des LR-Parsings:

  1. Viele Programmiersprachen verwenden einige Variationen eines LR-Parsers. Es sollte beachtet werden, dass C++ und Perl davon ausgenommen sind.
  2. LR Parser lässt sich sehr effizient implementieren.
  3. Von allen Parsern, die ihre Symbole von links nach rechts scannen, erkennen LR-Parser syntaktische Fehler so schnell wie möglich.

Hier betrachten wir die Konstruktion des GOTO-Graphen der Grammatik unter Verwendung aller vier LR-Parsing-Techniken. Um Fragen in GATE zu lösen, müssen wir das GOTO direkt für die gegebene Grammatik konstruieren, um Zeit zu sparen.

LR(0) Parser
Wir brauchen zwei Funktionen –
Closure()
Goto()

Erweiterte Grammatik
Wenn G eine Grammatik mit Startsymbol S ist, dann ist G', die erweiterte Grammatik für G, die Grammatik mit neuem Startsymbol S' und einer Produktion S' -> S. Der Zweck dieser neuen Startproduktion ist es, anzuzeigen den Parser, wenn er das Parsen beenden und die Annahme der Eingabe ankündigen sollte.
Eine Grammatik sei S -> AA
A -> aA | b
Die erweiterte Grammatik für die obige Grammatik ist
S' -> S
S -> AA
A -> aA | B

LR(0) Items
Ein LR(0) ist das Item einer Grammatik G ist eine Produktion von G mit einem Punkt an irgendeiner Position auf der rechten Seite.
S -> ABC ergibt vier Elemente
S -> .ABC
S -> A.BC
S -> AB.C
S -> ABC.
Die Produktion A -> ε erzeugt nur ein Item A -> .ε

Closure-Operation :
Wenn I eine Menge von Items für eine Grammatik G ist, dann ist Closure(I) die Menge von Items, die durch die beiden Regeln aus I konstruiert wird:

  1. Zu Beginn wird jedes Element in I zum Abschluss (I) hinzugefügt.
  2. Wenn A -> α.Bβ in Abschluss (I) ist und B -> γ eine Produktion ist, dann füge das Element B -> .γ zu I hinzu, falls es noch nicht vorhanden ist. Wir wenden diese Regel an, bis keine Artikel mehr zum Abschluss (I) hinzugefügt werden können.

Beispiel:


Goto-Operation :
Goto(I, X) = 1. Fügen Sie I hinzu, indem Sie den Punkt nach X verschieben
                      . 2. Wenden Sie den Abschluss auf den ersten Schritt an.


Aufbau des GOTO-Graphen

  • Zustand I 0 – Abschluss des erweiterten LR(0)-Elements
  • Mit I 0 finden Sie mit Hilfe von DFA alle Sammlungen von Sätzen von LR(0)-Elementen
  • Konvertieren Sie DFA in eine LR(0)-Parsing-Tabelle

Aufbau der LR(0)-Parsing-Tabelle :

  • Die Aktionsfunktion nimmt als Argumente einen Zustand i und ein Terminal a (oder $, die Eingabe-Ende-Markierung). Der Wert von ACTION[i, a] kann eine von vier Formen haben:
    1. Verschiebe j, wobei j ein Zustand ist.
    2. Reduziere A -> β.
    3. Akzeptieren
    4. Fehler
  • Wir erweitern die auf Mengen von Elementen definierte GOTO-Funktion auf Zustände: Wenn GOTO[I i , A] = I j ist, dann bildet GOTO auch einen Zustand i und ein Nichtterminal A auf den Zustand j ab.

Bsp.:
Betrachten Sie die Grammatik S ->AA
A -> aA | b
Erweiterte Grammatik S' -> S
S -> AA
A -> aA | B

Die LR(0)-Parsing-Tabelle für das obige GOTO-Diagramm lautet –

Der Aktionsteil der Tabelle enthält alle Terminals der Grammatik, während der Goto-Teil alle Nichtterminals enthält. Für jeden Zustand des Goto-Graphen schreiben wir alle Goto-Operationen in die Tabelle. Wenn goto auf ein Terminal angewendet wird, wird es in den Aktionsteil geschrieben, wenn goto auf ein Nichtterminal angewendet wird, wird es in den goto-Teil geschrieben. Wenn beim Anwenden von goto eine Produktion reduziert wird (dh wenn der Punkt das Ende der Produktion erreicht und kein weiterer Abschluss angewendet werden kann), wird dies als R i bezeichnet, und wenn die Produktion nicht reduziert (verschoben) wird, wird sie als S i bezeichnet .
Wenn eine Produktion reduziert wird, wird dies unter den Terminals geschrieben, die durch Folgen der linken Seite der Produktion angegeben werden, die reduziert wird, zum Beispiel: in I 5 S->AA wird reduziert, also R 1wird unter den Terminals in follow(S)={$} geschrieben (um mehr darüber zu erfahren, wie die Follow-Funktion berechnet wird: Klicken Sie hier ) im LR(0)-Parser.
Wenn in einem Zustand das Startsymbol der Grammatik reduziert ist, wird es als akzeptiert unter das $-Symbol geschrieben.

HINWEIS: Wenn in irgendeinem Zustand sowohl reduzierte als auch verschobene Produktionen vorhanden sind oder zwei reduzierte Produktionen vorhanden sind, wird dies als Konfliktsituation bezeichnet und die Grammatik ist keine LR-Grammatik.

HINWEIS:
1. Zwei reduzierte Produktionen in einem Staat – RR-Konflikt.
2. Eine reduzierte und eine verlagerte Produktion in einem Staat – SR-Konflikt.

Wenn kein SR- oder RR-Konflikt in der Analysetabelle vorhanden ist, dann ist die Grammatik eine LR(0)-Grammatik.
In obiger Grammatik kein Konflikt, also LR(0)-Grammatik.

HINWEIS -Beim Lösen der GATE-Frage müssen wir keine Parsing-Tabelle erstellen, nur durch Betrachten des GOTO-Graphen können wir bestimmen, ob die Grammatik LR(0)-Grammatik ist oder nicht. Wir müssen nur nach Konflikten im Goto-Graph suchen, dh wenn ein Zustand zwei reduzierte oder einen reduzierten und einen Verschiebungseintrag für eine TERMINAL-Variable enthält, dann gibt es einen Konflikt und es ist keine LR(0)-Grammatik. (Im Falle einer Verschiebung mit einer VARIABLE und einer reduzierten gibt es keinen Konflikt, da dann die Verschiebungseinträge in den GOTO-Teil der Tabelle gehen und reduzierte Einträge in den ACTION-Teil und somit keine Mehrfacheinträge).


Dieser Artikel wurde von Parul Sharma beigesteuert .

Lernen Sie alle GATE CS-Konzepte mit kostenlosen Live-Kursen auf unserem YouTube-Kanal kennen.