These algorithms were the first of their kind to employ deterministic top-down parsing with backtracking.

[2][3] Bryan Ford developed PEGs as an expansion of GTDPL and TS.

Unlike CFGs, PEGs are unambiguous and can match well with machine-oriented languages.

PEGs, similar to GTDPL and TS, can also express all LL(k) and LR(k).

This was done because PEGs have an unlimited lookahead capability resulting in a parser with exponential time performance in the worst case.

[2][3] Packrat keeps track of the intermediate results for all mutually recursive parsing functions.

In some instances of packrat implementation, if there is insufficient memory, certain parsing functions may need to be called multiple times at the same input position, causing the parser to take longer than linear time.

[4] The packrat parser takes in input the same syntax as PEGs: a simple PEG is composed of terminal and nonterminal symbols, possibly interleaved with operators that compose one or several derivation rules.

do not match Consumed: The atomic expression that has generated a success so if multiple succeed the first one is always returned

Left recursion happens when a grammar production refers to itself as its left-most element, either directly or indirectly.

Nonetheless, if there is an indirect left recursion involved, the process of rewriting can be quite complex and challenging.

If the time complexity requirements are loosened from linear to superlinear, it is possible to modify the memoization table of a Packrat parser to permit left recursion, without altering the input grammar.

As a matter of fact, the use of iterative combinators introduces a secret recursion that does not record intermediate results in the outcome matrix.

Memoization is an optimization technique in computing that aims to speed up programs by storing the results of expensive function calls.

This technique essentially works by caching the results so that when the same inputs occur again, the cached result is simply returned, thus avoiding the time-consuming process of re-computing.

Essentially, memoization table entries do not affect or rely on the parser's specific state at any given time.

[8] Packrat parsing stores results in a matrix or similar data structure that allows for quick look-ups and insertions.

The Packrat parser can be improved to update only the necessary cells in the matrix through a depth-first visit of each subexpression tree.

[1] Another operator called cut has been introduced to Packrat to reduce its average space complexity even further.

This operator utilizes the formal structures of many programming languages to eliminate impossible derivations.

For instance, control statements parsing in a standard programming language is mutually exclusive from the first recognized token, e.g.,

When a Packrat parser uses cut operators, it effectively clears its backtracking stack.

This is because a cut operator reduces the number of possible alternatives in an ordered choice.

By adding cut operators in the right places in a grammar's definition, the resulting Packrat parser only needs a nearly constant amount of space for memoization.

[5]Given the following context, a free grammar that recognizes simple arithmetic expressions composed of single digits interleaved by sum, multiplication, and parenthesis.

the line terminator we can apply the packrat algorithm Backtrack to the first grammar rule with unexplored alternative

No update because no nonterminal was fully recognized Backtrack to the first grammar rule with unexplored alternative

And we don't expand it has we have an hit in the memoization table P(4) ≠ 0 so shift the input by P(4).

Hit on P(4) Update M(4) = 1 as M was recognized Backtrack to the first grammar rule with unexplored alternative

And we don't expand it has we have an hit in the memoization table P(6) ≠ 0 so shift the input by P(6).