\documentclass[11pt]{article}

\input{../latex/compilerstoolbox.sty}
\usepackage{homework}
\usepackage{tikz}
\usepackage{proof}
\setlength{\inferLineSkip}{4pt}
\usepackage{latexsym}
\usepackage{graphicx}

\def\rotatechartwo#1{\reflectbox{#1}}
\newcommand{\assdate}{Tuesday, February 25th, 2025 (11:59PM)}
\newcommand{\assnum}{3}
\newcommand{\asstitle}{Parsing and Single Static Assignment}
\newcommand{\lecturer}{}
\setlength{\headsep}{0.2in}

\begin{document}
\maketitle

\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.
Hand in your solutions on Gradescope.
Please read the late policy for written assignments on the course web page.

As a reminder, \textbf{only submissions typeset in \LaTeX will be accepted}.

\clearpage
\section*{Problem 1: Parsing (30 points)}
The famed 15-150 mascot Polly has invaded the compilers course-staff and is in a glorious language battle with Opal the Otter!

Of course, Polly is not a fan of C0 instead preferring SML. But rather than changing the
entire class to compile to SML, he decides to instead write a new language.
Using context-free grammars Polly comes up with the language, $C_0^{\lambda}$,
which combines the usability of lambda calculus with the safety of C. He
specifies it with the following grammar (noting that \term{x} is an identifier
token and that $\gamma_3$ denotes function application\footnote{For example,
  \textbf{f x} is the function \textbf{f} applied to the argument
  \textbf{x}.}).

\begin{center}
\begin{tabular}{rclcl}
\production{1}{E}{\term{x}}
\production{2}{E}{\term{$\lambda$ x .} \nonterm{E}}
\production{3}{E}{\nonterm{E} \nonterm{E}}
\production{4}{E}{\term{(} \nonterm{E} \term{)}}
\end{tabular}
\end{center}

\begin{itemize}
\item [(a)] Polly gets Opal to review his grammar, and Opal uncovers a number of
  problems. Show two ambiguities in the above grammar by providing for each
  ambiguity two possible parse trees for the same string.
  
\item[(b)] Clarabelle the 15-210 mascot is seeking
  to use Polly's revolutionary language, having found much success with SML. However, Clarabelle requires an unambiguous grammar. As compiler writers, help Polly fix his language and rewrite the grammar so it is
  unambiguous. \textbf{You must accomplish this by modifying currently existing rules, and/or adding up to one more rule for a total of 5 rules.}\footnote{Hint: your new grammar may or may not have the
    precedence you'd expect from lambda calculus.}.
    
    For each ambiguity
  you found in (a), identify which of the two parse trees will be
  accepted by your new grammar. The grammar should describe the same
  set of strings as the original grammar.

\item[(c)] The 15-312 mascots, Progress and Preservation, also want to use Polly's language (being fans of lambda calculus). However, Progress and Preservation attempt to use a left-to-right recursive descent parser and discover that it loops infinitely.

Identify one reason why the top-down parser might loop infinitely on the grammar, and explain how to fix it.
\end{itemize}

\clearpage

\section*{Problem 2: Stuck in the Middle (20 points)}
After Polly's successful release of $C_0^{\lambda}$ she wonders if she dismissed
C0 a little to quickly. Opal informed her of a way to convert a C0 program to be
more faster and more functional... \\

We generate a \textit{Collatz sequence $c_i$}, starting from some positive
integer $n$, with the following mathematical definition:
$$ c_0 = n \hspace{3.9cm} $$
$$ c_{i+1} = \begin{cases} c_i/2 \;\;\;\;\;\;\;\;\;\text{   if } c_i \text{ is even} \\
            3c_i + 1    \;\;\;\;\; \text{   otherwise}
           \end{cases} $$

The following C0 function is intended to compute the \textit{maximum number} in
the Collatz sequence for $n$ before it stops.

\begin{verbatim}
int collatz(int n)
//@requires n >= 1;
{
  int r = n;
  while (n > 1) {
    if (n > r) r = n;
    if (n % 2 == 0)
      n = n / 2;
    else
      n = 3*n + 1;
  }
  return r;
}
\end{verbatim}

\newpage

The following is a valid three-address abstract assembly translation:
\begin{verbatim}
collatz(n):
    r <- n
    goto .loop
.loop:
    if (n > 1) then .body else .done
.body:
    if (n > r) then .l1 else .l2
.l1:
    r <- n
    goto .l2
.l2:
    m <- n % 2
    if (m == 0) then .l3 else .l4
.l3:
    n <- n / 2
    goto .loop
.l4:
    n <- n * 3
    n <- n + 1
    goto .loop
.done:
    ret r
\end{verbatim}

\begin{enumerate}
\item[(a)] Show the control flow graph of the program pictorially, carefully
encapsulating each basic block. Label each basic block with the label from the
abstract assembly code. \\
\item[(b)] Show the dominator tree of the program pictorially. Then, for each basic block, write its corresponding dominance frontier. \\
\item[(c)] Convert the abstract assembly program from (a) into SSA, inserting $\Phi$-functions and renaming variables as necessary. It is sufficient to submit the final result of your transformation. \\
\item[(d)] Apply the de-SSA transformation by replacing the $\Phi$-functions with sequential moves. \\


\end{enumerate}


\end{document}
