Skip to content

Instantly share code, notes, and snippets.

@codenamejason
Created February 20, 2018 13:45
Show Gist options
  • Save codenamejason/a53f9e47bd44a5ed35fe325a39ef2c29 to your computer and use it in GitHub Desktop.
Save codenamejason/a53f9e47bd44a5ed35fe325a39ef2c29 to your computer and use it in GitHub Desktop.
DECLARE ARRAY S;
function INIT(words)
S ← CREATE-ARRAY(LENGTH(words))
for k ← from 0 to LENGTH(words) do
S[k] ← EMPTY-ORDERED-SET
function EARLEY-PARSE(words, grammar)
INIT(words)
ADD-TO-SET((γ → •S, 0), S[0])
for k ← from 0 to LENGTH(words) do
for each state in S[k] do // S[k] can expand during this loop
if not FINISHED(state) then
if NEXT-ELEMENT-OF(state) is a nonterminal then
PREDICTOR(state, k, grammar) // non-terminal
else do
SCANNER(state, k, words) // terminal
else do
COMPLETER(state, k)
end
end
return chart
procedure PREDICTOR((A → α•Bβ, j), k, grammar)
for each (B → γ) in GRAMMAR-RULES-FOR(B, grammar) do
ADD-TO-SET((B → •γ, k), S[k])
end
procedure SCANNER((A → α•aβ, j), k, words)
if a ⊂ PARTS-OF-SPEECH(words[k]) then
ADD-TO-SET((A → αa•β, j), S[k+1])
end
procedure COMPLETER((B → γ•, x), k)
for each (A → α•Bβ, j) in S[x] do
ADD-TO-SET((A → αB•β, j), S[k])
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment