Compiler Design - Kurzanleitung

Computer sind eine ausgewogene Mischung aus Software und Hardware. Hardware ist nur ein mechanisches Gerät und seine Funktionen werden von einer kompatiblen Software gesteuert. Hardware versteht Anweisungen in Form von elektronischer Ladung, die das Gegenstück zur Binärsprache in der Softwareprogrammierung ist. Die Binärsprache hat nur zwei Alphabete, 0 und 1. Zum Anweisen müssen die Hardware-Codes im Binärformat geschrieben werden, das einfach eine Reihe von Einsen und Nullen ist. Es wäre eine schwierige und umständliche Aufgabe für Computerprogrammierer, solche Codes zu schreiben, weshalb wir Compiler haben, um solche Codes zu schreiben.

Sprachverarbeitungssystem

Wir haben gelernt, dass jedes Computersystem aus Hardware und Software besteht. Die Hardware versteht eine Sprache, die Menschen nicht verstehen können. Deshalb schreiben wir Programme in einer Hochsprache, die für uns leichter zu verstehen und zu merken ist. Diese Programme werden dann in eine Reihe von Tools und Betriebssystemkomponenten eingespeist, um den gewünschten Code zu erhalten, der von der Maschine verwendet werden kann. Dies ist als Sprachverarbeitungssystem bekannt.

Die Hochsprache wird in verschiedenen Phasen in eine Binärsprache umgewandelt. EINcompilerist ein Programm, das Hochsprache in Assemblersprache konvertiert. Ebenso einassembler ist ein Programm, das die Assemblersprache in eine Sprache auf Maschinenebene konvertiert.

Lassen Sie uns zunächst verstehen, wie ein Programm mit dem C-Compiler auf einem Host-Computer ausgeführt wird.

  • Der Benutzer schreibt ein Programm in der Sprache C (Hochsprache).

  • Der C-Compiler kompiliert das Programm und übersetzt es in ein Assembler-Programm (Low-Level-Sprache).

  • Ein Assembler übersetzt dann das Assemblerprogramm in Maschinencode (Objekt).

  • Ein Linker-Tool wird verwendet, um alle Teile des Programms zur Ausführung miteinander zu verknüpfen (ausführbarer Maschinencode).

  • Ein Loader lädt alle in den Speicher und dann wird das Programm ausgeführt.

Bevor wir uns direkt mit den Konzepten von Compilern befassen, sollten wir einige andere Tools verstehen, die eng mit Compilern zusammenarbeiten.

Präprozessor

Ein Präprozessor, der im Allgemeinen als Teil des Compilers betrachtet wird, ist ein Tool, das Eingaben für Compiler erzeugt. Es befasst sich mit Makroverarbeitung, Erweiterung, Dateieinbeziehung, Spracherweiterung usw.

Dolmetscher

Ein Interpreter übersetzt wie ein Compiler eine Hochsprache in eine Maschinensprache auf niedriger Ebene. Der Unterschied liegt in der Art und Weise, wie sie den Quellcode oder die Eingabe lesen. Ein Compiler liest den gesamten Quellcode auf einmal, erstellt Token, überprüft die Semantik, generiert Zwischencode, führt das gesamte Programm aus und kann viele Durchgänge umfassen. Im Gegensatz dazu liest ein Interpreter eine Anweisung aus der Eingabe, konvertiert sie in einen Zwischencode, führt sie aus und nimmt dann die nächste Anweisung nacheinander auf. Wenn ein Fehler auftritt, stoppt ein Interpreter die Ausführung und meldet ihn. Ein Compiler liest das gesamte Programm, auch wenn mehrere Fehler auftreten.

Assembler

Ein Assembler übersetzt Assembler-Programme in Maschinencode. Die Ausgabe eines Assemblers wird als Objektdatei bezeichnet, die eine Kombination von Maschinenanweisungen sowie die Daten enthält, die zum Speichern dieser Anweisungen im Speicher erforderlich sind.

Linker

Linker ist ein Computerprogramm, das verschiedene Objektdateien verknüpft und zusammenführt, um eine ausführbare Datei zu erstellen. Alle diese Dateien wurden möglicherweise von separaten Assemblern kompiliert. Die Hauptaufgabe eines Linkers besteht darin, referenzierte Module / Routinen in einem Programm zu suchen und zu lokalisieren und den Speicherort zu bestimmen, an dem diese Codes geladen werden, so dass die Programmanweisung absolute Referenzen enthält.

Lader

Loader ist Teil des Betriebssystems und dafür verantwortlich, ausführbare Dateien in den Speicher zu laden und auszuführen. Es berechnet die Größe eines Programms (Anweisungen und Daten) und schafft Speicherplatz dafür. Es initialisiert verschiedene Register, um die Ausführung zu initiieren.

Cross-Compiler

Ein Compiler, der auf Plattform (A) ausgeführt wird und ausführbaren Code für Plattform (B) generieren kann, wird als Cross-Compiler bezeichnet.

Source-to-Source-Compiler

Ein Compiler, der den Quellcode einer Programmiersprache in den Quellcode einer anderen Programmiersprache übersetzt, wird als Source-to-Source-Compiler bezeichnet.

Compiler-Architektur

Ein Compiler kann je nach Art der Kompilierung grob in zwei Phasen unterteilt werden.

Analysephase

Bekannt als das Front-End des Compilers, der analysis Die Phase des Compilers liest das Quellprogramm, unterteilt es in Kernteile und prüft dann auf lexikalische, Grammatik- und Syntaxfehler. Die Analysephase generiert eine Zwischendarstellung des Quellprogramms und der Symboltabelle, die der Synthesis-Phase als Eingabe zugeführt werden soll .

Synthesephase

Bekannt als das Back-End des Compilers, der synthesis phase generiert das Zielprogramm mit Hilfe der Zwischenquellcodedarstellung und der Symboltabelle.

Ein Compiler kann viele Phasen und Durchläufe haben.

  • Pass : Ein Pass bezieht sich auf das Durchlaufen eines Compilers durch das gesamte Programm.

  • Phase: Eine Phase eines Compilers ist eine unterscheidbare Stufe, die Eingaben aus der vorherigen Stufe verwendet, Ausgaben verarbeitet und liefert, die als Eingabe für die nächste Stufe verwendet werden können. Ein Pass kann mehr als eine Phase haben.

Phasen des Compilers

Der Kompilierungsprozess ist eine Folge verschiedener Phasen. Jede Phase nimmt Eingaben von ihrer vorherigen Stufe entgegen, hat eine eigene Darstellung des Quellprogramms und leitet ihre Ausgabe an die nächste Phase des Compilers weiter. Lassen Sie uns die Phasen eines Compilers verstehen.

Lexikalische Analyse

Die erste Phase des Scanners arbeitet als Textscanner. In dieser Phase wird der Quellcode als Zeichenstrom gescannt und in aussagekräftige Lexeme konvertiert. Der lexikalische Analysator repräsentiert diese Lexeme in Form von Token als:

<token-name, attribute-value>

Syntaxanalyse

Die nächste Phase heißt Syntaxanalyse oder parsing. Es verwendet das durch lexikalische Analyse erzeugte Token als Eingabe und generiert einen Analysebaum (oder Syntaxbaum). In dieser Phase werden Token-Anordnungen anhand der Quellcode-Grammatik überprüft, dh der Parser prüft, ob der von den Token erzeugte Ausdruck syntaktisch korrekt ist.

Semantische Analyse

Die semantische Analyse prüft, ob der erstellte Analysebaum den Sprachregeln entspricht. Die Zuweisung von Werten erfolgt beispielsweise zwischen kompatiblen Datentypen und das Hinzufügen einer Zeichenfolge zu einer Ganzzahl. Außerdem verfolgt der semantische Analysator die Bezeichner, ihre Typen und Ausdrücke. ob Bezeichner vor der Verwendung deklariert werden oder nicht usw. Der semantische Analysator erzeugt einen mit Anmerkungen versehenen Syntaxbaum als Ausgabe.

Zwischencode-Generierung

Nach der semantischen Analyse generiert der Compiler einen Zwischencode des Quellcodes für den Zielcomputer. Es repräsentiert ein Programm für eine abstrakte Maschine. Es liegt zwischen der Hochsprache und der Maschinensprache. Dieser Zwischencode sollte so generiert werden, dass er leichter in den Zielmaschinencode übersetzt werden kann.

Code-Optimierung

In der nächsten Phase wird der Zwischencode Code optimiert. Die Optimierung kann als etwas angesehen werden, das unnötige Codezeilen entfernt und die Reihenfolge der Anweisungen anordnet, um die Programmausführung zu beschleunigen, ohne Ressourcen (CPU, Speicher) zu verschwenden.

Codegenerierung

In dieser Phase nimmt der Codegenerator die optimierte Darstellung des Zwischencodes und ordnet ihn der Zielmaschinensprache zu. Der Codegenerator übersetzt den Zwischencode in eine Folge von (allgemein) umsetzbarem Maschinencode. Die Reihenfolge der Anweisungen des Maschinencodes führt die Aufgabe wie der Zwischencode aus.

Symboltabelle

Es ist eine Datenstruktur, die in allen Phasen eines Compilers gepflegt wird. Hier werden alle Namen der Kennung sowie deren Typen gespeichert. Die Symboltabelle erleichtert es dem Compiler, den Bezeichnerdatensatz schnell zu durchsuchen und abzurufen. Die Symboltabelle wird auch für die Bereichsverwaltung verwendet.

Die lexikalische Analyse ist die erste Phase eines Compilers. Es übernimmt den geänderten Quellcode von Sprachpräprozessoren, die in Form von Sätzen geschrieben sind. Der lexikalische Analysator unterteilt diese Syntax in eine Reihe von Token, indem Leerzeichen oder Kommentare im Quellcode entfernt werden.

Wenn der lexikalische Analysator ein ungültiges Token findet, wird ein Fehler generiert. Der lexikalische Analysator arbeitet eng mit dem Syntaxanalysator zusammen. Es liest Zeichenströme aus dem Quellcode, sucht nach legalen Token und leitet die Daten bei Bedarf an den Syntaxanalysator weiter.

Token

Lexeme sollen eine Folge von Zeichen (alphanumerisch) in einem Token sein. Es gibt einige vordefinierte Regeln für jedes Lexem, das als gültiges Token identifiziert werden soll. Diese Regeln werden durch Grammatikregeln mittels eines Musters definiert. Ein Muster erklärt, was ein Token sein kann, und diese Muster werden durch reguläre Ausdrücke definiert.

In der Programmiersprache können Schlüsselwörter, Konstanten, Bezeichner, Zeichenfolgen, Zahlen, Operatoren und Interpunktionssymbole als Token betrachtet werden.

In der Sprache C beispielsweise die Variablendeklarationszeile

int value = 100;

enthält die Token:

int (keyword), value (identifier), = (operator), 100 (constant) and ; (symbol).

Spezifikationen der Token

Lassen Sie uns verstehen, wie die Sprachtheorie die folgenden Begriffe übernimmt:

Alphabete

Jede endliche Menge von Symbolen {0,1} ist eine Menge von binären Alphabeten {0,1,2,3,4,5,6,7,8,9, A, B, C, D, E, F} ist eine Reihe von hexadezimalen Alphabeten, {az, AZ} ist eine Reihe von englischsprachigen Alphabeten.

Saiten

Jede endliche Folge von Alphabeten wird als Zeichenfolge bezeichnet. Die Länge der Zeichenfolge ist die Gesamtzahl des Auftretens von Alphabeten, z. B. beträgt die Länge des Zeichenfolgen-Tutorialpunkts 14 und wird mit | tutorialspoint | bezeichnet = 14. Eine Zeichenfolge ohne Alphabete, dh eine Zeichenfolge mit der Länge Null, wird als leere Zeichenfolge bezeichnet und mit ε (epsilon) bezeichnet.

Spezielle Symbole

Eine typische Hochsprache enthält die folgenden Symbole: -

Arithmetische Symbole Addition (+), Subtraktion (-), Modulo (%), Multiplikation (*), Division (/)
Interpunktion Komma (,), Semikolon (;), Punkt (.), Pfeil (->)
Zuordnung =
Sonderauftrag + =, / =, * =, - =
Vergleich == ,! =, <, <=,>,> =
Präprozessor #
Standortbezeichner &
Logisch &, &&, |, || ,!
Schichtführer >>, >>>, <<, <<<

Sprache

Eine Sprache wird als endliche Menge von Zeichenfolgen über eine endliche Menge von Alphabeten betrachtet. Computersprachen werden als endliche Mengen betrachtet, und mathematisch festgelegte Operationen können an ihnen ausgeführt werden. Endliche Sprachen können mit regulären Ausdrücken beschrieben werden.

Reguläre Ausdrücke

Der lexikalische Analysator muss nur einen endlichen Satz gültiger Zeichenfolgen / Token / Lexeme scannen und identifizieren, die zur jeweiligen Sprache gehören. Es sucht nach dem Muster, das durch die Sprachregeln definiert ist.

