Metraipolis › archive › dc_38cd9da0a36e

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

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.19063
License (as archived)
CC0-1.0
Archived
2026-10-15T17:13:06.126Z
SHA-256 of the archived text
90bb8c7a87661bb4b590ef017afea5b31c5da72ef3ba1402161eb6efdf6ae989
Stable URL of this page
https://metraipolis.com/documento/dc_38cd9da0a36e

How to cite

MSLL: A Runtime Multi-Stack Parsing Approach for Interactive Grammar Development - A Lightweight Extension of LL-Style Recursive Descent — arXiv:2609.19063 — arXiv (en), https://arxiv.org/abs/2609.19063 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_38cd9da0a36e (Metraipolis archive dc_38cd9da0a36e, sha256 90bb8c7a87661bb4b590ef017afea5b31c5da72ef3ba1402161eb6efdf6ae989)
BibTeX
@misc{dc38cd9da0a36e,
  title = {MSLL: A Runtime Multi-Stack Parsing Approach for Interactive Grammar Development - A Lightweight Extension of LL-Style Recursive Descent — arXiv:2609.19063},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.19063},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_38cd9da0a36e; sha256 90bb8c7a87661bb4b590ef017afea5b31c5da72ef3ba1402161eb6efdf6ae989},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.19063. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: calcolo e infrastrutture (retro-catalogo arXiv: annunci del 2026-09-17 in cs.PL).
Categorie arXiv: Programming Languages (cs.PL).
Pagina del lavoro: https://arxiv.org/abs/2609.19063 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-15T16:20:02.302Z dalla pagina https://arxiv.org/catchup/cs.PL/2026-09-17?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).