Compilerbau WS 2000 Dozent: Prof. Dr. K. Indermark

Eine Vorlesungsmitschrift

Thorsten Uthke

thorsten.uthke@post.rwth-aachen.de 27. Dezember 2000

2 INHALTSVERZEICHNIS

Inhaltsverzeichnis

0 Einleitung 3 1 Lexikalische Analyse 5 2 Syntaktische Analyse 13

2.1 Top-Down-Analyse, LL(k)-Grammatiken . . . . . . . . . . . . . . 14 2.2 Bottom-Up-Analyse, LR(k)-Grammatik . . . . . . . . . . . . . . . 21 2.3 Bottom-Up-Analyse mehrdeutiger Grammatiken . . . . . . . . . . 28

3 Semantische Analyse, Attributgrammatiken 29

0 Einleitung

Compiler = Programm zur Übersetzung von PS-Programmen (Quellprogramm) in äquivalente MS-Programme (Zielprogramm)

PS = höhere Programmiersprache

• imperative PS: Wertzuweisungen, Kontrollstrukturen, Datenstrukturen, Programmstrukturen (Moduln, Klassen)

• deklarative PS: funktional, logisch

• nebenläufige PS: kommunizierende Prozesse, verteilte Systeme

• objektorientierte PS: Klassen, Vererbung

MS = Maschinensprache Grundkonzept des Von-Neumann-Rechners elementare Maschinenbefehle (vergl. Rechnerstrukturen) RISC = reduced instruction set computer CISC = complex instruction set computer Parallelrechner, verteilte Systeme, Rechnernetze

Aspekte einer PS

1) Syntax: formaler hierarchischer Aufbau eines Programmes aus strukturellen Komponenten

2) Semantik: Bedeutung eines Programms, Zustandstransformation einer abstrakten Maschine

3) Pragmatik: benutzerfreundliche Formulierung, natürliche Sprache, Maschinenabhängigkeiten

Äquivalenz von Programmen ˆ= semantische Gleichheit

Struktur eines Compilers logisch unabhängige Phasen, die aber verzahnt als Passes (Läufe) durchgeführt werden: Analysephase & Synthesephase

Analyse : Bestimmung der syntaktischen Struktur, Fehlererkennung

• lexikalische Analyse: Erkennung von Symbolen, Trennzeichen, Kommentaren (endliche Automaten)

• syntaktische Analyse: Erkennung des hierarchischen Programmaufbaus, Ableitungsbaum (Kellerautomaten)

• semantische Analyse: Kontextabhängigkeiten, statische Semantik, Typinformation. Attributierung des Ableitungsbaums mit semantisch relevanter Information (attributierte Grammatiken)

Synthese : Erzeugung von MS-Code aus dem attributierten Ableitungsbaum

• Übersetzung in Zwischencode für eine abstrakte Maschine (Kann fehlen, erhöht die Portabilität, vergl. Java Virtual Machine (JVM))

• Optimierung: Verbesserung von Laufzeit und Speicherbedarf

• Codegenerierung: effiziente Verwendung von Registern und MS-Befehlssatz zur Erzeugung von MS-Code

Frontend: (MS-unabhängig) Analyse & Zwischencode & MS-unabhängige Optimierung Backend: (MS-abhängig) MS-Code-Generierung & Optimierung One-Pass-Compiler, n-Pass-Compiler: n = Anzahl der Läufe durch das Quellprogramm \underline{Ziele}:

• Wirkungsweise und Konstruktion von Compilern

• Vertieftes Verständnis von PS und ihrem Rechnerbezug

• Compiler als gut verstandenes Beispiel eines SW-Systems mit Interaktion von SW-Bausteinen

• Erkennung und Transformation strukturierter Objekte

1 Lexikalische Analyse

\underline{Ausgangspunkt:} Quellprogramm P als Zeichenfolge Σ_{0} Zeichensatz, a ∈ Σ_{0} Zeichen bzw. lexikalisches Atom, P ∈ Σ_{0}. P besitzt aufgrund der Pragmatik von PS eine lexikalische Struktur. Pragmatischer Aspekt: Benutzerfreundlichkeit von PS

• natürliche Sprache für Bezeichner, Schlüsselworte, …

• mathematische Formelsprache für Zahlen, Formeln. Indices linearisieren, z.B. y^{2} ⇝ y ∗ ∗2

• Leerzeichen, Zeilenwechsel, Einrückung, …

• Kommentare

⇝ gute Lesbarkeit und Wartbarkeit

Semantik von P und Übersetzung von P ist syntaxorientiert, sie folgt dem hierarchischen Programmaufbau, die pragmatischen Aspekte sind dabei unerheblich.

1. Beobachtung: Syntaktische Atome (Symbole) werden als Folgen von lexikalischen Atomen, sogenannten Lexemen, dargestellt.

1. Aufgabe der lexikalischen Analyse: Zerlegung des Quellprogramms P in eine Folge von Lexemen.

2. Beobachtung: Für die syntaktische Analyse ist der Unterschid von Lexemen oft irrelevant, z.B. müssen Bezeichner nicht unterschieden werden. Lexeme werden oft zu Symbolklassen zusammengefaßt.

Darstellung einer Symbolklasse: Token. Syntaktische Analyse bearbeitet eine Tokenfolge. Identifizierung eines Symbols durch zusätzliches Attribut für die semantische Analyse und Codegenerierung.

Symbol = (Token, Attribut).

2. Aufgabe: Transformation einer Lexem-Folge in eine Symbol-Folge.

Lexikalische Analyse Zerlegung eines Quellprogramms in eine Folge von Lexemen und deren Transformation in eine Folge von Symbolen.

Scanner: Programm für die lexikalische Analyse Beachte: Leerzeichen werden gelöscht. Sie spielen eine Rolle bei der Lexem-Gliederung. Kommentare werden gelöscht.

\underline{Wichtigste Symbolklassen} (eigentlich Lexem-Klassen)

• Bezeichner

• Zahlwörter

• Schlüsselwörter: Bezeichner mit vorgegebener Bedeutung

• Einfache Symbole: ein Sonderzeichen, z.B. +,-,*,(,…

• Zusammengesetzte Symbole: Folgen von 2 oder mehr Sonderzeichen, z.B. :=,**,<=,…

• Leerzeichen: ⊔, ⊔ … ⊔

• Spezielle Symbole: Kommentare, Pragmas (Compiler-Optionen)

Token: id, const, divsym, getsym, … Attribute: Zeiger in die Symboltabelle, Binärdarstellung einer Zahl, leer bei Symbolklassen mit einem Symbol Feststellung: Symbolklassen und reguläre Mengen ⇝ Beschreibung durch reguläre Ausdrücke Erkennung durch endliche Automaten, automatische Scanner-Generierung, z.B. Lex. Scanner-Konstruktion

Definition 1.1 (Reguläre Ausdrücke) Für ein Alphabet Σ ist die Menge RA(Σ) der regulären Ausdrücke über Σ definiert durch

• Λ ∈ RA(Σ), Σ ⊆ RA(Σ)

• α, β ∈ RA(Σ) ↷ (α ∨ β), (α · β), (α^{∗}) ∈ RA(Σ)

Semantik: [[]] : RA(Σ) → P(Σ^{∗})

• [[Λ]] := ∅, [[a]] := {a}

• [[α ∨ β]] := [[α]] ∪ [[β]]

• [[α · β]] := [[α]] · [[β]]

• [[α^{∗}]] := [[α]]^{∗} (L^{∗} = ⋃_{n=0}^{∞} L^{n})

Spracherweiterung von RA(Σ) zur einfacheren Beschreibung von Symbolklassen (regulären Sprachen)

a) Vereinfachende Bezeichnungen:

• Präzedenzregeln zur Vermeidung von Klammern ∗ bindet stärker als ·, · stärker als ∨ · und ∨ sind linksassioziativ · wird weggelassen, ∨ als | geschrieben Beispiel: a|b^{∗}c steht für (a ∨ ((b^{∗}) · c))

• Abkürzungen α^{+} := αα^{∗} α^{?} := α|Λ^{∗}

[abc] := a|b|c

[a − z] := a|b| … |z

b) Reguläre Definitionen Schrittweise Beschreibung von Symbolklassen durch zusätzliche frei gewählte Bezeichner (Meta-Bezeichner) \underline{id}_{1} = α_{1} mit \underline{id}_{1}, …, \underline{id}_{n} ∉ Σ

⋮ und α_{i} ∈ RA(Σ ·∪\{\underline{id}_{1}, …, \underline{id}_{n−1}\})

\underline{id}_{n} = α_{n}

Beachte: Keine Rekursion, Entschachtelung ist möglich, andernfalls EBNF (CFG).

Das einfache Matching-Problem Entscheide für α ∈ RA(Σ) und w ∈ Σ^{∗}, ob w ∈ [[α]] oder nicht. Hilfsmittel: Endliche Automaten 𝔄 =< Q, Σ, δ, q_{0}, F >∈ NF A(Σ), wenn δ : Q × (Σ ∪ {ε}) → P(Q). Für T ⊆ Q ist die ε-Hülle ε(T) definiert durch

• T ⊆ ε(T)

• q ∈ ε(T) ↷ δ(q, ε) ⊆ ε(T)

Die \underline{erweiterte} Transitionsfunktion \overline{δ} : P(Q) × Σ^{∗} → P(Q) ist definiert durch

• \overline{δ}(T, ε) := ε(T)

• \overline{δ}(T, wa) := ε(⋃_{δ∈\overline{δ}(T,w)} δ(q, a))

𝔄 erkennt die Sprache L(𝔄) := \{w ∈ Σ^{∗}|\overline{δ}(\{q_{0}\}, w) ∩ F ≠ ∅\} 𝔄 ∈ DF A(Σ), wenn gilt

|δ(q, a)| = 1 für alle q ∈ Q, a ∈ Σ und |δ(q, ε)| = 0 für alle q ∈ Q

Also: δ : Q × Σ → Q

DFA-Methode

α ∈ RA(Σ) ↦^{(1)} 𝔄(α) ∈ NF A(Σ) ↦^{(2)} 𝔄(α)^{P} ∈ DF A(Σ)

1) Methode von Thompson (Beweis des Satzes von Kleene) (1968) Korrektheit: folgende Eigenschaften Jeder Automat hat genau einen Anfangszustand q_{0} und genau einen Endzustand q_{f} mit q_{0} ≠ q_{f}, q_{0} Quelle, q_{f} Senke. Jeder Zustand hat höchstens zwei Folgezustände, einen a-Nachfolger oder höchstens 2 ε-Nachfolger. Komplexität: linearer Platz- und Zeitbedarf

• Platz: 𝔄(α) hat höchstens 2|α| Zustände |α| = Anzahl der Grundzeichen von Σ ∪ {Λ} und der Op. ∨,·,∗

• Zeit: Syntaxanalyse von α in O(|α|) Schritten, z.B. Transformation von α in Postfix-Notation (ohne Klammern) & schrittweiser Aufbau von 𝔄(α) in O(|α|) Schritten

