0
$\begingroup$

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 $$

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.