#+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]]