2) 𝔄(α) ∈ NF A(Σ) ↦ 𝔄(α)^{P} ∈ DF A(Σ)

Konstruktion der ε-Hülle Sei 𝔄(α) ∈ NF A(Σ) mit Zustandsmenge Q und T ⊆ Q. Aufgabe: Berechne ε(T) ⊆ Q Idee: Ein Stack speichert Zustände, welche auf ε-Nachfolger zu testen sind. Komplexität: Idee der Darstellung von T ⊆ Q (als Boolsches Array) Q = {1, …, n}, T̃ : Q → {0, 1}, damit: q ∈ T ⟺ T̃(q) = 1 Die Zugehörigkeit eines Zustandes q zu T ist also in O(1) zu prüfen.

• Platz: O(n), weil length(stack) ≤ n; denn ein Zustand q erscheint höchstens ein mal auf dem Stack (wegen der Überprüfung, ob q schon in clos(T) enthalten ist).

• Zeit: O(n), insbesondere weil die for-Schleife in konstanter Zeit durchlaufen wird (q hat höchstens 2 ε-Nachfolger).

\underline{Potenzmengenkonstruktion} 𝔄(α) ∈ NF A(Σ) ↦ 𝔄(α)^{P} ∈ DF A(Σ) 𝔄(α) =< Q, Σ, δ, q_{0}, F > mit δ : Q × (Σ ∪ {ε}) → P(Q) 𝔄(α)^{P} =< Q̂, Σ, δ̂, q̂_{0}, F̂ > mit

• Q̂ := \{T ⊆ Q|T = \overline{δ}(\{q_{0}\}, w), w ∈ Σ^{∗}\}

• δ̂: Q̂ × Σ → Q̂ und δ̂(T, a) := \overline{δ}(T, a)

• q̂_{0} := ε({q_{0}})

• T ∈ F̂ ⟺ T ∩ F ≠ ∅

\underline{Algorithmus} Idee: Q̂ mit ε({q_{0}}) initialisieren und sukkzessiv mit δ̂(T, a) erweitern; T ∈ Q̂ wird markiert, wenn seine Nachfolger in Q̂ liegen.

Komplexität:

• Platz: O(2^{|α|}) (jedoch nur erreichbare Zustände)

• Zeit: O(2^{|α|}), aber: Berechnung von δ̂(T, a) in Linearzeit, weil die ε-Hülle Linearzeit-Berechenbar ist und ein Zustand von 𝔄(α) höchstens einen a-Nachfolger hat.

NFA-Methode Verbesserung des Platzbedarfs bei längerer Laufzeit durch Verzicht auf die volle Potenzmengenkonstruktion, da die Eingabe w ∈ Σ^{∗} bekannt ist. Potenzmengenkonstruktion nur für den Lauf von w durch 𝔄(α). Direkte Berechnung von \overline{δ}(\{q_{0}\}, w).

Algorithmus:

Eingabe: 𝔄(α) ∈ NF A(Σ) und w = a_{1} … a_{n} ∈ Σ^{∗} in der Form a_{1} a_{n} eof ; …; ↑

Komplexität:

• Platz: O(|α| + |w|)

1. Stack für T

2. Stack für ⋃_{q∈T} δ(q, a)

Stacklänge ≤ |Q|, Berechnung der ε-Hülle mit zusätzlichem Bitvektor der Länge |Q|

• Zeit: O(|α| · |w|)

Kombination von NFA- und DFA- Methode Die Zwischenergebnisse von bereits berechneten Transitionen in einem Cache-Speicher ablegen.

Das erweiterte Matching-Problem Seien α_{1}, …, α_{n} ∈ RA(Σ) und w ∈ Σ^{∗}. Sei ferner △ = {S_{1}, …, S_{n}} ein Alphabet von Symbolen. Wenn w = w_{1}w_{2} … w_{k} und w_{j} ∈ [[α_{i_{j}}]] für j = 1, …, k, dann heißt (w_{1}, …, w_{k}) eine Zerlegung von w bezüglich α_{1}, …, α_{n} und v = S_{i_{1}} … S_{i_{k}} eine Analyse von w bezüglich α_{1}, …, α_{n}. v repräsentiert die lexikalische Struktur von w bezüglich α_{1}, …, α_{n}.

Aufgabe: Analyse bestimmen bzw. Fehler melden. Weder Zerlegung noch Analyse sind eindeutig bestimmt.

Konvention für Eindeutigkeit

1) Prinzip des längsten Matches (maximal munch) Eine Zerlegung (w_{1}, …, w_{k}) von w bezüglich α_{1}, …, α_{n} heißt lm-Zerlegung, wenn für alle j = 1, …, k, x, y ∈ Σ^{∗} und p, q ∈ {1, …, n} gilt: w = w_{1} … w_{j}xy mit w_{j} ∈ [[α_{p}]] und w_{j}x ∈ [[α_{q}]] ↷ x = ε. Folgerung: Für w, α_{1}, …, α_{n} gibt es höchstens eine lm-Zerlegung.

2) Prinzip des ersten Matches (für die Eindeutigkeit der Analyse) Denn trotz Eindeutigkeit der lm-Zerlegung, sind im Allgemeinen mehrere zugehörige Analysen möglich, da [[α_{p}]] ∩ [[α_{q}]] ≠ ∅ möglich. Konvention: Erster Match in der Reihe α_{1}, …, α_{n} zählt. Sei (w_{1}, …, w_{k}) eine lm-Zerlegung und v = S_{1} … S_{k} eine zugehörige Analyse von w bezüglich α_{1}, …, α_{n}. Dann heißt v eine flm-Analyse, falls für alle j = 1, …, k und i = 1, …, n gilt: w_{j} ∈ [[α_{i}]] ↷ i_{j} ≤ i. Folgerung: Für w und α_{1}, …, α_{n} gibt es höchstens eine flm-Analyse.

Berechnung der flm-Analyse Vorrausetzung: α_{1}, …, α_{n} ∈ RA(Σ). O.B.d.A. [[α_{i}]] ≠ ∅ und ε ∉ [[α_{i}]] für i = 1, …, n, w ∈ Σ^{∗}, △ = {S_{1}, …, S_{n}} Symbolalphabet.

1) Konstruiere für i = 1, …, n den Automat 𝔄_{i} = ⟨Q_{i}, Σ, δ_{i}, q_{0}^{(i)}, F_{i}⟩ ∈ DF A(Σ), so daß [[α_{i}]] = L(𝔄_{i}).

2) Bilde aus diesen den Produktautomaten 𝔄 = ⟨Q, Σ, δ, q_{0}, F ⟩ ∈ DF A(Σ) mit Q := Q_{1} × … × Q_{n}, q_{0} = (q_{0}^{(1)}, …, q_{0}^{(n)}), δ((q^{(1)}, …, q^{(n)}), a) = (δ(q^{(1)}, a), …, δ(q^{(n)}, a)) und (q^{(1)}, …, q^{(n)}) ∈ F ⟺ ∃i ∈ {1, …, n} : q^{(i)} ∈ F_{i}.

Dann gilt: L(𝔄) = ⋃_{i=1}^{n} [[α_{i}]]

Zerlege F wegen ”first match” in F = ⋃_{i=1}^{n} F^{(i)} durch die Forderung

(q^{(1)}, …, q^{(n)}) ∈ F^{(i)} ⟺ q^{(i)} ∈ F_{i} und q^{(j)} ∉ F_{j} für alle 1 ≤ j < i.

Dann gilt: \overline{δ}(q_{0}, w) ∈ F^{(i)} ⟺ w ∈ [[α_{i}]] und w ∉ ⋃_{j=1}^{i−1} [[α_{j}]]

q ∈ Q heißt produktiv ⟺ ∃w ∈ Σ^{∗} : \overline{δ}(q, w) ∈ F. P : Menge der produktiven Zustände, also F ⊆ P. Aufgabe: P bestimmen

3) Erweitere 𝔄 zu dem Backtrack-DFA B mit Ausgabe Idee: Einweg-Leseband mit 2 Köpfen, ein Backtrack-Kopf b zur Markierung eines Matches und einen Lookahead-Kopf l zur Bestimmung des längsten Matches _{↑_{b} ↑_{l}}

\underline{Konfigurationsmenge von B:} (\{N\} ∪ △) × Σ^{∗}QΣ^{∗} × △^{∗}\{ε, lexerror\} \underline{Anfangskonfiguration} für w ∈ Σ^{∗}: (N, q_{0}w, ε) \underline{Transitionen:} (wobei q′ := δ(q, a))

a) normal mode: Match suchen

(N, qaw, W) ⊢ \{ \begin{matrix}(N, q′w, W) & , falls q′ ∈ P \ F \\ (S_{i}, q′w, W) & , falls q′ ∈ F^{(i)} \\ Ausgabe: W lexxerror & , falls q′ ∉ P \end{matrix}

b) backtrack mode: längsten Match suchen

(S, vqaw, W) ⊢ \{ \begin{matrix}(S, vaq′w, W) & , falls q′ ∈ P \ F \\ (S_{i}, q′w, W) & , falls q′ ∈ F^{(i)} \\ (N, q_{0}vaw, W S) & , falls q′ ∉ P \end{matrix}

c) Eingabeende

(N, q, W) ⊢ Ausgabe: W lexxerror ,falls q ∈ P \ F
(S, q, W) ⊢ Ausgabe: W S  ,falls q ∈ F
(S, vaq, W) ⊢ (N, q_{0}va, W S)  ,falls q ∈ P \ F

Dann gilt für w ∈ Σ^{∗}:

(N, q_{0}w, ε) ⊢^{∗} Ausgabe: W ∈ △^{∗} ⟺ W ist flm-Analyse von w

(N, q_{0}w, ε) ⊢^{∗} Ausgabe: W lexxerror ⟺ es gibt keine flm-Analyse von w Zeitaufwand: O(|w|^{2}) im worst-case

\underline{Beispiel} α_{1} = abc, α_{2} = (abc) ∗ d und Σ = \{abcd\} ⟹ w = (abc)^{m} erfordert O(m^{2}) Schritte

Verbesserung durch Tabular-Methode (vergleiche KMP für string pattern matching) in Linearzeit Literatur: Th. Reps: ”Maximal munch”-Tokenization in Linear Time, ACM-TOPLAS 20, 1998, p259-273

\underline{Beispiel} Teil 1: siehe Folie 2-1 (Symbolklassen) Teil 2: Anweisungen

stmt = \underline{if} expr \underline{then} stmt | \underline{if} expr \underline{then} stmt \underline{else} stmt
expr = term \underline{relop} term | term
term = \underline{id} | \underline{num}

Annahme für die lexikalische Analyse: Die Lexeme eines stmt sind durch \underline{blanks} getrennt. ⟹ besondere Rolle von \underline{blanks} (White Space)

• Trennung von ”eigentlichen” Lexemen, um mit ”1-lookahead” auszukommen

• als Token für syntaktische Analyse überflüssig

