User:Ilgeco1995/sandbox

Ilgeco1995/sandbox
Class	Parsing grammars that are PEG
Data structure	String
Worst-case performance	or without special handling of iterative combinator
Best-case performance	;
Average performance
Worst-case space complexity

This is the user sandbox of Ilgeco1995. A user sandbox is a subpage of the user's user page. It serves as a testing spot and page development space for the user and is not an encyclopedia article. Create or edit your own sandbox here.

Other sandboxes: Main sandbox | Template sandbox

Finished writing a draft article? Are you ready to request review of it by an experienced editor for possible inclusion in Wikipedia? Submit your draft for review!

The Packrat parser is a type of parser that shares similarities with the recursive descent parser in its construction. However, it differs because it takes parsing expression grammar as input rather than LL grammar.^[1]

In 1970, A. Birman laid the groundwork for packrat parsing by introducing the TMG recognition schema (TS). His work was later refined by Aho and Ullman and renamed the Generalized Top-Down Parsing Language (GTDPL). This algorithm was the first of its 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). Bryan also introduced Packract as a parser that uses memoization techniques on top of a simple PEG parser. This was done because PEGs has an unlimited lookahead capability resulting in a parser with exponential time performance in the worst case. ^[2]^[3]

Packract keeps track of the intermediate results for all mutually recursive parsing functions. Each parsing function is only called once at a specific input position. 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]

Syntax

Packract takes in input the same syntax as a PEGs:

A simple PEG is compose by terminal and nonterminal possibly interleaved with operators that composed one or several derivation rules^[2]

Symbols:

nonterminal are indicated with capital letter ex. $\{S,E,F,D\}$
Terminal symbols are indicated with lower case ex. $\{a,b,z,e,g\}$
Expression are indicated with lower case Greek letter $\{\alpha ,\beta ,\gamma ,\omega ,\tau \}$ $\{\alpha ,\beta ,\gamma ,\omega ,\tau \}$
- Expression can be a mix of terminal, nonterminal and operator

Operator:

Syntax Rules
Operator	Semantics
Sequence $\alpha \beta$	Success:If $\alpha$ and $\beta$ are recognized Failure: If $\alpha$ or $\beta$ are not recognized Consumed: $\alpha$ and $\beta$ in case of Success
Ordered choice $\alpha /\beta /\gamma$	Success:If any of $\{\alpha ,\beta ,\gamma \}$ is recognized starting from the left Failure: All of $\{\alpha ,\beta ,\gamma \}$ don't match Consumed: The atomic expression that has generated a success so if multiple succeed the first one is always returned
And predicate $\&\alpha$	Success:If $\alpha$ is recognized Failure: If $\alpha$ is not recognized Consumed: No input is consumed
Not predicate $!\alpha$	Success:If $\alpha$ is not recognized Failure: If $\alpha$ is recognized Consumed:No input is consumed
One or more $\alpha +$	Success: Try to recognize $\alpha$ one or multiple time Failure: If $\alpha$ is not recognize Consumed: The maximum number that $\alpha$ is recognized
Zero or more $\alpha *$	Success: Try to recognize $\alpha$ zero or multiple time Failure: Cannot fail Consumed: The maximum number that $\alpha$ is recognized
Zero or one $\alpha ?$	Success: Try to recognize $\alpha$ zero or once Failure: Cannot fail Consumed: $\alpha$ if it is recognized
Terminal range [ $a-b$ ]	Success: Recognize any terminal $c$ that are inside the range $[a-b]$ . in the case of $[{\textbf {'}}h{\textbf {'}}-{\textbf {'}}z{\textbf {'}}]$ $c$ can be any letter from h to z Failure: If no terminal inside of $[a-b]$ can be recognize Consumed: $c$ if it is recognized
Any character $.$	Success: Recognize any character in input Failure: If no character in input Consumed: any character in input

Rules:

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

A special expression $\alpha _{s}$ is the starting point of the grammar^[2]. in case no $\alpha _{s}$ is specified the first expression of the first rule is used.

An input string is considered accepted by the parser if the $\alpha _{s}$ is recognized. As a side-effect a string $x$ can be recognized by the parser even if it was not fully consumed.^[2]

