I encountered with this problem while reading about Precedence climbing and Pratt parsing. This may be duplicate with this QA but that doesn't say much about Precedence climbing and Pratt parsing. The relation of these 2 parsing methods is shown in this wikipedia reference link.
To accommodate operators like these and additional prefix operators in a modular way, we can use Pratt parsing.
We'll rewrite the E procedure to use commands. The old E is
E(p) is precondition 0 ≤ p var t := P var r := +inf loop const l := next exit unless p≤prec(next)≤r consume if isBinary(l) then const y := E( rightPrec(l) ) t := mknode(binary(l), t, y) else t := mknode(postfix(l), t) r := nextPrec(l) return t
The new E is
E(p) is precondition 0 ≤ p var t := P var r := +inf loop const l := next const c := leftComm[l] exit unless p ≤ c.LBP ≤ r consume t := c.LeD( t, l ) r := c.NBP return t
As you can see, they share almost the same idea but Pratt parsing uses one "semantic code" idea (e.g. c.LeD( t, l )
above) which is related with OOP. That makes the program clearer.
we assign to each semantic token a program called its semantic code
But wikipedia says that Precedence climbing is one bottom-up parser while Pratt parsing is top-down because it is based on recursive descent ("based on recursive descent" is said in the above paper link). So I am a bit confused.
I tried to convince myself as the following:
For Precedence climbing, it will first iterate through child nodes with const y := E( rightPrec(l) )
etc (Shift step) and then do that for the parent by t := mknode(binary(l), t, y)
(Reduce step). So it is bottom-up.
Although Pratt parsing follows the same node traversal order as Precedence climbing, it is recursive descent due to its semantic code encapsulation. "Recursive descent" parser is considered as top-down parser due to that it considers the root procedure first and then child ones.
a recursive descent parser is a kind of top-down parser built from a set of mutually recursive procedures (or a non-recursive equivalent) where each such procedure implements one of the nonterminals of the grammar.
Q:
Is the above convince description fine to classify Precedence climbing and Pratt parsing? IMHO "top-down parser" is more about one design technique but not node traversal order in AST, at least for recursive descent parser. Is it that case?