StepLexer, StepParser and CognitiveGraph — Ambiguity, Zero-Copy, Grammar Switching, Extensions and Grammar Learning

A modern, high-performance lexical analysis and parsing system with comprehensive PCRE2 support and CognitiveGraph integration

StepLexer, StepParser and CognitiveGraph: How They Interact

This report explains, end to end, how the three subsystems of ENFAStepLexer-StepParser cooperate: DevelApp.StepLexer (zero-copy, forward-only ENFA tokenization), DevelApp.StepParser (GLR-style grammar parsing) and the CognitiveGraph (the packed semantic graph built while parsing). It focuses on five topics:

  1. How ambiguous input flows through the pipeline (lexical ambiguity → syntactic ambiguity → packed graph representations).
  2. How zero-copy is designed to work, and where the zero-copy chain is currently broken in the engine/parser/graph path (issue #85 comment).
  3. How the system shifts between grammars and grammar contexts at runtime.
  4. How grammars are extended: inheritance, overlays, and the designed extension-keyed external grammar importers (.g4, .y, .l, …).
  5. What “learning a new grammar” looks like today: the authoring / validation / feedback loop, plus the ML-assist roadmap that is explicitly designed but disabled by default.

All statements are grounded in the current main source; file names are given inline.

1. The Pipeline at a Glance

grammar file ──► GrammarLoader (inheritance, overlays, precedence, projections)
                     │
                     ├──► TokenRules ──► StepLexer (rules, context stack)
                     └──► ProductionRules ──► StepParser (_grammar)
                                              │
string input ──► Encoding.UTF8.GetBytes ──► StepLexer ──► StepToken[] ──► StepParser ──► ParserPaths
                     │                                              │
              LexerPath[] (parallel)                     CognitiveGraphBuilder
                                                          │
                                            Build(root, string sourceText)
                                                          │
                                                  CognitiveGraph (V1/V2)
                                                          │
                                        CognitiveGraphAnalytics (report)

2. StepLexer Under Ambiguity

2.1 Single-position multiple matches → split paths

When more than one token rule matches at the current position, StepLexer.Step() (StepLexer.Matching.cs) does not pick a winner. It calls ProcessMultipleMatches, which clones the current LexerPath once per matching rule and advances each clone independently. The active-path frontier therefore carries all lexical interpretations forward in lockstep.

Key mechanics:

2.2 Path merging (ambiguity containment)

MergePaths (StepLexer.AmbiguityResolution.cs) deduplicates the frontier each step. Two paths merge only when they share position, context and token-type sequence. The token-type sequence is compared via an incrementally maintained fingerprint (LexerPath.GetTokenFingerprint), so the merge check is O(1) amortized per step instead of O(tokens). Fingerprint collisions fall back to an exact sequence comparison, so merging is correct, not merely fast.

2.3 Splittable tokens (within-token ambiguity)

Some tokens are ambiguous inside their own text. The classic case in regex-pattern compilation is an escape like \\x{41}, which might be a two-character escape prefix plus literal, or a full hex escape. In ScanEscapeSequence (StepLexer.Phases.cs) the lexer creates a SplittableToken and attaches alternatives via Split(...). The two-phase regex compiler then resolves it:

So there are two distinct ambiguity layers in the lexer: across tokens (parallel paths, merged) and within a token (splittable alternatives, disambiguated in phase 2).

3. Zero-Copy: How It Works and Where It Breaks

This section answers the issue #85 comment: “how does the zero-copy work. It seems like that has been broken slowing down StepLexer and StepParser as file loaded is the zero-copy version that CognitiveGraph works on.” The short answer: the zero-copy primitives are intact and honored inside the pattern-compilation side of StepLexer, but the hot tokenization path and the entire engine → parser → CognitiveGraph chain materialize strings, so the promised zero-copy behavior does not currently reach the graph. The suspicion in the comment is correct.

3.1 What zero-copy means here

ZeroCopyStringView (ZeroCopyStringView.cs) is a readonly struct wrapping (ReadOnlyMemory<byte> buffer, int start, int length):

The design intent: input arrives once as ReadOnlyMemory<byte> (UTF-8), the lexer walks it forward-only, and every token is a window into that buffer. StepLexer.Initialize(ReadOnlyMemory<byte>, ...) stores the memory without copying and seeds a single path at position 0.

3.2 Where zero-copy is honored today

3.3 Where the chain breaks (the slowdown the comment observed)

Tracing a real StepParserEngine.Parse(string input) call (StepParserEngine.Parsing.cs) end to end:

  1. The engine’s only entry point takes a string and immediately copies it: Encoding.UTF8.GetBytes(input) allocates a full UTF-8 byte array of the entire source before the lexer ever runs. There is no Parse(ReadOnlyMemory<byte>) overload, so a file loaded from disk through the engine is copied at least twice (decode → string, string → bytes). The lexer’s zero-copy Initialize exists but is effectively unreachable through the public engine API.
  2. Every match attempt materializes token text: TryMatchLiteral (StepLexer.Matching.cs) decodes candidate bytes with Encoding.UTF8.GetString(...) to compare against the rule’s string pattern; MatchDigits / MatchIdentifier / MatchWhitespace / MatchMetavariable likewise return string text. This happens per rule, per position, per path — the allocation rate scales with rules × input × paths, not with tokens produced.
  3. PreprocessRegexPattern runs per match attempt: each TryMatchRegex call builds a fresh StringBuilder and (when the pattern has modifiers/comments/atomic groups) a new pattern string. Patterns are not precompiled at grammar-load time, so this cost is paid on the hot path, not once at load.
  4. StepToken carries string Value: ProcessSingleMatch constructs tokens from the materialized match text. Downstream consumers (parser shifts, diagnostics, RealTimeParserSession) therefore hold managed strings for every token, not views into the input buffer.
  5. The parser and the CognitiveGraph work on the string version: StepParser.Initialize(tokens, sourceText) stores _sourceText as a string, and graph construction calls _graphBuilder.Build(rootOffset, _sourceText). The built CognitiveGraph keeps the string as its source of record; SymbolNode.GetSourceText() slices that string. So, inverting the comment’s phrasing: it is not the case that the CognitiveGraph works on the zero-copy version — the graph is built over the materialized string, which is precisely why the zero-copy design does not pay off today.
  6. Incremental sessions inherit the same shape: RealTimeParserSession keeps _source as a string and re-lexes edited ranges through the same string-based matchers.

Net effect: zero-copy exists as an internal data structure of the lexer’s pattern compiler, but the end-to-end pipeline is currently string-based: encode copy → per-match string allocations → string tokens → string-backed graph. This matches the observed slowdown, and the per-match GetString calls in the matchers are the most likely hot-spot (they are on the rules × positions inner loop), ahead of the one-off input encode.

3.4 What restoring the chain would take

Sketch of the remediation direction (for a follow-up issue):

4. StepParser Under Ambiguity (GLR-style)

4.1 Every action is explored

For each parser path and each token, ProcessParserPath (StepParser.GLR.cs) plans all available actions against the unmutated path state:

Multiple possible actions clone the path (remainingActions > 1), exactly one action reuses the path in place — avoiding an O(stack) clone in the common case.

4.2 Ambiguity containment in the parser

4.3 Context-sensitive rules and grammar switching

Both lexer and parser filter rules through the same hierarchical IContextStack:

This is the primary mechanism for “shifting between grammars” at parse time: it is not a grammar swap but a context-gated rule subset of one composed grammar, evaluated per path. Because context is part of the lexer path key and the parser merge key, two regions in different contexts never cross-contaminate.

For static composition of different grammars, see extensions below.

5. CognitiveGraph Construction During Ambiguity

The parser writes the graph as it shifts and reduces (StepParser.GLR.cs):

Note that all node values written here (TokenValue, RuleName) come from the materialized strings discussed in §3.3 — the graph embeds the string-based representation.

CognitiveGraphAnalytics (CognitiveGraphAnalytics.cs) then traverses the graph as a DAG (shared children visited once, fan-out = distinct children) and reports depth, fan-out, ambiguity rate (IsAmbiguous or

1 packed node), source coverage, structural hotspots and a composite 0..1 complexity score. This is the feedback signal for grammar quality.

6. Extensions: How Grammars Are Extended

6.1 Grammar inheritance (Inherits:)

(GrammarLoader.Inheritance.cs)

6.2 Runtime overlays

(GrammarLoader.Overlay.cs, StepParserEngine.Overlay.cs — issue #66)

6.3 Extension-keyed grammar loading (the .extension importer design)

The TDS design document (docs/”ENFAStepLexer-StepParser Enhancements TDS.docx”, section on External Grammar Importers) specifies an extension-based, pluggable importer system for GrammarLoader:

Current implementation status on main: not yet implemented. GrammarLoader.LoadGrammar(filePath) (GrammarLoader.cs) reads any file’s text and parses it as the native grammar format regardless of extension; only Inherits: (and the runtime overlays above) exist. Extends:, %remove and the importers are design-stage, together with the required Grammar_File_Creation_Guide.md documentation mandate the TDS attaches to them.

6.4 Other extension points

7. Learning a New Grammar

“Learning a new grammar” currently means the authoring, validation and feedback loop, not statistical learning:

  1. Author the grammar in the declarative format (Grammar:, TokenSplitter:, token rules, production rules, optional %precedence/%left/%right, contexts, actions). The format is documented in docs/Grammar_File_Creation_Guide.md.
  2. Load it with LoadGrammarFromContent / LoadGrammar. The GrammarLoader parses token and production rules, processes inheritance and overlays, builds precedence tables, and validates rule references — malformed grammars fail fast with ENFA_GrammarBuild_Exception and diagnostic codes, including inheritance cycles and non-inheritable bases.
  3. Configure happens automatically on load: token rules are pushed into a fresh StepLexer, production rules into the StepParser’s _grammar list, default refactoring operations are registered.
  4. Parse with engine.Parse(...) or ParseMultipleFiles(...) (V1/V2 schema; V2 is optimized for massive graphs). Errors and warnings come back in StepParsingResult.
  5. Iterate with feedback:
    • RealTimeParserSession provides incremental editing: ApplyEdit re-lexes only the affected range, reuses tokens outside it, bumps a version and re-parses — ideal for developing a grammar against sample inputs in an editor/IDE loop.
    • CognitiveGraphAnalytics.Analyze(result) quantifies the grammar’s behavior: ambiguity rate and hotspots point at rules that generate excessive parallel parses; source coverage below 1.0 points at tokens the grammar fails to consume; complexity score tracks overall grammar health.

7.1 The ML-assist roadmap (designed, off by default)

Issue #58 / MlAssist.cs define four candidate learned behaviors, all disabled by default and observation-free until a prototype lands:

The contract (MlGuardRailTests-enforced): every feature routes through MlAssistOptions.IsEnabled, enabling requires a model version for reproducibility, and DisableAll / the DEVELAPP_STEPML_DISABLE_ALL environment variable is a runtime escape hatch. ML may never change token boundaries, parse trees or emitted diagnostics — so “learning a grammar” in the statistical sense will influence performance decisions, never parsing results. Note the connection to §3: once the zero-copy chain is restored, LearnedRulePrioritization and LearnedPathPruning plug into a hot loop that is actually cheap to run.

8. Summary of the Interaction Contract

Concern StepLexer StepParser CognitiveGraph
Ambiguity Parallel LexerPath clones + MergePaths fingerprints; SplittableToken alternatives resolved in Phase 2 (longest match) Parallel ParserPaths; shift/reduce/rest all explored; chained reductions; 128-bit stack-signature merging; budgets (32 intra-step, top-10 final) Packed nodes per alternative derivation; AmbiguousRoot (type 300) with ParseCount when several parses complete
Zero-copy Views honored in pattern compilation; hot matchers materialize strings per attempt Operates on string-valued tokens and string _sourceText Built over the string source, not the zero-copy buffer
Grammar switching Context-gated token rules per path Context-gated production rules + preconditions; SwitchGrammarContext pushes a context Node properties record the context each node was built in
Extensions New token rules via overlays/inheritance; PCRE2 constructs normalized in preprocessing New production rules, semantic action handlers, projections, refactoring ops Semantic actions extend graph content at reduce time
Learning a grammar Rules compile into the lexer on load Rules compile into _grammar on load Analytics + ambiguity rate give authoring feedback; ML-assist gates future learned optimization

9. Pointers