Foundationপ্রথম নীতি থেকে
LEVEL 5 · Compilers

Pratt Parser

প্র্যাট পার্সার

Top-down operator-precedence parsing — প্রতিটা token-এ binding power assign করে একটা লুপেই সব precedence/associativity handle।

also: top-down operator-precedence parsing

Recursive-descent-এর precedence-tower-কে table-এ নামিয়ে আনে:

def expr(min_bp=0):
    lhs = nudge()                      # prefix/primary
    while lbp(peek()) >= min_bp:
        op = advance()
        lhs = led(op, lhs, expr(rbp(op)))
    return lhs
  • lbp < rbp = left-assoc, lbp > rbp = right-assoc — সংখ্যা জোড়াই associativity
  • Nudge (prefix position) বনাম led (infix position) আলাদা handler — postfix/call সহজে ঢোকে
  • Vaughan Pratt, 1973 — “Top Down Operator Precedence”; Rust, Go, TypeScript-এর parser-এ Pratt-family logic