difference between bottom-up parser Precedence climbing and top-down parser Pratt parsing - Stack Overflow

admin管理员组

文章数量:1391937

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?

本文标签： difference between bottomup parser Precedence climbing and topdown parser Pratt parsingStack Overflow