Predicator.Parser (predicator v2.2.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 | equality
equality     → comparison ( ( "==" | "!=" ) comparison )*
comparison   → addition ( ( ">" | "<" | ">=" | "<=" | "=" | "in" | "contains" ) addition )?
addition     → multiplication ( ( "+" | "-" ) multiplication )*
multiplication → unary ( ( "*" | "/" | "%" ) unary )*
unary        → ( "-" | "!" ) unary | postfix
postfix      → primary ( "[" expression "]" )*
primary      → NUMBER | STRING | BOOLEAN | DATE | DATETIME | IDENTIFIER | function_call | list | "(" expression ")"
function_call → FUNCTION_NAME "(" ( expression ( "," expression )* )? ")"
list         → "[" ( expression ( "," expression )* )? "]"

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.

equality_op()

Equality operators in the AST.

membership_op()

Membership operators in the AST.

parser_state()

Internal parser state for tracking position and tokens.

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()}
  | {:equality, equality_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()]}
  | {:function_call, binary(), [ast()]}
  | {:bracket_access, ast(), ast()}

Abstract Syntax Tree node types.

{:literal, value} - A literal value (number, boolean, list, date, datetime)
{:string_literal, value, quote_type} - A string literal with quote type information
{:identifier, name} - A variable reference
{:comparison, operator, left, right} - A comparison expression
{:equality, operator, left, right} - An equality expression (== !=)
{: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
{: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])

comparison_op()

@type comparison_op() :: :gt | :lt | :gte | :lte | :eq

Comparison operators in the AST.

equality_op()

@type equality_op() :: :equal_equal | :ne

Equality operators in the AST.

membership_op()

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

Membership operators in the AST.

parser_state()

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

Internal parser state for tracking position and tokens.

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

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}}}