Packrat Parsing: A Literature Review <s> INTRODUCTION <s> From volume 1 Preface (See Front Matter for full Preface) ::: ::: This book is intended for a one or two semester course in compiling theory at the senior or graduate level. It is a theoretically oriented treatment of a practical subject. Our motivation for making it so is threefold. ::: ::: (1) In an area as rapidly changing as Computer Science, sound pedagogy demands that courses emphasize ideas, rather than implementation details. It is our hope that the algorithms and concepts presented in this book will survive the next generation of computers and programming languages, and that at least some of them will be applicable to fields other than compiler writing. ::: ::: (2) Compiler writing has progressed to the point where many portions of a compiler can be isolated and subjected to design optimization. It is important that appropriate mathematical tools be available to the person attempting this optimization. ::: ::: (3) Some of the most useful and most efficient compiler algorithms, e.g. LR(k) parsing, require a good deal of mathematical background for full understanding. We expect, therefore, that a good theoretical background will become essential for the compiler designer. ::: ::: While we have not omitted difficult theorems that are relevant to compiling, we have tried to make the book as readable as possible. Numerous examples are given, each based on a small grammar, rather than on the large grammars encountered in practice. It is hoped that these examples are sufficient to illustrate the basic ideas, even in cases where the theoretical developments are difficult to follow in isolation. ::: ::: From volume 2 Preface (See Front Matter for full Preface) ::: ::: Compiler design is one of the first major areas of systems programming for which a strong theoretical foundation is becoming available. Volume I of The Theory of Parsing, Translation, and Compiling developed the relevant parts of mathematics and language theory for this foundation and developed the principal methods of fast syntactic analysis. Volume II is a continuation of Volume I, but except for Chapters 7 and 8 it is oriented towards the nonsyntactic aspects of compiler design. ::: ::: The treatment of the material in Volume II is much the same as in Volume I, although proofs have become a little more sketchy. We have tried to make the discussion as readable as possible by providing numerous examples, each illustrating one or two concepts. ::: ::: Since the text emphasizes concepts rather than language or machine details, a programming laboratory should accompany a course based on this book, so that a student can develop some facility in applying the concepts discussed to practical problems. The programming exercises appearing at the ends of sections can be used as recommended projects in such a laboratory. Part of the laboratory course should discuss the code to be generated for such programming language constructs as recursion, parameter passing, subroutine linkages, array references, loops, and so forth. <s> BIB001 </s> Packrat Parsing: A Literature Review <s> INTRODUCTION <s> Two classes of restricted top-down parsing algorithms modeling “recursive descent” are considered. We show that the smaller class recognizes all deterministic context free languages, and that both classes can be simulated in linear time on a random access machine. Certain generalizations of these parsing algorithms are shown equivalent to the larger class. Finally, it is shown that the larger class has the property that loops and other “failures” can always be eliminated. <s> BIB002 </s> Packrat Parsing: A Literature Review <s> INTRODUCTION <s> Computer program input generally has some structure; in fact, every computer program that does input can be thought of as defining an ‘‘input language’’ which it accepts. An input language may be as complex as a programming language, or as simple as a sequence of numbers. Unfortunately, usual input facilities are limited, difficult to use, and often are lax about checking their inputs for validity. Yacc provides a general tool for describing the input to a computer program. The Yacc user specifies the structures of his input, together with code to be invoked as each such structure is recognized. Yacc turns such a specification into a subroutine that handles the input process; frequently, it is convenient and appropriate to have most of the flow of control in the user’s application handled by this subroutine. The input subroutine produced by Yacc calls a user-supplied routine to return the next basic input item. Thus, the user can specify his input in terms of individual input characters, or in terms of higher level constructs such as names and numbers. The user-supplied routine may also handle idiomatic features such as comment and continuation conventions, which typically defy easy grammatical specification. <s> BIB003 </s> Packrat Parsing: A Literature Review <s> INTRODUCTION <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> BIB004 </s> Packrat Parsing: A Literature Review <s> INTRODUCTION <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> BIB005 </s> Packrat Parsing: A Literature Review <s> INTRODUCTION <s> Two recent developments in the field of formal languages are Parsing Expression Grammar (PEG) and packrat parsing. The PEG formalism is similar to BNF, but defines syntax in terms of recognizing strings, rather than constructing them. It is, in fact, precise specification of a backtracking recursive-descent parser. Packrat parsing is a general method to handle backtracking in recursive-descent parsers. It ensures linear working time, at a huge memory cost. This paper reports an experiment that consisted of defining the syntax of Java 1.5 in PEG formalism, and literally transcribing the PEG definitions into parsing procedures (accidentally, also in Java). The resulting primitive parser shows an acceptable behavior, indicating that packrat parsing might be an overkill for practical languages. The exercise with defining the Java syntax suggests thatmore work is needed on PEG as a language specification tool. <s> BIB006
Parsing consists of two processes: lexical analysis and parsing. The job of the lexical analysis is to break down the input text (string) into smaller parts, called tokens. The lexical analyzer then sends these tokens to the parser in sequence. During parsing, the parser takes the help of a grammar to decide whether to accept the input string or reject .i.e. whether it is a subset of the accepting language or not. A set of grammar rules or productions is used to define the language of grammar. Each production can then, in turn, compose of several different alternative productions. These productions guide the parser throughout the parsing to determine whether to accept the input string or to reject it. Top-down parsing is a parsing strategy that attempts left-to-right leftmost derivation (LL) for the input string. This can be achieved with prediction, backtracking or a combination of the two. LL(k) top-down parser makes its decisions based on lookahead, where the parser attempts to "look ahead" k number of symbols of the input string. A top-down parser that uses backtracking instead evaluates each production and its choices in turn; if a choice/production fails the parser backtracks on the input string and evaluates the next choice/production, if the choice/production succeeds the parser merely continues. The bottom-up parsing is a parsing method that instead attempts to perform a left-to-right rightmost derivation (LR) in reverse of the input string. Shift-reduce parsing is widely used bottom-up parsing technique. A shift-reduce parser uses two different actions during parsing: shift and reduce. A shift action takes a number of symbols from the input string and places them on a stack. The reduce action reduces the symbols on the stack based on finding a matching grammar production for the symbols. The decisions regarding whether to shift or reduce are done based on lookahead. Several different parsing techniques have been developed over the years, both for parsing ambiguous and unambiguous grammars. One of the latest is packrat parsing BIB004 . Packrat parsing is based upon a top-down recursive descent parsing approach with memoization that guarantees linear parse time. Memoization employed in the packrat parsing eliminates disadvantage of conventional topdown backtracking algorithms which suffer from exponential parsing time in the worst case. This exponential runtime is due to performing redundant evaluations caused by backtracking. Packrat parsers avoid this by storing all of the evaluated results to be used for future backtracking eliminating redundant computations. This storing technique is called memoization which ensures guaranteed linear parsing time for packrat parsers. The memory consumption for conventional parse algorithms is linear to the size of the maximum recursion depth occurring during the parse. In the worst case it can be the same as the size of the input string. In packrat parsing, the memory consumption for a packrat parser is linearly proportional to the size of the input string. Packrat parsing is based upon parsing expression grammars (PEGs) which have the property of always producing unambiguous grammars. It has been proven that all LL(k) and LR(k) grammars can be rewritten into a PEG BIB005 . Thus, packrat parsing is able to parse all context-free grammars. In fact, it can even parse some grammars that are non-context-free BIB005 . Another characteristic of packrat parsing is that it is scannerless i.e. a separate lexical analyzer is not needed. In packrat parsers, they are both integrated into the same tool, as opposed to the Lex [10] /Yacc BIB003 approach where Lex is used for the lexical analysis and Yacc for parsing phase of the compiler.The founding work for packrat parsing was carried out in 1970 by A. Birman et. al.  . Birman introduced a schema called the TMG recognition schema (TS). Birman's work was later refined by A. Aho and J. Ullman et. al. BIB001 , and renamed into generalized top-down parsing language (GTDPL). This was the first top-down parsing algorithm that was deterministic and used backtracking. Due to deterministic nature of resulting grammar they discovered that the parsing results could be saved in a table to avoid redundant computations. However, this approach was never put into practice, due to the limited amount of main memory in computers at that time [10, BIB006 . Another characteristic of GTDPL is that it can express any LL(k) and LR(k) language, and even some non-context-free languages BIB001 BIB002 . Rest of the paper consists of introduction to Parsing Expression grammar 26 | P a g e www.ijarai.thesai.org along with discussion on its properties followed by the work carried out by researchers in this area. Finally the paper focuses upon the open problems in packrat parsing and concluded with future work.