Sieber: Programm zur Beseitigung überflüssiger Lexeme, wie Blanks, Kommentare, Pragmas, …

Attributberechnung Symbolklassen mit mehreren Lexemen erfordern zusätzlich eine Attributberechnung

• Dezimalzahl ⇝ Binärzahl (install num)

• Relationale Operatoren: LT,GT,EQ,…

• Bezeichner: Gleichheit von Bezeichenern relevant ⇒ Verwendung einer Lexemtabelle (LexTab) install id: Eintrag eines Bezeichners in LexTab, Zeiger als Attribut

Alternative Behandlung von Schlüsselwörtern Zunächst als Bezeichner behandeln, LexTab mit Schlüsselwörtern initialisieren, die Attributberechnung (install id) liefert statt (ID,[Zeiger in LexTab]) ein-

fach (IF,).

Automatische Scannergenerierung mit Lex (Unix-Tool)

scan.l ⇝^{Lex} lex.yy.c ⇝^{C−Compiler} a.out

(LexSpec)  (Scanner als C-Programm)  (ausführbarer Scanner)

Programm ⇝^{a.out} Tokenfolge

Aufbau einer Lex-Spezifikation

Definitionen
%%
Regeln

\begin{matrix}%% \\ C-Hilfsprozeduren \end{matrix} \} optional

\underline{Definitionen}

• Direkter C-Code

• Substitutionen (reguläre Def.): Name regexp

• Startzustände (hier nicht vorgestellt)

\underline{Regeln}: muster \{aktion\}
muster hat folgenden Aufbau: regexp_{1} [/regexp_{2}]

Eine Zeichenkette paßt zu muster, falls sie regexp_{1} matcht und ein lookahead regexp_{2} matcht. aktion: C-Code zur Berechnung von Token und Attribut

Finden der passenden Regel

1) longest match

2) first match

3) keine passende Regel: Zeichen wird ausgegeben, kann mit regexp: .|\n vermieden werden (regexp matcht alles)

Token werden als Int-Werte kodiert Attribute werden über globale Variablen weitergeleitet: vordef. Variable yylval Fileends: Anfang einer benutzerdefinierten Prozedur

  int yywrap(void)

Rückgabe 1 ⇝ Lex liefert 0 zurück (kein Token/Ende der Tokensequenz)

2 Syntaktische Analyse

Aufgabe: Zerlegung der Symbolfolge, die der Scanner ausgibt, in syntaktische Einheiten, bzw. Behandlung syntaktischer Fehler Syntaktische Einheiten: Variablen, Ausdrücke, Anweisungen,… Beachte: Schachtelung syntaktischer Einheiten, Baumstruktur im Unterschied zur linearen Symbolfolge

Parser: Programm für die syntaktische Analyse

Schnittstelle

Scanner

symbol (token, attr)

Parser

syntax tree

Semantic analyser

Error handler

Beschreibung der syntaktischen Struktur: kontextfreie Grammatiken Erkennung und Analyse: Kellerautomaten mit Ausgabe Problem: deterministische Simulation

Allgemeiner Fall: beliebige CFG Tabularverfahren von CYK (Cocke, Younger & Kasami) mit O(n^{3})-Zeit- und O(n^{2})-Platzkomplexität

Programmiersprachen: spezielle CFG Analyse durch deterministischen Automaten mit ”input look ahead” bei linearem Platz- und Zeitbedarf

a) Top-Down-Analyse: Konstruktion des Ableitungsbaums von der Wurzel zu den Blättern in Form einer Linksanalyse

b) Bottom-Up-Analyse: umgekehrt, entspricht gespiegelter Rechtsanalyse

Kontextfreie Grammatiken G = ⟨N, Σ, P, S⟩ ∈ CF G(Σ) Bezeichnungskonventionen:

A, B, C, … ∈ N Nichtterminalsymbole
a, b, c, … ∈ Σ Terminalsymbole
u, v, w, … ∈ Σ^{∗} Terminalwörter
α, β, γ, … ∈ X Satzformen (mit X = N ∪ Σ)
A → α  ∈ P Produktion/Regel

Ableitungsrelation: ⇒⊆ (X^{∗}) × (X^{∗}) ist definiert durch α ⇒ β ⟺ α = α_{1}Aα_{2}, A → γ ∈ P, β = α_{1}γα_{2}

Gilt außerdem α_{1} ∈ Σ^{∗} bzw. α_{2} ∈ Σ^{∗}, so α ⇒_{l} β bzw. α ⇒_{r} β. Sprechweise: Ableitungsschritt, Links…, Rechts…

Erzeugte Sprache: L(G) = {w ∈ Σ^{∗}|S ⇒^{∗} w} = {w ∈ Σ^{∗}|S ⇒^{∗}_{l} w} = {w ∈

Σ^{∗}|S ⇒^{∗}_{r} w}

Beispiel: G : S → aSb|ε S ⇒ aSb ⇒ a^{2}Sb^{2} ⇒ …

Ableitungsbaum: repräsentiert die syntaktische Struktur des abgeleiteten Wortes ^{S a S b a ε b}

Definition 2.1 G heißt eindeutig, wenn es für jedes w ∈ L(G) genau einen Ableitungsbaum gibt.

Folgerung: G ist eindeutig, genau dann wenn es für jedes w ∈ L(G) genau eine Links- bzw. Rechtsanalyse gibt.

Definition 2.2 G heißt mehrdeutig, wenn G nicht eindeutig ist.

l-Analyse, r-Analyse Darstellung von l- bzw. r-Ableitungen durch Nummernfolgen |P | = p, [p] := {1, …, p}, π : [p] → P bijektiv, π_{i} = π(i)

wAα ⇒^{i}_{l} wγα bzw. αAw ⇒^{i}_{r} αγw, falls π_{i} = A → γ

Für z = i_{1}i_{2} … i_{n} ∈ [p]^{+} soll α ⇒^{z}_{l} β ⟺ α ⇒^{i_{1}}_{l} α_{1} ⇒^{i_{2}}_{l} … ⇒^{i_{n}}_{l} α_{n} = β für

passende α_{1}, …, α_{n−1}. α ⇒^{ε}_{l} α (ein leerer l-Ableitungsschritt)

Definition 2.3 z heißt l-Analyse von α ⟺ S ⇒^{z}_{l} α. z heißt r-Analyse von α ⟺ S ⇒^{z}_{r} α.

Syntaxanlyse Gegeben: G ∈ CF G, w ∈ Σ^{∗}. Berechnung einer l/r-Analyse, falls w ∈ L(G); andernfalls Bestimmung syntaktischer Fehler.

Generalvoraussetzung G ∈ CF G ist reduziert, d.h. für jedes A ∈ N gibt es α, β ∈ X^{∗} und w ∈ Σ^{∗}, so daß S ⇒^{∗} αAβ (A erreichbar) und A ⇒^{∗} w (A produktiv).

2.1 Top-Down-Analyse, LL(k)-Grammatiken

Definition 2.4 (Top-Down-Analyseautomat von G ∈ CF G, NT A(G)) Eingabealphabet: Σ Kelleralphabet: X = N ∪ Σ Ausgabealphabet: [p] Zustandsalphabet: entfällt, der Automat arbeitet mit einem Kontrollzustand ^{Eingabeband w ↓ Kellerspeicher α ⇓ Ausgabeband z ↓} Konfigurationsmenge: Σ^{∗} × X^{∗} × [p]^{∗} (Kellerspitze links)

Transitionen:

• Ableitungsschritt: (w, Aα, z) ⊢ (w, βα, zi) falls π_{i} = A → β

• Vergleichsschritt: (aw, aα, z) ⊢ (w, α, z) für a ∈ Σ

Anfangskonfiguration für w ∈ Σ^{∗} : (w, S, ε) Endkonfiguration: (ε, ε, z) falls w ∈ L(G) (bzw. Fehler)

Beachte: Nichtdeterminismus wegen A → β|γ

