Parsing wird in zwei Kategorien eingeteilt, dh Top-Down-Parsing und Bottom-Up-Parsing. Das Top-Down-Parsing basiert auf der Ableitung ganz links, während das Bottom-Up-Parsing von der umgekehrten Ableitung ganz rechts abhängig ist.

Der Prozess zum Erstellen des Analysebaums, der von der Wurzel bis zum Blatt reicht, ist Top-Down-Parsing.

  • Top-Down-Parser konstruieren aus der Grammatik, die frei von Mehrdeutigkeit und Linksrekursion ist.
  • Top-Down-Parser verwenden die Ableitung ganz links, um einen Analysebaum zu erstellen.
  • Es ermöglicht eine Grammatik, die frei von Linksfaktorisierung ist.

Klassifizierung von Top-Down-Parsing –

  1. Mit Backtracking: Brute-Force-Technik
  2. Ohne Backtracking: 1. Rekursives Abstiegs-Parsing
    2. Vorhersagendes Parsing oder nicht-rekursives Parsing oder LL(1)-Parsing oder Tabellentreiber-Parsing

Brute-Force-Technik oder Recursive Descent Parsing –

  1. Wann immer ein Nicht-Terminal das erste Mal ausgibt, dann gehen Sie mit der ersten Alternative und vergleichen Sie mit dem gegebenen I/P-String
  2. Wenn keine Übereinstimmung auftritt, fahren Sie mit der zweiten Alternative fort und vergleichen Sie mit der angegebenen I/P-Zeichenfolge.
  3. Wenn die Übereinstimmung erneut nicht gefunden wird, fahren Sie mit der Alternative fort und so weiter.
  4. Darüber hinaus wird die I/P-Zeichenkette erfolgreich geparst, wenn für mindestens eine Alternative eine Übereinstimmung auftritt.

LL(1) oder Tabellentreiber oder prädiktiver Parser –

  1. In LL1 steht das erste L für Left to Right und das zweite L steht für Left-most Derivation. 1 steht für die Anzahl der Look-Aheads-Token, die vom Parser beim Parsen eines Satzes verwendet werden.
  2. LL(1)-Parsing wird aus der Grammatik konstruiert, die frei von Linksrekursion, gemeinsamem Präfix und Mehrdeutigkeit ist.
  3. Der LL(1)-Parser hängt von 1 Look-Ahead-Symbol ab, um die Produktion zum Erweitern des Analysebaums vorherzusagen.
  4. Dieser Parser ist nicht rekursiv.

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