PaperlayerView exact revision on arXiv

Source-linked AI summary

MSLL: A Runtime Multi-Stack Parsing Approach for Interactive Grammar Development - A Lightweight Extension of LL-Style Recursive Descent

Qunhui Zhang

arXiv:2609.19063v1cs.PL

TL;DR

Grammar authors often need to try overlapping rules before settling the grammar, but parser-generation workflows add friction to interactive development. MSLL runs an evolving ANTLR-style grammar by keeping and pruning runtime stacks for competing alternatives. The reported results show a small gap from baselines at 1k tokens that grows with input size, supporting its role as an exploration tool rather than a replacement for generated parsers.

  • Problem

    During grammar development, overlapping alternatives and generation, compilation, and IDE-refresh steps make it less comfortable to test a rule before refactoring.

    Source: §1 · p. 2

  • Method

    MSLL runs recursive-descent LL parsing with one active stack per unresolved prediction alternative, pruning stacks when input contradicts them.

    Source: §4.1 · p. 7

  • Results

    The MSLL-baseline gap is barely visible at 1k tokens, noticeable at 50k, and large enough to matter at 500k.

    Source: §8.5 · p. 22

  • Takeaways & Limitations

    MSLL is a temporary grammar-exploration mode; stabilized grammars should move to a generated parser.

    Source: §8.5 · p. 22, §9 · p. 24

    MSLL is limited by stack growth, lack of fine-grained incremental parsing, limited error recovery, incomplete formalization, and partial support for the full ANTLR grammar language.

    Source: §12.1 · p. 26

Abstract

from arXiv · show

Few grammars are designed in a straight line. During grammar prototyping, authors often want to run a partially settled rule before refactoring overlapping alternatives or regenerating parser code. Predictive parsers are effective for stable grammars, but their generation and compilation loop can slow down interactive grammar development. This paper presents MSLL, a lightweight runtime extension of recursive-descent LL parsing for edit-time grammar exploration. When a FIRST/FIRST conflict appears, MSLL keeps multiple live parsing stacks, lets each stack follow a different candidate production, and prunes a stack as soon as the input contradicts it. Ambiguity is therefore handled as a runtime state-management problem rather than as a condition that must be removed before execution. The prototype targets an ANTLR-style grammar workflow: run and inspect an evolving grammar directly, collect conflict traces, and later translate or adapt the stabilized grammar for a generated parser. Experiments on DSL-style workloads show that MSLL finishes three 1k-token benchmarks in 48, 49, and 59 ms; stays under one second on two ambiguous 50k-token workloads; and reaches 5.395 s on a 500k-token deeply nested stress case. A real-world JSON grammar case confirms interactive behavior on small and medium inputs while exposing prototype-level super-linear overhead at 500k tokens. The results position MSLL as a development-time companion to existing LL-based parser generators rather than a replacement for production parsers.

1. Introduction

MSLL targets grammar exploration, where overlapping alternatives and parser regeneration slow experimentation, by running evolving ANTLR-style grammars with competing runtime stacks. The paper specifies and implements this approach for a limited grammar dialect, discusses its correctness and stack-growth boundary, and evaluates it against parser baselines.

1. Introduction

  • Grammar prototyping is slowed by overlapping alternatives and workflows that require parser generation, compilation, or an IDE refresh before feedback.LL(k) requires fixed lookahead, while ANTLR's adaptive LL(*) uses generated prediction machinery.Source: §1 · p. 2

2. Contributions

  • MSLL forks one stack per candidate production at a FIRST/FIRST conflict, then records where branches fail so authors can inspect traces before rewriting rules.It avoids a generation step between grammar and execution and does not build a shared packed parse forest.Source: §2 · p. 3
  • The prototype supports a limited ANTLR-style grammar dialect and specifies operational behavior, correctness arguments, and stack-growth limits.The workflow is to use MSLL while a grammar is volatile, then translate or adapt the stabilized grammar for a generated parser.Source: §2 · p. 3, §1 · p. 3
  • The evaluation compares a Java prototype on three DSL-style workloads with rewritten LL(1) and generated ANTLR baselines, and adds a real-input JSON grammar case.Reported measures include wall-clock time, heap footprint, cumulative stack allocations, and peak live-stack counts.Source: §2 · pp. 3–4
  • The paper relates MSLL to language-tooling practice, including parser generators, incremental parsing, error-tolerant parsers, parallel parsing, and textual DSL workbenches [12] [13] [19] [21] [24] [25] [26]..Source: §2 · p. 4

