5 ms·

This 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.en

by ob 4y ago

This 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 4y ago
Pratt 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 4y ago
  Pratt 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 4y ago
    Precedence parsing can be derived from a recursive descent, taking an iterative approach
- chubot 4y 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.

by ob 4y ago

This 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 4y ago

Pratt 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 4y ago
Pratt 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 4y ago
  Precedence parsing can be derived from a recursive descent, taking an iterative approach
chubot 4y 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.