Satz 2.1 Der NTA(G) berechnet l-Analysen, d.h. (w, S, ε ⊢^{∗} (ε, ε, z) ⟺ z ist l-Analyse von w.

Beweis: ”⇒”, d.h. der Automat arbeitet korrekt

(∗) (w, α, y) ⊢^{∗} (ε, ε, yz) ↷ α ⇒^{z}_{l} w

Beweis von (∗) durch Induktion über k = |z|

k = 0: (w, α, y) ⊢^{∗} (ε, ε, y) nur Vergleichsschritte,

w = α, also (∗) mit w ⇒^{ε}_{l} w

k ⇝ k + 1: z = iz′, α = uAβ, w = uv, π_{i} = A → γ

(w, α, y) = (uv, uAβ, y) ⊢^{∗} (v, Aβ, y) ⊢ (v, γβ, yi) ⊢^{∗} (ε, ε, yiz′)

Nach IV: γβ ⇒^{z′}_{l} v (in |z′| = k Schritten) und damit folgt (∗) wegen

α = uAβ ⇒^{i}_{l} uγβ ⇒^{z′}_{l} uv = w, also α ⇒^{z}_{l} w.

”⇐” in der 3. Übung

Ziel: Nichtdeterminismus des NTA(G) durch k-lok-ahead auf der Eingabe beseitigen (k ∈ ℕ).

Definition 2.5 (first-Mengen) Sei G ∈ CF G, α ∈ X^{∗} und k ∈ ℕ. Wir definieren first_{k}(α) ⊆ Σ^{∗} durch

first_{k}(α) := {v ∈ Σ^{∗}|∃w ∈ Σ^{∗} : α ⇒^{∗} vw, |v| = k} ∪ {v ∈ Σ^{∗}|α ⇒^{∗} v, |v| < k}

\underline{Folgerungen}  [figure: A; v; ≀; ≀; ≀]

(i) first_{k}(α) ≠ ∅ weil G reduziert

(ii) ε ∈ first_{k}(α) ⟺ k = 0 oder α ⇒^{∗} ε

(iii) α ⇒^{∗} β ↷ first_{k}(β) ⊆ first_{k}(α)

(iv) v ∈ first_{k}(α) ⟺ ∃x ∈ Σ^{∗} : α ⇒^{∗}_{l} x, {v} = first_{k}(x)

Wunsch: A-Regel durch v festlegen ⇝ LL(k)-Grammatiken (Lesen der Eingabe von \underline{l}inks nach rechts mit \underline{k}-look-ahead, Berechnung einer \underline{L}inksanalyse)

Definition 2.6 (LL(k)-Grammatik) Sei G ∈ CF G und k ∈ ℕ. G ∈ LL(k) ⟺ Für alle l-Ableitungen der Form

S ⇒^{∗}_{l} wAα ↗ ↘^{l}_{l} wβα ⇒^{∗}_{l} wx wγα ⇒^{∗}_{l} wy mit first_{k}(x) = first_{k}(y) gilt: β = γ.

Bemerkung:

• Linksableitungsschritt für wAα ist durch die nächsten k auf w folgenden Symbole bestimmt.

• Der NTA(G) kann für G ∈ LL(k) mit k-look-ahead auf der Eingabe deterministisch simuliert werden.

Problem: Bestimmung der A-Regel aus k-look-ahead.

Lemma 2.1 G ∈ LL(k) ⟺ Für alle l-Ableitungen der Form

S ⇒^{∗}_{l} wAα ↗ ↘^{l}_{l} wβα wγα mit β ≠ γ gilt: first_{k}(βα) ∩ first_{k}(γα) = ∅.

Beweis: ↓ (”Def. ↷ Lemma”) Angenommen, die Definition und die Voraussetzung des Lemma (β ≠ γ) gilt, aber

v ∈ first_{k}(βα) ∩ first(γα). Dann muß βα ⇒^{∗}_{l} x und γα ⇒^{∗}_{l} y mit first_{k}(x) =

first_{k}(y). Also nach Def. β = γ ⇒ Widerspruch!

↑ (”Lemma-Eigenschaft ↷ Definition-Eigenschaft”) Angenommen Lemma-Eigenschaft und Voraussetzung der Definition gilt \underline{und} β ≠ γ. Daraus folgt: first_{k}(βα) ∩ first_{k}(γα) = ∅. Widerspruch, da first_{k}(x) ⊆ first_{k}(βα) und first_{k}(y) ⊆ first_{k}(γα).

Problem: Abhängig der look-ahead-Menge vom Rechtskontext α. Ziel: Betsimmung der look-ahead-Menge aus Regel allein. Idee: Mögliche Rechtskontexte vereinigen.

Definition 2.7 (follow-Mengen) Sei G ∈ CF G, A ∈ N und k ∈ ℕ. Wir definieren follow_{k}(A) ⊆ Σ^{∗} durch

follow_{k}(A) := {v ∈ Σ^{∗}|S ⇒^{∗}_{l} wAα, v ∈ first_{k}(α)}.

Der Fall k = 1

I.A. genügt k = 1. k > 1 ist aufwendiger (wird aber zum Teil in heutigen Parser-Generatoren verwendet).

Satz 2.2 Für G ∈ CF G (G reduziert) gilt: G ∈ LL(1) ⟺ Für alle Regelpaare A → β|γ mit β ≠ γ folgt: first_{1}(βfollow_{1}(A)) ∩ first(γfollow_{1}(A)) = ∅.

Abkürzung: fi := first_{1} und fo := follow_{1} Definition 2.8 la(A → β) := fi(βfo(A)) heißt Look-ahead-Menge von A → β.

Beachte:

• fi(α) ⊆ Σ_{ε} := Σ ∪ {ε}

• fo(A) ⊆ Σ_{ε}

• βfo(A) ⊆ X^{∗}

• Für Γ ⊂ X^{∗} ist fi(Γ) := ⋃_{α∈Γ} fi(α)

• la(A → β) = fi(βfo(A)) ⊆ Σ_{ε}

Eigenschaft:

• ε ∈ fi(βfo(A)) ⟺ β ⇒^{∗} ε und ε ∈ fo(A)

• a ∈ fi(βfo(A)) ⟺ a ∈ fi(β) oder [β ⇒^{∗} ε und a ∈ fo(A)]

Satz 2.3 G ∈ LL(1) ⟺ Für alle Regelpaare A → β|γ (β ≠ γ) folgt: la(A → β) ∩ la(A → γ) = ∅.

Beweis: ”↷” G ∈ LL(1) Angenommen, es gibt A → β|γ mit β ≠ γ und c ∈ fi(βfo(A)) ∩ fi(γfo(A))

für c ∈ Σ_{ε}. \underline{Fall 1:} c = ε, alsp ε ∈ fo(A) ↷ S ⇒^{∗}_{l} wAα und α ⇒^{∗} ε.

Außerdem β ⇒^{∗} ε und γ ⇒^{∗} ε. Dies ist bestimmt ein Widerspruch zu LL(1), weil

S ⇒^{∗}_{l} wAα ↗ ↘^{l}_{l} wβα wγα mit ε ∈ fi(βα) ∩ fi(γα).

\underline{Fall 2:} c = a ∈ Σ Es folgt:

1) a ∈ fi(β) ∩ fi(γ)

2) a ∈ fi(β), γ ⇒^{∗} ε und a ∈ fo(A)

3) a ∈ fi(γ), β ⇒^{∗} ε und a ∈ fo(A)

4) β ⇒^{∗} ε, γ ⇒^{∗} ε und a ∈ fo(A)

Aus (1) ergibt sich (da G reduziert) eine Ableitung S ⇒^{∗}_{l} wAα ↗ ↘^{l}_{l} wβα wγα mit a ∈ fi(βα) ∩ fi(γα), also Widerspruch zu G ∈ LL(1), da β ≠ γ.

In den Fällen (2)-(4) folgt aus a ∈ fo(A) ebenso eine Ableitung

S ⇒^{∗}_{l} wAα ↗ ↘^{l}_{l} wβα wγα mit a ∈ fi(α).

Für (2) folgt: a ∈ fi(β), also a ∈ fi(βα), γ ⇒^{∗} ε, also a ∈ fi(γα). Analog für (3) und (4).

18 2 SYNTAKTISCHE ANALYSE

”↶”: S ⇒^{∗}_{l} wAα ↗ ↘^{l}_{l} wβα wγα mit β = γ.

Nach Voraussetzung gilt: fi(βfo(A)) ∩ fi(γfo(A)) = ∅ fi(βα) ⊆ fi(βfo(A)) und fi(γα) ⊆ fi(γfo(A)) ↷ fi(βα) ∩ fi(γα) = ∅ Berechnung der la-Mengen

1) fi(X) für X ∈ X • X = a ∈ Σ ↷ fi(X) = {X}

• X → aα ↷ a ∈ fi(X)

• X → ε ↷ ε ∈ fi(X)

• X → A_{1} … A_{k}Y α, k ≥ 0, Y ∈ X , ε ∈ fi(A_{1}) ∩ … ∩ fi(A_{k}), a ∈ fi(Y) ↷ a ∈ fi(X)

• X → A_{1} … A_{k}, k ≥ 1, ε ∈ fi(A_{1}) ∩ … ∩ fi(A_{k}) ↷ ε ∈ fi(X)

2) fi(X_{1} … X_{n}) für X_{i} ∈ X , n ∈ ℕ • ε ∈ fi(X_{1}) ∩ … ∩ fi(X_{n}) ↷ ε ∈ fi(X_{1} … X_{n})

• ε ∈ fi(X_{1}) ∩ … ∩ fi(X_{i−1}), a ∈ fi(X_{i}) ↷ a ∈ fi(X_{1} … X_{n})

• fi(ε) = {ε}

3) fo(B) für B ∈ X • ε ∈ fo(S)

• A → αBβ, a ∈ fi(β), a ∈ Σ ↷ a ∈ fo(B)

• A → αBβ, ε ∈ fi(β), X ∈ fo(A), X ∈ Σ ∪ {ε} ↷ X ∈ fo(B)

• A → αB, X ∈ fo(A), X ∈ Σ ∪ {ε} ↷ X ∈ fo(B) \underline{Beispiel} G′_{AE} :

\begin{matrix}E → T E′ & (1) & E′ → +T E′|ε & (2, 3) & T → F T′ & (4) \\ T → ∗F T′|ε & (5, 6) & F → (E)|a & (7, 8) \end{matrix}

First- und Follow-Mengen: Look-ahead-Mengen:

\begin{aligned}& E & E′ & T & T′ & F \\ fi & ( & + & ( & ∗ & ( \\ & a & ε & a & ε & a \\ fo & ε & ε+ & + & ∗ \\ & ) & ) & ε & ε & + \\ & & & ( & ) & ε \\ & & & & & ) \end{aligned}  \begin{matrix}1 & ( a \\ 2 & + \\ 3 & ε ) \\ 4 & ( a \\ 5 & ∗ \\ 6 & + ε ) \\ 7 & ( \\ 8 & a \end{matrix}  durchschnittsfrei durchschnittsfrei durchschnittsfrei

⟹ G′_{AE} ∈ LL(1)

\underline{LL(1)-Test} la-Mengen berechnen und Alternativen auf Disjunktheit prüfen.

Deterministischer TD-Analyseautomat für G ∈ LL(1), DT A(G) Idee: Die Zugehörigkeit des Eingabesymbols zu einer la-Menge steuert die Regelauswahl. 1-llok-ahead auf der Eingabe.

Modifikation des Ableitungsschtritts des NTA(G):

• (aw, Aα, z) ⊢ (aw, βα, zi) falls π_{i} = A → β und a ∈ la(π_{i})

• (ε, Aα, z) ⊢ (ε, βα, zi) falls π_{i} = A → β und ε ∈ la(π_{i})

Folgerung: Deterministische Arbeitsweise des Analyseautomaten. Beachte: Das Eingabesymbol wird bei Ableitungsschritten nicht gelöscht!

Darstellung des DT A(G) durch die Analysetabelle von G oder die action-Funktion von G.

act : \underbrace{Σ_{ε}}_{Eingabe} × \underbrace{(N ∪ Σ_{ε})}_{Kellerspitze} → \underbrace{[\{α|A → α in G\} × [p]]}_{Behandlung NT} ∪ \underbrace{\{pop, error, accept\}}_{Behandlung T erminalsymbol}

ist definiert durch

• act(x, α) := (α, i), falls π_{i} = A → α, x ∈ la(π_{i})

• act(a, a) := pop

• act(ε, ε) := accept

• act(x, x) := error, sonst

Beachte: Look-ahead beseitigt Nichtdeterminismus \underline{und} erlaubt frühe Fehlererkennung.

Parserkonstruktion nach TD-Methode G ∈ CF G. Berechnung der la-Mengen (fi- und fo-Mengen). Analysetabelle, Eindeutigkeit prüfen ⟹ tabellengesteuerter Parser Problem: mehrdeutige Analysetabelle, d.h. G ∉ LL(1)

Transformation nach LL(1) 2 Methoden, G in eine äquivalente LL(1)-Grammatik zu transformieren (nicht immer möglich):

1) Beseitigung von Linksrekursion

2) Links-Faktorisieren

Die Methoden finden Verwendung in Parser-erzeugenden Systemen Vorsicht! Transformationen erhalten zwar die Äquivalenz, im Allgemeinen aber nicht die syntaktische Struktur (Veränderung des Ableitungsbaums).

(1) Beseitigung von Linksrekursion Definition 2.9 G ∈ CF G linksrekursiv ⟺ ∃A ∈ N, α ∈ X^{∗} : A ⇒^{+} Aα.

Folgerung: G linksrekursiv ↷ ∀k ∈ ℕ : G ist keine LL(k)-Grammatik. Grund: Wenn ein DTA A ⇒^{+} Aα simuliert, so bleibt der Eingabekopf stehen. Gleicher Look-ahead, also Endlosschleife! Keine Ableitung der Form S ⇒^{∗}_{l} wAβ ⇒^{+}_{l}

waαβ ⇒^{∗}_{l} wv

