In computer science and linguistics, parsing, or, more formally, syntactic analysis, is the process of analyzing a sequence of lexical analysis#Token to determine their grammatical structure with respect to a given formal grammar.... built from a set of mutually-recursive
Mutual recursion
Mutual recursion is a form of recursion where two mathematical or computational functions are defined in terms of each other.For instance, consider two functions even? and odd? defined as follows:... procedures (or a non-recursive equivalent) where each such procedure
Procedure
A procedure is a specified series of actions, acts or operations which have to be executed in the same manner in order to always obtain the same result under the same circumstances .... usually implements one of the production rules of the grammar
Formal grammar
In formal language theory, grammars, also called formal grammars or generative grammars, are a formalism used to describe formal languages – i.e.... . 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)
LL parser
An LL parser is a Top-down parsing parser for a subset of the context-free grammars. It parses the input from Left to right, and constructs a Context-free grammar#Derivations and syntax trees of the sentence .... 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.
Discussion
Ask a question about 'Recursive descent parser'
Start a new discussion about 'Recursive descent parser'
In computer science and linguistics, parsing, or, more formally, syntactic analysis, is the process of analyzing a sequence of lexical analysis#Token to determine their grammatical structure with respect to a given formal grammar.... built from a set of mutually-recursive
Mutual recursion
Mutual recursion is a form of recursion where two mathematical or computational functions are defined in terms of each other.For instance, consider two functions even? and odd? defined as follows:... procedures (or a non-recursive equivalent) where each such procedure
Procedure
A procedure is a specified series of actions, acts or operations which have to be executed in the same manner in order to always obtain the same result under the same circumstances .... usually implements one of the production rules of the grammar
Formal grammar
In formal language theory, grammars, also called formal grammars or generative grammars, are a formalism used to describe formal languages – i.e.... . 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)
LL parser
An LL parser is a Top-down parsing parser for a subset of the context-free grammars. It parses the input from Left to right, and constructs a Context-free grammar#Derivations and syntax trees of the sentence .... 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)
LL parser
An LL parser is a Top-down parsing parser for a subset of the context-free grammars. It parses the input from Left to right, and constructs a Context-free grammar#Derivations and syntax trees of the sentence .... grammars therefore exclude all ambiguous grammars, as well as all grammars that contain left recursion
Left recursion
In computer science, left recursion is a special case of recursion.In terms of context-free grammar, a non-terminal r is left-recursive if the left-most symbol in any of r?s ?alternatives? either immediately or through some other non-terminal definitions rewrites to r again.... . 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)
LL parser
An LL parser is a Top-down parsing parser for a subset of the context-free grammars. It parses the input from Left to right, and constructs a Context-free grammar#Derivations and syntax trees of the sentence .... grammar.) A predictive parser runs in linear time
Linear time
In computational complexity theory, an algorithm is said to take linear time, or Big O notation time, if the asymptotic upper bound for the time it requires is proportional to the size of the input, which is usually denoted n.... .
Recursive descent with backup is a technique that determines which production to use by trying each production in turn. Recursive descent with backup is not limited to LL(k)
LL parser
An LL parser is a Top-down parsing parser for a subset of the context-free grammars. It parses the input from Left to right, and constructs a Context-free grammar#Derivations and syntax trees of the sentence .... grammars, but is not guaranteed to terminate unless the grammar is LL(k)
LL parser
An LL parser is a Top-down parsing parser for a subset of the context-free grammars. It parses the input from Left to right, and constructs a Context-free grammar#Derivations and syntax trees of the sentence .... . Even when they terminate, parsers that use recursive descent with backup may require exponential time
Exponential time
In computational complexity theory, exponential time is the computation time of a problem where the time to complete the computation, m, is bounded by an exponential function of the problem size, n.... .
Although predictive parsers are widely used, programmers often prefer to create LR
LR parser
In computer science, an LR parser is a parser for context-free grammars that reads input from Left to right and produces a Context-free grammar#Derivations and syntax trees.... or LALR
LALR parser
In computer science, a lookahead LR parser or LALR parser is a specialized form of LR parser that can deal with more context-free grammars than Simple LR parser parsers.... parsers via parser generators without transforming the grammar into LL(k)
LL parser
An LL parser is a Top-down parsing parser for a subset of the context-free grammars. It parses the input from Left to right, and constructs a Context-free grammar#Derivations and syntax trees of the sentence .... form.
Some authors define recursive descent parsers as the predictive parsers. Other authors use the term more broadly, to include backed-up recursive descent.
Grammar is the field of linguistics that covers the conventions governing the use of any given natural language. It includes morphology and syntax, often complemented by phonetics, phonology, semantics, and pragmatics.... (for Niklaus Wirth
Niklaus Wirth
Niklaus Emil Wirth is a Switzerland computer science, best known for designing several programming languages, including Pascal , and for pioneering several classic topics in software engineering.... 's PL/0
PL/0
There are at least two programming languages known as PL/0. One is a subset of IBM's general-purpose programming language programming language PL/I.... programming language, from Algorithms + Data Structures = Programs
Algorithms + Data Structures = Programs
Algorithms + Data Structures = Programs is a book written by Niklaus Wirth covering some of the fundamental topics of computer programming. The book was published by Prentice-Hall in 1976 and is one of the most influential computer science books of the time.... ) is in LL(1)
LL parser
An LL parser is a Top-down parsing parser for a subset of the context-free grammars. It parses the input from Left to right, and constructs a Context-free grammar#Derivations and syntax trees of the sentence .... form (for simplicity, ident and number are assumed to be terminals):
Terminals are expressed in quotes (except for ident
and number). Each nonterminal is defined by a rule in the grammar.
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 on a global variable, sym, which contains the next symbol from the input, and the function getsym, which updates sym when called.
The implementations of the functions getsym and error are omitted for simplicity.
typedef enum Symbol;
Symbol sym;
void getsym(void);
void error(const char msg[]);
void expression(void);
int accept(Symbol s)
int expect(Symbol s)
void factor(void)
void term(void)
void expression(void)
void condition(void)
void statement(void)
void block(void)
void program(void)
Implementation in functional languages
Recursive descent parsers are particularly easy to implement in functional languages such as Haskell
Haskell (programming language)
Haskell is a standardized, purely functional programming language with non-strict programming language, named after logician Haskell Curry. The goals of the language are described as:... or ML
ML programming language
ML is a general-purpose functional programming language developed by Robin Milner and others in the late 1970s at the University of Edinburgh, whose syntax is inspired by ISWIM.... .
JavaCC is an open source parser generator for the Java . JavaCC is similar to Yacc in that it generates a parser for a formal grammar provided in Extended Backus-Naur form notation, except the output is Java source code.... - a recursive descent parser generator
Coco/R is a compiler generator that takes an L-attributed grammar EBNF grammar of a source language and generates a scanner and a parser for that language.... - a recursive descent parser generator
In computer based language recognition, ANother Tool for Language Recognition is the name of a parser generator that uses LL parser parsing. ANTLR is the successor to the Purdue Compiler Construction Tool Set , first developed in 1989, and is under active development.... - a recursive descent parser generator
A parsing expression grammar, or PEG, is a type of analytic grammar formal grammar that describes a formal language in terms of a set of rules for recognizing string in the language.... - another form representing recursive descent grammar
The Spirit Parser Framework is an object oriented Recursive descent parser parser generator framework implemented using template metaprogramming techniques.... - a C++ recursive descent parser generator framework requiring no pre-compile step
Tail recursive parsers are derived from the more common Recursive descent parsers. Tail recursive parsers are commonly used to parse left recursive grammars.... - a variant of the recursive descent parser
External links
- an easy to read introduction to parsing, with a comphrensive section on recursive descent parsing
- a brief tutorial on implementing recursive descent parser
- The tool that allows parsing and evaluating mathematical expressions from within Java program
, in Pascal, with assembler output, using a "keep it simple" approach