3. Related Work

The related-work discussion places MSLL between predictive, adaptive, and generalized parsing approaches, with its focus on directly inspecting ambiguous grammar behavior during design. It also distinguishes grammar editing from source editing and notes that its correctness argument is not mechanized.

3.1. Predictive LL Parsing

  • LL(1) requires disambiguated grammars, LL(k) fixes lookahead depth, and ANTLR adaptive LL(*) uses generated prediction machinery; MSLL instead runs overlapping alternatives during design.The goal is a temporary inspection mode, not displacement of optimized generated parsers.Source: §3.1 · pp. 4–5

3.2. Dynamic and Adaptive LL Parsing

  • MSLL keeps viable top-down paths as runtime values and prunes contradicted paths, rather than computing a lookahead bound or resolving grammar classes up front..Source: §3.2 · p. 5

3.3. Generalized Parsing Algorithms

  • Unlike GLR/GLL, MSLL uses plain copied stacks, interprets the grammar directly, and returns fork-and-prune traces rather than a parse forest [31].It gives up worst-case efficiency guarantees provided by graph-structured-stack sharing.Source: §3.3 · p. 5

3.4. Parsing Expression Grammars and Combinators

  • PEGs resolve ambiguity through ordered choice, whereas MSLL keeps alternatives visible until input rejects them, aiding inspection of overlapping productions..Source: §3.4 · p. 6

3.5. Incremental and Interactive Parsing Tools

  • Tree-sitter and Lezer optimize reparsing after source edits, while MSLL targets grammar edits, where a cached tree for the old grammar is less useful.Language-workbench studies report that grammars, metamodels, and examples often evolve together in small steps [13] [19] [21].Source: §3.5 · p. 6

3.6. Correctness and Verification

  • MSLL has no mechanized proof; it offers an operational argument that surviving stacks represent valid partial derivations and pruning removes contradicted paths..Source: §3.6 · pp. 6–7

3.7. Summary

  • MSLL occupies a middle ground between full generalized parsing and static LL generation, emphasizing transparent debugging of ambiguous alternatives..Source: §3.7 · p. 7
  • MSLL's explicit conflict traces serve grammar inspection, but persistent ambiguity can increase the number of live stacks..Source: §3.3 · p. 5, §3.7 · p. 7

4. MSLL Algorithm

MSLL extends recursive-descent LL parsing by maintaining active stacks for competing productions and pruning stacks when input contradicts them. It accepts only a unique complete parse and argues soundness and relative completeness for derivations admitted by its prediction relation.

4.1. Overview

  • At an ambiguous prediction, MSLL forks the active stack for each admitted production and prunes a branch when a terminal or prediction contradicts it.A deterministic prediction is applied in place; success requires exactly one stack to consume the full input with no remaining symbols.Source: §4.1 · p. 7, §4.2 · p. 8

4.2. Parsing Procedure

  • Each active stack carries expected grammar symbols, an input position, and a partial parse tree; terminal matches advance the position, while mismatches terminate that stack.Prediction lookup returns productions whose FIRST/FOLLOW information admits the current lookahead.Source: §4.2 · pp. 7–8, §4.3 · p. 9

4.3. Formal Specification

  • The formal specification defines success as one complete stack; zero or multiple complete stacks yield failure or residual ambiguity.For multiple admitted productions, the stack is duplicated into continuations, each following one right-hand side.Source: §4.3 · p. 9

4.4. Correctness of MSLL

  • The correctness argument says returned trees use legal grammar steps and admitted compatible derivations retain a corresponding stack until success or contradiction.It is scoped to the supported top-down subset and implemented prediction relation; persistent ambiguity can grow the stack count, while local conflicts may be pruned quickly.Source: §4.4 · pp. 9–10

4.5. Formal Pseudocode of MSLL

  • The pseudocode initializes one start-symbol stack, advances active states by terminal match or prediction, clones for multiple candidates, and returns a unique complete state or failure/ambiguity..Source: §4.5 · p. 11

5. System Design and Architecture

The runtime separates grammar processing, tokenization, prediction, stack management, and parse-tree assembly to support direct execution of evolving grammars. Its traces expose conflicts and pruning events for inspection.