Reguläre Ausdrücke können endliche Sprachen ausdrücken, indem sie ein Muster für endliche Zeichenfolgen definieren. Die durch reguläre Ausdrücke definierte Grammatik ist bekannt alsregular grammar. Die durch die reguläre Grammatik definierte Sprache ist bekannt alsregular language.

Regulärer Ausdruck ist eine wichtige Notation für die Angabe von Mustern. Jedes Muster entspricht einer Reihe von Zeichenfolgen, sodass reguläre Ausdrücke als Namen für eine Reihe von Zeichenfolgen dienen. Programmiersprachen-Token können durch reguläre Sprachen beschrieben werden. Die Angabe regulärer Ausdrücke ist ein Beispiel für eine rekursive Definition. Normale Sprachen sind leicht zu verstehen und effizient umzusetzen.

Es gibt eine Reihe von algebraischen Gesetzen, die von regulären Ausdrücken befolgt werden, mit denen reguläre Ausdrücke in äquivalente Formen gebracht werden können.

Operationen

Die verschiedenen Operationen für Sprachen sind:

  • Die Vereinigung der beiden Sprachen L und M ist geschrieben als

    LUM = {s | s ist in L oder s ist in M}

  • Die Verkettung von zwei Sprachen L und M wird als geschrieben

    LM = {st | s ist in L und t ist in M}

  • Der Kleene-Abschluss einer Sprache L ist geschrieben als

    L * = Null oder mehr Vorkommen der Sprache L.

Notationen

Wenn r und s reguläre Ausdrücke sind, die die Sprachen L (r) und L (s) bezeichnen, dann

  • Union : (r) | (s) ist ein regulärer Ausdruck, der L (r) UL (s) bezeichnet.

  • Concatenation : (r) (s) ist ein regulärer Ausdruck, der L (r) L (s) bezeichnet.

  • Kleene closure : (r) * ist ein regulärer Ausdruck für (L (r)) *

  • (r) ist ein regulärer Ausdruck, der L (r) bezeichnet.

Vorrang und Assoziativität

  • *, Verkettung (.) und | (Rohrzeichen) bleiben assoziativ
  • * hat die höchste Priorität
  • Die Verkettung (.) Hat die zweithöchste Priorität.
  • | (Rohrzeichen) hat die niedrigste Priorität von allen.

Darstellung gültiger Token einer Sprache im regulären Ausdruck

Wenn x ein regulärer Ausdruck ist, dann:

  • x * bedeutet null oder mehr Vorkommen von x.

    dh es kann {e, x, xx, xxx, xxxx,…} erzeugen

  • x + bedeutet ein oder mehrere Vorkommen von x.

    dh es kann {x, xx, xxx, xxxx…} oder xx * erzeugen

  • x? bedeutet höchstens ein Vorkommen von x

    dh es kann entweder {x} oder {e} erzeugen.

  • [az] sind alle Kleinbuchstaben der englischen Sprache.

    [AZ] sind alle Großbuchstaben der englischen Sprache.

    [0-9] sind alle natürlichen Ziffern, die in der Mathematik verwendet werden.

Darstellung des Auftretens von Symbolen mit regulären Ausdrücken

Buchstabe = [a - z] oder [A - Z]

Ziffer = 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 oder [0-9]

Vorzeichen = [+ | -]

Darstellung von Sprachtoken mit regulären Ausdrücken

Dezimal = (Vorzeichen) ? (Ziffer) +

Kennung = (Buchstabe) (Buchstabe | Ziffer) *

Das einzige Problem, das mit dem lexikalischen Analysator noch besteht, besteht darin, die Gültigkeit eines regulären Ausdrucks zu überprüfen, der zum Festlegen der Muster von Schlüsselwörtern einer Sprache verwendet wird. Eine akzeptierte Lösung besteht darin, endliche Automaten zur Verifizierung zu verwenden.

Endliche Automaten

Endliche Automaten sind eine Zustandsmaschine, die eine Reihe von Symbolen als Eingabe verwendet und ihren Zustand entsprechend ändert. Endliche Automaten sind ein Erkenner für reguläre Ausdrücke. Wenn eine Zeichenfolge mit regulären Ausdrücken in endliche Automaten eingespeist wird, ändert sie ihren Status für jedes Literal. Wenn die Eingabezeichenfolge erfolgreich verarbeitet wurde und die Automaten ihren Endzustand erreichen, wird sie akzeptiert, dh die gerade eingegebene Zeichenfolge wurde als gültiges Token der jeweiligen Sprache bezeichnet.

Das mathematische Modell endlicher Automaten besteht aus:

  • Endliche Menge von Zuständen (Q)
  • Endliche Menge von Eingabesymbolen (Σ)
  • Ein Startzustand (q0)
  • Menge der Endzustände (qf)
  • Übergangsfunktion (δ)

Die Übergangsfunktion (δ) bildet die endliche Menge des Zustands (Q) auf eine endliche Menge von Eingabesymbolen (Σ) ab, Q × Σ ➔ Q.

Endliche Automatenkonstruktion

Sei L (r) eine reguläre Sprache, die von einigen endlichen Automaten (FA) erkannt wird.

  • States: FA-Staaten werden durch Kreise dargestellt. Zustandsnamen werden in Kreise geschrieben.

  • Start state: Der Zustand, von dem aus die Automaten starten, wird als Startzustand bezeichnet. Im Startzustand zeigt ein Pfeil darauf.

  • Intermediate states: Alle Zwischenzustände haben mindestens zwei Pfeile; einer zeigt auf und ein anderer zeigt auf sie.

  • Final state: Wenn die Eingabezeichenfolge erfolgreich analysiert wurde, wird erwartet, dass sich die Automaten in diesem Zustand befinden. Der Endzustand wird durch Doppelkreise dargestellt. Es kann eine ungerade Anzahl von Pfeilen geben, die darauf zeigen, und eine gerade Anzahl von Pfeilen, die darauf zeigen. Die Anzahl der ungeraden Pfeile ist eins größer als gerade, dhodd = even+1.

  • Transition: Der Übergang von einem Zustand in einen anderen Zustand erfolgt, wenn ein gewünschtes Symbol in der Eingabe gefunden wird. Beim Übergang können Automaten entweder in den nächsten Status wechseln oder im selben Status bleiben. Die Bewegung von einem Zustand in einen anderen wird als gerichteter Pfeil angezeigt, wobei die Pfeile auf den Zielzustand zeigen. Wenn Automaten im selben Status bleiben, wird ein Pfeil gezeichnet, der von einem Status zu sich selbst zeigt.

Example: Wir nehmen an, dass FA einen beliebigen dreistelligen Binärwert akzeptiert, der mit Ziffer 1 endet. FA = {Q (q 0 , q f ), Σ (0,1), q 0 , q f , δ}

Längste Spielregel

Wenn der lexikalische Analysator den Quellcode liest, scannt er den Code Buchstabe für Buchstabe. und wenn es auf ein Leerzeichen, ein Operatorsymbol oder spezielle Symbole stößt, entscheidet es, dass ein Wort vervollständigt ist.

For example:

int intvalue;

Beim Scannen beider Lexeme bis 'int' kann der lexikalische Analysator nicht feststellen, ob es sich um ein Schlüsselwort int oder die Initialen des Bezeichners int handelt.

Die Regel für die längste Übereinstimmung besagt, dass das gescannte Lexem basierend auf der längsten Übereinstimmung unter allen verfügbaren Token bestimmt werden sollte.

Der lexikalische Analysator folgt ebenfalls rule priorityDabei wird einem reservierten Wort, z. B. einem Schlüsselwort, einer Sprache Vorrang vor Benutzereingaben eingeräumt. Das heißt, wenn der lexikalische Analysator ein Lexem findet, das mit einem vorhandenen reservierten Wort übereinstimmt, sollte er einen Fehler erzeugen.

Syntaxanalyse oder Parsing ist die zweite Phase eines Compilers. In diesem Kapitel lernen wir die grundlegenden Konzepte kennen, die beim Aufbau eines Parsers verwendet werden.

Wir haben gesehen, dass ein lexikalischer Analysator Token mithilfe von regulären Ausdrücken und Musterregeln identifizieren kann. Ein lexikalischer Analysator kann jedoch die Syntax eines bestimmten Satzes aufgrund der Einschränkungen der regulären Ausdrücke nicht überprüfen. Reguläre Ausdrücke können Ausgleichstoken wie Klammern nicht überprüfen. Daher wird in dieser Phase die kontextfreie Grammatik (CFG) verwendet, die von Push-Down-Automaten erkannt wird.

CFG hingegen ist eine Obermenge der regulären Grammatik, wie unten dargestellt:

Dies impliziert, dass jede reguläre Grammatik auch kontextfrei ist, es gibt jedoch einige Probleme, die über den Rahmen der regulären Grammatik hinausgehen. CFG ist ein hilfreiches Werkzeug zur Beschreibung der Syntax von Programmiersprachen.

Kontextfreie Grammatik

In diesem Abschnitt werden wir zunächst die Definition der kontextfreien Grammatik sehen und Terminologien einführen, die in der Parsing-Technologie verwendet werden.

Eine kontextfreie Grammatik besteht aus vier Komponenten:

  • Eine Menge von non-terminals(V). Nicht-Terminals sind syntaktische Variablen, die Sätze von Zeichenfolgen bezeichnen. Die Nicht-Terminals definieren Sätze von Zeichenfolgen, mit deren Hilfe die von der Grammatik erzeugte Sprache definiert werden kann.

  • Eine Reihe von Token, bekannt als terminal symbols(Σ). Terminals sind die Grundsymbole, aus denen Zeichenfolgen gebildet werden.

  • Eine Menge von productions(P). Die Produktionen einer Grammatik geben an, wie die Terminals und Nicht-Terminals zu Strings kombiniert werden können. Jede Produktion besteht aus anon-terminal nannte die linke Seite der Produktion einen Pfeil und eine Folge von Token und / oder on- terminals, die rechte Seite der Produktion genannt.

  • Eines der Nicht-Terminals wird als Startsymbol (S) bezeichnet. von wo aus die Produktion beginnt.

Die Zeichenfolgen werden vom Startsymbol abgeleitet, indem wiederholt ein Nicht-Terminal (anfänglich das Startsymbol) durch die rechte Seite einer Produktion für dieses Nicht-Terminal ersetzt wird.

Beispiel

Wir nehmen das Problem der Palindromsprache an, das nicht durch regulären Ausdruck beschrieben werden kann. Das heißt, L = {w | w = w R } ist keine reguläre Sprache. Es kann jedoch mittels CFG beschrieben werden, wie unten dargestellt:

G = ( V, Σ, P, S )

Wo:

V = { Q, Z, N }
Σ = { 0, 1 }
P = { Q → Z | Q → N | Q → ℇ | Z → 0Q0 | N → 1Q1 }
S = { Q }

Diese Grammatik beschreibt die Palindromsprache wie: 1001, 11100111, 00100, 1010101, 11111 usw.

Syntaxanalysatoren

Ein Syntaxanalysator oder Parser nimmt die Eingabe von einem lexikalischen Analysator in Form von Token-Streams entgegen. Der Parser analysiert den Quellcode (Token-Stream) anhand der Produktionsregeln, um Fehler im Code zu erkennen. Der Ausgang dieser Phase ist aparse tree.

Auf diese Weise führt der Parser zwei Aufgaben aus, nämlich das Parsen des Codes, das Suchen nach Fehlern und das Generieren eines Analysebaums als Ausgabe der Phase.

Von Parsern wird erwartet, dass sie den gesamten Code analysieren, auch wenn im Programm einige Fehler vorliegen. Parser verwenden Strategien zur Fehlerbehebung, die wir später in diesem Kapitel lernen werden.

Ableitung

Eine Ableitung ist im Grunde eine Folge von Produktionsregeln, um die Eingabezeichenfolge zu erhalten. Während des Parsens treffen wir zwei Entscheidungen für eine sententiale Form der Eingabe:

  • Entscheiden, welches Nicht-Terminal ersetzt werden soll.
  • Festlegen der Produktionsregel, durch die das Nicht-Terminal ersetzt wird.

Um zu entscheiden, welches Nicht-Terminal durch eine Produktionsregel ersetzt werden soll, haben wir zwei Möglichkeiten.

Ableitung ganz links

Wenn die Sententialform einer Eingabe gescannt und von links nach rechts ersetzt wird, spricht man von einer Ableitung ganz links. Die durch die Ableitung ganz links abgeleitete Sententialform wird als Sententialform links bezeichnet.

Ableitung ganz rechts

Wenn wir die Eingabe von rechts nach links scannen und durch Produktionsregeln ersetzen, wird dies als Ableitung ganz rechts bezeichnet. Die aus der Ableitung ganz rechts abgeleitete Sententialform wird als Sententialform rechts bezeichnet.

Example

Produktionsregeln:

E → E + E
E → E * E
E → id

Eingabezeichenfolge: id + id * id

Die Ableitung ganz links lautet:

E → E * E
E → E + E * E
E → id + E * E
E → id + id * E
E → id + id * id

