packrat parser

parsing algorithm that takes parsing expression grammars (PEGs) as input

Uses your system voice; voice and rate in settings.

Q11329019Snapshot

≈ 5 min read

Names in other languages

  • eopakrata sintaksanalizilo
  • slrazčlenjevalnik packrat
  • Englishpackrat parser
  • Françaisparser packrat
  • 日本語パックラット構文解析

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

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 grammars (PEGs) as input rather than LL grammars. In 1970, Alexander Birman laid the groundwork for packrat parsing by introducing the "TMG recognition scheme" (TS), and "generalized TS" (gTS).

TS was based upon Robert M. McClure's TMG compiler-compiler, and gTS was based upon Dewey Val Schorre's META compiler-compiler. Birman's work was later refined by Aho and Ullman; and renamed as Top-Down Parsing Language (TDPL), and Generalized TDPL (GTDPL), respectively. These algorithms were the first of their kind to employ deterministic top-down parsing with backtracking.

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). Ford also introduced Packrat as a parser that uses memoization techniques on top of a simple PEG parser.

This was done because PEGs have an unlimited lookahead capability resulting in a parser with exponential time performance in the worst case. Packrat keeps track of the intermediate results for all mutually recursive parsing functions. Each parsing function is only called once at a specific input position.…

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 grammars (PEGs) as input rather than LL grammars. In 1970, Alexander Birman laid the groundwork for packrat parsing by introducing the "TMG recognition scheme" (TS), and "generalized TS" (gTS).

TS was based upon Robert M. McClure's TMG compiler-compiler, and gTS was based upon Dewey Val Schorre's META compiler-compiler. Birman's work was later refined by Aho and Ullman; and renamed as Top-Down Parsing Language (TDPL), and Generalized TDPL (GTDPL), respectively. These algorithms were the first of their kind to employ deterministic top-down parsing with backtracking.

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). Ford also introduced Packrat as a parser that uses memoization techniques on top of a simple PEG parser.

This was done because PEGs have an unlimited lookahead capability resulting in a parser with exponential time performance in the worst case. Packrat 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. 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 D(1) = 1; P(1) = 1; |- | | | No update because no nonterminal was fully recognized |- | | | No update because no terminal was recognized |- | | | Update: D(4) = 1; P(4) = 1; |- | | | Hit on P(4) Update M(4) = 1 as M was recognized |- | | | No update because no terminal was recognized |- | | | Update: D(6) = 1; P(6) = 1; |- | | | Hit on P(6) Update M(6) = 1 as M was recognized |- | | | Hit on M(6) Update A(4) = 3 as A was recognized Update P(3)=5 as P was recognized |- | | | No update because no terminal was recognized |- | | | Hit on P(3) Update M(1)=7 as M was recognized |- | | | No update because no terminal was recognized |- | | | Hit on M(1) Update A(1)=7 as A was recognized Update S(1)=7 as S was recognized |}

Text derived from https://en.wikipedia.org/w/index.php?oldid=1369059820 under CC BY-SA 4.0; modifications have been made.

Provenance

snapshot packrat-parser-1230186-ed392930c6680704 · hash ed392930c66807046d4f67c57faf3615617cba67960a2218e05a1bda6b78eb4c · captured 1786547412.0 · version history

Cite this page as: encyclopegia.org, “packrat parser”, snapshot packrat-parser-1230186-ed392930c6680704. https://encyclopegia.org/a/packrat-parser

Sources cited in this revision

No external citation was extracted for this revision. That is a statement about the source, not a claim that none exists.