Inferring flow of control in program synthesis by example

摘要

We present a supervised, interactive learning technique that infers control structures of computer programs from user-demonstrated traces. A two-stage process is applied: first, a minimal deterministic finite automation (DFA) M labled by the instructions of the program is learned from a set of example traces and membership queries to the user. It accepts all prefixes of traces of the target program. The number of queries is bounded by O(k.|M|), with k being the total unmber of instructions in the initial example traces. In the second step we parse this automation into a high-level programming language in O(|M|~2) steps, replacing jumps by conditional control structures.