Beachten Sie, dass das Nicht-Terminal ganz links immer zuerst verarbeitet wird.

Die Ableitung ganz rechts lautet:

E → E + E
E → E + E * E
E → E + E * id
E → E + id * id
E → id + id * id

Baum analysieren

Ein Analysebaum ist eine grafische Darstellung einer Ableitung. Es ist praktisch zu sehen, wie Zeichenfolgen vom Startsymbol abgeleitet werden. Das Startsymbol der Ableitung wird zur Wurzel des Analysebaums. Lassen Sie uns dies anhand eines Beispiels aus dem letzten Thema sehen.

Wir nehmen die am weitesten links stehende Ableitung von a + b * c

Die Ableitung ganz links lautet:

E → E * E
E → E + E * E
E → id + E * E
E → id + id * E
E → id + id * id

Schritt 1:

E → E * E.

Schritt 2:

E → E + E * E.

Schritt 3:

E → id + E * E.

Schritt 4:

E → id + id * E.

Schritt 5:

E → ID + ID * ID

In einem Analysebaum:

  • Alle Blattknoten sind Terminals.
  • Alle inneren Knoten sind keine Terminals.
  • In-Order-Traversal ergibt die ursprüngliche Eingabezeichenfolge.

Ein Analysebaum zeigt die Assoziativität und Priorität von Operatoren. Der tiefste Unterbaum wird zuerst durchlaufen, daher hat der Operator in diesem Unterbaum Vorrang vor dem Operator, der sich in den übergeordneten Knoten befindet.

Arten der Analyse

Syntaxanalysatoren folgen Produktionsregeln, die mittels kontextfreier Grammatik definiert wurden. Die Art und Weise, wie die Produktionsregeln implementiert werden (Ableitung), unterteilt das Parsen in zwei Typen: Top-Down-Parsing und Bottom-Up-Parsing.

Top-Down-Analyse

Wenn der Parser beginnt, den Analysebaum aus dem Startsymbol zu erstellen, und dann versucht, das Startsymbol in die Eingabe umzuwandeln, wird dies als Top-Down-Analyse bezeichnet.

  • Recursive descent parsing: Es ist eine häufige Form der Top-Down-Analyse. Es wird als rekursiv bezeichnet, da es rekursive Prozeduren verwendet, um die Eingabe zu verarbeiten. Das Parsen rekursiver Abstammung leidet unter Backtracking.

  • Backtracking: Wenn eine Ableitung einer Produktion fehlschlägt, startet der Syntaxanalysator den Prozess unter Verwendung verschiedener Regeln derselben Produktion neu. Diese Technik kann die Eingabezeichenfolge mehr als einmal verarbeiten, um die richtige Produktion zu bestimmen.

Bottom-up-Analyse

Wie der Name schon sagt, beginnt die Analyse von unten nach oben mit den Eingabesymbolen und versucht, den Analysebaum bis zum Startsymbol zu erstellen.

Example:

Eingabezeichenfolge: a + b * c

Produktionsregeln:

S → E
E → E + T
E → E * T
E → T
T → id

Beginnen wir mit der Analyse von unten nach oben

a + b * c

Lesen Sie die Eingabe und prüfen Sie, ob eine Produktion mit der Eingabe übereinstimmt:

a + b * c
T + b * c
E + b * c
E + T * c
E * c
E * T
E
S

Mehrdeutigkeit

Eine Grammatik G gilt als mehrdeutig, wenn sie mehr als einen Analysebaum (linke oder rechte Ableitung) für mindestens eine Zeichenfolge hat.

Example

E → E + E
E → E – E
E → id

Für die Zeichenfolge id + id - id generiert die obige Grammatik zwei Analysebäume:

Die Sprache, die durch eine mehrdeutige Grammatik erzeugt wird, soll sein inherently ambiguous. Mehrdeutigkeit in der Grammatik ist für eine Compilerkonstruktion nicht gut. Keine Methode kann Mehrdeutigkeiten automatisch erkennen und entfernen, aber sie kann entfernt werden, indem entweder die gesamte Grammatik ohne Mehrdeutigkeit neu geschrieben wird oder indem Assoziativitäts- und Prioritätsbeschränkungen festgelegt und befolgt werden.

Assoziativität

Wenn ein Operand auf beiden Seiten Operatoren hat, wird die Seite, auf der der Operator diesen Operanden nimmt, durch die Assoziativität dieser Operatoren bestimmt. Wenn die Operation linksassoziativ ist, wird der Operand vom linken Operator übernommen, oder wenn die Operation rechtsassoziativ ist, übernimmt der rechte Operator den Operanden.

Example

Operationen wie Addition, Multiplikation, Subtraktion und Division bleiben assoziativ. Wenn der Ausdruck enthält:

id op id op id

Es wird bewertet als:

(id op id) op id

Zum Beispiel (id + id) + id

Operationen wie Exponentiation sind richtig assoziativ, dh die Reihenfolge der Bewertung im selben Ausdruck lautet:

id op (id op id)

Zum Beispiel id ^ (id ^ id)

Vorrang

Wenn zwei verschiedene Operatoren einen gemeinsamen Operanden gemeinsam haben, entscheidet die Priorität der Operatoren, welcher Operand verwendet wird. Das heißt, 2 + 3 * 4 kann zwei verschiedene Analysebäume haben, von denen einer (2 + 3) * 4 und einer 2+ (3 * 4) entspricht. Durch Festlegen der Priorität unter den Operatoren kann dieses Problem leicht behoben werden. Wie im vorherigen Beispiel hat mathematisch * (Multiplikation) Vorrang vor + (Addition), sodass der Ausdruck 2 + 3 * 4 immer wie folgt interpretiert wird:

2 + (3 * 4)

Diese Methoden verringern die Wahrscheinlichkeit von Mehrdeutigkeiten in einer Sprache oder ihrer Grammatik.

Linke Rekursion

Eine Grammatik wird linksrekursiv, wenn sie ein nicht-terminales 'A' hat, dessen Ableitung 'A' selbst als Symbol ganz links enthält. Linksrekursive Grammatik wird als problematische Situation für Top-Down-Parser angesehen. Top-Down-Parser beginnen mit dem Parsen über das Startsymbol, das an sich nicht terminal ist. Wenn der Parser in seiner Ableitung auf dasselbe Nicht-Terminal stößt, kann er nur schwer beurteilen, wann das Parsen des linken Nicht-Terminals beendet werden soll, und geht in eine Endlosschleife über.

Example:

(1) A => Aα | β

(2) S => Aα | β 
    A => Sd

(1) ist ein Beispiel für eine sofortige Rekursion nach links, wobei A ein beliebiges nicht-terminales Symbol ist und α eine Folge von nicht-terminalen Symbolen darstellt.

(2) ist ein Beispiel für eine indirekte Linksrekursion.

Ein Top-Down-Parser analysiert zuerst das A, was wiederum eine Zeichenfolge ergibt, die aus A selbst besteht, und der Parser kann für immer in eine Schleife geraten.

Entfernung der linken Rekursion

Eine Möglichkeit, die linke Rekursion zu entfernen, besteht in der folgenden Technik:

Die Produktion

A => Aα | β

wird in folgende Produktionen umgewandelt

A => βA’
A => αA’ | ε

Dies wirkt sich nicht auf die aus der Grammatik abgeleiteten Zeichenfolgen aus, entfernt jedoch die sofortige linke Rekursion.

Die zweite Methode besteht darin, den folgenden Algorithmus zu verwenden, der alle direkten und indirekten linken Rekursionen eliminieren soll.

Algorithm
START
Arrange non-terminals in some order like A1, A2, A3,…, An
for each i from 1 to n
{
for each j from 1 to i-1
   {
   replace each production of form Ai⟹Aj
   with Ai ⟹ δ1  | δ2 | δ3 |…|  
   where Aj ⟹ δ1 | δ2|…| δn  are current Aj productions
}
   }
   eliminate immediate left-recursion
END

Example

Das Produktionsset

S => Aα | β 
A => Sd

nach Anwendung des obigen Algorithmus sollte werden

S => Aα | β 
A => Aαd | βd

und entfernen Sie dann die sofortige linke Rekursion mit der ersten Technik.

A => βdA’
A => αdA’ | ε

Jetzt hat keine der Produktionen eine direkte oder indirekte Linksrekursion.

Linkes Factoring

Wenn mehr als eine Grammatikproduktionsregel eine gemeinsame Präfixzeichenfolge hat, kann der Top-Down-Parser keine Auswahl treffen, welche der Produktion zum Parsen der Zeichenfolge erforderlich ist.

Example

Wenn ein Top-Down-Parser auf eine Produktion wie stößt

A ⟹ αβ | α | …

Dann kann nicht bestimmt werden, welcher Produktion gefolgt werden soll, um den String zu analysieren, da beide Produktionen vom selben Terminal (oder Nicht-Terminal) aus starten. Um diese Verwirrung zu beseitigen, verwenden wir eine Technik namens Left Factoring.

Left Factoring transformiert die Grammatik, um sie für Top-Down-Parser nützlich zu machen. Bei dieser Technik machen wir eine Produktion für jedes gemeinsame Präfix und der Rest der Ableitung wird durch neue Produktionen hinzugefügt.

Example

Die obigen Produktionen können geschrieben werden als

A => αA’
A’=> β |  | …

Jetzt hat der Parser nur noch eine Produktion pro Präfix, was das Treffen von Entscheidungen erleichtert.

Erste und folgende Sätze

Ein wichtiger Teil der Parser-Tabellenkonstruktion besteht darin, erste und folgende Sätze zu erstellen. Diese Sätze können die tatsächliche Position jedes Terminals in der Ableitung liefern. Dies wird durchgeführt, um die Analysetabelle zu erstellen, in der die Entscheidung getroffen wird, T [A, t] = α durch eine Produktionsregel zu ersetzen.

Erstes Set

Dieser Satz wird erstellt, um zu wissen, welches Terminalsymbol an der ersten Position von einem Nicht-Terminal abgeleitet wird. Zum Beispiel,

α → t β

Das heißt, α leitet t (terminal) in der allerersten Position ab. Also ist t ∈ ZUERST (α).

Algorithmus zur Berechnung des ersten Satzes

Schauen Sie sich die Definition der ERSTEN (α) Menge an:

  • Wenn α ein Terminal ist, dann ist FIRST (α) = {α}.
  • Wenn α nicht terminal ist und α → ℇ eine Produktion ist, dann ist FIRST (α) = {ℇ}.
  • Wenn α nicht-terminal ist und α → 1 2 3… n und FIRST () t enthält, steht t in FIRST (α).

Der erste Satz kann gesehen werden als: FIRST (α) = {t | α → * t β} ∪ {ℇ | α → * ε}

Folgen Sie Set

Ebenso berechnen wir, welches Terminalsymbol in den Produktionsregeln unmittelbar auf ein Nicht-Terminal-α folgt. Wir überlegen nicht, was das Nicht-Terminal erzeugen kann, sondern sehen, welches das nächste Terminal-Symbol ist, das den Produktionen eines Nicht-Terminals folgt.

Algorithmus zur Berechnung Follow set:

  • Wenn α ein Startsymbol ist, ist FOLLOW () = $

  • Wenn α nicht terminal ist und eine Produktion α → AB hat, dann steht FIRST (B) in FOLLOW (A) mit Ausnahme von ℇ.

  • Wenn α nicht terminal ist und eine Produktion α → AB hat, wobei B ℇ ist, dann ist FOLLOW (A) in FOLLOW (α).

Der Folgesatz kann wie folgt gesehen werden: FOLLOW (α) = {t | S * αt *}

Strategien zur Fehlerbehebung

Ein Parser sollte in der Lage sein, Fehler im Programm zu erkennen und zu melden. Es wird erwartet, dass der Parser in der Lage sein sollte, einen Fehler zu behandeln und den Rest der Eingabe weiter zu analysieren. Meistens wird vom Parser erwartet, dass er nach Fehlern sucht, aber in verschiedenen Phasen des Kompilierungsprozesses können Fehler auftreten. Ein Programm kann in verschiedenen Phasen die folgenden Arten von Fehlern aufweisen:

  • Lexical : Name eines falsch eingegebenen Bezeichners

  • Syntactical : fehlendes Semikolon oder unausgeglichene Klammer

  • Semantical : Inkompatible Wertzuweisung

  • Logical : Code nicht erreichbar, Endlosschleife

Es gibt vier gängige Fehlerbehebungsstrategien, die im Parser implementiert werden können, um Fehler im Code zu beheben.

Panikmodus

Wenn ein Parser irgendwo in der Anweisung auf einen Fehler stößt, ignoriert er den Rest der Anweisung, indem er keine Eingaben von fehlerhaften Eingaben an Trennzeichen wie Semikolon verarbeitet. Dies ist der einfachste Weg zur Fehlerbehebung und verhindert außerdem, dass der Parser Endlosschleifen entwickelt.

Anweisungsmodus

