Compilerbau/Kapitel 3: Semantische Analyse

Aus Halloserv Wiki

Inhaltsverzeichnis

1 Attribuierte Grammatiken
- 1.1 Notationen
- 1.2 Berechnung einer Dekoration
  - 1.2.1 L-attribuierte Grammatiken
  - 1.2.2 S-attribuierte Grammatiken
2 statische semantische Eigenschaften
- 2.1 Gültigkeit und Sichtbarkeit von Bezeichnern (Scoping)
- 2.2 Auflösung der Überladung
  - 2.2.1 Algorithmus zur Auflösung von Überladungen in Ada
3 Scanner und Parser verbinden
4 abstrakte Syntax

Attribuierte Grammatiken

Ein Parser der nur als Erkenner fungiert ist nicht ausreichend für einen Compiler - seine Ausgabe verrät nichts über die Natur der geparsten Eingabe, nur ob sie zu der durch die unterliegenden Grammatik definierten Sprache gehört. Für einen Compiler muss ein Parser den Syntaxbaum, den er intern generiert hat, bereitstellen. Daher führt dieser Abschnitt eine erweiterte Notation der kontextfreien Grammatik ein: die attribuierte Grammatik. Eine attribuierte Grammatik verbindet zusätzliche Werte (die Attributsinstanzen) mit den Knoten eines Syntaxbaum und stellt Regeln bereit, die diese zu einander in Beziehung setzen. Ein Parser in einem Compiler berechnet die Werte der Attributsinstanzen und gibt diese zum Aufrufer zurück.

Attribuierte Grammatiken besitzen eine beträchtliche Menge an verwirrenden Formalismen. Einige Beispiele sollen die zentrale Idee verdeutlichen.

Wir betrachten eine Grammatik für konstante arithmetische Ausrücke. Aus technischen Gründen hat nur eine Zahl ein Literal: 42. Eine attribuierte Grammatik kann nun beschreiben wie man tatsächlich den Wert eines solchen Ausdrucks berechnet.

Beispiel: attribuierte Grammatik

$\begin{array}{lclcl} \langle exp \rangle & ::= & \langle term\rangle & & \langle exp\rangle .v = \langle term\rangle .v \\ & | & \langle term\rangle + \langle exp\rangle & & \langle exp\rangle_{LHS} .v = \langle term\rangle .v + \langle exp\rangle_{RHS} .v \\ & | & \langle term\rangle - \langle exp\rangle & & \langle exp\rangle_{LHS} .v = \langle term\rangle .v - \langle exp\rangle_{RHS} .v \\ \\ \langle term\rangle & ::= & \langle prod\rangle & & \langle term\rangle .v = \langle prod\rangle .v \\ & | & \langle prod\rangle * \langle term\rangle & & \langle term\rangle_{LHS} .v = \langle prod\rangle .v \cdot \langle term\rangle_{RHS} .v \\ & | & \langle prod\rangle / \langle term\rangle & & \langle term\rangle_{LHS} .v = \langle prod\rangle .v / \langle term\rangle_{RHS} .v \\ \\ \langle prod\rangle & ::= & 42 & & \langle prod\rangle .v = 42 \\ & | & (\langle exp\rangle ) & & \langle prod\rangle .v = \langle exp\rangle .v \\ \end{array}$

Beispiel: attribuierte Grammatik

$\begin{array}{lclcl} \langle bit\rangle & ::= & 0 & & \langle bit\rangle .v = 0 \\ & | & 1 & & \langle bit\rangle .v = 2^{\langle bit\rangle .s} \\ \\ \langle bits\rangle & ::= & \langle bit\rangle & & \langle bits\rangle .v = \langle bit\rangle .v \\ & & & & \langle bit\rangle .s = \langle bits\rangle .s \\ & & & & \langle bits\rangle .l = 1 \\ & | & \langle bits\rangle \langle bit\rangle & & \langle bits\rangle_{LHS} .v = \langle bits\rangle_{RHS} .v + \langle bit\rangle .v \\ & & & & \langle bit\rangle .s = \langle bits\rangle_{LHS} .s \\ & & & & \langle bits\rangle_{RHS} .s = \langle bits\rangle_{LHS} .s + 1 \\ & & & & \langle bits\rangle_{LHS} .l = \langle bits\rangle_{RHS} .l + 1 \\ \\ \langle num\rangle & ::= & \langle bits\rangle & & \langle num\rangle .v = \langle bits\rangle .v \\ & & & & \langle bits\rangle .s = 0 \\ & | & \langle bits\rangle . \langle bits\rangle & & \langle num\rangle .v = \langle bits\rangle_{RHS_1} .v + \langle bits\rangle_{RHS_2} .v \\ & & & & \langle bits\rangle_{RHS_1} .s = 0 \\ & & & & \langle bits\rangle_{RHS_2} .s = -\langle bits\rangle_{RHS_2} .l \\ \end{array}$

