“

Series: S3 Data Foundation · Article 7 | Level: Advanced | Reading Time: 20 min

OQL Parser Implementation: From Text to AST

Tags: #OQL #Parser #AST #Lexer #RecursiveDescent #coomia-dip

#TL;DR

The previous article defined OQL's complete grammar. This article dives into the parser implementation: how a raw OQL string is transformed into a structured Abstract Syntax Tree (AST). We chose a hand-written recursive descent parser over ANTLR/PEG generators for superior error recovery and performance. The article covers the Lexer's token design, the recursive descent Parser's core algorithms, the AST node type hierarchy, the semantic analysis phase (type checking and name resolution), and the user-friendly error reporting mechanism. Complete code examples trace the journey from FETCH Person WHERE age > 30 to an executable query plan.

#1. Parser Architecture Overview

#1.1 Three-Phase Processing Pipeline

Code

OQL Parser Processing Pipeline:

┌──────────┐    ┌──────────┐    ┌──────────┐    ┌──────────┐
│ OQL Text  │───→│  Lexer   │───→│  Parser  │───→│ Analyzer │
│          │    │          │    │          │    │          │
└──────────┘    └──────────┘    └──────────┘    └──────────┘
                     │               │               │
                     ▼               ▼               ▼
                Token Stream      Raw AST      Typed AST
                                                    │
                                                    ▼
                                            ┌──────────┐
                                            │  Query   │
                                            │  Plan    │
                                            └──────────┘

#1.2 Why Hand-Written Instead of Generated

Code

Hand-Written Parser vs. Generator Comparison:

┌─────────────────┬──────────────────┬──────────────────┐
│ Dimension        │ Recursive Descent │ ANTLR/PEG Gen    │
├─────────────────┼──────────────────┼──────────────────┤
│ Error Recovery   │ Fine-grained      │ Limited           │
│ Error Messages   │ Highly custom     │ Templated         │
│ Performance      │ Optimal           │ General overhead  │
│ Debugging        │ Direct step-thru  │ Generated code    │
│ Incremental      │ Easy to implement │ Extra framework   │
│ Dependencies     │ Zero              │ Runtime required  │
│ Learning Curve   │ Compiler basics   │ Tool chain        │
│ Maintenance      │ Medium            │ Low               │
└─────────────────┴──────────────────┴──────────────────┘

Conclusion: With ~50 productions, the hand-written parser's
advantages in error experience and performance far outweigh
maintenance costs.

#2. Lexer (Lexical Analyzer)

#2.1 Token Type Definitions

Python

from enum import Enum, auto
from dataclasses import dataclass
from typing import Optional

class TokenType(Enum):
    """OQL token types"""
    # Keywords
    FETCH = auto()
    TRAVERSE = auto()
    AGGREGATE = auto()
    TIMELINE = auto()
    DIFF = auto()
    WHERE = auto()
    WITH = auto()
    METRIC = auto()
    AT = auto()
    TIME = auto()
    BRANCH = auto()
    ORDER = auto()
    BY = auto()
    LIMIT = auto()
    OFFSET = auto()
    AS = auto()
    AND = auto()
    OR = auto()
    NOT = auto()
    IN = auto()
    BETWEEN = auto()
    LIKE = auto()
    IS = auto()
    NULL = auto()
    TRUE = auto()
    FALSE = auto()
    SELECT = auto()
    GROUP = auto()
    HAVING = auto()

    # Identifiers and literals
    IDENTIFIER = auto()
    STRING_LITERAL = auto()
    NUMBER_LITERAL = auto()
    FLOAT_LITERAL = auto()
    DATETIME_LITERAL = auto()

    # Operators
    EQ = auto()           # =
    NEQ = auto()          # !=
    LT = auto()           # <
    GT = auto()           # >
    LTE = auto()          # <=
    GTE = auto()          # >=
    ARROW = auto()        # ->
    DOT = auto()          # .
    STAR = auto()         # *
    PLUS = auto()         # +
    MINUS = auto()        # -
    SLASH = auto()        # /
    PERCENT = auto()      # %

    # Delimiters
    LPAREN = auto()
    RPAREN = auto()
    LBRACKET = auto()
    RBRACKET = auto()
    COMMA = auto()
    SEMICOLON = auto()
    COLON = auto()

    # Special
    EOF = auto()
    ERROR = auto()


