Syntaxanalyse: Top-Down- und Bottom-Up-Parsing-Typen des Compilers

Die Syntaxanalyse im Compiler-Design-Prozess folgt auf die Phase der lexikalischen Analyse. Sie wird auch als Parse-Baum oder Syntaxbaum bezeichnet. Der Parse-Baum wird mithilfe der vordefinierten Grammatik der Sprache entwickelt. Der Syntaxanalysator prüft auch, ob ein bestimmtes Programm die Regeln einer kontextfreien Grammatik erfüllt. Wenn dies der Fall ist, erstellt der Parser den Parse-Baum dieses Quellprogramms. Andernfalls werden Fehlermeldungen angezeigt.

Warum brauchen Sie den Syntaxanalysator?

• Überprüfen Sie, ob der Code grammatikalisch gültig ist
• Der syntaktische Analysator hilft Ihnen, Regeln auf den Code anzuwenden
• Hilft Ihnen sicherzustellen, dass jede öffnende Klammer eine entsprechende Schlusssaldo hat
• Jede Deklaration hat einen Typ und dieser Typ muss vorhanden sein

Wichtige Syntaxanalysator-Terminologie

Wichtige Terminologien, die im Syntaxanalyseprozess verwendet werden:

• Satz: Ein Satz ist eine Gruppe von Zeichen über einem Alphabet.

• Lexem: Ein Lexem ist die syntaktische Einheit der niedrigsten Ebene einer Sprache (z. B. total, start).

• Token: Ein Token ist nur eine Kategorie von Lexemen.

• Schlüsselwörter und reservierte Wörter – Es handelt sich um einen Bezeichner, der als fester Bestandteil der Syntax einer Anweisung verwendet wird. Es handelt sich um ein reserviertes Wort, das Sie nicht als Variablennamen oder Bezeichner verwenden können.

• Lärmwörter – Füllwörter sind optional und werden in eine Aussage eingefügt, um die Lesbarkeit des Satzes zu verbessern.

• Kommentare – Es ist ein sehr wichtiger Teil der Dokumentation. Es wird meistens durch /* */ oder//Leerzeichen (Leerzeichen) angezeigt.

• Begrenzer – Es handelt sich um ein syntaktisches Element, das den Anfang oder das Ende einer syntaktischen Einheit markiert. Wie eine Anweisung oder ein Ausdruck, „begin“…“end“ oder {}.

• Zeichensatz – ASCII, Unicode

• Identifiers – Es handelt sich um eine Längenbeschränkung, die dazu beiträgt, die Lesbarkeit des Satzes zu verringern.

• OperaTor-Symbole – + und – führt zwei grundlegende Rechenoperationen aus.
• Syntaktische Elemente der Sprache

Warum brauchen wir Parsing?

Bei einer Analyse wird außerdem überprüft, ob die Eingabezeichenfolge wohlgeformt ist. Wenn nicht, wird sie abgelehnt.

Im Folgenden sind wichtige Aufgaben aufgeführt, die der Parser beim Compilerentwurf ausführt:

• Hilft Ihnen, alle Arten von Syntaxfehlern zu erkennen
• Suchen Sie die Position, an der der Fehler aufgetreten ist
• Klare und genaue Beschreibung des Fehlers.
• Wiederherstellung nach einem Fehler, um fortzufahren und weitere Fehler im Code zu finden.
• Sollte die Kompilierung „richtiger“ Programme nicht beeinträchtigen.
• Der Parser muss ungültige Texte zurückweisen, indem er Syntaxfehler meldet

Parsing-Techniken

Parsing-Techniken werden in zwei verschiedene Gruppen unterteilt:

• Top-Down-Analyse,
• Bottom-Up-Analyse

Top-Down-Analyse

Beim Top-Down-Parsing beginnt der Aufbau des Parsebaums an der Wurzel und setzt sich dann in Richtung der Blätter fort.

Es gibt zwei Arten der Top-Down-Analyse:

1. Prädiktives Parsen:

Die prädiktive Analyse kann vorhersagen, welche Produktion zum Ersetzen der spezifischen Eingabezeichenfolge verwendet werden sollte. Der prädiktive Parser verwendet einen Look-Ahead-Punkt, der auf die nächsten Eingabesymbole zeigt. Backtracking ist bei dieser Parsing-Technik kein Problem. Es ist als LL(1)-Parser bekannt

2. Rekursives Abstiegs-Parsing:

Diese Parsing-Technik analysiert die Eingabe rekursiv, um einen Prase-Baum zu erstellen. Sie besteht aus mehreren kleinen Funktionen, eine für jedes Nichtterminal in der Grammatik.

Bottom-Up-Analyse

Beim Bottom-Up-Parsing im Compiler-Design beginnt die Konstruktion des Parse-Baums mit dem Blatt und arbeitet sich dann in Richtung seiner Wurzel vor. Es wird auch als Shift-Reduce-Parsing bezeichnet. Diese Art des Parsens im Compiler-Design wird mithilfe einiger Software-Tools.

Fehler – Wiederherstellungsmethoden

Häufige Fehler, die beim Parsen in der Systemsoftware auftreten

• Lexikalisch: Name eines falsch eingegebenen Bezeichners
• Syntaktisch: unausgeglichene Klammer oder ein fehlendes Semikolon
• Semantisch: inkompatible Wertzuweisung
• logisch: Endlosschleife und nicht erreichbarer Code

Ein Parser sollte in der Lage sein, alle im Programm gefundenen Fehler zu erkennen und zu melden. Wenn also ein Fehler auftritt, muss der Parser in der Lage sein, ihn zu verarbeiten und mit der Analyse der verbleibenden Eingabe fortzufahren. Ein Programm kann in verschiedenen Phasen des Kompilierungsprozesses folgende Fehlertypen aufweisen. Es gibt fünf gängige Fehlerbehebungsmethoden, die im Parser implementiert werden können.

Wiederherstellung im Anweisungsmodus

• Falls der Parser auf einen Fehler stößt, hilft er Ihnen, Korrekturmaßnahmen zu ergreifen. Dadurch können die restlichen Eingaben und Zustände im Voraus analysiert werden.
• Das Hinzufügen eines fehlenden Semikolons ist beispielsweise eine Wiederherstellungsmethode im Anweisungsmodus. Allerdings muss der Parse-Designer beim Vornehmen dieser Änderungen vorsichtig sein, da eine falsche Korrektur zu einer Endlosschleife führen kann.

Wiederherstellung im Panikmodus

• Falls der Parser auf einen Fehler stößt, ignoriert dieser Modus den Rest der Anweisung und verarbeitet keine Eingaben von fehlerhaften Eingaben bis hin zu Trennzeichen wie einem Semikolon. Dies ist eine einfache Methode zur Fehlerbehebung.
• Bei dieser Art von Wiederherstellungsmethode lehnt der Parser Eingabesymbole nacheinander ab, bis eine einzelne festgelegte Gruppe von Synchronisierungstoken gefunden wird. Die Synchronisierungstoken verwenden im Allgemeinen Trennzeichen wie oder.

Wiederherstellung auf Phrasenebene

• Der Compiler korrigiert das Programm, indem er Token einfügt oder löscht. Dadurch kann die Analyse an der Stelle fortgesetzt werden, an der sie sich befand. Es führt eine Korrektur für die verbleibende Eingabe durch. Es kann ein Präfix der verbleibenden Eingabe durch eine Zeichenfolge ersetzen, was dem Parser hilft, den Prozess fortzusetzen.

Fehlerproduktionen

• Die Wiederherstellung nach Fehlerproduktion erweitert die Grammatik für die Sprache, die die fehlerhaften Konstrukte generiert. Der Parser führt dann eine Fehlerdiagnose für dieses Konstrukt durch.

Globale Korrektur

• Der Compiler sollte bei der Verarbeitung einer falschen Eingabezeichenfolge so wenige Änderungen wie möglich vornehmen. Bei einer falschen Eingabezeichenfolge a und Grammatik c suchen Algorithmen nach einem Parse-Baum für eine verwandte Zeichenfolge b. Wie bei einigen Einfügungen, Löschungen und Änderungen an Token, die zum Umwandeln von a in b erforderlich sind, sind so wenig wie möglich erforderlich.

Grammatik

Eine Grammatik ist eine Reihe von Strukturregeln, die eine Sprache beschreiben. Grammatiken weisen jedem Satz eine Struktur zu. Dieser Begriff bezieht sich auch auf das Studium dieser Regeln, und diese Datei umfasst Morphologie, Phonologie und Syntax. Es ist in der Lage, viele der Syntax von zu beschreiben Programmiersprachen.

Regeln der Formengrammatik

• Das Nicht-Terminal-Symbol sollte links neben der mindestens einen Produktion erscheinen
• Das Zielsymbol sollte niemals rechts neben dem ::= einer Produktionsposition angezeigt werden.
• Eine Regel ist rekursiv, wenn LHS in ihrer RHS vorkommt

Notationskonventionen

Symbole der Notationskonventionen können durch Einschließen des Elements in eckige Klammern angegeben werden. Es handelt sich um eine beliebige Folge von Instanzen des Elements, die durch Einschließen des Elements in Klammern gefolgt von einem Sternsymbol, { … }*, angegeben werden kann.

Es handelt sich um eine Wahl der Alternative, die das Symbol innerhalb der Einzelregel verwenden darf. Bei Bedarf kann es in Klammern ([,]) eingeschlossen werden.

Es gibt zwei Arten von Notationskonventionen: Terminal und Nicht-Terminal

1. Terminals:

• Kleinbuchstaben im Alphabet wie a, b, c,
• OperaTorsymbole wie +,-, * usw.
• Satzzeichen wie Klammern, Raute, Komma
• 0, 1, …, 9 Ziffern
• Fettgedruckte Zeichenfolgen wie id oder if, alles, was ein einzelnes Terminalsymbol darstellt

2. Nichtterminals:

• Großbuchstaben wie A, B, C
• Kleingeschriebene kursive Namen: der Ausdruck oder einige

Kontextfreie Grammatik

Ein CFG ist eine linksrekursive Grammatik, die mindestens eine Produktion dieses Typs aufweist. Die Regeln in einer kontextfreien Grammatik sind hauptsächlich rekursiv. Ein Syntaxanalysator prüft, ob ein bestimmtes Programm alle Regeln der kontextfreien Grammatik erfüllt oder nicht. Wenn die Regeln erfüllt sind, können die Syntaxanalysatoren dieser Regeln einen Analysebaum für dieses Programm erstellen.

expression -> expression -+ term
expression -> expression – term 
expression-> term
term  -> term * factor
term -> expression/ factor
term  -> factor factor
factor ->  ( expression )
factor -> id

Grammatikableitung

Die Grammatikableitung ist eine Folge von Grammatikregeln, die das Startsymbol in eine Zeichenfolge umwandelt. Eine Ableitung beweist, dass die Zeichenfolge zur Sprache der Grammatik gehört.

Ableitung ganz links

Wenn die Satzform der Eingabe gescannt und in der Reihenfolge von links nach rechts ersetzt wird, spricht man von der Ableitung ganz links. Die Satzform, die durch die Ableitung ganz links abgeleitet wird, wird als Satzform links bezeichnet.

Ableitung ganz rechts

Ableitung ganz rechts scannen und die Eingabe durch Produktionsregeln ersetzen, von rechts nach links, Reihenfolge. Es ist als Ableitung ganz rechts bekannt. Die aus der Ableitung ganz rechts abgeleitete Satzform wird als Rechtssatzform bezeichnet.

Syntax vs. Lexikalischer Analysator

Syntaxanalysator	Lexikalischer Analysator
Der Syntaxanalysator befasst sich hauptsächlich mit rekursiven Konstrukten der Sprache.	Der lexikalische Analysator erleichtert die Aufgabe des Syntaxanalysators.
Der Syntaxanalysator arbeitet mit Tokens in einem Quellprogramm, um sinnvolle Strukturen in der Programmiersprache zu erkennen.	Der lexikalische Analysator erkennt das Token in einem Quellprogramm.
Es empfängt Eingaben in Form von Token von lexikalischen Analysatoren.	Sie ist für die Gültigkeit eines von bereitgestellten Tokens verantwortlich Der Syntaxanalysator

Nachteile der Verwendung von Syntaxanalysatoren

• Es wird niemals festgestellt, ob ein Token gültig ist oder nicht
• Hilft Ihnen nicht dabei, zu bestimmen, ob eine an einem Token-Typ ausgeführte Operation gültig ist oder nicht.
• Sie können nicht entscheiden, dass das Token deklariert und initialisiert wird, bevor es verwendet wird

Zusammenfassung

• Die Syntaxanalyse ist eine zweite Phase des Compiler-Entwurfsprozesses, die nach der lexikalischen Analyse folgt
• Der syntaktische Analysator hilft Ihnen, Regeln auf den Code anzuwenden
• Satz, Lexem, Token, Schlüsselwörter und reservierte Wörter, Füllwörter, Kommentare, Trennzeichen, Zeichensatz, Bezeichner sind einige wichtige Begriffe, die in der Syntaxanalyse bei der Compiler-Konstruktion verwendet werden
• Parse prüft, ob die Eingabezeichenfolge wohlgeformt ist, und lehnt sie andernfalls ab
• Parsing-Techniken werden in zwei verschiedene Gruppen unterteilt: Top-Down-Parsing und Bottom-Up-Parsing
• Lexikalische, syntaktische, semantische und logische Fehler sind einige häufige Fehler, die bei der Analysemethode auftreten
• Eine Grammatik ist eine Reihe von Strukturregeln, die eine Sprache beschreiben
• Notationskonventionen Das Symbol kann durch Einschließen des Elements in eckige Klammern angegeben werden
• Ein CFG ist eine linksrekursive Grammatik, die mindestens eine Produktion dieses Typs aufweist
• Die Grammatikableitung ist eine Folge von Grammatikregeln, die das Startsymbol in eine Zeichenfolge umwandelt
• Der Syntaxanalysator befasst sich hauptsächlich mit rekursiven Konstrukten der Sprache, während der lexikalische Analysator die Aufgabe des Syntaxanalysators erleichtert DBMS
• Der Nachteil der Syntaxanalysemethode besteht darin, dass sie niemals feststellen kann, ob ein Token gültig ist oder nicht