A survey of grammatical inference in software engineering

• We survey grammatical inference as it relates to software engineering.
• A background on the theory of grammatical inference is provided.
• We explore a variety of applications in software engineering.
• These include programming languages, DSLs, visual languages, and execution traces.

Grammatical inference – used successfully in a variety of fields such as pattern recognition, computational biology and natural language processing – is the process of automatically inferring a grammar by examining the sentences of an unknown language. Software engineering can also benefit from grammatical inference. Unlike these other fields, which use grammars as a convenient tool to model naturally occurring patterns, software engineering treats grammars as first-class objects typically created and maintained for a specific purpose by human designers. We introduce the theory of grammatical inference and review the state of the art as it relates to software engineering.