# Computing Earley Parsing Steps

I am trying to understand Earley parsing algorithm using an example. The grammar I use produces all the palindromes over $$\Sigma=\{a,b,c\}$$:

\begin{align*} Z & \to S\\ S & \to a\,|\,b\,|\,c\,|\,aa\,|\,bb\,|\,cc\,|\,aSa\,|\,bSb\,|\,cSc \end{align*}

For instance, the string abcba is derived as: $$Z\to S\to aSa\to abSba\to abcba$$

When I follow the algorithm steps, these are the Earley states I get:

$$\begin{array}{|c|} \hline S_{0}\\ \hline \begin{array}{ccc|c} (1) & Z\to\bullet S & ,0 & \text{start rule}\\ (2) & S\to\bullet a & ,0 & \text{predict from (1)}\\ (3) & S\to\bullet b & ,0 & \text{predict from (1)}\\ (4) & S\to\bullet c & ,0 & \text{predict from (1)}\\ (5) & S\to\bullet aa & ,0 & \text{predict from (1)}\\ (6) & S\to\bullet bb & ,0 & \text{predict from (1)}\\ (7) & S\to\bullet cc & ,0 & \text{predict from (1)}\\ (8) & S\to\bullet aSa & ,0 & \text{predict from (1)}\\ (9) & S\to\bullet bSb & ,0 & \text{predict from (1)}\\ (10) & S\to\bullet cSc & ,0 & \text{predict from (1)} \end{array} \\\hline \end{array}$$

$$\begin{array}{|c|} \hline S_{1}\\ \hline \begin{array}{ccc|c} (1) & S\to a\bullet & ,0 & \text{scan from } S_{0}(1)\\ (2) & S\to a\bullet a & ,0 & \text{scan from } S_{0}(4)\\ (3) & S\to a\bullet Sa & ,0 & \text{scan from }S_{0}(7)\\ (4) & S\to\bullet a & ,1 & \text{predict from (3)}\\ (5) & S\to\bullet b & ,1 & \text{predict from (3)}\\ (6) & S\to\bullet c & ,1 & \text{predict from (3)}\\ (7) & S\to\bullet aa & ,1 & \text{predict from (3)}\\ (8) & S\to\bullet bb & ,1 & \text{predict from (3)}\\ (9) & S\to\bullet cc & ,1 & \text{predict from (3)}\\ (10) & S\to\bullet aSa & ,1 & \text{predict from (3)}\\ (11) & S\to\bullet bSb & ,1 & \text{predict from (3)}\\ (12) & S\to\bullet cSc & ,1 & \text{predict from (3)}\\ (13) & Z\to S\bullet & ,0 & \text{complete from (1) and }S_{0}(1) \end{array} \\\hline \end{array}$$

$$\begin{array}{|c|} \hline S_{2}\\ \hline \begin{array}{ccc|c} (1) & S\to b\bullet & ,1 & \text{scan from } S_{1}(5)\\ (2) & S\to b\bullet b & ,1 & \text{scan from } S_{1}(8)\\ (3) & S\to b\bullet Sb & ,1 & \text{scan from } S_{1}(11)\\ (4) & S\to\bullet a & ,2 & \text{predict from (3)}\\ (5) & S\to\bullet b & ,2 & \text{predict from (3)}\\ (6) & S\to\bullet c & ,2 & \text{predict from (3)}\\ (7) & S\to\bullet aa & ,2 & \text{predict from (3)}\\ (8) & S\to\bullet bb & ,2 & \text{predict from (3)}\\ (9) & S\to\bullet cc & ,2 & \text{predict from (3)}\\ (10) & S\to\bullet aSa & ,2 & \text{predict from (3)}\\ (11) & S\to\bullet bSb & ,2 & \text{predict from (3)}\\ (12) & S\to\bullet cSc & ,2 & \text{predict from (3)}\\ (13) & S\to aS\bullet a & ,0 & \text{complete from (1) and }S_{1}(3) \end{array} \\\hline \end{array}$$