5. System Design and Architecture

  • The runtime separates grammar loading, tokenization, prediction lookup, active-stack management, and parse-tree assembly into inspectable components.The same grammar structure can be reused when preparing an equivalent grammar for a generated parser.Source: §5 · p. 11

5.1. Key Components

  • The lexer scans once and records token offsets, while the parser drives top-down expansion using a prediction table and a stack manager.These components respectively provide candidate productions and allocate, clone, schedule, and prune stacks.Source: §5.1 · p. 11

5.2. Processing Pipeline

  • Conflicts surface through active-stack traces and pruning events; fixed-order scheduling makes runs over the same grammar yield the same trace.Clones share immutable grammar metadata but keep their own symbol lists, input positions, and tree fragments; the stack scheduler could be parallelized without changing the algorithm.Source: §5.2 · p. 12

6. Implementation

MSLL executes evolving ANTLR-style grammars directly, retaining competing runtime stacks at conflicts and exposing their pruning traces. Its implementation supports a bounded grammar dialect and uses optimizations to limit work on deterministic regions.

6.1. Grammar Compatibility

  • MSLL supports grouping, repetition, alternatives, and terminal and non-terminal references, but not direct left recursion or full ANTLR semantic predicates; stabilized grammars may need adaptation for ANTLR.Its separate parser/lexer files and regular-expression lexer syntax mean compatibility is structural, not direct file portability.Source: §6.1 · p. 13

6.2. Parsing Pipeline

  • The pipeline builds runtime prediction entries from FIRST sets, retains multiple productions at conflicts, and forks stacks whose failed branches are pruned with their failure positions recorded.Successful parses return an annotated AST and conflict trace; failures report where all stacks were pruned.Source: §6.2 · p. 14

6.3. Parser Initialization

  • Grammar loading and prediction-table construction occur when the parser is created, and edits reload the grammar and rebuild runtime tables without generating Java parser source.The API supplies parser and lexer grammar files before parsing a source snippet.Source: §6.3 · p. 14

6.4. Optimizations

  • Greedy-first evaluation, lazy pruning, and immutable parse-tree prefix sharing reduce allocation and copying while preserving competing alternatives where ambiguity exists.Together, these optimizations let MSLL behave like ordinary LL parsing on unambiguous fragments.Source: §6.4 · p. 15

6.5. Example Demonstration

  • The brace-delimited example traces two alternative branches and shows the branch pruned when its next expected terminal fails to match.The figure illustrates runtime conflict handling through a fork followed by pruning.Source: §6.5 · p. 15, Figure 2 · p. 15

7. Evaluation

The evaluation tests correctness, runtime overhead, stack growth, and edit-loop cost across controlled DSL workloads and a real-world JSON grammar. Results show low-cost deterministic parsing and interactive behavior on smaller real inputs, but substantial prototype overhead on the largest real input.

7. Evaluation

  • The evaluation separates correctness, runtime overhead, and edit-loop cost to identify the useful operating range of runtime ambiguity handling.It compares returned parse trees with expected structures, measures time, memory and stack counts, and measures latency after a small rule edit.Source: §7 · p. 16

7.1. Evaluation Goals

  • The evaluation asks whether MSLL returns expected trees, how its time and heap overhead compare with LL(1) and ANTLR as inputs grow, and how stacks scale.It also measures cumulative and peak stack counts on deeply nested ambiguous inputs.Source: §7.1 · p. 16

7.2. Experimental Setup

  • Measurements used warmed parsers and fixed configurations for comparisons within each case, while the real-world JSON case ran on different hardware and JVM.ANTLR parsers were generated before timing; MSLL loaded its equivalent runtime-dialect grammar directly.Source: §7.2 · pp. 16–17

7.3. Case 1: Multi-Layer Code Blocks and JSON Structures

  • MSLL stays within the intended interactive range on nested code-block and JSON workloads, with low active-stack counts because conflicting alternatives are pruned within a few tokens.Table 1 reports parsing results for multi-layer code blocks and JSON structures.Source: Table 1 · p. 17, §7.3 · p. 18

7.4. Case 2: Pathological Ambiguity (Repeated Deep Nesting)

  • The repeated-deep-nesting stress test peaks at 33 simultaneous stacks, exposing duplication costs that grammar authors would need to control before production deployment.Table 2 reports parsing results for repeated deep nesting.Source: §7.4 · p. 18, Table 2 · p. 18