Notationen

Definition: Position

Eine Position identifiziert das Vorkommen eines Grammatiksymbols in einer Produktion. Das Symbol wird durch ein $\circ$ direkt davor identifiziert. Folglich identifiziert $\langle \circ A \rightarrow \alpha \rangle$ die linke Seite A und $\langle A \rightarrow \alpha \circ X \beta \rangle$ das X.

Definition: attribuierte Grammatik

Sei Att eine Menge von Attributen. Eine attribuierte Grammatik ist ein Tupel $(G,Syn,Inh,\mathcal{R},\mathcal{D})$ mit

$G = (N, T, P, S)$ als kontextfreie Grammatik,
$Syn: N \rightarrow \mathcal{P}(Att)$ spezifiziert für jedes Nichtterminal $A$ die Menge $S y n (A)$ der synthetisierten Attribute. Ein Attribut ist ein synthetisiertes Attribut wenn sein Wert an einem Knoten des Ableitungsbaums aus Attributwerten der Kinder des Knotens berechnet werden kann.
$Inh: N \rightarrow \mathcal{P}(Att)$ definiert für jedes Nichtterminal $A$ die Menge $I n h (A)$ der geerbten Attribut. Ein Attribut ist ein geerbtes Attribut wenn sein Wert an einem Knoten des Ableitungsbaums durch die Attribute seiner Eltern- oder Geschwisterknoten definiert werden kann.
$\mathcal{R}$ ist eine Familie von Attribuierungsregeln
$\mathcal{D} = ({\mathcal{D}}^{a})_{a \in Att}$ ist eine Familie von Attribut-Domänen sodass $\mathcal{D}^\mathrm{a}$ eine Menge von möglichen Werten für ein Attribut $a$ ist.

Für jedes $A$ gilt: $Syn(\mathrm{A}) \cap Inh(\mathrm{A}) = \emptyset$ und $Att(\mathrm{A}) := Inh(\mathrm{A}) \cup Syn(\mathrm{A})$ ist die Menge der Attribute von A.

Ein Attributvorkommen ist ein Paar $p . a$ das aus der Position innerhalb einer Produktion und einem Attribut besteht. Attributvorkommen muss entweder die Form $\langle \circ \mathrm{A} \rightarrow \alpha \rangle .a$ mit $a \in Att(\mathrm{A})$ oder $\langle A \rightarrow \gamma \circ \mathrm{B} \delta \rangle .a$ mit $a \in Att(\mathrm{B})$ haben.

Die Vorkommen einer Produktion fallen in 2 Klassen: Die definierenden Vorkommen $Def(\mathrm{A} \rightarrow \alpha)$ und die angewandten Vorkommen $App(\mathrm{A} \rightarrow \alpha)$ .

$Def(A \rightarrow \alpha) := \{ \langle \circ A \rightarrow \alpha \rangle .a | a \in Syn(A) \} \cup \{ \langle A \rightarrow \gamma \circ B \delta \rangle .a | \alpha = \gamma B \delta \wedge a \in Inh(B) \}$
$App(A \rightarrow \alpha):= \{ \langle \circ A \rightarrow \alpha \rangle .a | a \in Inh(A) \} \cup \{ \langle A \rightarrow \gamma \circ B \delta \rangle .a | \alpha = \gamma B \delta \wedge a \in Syn(B) \}$

Jedes definierende Vorkommen $p.a \in Def(A \rightarrow \alpha)$ hat eine damit verbundene Attribuierungsregel

$p.a = f_{p.a}(p_{1}.a_{1}, \ldots , p_{m}.a_{m})$

wobei $m$ irgendeine natürliche Zahl darstellt die mit $p . a$ verbunden ist und alle $p_{m}.a_{m} \in App(A \rightarrow \alpha)$ angewandte Attributvorkommen für die selbe Produktion sind. $f p . a$ muss eine Funktion ${\mathcal{D}}^{a_1} \times \ldots \times {\mathcal{D}}^{a_m} \rightarrow {\mathcal{D}}^{a}$ sein. $\mathcal{R}$ ist eine Familie aller solcher Attribuierungsregeln die durch die definierenden Attributsvorkommen indexiert werden.

Die Attributabhängigkeiten einer Grammatik sind nach der obrigen Definition in der Bochmann Normal Form: Vererbte Attribute hängen nur von "über" ihnen im Syntaxbaum ab, synthetisierte nur von denen "unter" ihnen. Eine attribuierte Grammatik verleiht einem Ableitungsbaum durch Vorschriften für seiner Knotenbeschriftung eine Bedeutung.

Datei:3-Example-Arithmectic-Gramm.png

Bild 3.1: Eine Attribuierung durch eine Grammatik

Definition: Ableitungsbaum

Ein Ableitungsbaum für eine kontextfreie Grammatik $(N, T, P, S)$ ist ein endlicher, geordneter und gerichteter Baum mit einer Menge Knoten $V$ sodass jeder Knoten mit einer Produktion beschriftet ist. Weiterhin

