Binding Power

Write an expression grammar the way you would say it, and the parse comes out wrong: 2 * 3 + 5 groups by how the recursion happened to fall rather than by what arithmetic means. Binding power is how you tell APM what the operators are worth.

A rule bound to a table is parsed by a precedence loop instead of a greedy tail. Left recursion in the rule is fine — write it directly.

The table

Each operator gets two numbers: a left binding power and a right binding power. Entries end with ;.

bindpow bp {
    "or"  : (10, 11) ;
    "and" : (20, 21) ;
    "=="  : (30, 31) ;
    "<"   : (40, 41) ;
    "+"   : (50, 51) ;
    "-"   : (50, 51) ;
    "*"   : (60, 61) ;
    "/"   : (60, 61) ;
    "not" : (0, 70) ;
};

Higher numbers bind tighter, so * takes its operands before + gets a look.

Associativity is the gap, not a keyword

There is no left or right to write. The relationship between an operator’s two numbers is its associativity.

In APM, an operator grabs what is to its left when the left number is high enough to beat what is already holding it, and it keeps going to the right while the right number stays above what follows. So:

Written	Means	Because
`r = l + 1`	left-associative — `a - b - c` is `(a - b) - c`	the right side binds one step tighter, so the second `-` cannot reach back and take `b` away from the first
`r = l - 1`	right-associative — `a ^ b ^ c` is `a ^ (b ^ c)`	the right side binds one step looser, so the second `^` wins `b`
`r = l`	left-associative, the same as `l + 1` in practice	a tie goes to whoever got there first

The gap is always one step. Bigger gaps between the two numbers of the same operator buy nothing; it is the gap between different operators that sets precedence.

Prefix and postfix are a zero

A side that binds nothing is 0, and that is also how the kind is written:


`(0, r)`	prefix — `not a`
`(l, 0)`	postfix — `a++`
`(l, r)`	infix — `a + b`

The slot is genuinely dead, so a 0 can never be mistaken for a real power. A prefix arm is only ever matched where an operand is expected, where nothing reads its left; a postfix arm folds immediately, so nothing reads its right.

What decides which kind an occurrence is is the grammar — where the alternative sits — not what the table calls it. The table only supplies the numbers.

Binding a rule to a table

feat {"bind": <table>} in front of the definition – feat always goes in front of what it configures, an action or a semvar:

feat {"bind": bp} expr := atom
      | expr . "or"  . expr
      | expr . "and" . expr
      | expr . "=="  . expr
      | expr . "<"   . expr
      | expr . "+"   . expr
      | expr . "-"   . expr
      | expr . "*"   . expr
      | expr . "/"   . expr
      | "not" . expr
      ;

atom  := number | string | ident | group;
group := "(" . expr . ")";

The first alternative that is not an operator arm is the operand — here atom. The rest are the arms, and each must name an operator the table declares.

A feat binding applies to the action itself, so every call site parses it that way. It is the right choice when the rule is an expression rule and there is no other way you would ever want it read.

The tree a bound rule makes

Without a map, a bound rule wraps each fold in a node of its own and the operator sits beside its operands:

expr "2 + 3 * 4"
├── atom "2"
├── text "+"
└── expr "3 * 4"

A map on the rule puts the operator on top, which is the shape every hand-written expression parser produces:

feat {"bind": bp} expr :=
    ( atom
    | 'l'expr . "+" . 'r'expr
    | 'l'expr . "*" . 'r'expr )
 -> ( atom
    | "+": ('l' 'r')
    | "*": ('l' 'r') );

text "+"
├── atom "2"
└── text "*"
    ├── atom "3"
    └── atom "4"

The two labels name the operands. They are not units of the arm – the loop supplies them – which is why they are the one place a label means something the body does not contain.

An arm may carry more than its operator

A ternary matches its middle operand inside the arm, and a subscript matches a whole expression between brackets. Both are ordinary units, and both keep what the map says about them:

bindpow post { "?" : (4, 3) ; "[" : (50, 0) ; "+" : (20, 21) ; };

feat {"bind": post} e :=
    ( num
    | 'l'e . "+" . 'r'e
    | 'c'e . "?" . 'q'e . ":" . 'x'e
    | 'h'e . "[" . 'i'e . "]" )
 -> ( num
    | "+": ('l' 'r')
    | "?": ('c' 'q' 'x')
    | "[": ('h' 'i') );

1+2?3:4                  1+2[3]
text "?"                 text "+"
├── text "+"             ├── num "1"
├── e "3"                └── text "["
└── num "4"                  ├── num "2"
                             └── e "3"

A unit the map does not name makes nothing, here as everywhere – which is what drops the : and the ].

Note

['l'] on an operand is wrong, and quietly so. An operand is either a plain unit or an earlier fold; ascend cannot tell them apart, so it would lift an inner fold’s children out and flatten the nesting the powers just built.

Binding at the call site

The other way round is to leave the rule unbound and pick the table where you call it, with table::-rule:

number = <0:9>+;

bindpow bp {
    "+" : (50, 51) ;
    "*" : (60, 61) ;
};

expr := number | expr . "+" . expr | expr . "*" . expr;

top := bp::-expr;   # parse expr under bp, here

Over 2 + 3 * 4 that gives 2 + (3 * 4).

Use this when the same rule should be read with different precedences in different places, or when you want the grammar to stay readable as a plain recursive rule and the precedence to be a decision made elsewhere.

Important

Every operator the rule writes must appear in the table, and every operator in the table must appear in the rule. An operator that is not declared simply ends the expression, which would silently truncate a parse rather than fail it — so it is refused when the grammar is validated.