@dataclass(frozen=True)
class Token:
    """Lexical token"""
    type: TokenType
    value: str
    line: int
    column: int
    offset: int  # byte offset in source text

    @property
    def span(self) -> tuple[int, int]:
        return (self.offset, self.offset + len(self.value))

#2.2 Core Lexer Implementation

Python

class OQLLexer:
    """OQL lexical analyzer — zero dependencies, single-pass scan"""

    KEYWORDS: dict[str, TokenType] = {
        'FETCH': TokenType.FETCH,
        'TRAVERSE': TokenType.TRAVERSE,
        'AGGREGATE': TokenType.AGGREGATE,
        'TIMELINE': TokenType.TIMELINE,
        'DIFF': TokenType.DIFF,
        'WHERE': TokenType.WHERE,
        'WITH': TokenType.WITH,
        'METRIC': TokenType.METRIC,
        'AT': TokenType.AT,
        'TIME': TokenType.TIME,
        'BRANCH': TokenType.BRANCH,
        # ... additional keywords omitted for brevity
    }

    def __init__(self, source: str):
        self._source = source
        self._pos = 0
        self._line = 1
        self._column = 1
        self._tokens: list[Token] = []

    def tokenize(self) -> list[Token]:
        while self._pos < len(self._source):
            self._skip_whitespace_and_comments()
            if self._pos >= len(self._source):
                break

            ch = self._source[self._pos]

            if ch.isalpha() or ch == '_':
                self._read_identifier_or_keyword()
            elif ch.isdigit():
                self._read_number()
            elif ch == "'":
                self._read_string()
            elif ch == '-' and self._peek(1) == '>':
                self._emit(TokenType.ARROW, '->', 2)
            elif ch == '!' and self._peek(1) == '=':
                self._emit(TokenType.NEQ, '!=', 2)
            elif ch == '<' and self._peek(1) == '=':
                self._emit(TokenType.LTE, '<=', 2)
            elif ch == '>' and self._peek(1) == '=':
                self._emit(TokenType.GTE, '>=', 2)
            else:
                self._read_single_char(ch)

        self._tokens.append(Token(
            TokenType.EOF, '', self._line, self._column, self._pos
        ))
        return self._tokens

#2.3 Case-Insensitive Keywords

Python

def _read_identifier_or_keyword(self):
    start = self._pos
    start_col = self._column
    while self._pos < len(self._source) and (
        self._source[self._pos].isalnum() or self._source[self._pos] == '_'
    ):
        self._advance()

    value = self._source[start:self._pos]
    upper = value.upper()

    # Case-insensitive keyword matching
    if upper in self.KEYWORDS:
        token_type = self.KEYWORDS[upper]
    else:
        token_type = TokenType.IDENTIFIER

    self._tokens.append(Token(token_type, value, self._line, start_col, start))

#3. Recursive Descent Parser

#3.1 AST Node Type Hierarchy

Python

from abc import ABC, abstractmethod
from dataclasses import dataclass, field
from typing import Union

class ASTNode(ABC):
    """AST node base class"""
    @abstractmethod
    def accept(self, visitor: 'ASTVisitor') -> any:
        ...

@dataclass
class FetchStatement(ASTNode):
    """FETCH statement node"""
    entity_type: str
    properties: list[str] | None  # None means SELECT *
    where_clause: 'Expression | None'
    with_metrics: list['MetricRef']
    at_clause: 'AtClause | None'
    order_by: list['OrderByItem']
    limit: int | None
    offset: int | None

    def accept(self, visitor):
        return visitor.visit_fetch(self)

