Turbo Toolbox/Turbo_Toolbox.iso/spezial/02/texte/pascomp.4

Text File | 1980-01-03 | 21.0 KB | 502 lines

Pascomp

Pascal baut einen Pascal - Compiler


Teil 5: Die semantische Analyse
        von Johannes Velmans


Mit   der   semantischen   Analyse   haben  wir  jetzt  nach  der
lexikalischen  und  der  syntaktischen  Analyse  die  letzte  zum
Analyseteil eines Compilers gehörende Arbeitsphase erreicht.

Die Aufgabe der semantischen Analyse besteht darin, die statische
Semantik  von  Programmen  zu überprüfen, sowie Informationen für
den  Syntheseteil  des  Compilers (Codeerzeugung und Optimierung)
bereitzustellen.  Wie  wir  bereits  aus  den  bisherigen  Folgen
erfahren  haben,  wird  die Syntax einer Programmiersprache durch
eine   kontextfreie   Grammatik,  die  meistens  in  BNF-Notation
formuliert   wird,   beschrieben.   Die  Syntaxanalyse  überprüft
demzufolge  die  strukturelle  Korrektheit  des  zu übersetzenden
Programms.  Soweit,  so gut. Programmiersprachen besitzen aber in
aller  Regel  die Eigenschaft, nicht kontextfrei zu sein, was dem
einen  oder  anderen  Compilerhersteller  schon  hin  und  wieder
Kopfschmerzen bereitet hat.

Für  den Nachweis der Korrektheit eines Programms ist es daher in
keinem  Fall  ausreichend, nur die syntaktische Korrektheit eines
Programms zu untersuchen. Die Korrektheit von Programmen hängt im
weiteren  noch  davon  ab,  ob  die  auftreten  den (angewandten)
Bezeichner  konsistent  mit ihren implizit und explizit gegebenen
Deklarationen und Definitionen benutzt werden. Diese Bedingungen,
die in entsprechenden Regeln "verpackt" werden, bezeichnet man in
der Fachliteratur mit dem Begriff der Kontextbedingungen.

Der aufmerksame Leser könnte an dieser Stelle meinen, daß es auch
hier  einen  Formalismus gibt, der die Semantik beschreibt. Einen
derartigen  Formalismus,  wie  es  ihn  bei der lexikalischen und
syntaktischen  Analyse  gab,  existiert  für die Beschreibung der
Semantik  einer  Programmiersprache  aber  leider  nicht. Bis zum
heutigen  Tage  ist  die  Semantik fast aller Programmiersprachen
informell,  das  heißt  in  natürlicher  Sprache  und  in  Worten
definiert.

Als  Beispiel  sei  hier an das Problem der zulässigen Feldindex-
Typen aus dem Pascal-Report erinnert. Hier lesen wir:

 ...type a=array[t1] of t2

wobei a ein neuer Typbezeichner ist. t1 ist der Indextyp, der ein
Scalar-  oder  ein  Unterbereichstyp  sein  kann, wobei die Typen
integer und real keine zugelassenen Indextypen sind...

Unterstellt  man  einmal,  daß  solche  Semantikbeschreibungen in
verantwortungsvoller Arbeit erstellt und überpüft wurden, so sind
derartige  informelle Beschreibungen nicht selten mit Fehlern und
Mehrdeutigkeiten übersät oder einfach unvollständig. Ein formaler
Ansatz  zur Semantikbeschreibung hätte dahingegen aufgrund seines
mechanischen  Aufbaus  den  Vorteil,  auf  einfache Art und Weise
einen  Entscheidungsprozess  herbeizuführen,  mit  dem  man  eine
Sprache  als  korrekt  und vollständig identifizieren könnte. Ein
weiterer,  genauso  wichtiger  Aspekt steht in engem Zusammenhang
mit  der  Implementierung  einer  beliebigen  Programmiersprache:
Außer  für  die  semantische  Analyse  bestehen  bereits für alle
weiteren Phasen eines Compilers erzeugende Systeme.

