Packrat Parsing: A Literature Review <s> D. Syntatic Predicates <s> Most language translation problems can be solved with existing LALR(1) or LL(k) language tools; e.g., YACC [Joh78] or ANTLR [PDC92]. However, there are language constructs that defy almost all parsing strategy commonly in use. Some of these constructs cannot be parsed without semantics, such as symbol table information, and some cannot be properly recognized without first examining the entire construct, that is we need “infinite lookahead.” <s> BIB001 </s> Packrat Parsing: A Literature Review <s> D. Syntatic Predicates <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> BIB002
PEGs allow the use of the syntactic predicates! and &. Consider the following grammar production: A <-!B C Every time this production is invoked it needs to establish if the input string matches a B and if it does, signal a failure. If there is no match the original input string is compared with the nonterminal C. This ability to "look ahead" an arbitrary amount of characters combined with the selective backtracking gives packrat parsers unlimited lookahead [10,  BIB002 BIB001 .