Wenn ein Parser auf einen Fehler stößt, versucht er, Korrekturmaßnahmen zu ergreifen, damit der Parser mit den restlichen Eingaben der Anweisung weiter analysieren kann. Zum Beispiel das Einfügen eines fehlenden Semikolons, das Ersetzen des Kommas durch ein Semikolon usw. Parser-Designer müssen hier vorsichtig sein, da eine falsche Korrektur zu einer Endlosschleife führen kann.

Fehlerproduktionen

Den Compiler-Designern sind einige häufige Fehler bekannt, die im Code auftreten können. Darüber hinaus können die Designer eine erweiterte Grammatik erstellen, die als Produktionen verwendet werden kann, die fehlerhafte Konstrukte erzeugen, wenn diese Fehler auftreten.

Globale Korrektur

Der Parser betrachtet das vorliegende Programm als Ganzes und versucht herauszufinden, was das Programm tun soll, und versucht, eine möglichst genaue Übereinstimmung für das Programm zu finden. Wenn eine fehlerhafte Eingabe (Anweisung) X eingegeben wird, wird ein Analysebaum für eine engste fehlerfreie Anweisung Y erstellt. Dies kann es dem Parser ermöglichen, minimale Änderungen am Quellcode vorzunehmen, jedoch aufgrund der Komplexität (Zeit und Raum) von Diese Strategie wurde noch nicht in die Praxis umgesetzt.

Abstrakte Syntaxbäume

Parse-Tree-Darstellungen können vom Compiler nicht einfach analysiert werden, da sie mehr Details enthalten, als tatsächlich benötigt werden. Nehmen Sie als Beispiel den folgenden Analysebaum:

Bei genauer Betrachtung stellen wir fest, dass die meisten Blattknoten für ihre übergeordneten Knoten ein einzelnes Kind sind. Diese Informationen können entfernt werden, bevor sie in die nächste Phase eingespeist werden. Durch Ausblenden zusätzlicher Informationen können wir einen Baum erhalten, wie unten gezeigt:

Abstrakter Baum kann dargestellt werden als:

ASTs sind wichtige Datenstrukturen in einem Compiler mit den wenigsten unnötigen Informationen. ASTs sind kompakter als ein Analysebaum und können von einem Compiler problemlos verwendet werden.

Einschränkungen von Syntaxanalysatoren

Syntaxanalysatoren erhalten ihre Eingaben in Form von Token von lexikalischen Analysatoren. Lexikalische Analysatoren sind für die Gültigkeit eines vom Syntaxanalysator bereitgestellten Tokens verantwortlich. Syntaxanalysatoren weisen die folgenden Nachteile auf:

  • es kann nicht feststellen, ob ein Token gültig ist,
  • Es kann nicht festgestellt werden, ob ein Token deklariert ist, bevor es verwendet wird.
  • Es kann nicht festgestellt werden, ob ein Token initialisiert wurde, bevor es verwendet wird.
  • Es kann nicht festgestellt werden, ob eine für einen Tokentyp ausgeführte Operation gültig ist oder nicht.

Diese Aufgaben werden vom semantischen Analysator ausgeführt, den wir in der semantischen Analyse untersuchen werden.

Wir haben gelernt, wie ein Parser in der Phase der Syntaxanalyse Analysebäume erstellt. Der in dieser Phase erstellte einfache Analysebaum ist für einen Compiler im Allgemeinen nicht von Nutzen, da er keine Informationen zur Auswertung des Baums enthält. Die Produktionen der kontextfreien Grammatik, die die Regeln der Sprache festlegt, berücksichtigen nicht, wie sie interpretiert werden sollen.

Zum Beispiel

E → E + T

Der oben genannten CFG-Produktion ist keine semantische Regel zugeordnet, und sie kann nicht dazu beitragen, die Produktion zu verstehen.

Semantik

Die Semantik einer Sprache verleiht ihren Konstrukten wie Token und Syntaxstruktur eine Bedeutung. Die Semantik hilft bei der Interpretation von Symbolen, ihren Typen und ihren Beziehungen zueinander. Die semantische Analyse beurteilt, ob die im Quellprogramm erstellte Syntaxstruktur eine Bedeutung hat oder nicht.

CFG + semantic rules = Syntax Directed Definitions

Zum Beispiel:

int a = “value”;

sollte in der Phase der lexikalischen Analyse und der Syntaxanalyse keinen Fehler ausgeben, da er lexikalisch und strukturell korrekt ist, sollte jedoch einen semantischen Fehler erzeugen, da sich die Art der Zuweisung unterscheidet. Diese Regeln werden durch die Grammatik der Sprache festgelegt und in der semantischen Analyse ausgewertet. Die folgenden Aufgaben sollten in der semantischen Analyse ausgeführt werden:

  • Umfangsauflösung
  • Typprüfung
  • Array-gebundene Prüfung

Semantische Fehler

Wir haben einige der Semantikfehler erwähnt, die der semantische Analysator voraussichtlich erkennen wird:

  • Geben Sie Mismatch ein
  • Nicht deklarierte Variable
  • Missbrauch der reservierten Kennung.
  • Mehrfachdeklaration einer Variablen in einem Bereich.
  • Zugriff auf eine Variable außerhalb des Gültigkeitsbereichs.
  • Tatsächliche und formale Nichtübereinstimmung der Parameter.

Attribut Grammatik

Die Attributgrammatik ist eine spezielle Form der kontextfreien Grammatik, bei der einige zusätzliche Informationen (Attribute) an eines oder mehrere ihrer Nicht-Terminals angehängt werden, um kontextsensitive Informationen bereitzustellen. Jedes Attribut verfügt über einen genau definierten Wertebereich, z. B. Ganzzahl, Gleitkomma, Zeichen, Zeichenfolge und Ausdrücke.

Die Attributgrammatik ist ein Medium zur Bereitstellung von Semantik für die kontextfreie Grammatik und kann dabei helfen, die Syntax und Semantik einer Programmiersprache festzulegen. Die Attributgrammatik (wenn sie als Analysebaum betrachtet wird) kann Werte oder Informationen zwischen den Knoten eines Baums übergeben.

Example:

E → E + T { E.value = E.value + T.value }

Der rechte Teil der CFG enthält die semantischen Regeln, die festlegen, wie die Grammatik interpretiert werden soll. Hier werden die Werte der Nichtterminals E und T addiert und das Ergebnis auf das Nichtterminal E kopiert.

Semantische Attribute können ihren Werten aus ihrer Domäne zum Zeitpunkt des Parsens zugewiesen und zum Zeitpunkt der Zuweisung oder der Bedingungen ausgewertet werden. Basierend auf der Art und Weise, wie die Attribute ihre Werte erhalten, können sie grob in zwei Kategorien unterteilt werden: synthetisierte Attribute und geerbte Attribute.

Synthetisierte Attribute

Diese Attribute erhalten Werte aus den Attributwerten ihrer untergeordneten Knoten. Nehmen Sie zur Veranschaulichung die folgende Produktion an:

S → ABC

Wenn S Werte von seinen untergeordneten Knoten (A, B, C) nimmt, wird es als synthetisiertes Attribut bezeichnet, da die Werte von ABC zu S synthetisiert werden.

Wie in unserem vorherigen Beispiel (E → E + T) erhält der übergeordnete Knoten E seinen Wert von seinem untergeordneten Knoten. Synthetisierte Attribute nehmen niemals Werte von ihren übergeordneten Knoten oder Geschwisterknoten an.

Geerbte Attribute

Im Gegensatz zu synthetisierten Attributen können geerbte Attribute Werte von Eltern und / oder Geschwistern annehmen. Wie in der folgenden Produktion,

S → ABC

A kann Werte von S, B und C erhalten. B kann Werte von S, A und C annehmen. Ebenso kann C Werte von S, A und B annehmen.

Expansion : Wenn ein Nicht-Terminal gemäß einer grammatikalischen Regel zu Terminals erweitert wird

Reduction: Wenn ein Terminal gemäß den Grammatikregeln auf das entsprechende Nicht-Terminal reduziert wird. Syntaxbäume werden von oben nach unten und von links nach rechts analysiert. Bei jeder Reduktion wenden wir die entsprechenden semantischen Regeln (Aktionen) an.

Die semantische Analyse verwendet Syntax Directed Translations, um die oben genannten Aufgaben auszuführen.

Der semantische Analysator empfängt AST (Abstract Syntax Tree) aus seiner vorherigen Phase (Syntaxanalyse).

Der Semantic Analyzer fügt AST Attributinformationen hinzu, die als Attributed AST bezeichnet werden.

Attribute sind zwei Tupelwerte, <Attributname, Attributwert>

Zum Beispiel:

int value  = 5;
<type, “integer”>
<presentvalue, “5”>

Für jede Produktion fügen wir eine semantische Regel hinzu.

S-zugeschriebene SDT

Wenn ein SDT nur synthetisierte Attribute verwendet, wird es als S-zugeschriebenes SDT bezeichnet. Diese Attribute werden mithilfe von S-zugewiesenen SDTs ausgewertet, deren semantische Aktionen nach der Produktion geschrieben werden (rechte Seite).

Wie oben dargestellt, werden Attribute in S-zugeordneten SDTs beim Bottom-up-Parsing ausgewertet, da die Werte der übergeordneten Knoten von den Werten der untergeordneten Knoten abhängen.

L-zugeschriebenes SDT

Diese Form der SDT verwendet sowohl synthetisierte als auch geerbte Attribute mit der Einschränkung, keine Werte von rechten Geschwistern zu übernehmen.

In L-zugewiesenen SDTs kann ein Nicht-Terminal Werte von seinen übergeordneten, untergeordneten und Geschwisterknoten abrufen. Wie in der folgenden Produktion

S → ABC

S kann Werte von A, B und C annehmen (synthetisiert). A kann nur Werte von S annehmen. B kann Werte von S und A annehmen. C kann Werte von S, A und B erhalten. Kein Nicht-Terminal kann Werte von dem Geschwister rechts von ihm erhalten.

Attribute in SDTs mit L-Attribut werden durch Parsen in der Tiefe zuerst und von links nach rechts bewertet.

Wir können daraus schließen, dass eine Definition, die S-zugeordnet ist, auch L-zugeordnet ist, da die L-zugeschriebene Definition S-zugeschriebene Definitionen enthält.

Im vorherigen Kapitel haben wir die grundlegenden Konzepte des Parsens verstanden. In diesem Kapitel lernen wir die verschiedenen Arten der verfügbaren Parser-Konstruktionsmethoden kennen.

Das Parsen kann je nach Aufbau des Analysebaums als von oben nach unten oder von unten nach oben definiert werden.

Top-Down-Analyse

Wir haben im letzten Kapitel erfahren, dass die Top-Down-Parsing-Technik die Eingabe analysiert und mit dem Erstellen eines Analysebaums vom Wurzelknoten beginnt, der sich allmählich zu den Blattknoten bewegt. Die Arten der Top-Down-Analyse sind nachfolgend dargestellt:

Rekursive Abstiegsanalyse

Der rekursive Abstieg ist eine Top-Down-Analysetechnik, bei der der Analysebaum von oben erstellt und die Eingabe von links nach rechts gelesen wird. Es werden Prozeduren für jedes Terminal und jede Nicht-Terminal-Entität verwendet. Diese Analysetechnik analysiert die Eingabe rekursiv, um einen Analysebaum zu erstellen, für den möglicherweise eine Rückverfolgung erforderlich ist oder nicht. Die damit verbundene Grammatik (wenn sie nicht berücksichtigt wird) kann jedoch ein Zurückverfolgen nicht vermeiden. Eine Form der Analyse rekursiver Abstammung, für die keine Rückverfolgung erforderlich ist, wird als bezeichnetpredictive parsing.

Diese Analysetechnik wird als rekursiv angesehen, da sie eine kontextfreie Grammatik verwendet, die rekursiver Natur ist.

Rückverfolgung

Top-Down-Parser beginnen am Stammknoten (Startsymbol) und vergleichen die Eingabezeichenfolge mit den Produktionsregeln, um sie zu ersetzen (falls übereinstimmend). Um dies zu verstehen, nehmen Sie das folgende Beispiel für CFG:

S → rXd | rZd
X → oa | ea
Z → ai

Für eine Eingabezeichenfolge: read, ein Top-Down-Parser, verhält sich wie folgt:

Es beginnt mit S aus den Produktionsregeln und passt seine Ausbeute an den am weitesten links stehenden Buchstaben der Eingabe an, dh 'r'. Die Produktion von S (S → rXd) stimmt damit überein. Der Top-Down-Parser fährt also mit dem nächsten Eingabebuchstaben (dh 'e') fort. Der Parser versucht, das nicht-terminale 'X' zu erweitern und überprüft seine Produktion von links (X → oa). Es stimmt nicht mit dem nächsten Eingabesymbol überein. Der Top-Down-Parser zieht sich also zurück, um die nächste Produktionsregel von X (X → ea) zu erhalten.

Jetzt ordnet der Parser alle eingegebenen Buchstaben in geordneter Weise zu. Die Zeichenfolge wird akzeptiert.

