Incremental Context-free Grammar Inference in Black Box Settings
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866917780114112512 |
|---|---|
| author | Li, Feifei Chen, Xiao Xiao, Xi Sun, Xiaoyu Chen, Chuan Wang, Shaohua Han, Jitao |
| author_facet | Li, Feifei Chen, Xiao Xiao, Xi Sun, Xiaoyu Chen, Chuan Wang, Shaohua Han, Jitao |
| contents | Black-box context-free grammar inference presents a significant challenge in many practical settings due to limited access to example programs. The state-of-the-art methods, Arvada and Treevada, employ heuristic approaches to generalize grammar rules, initiating from flat parse trees and exploring diverse generalization sequences. We have observed that these approaches suffer from low quality and readability, primarily because they process entire example strings, adding to the complexity and substantially slowing down computations. To overcome these limitations, we propose a novel method that segments example strings into smaller units and incrementally infers the grammar. Our approach, named Kedavra, has demonstrated superior grammar quality (enhanced precision and recall), faster runtime, and improved readability through empirical comparison. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_16706 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Incremental Context-free Grammar Inference in Black Box Settings Li, Feifei Chen, Xiao Xiao, Xi Sun, Xiaoyu Chen, Chuan Wang, Shaohua Han, Jitao Programming Languages Software Engineering Black-box context-free grammar inference presents a significant challenge in many practical settings due to limited access to example programs. The state-of-the-art methods, Arvada and Treevada, employ heuristic approaches to generalize grammar rules, initiating from flat parse trees and exploring diverse generalization sequences. We have observed that these approaches suffer from low quality and readability, primarily because they process entire example strings, adding to the complexity and substantially slowing down computations. To overcome these limitations, we propose a novel method that segments example strings into smaller units and incrementally infers the grammar. Our approach, named Kedavra, has demonstrated superior grammar quality (enhanced precision and recall), faster runtime, and improved readability through empirical comparison. |
| title | Incremental Context-free Grammar Inference in Black Box Settings |
| topic | Programming Languages Software Engineering |
| url | https://arxiv.org/abs/2408.16706 |