LR Parsing of Permutation Phrases
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866929533755588608 |
|---|---|
| author | Kostičová, Jana |
| author_facet | Kostičová, Jana |
| contents | 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(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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_06769 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | LR Parsing of Permutation Phrases Kostičová, Jana Formal Languages and Automata Theory Programming Languages F.4.2; D.3.1; D.3.4 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(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. |
| title | LR Parsing of Permutation Phrases |
| topic | Formal Languages and Automata Theory Programming Languages F.4.2; D.3.1; D.3.4 |
| url | https://arxiv.org/abs/2410.06769 |