7.5. Case 3: Flat Deterministic Grammar

  • MSLL tracks LL(1) closely whenever prediction is deterministic and no stack fork is needed; Table 3 reports parsing results for a flat deterministic grammar.Source: §7.5 · p. 18, Table 3 · p. 19

7.6. Case 4: A Real-World JSON Grammar on Real Inputs

  • 85 s versus 172 ms at 500k tokens; on the real JSON grammar, MSLL takes 6.6 ms at 1.2k tokens and about one second at 50k.At 500k tokens the peak stack count remains four, and the passage attributes the super-linear cost to per-fork bookkeeping rather than stack duplication.Source: §7.6 · pp. 19–20, Table 4 · p. 20

7.7. Threats to Validity

  • Three controlled workloads are synthetic and one real-world grammar cannot represent production-language variety; the editing-session evidence comes from one author and one grammar.Cases 1–3 and Case 4 were measured on different machines, so their absolute values should not be compared across that boundary.Source: §7.7 · p. 20

8. Experimental Result Analysis

MSLL’s performance is most suitable for interactive grammar exploration, with costs rising as ambiguity and input size increase. The proposed workflow moves stabilized grammars to generated parsers for production.

8.1. Small Code Sizes (<~1k tokens): Low Conflict, Fast Iteration

  • At small input sizes, MSLL, LL(1), and ANTLR have roughly similar perceptual latency, with bookkeeping—not exponential path growth—dominating MSLL overhead.Only a small number of duplicate stacks are created.Source: §8.1 · p. 20

8.2. Moderate Code Sizes (~50k tokens): Balanced Ambiguity and Depth

  • On ambiguous 50k-token workloads, MSLL trails ANTLR and LL(1) but still finishes in under one second.The high-ambiguity workload peaks at 33 live stacks, increasing time and heap use.Source: §8.2 · p. 21

8.3. Large Code Sizes (~500k tokens): Deep Recursion and High Ambiguity

  • Deep ambiguity can produce hundreds of thousands of total stack instances at 500k tokens, marking a limit for the approach.The simultaneous maximum remains much smaller; duplication is a cost to control before production deployment.Source: §8.3 · p. 21

8.4. Suggested Workflow Integration

  • The workflow uses MSLL while grammar rules are changing, then translates and validates a stabilized grammar for ANTLR generation and production deployment.ANTLR remains the better production choice when the grammar is stable and large inputs dominate.Source: §8.4 · pp. 21–22

8.5. Summary

  • At 1k tokens the Case 2 gap is barely visible, at 50k it becomes noticeable, and at 500k it is large enough to matter.Figure 3 plots the three Case 2 points from Table 2.Source: §8.5 · p. 22, Figure 3 · p. 22

9. Interactive-Debugging Experience

The section compares MSLL’s live grammar refresh with ANTLR’s generation-and-compilation cycle during repeated edits. Its editing-session evidence is illustrative, not a user-study claim.

Interactive refresh

  • MSLL reloads an edited grammar in memory and updates the parse preview, while the ANTLR cycle requires regeneration, compilation, and returning to the preview.The comparison quantifies latency, tool interactions, and generated-file counts across five successive grammar changes.Source: §9 · p. 23

Evidence scope

  • The five-edit session is an illustrative observation involving one author and one grammar, not a controlled experiment.The edits included adding a literal rule, changing delimiters, and renaming a non-terminal.Source: §9 · pp. 23–24

Transition to generation

  • Once the grammar settles, an equivalent .g4 grammar goes to ANTLR after compatibility checking and any needed syntax adaptation.The edit-time MSLL cycle removes the regeneration ritual from exploratory work.Source: §9 · p. 24

10. Complexity Analysis

MSLL’s time and space costs depend on how many alternative stacks remain live. Deterministic regions behave like ordinary LL parsing, while deep, persistent ambiguity can increase duplication.

10.1. Time Complexity

  • Time scales with active stacks x and input length n; x can reach b^d when branching persists across d unresolved conflicts.Local ambiguity can keep x small through pruning, whereas deep ambiguity with long-lived alternatives can make it grow exponentially.Source: §10.1 · pp. 24–25
  • Each live stack may simulate a parse over the remaining input, but MSLL does not restart from the beginning; stack duplication remains a real cost.Conflict tracing is part of the proposed workflow so grammar authors can see where branching occurs.Source: §10.1 · p. 25