Würde  man jetzt noch die Semantik formal definieren, so wäre man
in  der  Lage,  ein  Programm  zu  schreiben,  dessen Eingabe die
Beschreibung   einer   Programmiersprache  darstellt  und  dessen
Ausgabe  ein  Compiler  zu  dieser  Programmiersprache  wäre. Die
einzige  Aufgabe eines Compilerherstellers bestünde dann nur noch
darin, die Eingabe entsprechend formal zu definieren.

Die  Beschäftigung  mit  Scanner, Parser, Codeerzeugung usw. wäre
dann  "von  gestern".  Schön wär's. Doch zurück in die Steinzeit.
Alle  in  einer Programmiersprache definierten Kontextbedingungen
faßt man unter dem Begriff der statischen Semantik zusammen.

Neben  der  Überprüfung  der  statischen Semantik leitet sich die
Aufgabenstellung  der  semantischen Analyse aus der Notwendigkeit
her, das Programm so aufzuarbeiten, daß die Codeerzeugung und die
Codeoptimierung   möglichst   effizient  arbeiten  können.  Diese
Aufarbeitung   besteht   in   der  Zuordnung  von  Attributen  zu
bestimmten Programmelementen. Solche Elemente können zum Beispiel
Bezeichner  oder  (Teil-)Ausdrücke  sein,  denen als Attribut der
jeweilige Typ zugeordnet wird.

Der   Vorteil   dieser  Attributierung  ist,  daß  die  benötigte
Information  direkt  präsent  ist  und  sich  nur  auf  einen eng
begrenzten   Kontext   der  jeweils  bearbeiteten  Programmstelle
beschränkt.   Dies   macht   die   Implementierung  der  Semantik
übersichtlicher und leicht verständlich.


Was geschieht in der semantischen Analyse?

Abbildung 1: Informationsfluß un der semantischen Analyse


  ───────            ─────────────            ───────────────
 ( Parser)─────────>( semantische )─────────>( Codeerzeugung )
  ───────           (   Analyse   )           ───────────────
                     ──┬───────┬──
                       │       │
                       │       │
                       │       │
                       │       │
                     ──┴───────┴─
                    (   Error    )
                    (            )
                    (  Handler   )
                     ────────────



Bei   Eintritt   in   die   sematische   Analysephase   gilt  die
Voraussetzung,  daß  der zu übersetzende Programmtext syntaktisch
korrekt  ist.  Wie  man  aus  Abbildung  1  erkennt, dient dieser
Analysephase  der  vom  Parser erzeugte Strukturbaum als Eingabe.
Wir  erinnern uns: Den Strukturbaum erhält man, indem man aus dem
Ableitungsbaum semantisch irrelevante Einzelheiten eliminiert. So
enthält  ein  Strukturbaum  keine  notationswichtigen Details wie
Klammern, Semikolons usw.

