#+TITLE: Assignment Seven
#+AUTHOR: Lizzy Hunt
#+STARTUP: entitiespretty fold inlineimages
#+LATEX_HEADER: \notindent \notga \usepackage{ dsfont } \usepackage[utf8]{inputenc}  \usepackage{amsmath} \usepackage{fontspec} \usepackage[a4paper,margin=1in,portrait]{geometry} \usepackage{fontspec} \setmonofont{DejaVu Sans Mono}
#+LATEX:  \setlength\parindent{0pt}
#+LATEX_COMPILER: lualatex
#+OPTIONS: toc:nil

* Question One
** Removal of Left Recursion
\begin{verbatim}
A  -> BbA'
A' -> aA' | ε
B  -> aB | b
\end{verbatim}
** Left Factoring
No need to left factor this grammar
** Parse Table
*** Calculation of first and follow
\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}

*** Predictive Parse Table
| Nonterminal | a        | b        | $      |
| A           | A \rightarrow BbA' | A \rightarrow BbA' |        |
| A'          | A' \rightarrow aA' |          | A' \rightarrow \epsilon |
| B           | B \rightarrow aB   | B \rightarrow b    |        |

** Parse of "abba"
| Stack  | Input | Action   | Matched |
| A$     | abba$ | A \rightarrow BbA' |         |
| BbA'$  | abba$ | B \rightarrow aB   |         |
| aBbA'$ | bba$  | Match a  | a       |
| BbA'$  | bba$  | B \rightarrow b    | a       |
| bbA'$  | bba$  | Match b  | ab      |
| bA'$   | ba$   | Match b  | abb     |
| A'$    | a$    | A \rightarrow aA'  | abb     |
| aA'$   | a$    | Match a  | abba    |
| A'$    | $     | A' \rightarrow ε   | abba    |
| ε$     | $     | Match ε  | abba    |
| $      | $     | Match $  |         |
|        |       | Accept   |         |

* Question Two
| Stack | Input     | Action           |
| $     | (id)*id$  | shift            |
| $(    | id)*id$   | shift            |
| $(id  | )*id$     | reduce F \rightarrow id    |
| $(F   | )*id$     | reduce F \rightarrow E     |
| $(E)  | *id$      | shift            |
| $F    | *id$      | reduce F \rightarrow (E)   |
| $T    | *id$      | reduce T \rightarrow F     |
| $T*   | id$       | shift            |
| $T*id | $         | shift            |
| $T*F  | $         | reduce F \rightarrow id    |
| $T    | $         | reduce T \rightarrow T * F |
| $E    | $         | reduce E \rightarrow T     |
| $E    | $         | accept           |

* Question Three
| Stack       | Input   | Action    |
| $           | ()(())$ | Shift     |
| $(          | )(())$  | Shift     |
| $()         | (())$   | Shift     |
| $Pair       | (())$   | Reduce R5 |
| $List       | (())$   | Reduce R3 |
| $List(      | ())$    | Shift     |
| $List((     | ))$     | Shift     |
| $List(()    | )$      | Shift     |
| $List(Pair  | )$      | Reduce R5 |
| $List(Pair) | $       | Shift     |
| $List Pair  | $       | Reduce R4 |
| $Goal       | $       | Reduce R1 |
| $Goal       | $       | Accept    |

* Question Four
** a
{[N \rightarrow \cdot N + N], [N \rightarrow \cdot NN], [N \rightarrow \cdot (N)], [N \rightarrow \cdot N *], [N \rightarrow \cdot a]}

** b
{[N \rightarrow (\cdot N)], [N \rightarrow \cdot NN], [N \rightarrow \cdot (N)], [N \rightarrow \cdot N *], [N \rightarrow \cdot a]}

** c
{[N \rightarrow (N \cdot)]}
* Question Five
** a
{[A \rightarrow \cdot C B], [C \rightarrow \cdot E D], [E \rightarrow \cdot x A y], [E \rightarrow \cdot x]}

** b
{[B \rightarrow a \cdot C B], [C \rightarrow \cdot E D], [E \rightarrow \cdot x A y], [E \rightarrow \cdot x]}

** c
{[B \rightarrow a C \cdot B], [B \rightarrow \cdot a C B]}

** d
{[C \rightarrow E D \cdot]}

** e
{[D \rightarrow b \cdot E D], [E \rightarrow \cdot x A y], [E \rightarrow \cdot z]}