@dataclass
class TraverseStatement(ASTNode):
    """TRAVERSE statement node"""
    start_type: str
    path_segments: list['PathSegment']
    where_clause: 'Expression | None'
    max_depth: int | None
    return_mode: str  # 'NODES' | 'PATHS' | 'SUBGRAPH'

    def accept(self, visitor):
        return visitor.visit_traverse(self)

@dataclass
class AggregateStatement(ASTNode):
    """AGGREGATE statement node"""
    entity_type: str
    group_by: list[str]
    aggregations: list['AggregationExpr']
    where_clause: 'Expression | None'
    having_clause: 'Expression | None'

    def accept(self, visitor):
        return visitor.visit_aggregate(self)

@dataclass
class TimelineStatement(ASTNode):
    """TIMELINE statement node"""
    entity_type: str
    entity_filter: 'Expression | None'
    time_range: 'TimeRange | None'
    event_types: list[str]
    granularity: str | None

    def accept(self, visitor):
        return visitor.visit_timeline(self)

@dataclass
class DiffStatement(ASTNode):
    """DIFF statement node"""
    entity_type: str
    from_ref: 'BranchOrTimeRef'
    to_ref: 'BranchOrTimeRef'
    properties: list[str] | None

    def accept(self, visitor):
        return visitor.visit_diff(self)

#3.2 Expression Nodes

Python

@dataclass
class BinaryExpr(ASTNode):
    """Binary expression"""
    left: 'Expression'
    operator: str  # '=', '!=', '<', '>', '<=', '>=', 'AND', 'OR'
    right: 'Expression'

    def accept(self, visitor):
        return visitor.visit_binary(self)

@dataclass
class UnaryExpr(ASTNode):
    """Unary expression"""
    operator: str  # 'NOT', '-'
    operand: 'Expression'

    def accept(self, visitor):
        return visitor.visit_unary(self)

@dataclass
class PropertyRef(ASTNode):
    """Property reference"""
    entity_type: str | None  # optional qualifier
    property_name: str

    def accept(self, visitor):
        return visitor.visit_property_ref(self)

@dataclass
class LiteralExpr(ASTNode):
    """Literal value"""
    value: str | int | float | bool | None
    literal_type: str  # 'string', 'int', 'float', 'bool', 'null', 'datetime'

    def accept(self, visitor):
        return visitor.visit_literal(self)

# Type alias
Expression = Union[BinaryExpr, UnaryExpr, PropertyRef, LiteralExpr]

#3.3 Core Parser Logic

Python

class OQLParser:
    """OQL recursive descent parser"""

    def __init__(self, tokens: list[Token]):
        self._tokens = tokens
        self._pos = 0
        self._errors: list[ParseError] = []

    def parse(self) -> ASTNode:
        """Parse entry point"""
        token = self._current()

        if token.type == TokenType.FETCH:
            return self._parse_fetch()
        elif token.type == TokenType.TRAVERSE:
            return self._parse_traverse()
        elif token.type == TokenType.AGGREGATE:
            return self._parse_aggregate()
        elif token.type == TokenType.TIMELINE:
            return self._parse_timeline()
        elif token.type == TokenType.DIFF:
            return self._parse_diff()
        else:
            raise self._error(
                f"Expected statement keyword (FETCH, TRAVERSE, AGGREGATE, "
                f"TIMELINE, DIFF), found '{token.value}'",
                token
            )

    def _parse_fetch(self) -> FetchStatement:
        """
        FETCH EntityType
          [SELECT prop1, prop2, ...]
          [WHERE condition]
          [WITH METRIC metric1, metric2, ...]
          [AT TIME datetime | AT BRANCH name]
          [ORDER BY prop [ASC|DESC], ...]
          [LIMIT n [OFFSET m]]
        """
        self._expect(TokenType.FETCH)
        entity_type = self._expect(TokenType.IDENTIFIER).value

        properties = None
        if self._match(TokenType.SELECT):
            properties = self._parse_property_list()

        where_clause = None
        if self._match(TokenType.WHERE):
            where_clause = self._parse_expression()

        with_metrics = []
        if self._match(TokenType.WITH):
            self._expect(TokenType.METRIC)
            with_metrics = self._parse_metric_list()

        at_clause = None
        if self._match(TokenType.AT):
            at_clause = self._parse_at_clause()

        order_by = []
        if self._match(TokenType.ORDER):
            self._expect(TokenType.BY)
            order_by = self._parse_order_by_list()

        limit = None
        offset = None
        if self._match(TokenType.LIMIT):
            limit = int(self._expect(TokenType.NUMBER_LITERAL).value)
            if self._match(TokenType.OFFSET):
                offset = int(self._expect(TokenType.NUMBER_LITERAL).value)

        return FetchStatement(
            entity_type=entity_type,
            properties=properties,
            where_clause=where_clause,
            with_metrics=with_metrics,
            at_clause=at_clause,
            order_by=order_by,
            limit=limit,
            offset=offset,
        )

