\documentclass[11pt]{article}
\usepackage[T1]{fontenc}
\usepackage{textcomp}
\usepackage{lmodern}
\usepackage[margin=1in]{geometry}
\usepackage[pdftex]{graphicx, color}
\usepackage{mathtools}
\usepackage{listings}
\usepackage[pdfusetitle]{hyperref}
\usepackage{forest}
\tikzset{nodestyle/.style={rectangle,draw}}

\newcommand\tab[1][1cm]{\hspace*{#1}}
\usepackage{array}
\newcommand{\PreserveBackslash}[1]{\let\temp=\\#1\let\\=\temp}
\newcolumntype{C}[1]{>{\PreserveBackslash\centering}p{#1}}
\newcolumntype{R}[1]{>{\PreserveBackslash\raggedleft}p{#1}}
\newcolumntype{L}[1]{>{\PreserveBackslash\raggedright}p{#1}}

\usepackage{tikz}
\usetikzlibrary{automata,positioning}

\let\epsilon\varepsilon
\tikzset{shorten >=1pt, node distance=2cm, on grid, baseline={([yshift=-8pt] current bounding box.north)}}


\lstset{basicstyle=\small\ttfamily,breaklines=true}

\title{CS143 Spring 2024 -- Written Assignment 2}

\begin{document}
\begin{center}
% Change this:
\LARGE YOURNAME -- SUNETID \\
\LARGE CS143 Spring 2024 -- Written Assignment 2 \\
\large Due Monday, April 29, 2024 11:59 PM PDT
\end{center}

This assignment covers context free grammars and parsing. 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. Assignments can be submitted electronically through Gradescope as a \textsc{pdf} by 11:59 \textsc{pm PDT}. Please review the the course policies for more information: \url{https://web.stanford.edu/class/cs143/policies/}. A \LaTeX{} template for writing your solutions is available on the course website.
If you need to draw parse trees in \LaTeX{}, you may use the {\tt forest} package: \url{https://ctan.org/pkg/forest}.

\bigskip

\begin{enumerate}
% Problem 1
\item  Give a context-free grammar (CFG) for each of the following languages. Any grammar is acceptable---including ambiguous grammars---as long as it has the correct language. The start symbol should be $S$.
  \begin{enumerate}
    \item The set of all strings over the alphabet $\{3,4,*,-\}$ representing valid products of integers where the expression evaluates to some positive odd value.

    Example Strings in the Language:
    \begin{center}
      3 \tab \tab 3*433 \tab \tab -3*3*-3343
    \end{center}
    Strings not in the Language:
    \begin{center}
      $\epsilon$ \tab \tab -{}-3  \tab \tab -3*3*-3344
    \end{center}
    
    \textbf{Solution:}
    

    \item The set of all strings over the alphabet $\{\texttt{a}, \texttt{b}, \texttt{[}, \texttt{]}, \texttt{,}\}$ representing nested lists of $a$ and $b$'s where each list has an even length. Nested lists are defined as comma seperated sequences of elements enclosed with a pair of square brackets $[]$, where an element may be an $a$, $b$, or another list. 
    Example Strings in the Language:
    \begin{center}
        $[]$ \tab \tab $[a, [[b, a], a]]$ \tab \tab $[[], [a,b], [a,a], [[], [b,b]]]$
    \end{center}
    Strings not in the Language:
    \begin{center}
      $\epsilon$ \tab \tab $b$ \tab \tab $[a,b,]$  \tab \tab $[a$ \tab \tab $[a, [[b], a]]$
    \end{center}

    \textbf{Solution:}

  \item The set of all strings over the alphabet $\{0, 1\}$ where the number of $1$'s is more than the number of $0$'s.

    Example Strings in the Language:
    \begin{center}
      $1$ \tab \tab 101 \tab \tab 001111
    \end{center}
    Strings not in the Language: 
    \begin{center}
      $\epsilon$ \tab \tab 0 \tab \tab 01100101
    \end{center}

    \textbf{Solution:}
    
   
  \item The set of all strings over the alphabet $\{0, 1\}$ in the language $L : \{ 1^i 0^j 1^k \mid j \ge i + k \}$.

    Example Strings in the Language:
    \begin{center}
      $0$ \tab \tab 100011 \tab \tab $\epsilon$
    \end{center}
    Strings not in the Language: 
    \begin{center}
      $1$ \tab \tab 010 \tab \tab 101
    \end{center}

    \textbf{Solution:}
    
  \end{enumerate}
    
  \newpage

% Problem 2
\item Consider the following grammar for if-then-else expressions that involve a variable $x$:
  \begin{align*}
    E &\to \text{if} \ x \ \text{then} \ E \mid \mathit{M} \\
    \mathit{M} &\to \text{if} \ x \ \text{then} \ \mathit{M} \ \text{else} \ E \mid x
  \end{align*}
  Is this grammar ambiguous or not?
  If yes, give an example of an expression with two different parse trees and draw the two parse trees.
  If not, explain why that is the case.

  \textbf{Solution:}

  \newpage

% Problem 3
\item
  \begin{enumerate}
    
  \item Left factor the following grammar:
    \begin{equation*}
      \begin{split}
        S &\to T \mid T + T \mid T * T \\
        T &\to Ta \mid Tb \mid cU \\
        U &\to U0 \mid U1 \mid \epsilon \\
      \end{split}
    \end{equation*}

    \textbf{Solution:}

  \item Eliminate left recursion from the following grammar:
    \begin{equation*}
      \begin{split}
        S &\to S + S \mid (S) \mid T \\
        T &\to U U b \mid T a \\
        U &\to T T c \mid c
      \end{split}
    \end{equation*}

    \textbf{Solution:}

  \end{enumerate}

  \newpage
  
% Problem 4
\item Consider the following CFG, where the set of terminals is $\{a, b, c, <, > \}$:
  \begin{equation*}
    \begin{split}
      S &\to T<U \mid b>U \\
      T &\to aS<S \mid cU | >b \\
      U &\to >Ta \mid <Sb \\
    \end{split}
  \end{equation*}

  \begin{enumerate}
  \item Construct the FIRST sets for each of the nonterminals.

  \textbf{Solution:}
    
  \item Construct the FOLLOW sets for each of the nonterminals.

  \textbf{Solution:}

  \item Construct the LL(1) parsing table for the grammar. Where applicable, list all possible productions for every parse table cell.  

  \textbf{Solution:}
    
  \item Show the sequence of stack, input, and action configurations that occur during an LL(1) parse of the string ``$> b < > > b a$''. At the beginning of the parse, the stack should contain a single $S$. The acceptable actions include: "out <production>", "match <terminal>", "accept", and "error". 

  \textbf{Solution:}

  \end{enumerate}

  \newpage

% Problem 5
  \item Consider the following grammar G over the alphabet $\Sigma$ = $\{a,b,c\}$:
  \begin{equation*}
    \begin{split}
      S' &\to S \\
      S &\to Aa \\
      S &\to Bb \\
      A &\to Ac \\
      A &\to \epsilon\\
      B &\to Bc \\
      B &\to \epsilon \\
    \end{split}
  \end{equation*}
You want to implement G using an SLR(1) parser (note that we have already added the S' $\to$ S production for you). \begin{enumerate}
    \item Construct the first state of the LR(0) machine, compute the FOLLOW sets of A and B, and point out the conflicts that prevent the grammar from being SLR(1) \\
      \textbf{Solution:}
    
    \item Show modifications to production 4 (A $\to$ Ac) and production 6 (B $\to$ Bc) that make the grammar SLR(1) while having the same language as the original grammar G. Explain the intuition behind this result.\\
      \textbf{Solution:}

  \end{enumerate} 

\end{enumerate}
\end{document}
