Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.
Concept
Parser packrat
Résumé
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, 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 as Generalized Top-Down Parsing Language (GTDPL). This algorithm was the first of its 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). Bryan 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.
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., )
Terminal symbols are indicated with lowercase (e.g., )
Expressions are indicated with lower-case Greek letter (e.g., )
Expressions can be a mix of terminal symbols, nonterminal symbols and operators
A derivation rule is composed by a nonterminal symbol and an expression .
A special expression is the starting point of the grammar.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.