computer science

Recursive descent parser

Recursive descent parser is a computer science topic covered in the lgStudy science library. This page brings together a partial reference excerpt, illustrations, worked examples, real-world applications and a short study plan, so you can understand Recursive descent parser rather than just read about it. In short: 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.

Key takeaways

Recursive descent parser belongs to computer science; place it in that map before memorising details.
Learn the definition first, then one example that makes the definition concrete.
Connect Recursive descent parser to a quantity you can measure, compute or draw — that is where exam questions come from.
Reproduce the core statement of Recursive descent parser from memory before moving on to harder problems.

Reference excerpt

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. A predictive parser is a recursive descent parser that does not require backtracking. 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, 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.

Example parser The following EBNF-like grammar (for Niklaus Wirth's PL/0 programming language, from Algorithms + Data Structures = Programs) is in LL(1) form:

Terminals are expressed in quotes. Each nonterminal is defined by a rule in the grammar, except for ident and number, which are assumed to be implicitly defined.

C implementation What follows is an implementation of a recursive descent parser for the above language in C. The parser reads in source code, and exits with an error message if the code fails to parse, exiting silently if the code parses correctly. Notice how closely the predictive parser below mirrors the grammar above. There is a procedure for each nonterminal in the grammar. Parsing descends in a top-down manner until the final nonterminal has been processed. The program fragment depends the functions peeksym, which peeks at the current symbol; consumesym, which consumes the symbol to move to the next; and error, which displays an error message. These functions are assumed to be provided by the lexer.

Examples Some recursive descent parser generators:

TMG – an early compiler-compiler used in the 1960s and early 1970s JavaCC Coco/R ANTLR Spirit Parser Framework – a C++ recursive descent parser generator framework requiring no pre-compile step parboiled (Java) – a recursive descent PEG parsing library for Java The C++ front-end of the Clang compiler contains a hand-written parser based on the recursive-descent parsing algorithm.

See also Parser combinator – a higher-order function used in combinatory parsing, a method of factoring recursive descent parser designs Parsing expression grammar – another form representing recursive descent grammar Recursive ascent parser Tail recursive parser – a variant of the recursive descent parser

References

General references Compilers: Principles, Techniques, and Tools, first edition, Alfred V Aho, Ravi Sethi, and Jeffrey D Ullman, in particular Section 4.4. Modern Compiler Implementation in Java, Second Edition, Andrew Appel, 2002, ISBN 0-521-82060-X. Recursive Programming Techniques, W.H. Burge, 1975, ISBN 0-201-14450-6 Crafting a Compiler with C, Charles N Fischer and Richard J LeBlanc, Jr, 1991, ISBN 0-8053-2166-7. Compiling with C# and Java, Pat Terry, 2005, ISBN 0-321-26360-X, 624 Algorithms + Data Structures = Programs, Niklaus Wirth, 1975, ISBN 0-13-022418-9 Compiler Construction, Niklaus Wirth, 1996, ISBN 0-201-40353-6

External links Jack W. Crenshaw: Let's Build A Compiler (1988-1995), in Pascal, with assembly language output, using a "keep it simple" approach

Worked examples

Example 1 — a first encounter with Recursive descent parser

Start with the simplest possible case. Write down what Recursive descent parser claims or describes in one sentence, then invent the smallest concrete situation in which that sentence is true. In computer science, the smallest case is usually a single object, a single equation or a single measurement. Check that every symbol or term in your sentence has a meaning in that case.

Example 2 — changing one variable

Take the situation from Example 1 and change exactly one quantity: double it, halve it, or set it to zero. Predict what should happen to Recursive descent parser before you calculate. Comparing your prediction with the result is the fastest way to find out whether you understand the idea or only the words.

Example 3 — an exam-style question

Typical questions about Recursive descent parser ask you to (a) state it precisely, (b) apply it to given data, and (c) explain a limitation. Practise writing all three answers in under five minutes; the third part is what separates a full-mark answer from an average one.

Applications of Recursive descent parser

In research: Recursive descent parser appears in computer science research whenever the underlying quantities have to be modelled precisely. Papers usually cite it as a starting assumption and then explore where it breaks down.
In technology and industry: Engineering practice reuses Recursive descent parser in design rules, simulations and safety margins. Knowing the idea lets you read a specification sheet and understand why the numbers look the way they do.
In the classroom: Recursive descent parser is common in secondary-school and first-year university syllabi. It links to neighbouring topics Parsing algorithms, so understanding it makes those chapters shorter.
In everyday life: Look for Recursive descent parser outside the textbook — in sport, cooking, traffic, electronics or the sky above you. An example you found yourself is remembered far longer than one you were given.

Affiliate

Preply — study more efficiently by working with a personal tutor. 50% off.

How to study Recursive descent parser in 20 minutes

Read the reference excerpt below once, without taking notes.
Close the page and write down what Recursive descent parser means in your own words.
Compare your version with the excerpt and mark what you missed.
Work through the three examples above with pen and paper.
Explain Recursive descent parser out loud to somebody else — or to Teacher Smith in the lgStudy chat.

Frequently asked questions

What is Recursive descent parser in simple terms?

Why does Recursive descent parser matter?

Because it connects several computer science ideas at once: it gives you a definition you can apply, a quantity you can calculate, and a way to check whether a result is plausible.

How should I study Recursive descent parser?

Read the excerpt, restate it from memory, then work through the examples and applications listed on this page. The five-step study plan above takes about twenty minutes.

What does this page cover?

It gives you a compact reference excerpt plus original lgStudy explanations, examples, applications and study material on Recursive descent parser.