InitHEADmain

15 files changed, 569 insertions, 0 deletions

diff --git a/Homework/cs5300/homework-two/11-1.png b/Homework/cs5300/homework-two/11-1.png
new file mode 100644
index 0000000..a473d2b
--- /dev/null
+++ b/Homework/cs5300/homework-two/11-1.png
diff --git a/Homework/cs5300/homework-two/11-2.png b/Homework/cs5300/homework-two/11-2.png
new file mode 100644
index 0000000..39e507a
--- /dev/null
+++ b/Homework/cs5300/homework-two/11-2.png
diff --git a/Homework/cs5300/homework-two/17.png b/Homework/cs5300/homework-two/17.png
new file mode 100644
index 0000000..2ee9912
--- /dev/null
+++ b/Homework/cs5300/homework-two/17.png
diff --git a/Homework/cs5300/homework-two/18.png b/Homework/cs5300/homework-two/18.png
new file mode 100644
index 0000000..b32de02
--- /dev/null
+++ b/Homework/cs5300/homework-two/18.png
diff --git a/Homework/cs5300/homework-two/4c.png b/Homework/cs5300/homework-two/4c.png
new file mode 100644
index 0000000..a83f0e4
--- /dev/null
+++ b/Homework/cs5300/homework-two/4c.png
diff --git a/Homework/cs5300/homework-two/4d.png b/Homework/cs5300/homework-two/4d.png
new file mode 100644
index 0000000..c45ec6d
--- /dev/null
+++ b/Homework/cs5300/homework-two/4d.png
diff --git a/Homework/cs5300/homework-two/5a.png b/Homework/cs5300/homework-two/5a.png
new file mode 100644
index 0000000..251b097
--- /dev/null
+++ b/Homework/cs5300/homework-two/5a.png
diff --git a/Homework/cs5300/homework-two/5b.png b/Homework/cs5300/homework-two/5b.png
new file mode 100644
index 0000000..af0594c
--- /dev/null
+++ b/Homework/cs5300/homework-two/5b.png
diff --git a/Homework/cs5300/homework-two/9.png b/Homework/cs5300/homework-two/9.png
new file mode 100644
index 0000000..5dd948a
--- /dev/null
+++ b/Homework/cs5300/homework-two/9.png
diff --git a/Homework/cs5300/homework-two/Infix.class b/Homework/cs5300/homework-two/Infix.class
new file mode 100644
index 0000000..6def347
--- /dev/null
+++ b/Homework/cs5300/homework-two/Infix.class
diff --git a/Homework/cs5300/homework-two/Infix.java b/Homework/cs5300/homework-two/Infix.java
new file mode 100644
index 0000000..33c8dcf
--- /dev/null
+++ b/Homework/cs5300/homework-two/Infix.java
@@ -0,0 +1,72 @@
+import java.util.ArrayList;
+import java.io.IOException;
+
+public class Infix {
+    private ArrayList<Character> chars;
+    private int index;
+    
+    public static void main(String[] args) {
+        String str = "+++12-835";
+        if (args.length > 0) {
+            str = args[0];
+        }
+        try {
+            Infix parser = new Infix(str);
+        } catch (Exception e) {
+            System.out.println("error");
+        }
+    }
+    
+    public Infix(String terminals) throws IOException {
+        this.index = 0;
+        this.chars = new ArrayList<Character>();
+        for (char c: terminals.toCharArray()) 
+            this.chars.add(c);
+        
+        this.list();
+
+        if (this.index < this.chars.size())
+            throw new IOException("Could not parse entire string");
+        
+        System.out.println();
+    }
+
+    private void list() throws IOException {
+        char lookahead = this.lookahead();
+        if (lookahead == '+' || lookahead == '-') {
+            match(lookahead);
+            System.out.write('(');
+            list();
+            System.out.write(lookahead);
+            list();
+            System.out.write(')');
+        }
+        else if (lookahead >= '0' && lookahead <= '9') 
+            digit();
+        else 
+            throw new IOException("Expected lookahead to be a digit or plus/minus");
+    }
+
+    private void digit() throws IOException {
+        char lookahead = this.lookahead();
+        if (lookahead >= '0' && lookahead <= '9') {
+            match(lookahead);
+            System.out.write(lookahead);
+            return;
+        }
+        throw new IOException("Expected lookahead to be a digit");
+    }
+
+    private void match(char t) throws IOException {
+        boolean matches = this.lookahead() == t;
+
+        if (matches) 
+            this.index += 1;
+        else if (!matches) 
+            throw new IOException("Expected " + (char)this.lookahead() + " to match " + (char)t);
+    }
+
+    private char lookahead() {
+        return this.chars.get(this.index);
+    }
+}
diff --git a/Homework/cs5300/homework-two/InfixTest.py b/Homework/cs5300/homework-two/InfixTest.py
new file mode 100644
index 0000000..826085d
--- /dev/null
+++ b/Homework/cs5300/homework-two/InfixTest.py
@@ -0,0 +1,30 @@
+#!/usr/bin/python
+
+import os
+
+i=1
+def test(cmd, expected):
+    global i
+    stream = os.popen(cmd)
+    output = stream.read()
+    output = output.strip()
+    if output != expected:
+        print('Failed test {} ({}). Should have been "{}". Was "{}".'
+              .format(i, cmd, expected, output))
+    else:
+        print('Passed test {}.'.format(i))
+    i=i+1
+# Compile the code
+os.system('javac Infix.java')
+# Run the tests. The first argument is the command to run
+# and the second argument is the expected output of the
+# program.
+test('java Infix +12', '(1+2)')
+test('java Infix -+121', '((1+2)-1)')
+test('java Infix -+9-8+127', '((9+(8-(1+2)))-7)')
+test('java Infix -+9-81+27', '((9+(8-1))-(2+7))')
+test('java Infix +7', '(7+error')
+test('java Infix -9+7', '(9-(7+error')
+test('java Infix -+9-8+12', '((9+(8-(1+2)))-error')
+test('java Infix -+9-a+127', '((9+(error')
+test('java Infix -9-8+12+7', '(9-(8-(1+2)))error')
diff --git a/Homework/cs5300/homework-two/compilers_assn_2.org b/Homework/cs5300/homework-two/compilers_assn_2.org
new file mode 100644
index 0000000..186303d
--- /dev/null
+++ b/Homework/cs5300/homework-two/compilers_assn_2.org
@@ -0,0 +1,192 @@
+#+TITLE: Assignment Two
+#+AUTHOR: Logan Hunt
+#+STARTUP: entitiespretty fold inlineimages
+#+LATEX_HEADER: \notindent \notga \usepackage{ dsfont } \usepackage{amsmath}
+#+LATEX: \setlength\parindent{0pt}
+#+OPTIONS: toc:nil
+
+* Question One
+** a
+There are four productions.
+** b
+The terminals of this grammar are:
+
+\begin{verbatim}
+a b c d
+\end{verbatim}
+** c
+N_1, N_2, N_3, N_4 are all nonterminals.
+** d
+The start symbol is N_1.
+** e
+The symbols N_1, N_2, N_3, N_4 are present in the production heads.
+** f
+N_2, N_3, N_4, "a", "b", "c", "d" are present in the production bodies.
+* Question Two
+** a
+There are fifteen productions.
+** b
+The terminals of this grammar are:
+\begin{verbatim}
+0 1 2 3 4 5 6 7 8 9 + -
+\end{verbatim}
+** c
+The nonterminals are "list" and "digit".
+** d
+The start symbol is "list".
+** e
+"list" and "digit" are present in the production heads.
+** f
+"list", "digit", 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, $+$, $-$ are present in the production bodies.
+* Question Three
+\begin{verbatim}
+x -> A (3)
+x -> A (3)
+xx* -> AA* (2)
+(xx*)x+ -> AA+ (1)
+((xx*)x+)x+ -> AA+ (1)
+\end{verbatim}
+* Question Four
+** a
+Examples:
+1. "xy"
+2. "xxyy"
+3. "xxxyyy"
+4. "xxxxyyyy"
+
+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.
+
+** b
+Example:
+1. "x"
+2. "-xx"
+3. "+-xx-xx"
+4. "-x-xx"
+
+This grammar generates addition and subtraction prefix expressions on "x" or chains of "x".
+
+The grammar is unambiguous.
+
+** c
+Example:
+1. ""
+2. "()"
+3. "()()"
+4. "(())"
+
+This grammar generates balanced sets of potentially nested parentheses.
+
+The grammar is ambiguous. For example, the string "()()" can be parsed multiple ways:
+
+#+attr_latex: :width 250px
+[[./4c.png]]
+
+** d
+1. ""
+2. "xyyx"
+3. "xyxy"
+4. "xy"
+
+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:
+
+#+attr_latex: :width 250px
+[[./4d.png]]
+
+** e
+1. "(x)**"
+2. "x+x"
+3. "x*"
+4. "xx"
+
+This grammar generates combinations of + / * expressions on x in any nested amount of balanced parentheses.
+
+This grammar is unambiguous.
+
+* Question Five
+** a
+#+attr_latex: :width 250px
+[[./5a.png]]
+
+** b
+#+attr_latex: :width 250px
+[[./5b.png]]
+
+* Question Six
+\begin{verbatim}
+expr -> expr expr op
+expr -> factor
+op -> + | - | / | *
+factor -> 0
+factor -> 1
+factor ... 9
+\end{verbatim}
+* Question Seven
+\begin{verbatim}
+sentence -> character
+sentence -> character,sentence
+character -> a
+character -> b
+character -> ...
+\end{verbatim}
+* Question Eight
+\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}
+* Question Nine
+#+attr_latex: :width 250px
+[[./9.png]]
+* Question Ten
+\begin{verbatim}
+expr -> {print '+'} expr + term
+expr -> {print '-'} expr - term
+expr -> term                     
+term -> 0 {print '0'}
+term -> 1 {print '1'}          
+term -> ... {print ...}
+\end{verbatim}
+* Question Eleven
+** 3-1+2
+#+attr_latex: :width 250px
+[[./11-1.png]]
+** 2+3-1
+#+attr_latex: :width 250px
+[[./11-2.png]]
+
+* Question Twelve
+Predictive parsing is a special kind of recursive descent parsing where the "lookahead unambiguously determines the flow of control".
+* Question Thirteen
+None of the productions have the same start symbol (disjoint ~FIRST~ sets), and it is not left-recursive.
+* Question Fourteen
+See ~Infix.java~.
+* Question Fifteen
+\begin{verbatim}
+A -> w R
+R -> x y z R | \epsilon
+\end{verbatim}
+* Question Sixteen
+\begin{verbatim}
+S -> w R
+R -> x y z R
+R -> g h R
+R -> \epsilon
+\end{verbatim}
+* Question Seventeen
+[[./17.png]]
+* Question Eighteen
+#+attr_latex: :width 250px
+[[./18.png]]
diff --git a/Homework/cs5300/homework-two/compilers_assn_2.pdf b/Homework/cs5300/homework-two/compilers_assn_2.pdf
new file mode 100644
index 0000000..f5ea2f2
--- /dev/null
+++ b/Homework/cs5300/homework-two/compilers_assn_2.pdf
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