The key to our results is stratified synthesis, where we use a set of instructions whose semantics are known to synthesize the semantics of additional instruc- tions whose semantics are unknown. As the set of formally described instructions increases, the synthesis vocabulary expands, making it possible to synthesize the semantics of increasingly complex instructions