Parser Architecture

Fresh

Deep dive into the MD-LD parser internals. For contributors and those implementing MD-LD in other languages.

Overview

The MD-LD parser implements a single-pass, streaming-friendly architecture that transforms Markdown with semantic annotations into RDF/JS quads while maintaining complete provenance and supporting elevated statements extraction.

Character-Based Tokenization

The parser uses a unified character-based tokenization system for optimal performance:

// src/tokenizers.js - Centralized tokenization logic
export function detectFence(line)             // ```code blocks
export function detectPrefix(line)            // [prefix] <uri>
export function detectHeading(line)           // # Headings
export function detectList(line)              // - List items
export function detectBlockquote(line)        // > Blockquotes
export function detectStandaloneSubject(line) // {=subject}
export function scanInlineCarriers(text)      // [text], **bold**, `code`, <URL>

Performance benefits:

• 20-28% faster parsing than regex-based approaches
• Memory-efficient with ~640 bytes per quad retained
• O(n) linear time complexity maintained
• Better error handling with precise edge case detection

Parser State Object

const state = {
    ctx: {},                    // Prefix context for IRI expansion
    df: DataFactory,            // RDF/JS DataFactory instance
    quads: [],                  // Final resolved graph state
    quadBuffer: new Map(),      // Current parsing buffer
    removeSet: new Set(),       // External retractions
    origin: {
        quadIndex: new Map(),   // Lean quad provenance
        blocks: new Map(),      // Semantic anchors
        spans: new Map(),       // Textual topology
        documentStructure: []
    },
    currentSubject: null,       // Current subject context
    primarySubject: null,       // First non-fragment subject declaration
    primaryType: null,          // First rdf:type declaration
    primaryLabel: null,         // First rdfs:label literal
    primaryComment: null,       // First rdfs:comment literal
    tokens: null,               // Tokenized input
    currentTokenIndex: -1,      // Current processing position
    statements: [],             // Elevated statements array
    statementCandidates: new Map(), // Incomplete rdf:Statement patterns
    lastBlockEnd: 0,            // Byte position after last block
    lastBlockId: null,          // ID of previous block
    lastSpanId: null            // ID of previous span
};

State Component Lifecycle

Component	Purpose	Lifecycle
ctx	Prefix mappings for IRI expansion	Persistent, updated during prefix processing
quads	Final graph output	Accumulated throughout parsing
quadBuffer	Intra-document cancel tracking	Modified during quad emission
removeSet	External retractions	Accumulated for removal operations
origin	Provenance tracking	Updated with each block and quad
currentSubject	Subject context management	Reset and updated during parsing
primarySubject	First non-fragment subject	Set once, never changed
statements	Elevated statements	Accumulated during pattern detection
statementCandidates	Pattern completion tracking	Modified during rdf:Statement detection

Token Types

const TOKEN_TYPES = {
    heading:    'heading',    // ## Heading {=ex:subject .type}
    para:       'para',       // Paragraph with annotations
    list:       'list',       // - List item {+ex:predicate}
    blockquote: 'blockquote', // > Quote {ex:property}
    code:       'code',       // ```code {=ex:codeblock}
    prefix:     'prefix',     // [prefix] <uri>
    fence:      'fence'       // Code block delimiters
};

Processing Pipeline

Phase 1: Tokenization

Line-by-line scanning creates tokens with character ranges for every construct.

Phase 2: Prefix Processing

All prefix declarations are resolved first in a single pass. CURIEs are expanded to absolute IRIs using the accumulated context.

Phase 3: Semantic Processing

for (let i = 0; i < tokens.length; i++) {
    const token = tokens[i];
    state.currentTokenIndex = i;

    // Process token using appropriate processor
    TOKEN_PROCESSORS[token.type]?.(token, state);
}

Phase 4: Final Resolution

// Process retractions and ensure hard invariant: quads ∩ remove = empty set
const filteredRemove = processRetractions(state.quads, state.removeSet);

// Create structured primary object for semantic surface
const primary = {
    subject: state.primarySubject,
    type:    state.primaryType,
    label:   state.primaryLabel,
    comment: state.primaryComment
};

return {
    quads:          state.quads,          // Final resolved graph state
    remove:         filteredRemove,       // External retractions only
    statements:     state.statements,     // Elevated statements
    origin:         state.origin,         // Complete provenance
    context:        state.ctx,            // Final prefix context
    primarySubject: state.primarySubject, // Canonical append identity
    primary,                              // Semantic surface descriptor
    md:             scanResult.md         // Clean markdown without annotations
};

Retraction System

Retractions are first-class citizens in MD-LD. The system enforces a hard invariant: quads ∩ remove = empty set.

