Recursive descent parser: Difference between revisions

Revision as of 12:48, 8 May 2020

Latest revision as of 16:00, 27 August 2025

(24 intermediate revisions by 17 users not shown)

Line 1:

{{short description|Algorithm}}

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.<ref>{{cite book | title=Recursive Programming Techniques | author=Burge, W.H. | year=1975 | isbn=0-201-14450-6 | url-access=registration | url=https://archive.org/details/recursiveprogram0000burg }}</ref>

{{More footnotes|date=February 2009}}

In [[computer science]], a '''recursive descent parser''' is a kind of [[top-down parsing|top-down parser]] built from a set of [[mutual recursion|mutually recursive]] procedures (or a non-recursive equivalent) where each such [[procedure (computer science)|procedure]] implements one of the [[Terminal and nonterminal symbols|nonterminals]] of the [[formal grammar|grammar]]. Thus the structure of the resulting program closely mirrors that of the grammar it recognizes.<ref>{{FOLDOC|Recursive+descent+parser}}</ref><ref>{{cite book | title=Recursive Programming Techniques | author=Burge, W.H. | year=1975 | publisher=Addison-Wesley Publishing Company | isbn=0-201-14450-6 | url-access=registration | url=https://archive.org/details/recursiveprogram0000burg }}</ref>

A ''predictive parser'' is a recursive descent parser that does not require backtracking.<ref name="Watson2017">{{cite book|last=Watson|first=Des|title=A Practical Approach to Compiler Construction|url=https://books.google.com/books?id=05B0DgAAQBAJ&printsec=frontcover#v=onepage&q=%22predictive%20parser%22&f=false|date=22 March 2017|publisher=Springer|isbn=978-3-319-52789-5}}</ref> 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.

A ''predictive parser'' is a recursive descent parser that does not require [[backtracking]].<ref name="Watson2017">{{cite book|last=Watson|first=Des|title=A Practical Approach to Compiler Construction|url=https://books.google.com/books?id=05B0DgAAQBAJ&printsec=frontcover#v=onepage&q=%22predictive%20parser+parser%22&f=false|date=22 March 2017|publisher=Springer|isbn=978-3-319-52789-5}}</ref> Predictive parsing is possible only for the class of [[LL parser|LL(''k'')]] grammars, which are the [[context-free grammarsgrammar]]s 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 grammarsgrammar]]s, 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 rule (formal languages)|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.

Recursive descent with backtracking is a technique that determines which [[Production rule (formal languages)|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.

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|date=February 2018}} either for an LL(''k'') language or using an alternative parser, such as [[LALR parser|LALR]] or [[LR parser|LR]]. This is particularly the case if a grammar is not in [[LL parser|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.

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.<ref>{{cite book|last1=Aho|first1=Alfred V.|last2=Sethi|first2=Ravi|last3=Ullman|first3=Jeffrey|authorlink1=Alfred V. Aho|authorlink3=Jeffrey Ullman|title=Compilers: Principles, Techniques and Tools|url=https://archive.org/details/compilers00ahoa|url-access=limited|date=1986|publisher=Addison Wesley|page=[https://archive.org/details/compilers00ahoa/page/n193 183]|edition=first}}</ref>

==Example parser==

The following [[Extended Backus–Naur Form|EBNF]]-like [[formal grammar|grammar]] (for [[Niklaus Wirth]]'s [[PL/0]] programming language, from ''[[Algorithms + Data Structures = Programs]]'') is in [[LL parser|LL(1)]] form:

<sourcesyntaxhighlight lang="ebnf">

program = block "." .

block =

["const" ident "=" numnumber {"," ident "=" numnumber} ";"]

["var" ident {"," ident} ";"]

{"procedure" ident ";" block ";"} statement .

Line 39 ⟶ 42:

| number

| "(" expression ")" .

</syntaxhighlight>

</source>

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

Line 47 ⟶ 50:

What follows is an implementation of a recursive descent parser for the above language in [[C (programming language)|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 current symbol from the input, and the function ''nextsym'', which updates ''sym'' when called.

The implementations of the functions ''nextsym'' and ''error'' are omitted for simplicity.

<sourcesyntaxhighlight lang="c">

typedef enum {ident, number, lparen, rparen, times, slash, plus,

minus, eql, neq, lss, leq, gtr, geq, callsym, beginsym, semicolon,

Line 177 ⟶ 180:

expect(period);

}

</syntaxhighlight>

</source>

== Examples ==

Line 187 ⟶ 190:

*[[Spirit Parser Framework]] – a C++ recursive descent parser generator framework requiring no pre-compile step

*[[parboiled (Java)]] – a recursive descent [[Parsing expression grammar|PEG]] parsing library for [[Java (programming language)|Java]]

The C++ front-end of the [[Clang]] compiler contains a hand-written parser based on the recursive-descent parsing algorithm. <ref>How Clang handles the type / variable name ambiguity of C/C++

https://eli.thegreenplace.net/2012/07/05/how-clang-handles-the-type-variable-name-ambiguity-of-cc/</ref>

==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

*[[Tail recursive parser]] – a variant of the recursive descent parser

*[[Recursive ascent parser]]

*[[Tail recursive parser]] – a variant of the recursive descent parser

* [http://sourceforge.net/projects/bnf2xml/ bnf2xml] Markup input with XML tags using advanced BNF matching. (a top town LL recursive parser, front to back text, no compiling of lexor is needed or used)

* [https://metacpan.org/module/Parse::RecDescent Parse::RecDescent]: A versatile recursive descent [[Perl]] module.

* [http://pyparsing.wikispaces.com/ pyparsing]: A versatile [[Python (programming language)|Python]] recursive parsing module that is not recursive descent ([https://mail.python.org/pipermail/python-list/2007-November/416678.html python-list post]).

* [http://jparsec.codehaus.org/ Jparsec] a Java port of the Haskell [[Parsec (parser)|Parsec]] module.

==References==

{{Reflist}}

===General references===

{{reflist}}

{{FOLDOC}}

* ''[[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}}.

Line 210 ⟶ 213:

==External links==

*[httphttps://compilers.iecc.com/crenshaw/ Jack W. Crenshaw: ''Let's Build A Compiler'' (1988-1995)], in [[Pascal (programming language)|Pascal]], with [[assembly language]] output, using a "keep it simple" approach

*[http://www.mollypages.org/page/grammar/index.mp Introduction to Parsing] - an easy to read introduction to parsing, with a comprehensive section on recursive descent parsing

*[http://teaching.idallen.com/cst8152/98w/recursive_decent_parsing.html How to turn a Grammar into C code] - a brief tutorial on implementing recursive descent parser

*[http://lukaszwrobel.pl/blog/math-parser-part-3-implementation Simple mathematical expressions parser] in [[Ruby (programming language)|Ruby]]

*[http://effbot.org/zone/simple-top-down-parsing.htm Simple Top Down Parsing in Python]

*[http://compilers.iecc.com/crenshaw/ Jack W. Crenshaw: ''Let's Build A Compiler'' (1988-1995)], in [[Pascal (programming language)|Pascal]], with [[assembly language]] output, using a "keep it simple" approach

*[http://www.cs.nott.ac.uk/~gmh/pearl.pdf Functional Pearls: Monadic Parsing in Haskell]

{{Parsers}}