LR Parsing of Permutation Phrases
<|reference_start|>LR Parsing of Permutation Phrases: This paper presents an efficient method for LR parsing of permutation phrases. In practical cases, the proposed algorithm constructs an LR(0) automaton that requires significantly fewer states to process a permutation phrase compared to the standard construction. For most real-world grammars, the number of states is typically reduced from $\Omega(n!)$ to $O(2^{n})$, resulting in a much more compact parsing table. The state reduction increases with longer permutation phrases and a higher number of permutation phrases within the right-hand side of a rule. We demonstrate the effectiveness of this method through its application to parsing a JSON document.<|reference_end|>
@article{kostičová2024lr,
    title={LR Parsing of Permutation Phrases},
    author={Jana Kostiv{c}ov'a},
    journal={arXiv preprint arXiv:2410.06769},
    year={2024},
    archivePrefix={arXiv},
    eprint={2410.06769},
    primaryClass={cs.FL cs.PL}
}