Predictive Parser

Predictive Parser ist ein rekursiver Abstiegsparser, der vorhersagen kann, welche Produktion zum Ersetzen der Eingabezeichenfolge verwendet werden soll. Der Predictive Parser leidet nicht unter Backtracking.

Zur Erfüllung seiner Aufgaben verwendet der Predictive Parser einen Look-Ahead-Zeiger, der auf die nächsten Eingabesymbole zeigt. Um die Rückverfolgung des Parsers zu vereinfachen, legt der prädiktive Parser einige Einschränkungen für die Grammatik fest und akzeptiert nur eine Grammatikklasse, die als LL (k) -Grammatik bekannt ist.

Predictive Parsing verwendet einen Stapel und eine Parsing-Tabelle, um die Eingabe zu analysieren und einen Analysebaum zu generieren. Sowohl der Stapel als auch die Eingabe enthalten ein Endsymbol$um anzuzeigen, dass der Stapel leer ist und die Eingabe verbraucht wird. Der Parser bezieht sich auf die Analysetabelle, um eine Entscheidung über die Kombination aus Eingabe und Stapelelement zu treffen.

Bei der Analyse rekursiver Abstammung kann der Parser mehr als eine Produktion für eine einzelne Eingabeinstanz zur Auswahl haben, während beim prädiktiven Parser für jeden Schritt höchstens eine Produktion zur Auswahl steht. Es kann Fälle geben, in denen keine Produktion mit der Eingabezeichenfolge übereinstimmt, sodass die Analyseprozedur fehlschlägt.

LL Parser

Ein LL-Parser akzeptiert LL-Grammatik. Die LL-Grammatik ist eine Teilmenge der kontextfreien Grammatik, jedoch mit einigen Einschränkungen, um die vereinfachte Version zu erhalten und eine einfache Implementierung zu erreichen. Die LL-Grammatik kann mittels beider Algorithmen implementiert werden, nämlich rekursiv oder tabellengesteuert.

Der LL-Parser wird als LL (k) bezeichnet. Das erste L in LL (k) analysiert die Eingabe von links nach rechts, das zweite L in LL (k) steht für die Ableitung ganz links und k selbst repräsentiert die Anzahl der Vorausschau. Im Allgemeinen ist k = 1, daher kann LL (k) auch als LL (1) geschrieben werden.

LL-Parsing-Algorithmus

Wir können uns zur Erklärung des Parsers an das deterministische LL (1) halten, da die Größe der Tabelle exponentiell mit dem Wert von k wächst. Zweitens, wenn eine gegebene Grammatik nicht LL (1) ist, dann ist es normalerweise nicht LL (k) für ein gegebenes k.

Nachstehend ist ein Algorithmus zum Parsen von LL (1) angegeben:

Input: 
string ω 
parsing table M for grammar G
Output:
   If ω is in L(G) then left-most derivation of ω,
   error otherwise.

Initial State : $S on stack (with S being start symbol) ω$ in the input buffer

SET ip to point the first symbol of ω$.
repeat
let X be the top stack symbol and a the symbol pointed by ip.
if X∈ Vt or $
if X = a
   POP X and advance ip.
	else
   error()
 	endif
else	/* X is non-terminal */
   if M[X,a] = X → Y1, Y2,... Yk    
POP X
PUSH Yk, Yk-1,... Y1 /* Y1 on top */
   Output the production X → Y1, Y2,... Yk 
   else
   error()
   endif
	endif
until X = $	/* empty stack */

Eine Grammatik G ist LL (1), wenn A-> alpha | b sind zwei verschiedene Produktionen von G:

  • Für kein Terminal leiten sowohl Alpha als auch Beta Zeichenfolgen ab, die mit a beginnen.

  • höchstens Alpha und Beta können leere Zeichenfolgen ableiten.

  • Wenn beta => t, leitet alpha keine Zeichenfolge ab, die mit einem Terminal in FOLLOW (A) beginnt.

Bottom-up-Analyse

Das Bottom-up-Parsing beginnt an den Blattknoten eines Baums und funktioniert nach oben, bis es den Wurzelknoten erreicht. Hier beginnen wir mit einem Satz und wenden dann die Produktionsregeln in umgekehrter Weise an, um das Startsymbol zu erreichen. Das folgende Bild zeigt die verfügbaren Bottom-Up-Parser.

Parsing mit Umschalt-Reduzierung

Das Parsing mit Schichtreduzierung verwendet zwei einzigartige Schritte für das Bottom-Up-Parsing. Diese Schritte werden als Verschiebungsschritt und Reduzierungsschritt bezeichnet.

  • Shift step: Der Verschiebungsschritt bezieht sich auf das Vorrücken des Eingabezeigers zum nächsten Eingabesymbol, das als verschobenes Symbol bezeichnet wird. Dieses Symbol wird auf den Stapel geschoben. Das verschobene Symbol wird als einzelner Knoten des Analysebaums behandelt.

  • Reduce step: Wenn der Parser eine vollständige Grammatikregel (RHS) findet und durch (LHS) ersetzt, wird dies als Reduktionsschritt bezeichnet. Dies tritt auf, wenn die Oberseite des Stapels ein Handle enthält. Um dies zu reduzieren, wird eine POP-Funktion für den Stapel ausgeführt, die vom Handle abspringt und ihn durch das LHS-Symbol ohne Terminal ersetzt.

LR Parser

Der LR-Parser ist ein nicht rekursiver Bottom-Up-Parser mit reduzierter Verschiebung. Es verwendet eine breite Klasse kontextfreier Grammatik, was es zur effizientesten Syntaxanalysetechnik macht. LR-Parser sind auch als LR (k) -Parser bekannt, wobei L für das Scannen des Eingangsstroms von links nach rechts steht; R steht für die Konstruktion der Ableitung ganz rechts in umgekehrter Reihenfolge, und k bezeichnet die Anzahl der Lookahead-Symbole, um Entscheidungen zu treffen.

Für die Erstellung eines LR-Parsers stehen drei weit verbreitete Algorithmen zur Verfügung:

  • SLR (1) - Einfacher LR-Parser:
    • Funktioniert mit der kleinsten Grammatikklasse
    • Wenige Staaten, daher sehr kleine Tabelle
    • Einfache und schnelle Konstruktion
  • LR (1) - LR-Parser:
    • Arbeitet am kompletten Satz der LR (1) Grammatik
    • Erzeugt eine große Tabelle und eine große Anzahl von Zuständen
    • Langsame Konstruktion
  • LALR (1) - Look-Ahead LR-Parser:
    • Funktioniert mit mittlerer Grammatikgröße
    • Die Anzahl der Zustände ist dieselbe wie in SLR (1).

LR-Parsing-Algorithmus

Hier beschreiben wir einen Skelettalgorithmus eines LR-Parsers:

token = next_token()
repeat forever
   s = top of stack
   if action[s, token] = “shift si” then
   PUSH token
   PUSH si 
   token = next_token()
else if action[s, tpken] = “reduce A::= β“ then 
   POP 2 * |β| symbols
   s = top of stack
   PUSH A
	PUSH goto[s,A]
else if action[s, token] = “accept” then
	return
	else
   error()

LL gegen LR

LL LR
Führt eine Ableitung ganz links durch. Führt eine Ableitung ganz rechts in umgekehrter Reihenfolge durch.
Beginnt mit dem Root-Nonterminal auf dem Stapel. Endet mit dem Root-Nonterminal auf dem Stapel.
Endet, wenn der Stapel leer ist. Beginnt mit einem leeren Stapel.
Verwendet den Stapel, um festzulegen, was noch zu erwarten ist. Verwendet den Stapel, um zu kennzeichnen, was bereits gesehen wurde.
Erstellt den Analysebaum von oben nach unten. Erstellt den Analysebaum von unten nach oben.
Springt kontinuierlich ein Nichtterminal vom Stapel und drückt die entsprechende rechte Seite. Versucht, eine rechte Seite auf dem Stapel zu erkennen, öffnet sie und drückt auf das entsprechende Nichtterminal.
Erweitert die Nicht-Terminals. Reduziert die Nicht-Terminals.
Liest die Terminals, wenn sie vom Stapel genommen werden. Liest die Terminals, während sie auf den Stapel geschoben werden.
Durchlauf des Analysebaums vorbestellen. Nachbestellungsdurchquerung des Analysebaums.

Ein Programm als Quellcode ist lediglich eine Sammlung von Text (Code, Anweisungen usw.). Um es lebendig zu machen, müssen Aktionen auf dem Zielcomputer ausgeführt werden. Ein Programm benötigt Speicherressourcen, um Anweisungen auszuführen. Ein Programm enthält Namen für Prozeduren, Bezeichner usw., die zur Laufzeit dem tatsächlichen Speicherort zugeordnet werden müssen.

Mit Laufzeit meinen wir ein Programm in Ausführung. Die Laufzeitumgebung ist ein Status des Zielcomputers, der Softwarebibliotheken, Umgebungsvariablen usw. enthalten kann, um Dienste für die im System ausgeführten Prozesse bereitzustellen.

Das Runtime-Support-System ist ein Paket, das hauptsächlich mit dem ausführbaren Programm selbst generiert wird und die Prozesskommunikation zwischen dem Prozess und der Laufzeitumgebung erleichtert. Es kümmert sich um die Speicherzuweisung und -entzuweisung, während das Programm ausgeführt wird.

Aktivierungsbäume

Ein Programm ist eine Folge von Anweisungen, die zu einer Reihe von Prozeduren zusammengefasst sind. Anweisungen in einer Prozedur werden nacheinander ausgeführt. Eine Prozedur hat ein Start- und ein Endtrennzeichen, und alles, was sich darin befindet, wird als Hauptteil der Prozedur bezeichnet. Die Prozedurkennung und die Reihenfolge der darin enthaltenen endlichen Anweisungen bilden den Hauptteil der Prozedur.

Die Ausführung einer Prozedur wird als Aktivierung bezeichnet. Ein Aktivierungsdatensatz enthält alle erforderlichen Informationen, um eine Prozedur aufzurufen. Ein Aktivierungsdatensatz kann die folgenden Einheiten enthalten (abhängig von der verwendeten Ausgangssprache).

Temporäre Speichert temporäre und Zwischenwerte eines Ausdrucks.
Lokale Daten Speichert lokale Daten der aufgerufenen Prozedur.
Maschinenstatus Speichert den Maschinenstatus wie Register, Programmzähler usw., bevor die Prozedur aufgerufen wird.
Steuerverbindung Speichert die Adresse des Aktivierungsdatensatzes der Anruferprozedur.
Zugriffslink Speichert die Informationen von Daten, die außerhalb des lokalen Bereichs liegen.
Aktuelle Parameter Speichert tatsächliche Parameter, dh Parameter, die zum Senden von Eingaben an die aufgerufene Prozedur verwendet werden.
Rückgabewert Speichert Rückgabewerte.

Immer wenn eine Prozedur ausgeführt wird, wird ihr Aktivierungsdatensatz auf dem Stapel gespeichert, der auch als Steuerungsstapel bezeichnet wird. Wenn eine Prozedur eine andere Prozedur aufruft, wird die Ausführung des Aufrufers angehalten, bis die aufgerufene Prozedur die Ausführung beendet. Zu diesem Zeitpunkt wird der Aktivierungsdatensatz der aufgerufenen Prozedur auf dem Stapel gespeichert.

Wir gehen davon aus, dass die Programmsteuerung sequentiell abläuft und beim Aufruf einer Prozedur ihre Steuerung auf die aufgerufene Prozedur übertragen wird. Wenn eine aufgerufene Prozedur ausgeführt wird, gibt sie die Steuerung an den Aufrufer zurück. Diese Art des Kontrollflusses erleichtert die Darstellung einer Reihe von Aktivierungen in Form eines Baums, der alsactivation tree.

Um dieses Konzept zu verstehen, nehmen wir als Beispiel einen Code:

. . .
printf(“Enter Your Name: “);
scanf(“%s”, username);
show_data(username);
printf(“Press any key to continue…”);
. . .
int show_data(char *user)
   {
   printf(“Your name is %s”, username);
   return 0;
   }
. . .

Unten ist der Aktivierungsbaum des angegebenen Codes.

Jetzt verstehen wir, dass Prozeduren in der Tiefe zuerst ausgeführt werden, daher ist die Stapelzuweisung die am besten geeignete Speicherform für Prozeduraktivierungen.

Speicherzuordnung

Die Laufzeitumgebung verwaltet die Anforderungen an den Laufzeitspeicher für die folgenden Entitäten:

  • Code: Es ist als Textteil eines Programms bekannt, der sich zur Laufzeit nicht ändert. Der Speicherbedarf ist zur Kompilierungszeit bekannt.

  • Procedures: Ihr Textteil ist statisch, aber sie werden zufällig aufgerufen. Aus diesem Grund wird der Stapelspeicher zum Verwalten von Prozeduraufrufen und Aktivierungen verwendet.

  • Variables: Variablen sind nur zur Laufzeit bekannt, es sei denn, sie sind global oder konstant. Das Heap-Speicherzuweisungsschema wird zum Verwalten der Zuweisung und Aufhebung der Zuweisung von Speicher für Variablen zur Laufzeit verwendet.