\underline{Beispiel} G_{AE} ist linksrekursiv: G_{AE} : E → E + T |T (1, 2) T → T ∗ F |F (3, 4) F → (E)|a (5, 6)

LL(1)-Test: fi(E) = fi(T) = fi(F) = {(, a} ↷ la(π_{i}) = {(, a} für i = 1, …, 4 ↷ G_{AE} ∉ LL(1).

\underline{Spezialfall} Direkte Linksrekursion und ihre Beseitigung A → Aα|β mit β ≠ A … und α ≠ ε (ergibtβα^{∗}) wird ersetzt durch A → βA′ und A′ → αA′|ε Folgerung: L(G) unverändert, jedoch neue syntaktische Struktur.

A^{A} ^{α}^{A} ^{α}^{β}  ⟹^{Transformation}  ^{A}^{β} ^{A′}^{α} ^{A′}^{α} ^{A′}^{β}

Kein Problem bei assoziativen Operatoren wie +, ∗, da Semantik invariant.

\underline{Beispiel} Die Beseitigung der direkten Linksrekursion in G_{AE} ergibt die LL(1)- Grammatik G′_{AE}.

\underline{Allgemeiner Fall} indirekte Linksrekursion A → A_{1}α_{1}| … A_{1} → A_{2}α_{2}| …

⋮ A_{n} → Aα_{n+1}| …

Idee: Beseitigung durch Transformation in Greibach Normalform (GNF). GNF: Alle Regeln von der Form A → aβ_{1} … β_{n} (β_{1} ≠ S) oder S → ε. Also fi(βα) ∩ fi(γα) = ∅. Beachte: Beseitigung von Linksrekursion ergibt nicht notwendigerweise eine LL(1)-Grammatik. Grund: Jede G ∈ CF G ist äquivalent in GNF transformierbar, aber L(LL(k)) ⫋ L(LL(k + 1)) ⫋ L(DP DA)) ⫋ L(P DA) = CF L.

Komplexität der LL(1)-Analyse G ∈ LL(1) ↷ G nicht linksrekursiv. Der DT A(G) mit Eingabe von w ∈ Σ^{∗}:

• |w| Vergleichsschritte + 1 Erkennungsschritt für das Ende des Wortes

• maximal |N| aufeinanderfolgende Ableitungsschritte

↷ maximal |N| · (|w| + 1) Transitionen. Maximale Kellerlänge: max{|α| | A → α in P } · |N| · (|w| + 1) Also: linearer Zeit- und Platzbedarf

(2) Links-Faktorisieren

\underline{Beispiel} statement → if condition then statement else statement| if condition then statement

Idee: Verschieben der Entscheidung bis Alternative erkennbar: A → αβ|αγ ersetzen durch A → αA′ und A′ → β|γ.

TD-Analyse mit rekursiven Prozeduren Idee: Keine explizite Kellerbenutzung, sondern implizite Verwendung des Laufzeitkellers durch den Einsatz von rekursiven Prozeduren. Vorteil: leichte Programmierung (Wirth) Spezialfall: G ∈ LL(1), wie z.B. G′_{AE}

(1) Analyseverfahren durch rekursiven Abstieg (ohne la-Mengen), ”Recursive descent parser” Methode: A ∈ N ↦ A(), parameterlose Prozedur zur Simulationen eines Ableitungsschrittes Annahme: Alternativen durch Eingabesymbol entscheidbar Eingabe: sym: Variable für das Eingabesymbol

nextsym: zum Lesen des nächsten Eingabesymbols Ausgabe: print(i): Ausgabe einer Regelnummer Beispiel: siehe Folie

(2) Zusätzliche Verwendung der la-Mengen Vorteil: bessere Kontrolle der Regelverwendung, frühere Fehlererkennung

2.2 Bottom-Up-Analyse, LR(k)-Grammatik

Idee: Bottom-Up-Berechnung des Ableitungsbaums in Form einer gespiegelten Rechtsanalyse durch einen Kellerautomaten. Shift-Schritte: Verschieben von Eingabesymbolen auf den Keller Reduce-Schritte: Umkehrung von Ableitungsschritten (rechte Seite durch linke ersetzen) ⇝ Shift-Reduce-Verfahren Definition 2.10 Der (nichtdeterministische) Bottom-Up-Analyseautomat von G ∈ CF G, Bezeichnung NBA(G): Eingabelalphabet: Σ Kelleralphabet: X Ausgabealphabet: [p] Konfigurationsmenge: X^{∗} × Σ^{∗} × [p]^{∗} (Kellerspitze rechts) Transitionen:

• Shift-Schritt: (α, aw, z) ⊢ (αa, w, z) für a ∈ Σ

• Reduce-Schritt: (βα, w, z) ⊢ (βA, w, zi) falls π_{i} = A → α

Anfangskonfiguration für ein w ∈ Σ^{∗}: (ε, w, ε) Endkonfiguration: (S, ε, z)

Satz 2.4 Der NBA(G) berechnet gespiegelte r-Analysen, d.h. für w ∈ Σ^{∗} und

z ∈ [p]^{∗} gilt: z ist eine r-Analyse von w ⟺ (ε, w, ε) ⊢^{∗} (S, ε, \overleftarrow{z}) (Dabei ist \overleftarrow{z} die Spiegelung von z.)

Nichtdeterminismus:

1) Shift- oder Reduce-Schritt?

2) Reduce-Schritt: linker Henkelrand

3) Reduce-Schritt: linke Regelseite

4) Analyseende

Ziel: Nichtdeterminismus durch k-look-ahead auf der Eingabe beseitigen.

LL(k)-Grammatiken Generalvorraussetzung: G startsepariert, d.h. S nur in S → A mit A ≠ ε. Jede G ∈ CF G läßt sich durch Hinzufügen von S′ → S in eine startseparierte Grammatik transformieren. (Regelnummer: 0) Folgerung: (S′, ε, z) ist eine Endkonfiguration, die nicht erneut in eine weitere Endkonfiguration übergehen kann (Analyseende).

Beseitigung des restlichen Nichtdeterminismus durch LR(k)-Grammatiken.

Definition 2.11 (LR(k)-Grammatiken) Sei G ∈ CF G, startsepariert durch S′ → S, k ∈ ℕ. G ∈ LR(k) ⟺ Für

alle Rechtsableitungen der Form S↗ ↘^{r}_{r} αAw ⇒^{∗}_{r} αβw α′A′w′ ⇒^{∗}_{r} αβv mit first_{k}(w) = first_{k}(v)

gilt: α′ = α, A′ = A, w′ = v.

Folgerung: Der BU-Analyseautomat kann mit k-look-ahead auf der Eingabe die Transition entscheiden.

LR(0)-Grammatiken k = 0 : ↷ Entscheidung ohne look-ahead, allein durch Kellerinhalt αβ. Abstraktion endlicher Information aus αβ, welche für die Entscheidung ausreicht.

Definition 2.12 (LR(0)-Auskünfte, LR(0)-Mengen) Sei G ∈ CF G mit S′ → S und S′ ⇒^{∗}_{r} αAw ⇒_{r} αβ_{1}β_{2}w. Dann heißt [A → β_{1} · β_{2}] eine LR(0)-Auskunft für αβ_{1}. Für γ ∈ X^{∗} bezeichnet LR(0)(γ) die Menge aller LR(0)-Auskünfte für γ, die sogenannte LR(0)-Menge von γ.

Folgerung:

1) LR(0)(γ) endlich

2) LR(0)(G) := {LR(0)(γ)|γ ∈ X^{∗}} endlich

3) [A → β_{1}·] ∈ LR(0)(γ) signalisiert Reduktionsmöglichkeit (αβ_{1}, w, z) ⊢ (αA, w, zi) für π_{i} = A → β_{1} und γ = αβ_{1}.

4) [A → β_{1} · β_{2}] ∈ LR(0)(γ) mit β_{2} ≠ ε bedeutet Shift-Möglichkeit wegen unvollständigem Henkel (rechte Regelseite).

5) G ∈ LR(0) ⟺ Die LR(0)-Mengen enthalten keine wiedersprüchlichen Auskünfte (immer eindeutig).

Berechnung der LR(0)-Mengen einer Grammatik

Satz 2.5 G ∈ CF G mit S′ → S. G reduziert. Dann gilt:

1) LR(0)(ε) ist die kleinste Menge, welche

a) [S′ → ·S] enthält und

b) mit [A → ·Bδ] und B → β in G auch [B → ·β] enthält

2) LR(0)(aX) mit X ∈ X ist die kleinste Menge, welche

a) [A → β_{1}X · β_{2}] enthält, falls [A → β_{1} · Xβ_{2}] ∈ LR(0)(α)

b) und mit [A → γ · Bδ] und B → β in G auch [B → ·β] enthält

\underline{Beispiel} Siehe Folie 2.11 ⟹ Keine widersprüchlichen Auskünfte ⟹ G ist LR(0)-Grammatik.

Die goto-Funktion G ist LR(0)-Grammatik ↷ LR(0)(γ) liefert Shift-Reduce-Entscheidung für den BU-Analyseautomat mit Keller γ. Neues Kelleralphabet: LR(0)(G) statt X.

Beachte: LR(0)(γX) ist bestimmt durch LR(γ) und X, aber unabhängig von γ.

goto : LR(0)(G) × X → LR(0)(G) ist definiert durch goto(I, X) := I′ ⟺ ∃γ ∈ X^{∗} : I = LR(0)(γ), I′ = LR(0)(γX).

Berechnung der LR(0)-Mengen und goto-Funktion durch Potenzmengenkonstruktion des nichtdeterministischen endlichen Automaten.

Sei G ∈ CF G, G startsepariert mit S′ → S. Konstruktion eines 𝔄(G) ∈ NF A_{ε}: Zustandsmenge: Q := {[A → β_{1} · β_{2}]|A → β_{1}β_{2} in G} Eingabealphabet: X ∪ Σ Anfangszustand: q_{0} := [S′ → S] (Endzustandsmenge irrelevant, F = Q) Transitionsfunktion δ : Q × X_{ε} → P(Q) δ([A → β_{1} · Xβ_{2}], X) ∋ [A → β_{1}X · β_{2}] δ([A → β_{1} · Bβ_{2}], ε) ∋ [B → ·γ] falls B → γ

Potenzmengenkonstuktion (Thompson)

Konstruktion von { \atop 𝔄(G)} = ⟨Q̂, X , δ̂, q̂_{0}, ∅⟩ ∈ DF A.

Erweiterte Transitionsfunktion \overline{δ} : P(Q) × X^{∗} → P(Q) \overline{δ}(T, ε) := ε(T) \overline{δ}(T, wa) := ε(⋃_{q∈\overline{δ}(T,w)} δ(q, a)) Q̂ := \{\overline{δ}(\{[S′ → ·S]\}, α)|α ∈ X^{∗}\} δ̂(T, X) := \overline{δ}(T, X) q̂_{0} := ε({[S′ → ·S]}) Dann gilt: Q̂ = LR(0)(G), δ̂ = goto

