% 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}