Die  inneren  Knoten  eines  Baumes  stellen  im wesentlichen die
Operatoren (+, -, `, :=, ...) von Ausdrücken und Anweisungen dar.
Die  Blätter  hingegen  sind  die  Operanden dieser Ausdrücke und
Zuweisungen.   Die  konkrete  Aufgabe  der  semantischen  Analyse
besteht  nun  darin,  diesen  Knoten  Attribute  zuzuordnen (Typ,
Grenzen  usw.)  und  deren  Attributwerte  zu bestimmen (Integer,
1..100  usw.).  Abhängig von der Signifikanz eines Knotens können
mehrere   Attribute  (Attributemengen)  oder  auch  nur  einzelne
Attribute zugeordnet werden. Wir wollen diese Attributzuordnungen
an einem einfachen Beispiel betrachten:

Gegeben sei das kurze und fehlerhafte Pascalprogramm:

PROGRAM Error;
VAR i, j: INTEGER;
       r: REAL
BEGIN
 i := j + r;
END.

Betrachten wir den Teilbaum des Strukturbaums in Abbildung 2, der
die Zuweisung i:=j+r enthält.

Abbildung 2: Strukturbaum der Zuweisung i:=j+r



              assign
                │
                │
        ┌───────┴──────────────────┐
        │                          │

        i                         addop
                                   │
                                   │
                       ┌───────────┴────────────┐
                       │                        │
                       │                        │

                       j                         r




Nun ordnen wir den Knoten i,j , r , assign und addop ein Attribut
mit dem Namen hasvalue zu, wie in Abbildung 3 dargestellt.


Abbildung 3: ...und der attributiere Strukturbaum


              assign (hashvalue = ?)
                │
                │
        ┌───────┴──────────────────┐
        │                          │

        i (hashvalue = ?)        addop (hashvalue = ?)
                                   │
                                   │
                       ┌───────────┴────────────┐
                       │                        │
                       │                        │

                       j  (hashvalue)           r (hashvalue)





Als nächstes bestimmen wir die Werte dieser Attribute:

     i,j  erhalten den Wert Integer ,
      r     erhält den Wert Real    ,


-addop    :
Laut  Pascalsemantik  ist  Addition  von  Integer  und  Real eine
erlaubte Operation. Der Ergebnistyp ist Real . addop erhält somit
den Attributwert Real zugewiesen.

- assign    :
Pascal  läßt  eine  Zuweisung  von  Real  (=  hasvalue(addop)) an
Integer nicht zu. Hier kommt es also zu einem Semantikfehler. Die
Fehlermeldung könnte etwa lauten: "Typeconflict of operands".

Den  so mit Attributen "geschmückten" Strukturbaum bezeichnet man
als   attributierten  Strukturbaum,  der  gleichzeitig  auch  die
Ausgabe  der semantischen Analysephase darstellt. Als Hilfsmittel
zur formalen Beschreibung dieser Umformung von einem Strukturbaum
in   einen   attributierten   Strukturbaum  werden  attributierte
baumerzeugende  Systeme  benutzt.  Hierbei werden Zuordnungen von
Attributmengen   zu   Knoten   abstrakter   Strukturbäume  formal
festgelegt  und  Rechenregeln zur Bestimmung der Werte sämtlicher
Attribute spezifiziert.

In  solchen Systemen unterscheidet man zwei Arten von Attributen:
Die  "inherited"  (erworbenen)  Attribute  und  die "synthesized"
(abgeleiteten) Attribute. Erworbene Attribute erlauben dabei eine
Berechnung  ihrer Attributwerte ohne eine weitere Betrachtung der
Umgebung   des   Strukturbaumknotens.   Dahingegen   lassen  sich
abgeleitete  Attribute  erst  nach  der Betrachtung der Söhne des
aktuellen  Knotens  berechnen. Weiterhin gilt für ein Attribut A,
daß  es  entweder  ein  erworbenes oder ein abgeleitetes Attribut
ist, aber nie beiden Attributklassen gleichzeitig angehören kann.

Die  gesamte  Attributmenge  einer  Programmiersprache setzt sich
also  aus  diesen  beiden  disjunkten Attributmengen zusammen. In
unserem  Beispiel zählen die Attribute der Bezeichner i , j und r
zu  der  Menge  der  erworbenen  Attribute, assign und addop sind
dahingegen  abgeleitete  Attribute.  Um eine möglichst effiziente
Berechnung   der  Attributwerte  durchführen  zu  können,  wurden
zahlreiche Durchlaufstrategien durch den Strukturbaum entwickelt,
deren  Behandlung  den Rahmen dieser Folge sprengen würde. Es sei
an  dieser  Stelle  auf  ein  Buch  von Waite und Goos, "Compiler
Constructions",  aus  dem  Springer-Verlag hingewiesen, das näher
auf diese Problematik eingeht.


Analyse der statischen Semantik

Wie  jeder  "Pascalist"  weiß,  muß  allen  angewandten Auftreten
(applied   occurrence)  eines  Bezeichners  im  Programmtext  ein
definierendes  Auftreten  (defining  occurrence) voranstehen. Das
definierende  Auftreten  eines  Bezeichners  legt bekanntlich die
Bedeutung  des Bezeichners in einem bestimmten Gültigkeitsbereich
(scope)  fest.  Ein  angewandtes  Auftreten  stellt  dabei  einen
entsprechenden  Bezug zu diesem Gültigkeitsbereich dar. Analog zu
jedem  Gültigkeitsbereich  existiert  in  einem Programm in jedem
Punkt  eine  eindeutig bestimmte aktuelle Umgebung (environment),
die  die  Menge  der  an  dieser  Stelle  sichtbaren Definitionen
bezeichnet.  Zu  den  Aufgabenbereichen  der semantischen Analyse
zählt  nun auch die Bestimmung der jeweiligen aktuellen Umgebung.
Dies schließt folgendes mit ein:

   - Sämtliche  Definitionen  eines Blocks (Gültigkeitsbereiches)
   müssen auf Eindeutigkeit und Konsistenz hin überprüft werden.

   - Zu  jeder Programmiersprache existieren implizite Attribute.
   In  Pascal gehören zum Beispiel die Attribute Integer , Real ,
   Boolean   usw.   dazu.   Da   hier  eine  Definition  vor  der
   entsprechenden  Anwendung  nicht  erforderlich ist, müssen für
   diesen  Regelteil  der  Programmiersprache implizite Attribute
   erzeugt werden.

   - Für  jede  Definition eines Bezeichners sind die zugehörigen
   Attributwerte  zu  bestimmen  und  für jeden Eintritt in einen
   neuen Block ist die Umgebung entsprechend zu modifizieren.

   -  Realisierung  von  Blockumgebungen  als  Datenstrukturen in
   sogenannten  Displayvektoren.  Der  Displayvektor  spiegelt an
   einer    beliebigen   Stelle   im   Programm   die   statische
   Blockumgebung  wieder.  Jedes  Element  dieses Vektors ist ein
   Zeiger  auf  den  Anfang  der  Bezeichnerdefinitionen in einem
   Block.  Wird  ein  neuer Block betreten, so wird der Index des
   Displayvektors   um   1   inkrementiert   und  auf  den  neuen
   Blockanfang  verwiesen.  Bei Austritt aus einem Block wird der
   Displayvektor  um  1  dekrementiert. Durch eine Rückverfolgung
   der  Blöcke  über  den  Displayvektor  lassen  sich somit sehr
   leicht  alle  im  betrachteten  Block  sichtbaren Definitionen
   ausfindig  machen.  Der  Index  dieses  Vektors  ist dabei die
   aktuelle   Block  schachtelungstiefe  (BST)  der  betrachteten
   Prozedur.  Der  Wert  der  BST  wird in der Codeerzeugung eine
   wichtige  Rolle spielen, wenn es darum geht, die Adresse einer
   Variablen zu bestimmen.


Eine beispielhafte semantische Programmanalyse

Program Minimum;
(*  "Minimum" ist der Bezeichner des Programms. Dieser Bezeichner
ist  im  übrigen  meist  auf einer anderen Ebene als auf der Pro-
grammebene  selbst  definiert,  so daß kein zweiter, globaler Be-
zeichner "Minimum" in den meisten Fällen keine Fehlermeldung her-
vorruft.  Der Programmname wird somit von den wenigsten Compilern
mit übersetzt.*)

var i,j :integer;
      r :real
      (*  Einführung neuer globaler Variablen "i","j" und "r" Be-
      nutzung der Standardbezeichner "Integer" und "Real".*)

Begin
      (*  In der nachfolgenden aktuellen Umgebung sind die impli-
      ziten  Bezeichner (Integer, Real, Boolean etc.) und die Be-
      zeichner "i", "j", "r" und eventuell "Minimum" definiert.*)


  i:= 100 * 10 + 1;
      (* korrekte Zuweisung  eines konstanten-Ausdrucks an eine
       Integer-Variable "1"*)


  r:= 2 * 4.25;
      (*  Die  Berechnung  von  2*4.25  ist korrekt, da an dieser
      Stelle Integer zu real kompatibel ist. Die Konstante 2 wird
      nach  2.0  konvertiert.  Der gesamte Ausdruck erhält so den
      Typ Real und kann anschließend an die Variable "r" zugewie-
      sen werden.*)

  j:= i < r;
      (*  Vergleich:  Die  Integerzahl  "i" wird in eine Realzahl
      umgewandelt.  Der  Vergleich  "i < R" ist dann zulässig und
      erhält  den Wert "boolean". Eine Zuweisung an eine Integer-
      zahl  hingegen  ist inkompatibel mit der Definition von "j"
      da  der Ausdruck "i < r" einen Attributwert vom Typ "boole-
      an" hat und eine Zuweisung an eine Integerzahl laut Pascal-
      semantik nicht gestattet ist *)

End.
     (*  Ende der aktuellen Umgebung - und hier auch des gesamten
     Programms*)




In  der  semantischen  Analyse wird also zu jeder Anwendung eines
Bezeichners  in  der aktuellen Umgebung die zugehörige Definition
bestimmt. Die Anwendung muß dabei immer kompatibel mit der in der
Definition festgelegten Bedeutung des Bezeichners sein. Eine der-
artige  Überprüfung bedingt dabei allerdings, daß auch für nicht-
elementare Teilstrukturen des Programms Attributwert zu bestimmen
sind .


Operatoridentifikaton

Zum  Schluß  der  Analyse der statischen Semantik wollen wir noch
kurz   auf   das  Problem  der  Operatoridentifikation  eingehen.
Operatoren wie +, *, -, / etc. können in Programmiersprachen über
laden   (overloaded)   sein.   Genauer  wird  das  folgendermaßen
definiert:

Ein  Operator  in  einer  typisierten  Sprache wird als überladen
bezeichnet,  wenn  verschiedene  Bedeutungen  für diesen Operator
existieren  und  die  geeignete  Bedeutung  nur  aus  dem Typ der
Operanden bestimmt werden kann.

Ein  überladener  Operator  repräsentiert  dann  nicht  nur  eine
einzelne  Funktion,  sondern  eine  ganze  Klasse von Funktionen.
Dieses  Konzept wurde bereits in früheren Programmiersprachen wie
ALGOL60    oder    PL=1    gebraucht    und   ist   in   modernen
Programmiersprachen wie ADA sehr stark ausgebaut worden.

Auch  in  Pascal, wie könnte es auch anders sein, sind Operatoren
zum  größten  Teil überladen. Die Aufgabe der Operatoridentifika-
tion  besteht nun darin, für jedes Auftreten eines Operators eine
passende  Funktion  auszuwählen.  Die Wahl ist dabei abhängig vom
Typ  der  Operanden,  dem Kontext der Operanden und natürlich dem
Operator  selbst. Am Beispiel des Pascal "*"-Operators (Multipli-
kation) sei dies in Abbildung 4 verdeutlicht.


Implementierung der semantischen Analyse

Bei  dem Vorhaben für unseren Compiler eine geeignete Analysphase
zu  schreiben,  kommt  uns  die gewählte Konstruktion des Parsers
zugute.  Wir erinnern uns: Als Parser-Implementierung wählten wir
das Konzept des "recursive descent" Parsers, bei dem jedem Nicht-
terminal der Zerteilergrammatik eine Prozedur der Implementierung
entsprach.  Der  Aufbau  des  Strukturbaumes entsprach einem Lauf
durch die entsprechenden Teile der Zerteilergrammatik.

Um  nun  den  Strukturbaum mit Attributen zu schmücken, reicht es
aus,  in  jeder Prozedur, die einem Nichtterminal entspricht, Va-
riablen  für die benötigten Attribute zu definieren und deren At-
tributwerte  zu berechnen. Erworbene Attribute werden hierbei als
"call  by  value"-Parameter,  abgeleitete  Attribute als "call by
reference"-Parameter  an die aufzurufende Prozedur mit übergeben.
Unser  Parser braucht dann insgesamt nur noch an den entsprechen-
den  Stellen  mit  Attributvariablen erweitert zu werden. Die Be-
rechnung  der Attributwerte kann dann parallel mit dem Parserlauf
erledigt werden.

So,  das  war's für diesmal. In der nächsten Folge werden wir uns
mit  dem  Problem  der  Code-Erzeugung  für  die  Zwischensprache
beschäftigen.  Mit der Veröffentlichung der nächsten Ausgabe wird
dann  auch  der  gesamte Compiler mit Interpreter und Quelltexten
aus  der  DATA-Box  zu  haben  sein,  um alles bis dahin Gelernte
"life" mitzuerleben.



  Typ A │   Typ B │     Funktion des Operators
────────┼─────────┼─────────────────────────────────────────────
integer │ integer │ Integermultiplikation. Ergebnistyp : integer
integer │ real    │ Realmultiplikation. Ergebnistyp : real
   real │ integer │ Realmultiplikation. Ergebnistyp : real
   real │ real    │ Realmultiplikation. Ergebnistyp : real
set of T│ set of T│ Mengendurchschnitt. Ergebnistyp : set of T


Abb.  4: Überladung (overloading) des Multiplikationsoperators in
Pascal




Kurzreferenz Folge 2, 3, 4:

- Quellsprache: irgendeine Programmiersprache

-  Zielsprache: im allegemeinen die Maschinensprache eines Compu-
ters

-  Compiler:  übersetzt Anweisungen der Quellsprache in gleichbe-
deutende Anweisungen der Zielsprache

- Pass: Zyklus in der Verarbeitung einer Datei (Eingabe -> Verar-
beitung -> Ausgabe)

-  Nicht-Terminale:  Programmgefüge  wie  Prozeduren, Funktionen,
Anweisungsfolgen etc.,

-  Terminale:  Worte  (Bezeichner,  Schlüsselwörter etc.), die im
eigentlichen  Programm  vorkommen und Prozeduren, Funktionen etc.
bilden

- Grammatik, Syntax: Beschreibt Umfang und Stuktur einer Sprache

- Semantik: die Bedeutung von Sprachstukturen

- BNF: Backus-Naur Form. Darstellungsform von Grammatiken

-  Produktionen:  Ersetzungsregeln, nach den der Syntax genügende
"Sätze" einer Sprache erzeugt werden

- Grundsymbol: Bezeichner (Namen von Variablen, Prozeduren etc.),
Literale  (Zeichenketten  wie  "was nun?)", Schlüsselwörter (z.B.
"begin", "end"), Seperatoren (Semikolon, Leerzeichen,...)

-  Symbol-Token:  Abbildung eines Grundsymbols auf eine speicher-
platzsparende  und schnelleren Zugriff gewährende Form zur weite-
ren Verarbeitung

-  Symbol-Klassen: Bezeichner, ganze Zahlen, Zeichen, Anfangssym-
bol, Endsymbol usw.

-  Symbol-Merkmal: identifiziert die Symbole einer Symbol-Klasse,
z.B. der Wert einer ganzen Zahl

-  Symbol-Tabelle: nimmt aus dem Quelltext gelesenen Grundsymbole
(Bezeichner, Schlüsselwörter) mit ihren Merkmalen auf

-  lexikalische  Analyse:  überprüfung, ob die Bestandteile einer
Anweisung  der  Sprachdefinition entsprechen und ob keine undefi-
nierten Zeichen enthalten sind

-  Scanner: Dient zur Erkennung der Grundsymbole und deren Abbil-
dung  auf eine Symbolfolge (Tokenfolge), führt außerdem die lexi-
kalische Analyse durch

-  syntaktische Analyse: überprüfung, ob eine Folge von Grundsym-
bolen der Syntax (Grammatik) einer Sprache entspricht

-  Parser (Zerteiler): seine Aufgabe ist die syntaktische Analyse
der "Sätze" einer Sprache und die Fehlerbehandlung, wenn der Syn-
tax nicht entsprochen wird. Dabei wird ein "Stukturbaum" erzeugt,
der der semantischen Analyse unter worfen wird

-  Keller  (engl. "stack"): eine Datenstruktur, die nach dem "LI-
FO"-Prinzip  arbeitet  ("Last  In,  First Out"). Vergleichbar mit
einem Stapel Blätter, von dem nur das oberste Blatt genommen bzw.
ein neues Blatt nur zuoberst abgelegt werden kann

-  Kellerautomat:  Ein  möglicher Ansatz zur einfachen Lösung der
Syntaxanalyse

- Zerteilungsverfahren: es gibt verschiedene Verfahren zur Reali-
sierung von Parsern:
    - zielbezogene Zerteilung ("top-down"-Analyse): hier wird der
Stukturbaum von der Wurzel zu den Blättern (Ziel) hin erzeugt )

    -  quellbezogene  Zerteilung  ("bottom-up"-Analyse): Der Baum
wird  von  den  Blättern  zur  Wurzel (Quelle) verfolgt. Dies ist
mächtiger als die "top-down"-Analyse, aber auch komplizierter