$$\begin{array}{|c|} \hline S_{3}\\ \hline \begin{array}{ccc|c} (1) & \boldsymbol{S\to c\bullet} & ,2 & \text{scan from } S_{2}(6)\\ (2) & S\to c\bullet c & ,2 & \text{scan from } S_{2}(9)\\ (3) & S\to c\bullet Sc & ,2 & \text{scan from } S_{2}(12)\\ (4) & S\to\bullet a & ,3 & \text{predict from (3)}\\ (5) & S\to\bullet b & ,3 & \text{predict from (3)}\\ (6) & S\to\bullet c & ,3 & \text{predict from (3)}\\ (7) & S\to\bullet aa & ,3 & \text{predict from (3)}\\ (8) & S\to\bullet bb & ,3 & \text{predict from (3)}\\ (9) & S\to\bullet cc & ,3 & \text{predict from (3)}\\ (10) & S\to\bullet aSa & ,3 & \text{predict from (3)}\\ (11) & S\to\bullet bSb & ,3 & \text{predict from (3)}\\ (12) & S\to\bullet cSc & ,3 & \text{predict from (3)}\\ (13) & S\to bS\bullet b & ,1 & \text{complete from (1) and } S_{2}(3) \end{array} \\\hline \end{array}$$

$$\begin{array}{|c|} \hline S_{4}\\ \hline \begin{array}{ccc|c} (1) & S\to b\bullet & ,3 & \text{scan from } S_{3}(5)\\ (2) & S\to b\bullet b & ,3 & \text{scan from }S_{3}(8)\\ (3) & S\to b\bullet Sb & ,3 & \text{scan from } S_{3}(11)\\ (4) & \boldsymbol{S\to bSb\bullet} & ,1 & \text{scan from } S_{3}(13)\\ (5) & S\to\bullet a & ,4 & \text{predict from (3)}\\ (6) & S\to\bullet b & ,4 & \text{predict from (3)}\\ (7) & S\to\bullet c & ,4 & \text{predict from (3)}\\ (8) & S\to\bullet aa & ,4 & \text{predict from (3)}\\ (9) & S\to\bullet bb & ,4 & \text{predict from (3)}\\ (10) & S\to\bullet cc & ,4 & \text{predict from (3)}\\ (11) & S\to\bullet aSa & ,4 & \text{predict from (3)}\\ (12) & S\to\bullet bSb & ,4 & \text{predict from (3)}\\ (13) & S\to\bullet cSc & ,4 & \text{predict from (3)}\\ (14) & S\to cS\bullet c & ,2 & \text{complete from (1) and } S_{3}(3)\\ (15) & S\to a S\bullet a & ,0 & \text{complete from (4) and } S_{1}(3) \end{array} \\\hline \end{array}$$

$$\begin{array}{|c|} \hline S_{5}\\ \hline \begin{array}{ccc|c} (1) & S\to a\bullet & ,4 & \text{scan from } S_{4}(4)\\ (2) & S\to a\bullet a & ,4 & \text{scan from } S_{4}(7)\\ (3) & S\to a\bullet Sa & ,4 & \text{scan from } S_{4}(10)\\ (4) & S\to aSa\bullet & ,0 & \text{scan from } S_{4}(15)\\ (5) & S\to\bullet a & ,5 & \text{predict from (3)}\\ (6) & S\to\bullet b & ,5 & \text{predict from (3)}\\ (7) & S\to\bullet c & ,5 & \text{predict from (3)}\\ (8) & S\to\bullet aa & ,5 & \text{predict from (3)}\\ (9) & S\to\bullet bb & ,5 & \text{predict from (3)}\\ (10) & S\to\bullet cc & ,5 & \text{predict from (3)}\\ (11) & S\to\bullet aSa & ,5 & \text{predict from (3)}\\ (12) & S\to\bullet bSb & ,5 & \text{predict from (3)}\\ (13) & S\to\bullet cSc & ,5 & \text{predict from (3)}\\ (14) & S\to bS\bullet b & ,3 & \text{complete from (1) and } S_{4}(3)\\ (15) & S\to aS\bullet a & ,0 & \text{complete from (1) and } S_{4}(15)\\ (16) & Z\to S\bullet & ,0 & \text{complete from (4) and } S_{0}(1) \end{array} \\\hline \end{array}$$

Since $$S_5$$ contains $$Z\to S\bullet$$ we conclude that abcba was successfully derived.