Talk:Packrat parser

The phrase "In computing..." has been removed, as it implies a greater ubiquity of the term "packrat parser" than has yet been evidenced in the literture. This is a fairly recent advancement.

-- QTJ 20:16, 13 October 2006 (UTC)

Figure in section "Syntax"

The "example" subsection ends with a figure in the middle of the text. This figure should be put properly in a figure box and referenced (or not) in the text Cellomario (talk) 12:42, 7 July 2023 (UTC)

Overall a very well written page, especially the part about memoization techniques. The only suggestion that I can make is that the average reader would benefit from a more divulgative approach, both in the text and in the references Cellomario (talk) 13:01, 7 July 2023 (UTC)

Review

The article is clear and well written. The main aspects of the topic are understandable by someone with no particular expertise in the area. Fdrc.Mtll (talk) 14:31, 7 July 2023 (UTC)

Review

The description of the Packrat parser is very detailed and provides a useful example to understand the underlying algorithm.

mscuttari (talk) 14:55, 7 July 2023 (UTC)

Example in "Syntax" section

The grammar given in the "Example" subsection doesn't seem to work:

${\begin{cases}S\rightarrow A/B/D\\A\rightarrow {\texttt {'a'}}\ S\ {\texttt {'a'}}\\B\rightarrow {\texttt {'b'}}\ S\ {\texttt {'b'}}\\D\rightarrow ({\texttt {'0'}}-{\texttt {'9'}})?\end{cases}}$

Without a cut-off ${\displaystyle$ !.} it accepts every input string. Adding a wrapper rule like $W\rightarrow {S!.}$ doesn't work, because then inputs like ${\texttt {aaaa}}$ are rejected.

You can see this by roughly tracking the execution:

1. ${\texttt {aaaa}}$ input: the wrapper with ${\texttt {!.}}$ runs.
   1. ${\texttt {aaaa}}$ left: eventually $A$ runs: consumes initial ${\texttt {a}}$, runs $S$ on ${\texttt {aaa}}$,
      1. ${\texttt {aaa}}$ left: eventually $A$ runs: consumes initial ${\texttt {a}}$, runs $S$ on ${\texttt {aa}}$,
         1. ${\texttt {aa}}$ left: eventually succeeds, consumes all remaining input, returns.
      2. no input left: $A$ can't match the final ${\texttt {a}}$,
      3. ${\texttt {aaa}}$ left: $D$ runs instead, matches ${\texttt {''}}$, returns.
   2. ${\texttt {aaa}}$ left: $A$ consumes ${\texttt {a}}$, returns.
2. ${\texttt {aa}}$ left: some input remains, so wrapper rejects the palindrome.

So to me it looks like at least in this particular case $S$ consumes only ${\texttt {aa}}$ from the whole input string.

Can somebody correct the example? Alkiryk (talk) 13:20, 9 December 2025 (UTC)

You've made a mistake in your execution, when S is run on 'aaaa' it runs recursively on 'aa' which clearly succeeds, and it then consumes the first and last a. SweetOleDee (talk) 13:14, 18 July 2026 (UTC)