Konstruktion des deterministischen BU-Analyseautomat für G ∈ LR(0) Hilfsmittel: LR(0)(G) und goto-Funktion Die action-Funktion von G gibt die Shift-Reduce-Entscheidung an: act : LR(0)(G) → {shift, red i, accept, error|i ∈ [p]}

act(I) := \{ \begin{matrix}red i & , falls π_{i} = A → α und [A → α·] ∈ I \\ shift & , falls [A → α · Xβ] ∈ I \\ accept & , falls [S′ → S·] ∈ I \\ error & , falls I = ∅ \end{matrix}

Eindeutig bei LR(0).

Die Funktionen act und goto bilden die LR(0)-Analysetabelle von G. Diese Tabelle bestimmt den \underline{LR(0)-Analyseautomaten, DBA(G)}: Eingabealphabet: Σ Kelleralphabet: Γ := LR(0)(G) Ausgabealphabet: Δ := [p] ∪ {0} ∪ {error} Konfigurationsmenge: Γ^{∗} × Σ^{∗} × Δ∗ Transitionen:

• Shift-Schritt: (αI, aw, z) ⊢ (αII′, w, z) falls act(I) = shift und goto(I, a) = I′

• Reduce-Schritt: Abkürzung: wa_{1} … a_{n}|n := w (Entfernen der letzen n Zeichen) (αI, w, z) ⊢ (α̃ĨI′, w, zi) falls act(I) = red i, π_{i} = A → X_{1} … X_{n}, αI|n = α̃Ĩ und goto(I, A) = I′

• Accept-Schritt: (I_{0}I, ε, z) ⊢ (ε, ε, z0) falls act(I) = accept

• Fehlererkennung: (αI, w, z) ⊢ (ε, ε, z error), sonst

Anfangskonfiguration für w ∈ Σ^{∗} : (I_{0}, w, ε) mit I_{0} = LR(0)(ε)

Folgerung: Wenn LR(0)(G) konfliktfrei, also act eindeutig, so arbeitet der LR(0)- Analyseautomat deterministisch und es gilt für w ∈ Σ^{∗} und z ∈ [p]^{∗}:

• (I_{0}, w, ε) ⊢^{∗} (ε, ε, z0) ⟺ \overleftarrow{z} ist Rechtsanlyse von w

• (I_{0}, w, ε) ⊢^{∗} (ε, ε, z error) ⟺ w ∉ L(G)

\underline{Beispiel} w = aac bestimmt die folgende Berechnung: (0, aac, ε) ⊢ (04, ac, ε) ⊢ (044, c, ε) ⊢ (0446, ε, ε) ⊢ (0448, ε, 6) ⊢ (048, ε, 65) ⊢ (03, ε, 655) ⊢ (01, ε, 6552) ⊢ (ε, ε, 65520)

Überprüfung: S →^{0} S′ →^{2} C →^{5} aC →^{5} aaC →^{6} aac

SLR(1)-Analyse S - simple, look-ahead mit einem Symbol

\underline{Beispiel} siehe Folie CB 2-15

Konflikttypen: RR (reduce/reduce)-Konflikt und SR (shift/reduce)-Konflikt Im Beispiel nur SR-Konflikte. Ziel: Beseitigung des Konflikts durch das Eingabesymbol (look-ahead) \underline{Beobachtung}

1) [A → β_{1} · aβ_{2}] ∈ LR(0)(αβ_{1}) ↷ S ⇒^{∗}_{r} αAw ⇒_{r} \underbrace{αβ_{1}}_{Keller} \underbrace{a}_{Eingabesymbol} β_{2}w

Also: Shift nur bei Eingabe von a.

2) [A → β·] ∈ LR(0)(αβ) ↷ S ⇒^{∗}_{r} αAaw ⇒_{r} \underbrace{αβ}_{Keller} \underbrace{a}_{Eingabesymbol} w ↷

a ∈ fo(A) Also: Reduktion mit A → β nur falls a ∈ fo(A).

Für obiges Beispiel: I_{1}: Shift bei Eingabe von +, Accept bei Eingabe von $ ($ entspricht dem rechten Eingaberand ˆ= leeres Wort ε) I_{2}: Shift bei Eingabe von ∗, Reduce bei Eingabe von aus fo(E) = \{\underbrace{ε}_{ˆ=$}, +,)\}

I_{9}: Shift bei Eingabe von ∗, Reduce bei Eingabe von $, +,) ⟹ Konflikte beseitigt. Weiterer Vorteil: Frühere Fehlererkennung durch genauere Kontrolle der Aktionen.

SLR(1)-action-Funktion act : LR(0)(G) × (Σ ∪ {$}) → {shift, red i, accept, error|1 ≤ i ≤ r}

act(I, a) := \{ \begin{matrix}shift & , falls [A → α · aβ] ∈ I \\ red i & , falls π_{i} = A → α, [A → α·] ∈ I und a ∈ fo(A) \\ accept & , falls [S → S′] ∈ I und a = $ \\ error & , sonst \end{matrix}

Definition 2.13 G ∈ SLR(1) ⟺ act(I, a) eindeutig.

LR(1)-Analyse Nicht immer sind Konflikte über follow-Mengen lösbar. Beispiel: Folie CB 2-17 Verfeinerung der LR(0)-Auskünfte durch Mitführen der möglichen look-ahead-Symbole.

Definition 2.14 (LR(1)-Auskünfte und LR(1)-Mengen für G ∈ CF G) 1) Wenn S ⇒^{∗}_{r} αAaw ⇒_{r} αβ_{1}β_{2}aw, so [A → β_{1} · β_{2}, a] ∈ LR(1)(αβ_{1})

2) Wenn S ⇒^{∗}_{r} αA ⇒_{r} αβ_{1}β_{2}, so [A → β_{1} · β_{2}, $] ∈ LR(1)(αβ_{1})

LR(1)(G) := {LR(1)(γ)|γ ∈ X^{∗}}

Berechnung der LR(1)-Mengen Modifikation der Berechnung von LR(0)(G) unter Berücksichtigung des Rechtskontexts

• LR(1)(ε):

– [S′ → ·S, $]

– Wenn [A → ·Bδ, x], B → β in G, x ∈ Σ ∪ {$} und y ∈ fi(δx), so [B → ·β, y] ∈ LR(1)(ε)

• LR(1)(αX):

– Wenn [A → β_{1}·Xβ_{2}, x] ∈ LR(1)(α), so [A → β_{1}X·β_{2}, x] ∈ LR(1)(αX)

– Wenn [A → γ · Bδ, x] ∈ LR(1)(αX), B → β in G und y ∈ fi(δx), so [B → ·β, y] ∈ LR(1)(αX)

Die LR(1)-action-Funktion von G act : LR(1)(G) × (Σ ∪ {$} → {shift, accept, error} ∪ {red i|1 ≤ i ≤ r} sei definiert durch

act(I, x) := \{ \begin{matrix}red i & , falls π_{i} = A → α und [A → α·, x] ∈ I \\ accept & , falls x = $ und [S′ → S·] ∈ I \\ shift & , falls x ≠ $ und [A → α_{1} · xα_{2}, y] ∈ I \\ error & , sonst \end{matrix}

Dann gilt: G ∈ LR(1) ⟺ act eindeutig (konfliktfrei).

\underline{Beispiel} Folie CB 2-19 \underline{LALR(1)-Analyse} Beseitigung von Konflikten nach LR(1) zu aufwendig. Im Beispiel: |LR(0)(G)| = 11, |LR(1)(G)| = 15. Algol60: |LR(0)(G)| = 100, |LR(1)(G)| = 1000. Beobachtung: Informationsredundanz bei LR(1)(G_{2})

Definition 2.15 I_{1}, I_{2} ∈ LR(1)(G) heißen LR(0)-äquivalent, I_{1}_{0}I_{2} ⟺ die ”LR(0)-Anteile” von I_{1} und I_{2} sind gleich.

\underline{Beispiel} I′_{4}_{0}I′_{11}, I′_{5}_{0}I′_{12}, I′_{7}_{0}I′_{13}, I′_{8}_{0}I′_{10}

Folgerung: |LR(1)(G)/_{0}| = |LR(0)(G)| Oft können LR(0)-äquivalente LR(1)-Informationen vereinigt werden, ohne daß die Konfliktlösbarkeit verloren geht.

Definition 2.16 I ∈ LR(1)(G) bestimmt eine LALR(1)-Menge ⋃{I′ ∈ LR(1)(G)|I′_{0}I}.

Es gilt: |LALR(1)(G)| = |LR(0)(G)|. Aber im Unterschied zu LR(0)-Mengen enthalten LALR(1)-Mengen look-ahead-Symbole zur Lösung von Konflikten. Die LALR(1)-action-Funktion von G ist analog zu LR(1) definiert.

Definition 2.17 G ∈ LALR(1) ⟺ LALR(1)-action-Funktion ist eindeutig.

\underline{Beispiel} Die LALR(1)-Mengen von G_{2}, LALR(1)(G_{2}) := \{I_{i}^{(1/0)}|1 ≤ i ≤ 9\} I_{i}^{(1/0)} = I′_{i} für i ∈ {0, 1, 2, 3, 6, 9} I_{4}^{(1/0)} = I′_{4}∪I′_{11} : [L → ∗·R, = /$] [R → ·L, = /$] [L → ·∗R, = /$] [L → ·a, = /$] I_{5}^{(1/0)} = I′_{5} ∪ I′_{12} : [L → a·, = /$] (Vergröberung von I′_{12}) I_{7}^{(1/0)} = I′_{7} ∪ I′_{13} : [L → ∗R·, = /$] I_{8}^{(1/0)} = I′_{8} ∪ I′_{10} : [R → L·, = /$] Die LR(1)-action-Funktion zeigt, daß beim Übergang zu LALR(1) keine Konflikte auftreten ⟹ G_{2} ∈ LALR(1).

Die LR(1)-goto-Funktion überträgt sich auf LALR(1)(G), weil für LR(1)-Mengen

I_{1} und I_{2} gilt: I_{1}_{0}I_{2} ↷ goto(I_{1}, x)_{0}goto(I_{2}, x).

Grund: Der ”LR(0)-Kern” von LR(1)(αX) ist durch den ”LR(0)-Kern” von LR(1)(α) und X vollständig bestimmt.

2.3 Bottom-Up-Analyse mehrdeutiger Grammatiken

Es gilt für G ∈ CF G : G mehrdeutig ↷ G ∉ LR = ⋃_{k∈ℕ} LR(k). Mehrdeutigkeit: natürliches Beschreibungsmittel bei Programmiersprachen zur Vermeidung aufwendiger Klammerung. Auflösung durch Regeln für Präzendenz und Assoziativität von Op-Symbolen (allgemeiner: von Synt. Konstruktionen).

\underline{Beispiel} G_{AE}^{m} : E → E + E|E ∗ E|(E)|id

Mehrdeutige Grammatiken G_{AE}^{m}, Präzedenz: ∗ vor +, Assoziativität: links. Konflikte: I_{1} SLR(1)-lösbar, I_{7}, I_{8} nicht LR-lösbar

\underline{Beispiel-Rechnung:} I_{0} a + a ∗ a, I_{0}I_{3} + a ∗ a, I_{0}I_{1} + a ∗ a, I_{0}I_{1}I_{4} a ∗ a, I_{0}I_{1}I_{4}I3 ∗ a, I_{0}I_{1}I_{4}I_{7} ∗ a ⟹ shift oder reduce?

\underline{Beispiel} Mehrdeutigkeit bei Verzweigungen (”dangling else”) S → iSeS|iS|a|b if b then \underbrace{\underbrace{if b then a}_{Klammerung 1} else a}_{Klammerung 2}

Klammerung 1 macht man nicht, Klammerung 2 ist Standard act(I_{4}, e) = shift

3 Semantische Analyse, Attributgrammatiken

Ergebnis der syntaktischen Analyse: Ableitungsbaum Kontextabhängige Eigenschaften:

• Deklariertheit von Bezeichnern

• Typinformationen

nicht durch CF G beschreibbar. Festlegung dieser Eigenschaften durch

• Gültigkeitsregeln: Gültigkeitsbereich einer Deklaration

• Sichtbarkeitsregeln: Sichtbarkeit im Gültigkeitsbereich

• Typvorschriften: Typkonsistenz

\underline{Statische Semantik:} Kontextabhängige, laufzeitunabhängige Eigenschaften eines Programms. Formale Beschreibung durch Attributgrammatiken. Idee: CF G+ semantische Regeln ⇝ Zusatzinformationen für den Ableitungsbaum Semantische Analyse = Attributberechnung Ihr Ergebnis: attributierter Ableitungsbaum Grundlage für die anschließende Synthesephase.

Attributgrammatiken Idee: Attribute für A ∈ N, semantische Regeln für ihre Berechnung synthetische Attribute: Bottom-Up-Berechnung inherite^{1} Attribute: Top-Down-Berechnung ↷ belibiger Informationstransfer im Ableitungsbaum Attributwerte: Symboltabellen, Typen, Code, Fehler, … Breite Anwendbarkeit von Attributgrammatiken, syntaxgerichtete Programmierung Automatische Attributauswertung in Compilergeneratoren \underline{Hist.:} Knuth[68], Semantics of CFLs

\underline{Beispiel} Folie CB 3-1

B → 0  v.0 = 0
B → 1  v.0 = 1
L → B v.0 = v.1  l.0 = 1
L → LB v.0 = 2 ∗ v.1 + v.2 l.0 = l.1 + 1
N → L v.0 = v.1
N → L.L v.0 = v.1 + v.3/2^{l.3}

G_{B} erzeugt Binärzahlen mit und ohne Punkt, N Startsymbol Synthetische Attribute: B, N: v (value) L: v, l (value, length)

1vererbende

Semantische Regeln: Attributgleichungen mit Attributvariablen Index i: i-tes Symbol Ziel: Bestimmung des Zahlenwertes Attributwerte von v: rationale Zahlen (A^{v} = ℚ) Attributwerte von l: natürliche Zahlen (A^{l} = ℕ)

2. Attributierungsart von G_{B} mit synthetischen und inheriten Attributen Zusätzlich inherites Attribut für \underline{B}its und \underline{L}isten: p (position) \underline{Beispiel} Folie CB 3-3

Berechnung des Wurzelattributs:

1) Längen ↑

2) Position ↓

