Ichor.Toolkit.Pratt (IchorRuntime v0.1.0)

Copy Markdown View Source

Precedence-climbing (Pratt) expression parsing over a runtime-mutable operator table -- extracted from a pattern already hand-rolled once, OpExprTest.Operators.climb/6 (test/support/opexpr_operators.ex), the worked example proving Grammar.IR.Custom/@native(...) rule- position dispatch works at all. That fixture only ever needed infix chains; this generalizes to prefix and postfix too, since those are exactly what Track 1's own motivating scenarios need (Prolog's op/3 supports fy/fx prefix and xf/yf postfix operators alongside infix ones, Haskell fixity declarations are infix-only but mixfix notation is not).

Completely IR-agnostic, like Ichor.Toolkit.Codegen/Result: pos, the stream, and the parsed value are all opaque to this module. peek_op returning {op_name, pos_after_op} rather than just op_name is deliberate, not incidental -- an operator token may sit behind skippable trivia (whitespace, comments; @native(...) nodes are opaque to Aether's own @skip splicing, so a caller has to handle this itself, same as climb/6 already did), so where the operator actually ends can't be assumed to be a fixed offset from where the search for it started. parse_primary is trusted to do its own leading-trivia handling for the same reason.

The infix/postfix ambiguity

An operator registered as both infix and postfix at once is genuinely ambiguous: after parsing a left operand and seeing that token, nothing short of looking further ahead can tell whether an infix use (expecting a right operand next) or a postfix use (expecting nothing) was meant. This is exactly why ISO Prolog's own op/3 forbids defining an atom as both infix and postfix -- the same operator serving as prefix and infix (unary vs. binary -) or prefix and postfix has no such problem, since prefix is only ever attempted before a left operand exists and infix/postfix only after, two mutually exclusive positions.

The table itself doesn't reject the combination -- it has no way to know at build time whether a caller will later supply the means to resolve it, since callbacks are only ever known at parse/4 call time, not baked into the table. Instead, parse/4 only raises when it actually encounters a token where both fixities are simultaneously viable at the current precedence: if callbacks includes can_start_operand?, it's consulted (does a valid operand start right after the operator? infix if so, postfix if not); if it's absent, parse/4 raises ArgumentError naming the operator, rather than silently misparsing one way or the other.

Summary

Types

assoc()
callbacks()
fixity()
op_name()
table()

Functions

infix(table, op_name, prec, assoc \\ :left)

Registers op_name as an infix operator at prec with associativity assoc (default :left).

new()

An empty operator table.

parse(table, pos, callbacks, min_prec \\ 0)

Parses one expression starting at pos, only accepting an infix/postfix operator whose precedence is at least min_prec (default 0 -- pass a table entry's own precedence, bumped per associativity, on the recursive call that parses an operator's own operand).

postfix(table, op_name, prec)

Registers op_name as a postfix operator at prec.

prefix(table, op_name, prec)

Registers op_name as a prefix operator at prec.

Types

assoc()

@type assoc() :: :left | :right | :none

callbacks()

@type callbacks() :: %{
  :peek_op => (term() -> {op_name(), term()} | nil),
  :parse_primary => (term() -> {:ok, term(), term()} | :fail),
  :build => (fixity(), op_name(), [term()] -> term()),
  optional(:can_start_operand?) => (term() -> boolean())
}

fixity()

@type fixity() :: :prefix | :infix | :postfix

op_name()

@type op_name() :: term()

table()

@type table() :: %{
  optional(op_name()) => %{
    optional(:prefix) => non_neg_integer(),
    optional(:infix) => {non_neg_integer(), assoc()},
    optional(:postfix) => non_neg_integer()
  }
}

Functions

infix(table, op_name, prec, assoc \\ :left)

@spec infix(table(), op_name(), non_neg_integer(), assoc()) :: table()

Registers op_name as an infix operator at prec with associativity assoc (default :left).

new()

@spec new() :: table()

An empty operator table.

parse(table, pos, callbacks, min_prec \\ 0)

@spec parse(table(), term(), callbacks(), non_neg_integer()) ::
  {:ok, term(), term()} | :fail

Parses one expression starting at pos, only accepting an infix/postfix operator whose precedence is at least min_prec (default 0 -- pass a table entry's own precedence, bumped per associativity, on the recursive call that parses an operator's own operand).

postfix(table, op_name, prec)

@spec postfix(table(), op_name(), non_neg_integer()) :: table()

Registers op_name as a postfix operator at prec.

prefix(table, op_name, prec)

@spec prefix(table(), op_name(), non_neg_integer()) :: table()

Registers op_name as a prefix operator at prec.