Statische Zuordnung

In diesem Zuordnungsschema sind die Kompilierungsdaten an einen festen Ort im Speicher gebunden und ändern sich nicht, wenn das Programm ausgeführt wird. Da der Speicherbedarf und die Speicherorte im Voraus bekannt sind, ist kein Laufzeitunterstützungspaket für die Speicherzuweisung und -freigabe erforderlich.

Stapelzuordnung

Prozeduraufrufe und deren Aktivierung werden über die Stapelspeicherzuordnung verwaltet. Es funktioniert in der LIFO-Methode (Last-In-First-Out) und diese Zuordnungsstrategie ist sehr nützlich für rekursive Prozeduraufrufe.

Heap-Zuordnung

Lokale Variablen einer Prozedur werden nur zur Laufzeit zugewiesen und freigegeben. Die Heap-Zuweisung wird verwendet, um den Variablen dynamisch Speicher zuzuweisen und ihn zurückzufordern, wenn die Variablen nicht mehr benötigt werden.

Mit Ausnahme des statisch zugewiesenen Speicherbereichs können sowohl der Stapel- als auch der Heapspeicher dynamisch und unerwartet wachsen und schrumpfen. Daher können sie nicht mit einer festen Speichermenge im System versehen werden.

Wie in der obigen Abbildung gezeigt, wird dem Textteil des Codes eine feste Speichermenge zugewiesen. Stapel- und Heapspeicher sind an den Extremen des dem Programm zugewiesenen Gesamtspeichers angeordnet. Beide schrumpfen und wachsen gegeneinander.

Parameterübergabe

Das Kommunikationsmedium zwischen Prozeduren ist als Parameterübergabe bekannt. Die Werte der Variablen aus einer aufrufenden Prozedur werden durch einen Mechanismus in die aufgerufene Prozedur übertragen. Bevor Sie fortfahren, gehen Sie zunächst einige grundlegende Terminologien durch, die sich auf die Werte in einem Programm beziehen.

r-Wert

Der Wert eines Ausdrucks wird als r-Wert bezeichnet. Der in einer einzelnen Variablen enthaltene Wert wird auch zu einem r-Wert, wenn er auf der rechten Seite des Zuweisungsoperators angezeigt wird. r-Werte können immer einer anderen Variablen zugewiesen werden.

l-Wert

Der Speicherort (Adresse), an dem ein Ausdruck gespeichert ist, wird als l-Wert dieses Ausdrucks bezeichnet. Es wird immer auf der linken Seite eines Zuweisungsoperators angezeigt.

Zum Beispiel:

day = 1;
week = day * 7;
month = 1;
year = month * 12;

Aus diesem Beispiel verstehen wir, dass konstante Werte wie 1, 7, 12 und Variablen wie Tag, Woche, Monat und Jahr alle r-Werte haben. Nur Variablen haben l-Werte, da sie auch den ihnen zugewiesenen Speicherort darstellen.

Zum Beispiel:

7 = x + y;

ist ein l-Wert-Fehler, da die Konstante 7 keinen Speicherplatz darstellt.

Formale Parameter

Variablen, die die von der Aufruferprozedur übergebenen Informationen übernehmen, werden als formale Parameter bezeichnet. Diese Variablen werden in der Definition der aufgerufenen Funktion deklariert.

Aktuelle Parameter

Variablen, deren Werte oder Adressen an die aufgerufene Prozedur übergeben werden, werden als Aktualparameter bezeichnet. Diese Variablen werden im Funktionsaufruf als Argumente angegeben.

Example:

fun_one()
{
   int actual_parameter = 10;
   call fun_two(int actual_parameter);
}
   fun_two(int formal_parameter)
{
   print formal_parameter;
}

Formale Parameter enthalten die Informationen des tatsächlichen Parameters, abhängig von der verwendeten Parameterübergabetechnik. Es kann ein Wert oder eine Adresse sein.

Wert übergeben

Beim Pass-by-Value-Mechanismus übergibt die aufrufende Prozedur den r-Wert der tatsächlichen Parameter, und der Compiler fügt diesen in den Aktivierungsdatensatz der aufgerufenen Prozedur ein. Formale Parameter enthalten dann die Werte, die von der aufrufenden Prozedur übergeben wurden. Wenn die von den formalen Parametern gehaltenen Werte geändert werden, sollte dies keine Auswirkungen auf die tatsächlichen Parameter haben.

Referenz übergeben

Im Pass-by-Referenzmechanismus wird der l-Wert des Aktualparameters in den Aktivierungsdatensatz der aufgerufenen Prozedur kopiert. Auf diese Weise hat die aufgerufene Prozedur nun die Adresse (Speicherort) des tatsächlichen Parameters und der formale Parameter bezieht sich auf denselben Speicherort. Wenn daher der Wert, auf den der formale Parameter zeigt, geändert wird, sollte die Auswirkung auf den tatsächlichen Parameter gesehen werden, da sie auch auf denselben Wert zeigen sollten.

Pass by Copy-Restore

Dieser Parameterübergabemechanismus funktioniert ähnlich wie "Referenzübergabe", außer dass die Änderungen an den tatsächlichen Parametern vorgenommen werden, wenn die aufgerufene Prozedur endet. Beim Funktionsaufruf werden die Werte der Istparameter in den Aktivierungsdatensatz der aufgerufenen Prozedur kopiert. Wenn formale Parameter manipuliert werden, haben sie keine Echtzeitwirkung auf die tatsächlichen Parameter (wenn l-Werte übergeben werden), aber wenn die aufgerufene Prozedur endet, werden die l-Werte der formalen Parameter in die l-Werte der tatsächlichen Parameter kopiert.

Example:

int y; 
calling_procedure() 
{
   y = 10;     
   copy_restore(y); //l-value of y is passed
   printf y; //prints 99 
}
copy_restore(int x) 
{     
   x = 99; // y still has value 10 (unaffected)
   y = 0; // y is now 0 
}

Wenn diese Funktion endet, wird der l-Wert des formalen Parameters x in den tatsächlichen Parameter y kopiert. Selbst wenn der Wert von y vor dem Ende der Prozedur geändert wird, wird der l-Wert von x auf den l-Wert von y kopiert, sodass er sich wie ein Referenzaufruf verhält.

Mit Namen übergeben

Sprachen wie Algol bieten eine neue Art von Parameterübergabemechanismus, der wie ein Präprozessor in der C-Sprache funktioniert. Beim Pass-by-Name-Mechanismus wird der Name der aufgerufenen Prozedur durch ihren tatsächlichen Hauptteil ersetzt. Pass-by-Name ersetzt die Argumentausdrücke in einem Prozeduraufruf in Textform durch die entsprechenden Parameter im Hauptteil der Prozedur, sodass sie nun mit tatsächlichen Parametern arbeiten können, ähnlich wie bei der Referenzübergabe.

Die Symboltabelle ist eine wichtige Datenstruktur, die von Compilern erstellt und verwaltet wird, um Informationen über das Auftreten verschiedener Entitäten wie Variablennamen, Funktionsnamen, Objekte, Klassen, Schnittstellen usw. zu speichern. Die Symboltabelle wird sowohl von der Analyse als auch von der Synthese verwendet Teile eines Compilers.

Eine Symboltabelle kann abhängig von der jeweiligen Sprache folgenden Zwecken dienen:

  • Speichern der Namen aller Entitäten in strukturierter Form an einem Ort.

  • Um zu überprüfen, ob eine Variable deklariert wurde.

  • Um die Typprüfung zu implementieren, müssen Zuweisungen und Ausdrücke im Quellcode semantisch korrekt sein.

  • Bestimmen des Bereichs eines Namens (Bereichsauflösung).

Eine Symboltabelle ist einfach eine Tabelle, die entweder linear oder eine Hash-Tabelle sein kann. Es wird ein Eintrag für jeden Namen im folgenden Format verwaltet:

<symbol name,  type,  attribute>

Zum Beispiel, wenn eine Symboltabelle Informationen über die folgende Variablendeklaration speichern muss:

static int interest;

dann sollte es den Eintrag speichern wie:

<interest, int, static>

Die Attributklausel enthält die Einträge zum Namen.

Implementierung

Wenn ein Compiler eine kleine Datenmenge verarbeiten soll, kann die Symboltabelle als ungeordnete Liste implementiert werden, die leicht zu codieren ist, aber nur für kleine Tabellen geeignet ist. Eine Symboltabelle kann auf eine der folgenden Arten implementiert werden:

  • Lineare (sortierte oder unsortierte) Liste
  • Binärer Suchbaum
  • Hash-tabelle

Unter allen werden Symboltabellen meist als Hash-Tabellen implementiert, wobei das Quellcodesymbol selbst als Schlüssel für die Hash-Funktion behandelt wird und der Rückgabewert die Information über das Symbol ist.

Operationen

Eine Symboltabelle, entweder linear oder hash, sollte die folgenden Operationen bereitstellen.

einfügen()

Diese Operation wird häufiger in der Analysephase verwendet, dh in der ersten Hälfte des Compilers, in der Token identifiziert und Namen in der Tabelle gespeichert werden. Diese Operation wird verwendet, um der Symboltabelle Informationen zu eindeutigen Namen hinzuzufügen, die im Quellcode vorkommen. Das Format oder die Struktur, in der die Namen gespeichert sind, hängt vom jeweiligen Compiler ab.

Ein Attribut für ein Symbol im Quellcode ist die diesem Symbol zugeordnete Information. Diese Informationen enthalten den Wert, den Status, den Bereich und den Typ des Symbols. Die Funktion insert () verwendet das Symbol und seine Attribute als Argumente und speichert die Informationen in der Symboltabelle.

Zum Beispiel:

int a;

sollte vom Compiler wie folgt verarbeitet werden:

insert(a, int);

Nachsehen()

Mit der Operation lookup () wird ein Name in der Symboltabelle gesucht, um Folgendes zu ermitteln:

  • wenn das Symbol in der Tabelle vorhanden ist.
  • wenn es deklariert ist, bevor es verwendet wird.
  • wenn der Name im Bereich verwendet wird.
  • wenn das Symbol initialisiert ist.
  • wenn das Symbol mehrfach deklariert wurde.

Das Format der Funktion lookup () variiert je nach Programmiersprache. Das Grundformat sollte wie folgt übereinstimmen:

lookup(symbol)

Diese Methode gibt 0 (Null) zurück, wenn das Symbol nicht in der Symboltabelle vorhanden ist. Wenn das Symbol in der Symboltabelle vorhanden ist, gibt es seine in der Tabelle gespeicherten Attribute zurück.

Bereichsverwaltung

Ein Compiler verwaltet zwei Arten von Symboltabellen: a global symbol table auf die von allen Verfahren zugegriffen werden kann und scope symbol tables die für jeden Bereich im Programm erstellt werden.

Um den Umfang eines Namens zu bestimmen, werden Symboltabellen in hierarchischer Struktur angeordnet, wie im folgenden Beispiel gezeigt:

. . . 
int value=10;

void pro_one()
   {
   int one_1;
   int one_2;
   
      {              \
      int one_3;      |_  inner scope 1 
      int one_4;      | 
      }              /
      
   int one_5; 
   
      {              \   
      int one_6;      |_  inner scope 2
      int one_7;      |
      }              /
   }
   
void pro_two()
   {
   int two_1;
   int two_2;
   
      {              \
      int two_3;      |_  inner scope 3
      int two_4;      |
      }              /
      
   int two_5;
   }
. . .

Das obige Programm kann in einer hierarchischen Struktur von Symboltabellen dargestellt werden:

Die globale Symboltabelle enthält Namen für eine globale Variable (int-Wert) und zwei Prozedurnamen, die allen oben gezeigten untergeordneten Knoten zur Verfügung stehen sollten. Die in der Symboltabelle pro_one (und allen untergeordneten Tabellen) genannten Namen sind für die Symbole pro_two und die untergeordneten Tabellen nicht verfügbar.

Diese Datenstruktur-Hierarchie der Symboltabelle wird im semantischen Analysator gespeichert. Wenn ein Name in einer Symboltabelle gesucht werden muss, wird er mit dem folgenden Algorithmus durchsucht:

  • Zuerst wird ein Symbol im aktuellen Bereich gesucht, dh in der aktuellen Symboltabelle.

  • Wenn ein Name gefunden wird, ist die Suche abgeschlossen. Andernfalls wird er in der übergeordneten Symboltabelle gesucht, bis,

  • Entweder wurde der Name gefunden oder die globale Symboltabelle wurde nach dem Namen durchsucht.

