We concretely develop our approach by extending the classic formalism of attribute grammars [1]}. Attribute grammars are like context-free grammars but allow rules to carry symbolic attributes of the context in which a rule is fired.
In our model, called Neurosymbolic Attribute Grammars (Nsgs), the context is an incomplete program, and rules are fired to replace a nonterminal (a stand-in for unknown code) in this program.
The attributes are semantic relationships (for example, symbol tables) computed using static analysis. The neural part of the model represents a probability distribution over the rules of the grammar conditioned on the attributes. During generation, the model repeatedly samples from this distribution while simultaneously computing the attributes of the generated code.