Retraction Types

Type	Description
INTRA_DOCUMENT	Cancel within same document — both assertion and retraction disappear
EXTERNAL_RETRACT	Remove from prior state — stored in remove array

Retraction Processing

function processRetraction(quad, quadBuffer, removeSet, quads) {
    const quadKey = quadIndexKey(quad.subject, quad.predicate, quad.object);

    if (quadBuffer.has(quadKey)) {
        // Intra-document cancel: remove from current state
        quadBuffer.delete(quadKey);
        removeFromQuadsArray(quads, quad);
    } else {
        // External retract: target prior document state
        removeSet.add(quad);
    }
}

Polarity Forms

Form	Positive	Negative	Use Case
p	{p}	{-p}	Literal properties
?p	{?p}	{-?p}	Object properties
!p	{!p}	{-!p}	Reverse properties
.Class	{.Class}	{-.Class}	Type declarations

Elevated Statements Detection

The parser detects rdf:Statement patterns in a single pass:

function detectStatementPatternSinglePass(quad, dataFactory, meta, statements, statementCandidates) {
    // Only process rdf:Statement related predicates (optimized)
    if (!isRDFStatementPredicate(quad.predicate.value)) return;

    // Start new pattern: rdf:type rdf:Statement
    if (isStatementType(quad)) {
        statementCandidates.set(quad.subject.value, { spo: {} });
        return;
    }

    // Complete pattern parts: rdf:subject, rdf:predicate, rdf:object
    const candidate = statementCandidates.get(quad.subject.value);
    if (candidate) {
        updatePattern(candidate, quad);

        // Create elevated SPO when pattern complete
        if (isPatternComplete(candidate)) {
            const elevatedQuad = createElevatedQuad(candidate, dataFactory);
            statements.push(elevatedQuad);
            statementCandidates.delete(quad.subject.value);
        }
    }
}

When a node has rdf:type rdf:Statement plus rdf:subject, rdf:predicate, and rdf:object properties, the elevated SPO triple is automatically extracted into result.statements.

Primary Metadata Extraction

The parser tracks four primary fields during single-pass parsing:

// Track primary subject: first non-fragment subject declaration
if (newSubject && !state.primarySubject && !sem.subject.startsWith('=#')) {
    state.primarySubject = newSubject.value;
}

// Track primary type, label, and comment during quad emission
if (!state.primaryType && predicate.value === RDF_TYPE) {
    state.primaryType = object.value;
}
if (!state.primaryLabel && predicate.value === RDFS_LABEL && object.termType === 'Literal') {
    state.primaryLabel = object.value;
}
if (!state.primaryComment && predicate.value === RDFS_COMMENT && object.termType === 'Literal') {
    state.primaryComment = object.value;
}

Primary Metadata Applications

Field	Source	Purpose
primarySubject	First {=subject}	Document identity, storage routing
primaryType	First .Class	Stream filtering, UI categorization
primaryLabel	First {label}	Display titles, search indexing
primaryComment	First {comment}	UI descriptions, tooltips

Origin Tracking

Each quad emission creates an origin entry in quadIndex:

const originEntry = {
    blockId:     'block-identifier',  // Unique block identifier
    range:       [start, end],        // Source location (character range)
    carrierType: 'para',              // Token type
    subject:     'ex:subject',        // Subject IRI
    predicate:   'ex:predicate',      // Predicate IRI
    context:     { ...block.context },// Prefix context at parse time
    polarity:    '+',                  // '+' for add, '-' for remove
    value:       'source text'        // Original carrier content
};

Carrier Extraction

Carrier Types

Type	Syntax	Example
link	[text]	[Alice] {my:name}
emphasis	**text** or *text*	**Alice** {my:name}
code	`text`	`v1.2.0`
bracket	<url>	<https://example.org>

Performance Optimizations

Applied optimizations in the parser implementation:

1. Token Processing — Single loop instead of filter+forEach
2. Regex Pre-compilation — Pre-compiled carrier patterns
3. String Operations — Optimized fragment resolution
4. Array Operations — Direct iteration instead of Array.from()+filter()
5. Object Creation — Reduced spread operator usage
6. Early Filtering — Only process rdf:Statement related predicates
7. Module Constants — RDF constants defined once at module level

Error Recovery

// Graceful degradation for malformed input
if (!isValidAnnotation(attrs)) {
    // Log warning and continue processing
    return;
}

// Safe navigation for optional properties
const subject = resolveSubject(sem.subject, state) || skipProcessing();

The parser continues processing after encountering invalid annotations rather than throwing immediately, allowing partial results from malformed documents.