From 6bf4b90c90f15f4ab60833bddf5b5756d1a6b1f6 Mon Sep 17 00:00:00 2001
From: Elizabeth Alexander Hunt <me@liz.coffee>
Date: Thu, 2 Jul 2026 11:55:17 -0700
Subject: Init

---
 .../cs5300/homework-seven/compilers_assn_7.tex     | 381 +++++++++++++++++++++
 1 file changed, 381 insertions(+)
 create mode 100644 Homework/cs5300/homework-seven/compilers_assn_7.tex

(limited to 'Homework/cs5300/homework-seven/compilers_assn_7.tex')

diff --git a/Homework/cs5300/homework-seven/compilers_assn_7.tex b/Homework/cs5300/homework-seven/compilers_assn_7.tex
new file mode 100644
index 0000000..fc4c607
--- /dev/null
+++ b/Homework/cs5300/homework-seven/compilers_assn_7.tex
@@ -0,0 +1,381 @@
+% 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}
\ No newline at end of file
-- 
cgit v1.3

