\newcommand{\NN}{\mathbb{N}}

\begin{slide}{Attributgrammatiken (I)}

  \begin{itemize}\itemsep 1pt
  \item 
    Attribut: Annotation an Knoten des Syntaxbaums.
    
    $A : \text{Knotenmenge} \to \text{Attributwerte}$ \quad (Bsp: $\NN$)

  \item
    Attributgrammatik besteht aus:
    \begin{itemize} \itemsep 1pt
    \item kontextfreier Grammatik $G$ (Bsp: $\{S\to e \mid mSS\}$)
    \item für jeden Knotentyp (Terminal $+$ Regel)

      eine Menge (Relation) von erlaubten Attribut-Tupeln
      $(A(X_0), A(X_1), \ldots, A(X_n))$

      für Knoten $X_0$ mit Kindern $[X_1,\ldots,X_n]$

\bigskip
$S \to m S S$ , $A(X_0)+A(X_3)=A(X_2)$; \\
$S \to e$, $A(X_0) = A(X_1)$; \\
Terminale: $A(e)=1, A(m)=0$
    \end{itemize}
  \end{itemize}

\end{slide}

\begin{slide}{Attributgrammatiken (II)}

ein Ableitungsbaum  mit Annotationen ist \\
\emph{korrekt bezüglich einer Attributgrammatik}, 
wenn 
\begin{itemize}
\item zur zugrundeliegenden CF-Grammatik paßt
\item in jedem Knoten das Attribut-Tupel
  (von Knoten und Kindern) zur erlaubten Tupelmenge gehört
\end{itemize}

Plan:
\begin{itemize}
\item Baum beschreibt Syntax, Attribute beschreiben Semantik
\end{itemize}

Ursprung:
Donald Knuth: Semantics of Context-Free Languages,
(Math. Systems Theory 2, 1968)

technische Schwierigkeit: Attributwerte
effizient bestimmen. (beachte: (zirkuläre) Abhängigkeiten)

\end{slide}

\begin{slide}{Donald E. Knuth}

  \begin{itemize}
  \item The Art Of Computer Programming (1968, \dots)

    (Band 3: Sortieren und Suchen)
  \item
    \TeX, Metafont, Literate Programming (1983, \dots)

    (Leslie Lamport: \LaTeX)
  \item
    Attribut-Grammatiken
  \item
    die Bezeichnung \glqq NP-vollständig\grqq
  \item \dots
  \end{itemize}

\url{http://www-cs-faculty.stanford.edu/~uno/}

\end{slide}


\begin{slide}{Arten von Attributen}

\begin{itemize}
\item synthetisiert:

  hängt nur von Attributwerten in Kindknoten ab
\item ererbt (inherited)
  
  hängt nur von Attributwerten in Elternknoten
  und (linken) Geschwisterknoten ab
\end{itemize}

Wenn Abhängigkeiten bekannt sind,
kann man Attributwerte durch Werkzeuge bestimmen lassen.
\end{slide}

\begin{slide}{Attributgrammatiken--Beispiele}

\begin{itemize}
\item
  Auswertung arithmetischer Ausdrücke (dynamisch)
\item
  Bestimmung des abstrakten Syntaxbaumes
\item
  Typprüfung (statisch)
\item
  Kompilation (für Kellermaschine) (statisch)
\end{itemize}

\end{slide}

\begin{slide}{Konkrete und abstrakte Syntax}

  \begin{itemize}
  \item konkreter Syntaxbaum $=$ der Ableitungsbaum 
  \item abstrakter Syntaxbaum $=$ wesentliche Teile
des konkreten Baumes
  \end{itemize}
unwesentlich sind z. B. die Knoten, 
die zu Hilfsvariablen der Grammatik gehören.

abstrakter Syntaxbaum kann als
synthetisiertes Attribut konstruiert werden.

\bigskip

\begin{verbatim}
E -> E + P  ;  E.abs = new Plus(E.abs, P.abs)
E -> P      ;  E.abs = P.abs
\end{verbatim}


\end{slide}
