Logic Query DSL Grammar Documentation

Overview

This document describes the complete EBNF grammar for the Logic Query DSL, a declarative language for querying knowledge graphs. The grammar is designed to be unambiguous, LALR-parseable, and extensible.

Grammar File: grammar.lark
Parser: Lark (LALR algorithm)
Version: 1.0
Phase: 2.4 - Logic Query Parser

Grammar Structure

Top-Level Query

query ::= find_clause traversal_clause* where_clause?

A query consists of:

  1. Required: A Find clause to select entities

  2. Optional: Zero or more FOLLOWS clauses for graph traversal

  3. Optional: A WHERE clause for filtering

Examples:

Find(Person)
Find(Person) WHERE age > 30
Find(Person) FOLLOWS AuthoredBy FIND(Paper)
Find(Person) FOLLOWS AuthoredBy WHERE year > 2020

Find Clause - Entity Selection

find_clause ::= "Find" "(" entity_spec ")"
entity_spec ::= IDENTIFIER ("[" entity_name "]")?
entity_name ::= BACKTICK_STRING

Purpose: Select entities by type or by specific name.

Examples:

Find(Person)                    # All entities of type Person
Find(Person[`Alice`])           # Specific entity named "Alice"
Find(Paper[`Deep Learning`])    # Specific paper
Find(Company)                   # All companies

Notes:

  • Entity type is an IDENTIFIER (alphanumeric + underscore)

  • Entity name uses backticks to allow spaces and special characters

  • Entity name is optional (omit for all entities of that type)

Traversal Clause - Graph Navigation

traversal_clause ::= "FOLLOWS" relation_spec direction?
relation_spec ::= IDENTIFIER
direction ::= "INCOMING" | "OUTGOING"

Purpose: Navigate graph relationships.

Examples:

FOLLOWS AuthoredBy              # Follow AuthoredBy relation (default: outgoing)
FOLLOWS AuthoredBy OUTGOING     # Explicit outgoing direction
FOLLOWS AuthoredBy INCOMING     # Reverse direction
FOLLOWS WorksAt                 # Follow WorksAt relation

Notes:

  • Direction defaults to OUTGOING if not specified

  • INCOMING reverses the relation direction

  • Multiple FOLLOWS clauses create multi-hop traversals

Where Clause - Filtering

where_clause ::= "WHERE" condition
condition ::= simple_condition | compound_condition | "(" condition ")"
simple_condition ::= property_path operator value
compound_condition ::= condition ("AND" | "OR") condition | "NOT" condition

Purpose: Filter entities based on property values.

Examples:

WHERE name == "Alice"
WHERE age > 30
WHERE year >= 2020 AND citations > 100
WHERE (name == "Alice" OR name == "Bob") AND age > 30
WHERE NOT (status == "inactive")
WHERE title CONTAINS "machine learning"
WHERE status IN ["active", "pending"]

Operator Precedence (highest to lowest):

  1. NOT (unary)

  2. AND (binary)

  3. OR (binary)

Notes:

  • Use parentheses to override precedence

  • Operators are case-sensitive (use uppercase: AND, OR, NOT)

Property Paths

property_path ::= IDENTIFIER ("." IDENTIFIER)*

Purpose: Access nested properties.

Examples:

name                    # Top-level property
age                     # Top-level property
address.city            # Nested property
metadata.created_at     # Nested property

Notes:

  • Dot notation for nested properties

  • No limit on nesting depth (implementation-dependent)

Operators

operator ::= "==" | "!=" | ">" | "<" | ">=" | "<=" | "IN" | "CONTAINS"

Operator

Description

Example

==

Equality

age == 30

!=

Inequality

status != "inactive"

>

Greater than

year > 2020

<

Less than

age < 18

>=

Greater or equal

citations >= 100

<=

Less or equal

score <= 0.5

IN

Membership

status IN ["active", "pending"]

CONTAINS

Substring

title CONTAINS "learning"

Notes:

  • All operators are case-sensitive

  • IN requires a list value

  • CONTAINS is for string matching (case-sensitive)

Values and Literals

value ::= STRING | NUMBER | BOOLEAN | list | IDENTIFIER
list ::= "[" [value ("," value)*] "]"

String Literals:

"Alice"                 # Double-quoted
'Bob'                   # Single-quoted
"Hello, World!"         # With punctuation

Number Literals:

42                      # Integer
3.14                    # Float
0.001                   # Small float

Boolean Literals:

true                    # Lowercase
false                   # Lowercase
True                    # Capitalized (also valid)
False                   # Capitalized (also valid)

List Literals:

[1, 2, 3]              # Number list
["active", "pending"]   # String list
[true, false]          # Boolean list
[]                     # Empty list

Identifier Values:

variable_name          # Reference to variable (future use)

Complete Examples

Example 1: Simple Entity Lookup

Find(Person)

Meaning: Find all entities of type Person.

Example 2: Entity with Name

Find(Person[`Alice Smith`])

Meaning: Find the specific person named “Alice Smith”.

Example 3: Filter by Property

Find(Person) WHERE age > 30

Meaning: Find all persons older than 30.

Example 4: Multiple Filters with AND

Find(Paper) WHERE year > 2020 AND citations >= 100

Meaning: Find papers published after 2020 with at least 100 citations.

Example 5: Multiple Filters with OR

Find(Person) WHERE name == "Alice" OR name == "Bob"

Meaning: Find persons named Alice or Bob.

Example 6: Complex Boolean Logic

Find(Person) WHERE (name == "Alice" OR name == "Bob") AND age > 30

Meaning: Find persons named Alice or Bob who are older than 30.

Example 7: NOT Operator

Find(Person) WHERE NOT (age < 18)

Meaning: Find persons who are NOT under 18 (i.e., 18 or older).

Example 8: IN Operator

Find(Person) WHERE status IN ["active", "pending"]

Meaning: Find persons with status “active” or “pending”.

Example 9: CONTAINS Operator

Find(Paper) WHERE title CONTAINS "machine learning"

Meaning: Find papers whose title contains “machine learning”.

Example 10: Single-Hop Traversal

Find(Person[`Alice`]) FOLLOWS AuthoredBy

Meaning: Find entities that Alice authored (follow AuthoredBy relation).

Example 11: Multi-Hop Traversal

Find(Person) FOLLOWS AuthoredBy FOLLOWS PublishedIn

Meaning: Find persons → papers they authored → venues where published.

Example 12: Traversal with Direction

Find(Paper) FOLLOWS AuthoredBy INCOMING

Meaning: Find papers ← authors (reverse direction).

Example 13: Traversal with Filter

Find(Person) FOLLOWS AuthoredBy WHERE year > 2020

Meaning: Find persons → papers authored after 2020.

Example 14: Nested Properties

Find(Person) WHERE address.city == "Seattle"

Meaning: Find persons living in Seattle (nested property).

Example 15: Complex Query

Find(Person) WHERE age > 25 FOLLOWS WorksAt WHERE industry == "tech"

Meaning: Find persons over 25 → companies they work at in tech industry.

Grammar Validation

The grammar has been validated to be:

  • ✅ Unambiguous: No shift/reduce or reduce/reduce conflicts

  • ✅ LALR-parseable: Compatible with Lark’s LALR(1) parser

  • ✅ Deterministic: Each input has exactly one parse tree

  • ✅ Complete: Covers all DSL constructs from design spec

Operator Precedence Table

Precedence

Operator

Associativity

Example

1 (highest)

NOT

Right

NOT a AND b = (NOT a) AND b

2

AND

Left

a AND b AND c = (a AND b) AND c

3 (lowest)

OR

Left

a OR b OR c = (a OR b) OR c

Comparison operators (==, !=, >, <, >=, <=, IN, CONTAINS) have no precedence among themselves (cannot chain).

Reserved Keywords

The following keywords are reserved and cannot be used as identifiers:

  • Find

  • WHERE

  • FOLLOWS

  • INCOMING

  • OUTGOING

  • AND

  • OR

  • NOT

  • IN

  • CONTAINS

  • true, false, True, False

Terminal Symbols

Terminal

Pattern

Description

IDENTIFIER

[a-zA-Z_][a-zA-Z0-9_]*

Variable/type names

STRING

"..." or '...'

String literals

BACKTICK_STRING

`...`

Entity names

NUMBER

[0-9]+(\.[0-9]+)?

Numeric literals

BOOLEAN

true|false (case-insensitive)

Boolean literals

Future Extensions

The grammar is designed to support future extensions:

  1. Aggregations: AGGREGATE COUNT(*), SUM(citations)

  2. Subqueries: WHERE id IN (Find(...))

  3. Query Macros: DEFINE macro_name AS ...

  4. Qualified Relations: FOLLOWS Person.MEMBER_OF

  5. Query Hints: /*+ INDEX(name_idx) */

These extensions can be added without breaking existing queries.

References

  • EBNF Standard: ISO/IEC 14977

  • Lark Documentation: https://lark-parser.readthedocs.io/

  • Design Document: openspec/changes/phase-2-4-logic-enhanced/design.md

  • Proposal: openspec/changes/phase-2-4-logic-enhanced/proposal.md