Content deleted Content added
Rust's raw string literals are an example of a context-sensitive language that can be parsed left to right by a (tail-)recursive descent parser that is allowed to carry an integer in the stack frames, so the restriction to LL(1) assumes that recursive descent stack frames have a finite number of states Tag: Reverted |
|||
| (6 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
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]].
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==
*[
▲*[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
{{Parsers}}
| |||