Re:Super Tiny Compiler
by userbinator on Thursday March 31, 2016 @07:33AM
(#11396360)
TDOP, Pratt, precedence-climbing, I think they're all referring to the same, if not extremely similar, method of using a loop in the main recursive function that compares precedences and decides whether to recurse or loop:
https://www.engr.mun.ca/~theo/Misc/exp_parsing.htm#climbing
http://javascript.crockford.com/tdop/tdop.html
They're definitely very simple, and can be derived by refactoring a recursive descent parser and observing that there's no need to make a chain of nested recursive calls to the right level when the function can be called directly to "jump" to the desired level. The simplicity is probably why it's been rediscovered several times and has different names.
TDOP and Pratt are exactly the same thing, Vaughan Pratt is the inventor, Top Down Operator Precedence is the name he gave to the algorithm. And TDOP never "recurses or loops" (the precedence tells it whether it should stop looping). Part of the interest is how object-oriented it is, the main parsing loop ("expression" in the Crockford article) just tells a token "parse yourself as prefix" or "parse yourself as infix preceded by (AST)"
Re:Super Tiny Compiler
by abecedarius on Thursday March 31, 2016 @01:53PM
(#11399106)
They're the same algorithm expressed in different styles: structured for precedence climbing, and as you say OO or 'data driven' for Pratt.
https://github.com/darius/sketchbook/blob/master/parsing/pre...
https://github.com/darius/sketchbook/blob/master/parsing/pra...
I'd suggest starting with a Top Down Operator Precedence ("Pratt") parser, they're beautiful magic for the working man, highly declarative and slightly mind-bending in that they seem so simple they shouldn't work, they make expressions with infix priority a joy to handle.