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

---
 Homework/cs5300/homework-two/compilers_assn_2.tex | 275 ++++++++++++++++++++++
 1 file changed, 275 insertions(+)
 create mode 100644 Homework/cs5300/homework-two/compilers_assn_2.tex

(limited to 'Homework/cs5300/homework-two/compilers_assn_2.tex')

diff --git a/Homework/cs5300/homework-two/compilers_assn_2.tex b/Homework/cs5300/homework-two/compilers_assn_2.tex
new file mode 100644
index 0000000..408558b
--- /dev/null
+++ b/Homework/cs5300/homework-two/compilers_assn_2.tex
@@ -0,0 +1,275 @@
+% Created 2023-01-27 Fri 20:04
+% Intended LaTeX compiler: pdflatex
+\documentclass[11pt]{article}
+\usepackage[utf8]{inputenc}
+\usepackage[T1]{fontenc}
+\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{amsmath}
+\author{Logan Hunt}
+\date{\today}
+\title{Assignment Two}
+\hypersetup{
+ pdfauthor={Logan Hunt},
+ pdftitle={Assignment Two},
+ pdfkeywords={},
+ pdfsubject={},
+ pdfcreator={Emacs 28.2 (Org mode 9.6.1)}, 
+ pdflang={English}}
+\begin{document}
+
+\maketitle
+\setlength\parindent{0pt}
+
+\section{Question One}
+\label{sec:org87beba7}
+\subsection{a}
+\label{sec:orgf2add9e}
+There are four productions.
+\subsection{b}
+\label{sec:orgc7248f7}
+The terminals of this grammar are:
+
+\begin{verbatim}
+a b c d
+\end{verbatim}
+\subsection{c}
+\label{sec:orgf876127}
+N\textsubscript{1}, N\textsubscript{2}, N\textsubscript{3}, N\textsubscript{4} are all nonterminals.
+\subsection{d}
+\label{sec:orgf042bc3}
+The start symbol is N\textsubscript{1}.
+\subsection{e}
+\label{sec:orgd668266}
+The symbols N\textsubscript{1}, N\textsubscript{2}, N\textsubscript{3}, N\textsubscript{4} are present in the production heads.
+\subsection{f}
+\label{sec:org34be0af}
+N\textsubscript{2}, N\textsubscript{3}, N\textsubscript{4}, "a", "b", "c", "d" are present in the production bodies.
+\section{Question Two}
+\label{sec:org4b362f4}
+\subsection{a}
+\label{sec:orga65ff15}
+There are fifteen productions.
+\subsection{b}
+\label{sec:org3c23122}
+The terminals of this grammar are:
+\begin{verbatim}
+0 1 2 3 4 5 6 7 8 9 + -
+\end{verbatim}
+\subsection{c}
+\label{sec:org899f753}
+The nonterminals are "list" and "digit".
+\subsection{d}
+\label{sec:org3be2a40}
+The start symbol is "list".
+\subsection{e}
+\label{sec:org19adb89}
+"list" and "digit" are present in the production heads.
+\subsection{f}
+\label{sec:org6764041}
+"list", "digit", 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, \(+\), \(-\) are present in the production bodies.
+\section{Question Three}
+\label{sec:orgcef93d4}
+\begin{verbatim}
+x -> A (3)
+x -> A (3)
+xx* -> AA* (2)
+(xx*)x+ -> AA+ (1)
+((xx*)x+)x+ -> AA+ (1)
+\end{verbatim}
+\section{Question Four}
+\label{sec:orge97ecd2}
+\subsection{a}
+\label{sec:org8eb6283}
+Examples:
+\begin{enumerate}
+\item "xy"
+\item "xxyy"
+\item "xxxyyy"
+\item "xxxxyyyy"
+\end{enumerate}
+
+This grammar generates a string of x's prepended to a string of y's with the same amount of characters.
+
+The grammar is unambiguous.
+
+\subsection{b}
+\label{sec:org3b9ad4f}
+Example:
+\begin{enumerate}
+\item "x"
+\item "-xx"
+\item "+-xx-xx"
+\item "-x-xx"
+\end{enumerate}
+
+This grammar generates addition and subtraction prefix expressions on "x" or chains of "x".
+
+The grammar is unambiguous.
+
+\subsection{c}
+\label{sec:orgb960951}
+Example:
+\begin{enumerate}
+\item ""
+\item "()"
+\item "()()"
+\item "(())"
+\end{enumerate}
+
+This grammar generates balanced sets of potentially nested parentheses.
+
+The grammar is ambiguous. For example, the string "()()" can be parsed multiple ways:
+
+\begin{center}
+\includegraphics[width=250px]{./4c.png}
+\end{center}
+
+\subsection{d}
+\label{sec:org13f5216}
+\begin{enumerate}
+\item ""
+\item "xyyx"
+\item "xyxy"
+\item "xy"
+\end{enumerate}
+
+This grammar generates jumbled combinations of the same number of x's and y's.
+
+The grammar is ambiguous.
+
+For example, the string "xyxy" has two parse trees:
+
+\begin{center}
+\includegraphics[width=250px]{./4d.png}
+\end{center}
+
+\subsection{e}
+\label{sec:org88fd9c7}
+\begin{enumerate}
+\item "(x)**"
+\item "x+x"
+\item "x*"
+\item "xx"
+\end{enumerate}
+
+This grammar generates combinations of + / * expressions on x in any nested amount of balanced parentheses.
+
+This grammar is unambiguous.
+
+\section{Question Five}
+\label{sec:org85d516c}
+\subsection{a}
+\label{sec:orga24c671}
+\begin{center}
+\includegraphics[width=250px]{./5a.png}
+\end{center}
+
+\subsection{b}
+\label{sec:org2837306}
+\begin{center}
+\includegraphics[width=250px]{./5b.png}
+\end{center}
+
+\section{Question Six}
+\label{sec:orgfa68e73}
+\begin{verbatim}
+expr -> expr expr op
+expr -> factor
+op -> + | - | / | *
+factor -> 0
+factor -> 1
+factor ... 9
+\end{verbatim}
+\section{Question Seven}
+\label{sec:org6a6c81c}
+\begin{verbatim}
+sentence -> character
+sentence -> character,sentence
+character -> a
+character -> b
+character -> ...
+\end{verbatim}
+\section{Question Eight}
+\label{sec:orgc9de4dd}
+\begin{verbatim}
+expr -> expr - term
+expr -> expr + term
+expr -> expr * term
+expr -> expr / term
+expr -> term
+term -> +num
+term -> -num
+term -> num
+num -> Integer
+num -> Ident
+\end{verbatim}
+\section{Question Nine}
+\label{sec:org0c5cd84}
+\begin{center}
+\includegraphics[width=250px]{./9.png}
+\end{center}
+\section{Question Ten}
+\label{sec:org51dec25}
+\begin{verbatim}
+expr -> {print '+'} expr + term
+expr -> {print '-'} expr - term
+expr -> term                     
+term -> 0 {print '0'}
+term -> 1 {print '1'}          
+term -> ... {print ...}
+\end{verbatim}
+\section{Question Eleven}
+\label{sec:orgfe9e241}
+\subsection{3-1+2}
+\label{sec:org327f033}
+\begin{center}
+\includegraphics[width=250px]{./11-1.png}
+\end{center}
+\subsection{2+3-1}
+\label{sec:org9170442}
+\begin{center}
+\includegraphics[width=250px]{./11-2.png}
+\end{center}
+
+\section{Question Twelve}
+\label{sec:org24eacf8}
+Predictive parsing is a special kind of recursive descent parsing where the "lookahead unambiguously determines the flow of control".
+\section{Question Thirteen}
+\label{sec:org23d57f5}
+None of the productions have the same start symbol (disjoint \texttt{FIRST} sets), and it is not left-recursive.
+\section{Question Fourteen}
+\label{sec:org71b8b64}
+See \texttt{Infix.java}.
+\section{Question Fifteen}
+\label{sec:org1569332}
+\begin{verbatim}
+A -> w R
+R -> x y z R | \epsilon
+\end{verbatim}
+\section{Question Sixteen}
+\label{sec:org626e3a3}
+\begin{verbatim}
+S -> w R
+R -> x y z R
+R -> g h R
+R -> \epsilon
+\end{verbatim}
+\section{Question Seventeen}
+\label{sec:org8167863}
+\begin{center}
+\includegraphics[width=.9\linewidth]{./17.png}
+\end{center}
+\section{Question Eighteen}
+\label{sec:org2d4c8ce}
+\begin{center}
+\includegraphics[width=250px]{./18.png}
+\end{center}
+\end{document}
\ No newline at end of file
-- 
cgit v1.3