** f
{}

* Question Six
| GOTO   | state | items                  |
|        |     0 | closure(A' \rightarrow \cdot A)      |
|        |       | A' \rightarrow \cdot A               |
|        |       | A \rightarrow \cdot a A              |
|        |       | A \rightarrow \cdot B                |
|        |       | B \rightarrow \cdot b                |
| (0, A) |     1 | closure(A' \rightarrow A \cdot)      |
|        |       | A' \rightarrow A \cdot               |
| (0, B) |     2 | closure(A \rightarrow B \cdot)       |
|        |       | A \rightarrow B \cdot                |
| (0, a) |     3 | closure(A \rightarrow a \cdot A b B) |
|        |       | A \rightarrow a \cdot A              |
|        |       | A \rightarrow \cdot a A              |
|        |       | A \rightarrow \cdot B                |
|        |       | B \rightarrow \cdot b                |
| (0, b) |     4 | closure(B \rightarrow b \cdot )      |
|        |       | B \rightarrow b \cdot                |
| (3, A) |     5 | closure(A \rightarrow a A \cdot b B) |
|        |       | A \rightarrow a A \cdot              |
| (3, B) |     2 | A \rightarrow B \cdot                |
| (3, a) |     3 | A \rightarrow a \cdot A              |
|        |       | A \rightarrow \cdot a A              |
|        |       | A \rightarrow \cdot B                |
|        |       | B \rightarrow \cdot b                |
| (3, b) |     4 | B \rightarrow b \cdot                |
| (5, b) |     6 | closure(A \rightarrow a A b \cdot B) |
|        |       | A \rightarrow a A b \cdot B          |
|        |       | B \rightarrow \cdot b                |
| (6, B) |     7 | closure(A \rightarrow a A b B \cdot) |
|        |       | A \rightarrow a A b B \cdot          |
| (6, b) |     4 | B \rightarrow b \cdot                |

* Question Seven
** First, Follow
\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}

** Items
| GOTO   | state | items                            |
|        |     0 | closure(A' \rightarrow \cdot A)                |
|        |       | A' \rightarrow \cdot A                         |
|        |       | A \rightarrow \cdot A b B                      |
|        |       | A \rightarrow \cdot B a                        |
|        |       | B \rightarrow \cdot a                          |
| (0, A) |     1 | closure({A \rightarrow A \cdot b B, A' \rightarrow A \cdot}) |
|        |       | A \rightarrow A \cdot b B                      |
|        |       | A' \rightarrow A \cdot                         |
| (0, B) |     2 | closure(A \rightarrow B \cdot a)               |
|        |       | A \rightarrow B \cdot a                        |
| (0, a) |     3 | closure(B \rightarrow a \cdot)                 |
|        |       | B \rightarrow a \cdot                          |
| (1, b) |     4 | closure(A \rightarrow A b \cdot B)             |
|        |       | A \rightarrow A b \cdot B                      |
|        |       | B \rightarrow \cdot a                          |
| (2, a) |     5 | closure(A \rightarrow B a \cdot)               |
|        |       | A \rightarrow B a \cdot                        |
| (4, B) |     6 | closure(A \rightarrow A b B \cdot)             |
|        |       | A \rightarrow A b B \cdot                      |
| (4, a) |     3 | closure(B \rightarrow a \cdot)                 |
|        |       | B \rightarrow a \cdot                          |

** SLR Parse Table
| state | a  | b  | $   | A | B |
|     0 | s3 |    |     | 1 | 2 |
|     1 |    | s4 | acc |   |   |
|     2 | s5 |    |     |   |   |
|     3 | r4 | r4 | r4  |   |   |
|     4 | s3 |    |     |   | 6 |
|     5 |    | r3 | r3  |   |   |
|     6 |    | r2 | r2  |   |   |

** Parse of "aaba"
| stack   | symbols | input   | action   |
| 0       |         | aaba$   | shift 3  |
| 0 3     | a       | aba$    | reduce 4 |
| 0 2     | B       | aba$    | shift 5  |
| 0 2 5   | Ba      | ba$     | reduce 3 |
| 0 1     | A       | ba$     | shift 4  |
| 0 1 4   | Ab      | a$      | shift 3  |
| 0 1 4 3 | Aba     | $       | reduce 4 |
| 0 1 4 6 | AbB     | $       | reduce 2 |
| 0 1     | A       | $       | accept   |

* Question Eight
** First, Follow
\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}
** Items
| GOTO   | state | items                  |
|        |     0 | closure(A' \rightarrow \cdot A, \$)  |
|        |       | A' \rightarrow \cdot A, $            |
|        |       | A \rightarrow \cdot B a, $           |
|        |       | A \rightarrow \cdot a A, $           |
|        |       | B \rightarrow \cdot b B, a           |
|        |       | B \rightarrow \cdot f, a             |
| (0, A) |     1 | closure(A' \rightarrow A \cdot, $)   |
|        |       | A' \rightarrow A \cdot, $            |
| (0, B) |     2 | closure(A \rightarrow B \cdot a, $)  |
|        |       | A \rightarrow B \cdot a, $           |
| (0, a) |     3 | closure(A \rightarrow a \cdot A, $)  |
|        |       | A \rightarrow a \cdot A, $           |
|        |       | A \rightarrow \cdot B a, $           |
|        |       | A \rightarrow \cdot a A, $           |
|        |       | B \rightarrow \cdot b B, a           |
|        |       | B \rightarrow \cdot f, a             |
| (0, b) |     4 | closure(B \rightarrow b \cdot B, a)  |
|        |       | B \rightarrow b \cdot B, a           |
|        |       | B \rightarrow \cdot b B, a           |
|        |       | B \rightarrow \cdot f, a             |
| (0, f) |     5 | closure(B \rightarrow f \cdot, a)    |
|        |       | B \rightarrow f \cdot, a             |
| (2, a) |     6 | closure(A \rightarrow B a \cdot, $)  |
|        |       | A \rightarrow B a \cdot, $           |
| (3, A) |     7 | closure(A \rightarrow a A \cdot, $)  |
|        |       | A \rightarrow a A \cdot, \$          |
| (3, B) |     2 | closure(A \rightarrow B \cdot a, $)  |
|        |       | A \rightarrow B \cdot a, $           |
| (3, a) |     3 | closure(A \rightarrow a \cdot A, $)  |
|        |       | A \rightarrow a \cdot A, $           |
|        |       | A \rightarrow \cdot B a, $           |
|        |       | A \rightarrow \cdot a A, $           |
|        |       | B \rightarrow \cdot b B, a           |
|        |       | B \rightarrow \cdot f, a             |
| (3, b) |     4 | closure(B \rightarrow b \cdot B, a)  |
|        |       | B \rightarrow b \cdot B, a           |
|        |       | B \rightarrow \cdot b B, a           |
|        |       | B \rightarrow \cdot f, a             |
| (3, f) |     5 | closure(B \rightarrow f \cdot, a)    |
|        |       | B \rightarrow f \cdot, a             |
| (4, B) |     8 | closure(B \rightarrow b B \cdot, a)  |
|        |       | B \rightarrow b B \cdot, a           |
| (4, b) |     4 | closure(B \rightarrow b \cdot B, a)  |
|        |       | B \rightarrow b \cdot B, a           |
|        |       | B \rightarrow \cdot b B, a           |
|        |       | B \rightarrow \cdot f, a             |
| (4, f) |     5 | closure(B \rightarrow f \cdot, a)    |
|        |       | B \rightarrow f \cdot, a             |
** LR Parse Table
| state | a  | b  | f  | $   | A | B |
|     0 | s3 | s4 | s5 |     | 1 | 2 |
|     1 |    |    |    | acc |   |   |
|     2 | s6 |    |    |     |   |   |
|     3 | s3 | s4 | s5 |     | 7 | 2 |
|     4 |    | s4 | s5 |     |   | 8 |
|     5 | r5 |    |    |     |   |   |
|     6 |    |    |    | r2  |   |   |
|     7 |    |    |    | r3  |   |   |
|     8 | r4 |    |    |     |   |   |

** Parse of "abfa"
| stack   | symbols | input   | action   |
| 0       |         | abfa$   | shift 3  |
| 0 3     | a       | bfa$    | shift 4  |
| 0 3 4   | ab      | fa$     | shift 5  |
| 0 3 4 5 | abf     | a$      | reduce 5 |
| 0 3 4 8 | abB     | a$      | reduce 4 |
| 0 3 2   | aB      | a$      | shift 6  |
| 0 3 2 6 | aBa     | $       | reduce 2 |
| 0 3 7   | aBa     | $       | reduce 3 |
| 0 1     | aA      | $       | accept   |