Wenn der Knoten $v 0$ mit $A_{0} \rightarrow A_{1} \ldots A_{n}$ beschriftet ist muss $v 0$ genau $n$ Nachfolger $v_1, \ldots, v_n$ haben sodass $v i$ mit $A_i \rightarrow \alpha_i$ beschriftet ist.
in einem vollen Ableitungsbaum ist der Wurzelknoten mit der Start-Produktion $S \rightarrow \alpha$ beschriftet.

Definition: Attributsdekoration

Eine Attributsdekoration verbindet mit jedem Knoten $v$ eines Ableitungsbaum, der mit einer Produktion $A \rightarrow \alpha$ beschriftet ist, eine Attributsinstanz $v.a \in \mathcal{D}^a$ für jedes $a \in Att(A)$ . Eine Attributsdekoration ist gültig wenn für jeden Knoten $v 0$ , der mit $A_0 \rightarrow A_1 \ldots A_n$ beschriftet ist und $v_1, \ldots, v_n$ als Nachfolger besitzt und für jedes definierende Vorkommen $p_{0}.a \in Def(A_0 \rightarrow A_1 \ldots A_n)$ mit einer verbundenen Attribuierungsregel

$p_{0}.a = f_{p_{0}.a}(p_{1}.a_{1}, \ldots,p_{m}.a_{m} )$

gilt das

$v_{i_0}.a = f_{p_{0}.a}(v_{i_1}.a_{1}, \ldots,v_{i_m}.a_{m} )$

wobei die Position $p j$ nicht-terminale Vorkommen von $A_{i_j}$ und damit Knoten $v_{i_j}$ identifiziert.

Bemerkung: Eindeutigkeit einer Attributsdekoration

Eine Attributsdekoration muss nicht eindeutig sein.

Beispiel:

$\begin{array}{lcllcl} A & \rightarrow & B & & B.i & = f(B.s) \\ B & \rightarrow & \epsilon & & B.s_{\epsilon} & = g(B.i) \\ \end{array}$

$I n h (B) = {i}$

$S y n (B) = {s}$

Falls $f (x) = g (x) = x + 1$ , dann exisitiert keine Attributsdekoration.

Falls $f (x) = x + 1, g (x) = x - 1$ , dann exisitieren unendlich viele Attributsdekorationen.

Dies ist auch ein Beispiel für eine zirkuläre attribuierte Grammatik.

Einschub (nicht im Mitschrieb):

Daher definiert eine attribuierte Grammatik $G$ mit der Startproduktion $S \rightarrow A$ eine meaning function $\mathcal{M}:\mathcal{T}^{*} \times {\mathcal{D}}^{Inh(A)} \rightarrow {\mathcal{D}}^{Syn(S)}$ . Für $\xi \in \mathcal{L}(G)$ initialisiert $\mathcal{M}(\xi,v_{1}, \ldots,v_{|Inh(A)|})$ den Ableitungsbaum mit Attributsinstanzen für die geerbten Attribute von $A$ und erzeugt Instanzen der synthetisierten Attribute von $S$ die aus der Dekoration des Ableitungsbaums stammen.

Ende Einschub

Definition: Zirkularität einer attribuierten Grammatik

Eine attribuierte Grammatik ist zirkulär falls es einen Ableitungsbaum $t$ gibt sodass der Graph $D t (t)$ zirkulär ist. Dabei ist $D t (t) = (V, E)$ mit

$V$ ist die Menge der Attributsinstanzen
$E$ enthält $v_{i_j}.a_{j} \rightarrow v_{i_0}.a_0$ ,falls $v_{i_0}.a_0 = f_{p.a_0}(\ldots).$

Autoren-Anmerkung(Firefox): Offensichtlich muss hier statt den $\ldots$ in $f_{p.a_0}$ irgendein Bezug auf $v_{i_j}.a_{j}$ vorhanden sein. Intuitiv gibt es eine Kante von jedem Vorkommen rechts des Gleichheitszeichens auf das Vorkommen links des Gleichheitszeichens wenn beide das gleiche Nichtterminal haben. Genauere Definitionen werden ergänzt.

Das Testen einer attribuierten Grammatik auf Zirkularität ist exponentiell !

Berechnung einer Dekoration

Es gibt viele Techniken die tatsächlich solch eine Dekoration eines Ableitungsbaum produzieren, manche von ihnen sind auch sehr gut. Es ist jedoch augenscheinlich wünschenswert die Dekoration während des Parsens zu generieren. Da die Bedeutungsfunktion nur an den Attributsinstanzen der Startproduktion interessiert ist und der Ableitungsbaum selbst kein Teil davon ist, könnte das Generieren der Dekoration während des Parsens das Speichern des Baums vermeiden. Leider benötigen manche generelle attribuierte Grammatiken den ganzen Baum um Attribute zu evaluieren; die Attribuierungsregeln könnten außerdem Zirkularitäten generieren.
Deshalb ist es notwendig die Klasse der attribuierten Grammatiken so zu beschränken das sie für on-the-fly Attributsevaluation zugänglich werden. 2 separate Wege geeignete Restriktionen für attribuierte Grammatiken zu formulieren sind L-attribuierte und S-attribuierte Grammatiken.

