Compiler Principle
Compiler Principle
1.Einleitung
1.1 Der Überblick über Compiler
1.1.1 Lexikalische Analyse
Die lexikalische Analyse zerteilt den eingelesenen Quelltext in lexikalische Einheiten (Tokens) verschiedener Typen, zum Beispiel Schlüsselwörter, Bezeichner, Zahlen, Zeichenketten oder Operatoren. Dieser Teil des Compilers heißt Scanner oder Lexer.
1.1.2 Syntaktische Analyse
Die syntaktische Analyse überprüft, ob der eingelesene Quellcode in einer korrekten Struktur der zu übersetzenden Quellsprache vorliegt, das heißt der kontextfreien Syntax (Grammatik) der Quellsprache entspricht
1.1.3 Semantische Analyse
Die semantische Analyse überprüft die statische Semantik, also über die syntaktische Analyse hinausgehende Bedingungen an das Programm.
Verschiedene Phase der Compiler:
Eine Übersetzung des Satzes:
1.1.4 Interpreter
Ein Interpreter ist ein Computerprogramm, das einen Programm-Quellcode im Gegensatz zu Assemblern oder Compilern nicht in eine auf dem System direkt ausführbare Datei übersetzt, sondern den Quellcode einliest, analysiert und ausführt.
1.1.5 Compiler
Ein Compiler ist ein Computerprogramm, das Quellcodes einer bestimmten Programmiersprache in eine Form übersetzt, die von einem Computer (direkter) ausgeführt werden kann.
2.Lexikalische Analyse
2.1 Kette und Sprache
Kette:Die Kette in Alphabet ist endliche Sequenz der Alphabetstabelle
Sprache:Eine Ketteliste der Alphabet
2.2 Regulärer Ausdruck
Regulärer Ausdruck:Ein regulärer Ausdruck ist in der theoretischen Informatik eine Zeichenkette, die der Beschreibung von Mengen von Zeichenketten mit Hilfe bestimmter syntaktischer Regeln dient.
Regulärer Liste:ist eine Sprache,die mit regulärer Ausdruck ausdrucken kann.
Priorität der Rechnung:Closure>Verbindung>Auswahl
2.3 Die Definition der Regulärer Ausdruck
Man kann regulärer Ausdruck bennen und mit diese Name entsprechende regulärer Ausdruck zitieren.
Die Difinition der Regulärer Ausdruck:
Form wie
d1->r1
d2->r2
···
dn->rn
Zum Beispieil:
letter_->[A-Za-z_]
digit->0|1|···|9
id->letter_(letter_|digit)*
number->digit+(.digit+)?(E(+/-)?digit+)?
2.4 Nichtdeterministischer endlicher Automat
Ein nichtdeterministischer endlicher Automat (NEA; englisch nondeterministic finite automaton, NFA) ist ein endlicher Automat, bei dem es für den Zustandsübergang mehrere gleichwertige Möglichkeiten gibt. Im Unterschied zum deterministischen endlichen Automaten sind die Möglichkeiten nicht eindeutig, dem Automaten ist also nicht vorgegeben, welchen Übergang er zu wählen hat.
2.5 Deterministischer endlicher Automat
Ein deterministischer endlicher Automat (DEA; englisch deterministic finite automaton, DFA) ist ein endlicher Automat, der unter Eingabe eines Zeichens seines Eingabealphabetes (den möglichen Eingaben) von einem Zustand, in dem er sich befindet, in einen eindeutig bestimmten Folgezustand wechselt. Er unterscheidet sich darin von nichtdeterministischen endlichen Automaten, deren Zustandswechsel sich nicht immer deterministisch ereignen müssen.
2.5.1 Die Umsetzung von NFA nach DFA
Beispiel 1:Bildst du fur (a|b)*a(a|b) DFA
Zuerst zeichnen wir NFA
Bilden wir einen Dtran,gesamt vier verschiedene Liste
Abgrund des Dtrans zeichnen wir die Abbildung der DFA
Beispiel2:DFA,Die Binarzahl,die in {0,1} mit 5 Division ohne Rest machen kann,kann erkannt werden.
3.Syntaktische Analyse
3.1 Die Definition der Kontextfreie Grammatik
Normalerweise gesagt,G ist ein vierTuple(VT,VN,S,P),darunter:
(1)VT ist eine nicht leer und endliche Menge,deren Element wird als Terminalsymbol bezeichnet
(2)VN ist eine nicht leer und endliche Menge,deren Element wird als Nichtterminalsymbol bezeichnet
(3)S ist eine NichtTerminalsymbol,bezeichnen wir Startsymbol
(4)P ist eine Menge von Produktion
3.2 Folgendes Zeichen wird als Terminalsymbol/Nichtterminalsymbol benutzt
3.3 Die Zwei Bedeutung der Grammatik
Aufgrund der Grammatiks E->E+E|E*E|(E)|-E|id
3.4 Beseitigen Linke Rekursion
Es besteht A=>Aα,bezeichnen wir diese Grammatik Linke Rekursion
Linke Rekursion A->Aα|β kann mit nicht Linke Rekursion
A->βA'
A'->αA'|ε
ersetzen
3.5 LL(1) Grammatik
3.5.1 Die Definition der LL(1)
3.5.2 Berechnen First Menge
Methode:Berechnen wir Grammatik Symbolzeichenfolge,die Produktion der Terminalsymbol enthält,dann erhalten wir linken Seite der Produktion
Beispiel:FIRST(E) = FIRST(T) = FIRST(F) = {(,id} (Die Produktion müssen Terminalsymbol haben)
FIRST(E') = {+,ε} (Die Grammatik hier enthält Terminalsymbol,unnötig nach unten zu berechnen)
FIRST(T') = {*,ε} (gleich wie oben)
3.5.3 Berechnen Follow Menge
Methode:
berechnen wir der Rechte Seite des X,den Follow(X) Menge umfassen;
Vorhergehend Grammatik Symbolzeichenfolgen sitzen in dem Produktion der Follow;
Falls die Rechte Seite der X kein Terminalsymbol hat,fügen First Menge der Rechten Seite der X hinein;
Beispiel:FOLLOW(E) = FOLLOW(E') = {),$} (haben kein Verhältnis zu E',schauen wir der rechten Seite der Produktion der E,Ergebnis ist ')',legen es und '$' in Follow Menge)
FOLLOW(T) = FOLLOW(T') = {+,),$} (Weil First(E') ε und + umfasst,ε wird defalut beseitigt, legen '+' in Follow(E))
FOLLOW(F) = {+,*,),$} (Die rechte Seite der F hat kein Terminalsymbol F,fügen First(T') Follow(T) hinein)