\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 Written Assignment 2}

\begin{document}
\begin{center}
\LARGE CS143 Spring 2025 -- Written Assignment 2 \\
{\large Due Monday, April 28, 2025 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 $\{a,b,c\}$ such that the number of $a$'s plus the number of $b$'s is divisible by 3.
  Example Strings in the Language:
    \begin{center}
    $\epsilon$ \tab \tab abbc \tab \tab aaacc \tab \tab bbbacabccc
    \end{center}
    Strings not in the Language:
    \begin{center}
    a \tab \tab bb \tab \tab acbc \tab \tab abbbccc
    \end{center}
    
    \textbf{Solution}:
    \vspace{2in}
    
  \item The set of all strings over the alphabet $\{x,(,),;\}$ representing nested tuples of $x$'s where each tuple has an even length.

    Example Strings in the Language:
    \begin{center}
      $()$ \tab \tab $(x;())$ \tab \tab $((); x; ((); x); x)$
    \end{center}
    Strings not in the Language:
    \begin{center}
      $\epsilon$ \tab \tab $x$ \tab \tab $((); x; x)$  \tab \tab $(x; (); (x; (); x); x)$
    \end{center}
    
    \textbf{Solution}:

    \newpage
    \null
    \vspace{1.7in}
    
    
\item The set of all strings over the alphabet $\{0, 1\}$ where no consecutive 0's appear (no substring "00").
Example Strings in the Language:
\begin{center}
$\epsilon$  \tab 1  \tab 0  \tab 01  \tab 10  \tab 101 \tab  010  \tab 1010101
\end{center}
Strings not in the Language:
\begin{center}
00  \tab 100  \tab 001  \tab 1001  \tab 10010
\end{center}
    
    \textbf{Solution}:
    \vspace{2in}
    
\item The set of all strings over the alphabet $\{0,1\}$ in the language $L:\{0^i 1^j 0^k \mid j = i + k\}$.

    Example Strings in the Language:
    \begin{center}
      $\epsilon$ \tab \tab 10 \tab \tab 01 \tab \tab 0110  \tab \tab 000111
    \end{center}
    Strings not in the Language:
    \begin{center}
      0 \tab \tab 00 \tab \tab 001 \tab \tab 0010 \tab \tab 01110
    \end{center}

    \textbf{Solution}:
   
  \end{enumerate}

  \newpage
 

% Problem 2
\item Consider the following grammar for binary strings that involves the alphabet $\{a,b\}$:
  \begin{align*}
    E &\to Ea \mid Eb \mid aE \mid bE \mid T \\
    T &\to a \mid b \mid \epsilon \\
  \end{align*}
  Is this grammar ambiguous or not?
  If yes, give an example of an expression with two different parse trees, draw the parse trees, and make the grammar unambiguous.
  If not, explain why it is unambiguous.

  \textbf{Solution}:

  
  \newpage


% Problem 3
\item
  \begin{enumerate}
  \item Eliminate left recursion from the following grammar:
    \begin{equation*}
      \begin{split}
        S &\to S(T) \mid Sa \mid [ T ] \mid Tb \\
        T &\to T(S) \mid Tc \mid d
      \end{split}
    \end{equation*}

    \textbf{Solution}:
    \vspace{2.5in}
    
  \item Left factor the following grammar:
    \begin{equation*}
      \begin{split}
        S &\to (T+T) \mid (T) \\
        T &\to U*T \mid U*? \mid [ U ] \\
        U &\to U0 \mid U1 \mid \epsilon 
      \end{split}
    \end{equation*}
    
    \textbf{Solution}:
  \end{enumerate}

  \newpage
  

% Problem 4
\item Consider the following CFG, where the set of terminals is $\{0, 1, (, ), ;\}$:
\begin{equation*}
\begin{split}
    S &\to ( T \\
    T &\to C A \mid ) \\
    A &\to ; B \mid ) \\
    B &\to C A \mid ) \\
    C &\to 0 \mid 1 \mid S \\
\end{split}
\end{equation*}

\begin{enumerate}
    \item Construct the FIRST sets for each of the nonterminals. \\
    \textbf{Solution}:
    \begin{itemize}
        \item S: 
        \item T: 
        \item A: 
        \item B: 
        \item C: 
    \end{itemize}

    \vspace{0.3in}

    \item Construct the FOLLOW sets for each of the nonterminals.\\
    \textbf{Solution}:
    \begin{itemize}
        \item S: 
        \item T: 
        \item A: 
        \item B: 
        \item C: 
    \end{itemize}
    \vspace{0.3in}
    
    \item Construct the LL(1) parsing table for the grammar. \\
    \textbf{Solution}:
    \renewcommand{\arraystretch}{1.5}
    \begin{center}
    \begin{tabular}{l|p{1cm}|p{1cm}|p{1cm}|p{1cm}|p{1cm}|p{1cm}}
         Nonterminal & ( & ) & ; & 0 & 1 & \$ \\
         \hline
         S &    & & & & & \\
         \hline
         T &  &  & &  &  & \\
         \hline
         A & &  &  & & & \\
         \hline
         B &  &  &  &  &  & \\
         \hline
         C & & & & & & \\
    \end{tabular}
     \end{center}

    \vspace{0.3in}
    \item Show the sequence of stack, input and action configurations that occur during an LL(1) parse of the string "( ( ) ; 0 )". At the beginning of the parse, the stack should contain a single S. \\
    \textbf{Solution}:
    \begin{center}
      \begin{tabular}{R{10em}|R{10em}|L{10em}}
        Stack & Input & Action \\
        \hline
        & & \\
        & & \\
        & & \\
        & & \\
        & & \\
        & & \\
        & & \\
        & & \\
        & & \\
        & & \\
        & & \\
        & & \\
        & & \\
        & & \\
        & & \\
        & & \\
        & & \\
      \end{tabular}
    \end{center}
\end{enumerate}

\newpage



% Problem 5 
\item Consider the following grammar $G$ over the alphabet $\{x, = \}$:
  \begin{equation*}
    \begin{split}
      S' &\to S \\
      S &\to L = R \\
      S &\to R \\
      L &\to x \\
      R &\to L \\
    \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 DFA of the LR(0) machine, and identify all conflicting states and conflicts that prevent the grammar from being LR(0).

    \textbf{Solution}:
    \newpage

 
  \item Now, for each conflicting state in the DFA that prevents it from being LR(0), identify the FOLLOW sets of the left-hand nonterminals. Is the grammar SLR(1)? Explain. 
        Your explanation must reference at least one of the identified FOLLOW sets from each conflicting DFA state. 

    \textbf{Solution}:

    
  \end{enumerate} 

\end{enumerate}

\end{document}