3) Werte ↑

Definition 3.1 (Attributgrammatik) Sei G = ⟨N, Σ, P, S⟩ ∈ CF G. Sei Att eine Menge von Attributen, sei A = (A^{α}|α ∈ Att) eine Familie von Attributwertungen und sei att : X → P(Att) eine Attributzuordnung. Sei Att = Syn ·∪Inh eine Zerlegung in Teilmengen synthetischer und inheriter Attribute, so daß att in syn : X → P(Syn) mit syn(X) = att(X) ∩ Syn und inh : X → P(Inh) mit inh(X) = att(X) ∩ Inh zerfällt. Eine Regel π = X_{0} → X_{1}X_{2} … X_{r} ∈ P bestimmt die Menge V ar_{π} := {α.i|α ∈ att(X_{i}), 0 ≤ i ≤ r} der formalen Attributvariablen von π mit den Teilmengen IV ar_{π} := {α.i|(i = 0 und α ∈ syn(X_{i})) oder (1 ≤ i ≤ r und α ∈ inh(X_{i}))} und OV ar_{π} := V ar_{π} \ IV ar_{π} der Innen- und Außenvariablen. Eine Attributgleichung von π (semantische Regel) hat die Form α.i = f(α_{1}.i_{1}, …, α_{n}.i_{n}) mit α.i ∈ IV ar_{π}, α_{1}.i_{1}, …, α_{n}.i_{n} ∈ OV ar_{π}, f : A^{α_{1}} × A^{α_{2}} × … × A^{α_{n}} → A^{α} und n ∈ ℕ. Sei E_{π} eine (endliche) Menge von Attributgleichungen, in der jede Innenvariable genau einmal vorkommt. Dann heißt 𝔄 = ⟨G, {E_{π}|π ∈ P }⟩ eine Attributgrammatik, Bezeichnung: 𝔄 ∈ AG.

Definition 3.2 (Attributgleichungssystem eines Ableitungsbaums) Sei 𝔄 = ⟨G, {E_{π}|π ∈ P }⟩ ∈ AG. 𝔄 induziert für jeden Ableitungsbaum t von G ein Attributgleichungssystem E_{t}:

Sei Kn(t) die Menge der Knoten von t. Sie bestimmt die Menge

V ar_{t} := {α.k|k ∈ KN(t) markiert durch X ∈ X , α ∈ att(X)} der aktuellen Attributvariablen von t. Wird an einem inneren Knoten (kein Blatt knoten) k_{0} ∈ Kn(t) die Regel π = X_{0} → X_{1}X_{2} … X_{r} angewandt und sind k_{1}, …, k_{n} ∈ Kn(t) die entsprechenden Nachfolgeknoten, so erhält man das Attributgleichungssystem E_{k_{0}} von k_{0} aus E_{π} durch die Indextransformation (i → k_{i}|0 ≤ i ≤ r) bei den Attributvariablen (formale → aktuelle Parameter).

Dann ist E_{t} := ⋃{E_{k}|k innerer Knoten von t}.

Beachte: Zu jeder aktuellen Attributvariablen α.k, ausgenommen die inheriten der Wurzel und die synthetischen der Blätter, gibt es genau eine Gleichung α.k = …

\underline{Annahme}

• keine inheriten Attribute des Startsymbols (ausgenommen inkrementelle Übersetzung)

• synthetische Attribute der Terminalsymbole vom Scanner geliefert

Lösbarkeit von E_{t}: E_{t} kann keine, genau eine oder mehrere Lösungen haben.

\underline{Beispiel} G enthalte die Regeln A → u \underbrace{B}_{Symbol i} v und B → w. Ferner: α ∈ syn(B)

und β ∈ inh(B). Attributgleichungen: … β.i = f(α.i) α.0 = g(β.0) … Also existiert in E_{t} eine zirkuläre Abhängigkeit: β.k = f(α.k) α.k = g(β.k) Für A^{α} = A^{β} = ℕ, g = id_{ℕ} ↷ β.k = f(β.k)

1) f(x) = x + 1 ↷ keine Lösung

2) f(x) = 2x ↷ eine Lösung (β.k = 0)

3) f(x) = x ↷ unendlich viele Lösungen

Folgerung: Zirkularitäten sind unerwünscht. Sie entstehen erst in E_{t} := ⋃{E_{k}|k innerer Knoten von t}, nicht in E_{π}.

Definition 3.3 𝔄 ∈ AG heißt zirkulär ⟺ Es gibt einen Ableitungsbaum t mit zirkulärem Attributgleichungssystem E_{t}, d.h. eine aktuelle Attributvariable hängt von sich selbst ab.

Satz 3.1 Es ist entscheidbar, ob 𝔄 ∈ AG zirkulär ist. Zeitkomplexität: O(2^{n}) für n = |𝔄|.

Hilfsmittel für Zirkularitätstests und Attributberechnung

Definition 3.4 Sei 𝔄 ∈ AG und t ein Abbleitungsbaum von 𝔄. E_{t} bestimmt den Abhängigkeitsgraphen DG (Dependency graph):

Knotenmenge K_{n}(DG_{t}) := V ar_{t}

Kantenmenge (x_{1}, x_{2}) ∈ Kan(DG_{t}) ⟺ x_{2} = f(…, x_{1}, …) ∈ E_{t}

Also: [figure: x_{1}; x_{2}] in DG_{t}, wenn x_{2} direkt von x_{1} abhängt.

Attributberechnung

1) E_{t} als Termersetzungssystem, TD-Berechnung: Keine Zirkularität ⟹ Termination mit eindeutiger Lösung

2) BU-Berechnung: Variablen durch Werte ersetzen und Terme ausrechnen 3) Uniforme Berechnung: Unabhängigkeit vom Ableitungsbaum

a) Berechnungspläne für (E_{π}|π ∈ P) aufstellen [Kennedy/Warren]

b) Rekursive Prozeduren/Funktionen für (E_{π}|π ∈ P) [Jourdan/Gallie] Idee: Jeder synthetischen Attributvariablen wird eine Prozedur/Funktion zugeordnet mit den inheriten Attributvariablen als Parameter. Verwendung vor allem in der automatischen Compilererzeugung

4) Spezialfälle: SAG, LAG mit Attributberechnungen während der Syntaxanalyse

S-Attributgrammatiken

Definition 3.5 𝔄 ∈ AG heißt S-Attributgrammatik, 𝔄 ∈ SAG, wenn Inh = ∅, also Att = Syn.

Folgerung: BU-Berechnung der Attributwerte Spezialfall: Bestimmung des Wurzelattributs Idee: Durchführung während der BU-Syntaxanalyse

A → BaD

I_{1} v3 v.0 = f(…
I_{7}v2 w.0 = f(…

I_{8}v1

I_{2}  Beim Reduce-Schritt werden simultan die Werte der synthetischen

Attribute von A aus den Werten unter v1 v2 v3 berechnet (Records) Accept-Schritt: Werte der Wurzelattribute ausgeben

\underline{Beispiel} Stackcode für arithmetische Ausdrücke E → (E + E) | (E ∗ E) | id | num Attribut c: Stackcode a: Adresse z: Zahl

E → (E + E) c.0 = c.2; c.4; ADD (auch +)
E → (E ∗ E) c.0 = c.2; c.4; MULT (auch ∗)
id  c.0 = LOAD a.1
num  c.0 = LIT z.1

Werte von a.1, z.1: lexikalische Attribute, die mit dem Token vom Scanner übergeben werden: (id, x) (num, 7)

((3 + x) ∗ (y + 5)) ⇝ 3; x; +; y; 5; +; ∗ Scanner: ((< num, 3 > + < id, x >) ∗ (< id, y > + < num, 5 >))

Codegenerierung durch Attributsauswertung während der Syntayanalyse

a) Shift: Aufruf des Scanners durch ”nextsym”

1) Token ↦ LR(0).Menge mit goto

