% Created 2023-02-27 Mon 22:14
% Intended LaTeX compiler: lualatex
\documentclass[11pt]{article}
\usepackage{graphicx}
\usepackage{longtable}
\usepackage{wrapfig}
\usepackage{rotating}
\usepackage[normalem]{ulem}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{capt-of}
\usepackage{hyperref}
\notindent \notga \usepackage{ dsfont } \usepackage[utf8]{inputenc}  \usepackage{amsmath} \usepackage{fontspec} \usepackage[a4paper,margin=1in,portrait]{geometry} \usepackage{fontspec} \setmonofont{DejaVu Sans Mono}
\author{Lizzy Hunt}
\date{\today}
\title{Assignment Seven}
\hypersetup{
 pdfauthor={Lizzy Hunt},
 pdftitle={Assignment Seven},
 pdfkeywords={},
 pdfsubject={},
 pdfcreator={Emacs 28.2 (Org mode 9.6.1)}, 
 pdflang={English}}
\begin{document}

\maketitle
\setlength\parindent{0pt}

\section{Question One}
\label{sec:org41ddc16}
\subsection{Removal of Left Recursion}
\label{sec:org2e2ade2}
\begin{verbatim}
A  -> BbA'
A' -> aA' | ε
B  -> aB | b
\end{verbatim}
\subsection{Left Factoring}
\label{sec:orge4a4f75}
No need to left factor this grammar
\subsection{Parse Table}
\label{sec:org43628e4}
\subsubsection{Calculation of first and follow}
\label{sec:org8e7d2cc}
\begin{verbatim}
first(A) = first(B) = {a, b}
first(A') = first(a) U first(ε) = {a, ε}
first(B) = first(a) U first(b) = {a, b}

follow(A) = {$}
follow(A') = follow(A) = {$}
follow(B) = {b}
\end{verbatim}

\subsubsection{Predictive Parse Table}
\label{sec:orgc2ae298}
\begin{center}
\begin{tabular}{llll}
Nonterminal & a & b & \$\\[0pt]
A & A \(\rightarrow\) BbA' & A \(\rightarrow\) BbA' & \\[0pt]
A' & A' \(\rightarrow\) aA' &  & A' \(\rightarrow\) \(\epsilon\)\\[0pt]
B & B \(\rightarrow\) aB & B \(\rightarrow\) b & \\[0pt]
\end{tabular}
\end{center}

\subsection{Parse of "abba"}
\label{sec:orge26f0a1}
\begin{center}
\begin{tabular}{llll}
Stack & Input & Action & Matched\\[0pt]
A\$ & abba\$ & A \(\rightarrow\) BbA' & \\[0pt]
BbA'\$ & abba\$ & B \(\rightarrow\) aB & \\[0pt]
aBbA'\$ & bba\$ & Match a & a\\[0pt]
BbA'\$ & bba\$ & B \(\rightarrow\) b & a\\[0pt]
bbA'\$ & bba\$ & Match b & ab\\[0pt]
bA'\$ & ba\$ & Match b & abb\\[0pt]
A'\$ & a\$ & A \(\rightarrow\) aA' & abb\\[0pt]
aA'\$ & a\$ & Match a & abba\\[0pt]
A'\$ & \$ & A' \(\rightarrow\) ε & abba\\[0pt]
ε\$ & \$ & Match ε & abba\\[0pt]
\$ & \$ & Match \$ & \\[0pt]
 &  & Accept & \\[0pt]
\end{tabular}
\end{center}

\section{Question Two}
\label{sec:orgc3fb7f0}
\begin{center}
\begin{tabular}{lll}
Stack & Input & Action\\[0pt]
\$ & (id)*id\$ & shift\\[0pt]
\$( & id)*id\$ & shift\\[0pt]
\$(id & )*id\$ & reduce F \(\rightarrow\) id\\[0pt]
\$(F & )*id\$ & reduce F \(\rightarrow\) E\\[0pt]
\$(E) & *id\$ & shift\\[0pt]
\$F & *id\$ & reduce F \(\rightarrow\) (E)\\[0pt]
\$T & *id\$ & reduce T \(\rightarrow\) F\\[0pt]
\$T* & id\$ & shift\\[0pt]
\$T*id & \$ & shift\\[0pt]
\$T*F & \$ & reduce F \(\rightarrow\) id\\[0pt]
\$T & \$ & reduce T \(\rightarrow\) T * F\\[0pt]
\$E & \$ & reduce E \(\rightarrow\) T\\[0pt]
\$E & \$ & accept\\[0pt]
\end{tabular}
\end{center}

\section{Question Three}
\label{sec:org180e5b7}
\begin{center}
\begin{tabular}{lll}
Stack & Input & Action\\[0pt]
\$ & ()(())\$ & Shift\\[0pt]
\$( & )(())\$ & Shift\\[0pt]
\$() & (())\$ & Shift\\[0pt]
\$Pair & (())\$ & Reduce R5\\[0pt]
\$List & (())\$ & Reduce R3\\[0pt]
\$List( & ())\$ & Shift\\[0pt]
\$List(( & ))\$ & Shift\\[0pt]
\$List(() & )\$ & Shift\\[0pt]
\$List(Pair & )\$ & Reduce R5\\[0pt]
\$List(Pair) & \$ & Shift\\[0pt]
\$List Pair & \$ & Reduce R4\\[0pt]
\$Goal & \$ & Reduce R1\\[0pt]
\$Goal & \$ & Accept\\[0pt]
\end{tabular}
\end{center}

\section{Question Four}
\label{sec:orgd14094c}
\subsection{a}
\label{sec:org6873356}
\{[N \(\rightarrow\) \(\cdot\) N + N], [N \(\rightarrow\) \(\cdot\) NN], [N \(\rightarrow\) \(\cdot\) (N)], [N \(\rightarrow\) \(\cdot\) N *], [N \(\rightarrow\) \(\cdot\) a]\}

\subsection{b}
\label{sec:orgdf45b11}
\{[N \(\rightarrow\) (\(\cdot\) N)], [N \(\rightarrow\) \(\cdot\) NN], [N \(\rightarrow\) \(\cdot\) (N)], [N \(\rightarrow\) \(\cdot\) N *], [N \(\rightarrow\) \(\cdot\) a]\}

\subsection{c}
\label{sec:orga001b72}
\{[N \(\rightarrow\) (N \(\cdot\))]\}
\section{Question Five}
\label{sec:org4370427}
\subsection{a}
\label{sec:orgb30ece5}
\{[A \(\rightarrow\) \(\cdot\) C B], [C \(\rightarrow\) \(\cdot\) E D], [E \(\rightarrow\) \(\cdot\) x A y], [E \(\rightarrow\) \(\cdot\) x]\}

\subsection{b}
\label{sec:orgd13c8f9}
\{[B \(\rightarrow\) a \(\cdot\) C B], [C \(\rightarrow\) \(\cdot\) E D], [E \(\rightarrow\) \(\cdot\) x A y], [E \(\rightarrow\) \(\cdot\) x]\}

\subsection{c}
\label{sec:org2b3dacb}
\{[B \(\rightarrow\) a C \(\cdot\) B], [B \(\rightarrow\) \(\cdot\) a C B]\}

\subsection{d}
\label{sec:org5acc456}
\{[C \(\rightarrow\) E D \(\cdot\)]\}

\subsection{e}
\label{sec:org467fb21}
\{[D \(\rightarrow\) b \(\cdot\) E D], [E \(\rightarrow\) \(\cdot\) x A y], [E \(\rightarrow\) \(\cdot\) z]\}

\subsection{f}
\label{sec:orge62af27}
\{\}

\section{Question Six}
\label{sec:orgce910f1}
\begin{center}
\begin{tabular}{lrl}
GOTO & state & items\\[0pt]
 & 0 & closure(A' \(\rightarrow\) \(\cdot\) A)\\[0pt]
 &  & A' \(\rightarrow\) \(\cdot\) A\\[0pt]
 &  & A \(\rightarrow\) \(\cdot\) a A\\[0pt]
 &  & A \(\rightarrow\) \(\cdot\) B\\[0pt]
 &  & B \(\rightarrow\) \(\cdot\) b\\[0pt]
(0, A) & 1 & closure(A' \(\rightarrow\) A \(\cdot\))\\[0pt]
 &  & A' \(\rightarrow\) A \(\cdot\)\\[0pt]
(0, B) & 2 & closure(A \(\rightarrow\) B \(\cdot\))\\[0pt]
 &  & A \(\rightarrow\) B \(\cdot\)\\[0pt]
(0, a) & 3 & closure(A \(\rightarrow\) a \(\cdot\) A b B)\\[0pt]
 &  & A \(\rightarrow\) a \(\cdot\) A\\[0pt]
 &  & A \(\rightarrow\) \(\cdot\) a A\\[0pt]
 &  & A \(\rightarrow\) \(\cdot\) B\\[0pt]
 &  & B \(\rightarrow\) \(\cdot\) b\\[0pt]
(0, b) & 4 & closure(B \(\rightarrow\) b \(\cdot\) )\\[0pt]
 &  & B \(\rightarrow\) b \(\cdot\)\\[0pt]
(3, A) & 5 & closure(A \(\rightarrow\) a A \(\cdot\) b B)\\[0pt]
 &  & A \(\rightarrow\) a A \(\cdot\)\\[0pt]
(3, B) & 2 & A \(\rightarrow\) B \(\cdot\)\\[0pt]
(3, a) & 3 & A \(\rightarrow\) a \(\cdot\) A\\[0pt]
 &  & A \(\rightarrow\) \(\cdot\) a A\\[0pt]
 &  & A \(\rightarrow\) \(\cdot\) B\\[0pt]
 &  & B \(\rightarrow\) \(\cdot\) b\\[0pt]
(3, b) & 4 & B \(\rightarrow\) b \(\cdot\)\\[0pt]
(5, b) & 6 & closure(A \(\rightarrow\) a A b \(\cdot\) B)\\[0pt]
 &  & A \(\rightarrow\) a A b \(\cdot\) B\\[0pt]
 &  & B \(\rightarrow\) \(\cdot\) b\\[0pt]
(6, B) & 7 & closure(A \(\rightarrow\) a A b B \(\cdot\))\\[0pt]
 &  & A \(\rightarrow\) a A b B \(\cdot\)\\[0pt]
(6, b) & 4 & B \(\rightarrow\) b \(\cdot\)\\[0pt]
\end{tabular}
\end{center}

\section{Question Seven}
\label{sec:org5e0e964}
\subsection{First, Follow}
\label{sec:org631e4e0}
\begin{verbatim}
first(A') = first(A) = {a}
first(A) = first(B) = {a}
first(B) = first(a) = {a}

follow(A') = {$}
follow(A) = first(b) U follow(A') = {b, $}
follow(B) = first(a) U follow(A) = {a, b, $}
\end{verbatim}

\subsection{Items}
\label{sec:orga0edb23}
\begin{center}
\begin{tabular}{lrl}
GOTO & state & items\\[0pt]
 & 0 & closure(A' \(\rightarrow\) \(\cdot\) A)\\[0pt]
 &  & A' \(\rightarrow\) \(\cdot\) A\\[0pt]
 &  & A \(\rightarrow\) \(\cdot\) A b B\\[0pt]
 &  & A \(\rightarrow\) \(\cdot\) B a\\[0pt]
 &  & B \(\rightarrow\) \(\cdot\) a\\[0pt]
(0, A) & 1 & closure(\{A \(\rightarrow\) A \(\cdot\) b B, A' \(\rightarrow\) A \(\cdot\)\})\\[0pt]
 &  & A \(\rightarrow\) A \(\cdot\) b B\\[0pt]
 &  & A' \(\rightarrow\) A \(\cdot\)\\[0pt]
(0, B) & 2 & closure(A \(\rightarrow\) B \(\cdot\) a)\\[0pt]
 &  & A \(\rightarrow\) B \(\cdot\) a\\[0pt]
(0, a) & 3 & closure(B \(\rightarrow\) a \(\cdot\))\\[0pt]
 &  & B \(\rightarrow\) a \(\cdot\)\\[0pt]
(1, b) & 4 & closure(A \(\rightarrow\) A b \(\cdot\) B)\\[0pt]
 &  & A \(\rightarrow\) A b \(\cdot\) B\\[0pt]
 &  & B \(\rightarrow\) \(\cdot\) a\\[0pt]
(2, a) & 5 & closure(A \(\rightarrow\) B a \(\cdot\))\\[0pt]
 &  & A \(\rightarrow\) B a \(\cdot\)\\[0pt]
(4, B) & 6 & closure(A \(\rightarrow\) A b B \(\cdot\))\\[0pt]
 &  & A \(\rightarrow\) A b B \(\cdot\)\\[0pt]
(4, a) & 3 & closure(B \(\rightarrow\) a \(\cdot\))\\[0pt]
 &  & B \(\rightarrow\) a \(\cdot\)\\[0pt]
\end{tabular}
\end{center}

\subsection{SLR Parse Table}
\label{sec:org65e916a}
\begin{center}
\begin{tabular}{rlllrr}
state & a & b & \$ & A & B\\[0pt]
0 & s3 &  &  & 1 & 2\\[0pt]
1 &  & s4 & acc &  & \\[0pt]
2 & s5 &  &  &  & \\[0pt]
3 & r4 & r4 & r4 &  & \\[0pt]
4 & s3 &  &  &  & 6\\[0pt]
5 &  & r3 & r3 &  & \\[0pt]
6 &  & r2 & r2 &  & \\[0pt]
\end{tabular}
\end{center}

\subsection{Parse of "aaba"}
\label{sec:orgc668927}
\begin{center}
\begin{tabular}{llll}
stack & symbols & input & action\\[0pt]
0 &  & aaba\$ & shift 3\\[0pt]
0 3 & a & aba\$ & reduce 4\\[0pt]
0 2 & B & aba\$ & shift 5\\[0pt]
0 2 5 & Ba & ba\$ & reduce 3\\[0pt]
0 1 & A & ba\$ & shift 4\\[0pt]
0 1 4 & Ab & a\$ & shift 3\\[0pt]
0 1 4 3 & Aba & \$ & reduce 4\\[0pt]
0 1 4 6 & AbB & \$ & reduce 2\\[0pt]
0 1 & A & \$ & accept\\[0pt]
\end{tabular}
\end{center}

\section{Question Eight}
\label{sec:org9b3771e}
\subsection{First, Follow}
\label{sec:org8892bb8}
\begin{verbatim}
first(A') = first(A) = {a, b, f}
first(A) = first(a) U first(B) = {a, b, f}
first(B) = first(b) U first(f) = {b, f}

follow(A') = {$}
follow(A) = follow(A') = {$}
follow(B) = first(a) = {a}
\end{verbatim}
\subsection{Items}
\label{sec:orgc50d475}
\begin{center}
\begin{tabular}{lrl}
GOTO & state & items\\[0pt]
 & 0 & closure(A' \(\rightarrow\) \(\cdot\) A, $\backslash$$)\\[0pt]
 &  & A' \(\rightarrow\) \(\cdot\) A, \$\\[0pt]
 &  & A \(\rightarrow\) \(\cdot\) B a, \$\\[0pt]
 &  & A \(\rightarrow\) \(\cdot\) a A, \$\\[0pt]
 &  & B \(\rightarrow\) \(\cdot\) b B, a\\[0pt]
 &  & B \(\rightarrow\) \(\cdot\) f, a\\[0pt]
(0, A) & 1 & closure(A' \(\rightarrow\) A \(\cdot\), \$)\\[0pt]
 &  & A' \(\rightarrow\) A \(\cdot\), \$\\[0pt]
(0, B) & 2 & closure(A \(\rightarrow\) B \(\cdot\) a, \$)\\[0pt]
 &  & A \(\rightarrow\) B \(\cdot\) a, \$\\[0pt]
(0, a) & 3 & closure(A \(\rightarrow\) a \(\cdot\) A, \$)\\[0pt]
 &  & A \(\rightarrow\) a \(\cdot\) A, \$\\[0pt]
 &  & A \(\rightarrow\) \(\cdot\) B a, \$\\[0pt]
 &  & A \(\rightarrow\) \(\cdot\) a A, \$\\[0pt]
 &  & B \(\rightarrow\) \(\cdot\) b B, a\\[0pt]
 &  & B \(\rightarrow\) \(\cdot\) f, a\\[0pt]
(0, b) & 4 & closure(B \(\rightarrow\) b \(\cdot\) B, a)\\[0pt]
 &  & B \(\rightarrow\) b \(\cdot\) B, a\\[0pt]
 &  & B \(\rightarrow\) \(\cdot\) b B, a\\[0pt]
 &  & B \(\rightarrow\) \(\cdot\) f, a\\[0pt]
(0, f) & 5 & closure(B \(\rightarrow\) f \(\cdot\), a)\\[0pt]
 &  & B \(\rightarrow\) f \(\cdot\), a\\[0pt]
(2, a) & 6 & closure(A \(\rightarrow\) B a \(\cdot\), \$)\\[0pt]
 &  & A \(\rightarrow\) B a \(\cdot\), \$\\[0pt]
(3, A) & 7 & closure(A \(\rightarrow\) a A \(\cdot\), \$)\\[0pt]
 &  & A \(\rightarrow\) a A \(\cdot\), $\backslash$$\\[0pt]
(3, B) & 2 & closure(A \(\rightarrow\) B \(\cdot\) a, \$)\\[0pt]
 &  & A \(\rightarrow\) B \(\cdot\) a, \$\\[0pt]
(3, a) & 3 & closure(A \(\rightarrow\) a \(\cdot\) A, \$)\\[0pt]
 &  & A \(\rightarrow\) a \(\cdot\) A, \$\\[0pt]
 &  & A \(\rightarrow\) \(\cdot\) B a, \$\\[0pt]
 &  & A \(\rightarrow\) \(\cdot\) a A, \$\\[0pt]
 &  & B \(\rightarrow\) \(\cdot\) b B, a\\[0pt]
 &  & B \(\rightarrow\) \(\cdot\) f, a\\[0pt]
(3, b) & 4 & closure(B \(\rightarrow\) b \(\cdot\) B, a)\\[0pt]
 &  & B \(\rightarrow\) b \(\cdot\) B, a\\[0pt]
 &  & B \(\rightarrow\) \(\cdot\) b B, a\\[0pt]
 &  & B \(\rightarrow\) \(\cdot\) f, a\\[0pt]
(3, f) & 5 & closure(B \(\rightarrow\) f \(\cdot\), a)\\[0pt]
 &  & B \(\rightarrow\) f \(\cdot\), a\\[0pt]
(4, B) & 8 & closure(B \(\rightarrow\) b B \(\cdot\), a)\\[0pt]
 &  & B \(\rightarrow\) b B \(\cdot\), a\\[0pt]
(4, b) & 4 & closure(B \(\rightarrow\) b \(\cdot\) B, a)\\[0pt]
 &  & B \(\rightarrow\) b \(\cdot\) B, a\\[0pt]
 &  & B \(\rightarrow\) \(\cdot\) b B, a\\[0pt]
 &  & B \(\rightarrow\) \(\cdot\) f, a\\[0pt]
(4, f) & 5 & closure(B \(\rightarrow\) f \(\cdot\), a)\\[0pt]
 &  & B \(\rightarrow\) f \(\cdot\), a\\[0pt]
\end{tabular}
\end{center}
\subsection{LR Parse Table}
\label{sec:org69f6dbf}
\begin{center}
\begin{tabular}{rllllrr}
state & a & b & f & \$ & A & B\\[0pt]
0 & s3 & s4 & s5 &  & 1 & 2\\[0pt]
1 &  &  &  & acc &  & \\[0pt]
2 & s6 &  &  &  &  & \\[0pt]
3 & s3 & s4 & s5 &  & 7 & 2\\[0pt]
4 &  & s4 & s5 &  &  & 8\\[0pt]
5 & r5 &  &  &  &  & \\[0pt]
6 &  &  &  & r2 &  & \\[0pt]
7 &  &  &  & r3 &  & \\[0pt]
8 & r4 &  &  &  &  & \\[0pt]
\end{tabular}
\end{center}

\subsection{Parse of "abfa"}
\label{sec:org1d0a90c}
\begin{center}
\begin{tabular}{llll}
stack & symbols & input & action\\[0pt]
0 &  & abfa\$ & shift 3\\[0pt]
0 3 & a & bfa\$ & shift 4\\[0pt]
0 3 4 & ab & fa\$ & shift 5\\[0pt]
0 3 4 5 & abf & a\$ & reduce 5\\[0pt]
0 3 4 8 & abB & a\$ & reduce 4\\[0pt]
0 3 2 & aB & a\$ & shift 6\\[0pt]
0 3 2 6 & aBa & \$ & reduce 2\\[0pt]
0 3 7 & aBa & \$ & reduce 3\\[0pt]
0 1 & aA & \$ & accept\\[0pt]
\end{tabular}
\end{center}
\end{document}