L-attribuierte Grammatiken

Definition: L-attribuierte Grammatik

Eine L-attribuierte Grammatik ist eine attribuierte Grammatik bei der für jede Regel

$d = f_d(a_1 \ldots a_{i_d})$

mit $d$ von der Form $\langle A \rightarrow \alpha \circ B \beta \rangle .a$ (mit $a \in Inh(B)$ )gilt, das jedes $a j$ entweder die Form $\langle \circ A \rightarrow \alpha B \beta \rangle .a$ (mit $a \in Inh(A)$ ) oder $\langle A \rightarrow \gamma \circ \mathcal{C} \delta B \beta \rangle .a$ (mit $\gamma \mathcal{C} \delta = \alpha$ und $a \in Syn(\mathcal{C})$ ) besitzt. Regeln mit einem $d$ der Form $\langle \circ A \rightarrow \alpha \rangle .a$ haben keine Beschränkungen.

In einer L-attribuierten Grammatik dürfen alle Attributvorkommen nur von ihrem Auftreten auf der linken Seite abhängen (daher auch L-attribuiert). Weil ein rekursiv-absteigender Parser von links nach rechts durch die Grammatikregeln geht, bieten sich L-attribuierte Grammatiken für on-the-fly Attributevaluation durch rekursiv-absteigende Parser an.

Beispiel: L-attribuierte Grammatik

Betrachten sie ein Fragment eines rekursiv-absteigenden Parsers für die Grammatikregel $A \rightarrow A_1 \ldots A_m$ . Die Parserfunktion für $A$ nimmt die Eingabefolge und die vererbten Attribute von $A$ als Parameter und gibt die verbleibende Folge und die synthetisierten Attribute von A als Resultat zurück. Zur Vereinfachung nehmen wir an das es nur ein einziges synthetisiertes Attribute $s$ und ein vererbtes Attribute $i$ gibt.

$\begin{array}{lcl} [A] & : & {\mathcal{T}}^{*} \times Inh(A) \rightarrow {\mathcal{T}}^{*} \times Syn(A) \\ \left [ A \right ] (\xi ,inh) & = & \bold{let} \ {inh}_{1} = {f}_{\langle A \rightarrow \circ A_1 \ldots A_m \rangle .i}(inh)\ \bold{in} \\ & & \bold{let} \ ({\xi}_1,{syn}_1) = [A_1](\xi ,{inh}_1)\ \bold{in} \\ & & \bold{let} \ {inh}_2 = f_{\langle A \rightarrow A_1 \circ A_2 \ldots A_m \rangle .i}(inh, {syn}_1)\ \bold{in} \\ & & \vdots \\ & & \bold{let} \ ({\xi}_m , {syn}_m) = \left [ A_m \right ] ({\xi}_{m-1} , {inh}_m) \ \bold{in} \\ & & \bold{let} \ syn = f_{\langle \circ A \rightarrow A_1 \ldots A_m \rangle .s}(inh , {syn}_1 , \ldots , {syn}_m) \ \bold {in} \\ & & ({\xi}_m , syn) \end{array}$

S-attribuierte Grammatiken

Trotz alledem stellen L-attribuierte Grammatiken ein Problem für rekursiv-absteigende Parser dar: Während des Laufs eines rekursiv-absteigenden Parsers muss sich dieser mehrere verschiedene Produktion "merken", von denen jede komplett verschiedene Attribuierungsregeln besitzen kann. Er würde daher alle diese Regeln parallel auswerten müssen - und dadurch viel überflüssige Arbeit erledigen. Allerdings beschränken rekrusiv-aufsteigende Parser die Klasse der attribuierten Grammatiken die sie akzeptieren normalerweise noch weiter: Sie erlauben einfach keine vererbten Attribute.

Definition: S-attribuierte Grammatik

Eine S-attribuierte Grammatik ist eine attribuierte Grammatik $\mathcal{G,S,I,R,D}$ mit $Inh(A) = \emptyset$ für alle $A \in N$

