\documentclass[9pt]{beamer}

\usepackage[utf8x]{inputenc}
\usepackage[english]{babel}
\usepackage{arev,t1enc}
\usepackage{ulem}

\include{fu-beamer-template}


\titleimage{fu_500}
\title[Compilerbau]
{Abschlusspr\"{a}sentation}

\author{B.~B\"{o}hm \and A.~N\"{u}\ss{}lein \and M.~Popov \and T.~Rakowski \and J.~Rekittke \and A.~Sulfrian}

\institute[FU Berlin]
{Freie Universität Berlin}

\date[7~Jun,~2009]
{Softwareprojekt Compilerbau, SoSe 2009}

\renewcommand{\footlinetext}{\insertshortinstitute, \insertshorttitle, \insertshortdate}
%\AtBeginSubsection[]
%{
%  \begin{frame}<beamer>{Outline}
%    \tableofcontents[currentsection,currentsubsection]
%  \end{frame}
%}


\begin{document}

\begin{frame}[plain]
	\titlepage
\end{frame}


\begin{frame}{Gruppe: Quellsprache}
	\begin{itemize}
		\item\color{fu-green} erfinden der Quellsprache
		\begin{itemize}
			\item\color{fu-green} Paradigma: imperativ, prozedural
			\item\color{fu-red} \sout{Typsystem: static, weak, infered}
		\end{itemize}
		\item\color{fu-green} erstellen der EBNF
	\end{itemize}
\end{frame}

\begin{frame}[fragile]{Gruppe: Quellsprache (Beispiel)}
	\begin{verbatim}
fun fib[a]
    if a < 2
        @1
    end
    @(call fib[a-1] + call fib[a-2])
end

fun main[]
    sum = 0
    i = 1
    while i <= 10
        sum = sum + call fib[i]
        i = i + 1
    end
    @sum
end
	\end{verbatim}
\end{frame}

\begin{frame}{Gruppe: Schnittstellen}
	\begin{itemize}
		\item Lexer $\Rightarrow$ Parser:
		\begin{itemize}\item\color{fu-green} Tokenstream\end{itemize}
		\item Parser $\Rightarrow$ Zwischencode:
		\begin{itemize}\item\color{fu-green} AST\end{itemize}
		\item Zwischencode $\Rightarrow$ Codegenerator:
		\begin{itemize}\item\color{fu-green} 3AC\end{itemize}
		\item Codegenerator $\Rightarrow$ Assemblercode:
		\begin{itemize}\item\color{fu-green} vereinfachte MIPS ISA\end{itemize}
	\end{itemize}
\end{frame}

\begin{frame}{Alex: Lexikalische Analyse}
	\begin{itemize}
		\item Tokens:
		\begin{itemize}
			\item\color{fu-green} NUMBER, BOOL, IDENT
			\item\color{fu-green} ASSIGNMENT
			\item\color{fu-green} OPERATOR
			\item\color{fu-green} FUN, RETURN
			\item\color{fu-green} WHILE, IF, ELSE
			\item\color{fu-green} LBRAK, RBRAK, LPAREN, RPAREN, NEWLINE, COMMA, END
		\end{itemize}
		\item\color{fu-green} \"{U}bersetzungsregeln mit Regul\"{a}ren Ausdr\"{u}cken
	\end{itemize}
\end{frame}

\begin{frame}{Alex: Typsystem}
	\begin{itemize}
		\item\color{fu-red} \sout{Typinferenz bei Initialisierung von Variablen}
		\item\color{fu-red} \sout{Statische Typzuweisung in der Symboltabelle}
		\item\color{fu-red} \sout{ggf. automatische Typkonvertierung}
	\end{itemize}
\end{frame}

\begin{frame}{Michael: Syntaxanalyse/Parser}
	\begin{itemize}
		\item Top-Down-Parsing
		\item Ableitungsbaum:
		\begin{itemize}
			\item\color{fu-green} Program(Node)
			\item\color{fu-green} Function(Node)
			\item\color{fu-green} Statement(Node)
			\item\color{fu-green} Sequence(Statement)
			\item\color{fu-green} IfStatement(Statement)
			\item\color{fu-green} WhileStatement(Statement)
			\item\color{fu-green} ReturnStatement(Statement)
			\item\color{fu-green} AssignStatement(Statement)
			\item\color{fu-green} FunctionCall(Statement,Expression)
			\item\color{fu-green} Operation(Node)
			\item\color{fu-green} Expression(Operation)
			\item\color{fu-green} UnaryExpression(Expression)
			\item\color{fu-green} BinaryExpression(Expression)
			\item\color{fu-green} Variable(Expression)
			\item\color{fu-green} Constant(Expression)
		\end{itemize}
	\end{itemize}

\end{frame}

\begin{frame}{Michael: Semantische Analyse}
	\begin{itemize}
		\item\color{fu-green} Aufbau der Symboltabelle
		\item\color{fu-green} G\"{u}ltigkeitsbereiche der Bezeichner \"{u}berpr\"{u}fen
		\item\color{fu-green} eindeutige Zuweisungen von Bezeichnern
	\end{itemize}
\end{frame}

\begin{frame}{Andreas: Zwischencode}
	\begin{itemize}
		\item Drei-Adress-Code (SSA Form):
		\begin{itemize}
			\item\color{fu-green} Bin\"{a}re Operationen: ADD, SUB, MUL, DIV, MOD, AND, OR
			\item\color{fu-green} Un\"{a}re Operationen: NOT, MINUS
			\item\color{fu-green} Zuweisungen: ASSIGN
			\item\color{fu-green} Vergleiche: EQ, NE, LE, LT, GE, GT
			\item\color{fu-green} Bedingte Spr\"{u}nge: BEZ
			\item\color{fu-green} Nichtbedingte Spr\"{u}nge: JMP
			\item\color{fu-green} Funktionsaufrufe: PARAM, CALL, RETURN
		\end{itemize}
	\end{itemize}
\end{frame}

\begin{frame}{Andreas: Maschinenunabh\"{a}ngige Optimierung}
	\begin{itemize}
		\item\color{fu-red} \sout{Eliminierung gemeinsamer Teilausdr\"{u}cke}
		\item\color{fu-red} \sout{Kopiepropagation}
		\item\color{fu-red} \sout{Entfernen von totem Code}
		\item\color{fu-red} \sout{Konstantenfaltung}
	\end{itemize}
\end{frame}

\begin{frame}{Jana: Codegenerator}
	\begin{itemize}
		\item\color{orange} Zuweisung von Adressen/Registervergabe
		\item\color{fu-green} Zerlegen von Drei-Adress-Code in Grundbl\"{o}cke
		\item\color{fu-green} Befehlsauswahl
		\item\color{fu-green} Aufrufkonventionen
		\item\color{fu-green} Ausgabe als Assemblercode
	\end{itemize}
\end{frame}

\begin{frame}{Jana/Bene: RISC Emulator}
	\begin{itemize}
		\item Erfundene RISC ISA:
		\begin{itemize}
			\item\color{fu-green} Arithmetik: ADD, SUB, MUL, DIV, MOD
			\item\color{fu-green} Logik: AND, OR
			\item\color{fu-green} Load \& Store: MOV, LW, SW, PUSH, POP
			\item\color{fu-green} Vergleiche: CMP, EQ, NE, LE, LT, GE, GT
			\item\color{fu-green} Spr\"{u}nge: BEZ, JMP, CALL, RET
			\item\color{fu-green} Andere: SYS
		\end{itemize}
		\item keine Memory-Management-Unit
		\item\color{fu-green} I/O durch Nachbildung von System-Calls
	\end{itemize}
\end{frame}

\end{document}
