Namensliste

Die nachfolgenden Betrachtungen beziehen sich größtenteils auf den im Rahmen der Lehrveranstaltung zu entwickelnden Modellkompiler. 

Von zentraler Bedeutung ist die Namensliste für die semantische Analyse, aber auch für die Codegenerierung. In ihr sind alle Bezeichner enthalten, die zum aktuellen Zeitpunkt der Übersetzung gültig sind. Man nennt sie auch Symboltabelle. Sie enthält sowohl die Bezeichner, als auch Beschreibungen der bezeichneten Sprachelemente (Prozeduren, Variablen, Konstanten).

Da PL/0 nicht über Datentypen verfügt, gestalten sich die Beschreibungen für Konstanten, Variablen und Prozeduren recht einfach. Alle Beschreibungen enthalten als erstes ein Kennzeichen, das eigentlich redundant ist, sich aber bei umfangreicheren Compilern bewährt hat.

Folgende Operationen sind für Namenslisten zu implementieren:

• einfügen eines Bezeichners in die aktuelle Namensliste

• lokale Suche eines Bezeichners in der aktuellen Namensliste

• globale Suche eines Bezeichners „von innen nach außen“

Variablenbeschreibung:

typedef struct tVAR
{
 tKz Kz;	/* Kennzeichen */
 int Dspl;	/* Relativadresse der Variablen */
}tVar;

Zur Laufzeit werden die Variablen durch die virtuelle Maschine im Keller (run time stack) bei Aufruf der umgebenden Prozedur angelegt. Die Variablenbeschreibung zur Übersetzungszeit enthält nun die Relativadresse der Variable, die sie zur Laufzeit im Variablenbereich der Prozedur im Keller, relativ zu dessen Anfang belegen wird. Sie beginnt mit 0 und wird bei jeder weiteren Variable innerhalb der Prozedurvereinabrung um 4 erhöht, da jede Variable 4 Byte im Speicher belegt. Da die Variablenvereinbarungen einer Prozedur immer zusammenhängend in einer Variablenvereinbarungsliste angeordnet sind, kann als Speicherplatzzuordnungszähler eine statische Variable dienen, die am Anfang der Variablenvereinbarungsliste oder am Prozeduranfang auf null gesetzt wird.
Bei komplexeren Programmiersprachen kommen weitere Angaben zu Länge und zu Typ der Variablen hinzu.

Konstantenbeschreibung:

typedef struct tCONST
{
  tKz  Kz;		/* Kennzeichen */
  long Val;		/* Wert der Konstanten*/
  int  Idx;		/* Index im Konstantenblock */
}tConst;

Alle Konstanten eines PL0-Programms werden in einem Konstantenblock „gesammelt“. Jede Konstante soll nur einmal enthalten sein, auch wenn sie mehrfach im Quelltext auftritt. Im zu generierenden Code, der durch die virtuelle Maschine ausgeführt wird, wird die Konstante dann über den Index der Konstanten erreicht. Der gesamte Konstantenblock wird im Zwischencodefile hinter dem Code der letzten Prozedur (Hauptprogramm) abgelegt.
Natürlich sind auch andere Varianten denkbar. So könnten Konstanten auch als Literal direkt in Befehle eingefügt werden. Das hieße aber, dass die Konstante mehrfach im übersetzten Text existiert.

Prozedurbeschreibung:

typedef struct tPROC
{
  tKz    Kz;            /* Kennzeichen */
  short  IdxProc;       /* Prozedurindex */
  struct tPROC*pParent; /* Zeiger auf umgebende Prozedur */
  tList *pLBez;         /* Namensliste     */
  int    spzzVar	/* Speicherplatzzuordnungszähler Variable */
}tProc;

Die Prozedurbeschreibung enthält alle Informationen, die zur Übersetzung und zum Aufruf der Prozedur notwendig sind. Die Prozedurnummer ist von zentraler Bedeutung. Während der Übersetzung werden die Prozeduren gezählt somit bekommt jede Prozedur eine laufende Nummer, die ihrer Identifikation während der Übersetzung, aber auch zur Laufzeit dient. Das Hauptprogramm erhält die Prozedurnummer 0.

Da eine Prozedur weitere Prozeduren in beliebiger Schachtelungstiefe enthalten kann, und sich daraus Gültigkeitsbeziehungen bezüglich der Bezeichner ergeben, muss jeweils ein Bezug zur umgebenden Prozedur existieren (pParent). Der Bezeichner einer Prozedur wird jeweils in der Namensliste der umgebenden Prozedur geführt.
Schließlich enthält die Prozedurbeschreibung noch die Namensliste für alle Bezeichner, die in der Prozedur vereinbart sind. Sie wird als verkettete Liste implementiert.

Element der Namensliste:

typedef struct tBEZ
{
  tKz   Kz;             /* Kennzeichen */
  short IdxProc;        /* Prozedurindex */
  void* pObj;           /* Zeiger auf Beschreibung */
  char* pName;          /* Bezeichner */
}tBez;

Ein Namenslistenelement enthält den Bezeichner und einen Verweis auf die Beschreibung des benannten programmiersprachlichen Elements (Prozedurbeschreibung, Variablenbeschreibung, Konstantenbeschreibung). Außerdem wurde die Prozedurnummer mit in den Bezeichner aufgenommen. Sie ist redundant aber recht praktisch, da man bei jedem Bezeichner nach einer Suche weiß, zu welcher Prozedur er gehört.

Man kann nun zu jeder Prozedur eine lokale Namensliste aufbauen, die alle Bezeichner verwaltet, die innerhalb der Prozedur vereinbart wurden. Das Ergebnis wäre ein Baum, der sämtliche Bezeichner des Programms enthält. Da aber die Bezeichner, die innerhalb einer Prozedur verwandt wurden nach ihrer vollständigen Übersetzung nicht mehr benötigt werden, können diese wieder freigegeben werden. Auf diese Weise enthalten die Namenslisten immer nur die zu einem bestimmten Zeitpunkt gültigen Bezeichner.

Namensliste als pulsierender Keller

Eine andere Variante besteht in der Implementation der Namensliste als pulsierenden Keller. Dieser Keller wird dann sequenziell nach einem Namen durchsucht. Bei der lokalen Suche muss dabei am Ende begonnen und abgebrochen werden, wenn man bei dem Routinenamen angekommen ist, der Routinename ist der erste Bezeichner, der dann nicht mehr zur lokalen Namensliste der aktuellen Prozedur gehört. Der Zeiger pParent aus der Prozedurbeschreibung kann hier entfallen.