S-attribuierte Grammatiken werden auch von Parser-Generatoren wie z.B. yacc verwendet. Bei einer S-attribuierte Grammatiken verläuft die Attributevaluation von unten nach oben im Ableitungsbaum: Es können keine Zirkularitäten auftreten da alle Abhängigkeiten in die gleiche Richtung zeigen. Aus diesem Grund ist es ausreichend nur ein synthetisiertes Attribut pro Nichtterminal zu haben - verschiedene Attribute können einfach durch Zusammenfassungen wie Rekords simuliert werden. Daher nehmen wir im Rest dieser Sektion an, das $S y n (A) = {v}$ für alle $A \in N$ gilt. Außerdem besitzt der vereinfachten Darstellung wegen $f_{\langle A \rightarrow \alpha \rangle .v}$ immer $| α |$ Argumente. Terminalzeichen geben einfach irgendeinen reservierten Wert $\bot$ , der sonst nicht benutzt wird, als ihr Attribut zurück.

Beispiel: Erweiterung des LR-Parsers um die Auswertung von S-attribuierten Grammatiken

$\begin{array}{lll} \bold{parse}(qstk,vstk,w) & = & \\ & \bold{let} \ q & = top (qstk) \ \bold{in} \\ & & shift \ a \ v \ qstk \ vstk \ w' \ \ falls \ w = a w' \\ & & \ldots \end{array}$

Autoren-Anmerkung(Firefox): Dieses Beispiel ist zu komplex und muss für bessere Verständlichkeit überarbeitet werden. Interessierte finden es auf S61 des Vorlesungsskripts (Chapter 3: Semantic Analysis) von Prof. Thiemanns Vorlesung

statische semantische Eigenschaften

(vgl. Kapitel 8 in Wilhelm / Maurer)

Werte, die zu jedem Programmpunkt (Knoten im AST) aus dem Programmtext berechnet werden können.
Wert beschreibt alle während eines Programmlaufs an diesem Programmpunkt eintretenden Werte und Konfigurationen.

Beispiel: Beispiele für Werte

Typ eines Ausdrucks
Wertebereich eines Ausdrucks (z.B. ob Array-Zugriff OK ist)
Exakter Wert eines Ausdrucks (falls nicht möglich: $\top$ )
falls der Wert ein Dateihandle ist: ist die Datei offen oder geschlossen ?

Beispiel: Typberechnung für binäre arithmetische Operatoren

Es gibt in unserem Beispiel die Typen INT und REAL.

$\begin{array}{clll} \bold{ bin. \ Operator } & \bold{ 1. Operand } & \bold{ 2. Operand } & \bold{ Ergebnis } \\ +,-,* & INT & INT & INT \\ +,-,* & REAL & INT \vee REAL & REAL \\ +,-,* & INT \vee REAL & REAL & REAL \\ / & INT \vee REAL & INT \vee REAL & REAL \\ \% & INT & INT & INT \\ \end{array}$

Abstrakte Syntax: $e ::= i|r|e \odot e$

Typen gegeben durch S-attribuierte Grammatik

$\begin{array}{lcll} \langle \circ e \rightarrow i \rangle .typ & = & INT & \\ \langle \circ e \rightarrow r \rangle .typ & = & REAL & \\ \langle \circ e \rightarrow e \odot e \rangle .typ & = & \bold{let} \ t_1 & = \langle e \rightarrow \circ e \odot e \rangle .typ \ \bold{in} \\ & & \bold{let} \ t_2 & = \langle e \rightarrow e \odot \circ e \rangle .typ \ \bold{in} \\ & & & \bold{if} \ \exists \ Eintrag \ t \ fuer \ t_1 \odot t_2 \ in \ Tabelle \\ & & & \bold{then} \ t \\ & & & \bold{else} \ Fehler \ symbolisieren (?) \\ \end{array}$

Gültigkeit und Sichtbarkeit von Bezeichnern (Scoping)

Definition: Bezeichner

Ein Vorkommen eines Bezeichners oder Objekts einer Dekoration heißt definierendes Vorkommen (dV) alle anderen Vorkommen heißen angewandte Vorkommen (aV).

Problem: Im Allgemeinen gibt es mehrere definierende Vorkommen eines Bezeichners. Auf welches definierende Vorkommen bezieht sich ein angewandtes Vorkommen ?

Beispiel: mehrdeutige Bezeichner

$class \ A \{ int \ a; A(int \ a) \{ \ldots a=1; \ldots \}\}$

Definition: Gültigkeitsbereich

Der Gültigkeitsbereich eines definierenden Vorkommens eines Bezeichners id (Scope) ist Teil eines Programms, indem sich das angewandte Vorkommen von id auf diese definierenden Vorkommenen beziehen können. Für ein angewandtes Vorkommen kann es mehrere gültige definierende Vorkommen geben, aber nicht alle sind sichtbar. Durch geeignete Sprachelemente können weitere definierende Vorkommen sichtbar gemacht werden (qualifizierte Bezeichner - this.x, Importe, x.y, etc.). Definierende Vorkommen werden durch Schachtelung von Gültigkeitsebenen versteckt.

Die Identifizierung von Bezeichnern

ordnet jedem angewandtem Vorkommen ein definierendes Vorkommen zu. (Bei Überladung kann und soll sich ein angewandtes Vorkommen auf mehrere definierende Vorkommen beziehen; die Auflösung dieser Mehrdeutigkeit wird durch Kontextanalyse und meistens über Typinformationen realisiert). Die Implementierung wird mittels einer Symboltabelle gemacht, d.h. durch eine Abbildung Id $\rightarrow$ Info. Info ist die korrekte Deklaration für dieses angewandte Vorkommen. Um diese Abbildung zu implementieren gibt es drei Möglichkeiten:

Verweis auf den Knoten der Deklaration, also zum definierenden Vorkommen im AST
Referenz auf den Symboltabelleneintrag der Deklaration
direkt die Information aus der Deklaration kopieren.

Operationen der Symboltabelle

create Erzeugung und Initialisierung der Symboltabelle
enter_block Betritt einen neuen Gültigkeitsbereich und erzeugt sie falls sie nicht vorhanden ist
enter_id(id,decl) Erzeuge Eintrag für id
search-id(id) liefert Verweis auf sichtbares definierendes Vorkommen
exit_block verlässt den aktuellen Gültigkeitsbereich und wechselt auf die nächsthöhere Ebene.

Implementierung

naiv:

Die Symboltabelle ist ein Stack von Blocktabellen, die Tabelle des aktuellen Blocks ist das erste Element. Eine Blocktabelle enthält Einträge für alle Bezeichner deren definierendes Vorkommen im entsprechenden Block liegt.

besser:

eine globale Suchtabelle (Hashtable)
Eintrag zu Bezeichner ist Stack von Deklarationen
Stack von Mengen von Bezeichnern; eine Menge pro Block
- outer_block: push $\emptyset$
- exit_block: entferne den oberen Stackeintrag in der Tabelle zu jedem Bezeichner in der Menge auf der Stackspitze (pop).

Code: Scoping

type (id',decl') Symtab = {
 table : (id',decl') Hashtable.t; 
 stack : 'id list list ref 
}  

let create () = {
 table = Hashtable.create 101;
 Stack = ref left [right]
}  

let enter_block st = 
  st.block := left [right] :: !st.block 

let enter_id st id decl = 
  let_ = Hashtable.add st.table id decl in  (* versteckt unter anderem den alten Eintrag *) 
    let vars :: Stacks = lst,Stack in 
      st.block := (id::vars)::Stacks 

let search_id st id = 
  Hashtable.find st.table id 

let exit_block st = 
  let vars::blocks = !st.block in 
    let_ = st.block := blocks in 
      List.iter(Hashtable.remove st.table) vars

Auflösung der Überladung

Problem: Zu einem Attribut eines Bezeichners gibt es mehrere sichtbare definierende Vorkommen. Dies entsteht durch "Überladung" von Bezeichnern, meist Methoden- bzw. Funktionsnamen, Infixoperatoren, aber teilweise auch Variablen mit gleichem Namen aber unterschiedlichen Typen. Durch geeignete Auswahl der Identifikationskriterien lässt sich eine Überladung auflösen.

Beispiel: Auswahl bei Ada

Anzahl von Operanden
Typen der Operanden
Typ des Rückgabewerts
(Typkonvertierung (cast) macht weiter Schwierigkeiten)

Ein definierendes Vorkommen überdeckt - bei Überladung - nicht alle gültigen sondern nur die äquivalenten definierendes Vorkommen (bezüglich der Auswahl).

Algorithmus zur Auflösung von Überladungen in Ada

$\begin{array}{ll} O \rightarrow \odot & Operator \\ N \rightarrow \odot ( \ N_1 \ldots N_n ) & Operatoranwendung \\ \end{array}$

$\begin{array}{lcl} Syn(0) & := & Symbol \\ Inh(N) & := & par\_typ, \ erwarteter \ Ergebnistyp \ (Menge) \\ Syn(N) & := & res\_typ, \ berechneter \ Ergebnistyp \ (Menge \ von \ moegl. \ Ergebnistypen) \\ & & ops\_bn, \ Menge \ von \ definierenden \ Vorkommen \ der \ gleichen \ Operatorbezeichner \\ & & ops\_td, \ Menge \ von \ definierenden \ Vorkommen \ der \ gleichen \ Operatorbezeichner \\ & & op \subseteq Menge \ der \ definierenden \ Vorkommen \ eines \ Operators \\ & & arity(op), \ Die \ Stelligkeit \ eines \ Operators \\ par\_typ(op,i) & := & deklarierter \ Typ \ des \ i-ten \ Parameters \\ ret\_typ(op) & := & deklarierter \ Ergebnisstyp \ von \ op \\ \end{array}$

Code: Pseudocode

Diese Sektion ist nicht fertig! Der Algorithmus scheint fehlerhaft, bitte ignorieren sie diese Sektion

