Pratt Parser

AXSLC uses a Pratt parser (also known as top-down operator precedence parsing) for expression parsing.

Algorithm

The core function is:

NodeID Parser::parse_expr(int min_bp);

The algorithm works as follows:

1. Parse a prefix (literal, identifier, unary prefix, grouped expression, type constructor)
2. Enter a loop that repeatedly:
   • Peeks the next token
   • Looks up its left binding power (left_binding_power(op))
   • If the left binding power is negative or not greater than min_bp, stops
   • Otherwise consumes the operator and parses the right-hand side with a new minimum binding power

This naturally handles precedence and associativity without a grammar table.

Parsing Example Flow

Result: a + (b * c) with correct precedence

Binding Power Formula

Precedence levels are integer constants. Each level maps to a pair of binding powers:

#define BINDING_POWER_L(n)  ((n) * 2 - 1)   // left BP
#define BINDING_POWER_R(n)  ((n) * 2)        // right BP

Left-Associative Operators

For left-associative operators, right_binding_power = BINDING_POWER_R(n).

Since BINDING_POWER_R(n) > BINDING_POWER_L(n), a new operator at the same level will not be consumed into the current right-hand parse, producing left-to-right association.

Example: a + b + c is parsed as (a + b) + c

Right-Associative Operators

For right-associative operators (assignments, ternary), the right binding power used when parsing the RHS is BINDING_POWER_R(PRECEDENCE_ASSIGN) - the same as the left BP of assignment.

This means another assignment at the same level will be absorbed, producing right-to-left association.

Example: a = b = c is parsed as a = (b = c)

Precedence Table

Level	Name	Operators	Associativity
1	ASSIGN	= += -= *= /= %= &= `	=^=<<=>>=`
2	TERNARY	?:	Right
3	LOGICAL_OR	`
4	LOGICAL_AND	&&	Left
5	BIT_OR	`	`
6	BIT_XOR	^	Left
7	BIT_AND	&	Left
8	EQUALITY	== !=	Left
9	RELATIONAL	< > <= >=	Left
10	SHIFT	<< >>	Left
11	ADDITIVE	+ -	Left
12	MULT	* / %	Left
14	UNARY (prefix)	! ~ - + ++ --	Right (prefix)
15	POSTFIX	++ -- [ . (	Left

TIP

Level 13 is intentionally absent. This gap between MULT (12) and UNARY (14) ensures prefix unary operators bind tighter than any binary operator.

Precedence Hierarchy

Special Infix Handling

Some infix positions have dedicated parsing logic rather than going through right_binding_power:

Ternary ?:

Parses then with min_bp=0, then else with BINDING_POWER_R(TERNARY) - 1 to allow right-associative nesting.

// a ? b : c ? d : e
// parsed as: a ? b : (c ? d : e)

Postfix ++ and --

Creates a UnaryExpr with prefix=false:

x++   // UnaryExpr { op: ++, operand: x, prefix: false }

Subscript [

Parses a full expression for the index, then expects ]:

array[expr]

Field Access .

Calls expect_name() for the field identifier; produces FieldExpr:

object.field
vector.xyz

Call (

If the callee is an IdentifierExpr not in the declared set, it is promoted to UnresolvedRef before building CallExpr:

unknown_function(arg1, arg2)
// Creates: CallExpr { callee: UnresolvedRef("unknown_function"), args: [...] }

The Declared Set

The parser maintains a m_declared set of known identifiers. It is pre-seeded in the constructor with 70+ GLSL built-in function names:

radians, degrees, sin, cos, tan, asin, acos, atan, sinh, cosh, tanh,
asinh, acosh, atanh, pow, exp, log, exp2, log2, sqrt, inversesqrt,
abs, sign, floor, trunc, round, roundEven, ceil, fract, mod, modf,
min, max, clamp, mix, step, smoothstep, isnan, isinf,
length, distance, dot, cross, normalize, reflect, refract, faceforward,
matrixCompMult, outerProduct, transpose, determinant, inverse,
lessThan, lessThanEqual, greaterThan, greaterThanEqual, equal, notEqual,
any, all, not,
texture, texture2D, texture3D, textureCube, textureLod, texture2DLod,
textureSize, texelFetch, texelFetchOffset, textureOffset, textureGrad,
textureGather, imageLoad, imageStore, imageSize,
atomicAdd, atomicMin, atomicMax, atomicAnd, atomicOr, atomicXor,
atomicExchange, atomicCompSwap,
dFdx, dFdy, fwidth,
emit, endPrimitive,
barrier, memoryBarrier, groupMemoryBarrier,
packUnorm2x16, packSnorm2x16, unpackUnorm2x16, unpackSnorm2x16,
packHalf2x16, unpackHalf2x16

User-defined functions and struct names are added via declare(name) when their declarations are parsed.

Example: Parsing a + b * c

1. Parse prefix: a (identifier)
2. Loop:
   • Peek +, left BP = 21 (BINDING_POWER_L(11))
   • 21 > 0 (min_bp), so consume +
   • Parse RHS with min_bp = 22 (BINDING_POWER_R(11))
     • Parse prefix: b
     • Loop:
       • Peek *, left BP = 23 (BINDING_POWER_L(12))
       • 23 > 22, so consume *
       • Parse RHS with min_bp = 24
         • Parse prefix: c
         • Peek (nothing or lower precedence)
         • Return c
       • Return b * c
   • Return a + (b * c)

Result: BinaryExpr(+, a, BinaryExpr(*, b, c))

Example: Parsing a = b = c

1. Parse prefix: a
2. Loop:
   • Peek =, left BP = 1 (BINDING_POWER_L(1))
   • 1 > 0, consume =
   • Parse RHS with min_bp = 1 (BINDING_POWER_R(1) for right-associativity)
     • Parse prefix: b
     • Loop:
       • Peek =, left BP = 1
       • 1 > 1? No (not strictly greater)
       • Wait, for right-associative we use BINDING_POWER_R(PRECEDENCE_ASSIGN) = 2
     • Parse RHS with min_bp = 1
       • Parse prefix: b
       • Peek =, left BP = 1
       • 1 > 1? Actually uses specific logic for right-assoc
       • Result: b = c
   • Return a = (b = c)

Result: AssignExpr(a, AssignExpr(b, c))

Error Recovery

When an expression cannot be parsed (unexpected token, missing operand), the parser calls synchronize() to skip to the next ; or }, then returns a placeholder LiteralExpr{0} to keep the AST structurally valid.