3 ms·
Parsing Expressions by Recursive Descent (1999)
- ob 5y agoThis is a special case of Pratt parsing (the author wrote another article about it later on: https://www.engr.mun.ca/~theo/Misc/pratt_parsing.htm https://www.engr.mun.ca/~theo/Misc/pratt_parsing.htm)
- nly 5y agoPratt parsing, precedence climbing and recursive descent are all the same algorithm. https://www.oilshell.org/blog/2016/11/01.html https://www.oilshell.org/blog/2016/11/01.html
- jwmerrill 5y agoPratt parsing and precedence climbing are the same or very similar, but they are not the same as recursive descent (and the linked article does not claim this).
- nly 5y agoPrecedence parsing can be derived from a recursive descent, taking an iterative approach
- chubot 5y ago(author here) I generally think of Pratt parsing/precedence climbing as a "variant" of recursive descent. But there are expression parsers in GNU expr and bash that use recursive descent but do NOT use pratt parsing/precedence climbing. They make "extra" calls based on precedence levels encoded in a "grammar". (That is actually mentioned in the intro to the article.) I clarified this a bit here: Precedence Climbing is Widely Used http://www.oilshell.org/blog/2017/03/30.html http://www.oilshell.org/blog/2017/03/30.html I guess I would say the terminology is still kinda confusing. If you consider Pratt parsing and precedence climbing are the same, there are still at least 3 distinct ways to parse expressions, all found in working code. Which one you use doesn't really matter once it's working :) The plain recursive descent style is less efficient in theory, and somewhat longer. But I doubt it would show up in a profile of any real system. The "single recursive function" style of "precedence climbing" does appear to pretty popular, so that's why I wrote the followup post. It's the same algorithm but written in a common coding style.
- barrkel 5y agoI first encountered operator precedence parsing - the climbing algorithm - in the source of the Delphi compiler, which has a comment at the top dating it from 1990. That compiler was originally written by Peter Sollich.
- Theo-Norvell 5y agoThat’s interesting. The history goes back a bit farther. As far as I can tell the first use was in the BCPL compiler, which was written by Martin Richards in late 1960s and early 70s. Vaughn Pratt’s work was also in the early 70s. See the article in the OP for references.