Editing Packrat parser (section)

== The algorithm ==
Sketch of an implementation of a Packrat algorithm in a Lua-like pseudocode.<ref name=":2" />
<syntaxhighlight lang="lua" line highlight="1,3,11" style="font-size:95%">
INPUT(n) -- return the character at position n

RULE(R : Rule, P : Position )
    entry = GET_MEMO(R,P) -- return the number of elements previously matched in rule R at position P
    if entry == nil then
        return EVAL(R, P);
    end
    return entry;


EVAL(R : Rule, P : Position )
    start = P;   
    for choice in R.choices -- Return a list of choice
        acc=0;
        for symbol in choice then -- Return each element of a rule, terminal and nonterminal
            if symbol.is_terminal then
                if INPUT(start+acc) == symbol.terminal then
                    acc = acc + 1; --Found correct terminal skip pass it
                else
                    break;                
                end
            else 
                res = RULE(symbol.nonterminal , start+acc ); -- try to recognize a nonterminal in position start+acc
                SET_MEMO(symbol.nonterminal , start+acc, res ); -- we memoize also the failure with special value fail
                if res == fail then  
                    break; 
                end
                acc = acc + res;
            end
            if symbol == choice.last -- check if we have matched the last symbol in a choice if so return
                return acc;
        end
    end
    return fail; --if no choice match return fail
</syntaxhighlight>