2) lexikalisches Attribut ebenfalls auf Analysekeller

b) Reduce:

1) Reduktion auf dem Analysekeller

2) Simultane Attributberechnung

c) Accept: Wurzelattribute ausgeben

\underline{Beispiel} \begin{matrix}num & 3 \\ ( \\ ( \end{matrix} ⟹^{Reduce} \begin{matrix}id & x \\ + \\ E & LIT 3 \\ ( \\ ( \end{matrix} ⟹^{Reduce} \begin{matrix}) \\ E & LOAD x \\ + \\ E & LIT 3 \\ ( \\ ( \end{matrix}

⟹^{Reduce} \begin{matrix}) \\ E & LIT 3; LOAD x; ADD \\ ( \end{matrix}

Ergebnis: LIT 3; LOAD x; ADD; LOAD y; LIT 5; ADD; MUL

\underline{Beispiel} Berechnung des abstrakten Syntaxbaums Konkrete und abstrakte Syntax π = A_{0} → w_{0}A_{1}w_{1} … A_{r}w_{r} repräsentiert ein Op.-Symbol F_{π} vom Typ A_{1}x … xA_{r} → A_{0} (A_{i} := Sorte|Typ)

Bemerkung: ”Verkleben” der Regeln zu einem Ableitungsbaum entspricht der funkt. Applikation der zugehörigen Op.-Symbole. Folgerung: Ableitungsbaum vereinfacht sich zum abstrakten Syntaxbaum (AST). Nur dieser ist für die Übersetzung erforderlich.

Konkrete Syntax: benutzerfreundlich: ”Mix-Fix-Notation” (synthetischer Zucker) Verwendung natürlicher Sprache für Terminalsymbole von CFG. Abstrakte Syntax: Darstellungsunabhängige algebraische Struktur

\underline{Beispiel} Folie CB 3-6 id=num+id; if id<num then id=num+id end

\underline{Aufgabe} Berechnung des AST während der BU-Analyse \underline{Methode} S-Attributgrammatik

Darstellung des Aufbaus von abstrakten Syntaxbäumen durch Konstruktion von Graphen

a) \underline{Graphen}

a ∈ Adr unendliche Menge von Adressen für Speicheradressen (Heap) Ω Operationssymbolalphabet mit Stelligkeit f^{(n)} ∈ Ω = {assign^{(1)}, seq^{(2)}, cond^{(2)}, less^{(2)}, plus^{(2)}, ident^{(0)}, number^{(0)}} Kno Menge der Ω-Knoten k ∈ Kno := {(a, f, a_{1}, …, a_{n})|a, a_{i} ∈ Adr, f ∈ Ω} [figure: f · . . . ·; a; a_{1}; a_{n}] Graph: Menge von Knoten mit einer Wurzel G ∈ Graph := {(a, K)|a ∈ Adr, K ⊆ Kno}

b)

Konstruktorfunktionen für Graphen f^{(n)} ∈ Ω ↦ mk − f : Graph^{n} → Graph mk − f((a_{1}, K_{1}), …, (a_{n}, K_{n})) := (a, K) mit \underline{neuer} Adresse a und K := {a, f, a_{1}, …, a_{n})} ∪ ⋃_{i=1}^{n} K_{i}

S-Attributierung von G_{S} Wurzeladressen als S-Attribute im Analysekeller, Heap anstelle eines Ausgabebandes

\underline{Beispiel} Typberechnung für arithmetische Ausdrücke T yp := {int, real} mit max : T yp^{2} → T yp bzgl. int < real

L-Attributgrammatiken

Definition 3.6 𝔄 = ⟨G, (E_{π}|π ∈ P)⟩ ∈ AG ist eine L-Attributgrammatik, 𝔄 ∈ LAG ⟺ Für jede Attributgleichung α.i = f(…, β.j, …) gilt: α ∈ Inh, β ∈ Syn ↷ j < i

\underline{Beispiel} (DG_{π}) Erlaubter Abhängigkeitsgraph:

[figure: ∘A•; ∘B•; ∘C•; ∘ inherites Attribut; • synthetisches Attribut]

Folgerung: G ∈ LAG nicht zirkulär. Attributberechnung in ”depth-first, left to right-order” Baumreise mit zwei Knotenbesuchen

1) top-down: inherite Attribute

2) bottom-up: synthetische Attribute

Auswertungsreihenfolge:

[figure: ∘A•; ∘B•; ∘C•]

Syntaxanalyse mit L-Attributierung Sei 𝔄 = ⟨G, (E_{π}|π ∈ P)⟩ ∈ LAG mit G ∈ LL(1). \underline{Ziel} Erweiterung der Top-Down-Analyse zur Berechnung der synthetischen Wurzelattribute.

\underline{Methode} Expansion von A ∈ N auf Analysetabelle so gestalten, daß spätere Reduktion möglich, TD → inherite Attribute, BU → synthetische Attribute Kelleralphabet: ⋃_{π∈P} (LR(0)_{π}(G) × V al_{π}) mit LR(0)_{π}(G) := {[A → α · β]|π = A → αβ} und V al_{π} := {val_{π}|val_{π} : V ar_{π} −−→ ”Wertmenge (Attribute)”} \underline{Arbeitsweise} 3 Fälle

1) ”expand”-Schritt mit Berechnung inheriter Attribute

[A→X_{1}...X_{i−1}·Bγ] ^{val}^{•}^{•}^{•}  ⟹ ^{[A→X_{1}...X_{i−1}·Bγ]} ^{val}^{[B→·β]}  ^{val′}^{•}^{•}^{•} Dabei ist B → β wegen G ∈ LL(1) durch Eingabe-look-ahead bestimmt.

val′ belegt die inheriten Attributvariablenvon B nach den Attributgleichungen für A → X_{1} … X_{i−1}Bγ. Sei α ∈ inh(B) und α.i = t ∈ E_{X_{1}...X_{i−1}Bγ}, so ist val′(α.0) = v̂al(t), wobei v̂al die homomorphe Fortsetzung von val auf Terme (”einsetzen und ausrechnen”) ist.

•A∘^{•X_{1}•} ^{•X_{i−1}•} ^{| ∘ B∘} ^{∘γ}^{…}  ⟹  ^{•A∘}^{•X_{1}•} ^{•X_{i−1}•} ^{•B∘} ^{∘γ}^{…}  _{|β} 2) ”match”-Schritt

[A→γ·aγ′]  ^{val}^{•}^{•}^{•}  ⟹ ^{[A→γa·γ′]}  ^{val}^{•}^{•}^{•}

falls a nächstes Eingabesymbol ist

3) ”reduce”-Schritt mit Berechnung synthetischer Attribute

[A→X_{1}...X_{i−1}·Bγ] ^{val}^{[B→β·]}  ^{val′}^{•}^{•}^{•}  ⟹ ^{[A→X_{1}...X_{i−1}B·γ]} ^{val′′}^{•}^{•}^{•} val′′ erweitert val um die synthetischen Attribute von B

val′′(α.i) = \{ \begin{matrix}v̂al(t) & , falls α.0 = t ∈ E_{B→β} \\ val(α.i) & , sonst \end{matrix}

Anwendung von LAG Überprüfung der Deklariertheit von Bezeichnern.

\underline{Beispiel} Sei G gegeben durch

P → \underline{DL}; \underline{SL}  Programm
\underline{DL} → V |V; \underline{DL} Deklarationsliste
\underline{SL} → S|S; \underline{SL} Statementliste
V → a|b| …  Variablen
S → V \underline{:=}V  Statement

36 3 SEMANTISCHE ANALYSE, ATTRIBUTGRAMMATIKEN

a;b;a;c;c:=a;d:=b;...

\underline{Attribute}

syn. v deklarierte/benutzte Variable V  ∈ {a, b, …}
syn. dv deklarierte Variablen  DL  ⊆ {a, b, …}
inh. env Umgebung  S, SL  ⊆ {a, b, …}
syn. decl korrekt deklariert?  S, SL, P ∈ {true, false}

Attributgleichungen

P → \underline{DL}; \underline{SL} decl.0 = decl.3  \underline{SL} → S; \underline{SL} decl.0 = decl.1 AND decl.3
env.3 = dv.1  env.1 = env.0
\underline{DL} → V dv.0 = \{v.1\} env.3 = env.0
\underline{DL} → V; \underline{DL} dv.0 = \{v.1\} ∪ dv.3 V → a|b| … v.0 = a| …
\underline{SL} → S env.1 = env.0 S → V \underline{:=}V decl.0 = v.1 ∈ env.0
decl.0 = decl.1  AND v.3 ∈ env.0

Index

ε-Hülle, 7

Abkürzungen, 7 Ableitungsbaum, 14 Ableitungsrelation, 13 Abstrakte Syntax, 33 action-Funktion, 19 akutelle Attributvariable, 30 Analyse, 9

flm-, 10 Analysetabelle, 19 assoziativen, 20 Attribut, 5, 6

inherites, 29, 30 synthetisches, 29, 30

Attributgleichung, 30 Attributgleichungssystem, 30 Attributgrammatik, 29, 30 Attributwerte, 29 Attributwertung, 30 Attributzuordnung, 30 Außenvariable, 30

Backend, 4 Bottom-Up-Analyse:, 13

Compiler, 3

eindeutig, 14 Erzeugte Sprache, 13

follow-Mengen, 16 formale Attributvariable, 30 Frontend, 4

Innenvariable, 30

Konkrete Syntax, 33 Kontextfreie Grammatiken, 13

l-Analyse, 14 L-Attributgrammatik, 34 Lexem, 5 lexikalische Struktur, 5 lexikalisches Atom, 5 linksrekursiv, 20 LL(k)-Grammatik, 16 Look-ahead-Menge, 17 LR(0)-äquivalent, 27 LR(0)-Auskunft, 23 LR(0)-Menge, 23 LR(k)-Grammatik, 22

Matching-Problem, 7

erweitert, 9 mehrdeutig, 14

NTA, 14

Parser, 13 Passes, 3 Präzedenzregeln, 7 Pragmatik, 3 Prinzip des ersten Matches, 10 Prinzip des längsten Matches, 9 produktiv, 10

Quellprogramm, 3

r-Analyse, 14 Reguläre Ausdrücke, 6 Reguläre Definitionen, 7

S-Attributgrammatik, 32 Scanner, 5 Semantik, 3 Semantische Analyse, 29 Shift-Reduce-Verfahren, 21 Sieber, 11 startsepariert, 22 Symbole, 5 Symbolklasse, 5 Syntax, 3 Thompson-Konstruktion, 8 Token, 5, 6 Top-Down-Analyse:, 13 Top-Down-Analyseautomat, 14

Zeichen, 5 Zeichensatz, 5 Zerlegung, 9

lm-, 9 Zielprogramm, 3 zirkulär, 31 zirkuläre Abhängigkeit, 31