#3.4 Expression Parsing (Pratt Parsing)

Python

def _parse_expression(self, min_precedence: int = 0) -> Expression:
    """Pratt parsing for operator precedence"""
    left = self._parse_primary()

    while True:
        token = self._current()
        prec = self._get_precedence(token)
        if prec <= min_precedence:
            break

        operator = self._advance().value
        right = self._parse_expression(prec)
        left = BinaryExpr(left=left, operator=operator, right=right)

    return left

PRECEDENCE_TABLE = {
    'OR': 1,
    'AND': 2,
    'NOT': 3,
    '=': 4, '!=': 4,
    '<': 5, '>': 5, '<=': 5, '>=': 5,
    'IN': 5, 'BETWEEN': 5, 'LIKE': 5, 'IS': 5,
    '+': 6, '-': 6,
    '*': 7, '/': 7, '%': 7,
}

def _parse_primary(self) -> Expression:
    """Parse atomic expression"""
    token = self._current()

    if token.type == TokenType.LPAREN:
        self._advance()
        expr = self._parse_expression()
        self._expect(TokenType.RPAREN)
        return expr

    if token.type == TokenType.NOT:
        self._advance()
        operand = self._parse_expression(self.PRECEDENCE_TABLE['NOT'])
        return UnaryExpr(operator='NOT', operand=operand)

    if token.type == TokenType.NUMBER_LITERAL:
        self._advance()
        return LiteralExpr(value=int(token.value), literal_type='int')

    if token.type == TokenType.STRING_LITERAL:
        self._advance()
        return LiteralExpr(value=token.value, literal_type='string')

    if token.type in (TokenType.TRUE, TokenType.FALSE):
        self._advance()
        return LiteralExpr(
            value=token.type == TokenType.TRUE, literal_type='bool'
        )

    if token.type == TokenType.NULL:
        self._advance()
        return LiteralExpr(value=None, literal_type='null')

    if token.type == TokenType.IDENTIFIER:
        return self._parse_identifier_or_function()

    raise self._error(f"Unexpected token '{token.value}'", token)

#4. Semantic Analysis Phase

#4.1 Name Resolution

Python

