\begin{slide}{Grundsätzliches}

  \begin{itemize}
  \item ein Compiler verarbeitet Programme
  \item alle nicht trivialen semantischen Eigenschaften von Programmen
    (einer Turing-vollständigen Programmiersprache)
    sind unentscheidbar 
    (z. B.: wird eine Anweisung jemals ausgefÃ¼hrt,
    wird eine Speicherstelle mehr als einmal geschrieben usw.)
  \end{itemize}
Compiler haben es schwer
\begin{itemize}
\item Compiler muß raten/approximieren
\item oder Programmierer muß mithelfen (z. B. Typen deklarieren)
\end{itemize}

\end{slide}

\begin{slide}{Schwere Aufgaben für Compiler/Werkzeuge (Bsp 1)}
lexikalische/syntaktische Analyse 
(Generierung von Werkzeugen aus Beschreibungen)

\[ L(A)=L(B) \]
\begin{itemize}
\item für reguläre Ausdrücke $A,B$: entscheidbar
\item für kontextfreie Grammatiken $A,B$: nicht entscheidbar
\end{itemize}

\end{slide}

\begin{slide}{Schwere Aufgaben für Compiler (Bsp 2)}

Äquivalenz von algebraischen Ausdrücken (Polynomen)
  \begin{itemize}
  \item ist unentscheidbar (Hilberts 10. Problem)
  \item Anwendung: Optimierung von Zählschleifen
  \end{itemize}
  vgl. (In-)Äquivalenz regulärer Ausdrücke, 
  kleinster äquivalenter regulärer Ausdruck

\end{slide}

\begin{slide}{Schwere Aufgaben für Compiler (mehr Bsp)}

  \begin{itemize}
  \item (Maschinen)Befehls-Auswahl

    $\to$ Rucksack-Problem, NP-vollst.
  \item Registervergabe 

    $\to$ Graphenfärbung, NP-vollst.

  \item
    Typprüfung/Inferenz

    mit generischen Typen: wenigstens Exp-Time
  \end{itemize}

\end{slide}
