Pratt Parsing

• To eliminate Left Recursion
  • rewrite the grammar to eliminate the left recursion. 
  • for a handwritten parser, break away with a pure recursive paradigm and using a loop:

fn sum(p: &mut Parser) {
    int(p);
    while p.eat(PLUS) {
        int(p);
    }
}

Pratt parsing uses both loops and recursion:

Pratt Parsing

• Firstly parse the lhs, then use a loop to parse the rhs until we find an operator whose left_bp > prev_op_right_bp
• Binding Power: left and right number for operator

a   +   b   *   c   *   d   +   e
  1   2   3   4   3   4   1   2

Links

• Simple but Powerful Pratt Parsing