Earley Parser - Pseudocode

Pseudocode

Adapted from by Daniel Jurafsky and James H. Martin

function EARLEY-PARSE(words, grammar) ENQUEUE((γ → •S, 0), chart) for i ← from 0 to LENGTH(words) do for each state in chart do if INCOMPLETE?(state) then if NEXT-CAT(state) is a nonterminal then PREDICTOR(state, i, grammar) // non-terminal else do SCANNER(state, i) // terminal else do COMPLETER(state, i) end end return chart procedure PREDICTOR((A → α•B, i), j, grammar) for each (B → γ) in GRAMMAR-RULES-FOR(B, grammar) do ADD-TO-SET((B → •γ, j), chart) end procedure SCANNER((A → α•B, i), j) if B ⊂ PARTS-OF-SPEECH(word) then ADD-TO-SET((B → word, i), chart) end procedure COMPLETER((B → γ•, j), k) for each (A → α•Bβ, i) in chart do ADD-TO-SET((A → αB•β, i), chart) end