$\begin{array}{l} N \rightarrow 0 \ N_1 \ldots N_k \\ let \ ops = \{ op | op.symbol = 0.symbol, op \ sichtbar, arity(op)=k \} \ in \\ \ \ N.ops\_bn = \{ op \subseteq ops | {\forall}_i \ par.typ(op,i) \in N_{i}.res\_typ \} \ in \\ \ \ \ \ N.res\_typ = \{ res.typ(op)|op \in N.ops.bn \} \\ \ \ \ \ N.ops\_td = \{ op \in N.ops.bn | res\_typ (op) \ N.par\_typ res.typ(op)|op \in N.ops.bn \} \\ \end{array}$

Datei:Bsp algo scoping.png

Beispiel zur Auflösung von Überladungen

Scanner und Parser verbinden

Über all diese Überlegungen zum Parsen haben wir bisher die Frage nach der lexikalischen Analyse gänzlich ignoriert - sie spielt keine Rolle bei den theoretischen Grundlagen des Parsen. Natürlich ist es augenscheinlich notwendig das wir die beiden Aspekte auf irgendeine Art und Weise verbinden müssen. Die Trennung zwischen lexikalischer und syntaktischer Analyse ist kaum mehr als die Trennlinie, die bei Grammatiken die regulären von den nicht-regulären unterscheidet. Das bedeutet jedoch, daß die Terminalzeichen des nicht-regulären Teils (der Teil der von der syntaktischen Analyse behandelt wird), die die Tokens der lexikalischen Analyse darstellen, in Wirklichkeit Nichtterminalzeichen der originären, vollständigen Grammatik sind. Als solche benötigen sie Attribute.
Jetzt wird klar, daß die Attribute aus der Phase der lexikalischen Analyse tatsächlich die selbe Rolle wie die Attributsinstanzen der syntaktischen Analyse spielen. Es sind nun lediglich kleinere Veränderungen des Attribute evaluierenden Parsers notwendig, um die Tatsache zu berücksichtigen, daß seine Eingabe keine Folge aus Terminalzeichen $ξ$ ist, sondern vielmehr eine Folge von Terminalzeichen/Attribut-Paaren $w$ . In der folgenden Spezifiktion entnimmt ${\pi}_{1}^{*}:{(T \times X)}^{*} \rightarrow T^{*}$ nur die Terminalzeichen aus einer Sequenz von Terminalzeichen/Attribut-Paaren.

$\left [ q \right ] (\omega, c_1, \ldots , c_{nactive(q)}, v_1, \ldots , v_{nactive(q)} :=$

$\begin{array}{ll} \bold{letrec} & c_0 (X,v_0,\omega) = \bold{let} \ q' = goto(q,X) \ \bold{in} \\ & \ \ \ \left [ q' \right ] (\omega, c_o, c_1, \ldots , c_{nactive(q')-1}, v_0, v_1, \ldots , v_{nactive(q')-1}) \\ \bold{in} & A \rightarrow \alpha \cdot (\rho) \in \bar q \wedge {({\pi}_1^{*}(\omega))}_{|k} = \rho \ \triangleright c_{|\alpha|} (A, f_{\langle A \rightarrow \alpha \rangle .v})(v_{|\alpha|}, \ldots , v_1), \omega) \\ | & \omega = (x,v_0) {\omega}' \wedge x \in nextterm(q) \triangleright c_0 (x,v_0,{\omega}') \end{array}$

abstrakte Syntax

Es ist möglich den kompletten Kompilierungsprozess durch die Attribuierungsregeln einer attribuierten Grammatik ablaufen zu lassen. Jedoch werden die Attributevaluierungsregeln während der Evaluierung durch den Parser so weit beschränkt das dieser Vorgang sehr schwierig ist: Der Compiler müsste die Konstrukte in der selben Reihenfolge übersetzen in der sie eingelesen werden - das würde viele Optimierungen unmöglich machen. Außerdem benötigen bestimmte Sprachen mehrere Durchläufe durch das Programm um z.B. Bezeichner aufzulösen. Das kann nicht einfach mit einer on-the-fly Attributsevaluierung gemacht werden.

Konsequenterweise ist es besser die Attribuierungsregeln einfach eine Repräsentation eines Ableitungsbaum konstruieren zu lassen. Jedoch ist die direkte Repräsentation eines Ableitungsbaum nicht die geeignetste für die Zwecke des Compilers. Betrachten wir die Syntax einer Teilmenge von Caml namens Mini-Caml:

Code: Mini-Caml Syntax

<exp> ::= <literal>
   | <ident>
   | ( <operator-name> )
   | ( <exp> )
   | <exp> <exp>
   | <prefix-symbol> <exp>
   | <exp> <infix-symbol> <exp>
   | if <exp> then <exp> else <exp>
   | <exp> or <exp>
   | <exp> & <exp>
   | <exp> ; <exp>
   | function <ident> -> <exp>
   | raise <exp>
   | try <exp> with <ident> -> <exp>
   | let rec? <let-binding> <more-bindings>* in <exp>
   | [ <sequence> ]

