Predicator.Parser (predicator v3.4.0)

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:

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 )*
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

Examples

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

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

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

Summary

Types

arithmetic_op()

Arithmetic operators in the AST.

ast()

Abstract Syntax Tree node types.

comparison_op()

Comparison operators in the AST.

membership_op()

Membership operators in the AST.

object_entry()

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

object_key()

A key in an object literal - either an identifier or string literal.

parser_state()

Internal parser state for tracking position and tokens.

relative_direction()

Relative date directions in the AST.

result()

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

unary_op()

Unary operators in the AST.

value()

A value that can appear in literals.

Functions

parse(tokens)

Parses a list of tokens into an Abstract Syntax Tree.

Types

arithmetic_op()

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

Arithmetic operators in the AST.

ast()

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

Abstract Syntax Tree node types.

{:literal, value} - A literal value (number, boolean, list, date, datetime, duration)
{:string_literal, value, quote_type} - A string literal with quote type information
{:identifier, name} - A variable reference
{:comparison, operator, left, right} - A comparison expression (including equality)
{:arithmetic, operator, left, right} - An arithmetic expression (+, -, *, /, %)
{:unary, operator, operand} - A unary expression (-, !)
{:logical_and, left, right} - A logical AND expression
{:logical_or, left, right} - A logical OR expression
{:logical_not, operand} - A logical NOT expression
{:list, elements} - A list literal
{:object, entries} - An object literal with key-value pairs
{:membership, operator, left, right} - A membership operation (in/contains)
{:function_call, name, arguments} - A function call with arguments
{:bracket_access, object, key} - A bracket access expression (obj[key])
{:duration, units} - A duration literal (e.g., 3d8h)
{:relative_date, duration, direction} - A relative date expression (e.g., 3d ago, next 2w)

comparison_op()

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

Comparison operators in the AST.

membership_op()

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

Membership operators in the AST.

object_entry()

@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()

@type object_key() :: {:identifier, binary()} | {:string_literal, binary()}

A key in an object literal - either an identifier or string literal.

parser_state()

@type parser_state() :: %{
  tokens: [Predicator.Lexer.token()],
  position: non_neg_integer()
}

Internal parser state for tracking position and tokens.

relative_direction()

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

Relative date directions in the AST.

result()

@type result() :: {:ok, ast()} | {:error, binary(), pos_integer(), pos_integer()}

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

unary_op()

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

Unary operators in the AST.

value()

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

A value that can appear in literals.

Functions

parse(tokens)

@spec parse([Predicator.Lexer.token()]) :: result()

Parses a list of tokens into an Abstract Syntax Tree.

Parameters

tokens - List of tokens from the lexer

Returns

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

Examples

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

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

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