This article includes a list of general references, but it lacks sufficient corresponding inline citations. Please help to improve this article by introducing more precise citations.(February 2009) (Learn how and when to remove this message)
In computer science, a recursive descent parser is a kind of top-down parser built from a set of mutually recursive procedures (or a non-recursive equivalent) where each such procedure implements one of the nonterminals of the grammar. Thus the structure of the resulting program closely mirrors that of the grammar it recognizes.[1]
A predictive parser is a recursive descent parser that does not require backtracking.[2] Predictive parsing is possible only for the class of LL(k) grammars, which are the context-free grammars for which there exists some positive integer k that allows a recursive descent parser to decide which production to use by examining only the next k tokens of input. The LL(k) grammars therefore exclude all ambiguous grammars, as well as all grammars that contain left recursion. Any context-free grammar can be transformed into an equivalent grammar that has no left recursion, but removal of left recursion does not always yield an LL(k) grammar. A predictive parser runs in linear time.
Recursive descent with backtracking is a technique that determines which production to use by trying each production in turn. Recursive descent with backtracking is not limited to LL(k) grammars, but is not guaranteed to terminate unless the grammar is LL(k). Even when they terminate, parsers that use recursive descent with backtracking may require exponential time.
Although predictive parsers are widely used, and are frequently chosen if writing a parser by hand, programmers often prefer to use a table-based parser produced by a parser generator,[citation needed] either for an LL(k) language or using an alternative parser, such as LALR or LR. This is particularly the case if a grammar is not in LL(k) form, as transforming the grammar to LL to make it suitable for predictive parsing is involved. Predictive parsers can also be automatically generated, using tools like ANTLR.
Predictive parsers can be depicted using transition diagrams for each non-terminal symbol where the edges between the initial and the final states are labelled by the symbols (terminals and non-terminals) of the right side of the production rule.[3]
^Burge, W.H. (1975). Recursive Programming Techniques. ISBN 0-201-14450-6.
^Watson, Des (22 March 2017). A Practical Approach to Compiler Construction. Springer. ISBN 978-3-319-52789-5.
^Aho, Alfred V.; Sethi, Ravi; Ullman, Jeffrey (1986). Compilers: Principles, Techniques and Tools (first ed.). Addison Wesley. p. 183.
and 23 Related for: Recursive descent parser information
computer science, a recursivedescentparser is a kind of top-down parser built from a set of mutually recursive procedures (or a non-recursive equivalent) where...
in practice, e.g. by a recursivedescentparser. Unlike CFGs, PEGs cannot be ambiguous; a string has exactly one valid parse tree or none. It is conjectured...
parser combinator is a higher-order function that accepts several parsers as input and returns a new parser as its output. In this context, a parser is...
<identifier> A simple tail recursiveparser can be written much like a recursivedescentparser. The typical algorithm for parsing a grammar like this using...
backtracking recursivedescentparser to solve the problem of exponential time complexity. The basic idea in Norvig's approach is that when a parser is applied...
supporting some context-free grammars and parsing expression grammars Recursivedescentparser: a top-down parser suitable for LL(k) grammars Shunting-yard...
computer science, an LL parser (Left-to-right, leftmost derivation) is a top-down parser for a restricted context-free language. It parses the input from Left...
is about the formal properties of LL grammars; for parsing, see LL parser or recursivedescentparser. Given a natural number k ≥ 0 {\displaystyle k\geq...
recursive ascent parsing is a technique for implementing an LR parser which uses mutually-recursive functions rather than tables. Thus, the parser is...
{Expression}}+{\mathit {Term}}} is directly left-recursive. A left-to-right recursivedescentparser for this rule might look like void Expression() {...
code. A recursive ascent parser implements an LALR parser using mutually-recursive functions rather than tables. Thus, the parser is directly encoded in...
parser loop in table-driven parsers. The fastest parsers use generated assembler code. In the recursive ascent parser variation, the explicit parse stack...
and in some problem domains, such as recursivedescentparsers, where the datatypes are naturally mutually recursive. The most important basic example of...
Pull parsing treats the document as a series of items read in sequence using the iterator design pattern. This allows for writing of recursivedescent parsers...
A recursive neural network is a kind of deep neural network created by applying the same set of weights recursively over a structured input, to produce...
detection program, for analysing genetic recombination Recursivedescentparser, a type of top-down parser Remote Desktop Protocol, a Microsoft remote access...
grammars. GCC started out using Bison, but switched to a hand-written recursive-descentparser for C++ in 2004 (version 3.4), and for C and Objective-C in 2006...
GCC started out using LALR parsers generated with Bison, but gradually switched to hand-written recursive-descentparsers for C++ in 2004, and for C and...
of Perl 5.x regexes, but also allow BNF-style definition of a recursivedescentparser via sub-rules. The use of regexes in structured information standards...
whom?] The first C compiler, written by Dennis Ritchie, used a recursivedescentparser, incorporated specific knowledge about the PDP-11, and relied on...
Global Information