2024/10/09 by Jana Kostičová, Kostičová, Jana
Biochemistry, Genetics and Molecular Biology · Computer Science · #D.3.1 #D.3.4 #DNA and Biological Computing #F.4.2 #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Natural Language Processing Techniques #Programming Languages (cs.PL) #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2410.06769
openalex publication_date 2024/10/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 Ω(n!) to O(2n), 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.