Recursive descent parser: Difference between revisions

Revision as of 02:49, 6 November 2023

Latest revision as of 16:00, 27 August 2025

(7 intermediate revisions by 5 users not shown)

Line 2:

{{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&q=%22predictive+parser%22|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 grammar]]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 grammar]]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]].

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

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