Klassifizierung von Top-Down-Parsern
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 –
- Mit Backtracking: Brute-Force-Technik
- 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 –
- 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
- Wenn keine Übereinstimmung auftritt, fahren Sie mit der zweiten Alternative fort und vergleichen Sie mit der angegebenen I/P-Zeichenfolge.
- Wenn die Übereinstimmung erneut nicht gefunden wird, fahren Sie mit der Alternative fort und so weiter.
- 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 –
- 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.
- LL(1)-Parsing wird aus der Grammatik konstruiert, die frei von Linksrekursion, gemeinsamem Präfix und Mehrdeutigkeit ist.
- Der LL(1)-Parser hängt von 1 Look-Ahead-Symbol ab, um die Produktion zum Erweitern des Analysebaums vorherzusagen.
- Dieser Parser ist nicht rekursiv.
Lernen Sie alle GATE CS-Konzepte mit kostenlosen Live-Kursen auf unserem YouTube-Kanal kennen.