summaryrefslogtreecommitdiff
path: root/Homework/cs5300/homework-seven
diff options
context:
space:
mode:
Diffstat (limited to 'Homework/cs5300/homework-seven')
-rw-r--r--Homework/cs5300/homework-seven/compilers_assn_7.org285
-rw-r--r--Homework/cs5300/homework-seven/compilers_assn_7.pdfbin0 -> 70731 bytes
-rw-r--r--Homework/cs5300/homework-seven/compilers_assn_7.tex381
3 files changed, 666 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 |
diff --git a/Homework/cs5300/homework-seven/compilers_assn_7.pdf b/Homework/cs5300/homework-seven/compilers_assn_7.pdf
new file mode 100644
index 0000000..9c80b5e
--- /dev/null
+++ b/Homework/cs5300/homework-seven/compilers_assn_7.pdf
Binary files differ
diff --git a/Homework/cs5300/homework-seven/compilers_assn_7.tex b/Homework/cs5300/homework-seven/compilers_assn_7.tex
new file mode 100644
index 0000000..fc4c607
--- /dev/null
+++ b/Homework/cs5300/homework-seven/compilers_assn_7.tex
@@ -0,0 +1,381 @@
+% Created 2023-02-27 Mon 22:14
+% Intended LaTeX compiler: lualatex
+\documentclass[11pt]{article}
+\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[utf8]{inputenc} \usepackage{amsmath} \usepackage{fontspec} \usepackage[a4paper,margin=1in,portrait]{geometry} \usepackage{fontspec} \setmonofont{DejaVu Sans Mono}
+\author{Lizzy Hunt}
+\date{\today}
+\title{Assignment Seven}
+\hypersetup{
+ pdfauthor={Lizzy Hunt},
+ pdftitle={Assignment Seven},
+ pdfkeywords={},
+ pdfsubject={},
+ pdfcreator={Emacs 28.2 (Org mode 9.6.1)},
+ pdflang={English}}
+\begin{document}
+
+\maketitle
+\setlength\parindent{0pt}
+
+\section{Question One}
+\label{sec:org41ddc16}
+\subsection{Removal of Left Recursion}
+\label{sec:org2e2ade2}
+\begin{verbatim}
+A -> BbA'
+A' -> aA' | ε
+B -> aB | b
+\end{verbatim}
+\subsection{Left Factoring}
+\label{sec:orge4a4f75}
+No need to left factor this grammar
+\subsection{Parse Table}
+\label{sec:org43628e4}
+\subsubsection{Calculation of first and follow}
+\label{sec:org8e7d2cc}
+\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}
+
+\subsubsection{Predictive Parse Table}
+\label{sec:orgc2ae298}
+\begin{center}
+\begin{tabular}{llll}
+Nonterminal & a & b & \$\\[0pt]
+A & A \(\rightarrow\) BbA' & A \(\rightarrow\) BbA' & \\[0pt]
+A' & A' \(\rightarrow\) aA' & & A' \(\rightarrow\) \(\epsilon\)\\[0pt]
+B & B \(\rightarrow\) aB & B \(\rightarrow\) b & \\[0pt]
+\end{tabular}
+\end{center}
+
+\subsection{Parse of "abba"}
+\label{sec:orge26f0a1}
+\begin{center}
+\begin{tabular}{llll}
+Stack & Input & Action & Matched\\[0pt]
+A\$ & abba\$ & A \(\rightarrow\) BbA' & \\[0pt]
+BbA'\$ & abba\$ & B \(\rightarrow\) aB & \\[0pt]
+aBbA'\$ & bba\$ & Match a & a\\[0pt]
+BbA'\$ & bba\$ & B \(\rightarrow\) b & a\\[0pt]
+bbA'\$ & bba\$ & Match b & ab\\[0pt]
+bA'\$ & ba\$ & Match b & abb\\[0pt]
+A'\$ & a\$ & A \(\rightarrow\) aA' & abb\\[0pt]
+aA'\$ & a\$ & Match a & abba\\[0pt]
+A'\$ & \$ & A' \(\rightarrow\) ε & abba\\[0pt]
+ε\$ & \$ & Match ε & abba\\[0pt]
+\$ & \$ & Match \$ & \\[0pt]
+ & & Accept & \\[0pt]
+\end{tabular}
+\end{center}
+
+\section{Question Two}
+\label{sec:orgc3fb7f0}
+\begin{center}
+\begin{tabular}{lll}
+Stack & Input & Action\\[0pt]
+\$ & (id)*id\$ & shift\\[0pt]
+\$( & id)*id\$ & shift\\[0pt]
+\$(id & )*id\$ & reduce F \(\rightarrow\) id\\[0pt]
+\$(F & )*id\$ & reduce F \(\rightarrow\) E\\[0pt]
+\$(E) & *id\$ & shift\\[0pt]
+\$F & *id\$ & reduce F \(\rightarrow\) (E)\\[0pt]
+\$T & *id\$ & reduce T \(\rightarrow\) F\\[0pt]
+\$T* & id\$ & shift\\[0pt]
+\$T*id & \$ & shift\\[0pt]
+\$T*F & \$ & reduce F \(\rightarrow\) id\\[0pt]
+\$T & \$ & reduce T \(\rightarrow\) T * F\\[0pt]
+\$E & \$ & reduce E \(\rightarrow\) T\\[0pt]
+\$E & \$ & accept\\[0pt]
+\end{tabular}
+\end{center}
+
+\section{Question Three}
+\label{sec:org180e5b7}
+\begin{center}
+\begin{tabular}{lll}
+Stack & Input & Action\\[0pt]
+\$ & ()(())\$ & Shift\\[0pt]
+\$( & )(())\$ & Shift\\[0pt]
+\$() & (())\$ & Shift\\[0pt]
+\$Pair & (())\$ & Reduce R5\\[0pt]
+\$List & (())\$ & Reduce R3\\[0pt]
+\$List( & ())\$ & Shift\\[0pt]
+\$List(( & ))\$ & Shift\\[0pt]
+\$List(() & )\$ & Shift\\[0pt]
+\$List(Pair & )\$ & Reduce R5\\[0pt]
+\$List(Pair) & \$ & Shift\\[0pt]
+\$List Pair & \$ & Reduce R4\\[0pt]
+\$Goal & \$ & Reduce R1\\[0pt]
+\$Goal & \$ & Accept\\[0pt]
+\end{tabular}
+\end{center}
+
+\section{Question Four}
+\label{sec:orgd14094c}
+\subsection{a}
+\label{sec:org6873356}
+\{[N \(\rightarrow\) \(\cdot\) N + N], [N \(\rightarrow\) \(\cdot\) NN], [N \(\rightarrow\) \(\cdot\) (N)], [N \(\rightarrow\) \(\cdot\) N *], [N \(\rightarrow\) \(\cdot\) a]\}
+
+\subsection{b}
+\label{sec:orgdf45b11}
+\{[N \(\rightarrow\) (\(\cdot\) N)], [N \(\rightarrow\) \(\cdot\) NN], [N \(\rightarrow\) \(\cdot\) (N)], [N \(\rightarrow\) \(\cdot\) N *], [N \(\rightarrow\) \(\cdot\) a]\}
+
+\subsection{c}
+\label{sec:orga001b72}
+\{[N \(\rightarrow\) (N \(\cdot\))]\}
+\section{Question Five}
+\label{sec:org4370427}
+\subsection{a}
+\label{sec:orgb30ece5}
+\{[A \(\rightarrow\) \(\cdot\) C B], [C \(\rightarrow\) \(\cdot\) E D], [E \(\rightarrow\) \(\cdot\) x A y], [E \(\rightarrow\) \(\cdot\) x]\}
+
+\subsection{b}
+\label{sec:orgd13c8f9}
+\{[B \(\rightarrow\) a \(\cdot\) C B], [C \(\rightarrow\) \(\cdot\) E D], [E \(\rightarrow\) \(\cdot\) x A y], [E \(\rightarrow\) \(\cdot\) x]\}
+
+\subsection{c}
+\label{sec:org2b3dacb}
+\{[B \(\rightarrow\) a C \(\cdot\) B], [B \(\rightarrow\) \(\cdot\) a C B]\}
+
+\subsection{d}
+\label{sec:org5acc456}
+\{[C \(\rightarrow\) E D \(\cdot\)]\}
+
+\subsection{e}
+\label{sec:org467fb21}
+\{[D \(\rightarrow\) b \(\cdot\) E D], [E \(\rightarrow\) \(\cdot\) x A y], [E \(\rightarrow\) \(\cdot\) z]\}
+
+\subsection{f}
+\label{sec:orge62af27}
+\{\}
+
+\section{Question Six}
+\label{sec:orgce910f1}
+\begin{center}
+\begin{tabular}{lrl}
+GOTO & state & items\\[0pt]
+ & 0 & closure(A' \(\rightarrow\) \(\cdot\) A)\\[0pt]
+ & & A' \(\rightarrow\) \(\cdot\) A\\[0pt]
+ & & A \(\rightarrow\) \(\cdot\) a A\\[0pt]
+ & & A \(\rightarrow\) \(\cdot\) B\\[0pt]
+ & & B \(\rightarrow\) \(\cdot\) b\\[0pt]
+(0, A) & 1 & closure(A' \(\rightarrow\) A \(\cdot\))\\[0pt]
+ & & A' \(\rightarrow\) A \(\cdot\)\\[0pt]
+(0, B) & 2 & closure(A \(\rightarrow\) B \(\cdot\))\\[0pt]
+ & & A \(\rightarrow\) B \(\cdot\)\\[0pt]
+(0, a) & 3 & closure(A \(\rightarrow\) a \(\cdot\) A b B)\\[0pt]
+ & & A \(\rightarrow\) a \(\cdot\) A\\[0pt]
+ & & A \(\rightarrow\) \(\cdot\) a A\\[0pt]
+ & & A \(\rightarrow\) \(\cdot\) B\\[0pt]
+ & & B \(\rightarrow\) \(\cdot\) b\\[0pt]
+(0, b) & 4 & closure(B \(\rightarrow\) b \(\cdot\) )\\[0pt]
+ & & B \(\rightarrow\) b \(\cdot\)\\[0pt]
+(3, A) & 5 & closure(A \(\rightarrow\) a A \(\cdot\) b B)\\[0pt]
+ & & A \(\rightarrow\) a A \(\cdot\)\\[0pt]
+(3, B) & 2 & A \(\rightarrow\) B \(\cdot\)\\[0pt]
+(3, a) & 3 & A \(\rightarrow\) a \(\cdot\) A\\[0pt]
+ & & A \(\rightarrow\) \(\cdot\) a A\\[0pt]
+ & & A \(\rightarrow\) \(\cdot\) B\\[0pt]
+ & & B \(\rightarrow\) \(\cdot\) b\\[0pt]
+(3, b) & 4 & B \(\rightarrow\) b \(\cdot\)\\[0pt]
+(5, b) & 6 & closure(A \(\rightarrow\) a A b \(\cdot\) B)\\[0pt]
+ & & A \(\rightarrow\) a A b \(\cdot\) B\\[0pt]
+ & & B \(\rightarrow\) \(\cdot\) b\\[0pt]
+(6, B) & 7 & closure(A \(\rightarrow\) a A b B \(\cdot\))\\[0pt]
+ & & A \(\rightarrow\) a A b B \(\cdot\)\\[0pt]
+(6, b) & 4 & B \(\rightarrow\) b \(\cdot\)\\[0pt]
+\end{tabular}
+\end{center}
+
+\section{Question Seven}
+\label{sec:org5e0e964}
+\subsection{First, Follow}
+\label{sec:org631e4e0}
+\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}
+
+\subsection{Items}
+\label{sec:orga0edb23}
+\begin{center}
+\begin{tabular}{lrl}
+GOTO & state & items\\[0pt]
+ & 0 & closure(A' \(\rightarrow\) \(\cdot\) A)\\[0pt]
+ & & A' \(\rightarrow\) \(\cdot\) A\\[0pt]
+ & & A \(\rightarrow\) \(\cdot\) A b B\\[0pt]
+ & & A \(\rightarrow\) \(\cdot\) B a\\[0pt]
+ & & B \(\rightarrow\) \(\cdot\) a\\[0pt]
+(0, A) & 1 & closure(\{A \(\rightarrow\) A \(\cdot\) b B, A' \(\rightarrow\) A \(\cdot\)\})\\[0pt]
+ & & A \(\rightarrow\) A \(\cdot\) b B\\[0pt]
+ & & A' \(\rightarrow\) A \(\cdot\)\\[0pt]
+(0, B) & 2 & closure(A \(\rightarrow\) B \(\cdot\) a)\\[0pt]
+ & & A \(\rightarrow\) B \(\cdot\) a\\[0pt]
+(0, a) & 3 & closure(B \(\rightarrow\) a \(\cdot\))\\[0pt]
+ & & B \(\rightarrow\) a \(\cdot\)\\[0pt]
+(1, b) & 4 & closure(A \(\rightarrow\) A b \(\cdot\) B)\\[0pt]
+ & & A \(\rightarrow\) A b \(\cdot\) B\\[0pt]
+ & & B \(\rightarrow\) \(\cdot\) a\\[0pt]
+(2, a) & 5 & closure(A \(\rightarrow\) B a \(\cdot\))\\[0pt]
+ & & A \(\rightarrow\) B a \(\cdot\)\\[0pt]
+(4, B) & 6 & closure(A \(\rightarrow\) A b B \(\cdot\))\\[0pt]
+ & & A \(\rightarrow\) A b B \(\cdot\)\\[0pt]
+(4, a) & 3 & closure(B \(\rightarrow\) a \(\cdot\))\\[0pt]
+ & & B \(\rightarrow\) a \(\cdot\)\\[0pt]
+\end{tabular}
+\end{center}
+
+\subsection{SLR Parse Table}
+\label{sec:org65e916a}
+\begin{center}
+\begin{tabular}{rlllrr}
+state & a & b & \$ & A & B\\[0pt]
+0 & s3 & & & 1 & 2\\[0pt]
+1 & & s4 & acc & & \\[0pt]
+2 & s5 & & & & \\[0pt]
+3 & r4 & r4 & r4 & & \\[0pt]
+4 & s3 & & & & 6\\[0pt]
+5 & & r3 & r3 & & \\[0pt]
+6 & & r2 & r2 & & \\[0pt]
+\end{tabular}
+\end{center}
+
+\subsection{Parse of "aaba"}
+\label{sec:orgc668927}
+\begin{center}
+\begin{tabular}{llll}
+stack & symbols & input & action\\[0pt]
+0 & & aaba\$ & shift 3\\[0pt]
+0 3 & a & aba\$ & reduce 4\\[0pt]
+0 2 & B & aba\$ & shift 5\\[0pt]
+0 2 5 & Ba & ba\$ & reduce 3\\[0pt]
+0 1 & A & ba\$ & shift 4\\[0pt]
+0 1 4 & Ab & a\$ & shift 3\\[0pt]
+0 1 4 3 & Aba & \$ & reduce 4\\[0pt]
+0 1 4 6 & AbB & \$ & reduce 2\\[0pt]
+0 1 & A & \$ & accept\\[0pt]
+\end{tabular}
+\end{center}
+
+\section{Question Eight}
+\label{sec:org9b3771e}
+\subsection{First, Follow}
+\label{sec:org8892bb8}
+\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}
+\subsection{Items}
+\label{sec:orgc50d475}
+\begin{center}
+\begin{tabular}{lrl}
+GOTO & state & items\\[0pt]
+ & 0 & closure(A' \(\rightarrow\) \(\cdot\) A, $\backslash$$)\\[0pt]
+ & & A' \(\rightarrow\) \(\cdot\) A, \$\\[0pt]
+ & & A \(\rightarrow\) \(\cdot\) B a, \$\\[0pt]
+ & & A \(\rightarrow\) \(\cdot\) a A, \$\\[0pt]
+ & & B \(\rightarrow\) \(\cdot\) b B, a\\[0pt]
+ & & B \(\rightarrow\) \(\cdot\) f, a\\[0pt]
+(0, A) & 1 & closure(A' \(\rightarrow\) A \(\cdot\), \$)\\[0pt]
+ & & A' \(\rightarrow\) A \(\cdot\), \$\\[0pt]
+(0, B) & 2 & closure(A \(\rightarrow\) B \(\cdot\) a, \$)\\[0pt]
+ & & A \(\rightarrow\) B \(\cdot\) a, \$\\[0pt]
+(0, a) & 3 & closure(A \(\rightarrow\) a \(\cdot\) A, \$)\\[0pt]
+ & & A \(\rightarrow\) a \(\cdot\) A, \$\\[0pt]
+ & & A \(\rightarrow\) \(\cdot\) B a, \$\\[0pt]
+ & & A \(\rightarrow\) \(\cdot\) a A, \$\\[0pt]
+ & & B \(\rightarrow\) \(\cdot\) b B, a\\[0pt]
+ & & B \(\rightarrow\) \(\cdot\) f, a\\[0pt]
+(0, b) & 4 & closure(B \(\rightarrow\) b \(\cdot\) B, a)\\[0pt]
+ & & B \(\rightarrow\) b \(\cdot\) B, a\\[0pt]
+ & & B \(\rightarrow\) \(\cdot\) b B, a\\[0pt]
+ & & B \(\rightarrow\) \(\cdot\) f, a\\[0pt]
+(0, f) & 5 & closure(B \(\rightarrow\) f \(\cdot\), a)\\[0pt]
+ & & B \(\rightarrow\) f \(\cdot\), a\\[0pt]
+(2, a) & 6 & closure(A \(\rightarrow\) B a \(\cdot\), \$)\\[0pt]
+ & & A \(\rightarrow\) B a \(\cdot\), \$\\[0pt]
+(3, A) & 7 & closure(A \(\rightarrow\) a A \(\cdot\), \$)\\[0pt]
+ & & A \(\rightarrow\) a A \(\cdot\), $\backslash$$\\[0pt]
+(3, B) & 2 & closure(A \(\rightarrow\) B \(\cdot\) a, \$)\\[0pt]
+ & & A \(\rightarrow\) B \(\cdot\) a, \$\\[0pt]
+(3, a) & 3 & closure(A \(\rightarrow\) a \(\cdot\) A, \$)\\[0pt]
+ & & A \(\rightarrow\) a \(\cdot\) A, \$\\[0pt]
+ & & A \(\rightarrow\) \(\cdot\) B a, \$\\[0pt]
+ & & A \(\rightarrow\) \(\cdot\) a A, \$\\[0pt]
+ & & B \(\rightarrow\) \(\cdot\) b B, a\\[0pt]
+ & & B \(\rightarrow\) \(\cdot\) f, a\\[0pt]
+(3, b) & 4 & closure(B \(\rightarrow\) b \(\cdot\) B, a)\\[0pt]
+ & & B \(\rightarrow\) b \(\cdot\) B, a\\[0pt]
+ & & B \(\rightarrow\) \(\cdot\) b B, a\\[0pt]
+ & & B \(\rightarrow\) \(\cdot\) f, a\\[0pt]
+(3, f) & 5 & closure(B \(\rightarrow\) f \(\cdot\), a)\\[0pt]
+ & & B \(\rightarrow\) f \(\cdot\), a\\[0pt]
+(4, B) & 8 & closure(B \(\rightarrow\) b B \(\cdot\), a)\\[0pt]
+ & & B \(\rightarrow\) b B \(\cdot\), a\\[0pt]
+(4, b) & 4 & closure(B \(\rightarrow\) b \(\cdot\) B, a)\\[0pt]
+ & & B \(\rightarrow\) b \(\cdot\) B, a\\[0pt]
+ & & B \(\rightarrow\) \(\cdot\) b B, a\\[0pt]
+ & & B \(\rightarrow\) \(\cdot\) f, a\\[0pt]
+(4, f) & 5 & closure(B \(\rightarrow\) f \(\cdot\), a)\\[0pt]
+ & & B \(\rightarrow\) f \(\cdot\), a\\[0pt]
+\end{tabular}
+\end{center}
+\subsection{LR Parse Table}
+\label{sec:org69f6dbf}
+\begin{center}
+\begin{tabular}{rllllrr}
+state & a & b & f & \$ & A & B\\[0pt]
+0 & s3 & s4 & s5 & & 1 & 2\\[0pt]
+1 & & & & acc & & \\[0pt]
+2 & s6 & & & & & \\[0pt]
+3 & s3 & s4 & s5 & & 7 & 2\\[0pt]
+4 & & s4 & s5 & & & 8\\[0pt]
+5 & r5 & & & & & \\[0pt]
+6 & & & & r2 & & \\[0pt]
+7 & & & & r3 & & \\[0pt]
+8 & r4 & & & & & \\[0pt]
+\end{tabular}
+\end{center}
+
+\subsection{Parse of "abfa"}
+\label{sec:org1d0a90c}
+\begin{center}
+\begin{tabular}{llll}
+stack & symbols & input & action\\[0pt]
+0 & & abfa\$ & shift 3\\[0pt]
+0 3 & a & bfa\$ & shift 4\\[0pt]
+0 3 4 & ab & fa\$ & shift 5\\[0pt]
+0 3 4 5 & abf & a\$ & reduce 5\\[0pt]
+0 3 4 8 & abB & a\$ & reduce 4\\[0pt]
+0 3 2 & aB & a\$ & shift 6\\[0pt]
+0 3 2 6 & aBa & \$ & reduce 2\\[0pt]
+0 3 7 & aBa & \$ & reduce 3\\[0pt]
+0 1 & aA & \$ & accept\\[0pt]
+\end{tabular}
+\end{center}
+\end{document} \ No newline at end of file
generated by cgit v1.3 (git 2.53.0) at 2026-07-18 13:27:45 +0000