An extreme case of this rule is that the grammar $S\rightarrow x*$ match any string

This can be avoided rewriting the grammar as $S->x*!.$

Example:

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

This grammar recognize the palindrome string over the alphabet $\{a,b\}$ with in the middle any digit

A Possible derivation is

Left recursion:

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^[5]. Since Packrat is a recursive descent parser, it cannot handle left recursion directly. During the early stages of development, it was found that a production that is left-recursive can be transformed into a right-recursive production.^[6] 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^[5].

Iterative combinator:

The iterative combinator $\alpha +$ , $\alpha *$ , needs special attention when a translated into a packrat parser. In fact the use of iterative combinators introduces a "secret" recursion that doesn't record intermediate results in the outcome matrix. This can lead to the parser operating in a superlinear. This Problem can be resolved apply the following transformation^[1]:


Original	Translated
$S\rightarrow \alpha +$	$S\rightarrow \alpha S/\alpha$
$S\rightarrow \alpha *$	$S\rightarrow \alpha S/\epsilon$

With these transformation the intermediate results can be properly memoizated.

Memoization technique

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.^[7] 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, memo 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. 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.^[9] When evaluating the entire $m*n$ matrix in a tabular approach, it would require $\Theta (mn)$ space.^[9] Here, $m$ represents the number of nonterminals, and $n$ represents the input string size.

In a naïve implementation the full 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 deep first visit of each subexpression. Consequently, using a matrix with dimensions of $m*n$ is often wasteful, as most entries will remain empty.^[5] These cells are linked to the input string, not the nonterminals of the grammar. This means that increasing the input string size will always increase memory consumption, while the number of parsing rules changes only the worst space complexity.^[1]

Cut operator

Another operator called "cut" has been introduced to Packract 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 ex $\{if,do,while,switch\}$ .^[10]

Operator	Semantics
Cut ${\begin{array}{l}\alpha \uparrow \beta /\gamma \\(\alpha \uparrow \beta )*\end{array}}$	if $\alpha$ is recognized but $\beta$ is not skip the evaluation of the alternative. In the first case don't evaluate $\gamma$ if $\alpha$ was recognized The second rule is can be rewritten as $N\rightarrow \alpha \uparrow \beta N/\epsilon$ and the same rules can be applied

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 will only need a nearly constant amount of space for memoization.^[10]

The algorithm

Sketch of a implementation of a packract algorithm in a LUA like pseudocode.^[5]

INPUT(n) -- return the character at position n

