# `Predicator.Parser`
[🔗](https://github.com/riddler/predicator-ex/blob/v9.4.1/lib/predicator/parser.ex#L1)

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
`t: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("limit > 85")
    iex> Predicator.Parser.parse(tokens)
    {:ok, {:comparison, :gt, {:identifier, "limit", {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("limit > 85 AND age >= 18")
    iex> Predicator.Parser.parse(tokens)
    {:ok, {:logical_and, {:comparison, :gt, {:identifier, "limit", {1, 1}}, {:literal, 85, {1, 9}}, {1, 7}}, {:comparison, :gte, {:identifier, "age", {1, 16}}, {:literal, 18, {1, 23}}, {1, 20}}, {1, 12}}}

# `arithmetic_op`

```elixir
@type arithmetic_op() :: :add | :subtract | :multiply | :divide | :modulo
```

Arithmetic operators in the AST.

# `assignment`

```elixir
@type assignment() :: {:assignment, ast(), ast(), position()}
```

An assignment statement: `location "=" expression`.

`location` is the raw access chain the parser built - an `{:identifier, ...}`
optionally wrapped in any number of `{:property_access, ...}` and
`{:bracket_access, ...}` nodes. It is kept as a chain rather than flattened to
a path because a bracket key may be an arbitrary expression, resolvable only
against a context; `Predicator.ContextLocation.resolve/2` does that at
runtime. The chain's depth is the segment count `["store", n]` needs
(ADR-0001).

# `ast`

```elixir
@type ast() ::
  {:literal, value(), position()}
  | {:string_literal, binary(), :double | :single, position()}
  | {:identifier, binary(), position()}
  | {:comparison, comparison_op(), ast(), ast(), position()}
  | {:arithmetic, arithmetic_op(), ast(), ast(), position()}
  | {:unary, unary_op(), ast(), position()}
  | {:membership, membership_op(), ast(), ast(), position()}
  | {:logical_and, ast(), ast(), position()}
  | {:logical_or, ast(), ast(), position()}
  | {:logical_not, ast(), position()}
  | {:list, [ast()], position()}
  | {:object, [object_entry()], position()}
  | {:function_call, binary(), [ast()], position()}
  | {:bracket_access, ast(), ast(), position()}
  | {:property_access, ast(), binary(), position()}
  | {:cast, ast(), binary(), position()}
  | {:duration, [{integer(), binary()}], position()}
  | {:relative_date, ast(), relative_direction(), position()}
```

Abstract Syntax Tree node types.

Every node carries a trailing source position - the `{line, column}` of the
token that defines it, or `nil` for a node built by a caller rather than
parsed.

- `{:literal, value, pos}` - A literal value (number, boolean, list, date, datetime, duration)
- `{:string_literal, value, quote_type, pos}` - A string literal with quote type information
- `{:identifier, name, pos}` - A variable reference
- `{:comparison, operator, left, right, pos}` - A comparison expression (including equality)
- `{:arithmetic, operator, left, right, pos}` - An arithmetic expression (+, -, *, /, %)
- `{:unary, operator, operand, pos}` - A unary expression (-, !)
- `{:logical_and, left, right, pos}` - A logical AND expression
- `{:logical_or, left, right, pos}` - A logical OR expression
- `{:logical_not, operand, pos}` - A logical NOT expression
- `{:list, elements, pos}` - A list literal
- `{:object, entries, pos}` - An object literal whose keys are `t:object_key/0`
- `{:membership, operator, left, right, pos}` - A membership operation (in/contains)
- `{:function_call, name, arguments, pos}` - A function call with arguments
- `{:bracket_access, object, key, pos}` - A bracket access expression (obj[key])
- `{:property_access, object, property, pos}` - A property access expression (obj.prop)
- `{:cast, expression, type_name, pos}` - a postfix type cast (`expr::integer`);
  `type_name` is one of the seven scalar ISA type names, validated at parse time
- `{:duration, units, pos}` - A duration literal (e.g., 3d8h)
- `{:relative_date, duration, direction, pos}` - A relative date expression (e.g., 3d ago, next 2w)

# `block`

```elixir
@type block() :: {:block, [statement()], position()}
```

A brace-delimited statement sequence: `"{" ( statement (";" statement)* (";")? )? "}"`.

Produced only as the then/else slot of an `t:if_statement/0` or the body slot
of a `t:while_statement/0` - a block has no meaning without the statement
that holds it. Not a member of `t:ast/0`, the same as `t:program/0` and
`t:assignment/0`.

# `comparison_op`

```elixir
@type comparison_op() ::
  :gt | :lt | :gte | :lte | :eq | :equal_equal | :ne | :strict_eq | :strict_ne
```

Comparison operators in the AST.

# `if_statement`

```elixir
@type if_statement() :: {:if, ast(), block(), block() | nil, position()}
```

An if statement: `"if" expression block ( "else" ( block | if_statement ) )?`.

`else_block` is `nil` when there is no `else` and a `t:block/0` when there is
- including for `else { }`, whose empty block stays distinguishable from an
absent one. `else if c { B }` desugars to an `else_block` of
`{:block, [{:if, c, ..., ...}], pos}`, with no separate chain node in the AST
(ADR-0013). Not a member of `t:ast/0`.

# `membership_op`

```elixir
@type membership_op() :: :in | :contains
```

Membership operators in the AST.

# `object_entry`

```elixir
@type object_entry() :: {object_key(), ast()}
```

An object entry (key-value pair) in an object literal.

The key can be either an identifier or a string literal.

# `object_key`

```elixir
@type object_key() :: {:object_key, binary(), object_key_style(), position()}
```

A key in an object literal.

Object keys have their own tag rather than reusing the expression node tags,
so no consumer has to tell a key from an expression by tuple arity. `style`
records how the key was written - bare, or quoted with which character - so
`Predicator.Visitors.StringVisitor` can render it back as the author wrote it.

# `object_key_style`

```elixir
@type object_key_style() :: :identifier | :double | :single
```

How an object key was written: bare (`{name: 1}`), double-quoted
(`{"name": 1}`), or single-quoted (`{'name': 1}`).

# `parser_state`

```elixir
@type parser_state() :: %{
  tokens: [Predicator.Lexer.token()],
  position: non_neg_integer(),
  spans?: boolean()
}
```

Internal parser state for tracking position and tokens.

`spans?` records whether the caller asked for spans; it selects what `loc/3`
puts in each node's trailing slot.

# `position`

```elixir
@type position() :: Predicator.Types.position() | Predicator.Types.span() | nil
```

A node's trailing source metadata.

A `t:Predicator.Types.position/0` by default - the `{line, column}` of the
token that defines the node - or a `t:Predicator.Types.span/0` when the AST
was parsed with `spans: true`, or `nil` when the node was not produced by the
parser. One parse produces one kind throughout; the two are never mixed in a
single tree.

# `program`

```elixir
@type program() :: {:program, [statement()], position()}
```

A parsed statement sequence: `statement (";" statement)* [";"]`.

Produced only by `parse_program/2`. A program is never an `t:ast/0`: the
expression entry point cannot return one, and an expression consumer never
has to handle one.

# `program_result`

```elixir
@type program_result() ::
  {:ok, program()}
  | {:error, binary(), pos_integer(), pos_integer(), Predicator.Types.span()}
```

Program parser result.

# `relative_direction`

```elixir
@type relative_direction() :: :ago | :future | :next | :last
```

Relative date directions in the AST.

# `result`

```elixir
@type result() ::
  {:ok, ast()}
  | {:error, binary(), pos_integer(), pos_integer(), Predicator.Types.span()}
```

Parser result - either success with AST or error with details.

# `statement`

```elixir
@type statement() :: assignment() | if_statement() | while_statement() | ast()
```

One statement: an if statement, a while statement, an assignment, or a bare
expression.

# `unary_op`

```elixir
@type unary_op() :: :minus | :bang
```

Unary operators in the AST.

# `value`

```elixir
@type value() ::
  boolean()
  | integer()
  | binary()
  | [value()]
  | Date.t()
  | DateTime.t()
  | Predicator.Types.duration()
  | :undefined
  | nil
```

A value that can appear in literals, including the `undefined` and `null`
literals.

# `visitable`

```elixir
@type visitable() :: program() | statement() | block()
```

Anything a visitor accepts: a whole program, any single statement, or the
block an if statement holds. Wider than `t:ast/0`, which is the expression
layer only.

# `while_statement`

```elixir
@type while_statement() :: {:while, ast(), block(), position()}
```

A while statement: `"while" expression block`.

Statement-position only, on the same terms as `t:if_statement/0`: braces are
mandatory and the body block opens no scope of its own (ADR-0013). Not a
member of `t:ast/0`.

# `parse`

```elixir
@spec parse(
  [Predicator.Lexer.token()],
  keyword()
) :: result()
```

Parses a list of tokens into an Abstract Syntax Tree.

## Parameters

- `tokens` - List of tokens from the lexer
- `opts` - Options:
  - `:spans` - when `true`, each node's trailing slot carries a
    `t:Predicator.Types.span/0` covering the source text the node spans,
    instead of the `{line, column}` of the token that defines it. Defaults to
    `false`.

## Returns

- `{:ok, ast}` - Successfully parsed expression
- `{:error, message, line, column}` - Parse error with position

## Examples

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

    iex> {:ok, tokens} = Predicator.Lexer.tokenize("name == \"John\"")
    iex> Predicator.Parser.parse(tokens)
    {:ok, {:comparison, :equal_equal, {:identifier, "name", {1, 1}}, {:string_literal, "John", :double, {1, 9}}, {1, 6}}}

    iex> {:ok, tokens} = Predicator.Lexer.tokenize("active == true")
    iex> Predicator.Parser.parse(tokens)
    {:ok, {:comparison, :equal_equal, {:identifier, "active", {1, 1}}, {:literal, true, {1, 11}}, {1, 8}}}

    iex> {:ok, tokens} = Predicator.Lexer.tokenize("a * true")
    iex> Predicator.Parser.parse(tokens, spans: true)
    {:ok, {:arithmetic, :multiply, {:identifier, "a", {{1, 1}, {1, 2}}}, {:literal, true, {{1, 5}, {1, 9}}}, {{1, 1}, {1, 9}}}}

# `parse_program`

```elixir
@spec parse_program(
  [Predicator.Lexer.token()],
  keyword()
) :: program_result()
```

Parses a list of tokens into a statement sequence.

Implements `program := statement (";" statement)* [";"]`, where a statement
is either an assignment (`location "=" expression`) or an ordinary
expression. `parse/2` and `parse_program/2` are separate entry points
because the mode - expression or statement - belongs to the entry point, not
to the token stream (`docs/isa.md` section 2): `parse/2` never returns a
`t:program/0`, and `parse_program/2` always returns one, even for a single
statement.

## Parameters

- `tokens` - List of tokens from the lexer
- `opts` - Options: `:spans`, with the same meaning as `parse/2`

## Returns

- `{:ok, program}` - Successfully parsed statement sequence
- `{:error, message, line, column}` - Parse error with position

## Examples

    iex> {:ok, tokens} = Predicator.Lexer.tokenize("a = 1; b = a + 1")
    iex> {:ok, {:program, statements, _pos}} = Predicator.Parser.parse_program(tokens)
    iex> statements
    [
      {:assignment, {:identifier, "a", {1, 1}}, {:literal, 1, {1, 5}}, {1, 3}},
      {:assignment, {:identifier, "b", {1, 8}}, {:arithmetic, :add, {:identifier, "a", {1, 12}}, {:literal, 1, {1, 16}}, {1, 14}}, {1, 10}}
    ]

    iex> {:ok, tokens} = Predicator.Lexer.tokenize("42 = 1")
    iex> Predicator.Parser.parse_program(tokens)
    {:error, "Left side of '=' must be an assignable location - an identifier, a property access, or a bracket access.", 1, 4, {{1, 4}, {1, 5}}}

---

*Consult [api-reference.md](api-reference.md) for complete listing*