Earley parser: Encyclopedia II - Earley parser - Example

Earley parser - Example

The algorithm is hard to see from the abstract description above. It becomes much clearer how it operates once you see it in action. The output is a little verbose, but you should be able to follow it.

Let's say you have the following simple arithmetic grammar:

 P → S      # the start rule
 S → S + M
    | M
 M → M * T
    | T
 T → number

And you have the input:

 2 + 3 * 4

Here are the generated state sets:

 (state no.) Production          (Origin) # Comment
 ---------------------------------
 == S(0): • 2 + 3 * 4 ==
 (1)  P → • S         (0)    # start rule
 (2)  S → • S + M     (0)    # predict from (1)
 (3)  S → • M         (0)    # predict from (1)
 (4)  M → • M * T     (0)    # predict from (3)
 (5)  M → • T         (0)    # predict from (3)
 (6)  T → • number    (0)    # predict from (5)
 
 == S(1): 2 • + 3 * 4 ==
 (1)  T → number •    (0)    # scan from S(0)(6)
 (2)  M → T •         (0)    # complete from S(0)(5)
 (3)  M → M • * T     (0)    # complete from S(0)(4)
 (4)  S → M •         (0)    # complete from S(0)(3)
 (5)  S → S • + M     (0)    # complete from S(0)(2)
 (6)  P → S •         (0)    # complete from S(0)(1)
 
 == S(2): 2 + • 3 * 4 ==
 (1)  S → S + • M     (0)    # scan from S(1)(5)
 (2)  M → • M * T     (2)    # predict from (1)
 (3)  M → • T         (2)    # predict from (1)
 (4)  T → • number    (2)    # predict from (3)
 
 == S(3): 2 + 3 • * 4 ==
 (1)  T → number •    (2)    # scan from S(2)(4)
 (2)  M → T •         (2)    # complete from S(2)(3)
 (3)  M → M • * T     (2)    # complete from S(2)(2)
 (4)  S → S + M •     (0)    # complete from S(2)(1)
 (5)  S → S • + M     (0)    # complete from S(0)(2)
 (6)  P → S •         (0)    # complete from S(0)(1)
 
 == S(4): 2 + 3 * • 4 ==
 (1)  M → M * • T     (2)    # scan from S(3)(3)
 (2)  T → • number    (4)    # predict from (1)
 
 == S(5): 2 + 3 * 4 • ==
 (1)  T → number •    (4)    # scan from S(4)(2)
 (2)  M → M * T •     (2)    # complete from S(4)(1)
 (3)  M → M • * T     (2)    # complete from S(2)(2)
 (4)  S → S + M •     (0)    # complete from S(2)(1)
 (5)  S → S • + M     (0)    # complete from S(0)(2)
 (6)  P → S •         (0)    # complete from S(0)(1)

And now the input is parsed, since we have the state (P → S •, 0) (note that we also had it in S(3) and S(1); those were complete sentences).

Adapted from the Wikipedia article "Example", under the G.N U Free Docmentation License. Please also see http://en.wikipedia.org/wiki