Recursive descent parser for predicator expressions.

The parser converts a stream of tokens from the lexer into an Abstract Syntax Tree (AST) with comprehensive error reporting including exact position information.

Grammar

The parser implements this grammar with proper operator precedence:

program      → statement ( ";" statement )* ( ";" )?
statement    → if_statement | while_statement | assignment | expression
if_statement → "if" expression block ( "else" ( block | if_statement ) )?
while_statement → "while" expression block
block        → "{" ( statement ( ";" statement )* ( ";" )? )? "}"
assignment   → location "=" expression
location     → IDENTIFIER ( "." IDENTIFIER | "[" expression "]" )*
expression   → logical_or
logical_or   → logical_and ( "OR" | "||" logical_and )*
logical_and  → logical_not ( "AND" | "&&" logical_not )*
logical_not  → "NOT" | "!" logical_not | comparison
comparison   → addition ( ( ">" | "<" | ">=" | "<=" | "==" | "!=" | "===" | "!==" | "in" | "contains" ) addition )?
addition     → multiplication ( ( "+" | "-" ) multiplication )*
multiplication → unary ( ( "*" | "/" | "%" ) unary )*
unary        → ( "-" | "!" ) unary | postfix
postfix      → primary ( "[" expression "]" | "." IDENTIFIER | "::" TYPE_NAME )*
TYPE_NAME    → "integer" | "float" | "string" | "boolean" | "date" | "datetime" | "duration"
primary      → NUMBER | FLOAT | STRING | BOOLEAN | DATE | DATETIME | IDENTIFIER | duration | relative_date | function_call | list | object | "(" expression ")"
function_call → FUNCTION_NAME "(" ( expression ( "," expression )* )? ")"
list         → "[" ( expression ( "," expression )* )? "]"
object       → "{" ( object_entry ( "," object_entry )* )? "}"
object_entry → object_key ":" expression
object_key   → IDENTIFIER | STRING
duration     → NUMBER UNIT+
relative_date → duration "ago" | duration "from" "now" | "next" duration | "last" duration

TYPE_NAME is matched contextually against an IDENTIFIER token rather than lexed as its own keyword, so the seven names remain usable as variables, properties, and object keys everywhere else (ADR-0011).

Two entry points reach those two grammars. parse/2 parses the expression production alone and rejects a top-level =; parse_program/2 parses the program production and is the only place assignment is legal. The mode - expression or statement - belongs to the entry point rather than to anything in the token stream, which is the same split docs/isa.md draws between Predicator.evaluate/2,3 and Predicator.execute/2.

= is assignment, not equality: it is valid only at the start of a statement and only with an assignable left side. A bare = in expression position is a parse error naming == as the fix. == and === are the only equality operators.

Source positions

Every AST node carries a trailing {line, column} giving the 1-based position of the token that defines it. Leaves point at their own token; operators point at the operator token, so the arithmetic node in a * true reports column 3.

A node built by a caller rather than parsed carries nil in that slot. The slot is not optional: there is one AST shape, and the visitors match on it.

Source spans

Pass spans: true to parse/2 and the same trailing slot carries a Predicator.Types.span/0 instead - the source text the node covers, which is what a diagnostic underlines.

# default
{:arithmetic, :multiply, {:identifier, "a", {1, 1}}, {:literal, true, {1, 5}}, {1, 3}}

# spans: true
{:arithmetic, :multiply,
  {:identifier, "a", {{1, 1}, {1, 2}}},
  {:literal, true, {{1, 5}, {1, 9}}},
  {{1, 1}, {1, 9}}}

A span's end is exclusive - one past the last character - so on a single line end_column - start_column is the length, matching LSP ranges. One parse produces one kind of metadata throughout; positions and spans are never mixed in a single tree.

A parenthesized expression's span widens to include its parentheses: (a + b) gives the arithmetic node the span of (a + b), not just a + b, so the span always reads as balanced. Nesting composes to the outermost pair - ((a)) gives the identifier node the span of ((a)) - and a parenthesized leaf widens the same way a parenthesized compound expression does.

Examples

iex> {:ok, tokens} = Predicator.Lexer.tokenize("score > 85")
iex> Predicator.Parser.parse(tokens)
{:ok, {:comparison, :gt, {:identifier, "score", {1, 1}}, {:literal, 85, {1, 9}}, {1, 7}}}

iex> {:ok, tokens} = Predicator.Lexer.tokenize("(age >= 18)")
iex> Predicator.Parser.parse(tokens)
{:ok, {:comparison, :gte, {:identifier, "age", {1, 2}}, {:literal, 18, {1, 9}}, {1, 6}}}

iex> {:ok, tokens} = Predicator.Lexer.tokenize("score > 85 AND age >= 18")
iex> Predicator.Parser.parse(tokens)
{:ok, {:logical_and, {:comparison, :gt, {:identifier, "score", {1, 1}}, {:literal, 85, {1, 9}}, {1, 7}}, {:comparison, :gte, {:identifier, "age", {1, 16}}, {:literal, 18, {1, 23}}, {1, 20}}, {1, 12}}}