class NameResolver(ASTVisitor):
    """Resolves identifiers against the Ontology Schema"""

    def __init__(self, schema_registry: SchemaRegistry):
        self._registry = schema_registry
        self._errors: list[SemanticError] = []

    def visit_fetch(self, node: FetchStatement):
        # Verify Entity Type exists
        entity_def = self._registry.get_entity_type(node.entity_type)
        if entity_def is None:
            candidates = self._registry.suggest_entity_type(node.entity_type)
            self._errors.append(SemanticError(
                f"Unknown entity type '{node.entity_type}'",
                suggestions=candidates,
                node=node
            ))
            return

        # Verify properties exist
        if node.properties:
            for prop in node.properties:
                if prop not in entity_def.properties:
                    candidates = entity_def.suggest_property(prop)
                    self._errors.append(SemanticError(
                        f"Unknown property '{prop}' on type "
                        f"'{node.entity_type}'",
                        suggestions=candidates,
                        node=node
                    ))

        # Verify WHERE clause property references
        if node.where_clause:
            self._resolve_expression(node.where_clause, entity_def)

        # Verify METRIC references
        for metric in node.with_metrics:
            metric_def = self._registry.get_metric(metric.name)
            if metric_def is None:
                self._errors.append(SemanticError(
                    f"Unknown metric '{metric.name}'",
                    node=node
                ))

#4.2 Type Checking

Python

class TypeChecker(ASTVisitor):
    """Verifies expression type compatibility"""

    def visit_binary(self, node: BinaryExpr) -> OQLType:
        left_type = node.left.accept(self)
        right_type = node.right.accept(self)

        if node.operator in ('AND', 'OR'):
            if left_type != OQLType.BOOLEAN or right_type != OQLType.BOOLEAN:
                self._error(
                    f"Operator '{node.operator}' requires boolean operands, "
                    f"got {left_type} and {right_type}",
                    node
                )
            return OQLType.BOOLEAN

        if node.operator in ('=', '!='):
            if not self._types_comparable(left_type, right_type):
                self._error(
                    f"Cannot compare {left_type} with {right_type}",
                    node
                )
            return OQLType.BOOLEAN

        if node.operator in ('<', '>', '<=', '>='):
            if not self._types_orderable(left_type, right_type):
                self._error(
                    f"Cannot order-compare {left_type} with {right_type}",
                    node
                )
            return OQLType.BOOLEAN

        if node.operator in ('+', '-', '*', '/'):
            return self._numeric_promotion(left_type, right_type, node)

        raise ValueError(f"Unknown operator: {node.operator}")

#4.3 Schema Validation Example

Code

Full Semantic Analysis Example:

Input OQL:
  FETCH Person
  SELECT name, age, department.name
  WHERE age > 30 AND status = 'active'
  WITH METRIC direct_reports, total_revenue
  AT BRANCH 'feature-branch'
  ORDER BY age DESC
  LIMIT 100

Name Resolution Results:
  OK  Person          -> EntityType(id='person', namespace='core')
  OK  name            -> Property(name='name', type=STRING)
  OK  age             -> Property(name='age', type=INT)
  OK  department.name -> Traversal(Person->BelongsTo->Department).name
  OK  status          -> Property(name='status', type=STRING)
  OK  direct_reports  -> Metric(id='direct_reports', return_type=INT)
  OK  total_revenue   -> Metric(id='total_revenue', return_type=DECIMAL)
  OK  'feature-branch' -> Branch(name='feature-branch')

Type Check Results:
  OK  age > 30           : INT > INT -> BOOLEAN
  OK  status = 'active'  : STRING = STRING -> BOOLEAN
  OK  ... AND ...        : BOOLEAN AND BOOLEAN -> BOOLEAN
  OK  ORDER BY age       : INT is orderable

#5. Error Recovery Mechanism

#5.1 Panic Mode Recovery

Python

class ErrorRecovery:
    """Parser error recovery strategies"""

    # Synchronization points: stop skipping at these tokens
    SYNC_TOKENS = {
        TokenType.FETCH, TokenType.TRAVERSE, TokenType.AGGREGATE,
        TokenType.TIMELINE, TokenType.DIFF,
        TokenType.WHERE, TokenType.WITH, TokenType.AT,
        TokenType.ORDER, TokenType.LIMIT,
        TokenType.SEMICOLON, TokenType.EOF,
    }

    @staticmethod
    def synchronize(parser: 'OQLParser'):
        """Panic mode: skip tokens until a sync point is found"""
        parser._advance()  # skip the error-causing token
        while not parser._is_at_end():
            if parser._current().type in ErrorRecovery.SYNC_TOKENS:
                return
            parser._advance()