<literal> ::= ( ) | <integer-literal> | <character-literal> | <string-literal>
<operator-name> ::== <infix-symbol> | <prefix-symbol>
<sequence> ::= <empty> | <exp> <sequence-rest>*
<sequence-rest> ::= ; <exp>
<let-binding> ::= <ident>+ = <exp>
<more-bindings> ::= and <let-binding>
<definition> ::= let rec? <let-binding> <more-bindings>*
<program> ::= <definition>*

Die Syntax beinhaltet viel "Interpunktion": Klammern, Pfeile, Infixseparatoren wie in oder then die in Ableitungsbaum einfach "tote Blätter" werden: Selbst wenn wir sie auslassen könnten sie leicht automatisch wieder hergestellt werden. Außerdem erlaubt die Syntax Infix-Ausdrücke die eigentlich nur ein anderer Weg sind, binäre Funktionen zu schreiben. Außerhalb der Grammatik gibt es keine Notwendigkeit zwischen der Anwendung von Infixen und Präfixen zu unterscheiden.
Daher verwenden Compiler normalerweise eine abstraktere Repräsentation eines Ableitungsbaums die abtstrakter Syntaxbaum (AST) genannt wird.

Diese beinhaltet immer noch alle notwendigen Informationen um die Bedeutung eines Programms herleiten zu können läßt aber alle unnötigen Details aus. Es ist möglich aus der abstrakten Syntax des Originalprogramm ein äquivalentes Programm zu konstruieren. Deswegen hat die abstrakte Syntax ähnliche Eigenschaften wie die Token/Attribut-Paare, die der Scanner herstellt. Als Faustregel kann man sagen das eine Produktion in der Grammatik zu einem Konstrukt in der abstrakten Syntax korrespondiert. Die Einzelheiten hängen jedoch von der jeweiligen Grammatik und der jeweiligen Parser-Methode, die die Struktur der Grammatik beeinflussen kann, ab.

Mit Hilfe der abtstrakten Syntaxbäume kann nun der volle Formalismus der attribuierten Grammatiken hergestellt werden. Die wichtigste Erkenntnis ist, das Attribuierungen nicht auf Ableitungsbäume beschränkt sind sondern für alle Arten von Baumstrukturen angewendet werden können, im speziellen für abtstrakte Syntaxbäume. Daher kann eine attribuierte Grammatik in geeigneter und erklärender (conveniently and declaratively ) Weise alle Arten von semantischen Analysen auf abtstrakten Syntaxbäume spezifizieren. In diesem Fall ist die Beschränkung alle Attributsdekorationen in einem Durchlauf (z.B. während des Parsens) zu erzeugen nicht mehr vorhanden; fortgeschrittene Multi-Pass-Techniken für das Berechnen der Attributsdekoration existieren und können angewandt werden.

Im Falle von Mini-Caml (was schon einige der syntaktischen Frivolitäten der vollen Caml-Sprache ausläßt) kann die abstrakte Syntax sogar noch einfacher als die konkrete Syntax sein. Die nächste Sektion zeigt eine Caml-Typ Deklaration für eine solche abstrakte Syntax:

Code: abstrakte Mini-Caml Syntax

type 'ident syntax = 
     Nil
   | Int of int
   | String of string
   | Char of char
   | Ident of 'ident
   | Builtin of 'ident
   | Apply of 'ident syntax * 'ident syntax
   | If of 'ident syntax * 'ident syntax * 'ident syntax
   | Sequence of 'ident syntax * 'ident syntax
   | Function of 'ident * 'ident syntax
   | Raise of 'ident syntax
   | Try of 'ident syntax * 'ident * 'ident syntax 
   | Let of 'ident binding * 'ident syntax
   | Letrec of 'ident binding list * 'ident syntax
 and 'ident binding = 'ident * 'ident syntax

type 'ident definition = 'ident binding list

type 'ident program = 'ident definition list

Natürlich gibt es einige seltsame Konstrukte die nach einer Erklärung verlangen:

Die Typdeklaration ist mit dem Typ der Bezeichner parametrisiert. Das macht es später einfacher automatisch generierte Bezeichner modulare Systeme und ähnliches zu behandeln.
Sie unterscheidet zwischen "normalen" (Ident) und eingebauten (Builtin) Bezeichnern, wobei sich die eingebauten auf eingebaute Operationen wie primitive arithemtische Operationen, Speicheralloziierung und ähnliches beziehen. Obwohl der Parser keine Builtin-Knoten produzieren wird, kann eine spätere Analyse herausfinden, welche Ident-Knoten sich tatsächlich auf eingebaute Operationen beziehen.
Sie unterscheidet zwischen let und letrec. Es wird klarwerden das beide Konstrukte in einer späteren Phase des Kompilierens genügend unterschiedliche Behandlung benötigen um diese Unterscheidung zu rechtfertigen.