\documentclass[10pt]{article}
\usepackage[pdftex]{graphicx, color}
\usepackage{listings}
\usepackage{tikz}
\usetikzlibrary{automata,positioning}
\headheight 8pt \headsep 20pt \footskip 30pt
\textheight 9in \textwidth 6.5in
\oddsidemargin 0in \evensidemargin 0in
\topmargin -.35in
\lstset{basicstyle=\small\ttfamily,breaklines=true}
\newcommand {\pts}[1]{{\bf #1 pts}}
\begin{document}
\begin{center}
\Large CS131 Compilers: Writing Assignment 2\\Due Tuesday, April 6, 2017 at 8:15am
\end{center}
\begin{center}
%% Change this:
\LARGE Name - ID
\end{center}
This assignment asks you to prepare written answers to questions on
context-free grammars and parsing. Each of the questions has a short answer. You
may discuss this assignment with other students and work on the problems
together. However, your write-up should be your own individual work.
and you should indicate in your submission who you worked with, if applicable.
Written assignments are turned in at the start of lecture.
You should use the Latex template provided at the course web site to write your solution.
\begin{center}
%% Change this:
I worked with: (Name,ID), (Name,ID)...
\end{center}
\begin{enumerate}
\item \pts{$2\times 3= 6$} Give context-free grammar (CFG) for each of the following languages:
\begin{enumerate}
\item The set of all finite strings over the alphabet $\{0,1\}$ with an equal number of 0's and 1's.
\[
%% Your answer here
\]
\item The set of all finite strings over the alphabet $\{0,1\}$ with an unequal number of 0's and 1's.
\[
%% Your answer here
\]
\item The set $L_3=L_1\cap L_2$, where $L_1$ and $L_2$ are defined below.
Let $L_1$ be the finite strings consisting of all non-empty \emph{palindromes} over the alphabet $\{a,b\}$. That is $L_1$
consists of all sequences of a's and b's that read the same forward or backward. For example, $abba,~aabbbaa\in L_1$, but $abb\not\in L_1$.
Let $L_2$ be the language over $\{a,b\}$ representing the language of the regular expression $b(a+b)^\ast$.
\[
%% Your answer here
\]
\end{enumerate}
%
\item \pts{$3\times 2= 6$} Consider the following CFG with terminals $\{(,),+,*,a,b\}$ ($+$ represents union) that is used to represent
regular expressions over alphabet $\{a, b\}$:
\[R\rightarrow R+R \mid RR\mid (R)\mid R^\ast \mid a\mid b\]
\begin{enumerate}
\item Using the above CFG, provide a derivation for the following input string $(a+(ba)^\ast b)^\ast$.
\[
%% Your answer here
\]
\item For the derivation in above solution, provide the corresponding parse tree.
\[
%% Your answer here
\]
\end{enumerate}
\newpage
\item \pts{$3\times 3= 9$} Consider the following CFG.
\[\begin{array}{cll}
S & \rightarrow & AED \mid F \\
A & \rightarrow & Aa \mid a \\
B & \rightarrow & Bb \mid b \\
C & \rightarrow & Cc \mid c \\
D & \rightarrow & Dd \mid d \\
E & \rightarrow & bEc \mid bc \\
F & \rightarrow & aFd \mid BC
\end{array}\]
\begin{enumerate}
\item What is the language generated by this grammar?
\[
%% Your answer here
\]
\item Is the grammar as given ambiguous? If yes, give an example of an expression
with two parse trees under this grammar. If not, explain why that is the case.
\[
%% Your answer here
\]
\item Transform the CFG given above by eliminating ambiguity and
left recursion, if needed.
\[
%% Your answer here
\]
\end{enumerate}
\newpage
\item \pts{$3\times 3= 9$} Consider the following CFG.
\[\begin{array}{cll}
A & \rightarrow & [AB] \mid a \\
B & \rightarrow & \epsilon \mid +AC \mid Cb \\
C & \rightarrow & \epsilon \mid -ABc
\end{array}\]
\begin{enumerate}
\item Compute the First and Follow sets for the grammar.
\[
%% Your answer here
\]
\item Give the LL(1) parsing table for the grammar.
\[
%% Your answer here
\]
\item Is this grammar LL(1)? and Why.
\[
%% Your answer here
\]
\end{enumerate}
\item \pts{$8$} Using the context-free grammar for Cool given in Section 11 of the Cool
manual, draw a parse tree for the following expression.
\begin{lstlisting}
while not (x <-z <- 0) loop
y <- z + 2 * x + 1
pool
\end{lstlisting}
Note that the context-free grammar by itself is ambiguous, so you will
need to use the precedence and associativity rules in Section 11.1 to
get the correct tree.
\[
%% Your answer here
\]
\newpage
\item \pts{$4\times 4 =16$} Consider the following grammar describing a certain sort of nested lists:
\[\begin{array}{cll}
S & \rightarrow & T;S \mid \epsilon \\
T & \rightarrow & U\star T \mid U \\
U & \rightarrow & x\mid y\mid [S]
\end{array}\]
$S$, $T$, and $U$ are nonterminals, while others are terminals.
\begin{enumerate}
\item Left-factor this grammar.
\[
%% Your answer here
\]
\item Give the First and Follow sets for each nonterminal in the grammar obtained in part (a).
\[
%% Your answer here
\]
\item Using this information, construct an LL(1) parsing table for the grammar obtained in part (a).
\[
%% Your answer here
\]
\item Suppose we generated an LL(1) parser for the grammar using the table you constructed. What would go wrong if it tried to parse the following input string?
\[[x;y]\star [;\]
\[
%% Your answer here
\]
\end{enumerate}
\newpage
\item \pts{$3\times 2+5\times 2 =16$} Consider the following CFG, which has the set of terminals
$T = \{ \textbf{a}, \textbf{b} \}$.
\[\begin{array}{cll}
S & \rightarrow & X \textbf{a} \\
X & \rightarrow & \textbf{a} \mid \textbf{a} X \textbf{b}
\end{array}\]
\begin{enumerate}
\item Construct a DFA for viable prefixes of this grammar using LR(0)
items.
\[
%% Your answer here
\]
\item Identify a shift-reduce conflict in this grammar under the
SLR(1) rules.
\[
%% Your answer here
\]
\item Assuming that an SLR(1) parser resolves shift-reduce conflicts
by choosing to shift, show the operation of such a parser on the input
string \textbf{aaba}.
\[
%% Your answer here
\]
\item Suppose that the production $X \rightarrow \varepsilon$ is added
to this grammar. Identify a reduce-reduce conflict in the resulting
grammar under the SLR(1) rules.
\[
%% Your answer here
\]
\end{enumerate}
\end{enumerate}
\end{document}