Earley's algorithm -- supplemental material for the curious Early discovered one of two known completely general context-free parsing algorithms. It's a little messy when you try to dot all the i's and cross the t's, but the basic idea is straightforward. The algorithm works to parse ANY CFG, even highly ambiguous ones. It's a dynamic programming algorithm, kind of analogous to the on-line simulation of an NFA that we considered in the previous unit (the one where we maintain a set of states that the machine might be in at present). Earley's algorithm maintains a sequence of lists ("states"), equal in number to the number of tokens in the source. Each list indicates the places within right-hand sides of productions where we might be at present. Each item in list j consists of a production with a "dot" somewhere in the RHS (indicating where we might be), together with a back pointer to the state i that we were in when we first considered the possibility that we might be in this production. To get from one state to the next we (1) move the dot across any appropriate terminal. This creates the "kernel" of the state. (2) if there are any items in which the dot is now in front of a non-terminal, "predict" any productions that have that non-terminal on the LHS. (3) if there are any items A --> alpha . [n] in which the dot is now at the end of the RHS, "complete" items from state n for which the dot was in front of an A. (4) if prediction or completion has added any items in which the dot is in front of a non-terminal or at the end of the RHS, predict or complete again. Continue until nothing more can be added. Example: Consider our ambiguous grammar for expressions: E --> number E --> ( E ) E --> E + E E --> E - E E --> E * E E --> E / E For simplcity, let's make that E --> number E --> ( E ) E --> E op E And suppose we want to parse the string 1 + 2 * 3. State (list) 0 begins with 0: E --> . number [0] E --> . ( E ) [0] E --> . E op E [0] When we see the 1 we move to a state whose kernel is 1: E --> number . [0] Since the dot in this state is at the end of the RHS, we must "complete" the state by considering that we may have just finished seeing an E that we started considering in state 0. This gives us 1: E --> number . [0] E --> E . op E [0] Now when we see the + we move to 2: E --> E op . E [0] But now our dot is in front of a non-terminal (E), so we have to "predict" additional items for the state: 2: E --> E op . E [0] E --> . number [2] E --> . ( E ) [2] E --> . E op E [2] Note the 2's in the back-pointers of the predicted items. Now we see the 2 in the input, taking us to 3: E --> number . [2] Once again we must "complete", yielding 3: E --> number . [2] E --> E op E . [0] E --> E . op E [2] Again, note the backpointers. The 2 in the basis item tells us to work from items in state 2. There are two items in that state with a dot in front of an E. These give rise to two new items in state 3. One of them has a dot at the end of the production again, prompting another round of completion: 3: E --> number . [2] E --> E op E . [0] E --> E . op E [2] E --> E . op E [0] Now we have no new items with a dot in front of a non-terminal (suggesting the need for prediction) or at the end of a RHS (suggesting the need for completion), so we move on to state 4. We see the * on the input, taking us to 4: E --> E op . E [2] E --> E op . E [0] Again we predict, yielding 4: E --> E op . E [2] E --> E op . E [0] E --> . number [4] E --> . ( E ) [4] E --> . E op E [4] This introduces no new needs for prediction or completion. Finally we see the 3 on the input, taking us to 5: E --> number . [4] We complete (once) to get 5: E --> number . [4] E --> E op E . [2] E --> E op E . [0] E --> E . op E [4] We now have two new items with the dot at the end, so we must complete a second time: 5: E --> number . [4] E --> E op E . [2] E --> E op E . [0] E --> E . op E [4] E --> E . op E [2] E --> E . op E [0] Some of these items are added more than once. We only keep one copy, however. Notice the item E --> E + E . [0] This indicates that we may have just finished parsing an E predicted in state 0. (At the beginning of the parse). Given that we're now at the end of the input, we know our string is in the language. It can be shown (thought it's a little tricky) that Earley's algorithm runs in time O(n^3) and space O(n^2), where n is the length of the input string. This is too slow for compilers and other recognizers of long strings.