Fast Deterministic Black-box Context-free Grammar Inference

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 differe...

Full description

Saved in:
Bibliographic Details
Main Authors: Arefin, Mohammad Rifat, Shetiya, Suraj, Wang, Zili, Csallner, Christoph
Format: Conference Proceeding
Language:English
Subjects:
bracket-implied nesting structure
Closed box
Computing methodologies > Machine learning > Learning settings > Active learning settings
deterministic synthesis
Grammar
Grammar inference
nested language concepts
oracle
Runtime
Software and its engineering > Software creation and management > Software post-development issues > Software reverse engineering
Software and its engineering > Software notations and tools > Formal language definitions > Syntax
Software and its engineering > Software notations and tools > Software maintenance tools
Source coding
Theory of computation > Formal languages and automata theory > Grammars and context-free languages
Training data
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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).
ISSN:1558-1225
DOI:10.1145/3597503.3639214