10.2. Space Complexity

  • Space accounts for active-stack depth and auxiliary parse-tree state; prefix sharing reduces copying but cannot remove costs from branches that remain indistinguishable.The grammar itself is stored once and shared across branches.Source: §10.2 · p. 25

10.3. Complexity Summary

  • MSLL trades deterministic speed for edit-time flexibility, making it sensible for grammar prototyping, DSL editing, teaching interpreters, and embedded parsing when a short feedback loop outweighs the fastest steady-state parsing.Source: §10.3 · p. 25

11. Discussion

MSLL is a phase-specific choice: it favors edit-time grammar flexibility over deterministic speed, then yields to generated or adaptive parsers for production. Its traces expose conflicts before generated parser source exists.

11. Discussion

  • MSLL is aimed at the interval after a grammar file changes but before generated parser source exists, rather than replacing incremental parsing tools for source-file edits.The discussion says visible stack traces can show non-specialist authors where rules collide, such as on a brace, keyword, or expression prefix.Source: §11 · p. 26

12. Limitations and Future Work

MSLL’s limitations include stack growth, lack of incremental parsing and integrated recovery, incomplete formalization, and partial ANTLR support. Future work prioritizes practical performance and feedback improvements for grammar-development settings.

12.1. Limitations

  • Deep ambiguity can spawn exponentially many paths, with nested object-like inputs generating tens of thousands of stack instances.Greedy-first evaluation and lazy pruning tame common cases, but the theoretical worst case remains.Source: §12.1 · pp. 26–27
  • Every invocation reparses from scratch, making persistent tree and stack fragments necessary for large editor buffers.The reported small grammar-prototyping runs are considered suitable for this current limitation.Source: §12.1 · p. 27
  • When all stacks fail, the prototype reports failure rather than building a partial tree.The operational soundness and completeness arguments are not mechanized, particularly around pruning and shared tree nodes.Source: §12.1 · p. 27

12.2. Future Work

  • Case 4’s super-linear cost on long real inputs calls for profiling per-fork work before the prototype can remain interactive beyond mid-sized files.The peak stack count stays constant in this case.Source: §12.2 · p. 27
  • Conflict-bounded execution could retain only promising stacks when ambiguity runs too deep, trading completeness for bounded interactivity.Suggested ranking signals include token progress, production priority, or grammar annotations.Source: §12.2 · p. 27
  • Parallel stack evaluation and persistence across small edits are proposed to improve execution and avoid reparsing unchanged prefixes.Parallel evaluation would require coordinating pruning and shared parse-tree prefixes.Source: §12.2 · p. 27
  • Token insertion, deletion, synchronization, or rule skipping could let MSLL return useful partial trees in editor settings.These recovery mechanisms address the current failure behavior when every stack fails.Source: §12.1 · p. 27, §12.2 · p. 28
  • IDE integration would test whether conflict traces help grammar authors decide how to refactor, while better ambiguity feedback is the key next step.The proposed settings include VS Code, IntelliJ, or a web workbench.Source: §12.2 · p. 28

13. Conclusions

MSLL is an edit-time parsing mode for ANTLR-style grammars that lets authors inspect ambiguous behavior while syntax is evolving. Its intended role is exploratory: use it during design, then adapt a stabilized grammar for production parsing.

13. Conclusions

  • MSLL reads an ANTLR-style grammar directly, forks runtime stacks for unresolved alternatives, and discards branches as token evidence rules them out.This keeps grammar experiments in the editor loop rather than routing each small change through grammar rewriting or parser regeneration.Source: §13 · p. 28
  • Deterministic inputs cost little extra, and moderate ambiguity stays comfortable for short and medium inputs.Deeply nested ambiguity can keep many alternatives alive, so such grammars should be factored, bounded, or moved to a generated parser once stable.Source: §13 · p. 28
  • The intended workflow uses MSLL while syntax decisions are in motion, then checks and, if necessary, adapts the stable grammar for a production parser toolchain.The paper frames MSLL as a way to watch ambiguous behavior, collect conflict traces, and revise syntax decisions—not as a competitor to generated parsers.Source: §13 · p. 28
Loading 2609.19063v1…