Ein Quellcode kann direkt in seinen Zielmaschinencode übersetzt werden. Warum müssen wir dann den Quellcode überhaupt in einen Zwischencode übersetzen, der dann in seinen Zielcode übersetzt wird? Lassen Sie uns die Gründe sehen, warum wir einen Zwischencode benötigen.

  • Wenn ein Compiler die Quellsprache in seine Zielcomputersprache übersetzt, ohne die Option zum Generieren von Zwischencode zu haben, ist für jeden neuen Computer ein vollständiger nativer Compiler erforderlich.

  • Durch den Zwischencode ist kein neuer vollständiger Compiler für jede einzelne Maschine erforderlich, da der Analyseteil für alle Compiler gleich bleibt.

  • Der zweite Teil des Compilers, die Synthese, wird entsprechend der Zielmaschine geändert.

  • Es wird einfacher, die Quellcodemodifikationen anzuwenden, um die Codeleistung zu verbessern, indem Codeoptimierungstechniken auf den Zwischencode angewendet werden.

Zwischenvertretung

Zwischencodes können auf verschiedene Arten dargestellt werden und haben ihre eigenen Vorteile.

  • High Level IR- Die Darstellung von Zwischencode auf hoher Ebene kommt der Quellsprache selbst sehr nahe. Sie können einfach aus dem Quellcode generiert werden, und wir können problemlos Codemodifikationen anwenden, um die Leistung zu verbessern. Für die Zielmaschinenoptimierung ist dies jedoch weniger bevorzugt.

  • Low Level IR - Dieser befindet sich in der Nähe des Zielcomputers, wodurch er für die Register- und Speicherzuordnung, die Auswahl von Befehlssätzen usw. geeignet ist. Er eignet sich für maschinenabhängige Optimierungen.

Zwischencode kann entweder sprachspezifisch (z. B. Bytecode für Java) oder sprachunabhängig (Code mit drei Adressen) sein.

Code mit drei Adressen

Der Zwischencodegenerator empfängt Eingaben von seiner Vorgängerphase, dem semantischen Analysator, in Form eines mit Anmerkungen versehenen Syntaxbaums. Dieser Syntaxbaum kann dann in eine lineare Darstellung konvertiert werden, z. B. Postfix-Notation. Zwischencode ist in der Regel maschinenunabhängiger Code. Daher geht der Codegenerator von einer unbegrenzten Anzahl von Speichern (Registern) aus, um Code zu generieren.

Zum Beispiel:

a = b + c * d;

Der Zwischencodegenerator versucht, diesen Ausdruck in Unterausdrücke zu unterteilen und dann den entsprechenden Code zu generieren.

r1 = c * d;
r2 = b + r1;
a = r2

r wird als Register im Zielprogramm verwendet.

Ein Code mit drei Adressen hat höchstens drei Adresspositionen, um den Ausdruck zu berechnen. Ein Code mit drei Adressen kann in zwei Formen dargestellt werden: vierfach und dreifach.

Vierfache

Jede Anweisung in der Vierfachpräsentation ist in vier Felder unterteilt: Operator, arg1, arg2 und Ergebnis. Das obige Beispiel ist unten im Vierfachformat dargestellt:

Op arg 1 arg 2 Ergebnis
* * c d r1
+ b r1 r2
+ r2 r1 r3
= r3 ein

Dreifache

Jede Anweisung in Dreifachdarstellung hat drei Felder: op, arg1 und arg2. Die Ergebnisse der jeweiligen Unterausdrücke werden durch die Position des Ausdrucks angegeben. Tripel stehen für Ähnlichkeit mit DAG und Syntaxbaum. Sie entsprechen der DAG, während sie Ausdrücke darstellen.

Op arg 1 arg 2
* * c d
+ b (0)
+ (1) (0)
= (2)

Tripel sehen sich dem Problem der Code-Unbeweglichkeit während der Optimierung gegenüber, da die Ergebnisse positionell sind und das Ändern der Reihenfolge oder Position eines Ausdrucks Probleme verursachen kann.

Indirekte Tripel

Diese Darstellung ist eine Verbesserung gegenüber der Dreifachdarstellung. Es werden Zeiger anstelle der Position verwendet, um die Ergebnisse zu speichern. Dadurch können die Optimierer den Unterausdruck frei positionieren, um einen optimierten Code zu erzeugen.

Erklärungen

Eine Variable oder Prozedur muss deklariert werden, bevor sie verwendet werden kann. Die Deklaration umfasst die Zuweisung von Speicherplatz im Speicher und die Eingabe von Typ und Name in die Symboltabelle. Ein Programm kann unter Berücksichtigung der Zielmaschinenstruktur codiert und entworfen werden, es ist jedoch möglicherweise nicht immer möglich, einen Quellcode genau in seine Zielsprache zu konvertieren.

Wenn das gesamte Programm als Sammlung von Prozeduren und Unterprozeduren betrachtet wird, können alle lokalen Namen der Prozedur deklariert werden. Die Speicherzuweisung erfolgt nacheinander, und die Namen werden dem Speicher in der Reihenfolge zugewiesen, in der sie im Programm deklariert sind. Wir verwenden die Offset-Variable und setzen sie auf Null {offset = 0}, was die Basisadresse bezeichnet.

Die Quellprogrammiersprache und die Zielmaschinenarchitektur können in der Art und Weise, wie Namen gespeichert werden, variieren, sodass die relative Adressierung verwendet wird. Während dem Vornamen ab dem Speicherort 0 {offset = 0} Speicher zugewiesen wird, sollte dem später deklarierten nächsten Namen neben dem ersten Speicher zugewiesen werden.

Example:

Wir nehmen das Beispiel der Programmiersprache C, in der einer ganzzahligen Variablen 2 Byte Speicher und einer Float-Variablen 4 Byte Speicher zugewiesen werden.

int a;
float b;
Allocation process:
{offset = 0}
int a;
id.type = int
id.width = 2
offset = offset + id.width 
{offset = 2}
float b;
   id.type = float
   id.width = 4
   offset = offset + id.width 
{offset = 6}

Um dieses Detail in eine Symboltabelle einzugeben, kann eine Prozedureingabe verwendet werden. Diese Methode kann folgende Struktur haben:

enter(name, type, offset)

Dieses Verfahren sollte einen Eintrag in der Symboltabelle für variable erstellen Namen , ihren Typ Satz aufweist und die relative Adresse geben Offset in seinem Datenbereich.

Die Codegenerierung kann als letzte Phase der Kompilierung betrachtet werden. Durch die Postleitzahlgenerierung kann der Optimierungsprozess auf den Code angewendet werden, dies kann jedoch als Teil der Codegenerierungsphase selbst angesehen werden. Der vom Compiler generierte Code ist ein Objektcode einer untergeordneten Programmiersprache, z. B. Assemblersprache. Wir haben gesehen, dass der in einer höheren Sprache geschriebene Quellcode in eine niedrigere Sprache umgewandelt wird, was zu einem niedrigeren Objektcode führt, der die folgenden Mindesteigenschaften haben sollte:

  • Es sollte die genaue Bedeutung des Quellcodes tragen.
  • Es sollte in Bezug auf CPU-Auslastung und Speicherverwaltung effizient sein.

Wir werden nun sehen, wie der Zwischencode in Zielobjektcode (in diesem Fall Assembler-Code) umgewandelt wird.

Directed Acyclic Graph

Directed Acyclic Graph (DAG) ist ein Tool, das die Struktur von Basisblöcken darstellt, den Wertefluss zwischen den Basisblöcken erkennt und auch Optimierungen bietet. DAG bietet eine einfache Transformation für Basisblöcke. DAG kann hier verstanden werden:

  • Blattknoten repräsentieren Bezeichner, Namen oder Konstanten.

  • Innenknoten repräsentieren Operatoren.

  • Innenknoten repräsentieren auch die Ergebnisse von Ausdrücken oder die Bezeichner / Namen, in denen die Werte gespeichert oder zugewiesen werden sollen.

Example:

t0 = a + b
t1 = t0 + c
d = t0 + t1

[t 0 = a + b]

[t 1 = t 0 + c]

[d = t 0 + t 1 ]

Gucklochoptimierung

Diese Optimierungstechnik arbeitet lokal mit dem Quellcode, um ihn in einen optimierten Code umzuwandeln. Mit lokal meinen wir einen kleinen Teil des vorliegenden Codeblocks. Diese Methoden können sowohl auf Zwischencodes als auch auf Zielcodes angewendet werden. Eine Reihe von Aussagen wird analysiert und auf folgende mögliche Optimierung überprüft:

Redundante Anweisungseliminierung

Auf Quellcodeebene kann der Benutzer Folgendes tun:

int add_ten(int x)
   {
   int y, z;
   y = 10;
   z = x + y;
   return z;
   }
int add_ten(int x)
   {
   int y;
   y = 10;
   y = x + y;
   return y;
   }
int add_ten(int x)
   {
   int y = 10;
   return x + y;
   }
int add_ten(int x)
   {
   return x + 10;
   }

Auf Kompilierungsebene sucht der Compiler nach redundanten Anweisungen. Das mehrfache Laden und Speichern von Anweisungen kann dieselbe Bedeutung haben, selbst wenn einige von ihnen entfernt werden. Zum Beispiel:

  • MOV x, R0
  • MOV R0, R1

Wir können die erste Anweisung löschen und den Satz neu schreiben als:

MOV x, R1

Unerreichbarer Code

Nicht erreichbarer Code ist ein Teil des Programmcodes, auf den aufgrund von Programmierkonstrukten nie zugegriffen wird. Programmierer haben möglicherweise versehentlich einen Code geschrieben, der niemals erreicht werden kann.

Example:

void add_ten(int x)
{
   return x + 10;
   printf(“value of x is %d”, x);
}

In diesem Codesegment wird die printf Die Anweisung wird niemals ausgeführt, da die Programmsteuerung zurückkehrt, bevor sie ausgeführt werden kann printf kann entfernt werden.

Ablauf der Steuerungsoptimierung

Es gibt Fälle in einem Code, in denen die Programmsteuerung hin und her springt, ohne eine wesentliche Aufgabe auszuführen. Diese Sprünge können entfernt werden. Betrachten Sie den folgenden Codeabschnitt:

...		
MOV R1, R2
GOTO L1
...
L1 :   GOTO L2
L2 :   INC R1

In diesem Code kann die Bezeichnung L1 entfernt werden, wenn die Steuerung an L2 übergeben wird. Anstatt also zu L1 und dann zu L2 zu springen, kann die Steuerung L2 direkt erreichen, wie unten gezeigt:

...		
MOV R1, R2
GOTO L2
...
L2 :   INC R1

Vereinfachung des algebraischen Ausdrucks

Es gibt Fälle, in denen algebraische Ausdrücke einfach gemacht werden können. Zum Beispiel der Ausdrucka = a + 0 kann ersetzt werden durch a selbst und der Ausdruck a = a + 1 können einfach durch INC a ersetzt werden.

Kraftreduzierung

Es gibt Vorgänge, die mehr Zeit und Platz beanspruchen. Ihre "Stärke" kann verringert werden, indem sie durch andere Vorgänge ersetzt werden, die weniger Zeit und Platz verbrauchen, aber das gleiche Ergebnis erzielen.

Zum Beispiel, x * 2 kann ersetzt werden durch x << 1, was nur eine Linksverschiebung beinhaltet. Obwohl die Ausgabe von a * a und a 2 gleich ist, ist die Implementierung einer 2 viel effizienter.

Zugriff auf Maschinenanweisungen

Der Zielcomputer kann komplexere Anweisungen bereitstellen, mit denen bestimmte Vorgänge sehr effizient ausgeführt werden können. Wenn der Zielcode diese Anweisungen direkt aufnehmen kann, verbessert dies nicht nur die Qualität des Codes, sondern führt auch zu effizienteren Ergebnissen.

Code Generator

Von einem Codegenerator wird erwartet, dass er die Laufzeitumgebung des Zielcomputers und seinen Befehlssatz versteht. Der Codegenerator sollte die folgenden Aspekte berücksichtigen, um den Code zu generieren:

  • Target language: Der Codegenerator muss die Art der Zielsprache kennen, für die der Code transformiert werden soll. Diese Sprache kann einige maschinenspezifische Anweisungen erleichtern, damit der Compiler den Code bequemer generieren kann. Der Zielcomputer kann entweder über eine CISC- oder eine RISC-Prozessorarchitektur verfügen.

  • IR Type: Zwischendarstellung hat verschiedene Formen. Es kann sich um eine AST-Struktur (Abstract Syntax Tree), eine umgekehrte polnische Notation oder einen Code mit drei Adressen handeln.

  • Selection of instruction: Der Codegenerator nimmt die Zwischendarstellung als Eingabe und konvertiert sie (ordnet sie zu) in den Befehlssatz der Zielmaschine. Eine Darstellung kann viele Möglichkeiten (Anweisungen) haben, um sie zu konvertieren. Daher liegt es in der Verantwortung des Codegenerators, die entsprechenden Anweisungen mit Bedacht auszuwählen.

  • Register allocation: Ein Programm hat eine Reihe von Werten, die während der Ausführung beibehalten werden müssen. Die Architektur des Zielcomputers ermöglicht möglicherweise nicht, dass alle Werte im CPU-Speicher oder in den Registern gespeichert werden. Der Codegenerator entscheidet, welche Werte in den Registern gespeichert werden sollen. Außerdem entscheidet es, welche Register verwendet werden sollen, um diese Werte beizubehalten.

  • Ordering of instructions: Zuletzt entscheidet der Codegenerator über die Reihenfolge, in der der Befehl ausgeführt wird. Es werden Zeitpläne für Anweisungen erstellt, um sie auszuführen.

