4 ms·
Top Down Operator Precedence (1971) [pdf]
- dang 7y agoA thread from 2015: https://news.ycombinator.com/item?id=9599969 https://news.ycombinator.com/item?id=9599969 2010: https://news.ycombinator.com/item?id=1027417 https://news.ycombinator.com/item?id=1027417
- drallison 7y agoThe only way to fly....
- nly 7y agoPrecedence climbing can be derived intuitively from recursive descent: https://www.engr.mun.ca/~theo/Misc/exp_parsing.htm#more_climbing https://www.engr.mun.ca/~theo/Misc/exp_parsing.htm#more_clim... ... and "Pratt Parsing and Precedence Climbing Are the Same Algorithm" 2016): https://www.oilshell.org/blog/2016/11/01.html https://www.oilshell.org/blog/2016/11/01.html and these techniques, despite originating in the 70s, are still the state of the art in most production programming language parsers
- cbarrick 7y agoThat article "Pratt Parsing and Precedence Climbing Are the Same Algorithm" is excellent. Though Andy has a later article where he clarifies that Precedence Climbing is a special case and is more popular than general Pratt Parsing because of it's simplicity [1]. [1] "Precedence Climbing is Widely Used" http://www.oilshell.org/blog/2017/03/30.html http://www.oilshell.org/blog/2017/03/30.html