Document Type
Article
Source Publication Title
2024 IEEE/ACM 46th International Conference on Software Engineering
DOI
https://dl.acm.org/doi/10.1145/3597503.3639214
Abstract
Black-box context-free grammar inference is a hard problem as in many practical settings it only has access to a limited number of example programs. The state-of-the-art approach Arvada heuristically generalizes grammar rules starting from flat parse trees and is non-deterministic to explore different generalization sequences. We observe that many of Arvada’s generalization steps violate common language concept nesting rules. We thus propose to pre-structure input programs along these nesting rules, apply learnt rules recursively, and make black-box context-free grammar inference deterministic. The resulting TreeVada yielded faster runtime and higher-quality grammars in an empirical comparison. The TreeVada source code, scripts, evaluation parameters, and training data are open-source and publicly available (https://doi.org/10.6084/m9.figshare.23907738).
Publication Date
4-12-2024
Language
English
License
This work is licensed under a Creative Commons Attribution 4.0 International License.
Recommended Citation
Arefin, Mohammad Rifat; Shetiya, Suraj; Csallner, Christoph; and Wang, Zili, "Fast Deterministic Black-box Context-free Grammar Inference" (2024). Association of Computing Machinery Open Access Agreement Publications-Archive. 82.
https://mavmatrix.uta.edu/utalibraries_acmoapubs/82