#5.2 Friendly Error Messages

Code

Error message design principles:

1. Point to the error location (line, column, context)
2. Explain what was expected
3. Suggest corrections

Example output:

Error at line 1, column 14:
  FETCH Person WERE age > 30
               ^^^^
  Expected 'WHERE', found 'WERE'.
  Did you mean: WHERE

Error at line 2, column 3:
  FETCH Person
  WHERE ages > 30
        ^^^^
  Unknown property 'ages' on type 'Person'.
  Available properties: age (Int), name (String), email (String)
  Did you mean: age

Error at line 1, column 26:
  FETCH Person WHERE age > 'thirty'
                           ^^^^^^^^
  Type mismatch: cannot compare Int with String.
  Property 'age' is of type Int, but got String literal 'thirty'.

#5.3 Multi-Error Collection

Python

class MultiErrorCollector:
    """Collects all errors instead of stopping at the first one"""

    def __init__(self, max_errors: int = 20):
        self._errors: list[OQLError] = []
        self._max_errors = max_errors

    def report(self, error: OQLError):
        self._errors.append(error)
        if len(self._errors) >= self._max_errors:
            raise TooManyErrorsException(self._errors)

    def has_errors(self) -> bool:
        return len(self._errors) > 0

    def format_all(self, source: str) -> str:
        """Format all errors into user-friendly output"""
        lines = source.splitlines()
        output = []
        for error in self._errors:
            output.append(f"\nError at line {error.line}, column {error.column}:")
            if 0 < error.line <= len(lines):
                output.append(f"  {lines[error.line - 1]}")
                output.append(
                    f"  {' ' * (error.column - 1)}{'^' * error.length}"
                )
            output.append(f"  {error.message}")
            if error.suggestions:
                output.append(
                    f"  Did you mean: {', '.join(error.suggestions)}"
                )
        return '\n'.join(output)

#6. AST to Query Plan Conversion

#6.1 Logical Plan Generation

Python

class LogicalPlanGenerator(ASTVisitor):
    """Converts Typed AST into a logical query plan"""

    def visit_fetch(self, node: FetchStatement) -> LogicalPlan:
        plan = EntityScan(entity_type=node.entity_type)

        if node.where_clause:
            predicate = self._compile_expression(node.where_clause)
            plan = Filter(child=plan, predicate=predicate)

        if node.properties:
            plan = Project(child=plan, columns=node.properties)

        for metric in node.with_metrics:
            plan = MetricExpansion(child=plan, metric=metric)

        if node.at_clause:
            plan = TimeTravel(child=plan, ref=node.at_clause)

        if node.order_by:
            plan = Sort(child=plan, order_by=node.order_by)

        if node.limit is not None:
            plan = Limit(child=plan, limit=node.limit, offset=node.offset)

        return plan

#6.2 Complete Compilation Example

Code

Full Compilation Pipeline Example:

OQL Input:
  FETCH Person
  WHERE age > 30 AND department.name = 'Engineering'
  WITH METRIC direct_reports
  ORDER BY age DESC
  LIMIT 50

    -> Lexer

Token Stream:
  [FETCH] [Person:ID] [WHERE] [age:ID] [>] [30:NUM]
  [AND] [department:ID] [.] [name:ID] [=] ['Engineering':STR]
  [WITH] [METRIC] [direct_reports:ID]
  [ORDER] [BY] [age:ID] [DESC:ID]
  [LIMIT] [50:NUM] [EOF]

    -> Parser

