# msll

**Repository Path**: will-captain/msll

## Basic Information

- **Project Name**: msll
- **Description**: MSLL (Multi-Stack LL()) is a parsing technique designed to handle complex grammar parsing scenarios with multiple stacks, providing more flexibility and resolving limitations of  LL() parsers.
- **Primary Language**: Java
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2025-04-09
- **Last Updated**: 2025-04-09

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# msll
Traditional LL(1) parsers efficiently handle simple grammatical structures by utilizing a single lookahead symbol. However, their effectiveness diminishes when confronted with complex or highly ambiguous grammars. While LL(k) parsers extend LL(1) capabilities by employing a fixed number of lookahead symbols, they still encounter limitations in parsing intricate and recursive syntactic constructs, often leading to increased complexity as the lookahead depth (k) grows.

To address these challenges, we introduce a novel Multi-Stack LL(*) Parsing method (MSLL) that offers a simpler and more intuitive solution by dynamically managing multiple parsing stacks without relying on complex Deterministic Finite Automata (DFA) constructions and code generation. MSLL preserves all the beneficial outcomes of LL(1) parsers, such as simplicity and ease of implementation, while extending their capabilities to handle more intricate and ambiguous grammars. Instead of constructing DFAs, MSLL duplicates parsing stacks whenever multiple productions match a given token, allowing the parser to explore multiple parsing paths concurrently. This multi-stack approach effectively manages ambiguities and recursive structures by maintaining independent parsing states across stacks.

We detail the MSLL methodology, including stack duplication and advancement, stack elimination and validity detection, and parse tree tagging and cleanup. Through comprehensive experiments, we demonstrate that MSLL successfully parses complex grammars, such as nested JSON objects and code blocks, while maintaining simplicity in grammar design. Although MSLL incurs a little additional memory and computational overhead due to stack duplication, it offers significant flexibility in grammar design and simplifies the parsing process by eliminating the need for intricate DFA constructions and code generation. Furthermore, we analyze the time and space complexities of MSLL, highlighting its suitability for applications where grammar flexibility and implementation simplicity outweigh performance constraints. The paper concludes with a discussion of potential optimizations to mitigate performance drawbacks and suggestions for future research to enhance the efficiency and scalability of the multi-stack approach.