Skip to the content ForoHackers
Log inJoin

Pratt parsing: operator precedence in twenty lines

CompilersInterpreters and virtual machinesLanguage design
#1146 · polyglot_parser · · Report

If you are writing a hobby language, you will hit the expression problem early: 1 + 2 * 3 must parse as 1 + (2 * 3), and 2 ^ 3 ^ 2 must group to the right. Many people reach for a parser generator or a stack of grammar rules, one per precedence level. There is a smaller way, usually called Pratt parsing or precedence climbing: give every operator a pair of binding powers and recurse.

BP = {"+": (1, 2), "-": (1, 2), "*": (3, 4), "/": (3, 4), "^": (6, 5)}

def parse(tokens, min_bp=0):
    tok = tokens.pop(0)
    if tok == "(":
        lhs = parse(tokens)
        tokens.pop(0)              # the ")"
    else:
        lhs = int(tok)
    while tokens and tokens[0] in BP:
        left, right = BP[tokens[0]]
        if left < min_bp:
            break
        op = tokens.pop(0)
        rhs = parse(tokens, right)
        lhs = (op, lhs, rhs)
    return lhs

print(parse("1 + 2 * 3".split()))   # ('+', 1, ('*', 2, 3))
print(parse("2 ^ 3 ^ 2".split()))   # ('^', 2, ('^', 3, 2))
print(parse("1 - 2 - 3".split()))   # ('-', ('-', 1, 2), 3)

The trick is the two numbers. If left < right, the operator is left-associative (the right side binds a bit tighter, so the next operator of the same level will not be swallowed). If left > right, it is right-associative. min_bp says how strongly the thing to my left is already pulling on my left operand.

Prefix operators, function calls and ternaries all fit in the same loop with a few more lines. The linguist in me finds it beautiful that precedence is just a number and not a grammar.

#1903 · lambda_llama · · Report

I did this exercise in Haskell once and the parser fit on a screen with the tokens as a list pattern match. Pratt's idea survives any language: precedence is data, not grammar structure.

#1904 · quiet_quine · · Report

Add error handling by checking tokens is non-empty before each pop. Without it, parse(["1", "+"]) dies with an IndexError instead of a message.

#1905 · polyglot_parser · · Report

Good catch, I cut it for space. A real version wants a token class with a position, so the message can say where the expression ended too early.

Log in or join to reply.