InitHEADmain

1 files changed, 285 insertions, 0 deletions

diff --git a/Homework/cs5300/homework-seven/compilers_assn_7.org b/Homework/cs5300/homework-seven/compilers_assn_7.org
new file mode 100644
index 0000000..a6e5f35
--- /dev/null
+++ b/Homework/cs5300/homework-seven/compilers_assn_7.org
@@ -0,0 +1,285 @@
+#+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   |