Earley Parser

final_state <- final_state()
root <- #

for parent in final_state.parents do:
    parse(root, root, parent)


parse(root, node, state)
    if state = initial_state() then:
        return root

    if state.is_finished() then:
        node.add_child(state.lhs)

    # Todo estado que é part-of-speech está finalizado portanto um filho foi
    # certamente adicionado no passo anterior.

    if is_part_of_speech(state.lhs) then:
        child <- node.get_child(0)
        child.add_child(state.rhs.first)

    if dot_is_first(state) then:
        node <- node.parent
    else if not is_part_of_speech(state.lhs) and state.is_finished() then:
        node <- node.get_child(0)

    for parent in state.parents do:
        if parent.lhs = state.prior_to_dot() or
           parent.rhs and parent.lhs =  some_evaluated_state() then:
            parse(root, node, parent)