V-Star: Learning Visibly Pushdown Grammars from Program Inputs
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866916195414835200 |
|---|---|
| author | Jia, Xiaodong Tan, Gang |
| author_facet | Jia, Xiaodong Tan, Gang |
| contents | Accurate description of program inputs remains a critical challenge in the field of programming languages. Active learning, as a well-established field, achieves exact learning for regular languages. We offer an innovative grammar inference tool, V-Star, based on the active learning of visibly pushdown automata. V-Star deduces nesting structures of program input languages from sample inputs, employing a novel inference mechanism based on nested patterns. This mechanism identifies token boundaries and converts languages such as XML documents into VPLs. We then adapted Angluin's L-Star, an exact learning algorithm, for VPA learning, which improves the precision of our tool. Our evaluation demonstrates that V-Star effectively and efficiently learns a variety of practical grammars, including S-Expressions, JSON, and XML, and outperforms other state-of-the-art tools. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_04201 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | V-Star: Learning Visibly Pushdown Grammars from Program Inputs Jia, Xiaodong Tan, Gang Programming Languages Formal Languages and Automata Theory Accurate description of program inputs remains a critical challenge in the field of programming languages. Active learning, as a well-established field, achieves exact learning for regular languages. We offer an innovative grammar inference tool, V-Star, based on the active learning of visibly pushdown automata. V-Star deduces nesting structures of program input languages from sample inputs, employing a novel inference mechanism based on nested patterns. This mechanism identifies token boundaries and converts languages such as XML documents into VPLs. We then adapted Angluin's L-Star, an exact learning algorithm, for VPA learning, which improves the precision of our tool. Our evaluation demonstrates that V-Star effectively and efficiently learns a variety of practical grammars, including S-Expressions, JSON, and XML, and outperforms other state-of-the-art tools. |
| title | V-Star: Learning Visibly Pushdown Grammars from Program Inputs |
| topic | Programming Languages Formal Languages and Automata Theory |
| url | https://arxiv.org/abs/2404.04201 |