Packrat Parsing: A Literature Review <s> III. LITERATURE SURVEY <s> Packrat parsing is a newly popular technique for efficiently implementing recursive descent parsers. Packrat parsing avoids the potential exponential costs of recursive descent parsing with backtracking by ensuring that each production rule in the grammar is tested at most once against each position in the input stream. This paper argues that (a) packrat parsers can be trivially implemented using a combination of definite clause grammar rules and memoing, and that (b) packrat parsing may actually be significantly less efficient than plain recursive descent with backtracking, but (c) memoing the recognizers of just one or two nonterminals, selected in accordance with Amdahl's law, can sometimes yield speedups. We present experimental evidence to support these claims. <s> BIB001 </s> Packrat Parsing: A Literature Review <s> III. LITERATURE SURVEY <s> Packrat parsing is a novel technique for implementing parsers in a lazy functional programming language. A packrat parser provides the power and flexibility of top-down parsing with backtracking and unlimited lookahead, but nevertheless guarantees linear parse time. Any language defined by an LL(k) or LR(k) grammar can be recognized by a packrat parser, in addition to many languages that conventional linear-time algorithms do not support. This additional power simplifies the handling of common syntactic idioms such as the widespread but troublesome longest-match rule, enables the use of sophisticated disambiguation strategies such as syntactic and semantic predicates, provides better grammar composition properties, and allows lexical analysis to be integrated seamlessly into parsing. Yet despite its power, packrat parsing shares the same simplicity and elegance as recursive descent parsing; in fact converting a backtracking recursive descent parser into a linear-time packrat parser often involves only a fairly straightforward structural change. This paper describes packrat parsing informally with emphasis on its use in practical applications, and explores its advantages and disadvantages with respect to the more conventional alternatives. <s> BIB002 </s> Packrat Parsing: A Literature Review <s> III. LITERATURE SURVEY <s> For decades we have been using Chomsky's generative system of grammars, particularly context-free grammars (CFGs) and regular expressions (REs), to express the syntax of programming languages and protocols. The power of generative grammars to express ambiguity is crucial to their original purpose of modelling natural languages, but this very power makes it unnecessarily difficult both to express and to parse machine-oriented languages using CFGs. Parsing Expression Grammars (PEGs) provide an alternative, recognition-based formal foundation for describing machine-oriented syntax, which solves the ambiguity problem by not introducing ambiguity in the first place. Where CFGs express nondeterministic choice between alternatives, PEGs instead use prioritized choice. PEGs address frequently felt expressiveness limitations of CFGs and REs, simplifying syntax definitions and making it unnecessary to separate their lexical and hierarchical components. A linear-time parser can be built for any PEG, avoiding both the complexity and fickleness of LR parsers and the inefficiency of generalized CFG parsing. While PEGs provide a rich set of operators for constructing grammars, they are reducible to two minimal recognition schemas developed around 1970, TS/TDPL and gTS/GTDPL, which are here proven equivalent in effective recognition power. <s> BIB003 </s> Packrat Parsing: A Literature Review <s> III. LITERATURE SURVEY <s> We explore how to make the benefits of modularity available for syntactic specifications and present Rats!, a parser generator for Java that supports easily extensible syntax. Our parser generator builds on recent research on parsing expression grammars (PEGs), which, by being closed under composition, prioritizing choices, supporting unlimited lookahead, and integrating lexing and parsing, offer an attractive alternative to context-free grammars. PEGs are implemented by so-called packrat parsers, which are recursive descent parsers that memoize all intermediate results (hence their name). Memoization ensures linear-time performance in the presence of unlimited lookahead, but also results in an essentially lazy, functional parsing technique. In this paper, we explore how to leverage PEGs and packrat parsers as the foundation for extensible syntax. In particular, we show how make packrat parsing more widely applicable by implementing this lazy, functional technique in a strict, imperative language, while also generating better performing parsers through aggressive optimizations. Next, we develop a module system for organizing, modifying, and composing large-scale syntactic specifications. Finally, we describe a new technique for managing (global) parsing state in functional parsers. Our experimental evaluation demonstrates that the resulting parser generator succeeds at providing extensible syntax. In particular, Rats! enables other grammar writers to realize real-world language extensions in little time and code, and it generates parsers that consistently out-perform parsers created by two GLR parser generators. <s> BIB004 </s> Packrat Parsing: A Literature Review <s> III. LITERATURE SURVEY <s> Parsing Expression Grammar (PEG) is a recognition-based foundation for describing syntax that renewed interest in top-down parsing approaches. Generally, the implementation of PEGs is based on a recursive-descent parser, or uses a memoization algorithm. We present a new approach for implementing PEGs, based on a virtual parsing machine, which is more suitable for pattern matching. Each PEG has a corresponding program that is executed by the parsing machine, and new programs are dynamically created and composed. The virtual machine is embedded in a scripting language and used by a patternmatching tool. We give an operational semantics of PEGs used for pattern matching, then describe our parsing machine and its semantics. We show how to transform PEGs to parsing machine programs, and give a correctness proof of our transformation. <s> BIB005 </s> Packrat Parsing: A Literature Review <s> III. LITERATURE SURVEY <s> Packrat parsing offers several advantages over other parsing techniques, such as the guarantee of linear parse times while supporting backtracking and unlimited look-ahead. Unfortunately, the limited support for left recursion in packrat parser implementations makes them difficult to use for a large class of grammars (Java's, for example). This paper presents a modification to the memoization mechanism used by packrat parser implementations that makes it possible for them to support (even indirectly or mutually) left-recursive rules. While it is possible for a packrat parser with our modification to yield super-linear parse times for some left-recursive grammars, our experimentsshow that this is not the case for typical uses of left recursion. <s> BIB006 </s> Packrat Parsing: A Literature Review <s> III. LITERATURE SURVEY <s> The paper is an attempt to see how much we can learn about a given Parsing Expression Grammar with the help of classical concepts used in the construction of predictive top-down parsers. <s> BIB007 </s> Packrat Parsing: A Literature Review <s> III. LITERATURE SURVEY <s> Packrat parsing is a powerful parsing algorithm presented by Ford in 2002. Packrat parsers can handle complicated grammars and recursive structures in lexical elements more easily than the traditional LL(k) or LR(1) parsing algorithms. However, packrat parsers require O(n) space for memoization, where n is the length of the input. This space inefficiency makes packrat parsers impractical in some applications. In our earlier work, we had proposed a packrat parser generator that accepts grammars extended with cut operators, which enable the generated parsers to reduce the amount of storage required. Experiments showed that parsers generated from cut-inserted grammars can parse Java programs and subset XML files in bounded space. In this study, we propose methods to automatically insert cut operators into some practical grammars without changing the accepted languages. Our experimental evaluations indicated that using our methods, packrat parsers can handle some practical grammars including the Java grammar in mostly constant space without requiring any extra annotations. <s> BIB008
PEGs are a recently introduced technique for describing grammars by Ford in BIB002 with implementation of the packrat parser. Theory is based upon strong foundations. Ford BIB004 showed how PRGs can be reduced to TDPLs long back in the 1970s. It was shown by Roman  that primitive recursivedescent parser with limited backtracking alongwith integrated lexing can be used for parsing Java 1.5 where requirement is of moderate performance. PEG is not good as a language specification tool as shown in [25] . The characteristic of a specification is that what it specifies is clearly to be seen. But this is, unfortunately, not valid for PEG. Further it gives reasonable performance when C grammar is slightly modified and also in BIB007 he studied that classical properties like FIRST and FOLLOW where he demonstrated those can be redefined for PEG and can be obtained even for a large grammar. FIRST and FOLLOW are used to define conditions for choice and iteration that are similar to the classical LL(1) conditions, although they have a different structure and semantics. This is different from classical properties like FIRST and FOLLOW where letters are terminal expressions, which may mean sets of letters, or strings. Checking these conditions gives an idea of useful information like the absence of reprocessing or language hiding which is helpful in locating places that need further examination. The properties FIRST and FOLLOW are kind of upper bounds, and conditions using them are sufficient, but not necessary which may results in false warnings In BIB005 a virtual parsing machine approach is proposed for implementing PEG which is can be applied to pattern matching. Each PEG is converted directly into its equivalent corresponding program Virtual parsing machine then using scripting language excutes the translated program. Creation and composition of new programs are done on fly. In BIB003 Robert grimm parsing technique made practical for object-oriented languages. This parser generator employs simpler grammar specifications. Error reporting is also made easy by this parser generator and shown to be better performing parsers through aggressive optimizations. In  cut operator was introduced to parsing expression grammars (PEGs) and when applied to PEG on which packrat parsing is based. Disadvantage is largely addressed with this approach. Concept of cut operator was borrowed from Prolog  . It introduces degree of controlling backtracking. An efficient packrat parser can be developed avoiding unnecessary space for memorization by inserting cut operators into a PEG grammar at appropriate places. To show effectiveness and usefulness of cut operators, a packrat parser generator called Yapp was implemented and used. It accepts Parsing Expression Grammar marked with cut operator. The experimental evaluations showed that the packrat parsers generated using grammars with cut operators inserted can parse Java programs and subset of XML files in mostly constant space, unlike conventional packrat parsers. In BIB008 automatic insertion of cut operators was proposed that achieves the same effect. In these methods, a statistical analysis is made of a PEG grammar by parser generator in order to find the places where the parser generator can insert cut operators without changing the meaning of the grammar and cut operators are inserted at these identified points. Definite clause grammar rules and memoing can be a possible combination for implementation of packrat parser as shown in BIB001 .Further it points out that packrat parsing may degrade its performance over plain recursive descent with backtracking, but memoing the recognizers of just one or two nonterminals can sometimes give reasonable performance. Warth BIB006 tweaked memoization approach used by packrat parser because of which left-recursion even indirectly or mutually was supported. But some experiments were conducted out to show that this is not the case for typical uses of left recursion. In BIB004 Coq formalization of the theory of PEGs is proposed and with this as a foundation a formally verified parser interpreter for PEGs, TRX is developed. This gives rise to writing a PEG, together with its semantic actions, in Coq and then a parser can be extracted from it a parser with total correctness guarantees. This ensures that the parser will terminate on all kind of inputs and produces output as a parsing results correct with respect to the semantics of PEGs. In  concept of elastic sliding window is used and it is based upon the observation of worst longest backtrack length. Particularly author noted that if a window in the form of small memorization table slides and covers the longest backtrack then redundant calls are avoided since the storage is sufficient enough to store all the results. Practically, it is difficult to get the longest backtrack before parsing as it is runtime entity. Here window is approximated from empirical investigation and if needed may be expanded during parsing. [28] introduces derivative parsing with memorized approach algorithm for recognition of PEG. Main problem in this algorithm since derivative parsing attempts all possible parses concurrently is to identify which constructs exactly in the current parse tree can match against or consume the current character. This problem is solved by using concept of a backtracking generation (or generation) as a means to take into account for backtracking choices in the process of parsing. Execution of the algorithm is found to be in worst case quadratic time and cubic space. However, it is stressed in this paper that due to the limited amount of backtracking and recursion in grammars when put in practical use and input, practical performance may be nearer to linear time and constant space and requires experimental validation for the same which is in progress. Table II summarizes the  comparative study of major packrat parser generators. TABLE I. COMPARISON OF VARIOUS PACKRAT PARSER GENERATORS