AST:
  FetchStatement(
    entity_type='Person',
    where=BinaryExpr(AND,
      BinaryExpr(>, PropertyRef('age'), Literal(30)),
      BinaryExpr(=, PropertyRef('department.name'), Literal('Engineering'))
    ),
    metrics=[MetricRef('direct_reports')],
    order_by=[OrderBy('age', DESC)],
    limit=50
  )

    -> Semantic Analysis

Typed AST:
  (same as above, but property refs bound to schema, types verified)

    -> Logical Plan

  Limit(50)
    +-- Sort(age DESC)
       +-- MetricExpansion(direct_reports)
          +-- Filter(age > 30 AND department.name = 'Engineering')
             +-- EntityScan(Person)

    -> SQL Compilation

  SELECT t2.*, (
    SELECT COUNT(*) FROM entity_edge
    WHERE source_id = t2.entity_id AND edge_type = 'Manages'
  ) AS direct_reports
  FROM (
    SELECT ec.* FROM entity_common ec
    JOIN entity_edge ee ON ec.entity_id = ee.source_id
    JOIN entity_common ec2 ON ee.target_id = ec2.entity_id
    WHERE ec.entity_type = 'Person'
      AND JSON_EXTRACT(ec.properties, '$.age') > 30
      AND ee.edge_type = 'BelongsTo'
      AND ec2.entity_type = 'Department'
      AND JSON_EXTRACT(ec2.properties, '$.name') = 'Engineering'
  ) t2
  ORDER BY JSON_EXTRACT(t2.properties, '$.age') DESC
  LIMIT 50

#7. Incremental Parsing and IDE Support

#7.1 Incremental Parsing Strategy

Code

Incremental Parsing: Real-time feedback during user input

Strategy:
1. Split document into independent parse units by statement
2. Re-parse only affected statements on edit
3. Token-level change detection minimizes re-parsing scope

+-------------------------------------------+
| Document                                   |
|                                            |
|  FETCH Person WHERE age > 30  <- cached    |
|  ;                                         |
|  TRAVERSE Person -> Company   <- editing   |
|  ;                                         |
|  AGGREGATE Device GROUP BY type <- cached  |
+-------------------------------------------+

Only re-parse statement 2; others use cached ASTs

#7.2 Auto-Completion Support

Python

class OQLCompletionProvider:
    """OQL auto-completion provider"""

    def complete(self, source: str, cursor_pos: int) -> list[Completion]:
        tokens = self._lexer.tokenize(source[:cursor_pos])
        context = self._analyze_context(tokens)

        if context == CompletionContext.STATEMENT_START:
            return [
                Completion('FETCH', 'Query entities'),
                Completion('TRAVERSE', 'Graph traversal'),
                Completion('AGGREGATE', 'Aggregation query'),
                Completion('TIMELINE', 'Event timeline'),
                Completion('DIFF', 'Branch diff'),
            ]

        if context == CompletionContext.ENTITY_TYPE:
            return [
                Completion(et.name, et.description)
                for et in self._registry.list_entity_types()
            ]

        if context == CompletionContext.PROPERTY:
            entity_type = self._resolve_current_entity_type(tokens)
            if entity_type:
                return [
                    Completion(p.name, f"{p.type} - {p.description}")
                    for p in entity_type.properties.values()
                ]

        return []

#8. Performance Benchmarks

#8.1 Parsing Performance

Code

OQL Parser Performance Benchmarks (single-thread, Apple M2):

+-------------------------------+----------+----------+
| Test Case                      | Parse    | Through- |
|                                | Time     | put      |
+-------------------------------+----------+----------+
| Simple FETCH (30 chars)        | 12 us    | 83K qps  |
| FETCH with WHERE (100 chars)   | 28 us    | 36K qps  |
| Complex TRAVERSE (200 chars)   | 45 us    | 22K qps  |
| Full query (500 chars)         | 89 us    | 11K qps  |
| Large aggregation (1000 chars) | 156 us   | 6.4K qps |
+-------------------------------+----------+----------+

