\documentclass{article}
\usepackage{fullpage}
\usepackage{array}
\usepackage{parskip}
\usepackage{fancyhdr}
\usepackage{lastpage}

\pagestyle{fancy}
\cfoot{\thepage\ of \pageref{LastPage}}
\fancyhead{}
\renewcommand{\headrulewidth}{0 pt}

\title{Assignment 2: Lexing, Grammars, and Dataflow Analysis}
\author{15-411: Compiler Design\\
Ian Gillis (igillis) and Alex Crichton (acrichto)}
\date{Due: Tuesday, September 25, 2012 (1:30 pm)}

\begin{document}
\maketitle

\thispagestyle{fancy}

\newcommand{\nonterm}[1]{\ensuremath{\langle{\mbox{#1}}\rangle}}
\newcommand{\term}[1]{{#1}}
\newcommand{\OR}{\ensuremath{\ | \ \ }}
\newcommand{\production}[3]{\ensuremath{\gamma_{#1}} & : & \nonterm{#2} & $\rightarrow$ & {#3} \\}

\textbf{Reminder:} Assignments are individual assignments,
not done in pairs.  The work must be all your own.

You may hand in a handwritten solution
solution at the beginning of lecture on Tuesday, September 25.  Please
read the late policy for written assignments on the course web page.
If you decide not to typeset your answers, make sure the text and
pictures are legible and clear.

\section*{Problem 1 (20 points)}

The following table defines the tokens for a simple language with $\Sigma$ = $\{[a-z], [0-9], ., \oplus \}$.

\begin{figure}[h!]
\centering
\begin{tabular}{ll}
token & regular expression\\
\hline
$\langle num\rangle$ & $\equiv$  0 $\vert$ [1-9][0-9]*\\
$\langle var\rangle$ & $\equiv$ [a-z][a-z0-9]*\\
$\langle lam\rangle$ & $\equiv$ lam\\
$\langle dot\rangle$ & $\equiv$ . \\
$\langle binop\rangle$ & $\equiv \oplus$ \\
\hline
\end{tabular}
\end{figure}

\begin{itemize}
\item [(a)] Construct a DFA which accepts tokens from this language. You may draw the states and transitions graphically or use the notation described in the lecture notes.
\end{itemize}
Here is the grammar for the language whose tokens were defined in part a.

\begin{center}
\begin{tabular}{rclcl}
\production{1}{E}{\term{x}}
\production{2}{E}{$\overline{n}$}
\production{3}{E}{\term{lam x .} \nonterm{E}}
\production{4}{E}{\nonterm{E} \nonterm{E}}
\production{5}{E}{\term{$\oplus$} \nonterm{E}}
\production{6}{E}{\nonterm{E} \term{$\oplus$} \nonterm{E}}
\end{tabular}
\end{center}

\begin{itemize}
\item [(b)] This grammar is ambiguous. Give an example of an ambiguous
expression along with two (or more) ways which it can be parsed.
\item [(c)] What additional information or rules are needed to fully specify
this language? Make a design decision about the language and write down the
disambiguating information, then update your parsing table based on your new
specification.
\end{itemize}

\newpage

\section*{Problem 2 (20 points)}

One useful dataflow analysis is that of ``available expressions.'' We will say
that an expression $e$ is available at a point $l$ in the program if:

\begin{itemize}
  \item $e$ is computed on every path to $l$
  \item the value of $e$ has not changed since it was last computed on a path to
        $l$
\end{itemize}

For example, the following code:

\begin{verbatim}
l1: t0 <- t1 + t2
l2: t1 <- t2 * t4
\end{verbatim}

Has \texttt{\{t1 + t2\}} available at \texttt{l1}, and
\texttt{\{t2 * t4\}} available at \texttt{l2}. The first expression is
eliminated because its component, \texttt{t1} changed with the result of
\texttt{l2}.

We can use this information to eliminate redundant computation of expressions.
In this problem you will practice performing dataflow analysis on a small
amount of code. Note that this is not the entire program in the sense that not
all temps are assigned before they are used; you should assume that these have
been initialized by previous code.

\begin{enumerate}

\item []
\begin{verbatim}
a <- b + c
jmpnzero 1 d
b <- e + 3
a <- b + c
label 1
t1 <- e + 3
t2 <- b + c
return t1 + t2
\end{verbatim}

\item [(a)]
Compute the available expression(s) at each instruction.

\item [(d)]
Use the results of part (a) to give a (slighty) optimized version of the program
snippet.

\end{enumerate}

\newpage

\section*{Problem 3 (20 points)}

The lecture notes on liveness analysis and dataflow analysis mention the
dataflow equation forms of both liveness and reaching definition anylysis.
Recall:
\begin{itemize}
\item $A_\bullet(l)$ represents the result of the analysis just after statement $l$.
\item $A_\circ(l)$ represents the result of the analysis just before statement $l$.
\item $l \mapsto l'$ means that $l'$ is a successor of $l$.
\end{itemize}

For reaching definitions, a forward analysis, we used the equations:
\[A_\circ(l) = \bigcup_{l_i \mapsto l} A_\bullet(l_i)\]
\[A_\bullet(l) = (A_\circ(l) \setminus \mathsf{kill}(l)) \cup \mathsf{gen}(l)\]
For liveness, which is a backward analysis, we instead used:
\[A_\bullet(l) = \bigcup_{l \mapsto l_i} A_\circ(l_i)\]
\[A_\circ(l) = (A_\bullet(l) \setminus \mathsf{kill}(l)) \cup \mathsf{gen}(l)\]
In the assembly language from Problem 1, for reaching definitions,
$\mathsf{kill}$ and $\mathsf{gen}$ are defined as:

\begin{figure}[h!]
\centering
\begin{tabular}{lllll}
\hline
& \multicolumn{2}{c}{Reaching Definitions} & \multicolumn{2}{c}{Liveness} \\
statement $l$ & $\mathsf{gen}(l)$ & $\mathsf{kill}(l)$ & $\mathsf{gen}(l)$ & $\mathsf{kill}(l)$ \\
\hline
\hline
$l : x \leftarrow a + b$ & $\{l\}$ & $\{l | \mathsf{def}(l, x)\}$ & $\{a, b\}$ & $\{x\}$ \\
$l : x \leftarrow a - b$ & $\{l\}$ & $\{l | \mathsf{def}(l, x)\}$ & $\{a, b\}$ & $\{x\}$ \\
$l : x \leftarrow a * b$ & $\{l\}$ & $\{l | \mathsf{def}(l, x)\}$ & $\{a, b\}$ & $\{x\}$ \\
$l : x \leftarrow a / b$ & $\{l\}$ & $\{l | \mathsf{def}(l, x)\}$ & $\{a, b\}$ & $\{x\}$ \\
$l : \mathrm{jmpnzero}\ l'\ x $ & $\emptyset$ & $\emptyset$ & $\{x\}$ & $\emptyset$ \\
$l : \mathrm{jmp}\ l' $ & $\emptyset$ & $\emptyset$ & $\emptyset$ & $\emptyset$ \\
$l : \mathrm{return}\ x$ & $\emptyset$ & $\emptyset$ & $\{x\}$ & $\emptyset$ \\
$l : \mathrm{label}\ l'$ & $\emptyset$ & $\emptyset$ & $\emptyset$ & $\emptyset$ \\
\hline
\end{tabular}
\end{figure}

We solve these equations by initializing $A_\bullet(l)$ to $\{\}$ for each $l$
and then stepping the equations until they saturate.

The interesting aspect of this approach is that it is very general. Changing
the definitions of \textsf{gen} and \textsf{kill} will clearly yield a
different analysis. Similarly, we might replace set union with set intersection
to combine the output from previous statements. Finally, reaching definition
analysis runs forward; where we used $l_i \mapsto l$ in reaching analysis, we
can use $l \mapsto l_i$ to do backwards-flowing analysis. By changing these
parameters, we can use the same algorithm to compute a variety of interesting
analyses. In this problem, you will develop these parameters for availability
analysis.

\begin{enumerate}

\item [(a)]
Is availability a forward analysis or a backward analysis? Why?

\item [(b)]
Is the set operation to combine analysis from other statements a union or an
intersection? Why?

\item [(c)]
Write down the table defining \textsf{gen} and \textsf{kill} for each
instruction. You may use operations which you define outside of the table if you
find that easier.

\end{enumerate}
\end{document}