RULE(R : Rule, P : Position )
    entry = GET_MEMO(R,P) -- return the number of elements previusly 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 non terminal
            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(synbol.nonterminal , start+acc ); -- try to recognize a nonterminal in position start+acc
                SET_MEMO(synbol.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 match the last symbol in a choice if so return
                return start+acc;
        end
    end
    return fail; --if no choice match return fail

Example

Given the following context free grammar that recognize simple arithmetic expression composed by single digit interleaved by sum, multiplication and parenthesis.

${\begin{cases}S\rightarrow A\\A\rightarrow M\ {\textbf {'+'}}\ A\ /\ M\\M\rightarrow P\ {\textbf {'*'}}\ M\ /\ P\\P\rightarrow {\textbf {'('}}\ A\ {\textbf {')'}}\ /\ D\\D\rightarrow ({\textbf {'0'}}-{\textbf {'9'}})\end{cases}}$

Denoted with $\dashv$ the line terminator we can apply the packrat algorithm

Derivation of

2*(3+4)\dashv

Syntax tree

Action

Packrat Table

Derivation Rules	Input shifted
${\begin{array}{l}S\rightarrow A\\A\rightarrow M\ {\textbf {'+'}}\ A\\M\rightarrow P\ {\textbf {'*'}}\ M\\P\rightarrow {\textbf {'('}}\ A\ {\textbf {')'}}\end{array}}$	ɛ
Notes	Input left
Input doesn't match the first element in the derivation. Backtrack to the first grammar rule with unexplored alternative ${\textstyle P\rightarrow {\textbf {'('}}\ A\ {\textbf {')'}}\ /\ {\underline {D}}}$	$2*(3+4)\dashv$


	Index
	1	2	3	4	5	6	7
S
A
M
P
D
	2	*	(	3	+	4	)

No update because no terminal was recognized

Derivation Rules	Input shifted
$P\rightarrow D$ $D\rightarrow 2$	$2$
Notes	Input left
Shift input by one after deriving terminal $2$	$*(3+4)\dashv$

	Index
	1	2	3	4	5	6	7
S
A
M
P	1
D	1
	2	*	(	3	+	4	)

Update:

D(1) = 1;

P(1) = 1;

Derivation Rules	Input shifted
$M\rightarrow P\ {\textbf {'*'}}\ M$ $P\rightarrow {\textbf {'('}}\ A\ {\textbf {')'}}$	$2*($
Notes	Input left
Shift input by two terminal $\{{\textbf {*}},{\textbf {(}}\}$	$3+4)\dashv$

	Index
	1	2	3	4	5	6	7
S
A
M
P	1
D	1
	2	*	(	3	+	4	)

No update because no nonterminal was fully recognized

Derivation Rules	Input shifted
$A\rightarrow M\ {\textbf {'+'}}\ A$ $M\rightarrow P\ {\textbf {'*'}}\ M$ $P\rightarrow {\textbf {'('}}\ A\ {\textbf {')'}}$	$2*($
Notes	Input left
Input doesn't match the first element in the derivation. Backtrack to the first grammar rule with unexplored alternative ${\textstyle P\rightarrow {\textbf {'('}}\ A\ {\textbf {')'}}\ /\ {\underline {D}}}$	$3+4)\dashv$

	Index
	1	2	3	4	5	6	7
S
A
M
P	1
D	1
	2	*	(	3	+	4	)

No update because no terminal was recognized

Derivation Rules	Input shifted
$P\rightarrow D$ $D\rightarrow 3$	$2*($
Notes	Input left
Shift input by one after deriving terminal $3$ but the new input will not match $$ inside $M\rightarrow P\ {\textbf {''}}\ M$ so an unroll is necessary to $M\rightarrow P\ {\textbf {'*'}}\ M\ /\ {\underline {P}}$	$3+4)\dashv$

	Index
	1	2	3	4	5	6	7
S
A
M
P	1			1
D	1			1
	2	*	(	3	+	4	)

Update:

D(4) = 1;

P(4) = 1;

Derivation Rules	Input shifted
$M\rightarrow P$	$2*(3+$
Notes	Input left
Roll Back to $M\rightarrow P\ {\textbf {'*'}}\ M\ /\ {\underline {P}}$ 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). Shift also the $+$ from $A\rightarrow M\ {\textbf {'+'}}\ A$	$4)\dashv$

	Index
	1	2	3	4	5	6	7
S
A
M				1
P	1			1
D	1			1
	2	*	(	3	+	4	)

Hit on P(4)

Update M(4) = 1 as M was recognized

Derivation Rules	Input shifted
$A\rightarrow M\ {\textbf {'+'}}\ A$ $M\rightarrow P\ {\textbf {'*'}}\ M$ $P\rightarrow {\textbf {'('}}\ A\ {\textbf {')'}}$	$2*(3+$
Notes	Input left
Input doesn't match the first element in the derivation. Backtrack to the first grammar rule with unexplored alternative ${\textstyle P\rightarrow {\textbf {'('}}\ A\ {\textbf {')'}}\ /\ {\underline {D}}}$	$4)\dashv$

	Index
	1	2	3	4	5	6	7
S
A
M				1
P	1			1
D	1			1
	2	*	(	3	+	4	)

No update because no terminal was recognized

Derivation Rules	Input shifted
$P\rightarrow D$ $D\rightarrow 4$	$2*(3+$
Notes	Input left
Shift input by one after deriving terminal $4$ but the new input will not match $$ inside $M\rightarrow P\ {\textbf {''}}\ M$ so an unroll is necessary	$4)\dashv$

	Index
	1	2	3	4	5	6	7
S
A
M				1
P	1			1		1
D	1			1		1
	2	*	(	3	+	4	)

Update:

D(6) = 1;

P(6) = 1;

Derivation Rules	Input shifted
$M\rightarrow P$	$2*(3+$
Notes	Input left
Roll Back to $M\rightarrow P\ {\textbf {'*'}}\ M\ /\ {\underline {P}}$ 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). but the new input will not match $+$ inside $A\rightarrow M\ {\textbf {'+'}}\ A$ so an unroll is necessary	$4)\dashv$

	Index
	1	2	3	4	5	6	7
S
A
M				1		1
P	1			1		1
D	1			1		1
	2	*	(	3	+	4	)

Hit on P(6)

Update M(6) = 1 as M was recognized

Derivation Rules	Input shifted
$A\rightarrow M$	$2*(3+4)$
Notes	Input left
Roll Back to $A\rightarrow M\ {\textbf {'+'}}\ A\ /\ {\underline {M}}$ And we don't expand it has we have an hit in the memoization table M(6) ≠ 0 so shift the input by M(6). Also shift $)$ from $P\rightarrow {\textbf {'('}}\ A\ {\textbf {')'}}$	$\dashv$

	Index
	1	2	3	4	5	6	7
S
A				3
M				1		1
P	1		5	1		1
D	1			1		1
	2	*	(	3	+	4	)

Hit on M(6)

Update A(4) = 3 as A was recognized

Update P(3)=5 as P was recognized

Derivation Rules	Input shifted
	$2*$
Notes	Input left
Roll Back to $M\rightarrow P\ {\textbf {''}}\ M\ /\ {\underline {P}}$ as terminal $\neq \dashv$	$(3+4)\dashv$

	Index
	1	2	3	4	5	6	7
S
A				3
M				1		1
P	1		5	1		1
D	1			1		1
	2	*	(	3	+	4	)

No update because no terminal was recognized

Derivation Rules	Input shifted
$M\rightarrow P$	$2*(3+4)$
Notes	Input left
we don't expand it has we have an hit in the memoization table P(3) ≠ 0 so shift the input by P(3).	$\dashv$

	Index
	1	2	3	4	5	6	7
S
A				3
M	7			1		1
P	1		5	1		1
D	1			1		1
	2	*	(	3	+	4	)

Hit on P(3)

Update M(1)=7 as M was recognized

Derivation Rules	Input shifted

Notes	Input left
Roll Back to $A\rightarrow M\ {\textbf {'+'}}\ A\ /\ {\underline {M}}$ as as terminal $+\neq \dashv$	$2*(3+4)\dashv$

	Index
	1	2	3	4	5	6	7
S
A				3
M	7			1		1
P	1		5	1		1
D	1			1		1
	2	*	(	3	+	4	)

No update because no terminal was recognized

Derivation Rules	Input shifted
$A\rightarrow M$	$2*(3+4)\dashv$
Notes	Input left
we don't expand it has we have an hit in the memoization table M(1) ≠ 0 so shift the input by M(1). S was totally reduced so the input string is recognized

	Index
	1	2	3	4	5	6	7
S	7
A	7			3
M	7			1		1
P	1		5	1		1
D	1			1		1
	2	*	(	3	+	4	)

Hit on M(1)

Update A(1)=7 as A was recognized

Update S(1)=7 as S was recognized

Implementation

Name	Parsing algorithm	Output languages	Grammar, code	Development platform	License
AustenX	Packrat (modified)	Java	Separate	All	Free, BSD
Aurochs	Packrat	C, OCaml, Java	Mixed	All	Free, GNU GPL
Canopy	Packrat	Java, JavaScript, Python, Ruby	Separate	All	Free, GNU GPL
CL-peg	Packrat	Common Lisp	Mixed	All	Free, MIT
Drat!	Packrat	D	Mixed	All	Free, GNU GPL
Frisby	Packrat	Haskell	Mixed	All	Free, BSD
grammar::peg	Packrat	Tcl	Mixed	All	Free, BSD
IronMeta	Packrat	C#	Mixed	Windows	Free, BSD
lars::Parser	Packrat (supporting left-recursion and grammar ambiguity)	C++	Identical	All	Free, BSD
Narwhal	Packrat	C	Mixed	POSIX, Windows	Free, BSD
neotoma	Packrat	Erlang	Separate	All	Free, MIT
OMeta	Packrat (modified, partial memoization)	JavaScript, Squeak, Python	Mixed	All	Free, MIT
PackCC	Packrat (modified, left-recursion support)	C	Mixed	All	Free, MIT
Packrat	Packrat	Scheme	Mixed	All	Free, MIT
Pappy	Packrat	Haskell	Mixed	All	Free, BSD
Parsnip	Packrat	C++	Mixed	Windows	Free, GNU GPL
PEG.js	Packrat (partial memoization)	JavaScript	Mixed	All	Free, MIT
Peggy^[11]	Packrat (partial memoization)	JavaScript	Mixed	All	Free, MIT
Pegasus	Recursive descent, Packrat (selectively)	C#	Mixed	Windows	Free, MIT
PetitParser	Packrat	Smalltalk, Java, Dart	Mixed	All	Free, MIT
PyPy rlib	Packrat	Python	Mixed	All	Free, MIT
Rats!	Packrat	Java	Mixed	Java virtual machine	Free, GNU LGPL

References

^ ^a ^b ^c Ford, Bryan (2006). "Packrat Parsing: Simple, Powerful, Lazy, Linear Time". International Conference on Functional Programming. arXiv:cs/0603077. Bibcode:2006cs........3077F.
^ ^a ^b ^c ^d ^e Ford, Bryan (2004-01-01). "Parsing expression grammars: A recognition-based syntactic foundation". Proceedings of the 31st ACM SIGPLAN-SIGACT symposium on Principles of programming languages. POPL '04. New York, NY, USA: Association for Computing Machinery. pp. 111–122. doi:10.1145/964001.964011. ISBN 978-1-58113-729-3. S2CID 7762102.
^ ^a ^b Flodin, Daniel. "A Comparison Between Packrat Parsing and Conventional Shift-Reduce Parsing on Real-World Grammars and Inputs" (PDF).{{cite web}}: CS1 maint: url-status (link)
^ Mizushima, Kota; Maeda, Atusi; Yamaguchi, Yoshinori (2010-05-06). "Packrat parsers can handle practical grammars in mostly constant space". Proceedings of the 9th ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering. ACM. pp. 29–36. doi:10.1145/1806672.1806679. ISBN 978-1-4503-0082-7. S2CID 14498865.
^ ^a ^b ^c ^d Warth, Alessandro; Douglass, James R.; Millstein, Todd (2008-01-07). "Packrat parsers can support left recursion". Proceedings of the 2008 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation. PEPM '08. New York, NY, USA: Association for Computing Machinery. pp. 103–110. doi:10.1145/1328408.1328424. ISBN 978-1-59593-977-7. S2CID 2168153.
^ Aho, Alfred V.; Lam, Monica S.; Sethi, Ravi; Ullman, Jeffrey D., eds. (2007). Compilers: principles, techniques, & tools (2nd ed.). Boston Munich: Pearson Addison-Wesley. ISBN 978-0-321-48681-3.
^ Norvig, Peter (1991-03-01). "Techniques for automatic memoization with applications to context-free parsing". Computational Linguistics. 17 (1): 91–98. ISSN 0891-2017.
^ Dubroy, Patrick; Warth, Alessandro (2017-10-23). "Incremental packrat parsing". Proceedings of the 10th ACM SIGPLAN International Conference on Software Language Engineering. SLE 2017. New York, NY, USA: Association for Computing Machinery. pp. 14–25. doi:10.1145/3136014.3136022. ISBN 978-1-4503-5525-4. S2CID 13047585.
^ ^a ^b Science, International Journal of Scientific Research in; Ijsrset, Engineering and Technology. "A Survey of Packrat Parser". A Survey of Packrat Parser.
^ ^a ^b Mizushima, Kota; Maeda, Atusi; Yamaguchi, Yoshinori (2010-05-06). "Packrat parsers can handle practical grammars in mostly constant space". Proceedings of the 9th ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering. PASTE '10. New York, NY, USA: Association for Computing Machinery. pp. 29–36. doi:10.1145/1806672.1806679. ISBN 978-1-4503-0082-7. S2CID 14498865.
^ Maintained fork of PEG.js

External links

Packrat Parsing: Simple, Powerful, Lazy, Linear Time

Parsing Expression Grammars: A Recognition-Based Syntactic Foundation

[:3-1] Ford, Bryan (2006). "Packrat Parsing: Simple, Powerful, Lazy, Linear Time". International Conference on Functional Programming. arXiv:cs/0603077. Bibcode:2006cs........3077F.

[:1-2] Ford, Bryan (2004-01-01). "Parsing expression grammars: A recognition-based syntactic foundation". Proceedings of the 31st ACM SIGPLAN-SIGACT symposium on Principles of programming languages. POPL '04. New York, NY, USA: Association for Computing Machinery. pp. 111–122. doi:10.1145/964001.964011. ISBN 978-1-58113-729-3. S2CID 7762102.

[:0-3] Flodin, Daniel. "A Comparison Between Packrat Parsing and Conventional Shift-Reduce Parsing on Real-World Grammars and Inputs" (PDF).{{cite web}}: CS1 maint: url-status (link)

[4] Mizushima, Kota; Maeda, Atusi; Yamaguchi, Yoshinori (2010-05-06). "Packrat parsers can handle practical grammars in mostly constant space". Proceedings of the 9th ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering. ACM. pp. 29–36. doi:10.1145/1806672.1806679. ISBN 978-1-4503-0082-7. S2CID 14498865.

[:2-5] Warth, Alessandro; Douglass, James R.; Millstein, Todd (2008-01-07). "Packrat parsers can support left recursion". Proceedings of the 2008 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation. PEPM '08. New York, NY, USA: Association for Computing Machinery. pp. 103–110. doi:10.1145/1328408.1328424. ISBN 978-1-59593-977-7. S2CID 2168153.

[6] Aho, Alfred V.; Lam, Monica S.; Sethi, Ravi; Ullman, Jeffrey D., eds. (2007). Compilers: principles, techniques, & tools (2nd ed.). Boston Munich: Pearson Addison-Wesley. ISBN 978-0-321-48681-3.

[7] Norvig, Peter (1991-03-01). "Techniques for automatic memoization with applications to context-free parsing". Computational Linguistics. 17 (1): 91–98. ISSN 0891-2017.

[8] Dubroy, Patrick; Warth, Alessandro (2017-10-23). "Incremental packrat parsing". Proceedings of the 10th ACM SIGPLAN International Conference on Software Language Engineering. SLE 2017. New York, NY, USA: Association for Computing Machinery. pp. 14–25. doi:10.1145/3136014.3136022. ISBN 978-1-4503-5525-4. S2CID 13047585.

[:4-9] Science, International Journal of Scientific Research in; Ijsrset, Engineering and Technology. "A Survey of Packrat Parser". A Survey of Packrat Parser.

[:5-10] Mizushima, Kota; Maeda, Atusi; Yamaguchi, Yoshinori (2010-05-06). "Packrat parsers can handle practical grammars in mostly constant space". Proceedings of the 9th ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering. PASTE '10. New York, NY, USA: Association for Computing Machinery. pp. 29–36. doi:10.1145/1806672.1806679. ISBN 978-1-4503-0082-7. S2CID 14498865.

[11] Maintained fork of PEG.js

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

v t e Parsing algorithms
Top-down	Earley LL Recursive descent Tail recursive
Bottom-up	Precedence Simple Operator Shunting-yard LR Simple Look-ahead Canonical Generalized CYK Recursive ascent Shift-reduce
Mixed, other	Combinator Chart Left corner Statistical
Related topics	PEG Definite clause grammar Deterministic parsing Dynamic programming Memoization Parser generator LALR Parse tree AST Scannerless parsing History of compiler construction Comparison of parser generators Operator-precedence grammar

Syntax

Symbols:

Operator:

Rules:

Example:

Left recursion:

Iterative combinator:

Memoization technique

Cut operator

The algorithm

Example

Implementation

See also

References

External links