packrat parser

{{See also|Parsing expression grammar#Syntax}}

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.

• Nonterminal symbols are indicated with capital letters (e.g., $\backslash \{S,\; E,\; F,\; D\backslash \}$)
• Terminal symbols are indicated with lowercase (e.g., $\backslash \{a,b,z,e,g\; \backslash \}$)
• Expressions are indicated with lower-case Greek letter (e.g., $\backslash \{\backslash alpha,\backslash beta,\backslash gamma,\backslash omega,\backslash tau\backslash \}$)
• Expressions can be a mix of terminal symbols, nonterminal symbols and operators

A derivation rule is composed by a nonterminal symbol and an expression $S\; \backslash rightarrow\; \backslash alpha$.

A special expression $\backslash alpha\_s$ is the starting point of the grammar. In case no $\backslash alpha\_s$ is specified, the first expression of the first rule is used.

An input string is considered accepted by the parser if the $\backslash alpha\_s$ is recognized. As a side-effect, a string $x$ can be recognized by the parser even if it was not fully consumed.

An extreme case of this rule is that the grammar $S\; \backslash rightarrow\; x*$ matches any string.

This can be avoided by rewriting the grammar as $S\; \backslash rightarrow\; x*!.$

$\backslash 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}

This grammar recognizes a palindrome over the alphabet $\backslash \{\; a,b\; \backslash \}$, with an optional digit in the middle.

Example strings accepted by the grammar include: $\backslash texttt\{\text{'}aa\text{'}\}$ and $\backslash texttt\{\text{'}aba3aba\text{'}\}$.

Left recursion happens when a grammar production refers to itself as its left-most element, either directly or indirectly. Since Packrat is a recursive descent parser, it cannot handle left recursion directly.{{Cite book |last1=Warth |first1=Alessandro |last2=Douglass |first2=James R. |last3=Millstein |first3=Todd |title=Proceedings of the 2008 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation |chapter=Packrat parsers can support left recursion |date=2008-01-07 |chapter-url=https://doi.org/10.1145/1328408.1328424 |series=PEPM '08 |location=New York, NY, USA |publisher=Association for Computing Machinery |pages=103–110 |doi=10.1145/1328408.1328424 |isbn=978-1-59593-977-7|s2cid=2168153 }} During the early stages of development, it was found that a production that is left-recursive can be transformed into a right-recursive production.{{Cite book |title=Compilers: principles, techniques, & tools |date=2007 |publisher=Pearson Addison-Wesley |isbn=978-0-321-48681-3 |editor-last=Aho |editor-first=Alfred V. |edition=2nd |location=Boston Munich |editor-last2=Lam |editor-first2=Monica S. |editor-last3=Sethi |editor-first3=Ravi |editor-last4=Ullman |editor-first4=Jeffrey D.}} This modification significantly simplifies the task of a Packrat parser. 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.

The iterative combinators $\backslash alpha\; +$ and $\backslash alpha\; *$ need special attention when used in a Packrat parser: these combinators introduce a secret recursion that does not record intermediate results in the outcome matrix, which can lead to the parser operating with a superlinear behaviour. This problem can be resolved by applying the following transformation:

With this transformation, the intermediate results can be properly memoized.

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.{{Cite journal |last=Norvig |first=Peter |date=1991-03-01 |title=Techniques for automatic memoization with applications to context-free parsing |url=https://dl.acm.org/doi/abs/10.5555/971738.971743 |journal=Computational Linguistics |volume=17 |issue=1 |pages=91–98 |doi= |issn=0891-2017}} When using packrat parsing and memoization, it's noteworthy that the parsing function for each nonterminal is solely based on the input string. It does not depend on any information gathered during the parsing process. Essentially, memoization table entries do not affect or rely on the parser's specific state at any given time.{{Cite book |last1=Dubroy |first1=Patrick |last2=Warth |first2=Alessandro |title=Proceedings of the 10th ACM SIGPLAN International Conference on Software Language Engineering |chapter=Incremental packrat parsing |date=2017-10-23 |chapter-url=https://doi.org/10.1145/3136014.3136022 |series=SLE 2017 |location=New York, NY, USA |publisher=Association for Computing Machinery |pages=14–25 |doi=10.1145/3136014.3136022 |isbn=978-1-4503-5525-4|s2cid=13047585 }}

Packrat parsing stores results in a matrix or similar data structure that allows for quick look-ups and insertions. When a production is encountered, the matrix is checked to see if it has already occurred. If it has, the result is retrieved from the matrix. If not, the production is evaluated, the result is inserted into the matrix, and then returned.{{Cite journal |last1=Science |first1=International Journal of Scientific Research in |last2=Ijsrset |first2=Engineering and Technology |title=A Survey of Packrat Parser |url=https://www.academia.edu/17779983 |journal=A Survey of Packrat Parser}} When evaluating the entire $m*n$ matrix in a tabular approach, it would require $\backslash Theta(mn)$ space. Here, $m$ represents the number of nonterminals, and $n$ represents the input string size.

In a naïve implementation, the entire table can be derived from the input string starting from the end of the string.

The Packrat parser can be improved to update only the necessary cells in the matrix through a depth-first visit of each subexpression tree. Consequently, using a matrix with dimensions of $m*n$ is often wasteful, as most entries would remain empty. These cells are linked to the input string, not to the nonterminals of the grammar. This means that increasing the input string size would always increase memory consumption, while the number of parsing rules changes only the worst space complexity.

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.,$\backslash \{\backslash mathtt\{if,\; do,\; while,\; switch\}\backslash \}$.{{Cite book |last1=Mizushima |first1=Kota |last2=Maeda |first2=Atusi |last3=Yamaguchi |first3=Yoshinori |title=Proceedings of the 9th ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering |chapter=Packrat parsers can handle practical grammars in mostly constant space |date=2010-05-06 |chapter-url=https://doi.org/10.1145/1806672.1806679 |series=PASTE '10 |location=New York, NY, USA |publisher=Association for Computing Machinery |pages=29–36 |doi=10.1145/1806672.1806679 |isbn=978-1-4503-0082-7|s2cid=14498865 }}

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.

Sketch of an implementation of a Packrat algorithm in a Lua-like pseudocode.

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

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

$\backslash begin\{cases\}$

S \rightarrow A \\

A \rightarrow M\ \texttt{'+'}\ A \ / \ M \\

M \rightarrow P\ \texttt{'*'}\ M \ / \ P \\

P \rightarrow \texttt{'('}\ A\ \texttt{')'}\ / \ D \\

D \rightarrow (\texttt{'0'}-\texttt{'9'})

\end{cases}

Denoted with ⊣ the line terminator we can apply the packrat algorithm

|

No update because no terminal was recognized

|-

|File:Second_step_in_Parsing_a_CFG_with_packrat.svg

|

|

Update:

D(1) = 1;

P(1) = 1;

|-

|File:Third_step_of_recognizing_CFG_with_packrat.svg

|

|

No update because no nonterminal was fully recognized

|-

|File:Fourth_step_in_recognizing_CFG_grammar_with_Packrat.svg

|

|

No update because no terminal was recognized

|-

|File:5th step of recognizing CFG with packrat.svg

|

|

Update:

D(4) = 1;

P(4) = 1;

|-

|File:Sixth step of recognizing CFG with packrat.svg

|

|

Hit on P(4)

Update M(4) = 1 as M was recognized

|-

|File:Seventh step of recognizing CFG with packrat.svg

|

|

No update because no terminal was recognized

|-

|File:Eighth step of recognizing CFG with packrat.svg

|

|

Update:

D(6) = 1;

P(6) = 1;

|-

|File:Ninth step of recognizing CFG with packrat.svg

|

|

Hit on P(6)

Update M(6) = 1 as M was recognized

|-

|File:Tenth step of recognizing CFG with packrat.svg

|

|

Hit on M(6)

Update A(4) = 3 as A was recognized

Update P(3)=5 as P was recognized

|-

|File:Eleventh step of recognizing CFG with packrat.svg

|

|

No update because no terminal was recognized

|-

|File:Twelfth step of recognizing CFG with packrat.svg

|

|

Hit on P(3)

Update M(1)=7 as M was recognized

|-

|File:13th step of recognizing CFG with packrat.svg

|

|

No update because no terminal was recognized

|-

|File:14th step of recognizing CFG with packrat.svg

|

|

Hit on M(1)

Update A(1)=7 as A was recognized

Update S(1)=7 as S was recognized

|}

{{See also|Comparison of parser generators#Parsing expression grammars, deterministic boolean grammars}}

• CYK algorithm
• Context-free grammar
• Parsing algorithms
• Earley parser

{{Reflist}}

• [https://bford.info/pub/lang/packrat-icfp02.pdf Packrat Parsing: Simple, Powerful, Lazy, Linear Time]
• [https://bford.info/pub/lang/peg.pdf Parsing Expression Grammars: A Recognition-Based Syntactic Foundation]

{{parsers}}

Category:Parsing algorithms

Category:Dynamic programming