Comparison (same queries):
  ANTLR 4 generated parser:  3-5x slower
  Python lark library:        8-12x slower
  Hand-written Lexer+Parser:  fastest

#8.2 Memory Footprint

Code

AST Memory Footprint:

+-------------------+----------+----------+
| AST Node Type      | Per Node | Typical  |
+-------------------+----------+----------+
| FetchStatement    | 128 B    | 1        |
| BinaryExpr        | 64 B     | 3-10     |
| PropertyRef       | 48 B     | 5-20     |
| LiteralExpr       | 40 B     | 3-10     |
| MetricRef         | 32 B     | 0-5      |
+-------------------+----------+----------+
| Typical query      | ~1.5 KB  |          |
| Complex query      | ~5 KB    |          |
+-------------------+----------+----------+

Even with 10,000 concurrent queries, total AST memory < 50 MB

#9. Testing Strategy

#9.1 Parser Test Matrix

Python

class TestOQLParser:
    """OQL parser tests"""

    def test_simple_fetch(self):
        ast = parse("FETCH Person")
        assert isinstance(ast, FetchStatement)
        assert ast.entity_type == "Person"
        assert ast.where_clause is None

    def test_fetch_with_where(self):
        ast = parse("FETCH Person WHERE age > 30 AND name = 'Alice'")
        assert isinstance(ast.where_clause, BinaryExpr)
        assert ast.where_clause.operator == "AND"

    def test_traverse_multi_hop(self):
        ast = parse(
            "TRAVERSE Person -> WorksAt -> Company -> LocatedIn -> City"
        )
        assert isinstance(ast, TraverseStatement)
        assert len(ast.path_segments) == 4

    def test_case_insensitive_keywords(self):
        ast1 = parse("FETCH Person")
        ast2 = parse("fetch Person")
        ast3 = parse("Fetch Person")
        assert ast1.entity_type == ast2.entity_type == ast3.entity_type

    def test_error_recovery(self):
        errors = parse_with_errors("FETCH Person WERE age > 30")
        assert len(errors) == 1
        assert "WHERE" in errors[0].suggestions

    def test_operator_precedence(self):
        ast = parse("FETCH Person WHERE a > 1 OR b > 2 AND c > 3")
        # AND binds tighter than OR
        assert ast.where_clause.operator == "OR"
        assert ast.where_clause.right.operator == "AND"

#9.2 Fuzz Testing

Python

from hypothesis import given, strategies as st

@given(st.text(min_size=1, max_size=1000))
def test_parser_never_crashes(random_text):
    """Parser should never crash on any input"""
    try:
        parse(random_text)
    except OQLParseError:
        pass  # legitimate parse error
    # Should NOT throw other exceptions (IndexError, KeyError, etc.)

#Key Takeaways

A hand-written recursive descent parser is the optimal choice for OQL-scale languages: with ~50 productions, the hand-written parser's error recovery and performance advantages significantly outweigh ANTLR/PEG generators.
The three-phase pipeline (Lexer -> Parser -> Semantic Analyzer) achieves separation of concerns: each phase handles one layer of complexity, reducing overall maintenance burden.
Pratt Parsing elegantly solves operator precedence: precedence-table-driven recursive calls eliminate the need for separate parse functions per precedence level.
Semantic analysis connects to the Ontology Schema: name resolution and type checking validate queries before execution, surfacing errors early.
Friendly error messages are key to user experience: location + expectation + suggestion — these three elements transform error messages from "incomprehensible" to "self-service fixable".

#Next Article

Next up: S3-08 "Query Federation: Unified Cross-Engine Queries" will show how compiled OQL query plans are dispatched to Doris, DuckDB, Elasticsearch, and other engines, enabling a single OQL query to federate across multiple execution backends.

Tags: #OQL #Parser #AST #Lexer #RecursiveDescent #PrattParsing #SemanticAnalysis #TypeChecker #ErrorRecovery #coomia-dip #DataFoundation