Deskriptoren

Der Codegenerator muss beim Generieren des Codes sowohl die Register (auf Verfügbarkeit) als auch die Adressen (Position der Werte) verfolgen. Für beide werden die folgenden zwei Deskriptoren verwendet:

  • Register descriptor: Der Registerdeskriptor wird verwendet, um den Codegenerator über die Verfügbarkeit von Registern zu informieren. Der Registerdeskriptor verfolgt die in jedem Register gespeicherten Werte. Wenn während der Codegenerierung ein neues Register erforderlich ist, wird dieser Deskriptor zur Verfügbarkeit des Registers herangezogen.

  • Address descriptor: Die Werte der im Programm verwendeten Namen (Bezeichner) können während der Ausführung an verschiedenen Orten gespeichert werden. Adressdeskriptoren werden verwendet, um Speicherorte zu verfolgen, an denen die Werte von Bezeichnern gespeichert sind. Diese Speicherorte können CPU-Register, Heaps, Stapel, Speicher oder eine Kombination der genannten Speicherorte umfassen.

Der Codegenerator hält beide Deskriptoren in Echtzeit auf dem neuesten Stand. Für eine Ladeanweisung, LD R1, x, der Codegenerator:

  • aktualisiert den Registerdeskriptor R1 mit dem Wert x und
  • aktualisiert den Adressdeskriptor (x), um anzuzeigen, dass sich eine Instanz von x in R1 befindet.

Codegenerierung

Grundblöcke bestehen aus einer Folge von Anweisungen mit drei Adressen. Der Codegenerator verwendet diese Befehlsfolge als Eingabe.

Note: Wenn der Wert eines Namens an mehr als einer Stelle gefunden wird (Register, Cache oder Speicher), wird der Wert des Registers dem Cache und dem Hauptspeicher vorgezogen. Ebenso wird der Wert des Caches dem Hauptspeicher vorgezogen. Der Hauptspeicher wird kaum bevorzugt.

getReg: Der Codegenerator verwendet die Funktion getReg , um den Status der verfügbaren Register und die Position der Namenswerte zu bestimmen. getReg funktioniert wie folgt:

  • Befindet sich die Variable Y bereits im Register R, wird dieses Register verwendet.

  • Andernfalls wird dieses Register verwendet, wenn ein Register R verfügbar ist.

  • Andernfalls, wenn beide oben genannten Optionen nicht möglich sind, wird ein Register ausgewählt, das eine minimale Anzahl von Lade- und Speicheranweisungen erfordert.

Für eine Anweisung x = y OP z kann der Codegenerator die folgenden Aktionen ausführen. Nehmen wir an, dass L der Ort (vorzugsweise Register) ist, an dem die Ausgabe von y OP z gespeichert werden soll:

  • Rufen Sie die Funktion getReg auf, um den Standort von L zu bestimmen.

  • Bestimmen Sie den aktuellen Speicherort (Register oder Speicher) von y durch Rücksprache mit dem Adressdeskriptor von y. Wenny ist derzeit nicht im Register LGenerieren Sie dann die folgende Anweisung, um den Wert von zu kopieren y zu L::

    MOV y ', L.

    wo y’ repräsentiert den kopierten Wert von y.

  • Bestimmen Sie den aktuellen Standort von z unter Verwendung der gleichen Methode wie in Schritt 2 für y und generieren Sie die folgende Anweisung:

    OP z ', L.

    wo z’ repräsentiert den kopierten Wert von z.

  • Jetzt enthält L den Wert von y OP z, dem zugewiesen werden soll x. Wenn L also ein Register ist, aktualisieren Sie seinen Deskriptor, um anzuzeigen, dass er den Wert von enthältx. Aktualisieren Sie den Deskriptor vonx um anzuzeigen, dass es am Ort gespeichert ist L.

  • Wenn y und z keine weitere Verwendung haben, können sie an das System zurückgegeben werden.

Andere Codekonstrukte wie Schleifen und bedingte Anweisungen werden auf allgemeine Assemblierungsweise in Assemblersprache umgewandelt.

Bei der Optimierung handelt es sich um eine Programmtransformationstechnik, mit der versucht wird, den Code zu verbessern, indem weniger Ressourcen (z. B. CPU, Speicher) verbraucht werden und eine hohe Geschwindigkeit bereitgestellt wird.

Bei der Optimierung werden allgemeine Programmierkonstrukte auf hoher Ebene durch sehr effiziente Programmiercodes auf niedriger Ebene ersetzt. Ein Codeoptimierungsprozess muss den folgenden drei Regeln folgen:

  • Der Ausgabecode darf die Bedeutung des Programms in keiner Weise ändern.

  • Die Optimierung sollte die Geschwindigkeit des Programms erhöhen und wenn möglich, sollte das Programm weniger Ressourcen erfordern.

  • Die Optimierung sollte selbst schnell sein und den gesamten Kompilierungsprozess nicht verzögern.

Auf verschiedenen Ebenen der Kompilierung des Prozesses können Anstrengungen für einen optimierten Code unternommen werden.

  • Zu Beginn können Benutzer den Code ändern / neu anordnen oder bessere Algorithmen verwenden, um den Code zu schreiben.

  • Nach dem Generieren des Zwischencodes kann der Compiler den Zwischencode durch Adressberechnungen und Verbessern von Schleifen ändern.

  • Während der Erstellung des Zielmaschinencodes kann der Compiler Speicherhierarchie und CPU-Register verwenden.

Die Optimierung kann grob in zwei Typen eingeteilt werden: maschinenunabhängig und maschinenabhängig.

Maschinenunabhängige Optimierung

Bei dieser Optimierung nimmt der Compiler den Zwischencode auf und transformiert einen Teil des Codes, der keine CPU-Register und / oder absoluten Speicherplätze enthält. Zum Beispiel:

do
{
   item = 10;
   value = value + item; 
}while(value<100);

Dieser Code beinhaltet die wiederholte Zuweisung des Identifizierungselements. Wenn wir dies so ausdrücken:

Item = 10;
do
{
   value = value + item; 
} while(value<100);

sollte nicht nur die CPU-Zyklen speichern, sondern kann auf jedem Prozessor verwendet werden.

Maschinenabhängige Optimierung

Die maschinenabhängige Optimierung erfolgt nach der Generierung des Zielcodes und nach der Transformation des Codes gemäß der Zielmaschinenarchitektur. Es handelt sich um CPU-Register und kann eher absolute Speicherreferenzen als relative Referenzen haben. Maschinenabhängige Optimierer bemühen sich, die Speicherhierarchie optimal zu nutzen.

Grundblöcke

Quellcodes enthalten im Allgemeinen eine Reihe von Anweisungen, die immer nacheinander ausgeführt werden und als Grundblöcke des Codes betrachtet werden. Diese Basisblöcke enthalten keine Sprunganweisungen, dh wenn der erste Befehl ausgeführt wird, werden alle Befehle im selben Basisblock in ihrer Reihenfolge ausgeführt, ohne dass die Ablaufsteuerung des Programms verloren geht.

Ein Programm kann verschiedene Konstrukte als Basisblöcke haben, wie z. B. bedingte Anweisungen IF-THEN-ELSE, SWITCH-CASE und Schleifen wie DO-WHILE, FOR und REPEAT-UNTIL usw.

Grundlegende Blockidentifikation

Wir können den folgenden Algorithmus verwenden, um die Grundblöcke in einem Programm zu finden:

  • Durchsuchen Sie die Header-Anweisungen aller Basisblöcke, von denen aus ein Basisblock beginnt:

    • Erste Aussage eines Programms.
    • Anweisungen, die Ziel eines Zweigs sind (bedingt / bedingungslos).
    • Anweisungen, die auf eine Verzweigungsanweisung folgen.
  • Header-Anweisungen und die darauf folgenden Anweisungen bilden einen Basisblock.

  • Ein Basisblock enthält keine Header-Anweisung eines anderen Basisblocks.

Grundblöcke sind wichtige Konzepte sowohl aus Sicht der Codegenerierung als auch der Optimierung.

Basisblöcke spielen eine wichtige Rolle bei der Identifizierung von Variablen, die in einem einzelnen Basisblock mehrmals verwendet werden. Wenn eine Variable mehrmals verwendet wird, muss der dieser Variablen zugewiesene Registerspeicher erst geleert werden, wenn der Block die Ausführung beendet hat.

Kontrollflussdiagramm

Grundbausteine ​​in einem Programm können mit Hilfe von Kontrollflussdiagrammen dargestellt werden. Ein Steuerungsflussdiagramm zeigt, wie die Programmsteuerung zwischen den Blöcken übergeben wird. Es ist ein nützliches Tool, das bei der Optimierung hilft, indem es unerwünschte Schleifen im Programm findet.

Schleifenoptimierung

Die meisten Programme werden als Schleife im System ausgeführt. Es wird notwendig, die Schleifen zu optimieren, um CPU-Zyklen und Speicher zu sparen. Schleifen können durch die folgenden Techniken optimiert werden:

  • Invariant code: Ein Codefragment, das sich in der Schleife befindet und bei jeder Iteration denselben Wert berechnet, wird als schleifeninvarianter Code bezeichnet. Dieser Code kann aus der Schleife verschoben werden, indem er gespeichert wird, damit er nur einmal und nicht bei jeder Iteration berechnet wird.

  • Induction analysis : Eine Variable wird als Induktionsvariable bezeichnet, wenn ihr Wert innerhalb der Schleife durch einen schleifeninvarianten Wert geändert wird.

  • Strength reduction: Es gibt Ausdrücke, die mehr CPU-Zyklen, Zeit und Speicher verbrauchen. Diese Ausdrücke sollten durch billigere Ausdrücke ersetzt werden, ohne die Ausgabe des Ausdrucks zu beeinträchtigen. Beispielsweise ist die Multiplikation (x * 2) in Bezug auf die CPU-Zyklen teurer als (x << 1) und liefert das gleiche Ergebnis.

Dead-Code-Eliminierung

Toter Code ist eine oder mehrere Code-Anweisungen, die:

  • Entweder nie ausgeführt oder nicht erreichbar,
  • Oder wenn sie ausgeführt werden, wird ihre Ausgabe niemals verwendet.

Somit spielt toter Code bei keiner Programmoperation eine Rolle und kann daher einfach beseitigt werden.

Teilweise toter Code

Es gibt einige Code-Anweisungen, deren berechnete Werte nur unter bestimmten Umständen verwendet werden, dh manchmal werden die Werte verwendet und manchmal nicht. Solche Codes werden als teilweise toter Code bezeichnet.

Das obige Kontrollflussdiagramm zeigt einen Programmabschnitt, in dem die Variable 'a' verwendet wird, um die Ausgabe des Ausdrucks 'x * y' zuzuweisen. Nehmen wir an, dass der Wert, der 'a' zugewiesen ist, niemals innerhalb der Schleife verwendet wird. Unmittelbar nachdem das Steuerelement die Schleife verlassen hat, wird 'a' der Wert der Variablen 'z' zugewiesen, der später im Programm verwendet wird. Wir schließen hier, dass der Zuweisungscode von 'a' nirgendwo verwendet wird und daher entfernt werden kann.

Ebenso zeigt das obige Bild, dass die bedingte Anweisung immer falsch ist, was bedeutet, dass der im wahren Fall geschriebene Code niemals ausgeführt wird und daher entfernt werden kann.

Teilredundanz

Redundante Ausdrücke werden mehr als einmal im parallelen Pfad ohne Änderung der Operanden berechnet. Teilredundante Ausdrücke werden mehr als einmal im Pfad ohne Änderung der Operanden berechnet. Zum Beispiel,

[redundanter Ausdruck]

[teilweise redundanter Ausdruck]

Schleifeninvarianter Code ist teilweise redundant und kann mithilfe einer Code-Motion-Technik eliminiert werden.

Ein weiteres Beispiel für einen teilweise redundanten Code kann sein:

If (condition)
{
   a = y OP z;
}
else
{
   ...
}
c = y OP z;

Wir nehmen an, dass die Werte von Operanden (y und z) werden von der Zuweisung der Variablen nicht geändert a zu variabel c. Wenn hier die Bedingungsanweisung wahr ist, wird y OP z zweimal berechnet, andernfalls einmal. Code-Bewegung kann verwendet werden, um diese Redundanz zu beseitigen, wie unten gezeigt:

If (condition)
{
   ...
   tmp = y OP z;
   a = tmp;
   ...
}
else
{
   ...
   tmp = y OP z;
}
c = tmp;

Hier, ob die Bedingung wahr oder falsch ist; y OP z sollte nur einmal berechnet werden.