A Syntactic Neural Model for General-Purpose Code Generation
Pengcheng Yin
Language Technologies Institute
Carnegie Mellon University
pcyin@cs.cmu.edu

Graham Neubig
Language Technologies Institute
Carnegie Mellon University
gneubig@cs.cmu.edu

Abstract

In parallel, the NLP community has developed
methods for data-driven semantic parsing, whichattempt to map NL to structured logical forms executable by computers. These logical forms can begeneral-purpose meaning representations (Clark
and Curran, 2007; Banarescu et al., 2013), formalisms for querying knowledge bases (Tang andMooney, 2001; Zettlemoyer and Collins, 2005;
Berant et al., 2013) and instructions for robots or
personal assistants (Artzi and Zettlemoyer, 2013;
Quirk et al., 2015; Misra et al., 2015), among others. While these methods have the advantage ofbeing learnable from data, compared to the programming languages (PLs) in use by programmers, the domain-specific languages targeted bythese works have a schema and syntax that is relatively simple.
Recently, Ling et al. (2016) have proposed adata-driven code generation method for high-level,
general-purpose PLs like Python and Java. This
work treats code generation as a sequence-tosequence modeling problem, and introduce methods to generate words from character-level models, and copy variable names from input descriptions. However, unlike most work in semantic
parsing, it does not consider the fact that code has
to be well-defined programs in the target syntax.
In this work, we propose a data-driven syntaxbased neural network model tailored for generation of general-purpose PLs like Python. In order to capture the strong underlying syntax of thePL, we define a model that transduces an NL statement into an Abstract Syntax Tree (AST; Fig. 1(a),§ 2) for the target PL. ASTs can be deterministically generated for all well-formed programs using standard parsers provided by the PL, and thus
give us a way to obtain syntax information withminimal engineering. Once we generate an AST,
we can use deterministic generation tools to convert the AST into surface code. We hypothesize

We consider the problem of parsing natural language descriptions into source code
written in a general-purpose programming
language like Python. Existing datadriven methods treat this problem as a language generation task without considering
the underlying syntax of the target programming language. Informed by previous work in semantic parsing, in this paper we propose a novel neural architecture
powered by a grammar model to explicitly
capture the target syntax as prior knowledge. Experiments find this an effective
way to scale up to generation of complex
programs from natural language descriptions, achieving state-of-the-art results thatwell outperform previous code generationand semantic parsing approaches.

1

Introduction

Every programmer has experienced the situation
where they know what they want to do, but do
not have the ability to turn it into a concrete implementation. For example, a Python programmer
may want to “sort my list in descending order,”but not be able to come up with the proper syntax sorted(my list, reverse=True) to realize his intention. To resolve this impasse, it iscommon for programmers to search the web innatural language (NL), find an answer, and modify it into the desired form (Brandt et al., 2009,2010). However, this is time-consuming, andthus the software engineering literature is ripewith methods to directly generate code from NL
descriptions, mostly with hand-engineered methods highly tailored to specific programming languages (Balzer, 1985; Little and Miller, 2009;
Gvero and Kuncak, 2015).
440

Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics, pages 440–450
Vancouver, Canada, July 30 - August 4, 2017. c 2017 Association for Computational Linguistics
https://doi.org/10.18653/v1/P17-1041

Production Rule
Role
Explanation
Call 7! expr[func] expr*[args] keyword*[keywords] Function Call . func: the function to be invoked . args: arguments
list . keywords: keyword arguments list
If 7! expr[test] stmt*[body] stmt*[orelse]
If Statement. test: condition expression . body: statements inside the If clause . orelse: elif or else statements
For 7! expr[target] expr*[iter] stmt*[body]
For Loop. target: iteration variable . iter: enumerable to iterstmt*[orelse]
ate over . body: loop body . orelse: else statements
FunctionDef 7! identifier[name] arguments*[args] Function Def. . name: function name . args: function arguments
stmt*[body]. body: function body
Table 1: Example production rules for common Python statements (Python Software Foundation, 2016)

2that such a structured approach has two benefits.
First, we hypothesize that structure can be used
to constrain our search space, ensuring generationof well-formed code. To this end, we propose a
syntax-driven neural code generation model. The
backbone of our approach is a grammar model(§ 3) which formalizes the generation story of a
derivation AST into sequential application of actions that either apply production rules (§ 3.1), or
emit terminal tokens (§ 3.2). The underlying syntax of the PL is therefore encoded in the grammar
model a priori as the set of possible actions. Our
approach frees the model from recovering the underlying grammar from limited training data, andinstead enables the system to focus on learning thecompositionality among existing grammar rules.
Xiao et al. (2016) have noted that this impositionof structure on neural models is useful for semantic parsing, and we expect this to be even more important for general-purpose PLs where the syntax
trees are larger and more complex.
Second, we hypothesize that structural information helps to model information flow within theneural network, which naturally reflects the recursive structure of PLs. To test this, we extend a
standard recurrent neural network (RNN) decoder
to allow for additional neural connections whichreflect the recursive structure of an AST (§ 4.2).
As an example, when expanding the node ? inFig. 1(a), we make use of the information fromboth its parent and left sibling (the dashed rectangle). This enables us to locally pass informationof relevant code segments via neural network connections, resulting in more confident predictions.
Experiments (§ 5) on two Python code generation tasks show 11.7% and 9.3% absolute improvements in accuracy against the state-of-the-art
system (Ling et al., 2016). Our model also gives
competitive performance on a standard semantic
parsing benchmark1 .

The Code Generation Problem

Given an NL description x, our task is to generate
the code snippet c in a modern PL based on the intent of x. We attack this problem by first generating the underlying AST. We define a probabilistic
grammar model of generating an AST y given x:p(y|x). The best-possible AST ŷ is then given byŷ = arg max p(y|x).
y(1)

ŷ is then deterministically converted to the corresponding surface code c.2 While this paper uses
examples from Python code, our method is PLagnostic.
Before detailing our approach, we first presenta brief introduction of the Python AST and its
underlying grammar. The Python abstract grammar contains a set of production rules, and an
AST is generated by applying several production
rules composed of a head node and multiple childnodes. For instance, the first rule in Tab. 1 isused to generate the function call sorted(·) in
Fig. 1(a). It consists of a head node of type Call,and three child nodes of type expr, expr* andkeyword*, respectively. Labels of each node are
noted within brackets. In an AST, non-terminal
nodes sketch the general structure of the target
code, while terminal nodes can be categorized into
two types: operation terminals and variable terminals. Operation terminals correspond to basicarithmetic operations like AddOp.Variable terminal nodes store values for variables and constantsof built-in data types3 . For instance, all terminal
nodes in Fig. 1(a) are variable terminal nodes.

3

Grammar Model

Before detailing our neural code generation
method, we first introduce the grammar model at
its core. Our probabilistic grammar model defines
the generative story of a derivation AST. We fac2

1
Implementation available at https://github.
com/neulab/NL2code

3441

We use astor library to convert ASTs into Python code.
bool, float, int, str.

root
Expr
expr[value]Call

expr*[args]

keyword*[keywords]

Name

expr

keywordstr(sorted)Namestr(reverse)...

expr[func]

Action Flow

expr[value]

Parent Feeding
Apply RuleName

str(my_list)

Generate Token

str(True)

GenToken with Copy

(a)

(b)

Code:

Input:

Figure 1: (a) the Abstract Syntax Tree (AST) for the given example code. Dashed nodes denote terminals. Nodes are labeledwith time steps during which they are generated. (b) the action sequence (up to t14 ) used to generate the AST in (a)torize the generation process of an AST into sequential application of actions of two types:

time step t: nft ) in a depth-first, left-to-righttraversal of the tree. Given a fixed set of production rules, A PPLY RULE chooses a rule r from thesubset that has a head matching the type of nft ,and uses r to expand nft by appending all childnodes specified by the selected production. As an
example, in Fig. 1(b), the rule Call 7! expr. . .
expands the frontier node Call at time step t4 , andits three child nodes expr, expr* and keyword*
are added to the derivation.
A PPLY RULE actions grow the derivation AST
by appending nodes. When a variable terminal
node (e.g., str) is added to the derivation and becomes the frontier node, the grammar model thenswitches to G EN T OKEN actions to populate thevariable terminal with tokens.
Unary Closure Sometimes, generating an AST
requires applying a chain of unary productions.
For instance, it takes three time steps (t9 t11 )to generate the sub-structure expr* 7! expr 7!
Name 7! str in Fig. 1(a). This can be effectively
reduced to one step of A PPLY RULE action by taking the closure of the chain of unary productions
and merging them into a single rule: expr* 7!⇤
str. Unary closures reduce the number of actions
needed, but would potentially increase the size ofthe grammar. In our experiments we tested ourmodel both with and without unary closures (§ 5).

• A PPLY RULE[r] applies a production rule r to
the current derivation tree;• G EN T OKEN[v] populates a variable terminal
node by appending a terminal token v.
Fig. 1(b) shows the generation process of the target AST in Fig. 1(a). Each node in Fig. 1(b) indicates an action. Action nodes are connected bysolid arrows which depict the chronological orderof the action flow. The generation proceeds in
depth-first, left-to-right order (dotted arrows represent parent feeding, explained in § 4.2.1).
Formally, under our grammar model, the probability of generating an AST y is factorized as:p(y|x) =TY
t=1

p(at |x, a<t ),(2)where at is the action taken at time step t, anda<t is the sequence of actions before t. We will
explain how to compute the action probabilitiesp(at |·) in Eq. (2) in § 4. Put simply, the generation process begins from a root node at t0 ,and proceeds by the model choosing A PPLY RULE
actions to generate the overall program structurefrom a closed set of grammar rules, then at leavesof the tree corresponding to variable terminals, themodel switches to G EN T OKEN actions to generate variables or constants from the open set. We
describe this process in detail below.

3.2

G EN T OKEN Actions

Once we reach a frontier node nft that corresponds
to a variable type (e.g., str), G EN T OKEN actions
are used to fill this node with values. For generalpurpose PLs like Python, variables and constants
have values with one or multiple tokens. For in-

3.1 A PPLY RULE Actions
A PPLY RULE actions generate program structure,
expanding the current node (the frontier node at442

stance, a node that stores the name of a function(e.g., sorted) has a single token, while a nodethat denotes a string constant (e.g., a=‘helloworld’) could have multiple tokens. Our model
copes with both scenarios by firing G EN T OKEN
actions at one or more time steps. At each time
step, G EN T OKEN appends one terminal token to
the current frontier variable node. A special </n>token is used to “close” the node. The grammar
model then proceeds to the new frontier node.
Terminal tokens can be generated from a predefined vocabulary, or be directly copied from the
input NL. This is motivated by the observationthat the input description often contains out-ofvocabulary (OOV) variable names or literal values
that are directly used in the target code. For instance, in our running example the variable namemy list can be directly copied from the the input
at t12 . We give implementation details in § 4.2.2.

4

...

...
non­terminal

variable terminal

type ofembedding of?

+
ApplyRule[Call]

Parent Stateembedding of node typesort

my_listindescending

order

Figure 2: Illustration of a decoder time step (t = 9)

where fLSTM (·) is the LSTM update function.
[:] denotes vector concatenation. st will then be
used to compute action probabilities p(at |x, a<t )in Eq. (2). Here, at 1 is the embedding of the previous action. ct is a context vector retrieved from
input encodings {hi } via soft attention. pt is avector that encodes the information of the parent
action. nft denotes the node type embedding of
the current frontier node nft 4 . Intuitively, feeding
the decoder the information of nft helps the model
to keep track of the frontier node to expand.
Action Embedding at We maintain two action
embedding matrices, WR and WG . Each row in
WR (WG ) corresponds to an embedding vector
for an action A PPLY RULE[r] (G EN T OKEN[v]).
Context Vector ct The decoder RNN uses soft attention to retrieve a context vector ct from the input encodings {hi } pertain to the prediction of thecurrent action. We follow Bahdanau et al. (2014)
and use a Deep Neural Network (DNN) with a single hidden layer to compute attention weights.
Parent Feeding pt Our decoder RNN uses additional neural connections to directly pass information from parent actions. For instance, when
computing s9 , the information from its parent action step t4 will be used. Formally, we define theparent action step pt as the time step at which
the frontier node nft is generated. As an example, for t9 , its parent action step p9 is t4 , since
nf9 is the node ?, which is generated at t4 by the
A PPLY RULE[Call7!. . .] action.
We model parent information pt from twosources: (1) the hidden state of parent action spt ,and (2) the embedding of parent action apt . pt isthe concatenation. The parent feeding schema en-

Estimating Action Probabilities

We estimate action probabilities in Eq. (2) using
attentional neural encoder-decoder models with aninformation flow structured by the syntax trees.
4.1 Encoder
For an NL description x consisting of n words{wi }ni=1 , the encoder computes a context sensitive embedding hi for each wi using a bidirectional Long Short-Term Memory (LSTM) network (Hochreiter and Schmidhuber, 1997), similar to the setting in (Bahdanau et al., 2014). See
supplementary materials for detailed equations.
4.2 Decoder
The decoder uses an RNN to model the sequential
generation process of an AST defined as Eq. (2).
Each action step in the grammar model naturally
grounds to a time step in the decoder RNN. Therefore, the action sequence in Fig. 1(b) can be interpreted as unrolling RNN time steps, with solid
arrows indicating RNN connections. The RNN
maintains an internal state to track the generation
process (§ 4.2.1), which will then be used to compute action probabilities p(at |x, a<t ) (§ 4.2.2).
4.2.1 Tracking Generation States
Our implementation of the decoder resembles avanilla LSTM, with additional neural connections(parent feeding, Fig. 1(b)) to reflect the topologicalstructure of an AST. The decoder’s internal hidden
state at time step t, st , is given by:
st = fLSTM ([at 1 : ct : pt : nft ], st 1 ),GenToken

ApplyRule

(3)

4

443

We maintain an embedding for each node type.

ables the model to utilize the information of parent code segments to make more confident predictions. Similar approaches of injecting parent information were also explored in the S EQ 2T REE
model in Dong and Lapata (2016)5 .
4.2.2 Calculating Action Probabilities
In this section we explain how action probabilitiesp(at |x, a<t ) are computed based on st .
A PPLY RULE The probability of applying rule r
as the current action at is given by a softmax6 :p(at = A PPLY RULE[r]|x, a<t ) =softmax(WR · g(st ))| · e(r) (4)where g(·) is a non-linearity tanh(W·st +b), ande(r) the one-hot vector for rule r.
G EN T OKEN As in § 3.2, a token v can be generated from a predefined vocabulary or copied fromthe input, defined as the marginal probability:

DatasetHS

D JANGOI FTTT

Train
Development
Test

533
66
66

16,0001,000
1,805

77,495
5,171
758

Avg. tokens in description
Avg. characters in code
Avg. size of AST (# nodes)

39.1
360.3
136.6

14.3
41.1
17.2

7.4
62.2
7.0

Statistics of Grammar
w/o unary closure# productions
100
222# node types
61
96
terminal vocabulary size
1361 6733
Avg. # actions per example 173.4 20.3

1009
828
0
5.0

w/ unary closure# productions# node types
Avg. # actions per example

–
–
–

100
57
141.7

237
92
16.4

Table 2: Statistics of datasets and associated grammars

decompose yi into a sequence of oracle actions,which explains the generation story of yi under thegrammar model. The model is then optimized by
maximizing the log-likelihood of the oracle action
sequence. At inference time, given an NL description, we use beam search to approximate the best
AST ŷ in Eq. (1). See supplementary materials forthe pseudo-code of the inference algorithm.

p(at = G EN T OKEN[v]|x, a<t ) =p(gen|x, a<t )p(v|gen, x, a<t )+ p(copy|x, a<t )p(v|copy, x, a<t ).
The selection probabilities p(gen|·) and p(copy|·)
are given by softmax(WS · st ). The probability of generating v from the vocabulary,p(v|gen, x, a<t ), is defined similarly as Eq. (4),except that we use the G EN T OKEN embedding
matrix WG , and we concatenate the context vector
ct with st as input. To model the copy probability,
we follow recent advances in modeling copying
mechanism in neural networks (Gu et al., 2016;
Jia and Liang, 2016; Ling et al., 2016), and use apointer network (Vinyals et al., 2015) to computethe probability of copying the i-th word from the
input by attending to input representations {hi }:exp(!(hi , st , ct ))p(wi |copy, x, a<t ) = Pn,
i0 =1 exp(!(hi0 , st , ct ))5Experimental Evaluation

5.1

Datasets and Metrics

H EARTH S TONE (HS) dataset (Ling et al., 2016)is a collection of Python classes that implement
cards for the card game HearthStone. Each cardcomes with a set of fields (e.g., name, cost, anddescription), which we concatenate to create theinput sequence. This dataset is relatively difficult:input descriptions are short, while the target code
is in complex class structures, with each AST having 137 nodes on average.
D JANGO dataset (Oda et al., 2015) is a collectionof lines of code from the Django web framework,
each with a manually annotated NL description.
Compared with the HS dataset where card implementations are somewhat homogenous, examples
in D JANGO are more diverse, spanning a wide variety of real-world use cases like string manipulation, IO operations, and exception handling.
I FTTT dataset (Quirk et al., 2015) is a domainspecific benchmark that provides an interesting side comparison. Different from HS andD JANGO which are in a general-purpose PL, programs in I FTTT are written in a domain-specificlanguage used by the IFTTT task automation

where !(·) is a DNN with a single hidden layer.
Specifically, if wi is an OOV word (e.g., the variable name my list), which is represented by aspecial <unk> token during encoding, we then directly copy the actual word wi from the input description to the derivation.
4.3 Training and Inference
Given a dataset of pairs of NL descriptions xi andcode snippets ci , we parse ci into its AST yi and5
S EQ 2T REE generates tree-structured outputs by conditioning on the hidden states of parent non-terminals, while
our parent feeding uses the states of parent actions.
6
We do not show bias terms for all softmax equations.

444

App. Users of the App write simple instructions (e.g., If Instagram.AnyNewPhotoByYou
Then Dropbox.AddFileFromURL) with NL descriptions (e.g., “Autosave your Instagram photos
to Dropbox”). Each statement inside the If or
Then clause consists of a channel (e.g., Dropbox)
and a function (e.g., AddFileFromURL)7 . This
simple structure results in much more concise
ASTs (7 nodes on average). Because all examples
are created by ordinary Apps users, the dataset
is highly noisy, with input NL very loosely connected to target ASTs. The authors thus provide ahigh-quality filtered test set, where each example
is verified by at least three annotators. We use thisset for evaluation. Also note I FTTT’s grammar has
more productions (Tab. 2), but this does not imply
that its grammar is more complex. This is because
for HS and D JANGO terminal tokens are generatedby G EN T OKEN actions, but for I FTTT, all the codeis generated directly by A PPLY RULE actions.
Metrics As is standard in semantic parsing, wemeasure accuracy, the fraction of correctly generated examples. However, because generating anexact match for complex code structures is nontrivial, we follow Ling et al. (2016), and use tokenlevel BLEU-4 with as a secondary metric, definedas the averaged BLEU scores over all examples.8
5.2

HS

D JANGO

ACC

BLEU

ACC

BLEU

Retrieval System†
Phrasal Statistical MT†
Hierarchical Statistical MT†

0.0
0.0
0.0

62.5
34.1
43.2

14.7
31.5
9.5

18.6
47.6
35.9

NMT
S EQ 2T REE
S EQ 2T REE–UNK
†

1.5
1.5
13.6
4.5

60.4
53.4
62.8
65.6

45.1
28.9
39.4
62.3

63.4
44.6
58.2
77.6

Our system

16.2

75.8

71.6

84.5

16.7
10.6
3.0

75.8
75.7
65.7

70.7
71.5
32.3
70.3

83.8
84.3
61.7
83.3

LPN

Ablation Study– frontier embed.
– parent feed.
– copy terminals+ unary closure– unary closure

10.1

–

74.8

–

Table 3: Results on two Python code generation tasks.
†
Results previously reported in Ling et al. (2016).

dropouts (Gal and Ghahramani, 2016) for all recurrent networks, together with standard dropout
layers added to the inputs and outputs of the decoder RNN. We validate the dropout probability
from {0, 0.2, 0.3, 0.4}. For decoding, we use abeam size of 15.
5.3 Results
Evaluation results for Python code generation
tasks are listed in Tab. 3. Numbers for our systems are averaged over three runs. We compare
primarily with two approaches: (1) Latent Predictor Network (LPN), a state-of-the-art sequenceto-sequence code generation model (Ling et al.,2016), and (2) S EQ 2T REE, a neural semantic parsing model (Dong and Lapata, 2016). S EQ 2T REE
generates trees one node at a time, and the target grammar is not explicitly modeled a priori,
but implicitly learned from data. We test boththe original S EQ 2T REE model released by the authors and our revised one (S EQ 2T REE–UNK) thatuses unknown word replacement to handle rarewords (Luong et al., 2015). For completeness,
we also compare with a strong neural machinetranslation (NMT) system (Neubig, 2015) using astandard encoder-decoder architecture with attention and unknown word replacement9 , and include
numbers from other baselines used in Ling et al.
(2016). On the HS dataset, which has relatively
large ASTs, we use unary closure for our modeland S EQ 2T REE, and for D JANGO we do not.

Setup

Preprocessing All input descriptions are tokenized using NLTK. We perform simple canonicalization for D JANGO, such as replacing quoted
strings in the inputs with place holders. See supplementary materials for details. We extract unaryclosures whose frequency is larger than a threshold k (k = 30 for HS and 50 for D JANGO).
Configuration The size of all embeddings is 128,
except for node type embeddings, which is 64.
The dimensions of RNN states and hidden layers
are 256 and 50, respectively. Since our datasets are
relatively small for a data-hungry neural model,
we impose strong regularization using recurrent
7
Like Beltagy and Quirk (2016), we strip function parameters since they are mostly specific to users.
8
These two metrics are not ideal: accuracy only measures
exact match and thus lacks the ability to give credit to semantically correct code that is different from the reference, while
it is not clear whether BLEU provides an appropriate proxyfor measuring semantics in the code generation task. A more
intriguing metric would be directly measuring semantic/functional code equivalence, for which we present a pilot study
at the end of this section (cf. Error Analysis). We leave exploring more sophisticated metrics (e.g. based on static codeanalysis) as future work.

9
For NMT, we also attempted to find the best-scoring syntactically correct predictions in the size-5 beam, but this did
not yield a significant improvement over the NMT results in
Tab. 3.

445

C HANNEL F ULL T REE
Classical Methods
posclass (Quirk et al., 2015)
LR (Beltagy and Quirk, 2016)
Neural Network Methods
NMT

NN (Beltagy and Quirk, 2016)
S EQ 2T REE (Dong and Lapata, 2016)
Doubly-Recurrent NN(Alvarez-Melis and Jaakkola, 2017)

Figure 3: Performance w.r.t reference AST size on D JANGO

Our system– parent feed.
– frontier embed.

81.4
88.8

71.0
82.5

87.7
88.0
89.7

77.7
74.3
78.4

90.1

78.2

90.0
89.9
90.1

82.0
81.1
78.7

Table 4: Results on the noise-filtered I FTTT test set of “>3
agree with gold annotations” (averaged over three runs), ourmodel performs competitively among neural models.

Figure 4: Performance w.r.t reference AST size on HS

System Comparison As in Tab. 3, our model
registers 11.7% and 9.3% absolute improvements
over LPN in accuracy on HS and D JANGO. Thisboost in performance strongly indicates the importance of modeling grammar in code generation.
For the baselines, we find LPN outperforms NMT
and S EQ 2T REE in most cases. We also note thatS EQ 2T REE achieves a decent accuracy of 13.6%
on HS, which is due to the effect of unknown word
replacement, since we only achieved 1.5% without it. A closer comparison with S EQ 2T REE isinsightful for understanding the advantage of our
syntax-driven approach, since both S EQ 2T REE
and our system output ASTs: (1) S EQ 2T REE predicts one node each time step, and requires additional “dummy” nodes to mark the boundary ofa subtree. The sheer number of nodes in target
ASTs makes the prediction process error-prone. In
contrast, the A PPLY RULE actions of our grammar
model allows for generating multiple nodes at asingle time step. Empirically, we found that in HS,
S EQ 2T REE takes more than 300 time steps on average to generate a target AST, while our modeltakes only 170 steps. (2) S EQ 2T REE does not directly use productions in the grammar, which possibly leads to grammatically incorrect ASTs andthus empty code outputs. We observe that the ratio of grammatically incorrect ASTs predicted by
S EQ 2T REE on HS and D JANGO are 21.2% and10.9%, respectively, while our system guarantees
grammaticality.

curacy on HS. This is probably because that thegrammar of HS has fewer node types, and thus
the RNN is able to keep track of nft without depending on its embedding. Next, “–parent feed.”removes the parent feeding mechanism. The accuracy drops significantly on HS, with a marginal
deterioration on D JANGO. This result is interesting because it suggests that parent feeding is more
important when the ASTs are larger, which willbe the case when handling more complicated code
generation tasks like HS. Finally, removing thepointer network (“–copy terminals”) in G EN T O KEN actions gives poor results, indicating that it
is important to directly copy variable names andvalues from the input.
The results with and without unary closure
demonstrate that, interestingly, it is effective on
HS but not on D JANGO. We conjecture that this isbecause on HS it significantly reduces the numberof actions from 173 to 142 (c.f., Tab. 2), with thenumber of productions in the grammar remaining
unchanged. In contrast, D JANGO has a broader
domain, and thus unary closure results in moreproductions in the grammar (237 for D JANGO
vs. 100 for HS), increasing sparsity.
Performance by the size of AST We further investigate our model’s performance w.r.t. the sizeof the gold-standard ASTs in Figs. 3 and 4. Not
surprisingly, the performance drops when the sizeof the reference ASTs increases. Additionally, on
the HS dataset, the BLEU score still remains ataround 50 even when the size of ASTs grows to200, indicating that our proposed syntax-driven
approach is robust for long code segments.
Domain Specific Code Generation Although thisis not the focus of our work, evaluation on I FTTT
brings us closer to a standard semantic parsing set-

Ablation Study We also ablated our bestperforming models to analyze the contribution ofeach component. “–frontier embed.” removes thefrontier node embedding nft from the decoder
RNN inputs (Eq. (3)). This yields worse results on
D JANGO while gives slight improvements in ac446

copying. For instance, the first example is one that
our model predicted wrong — it generated code
block A instead of the gold B (it also missed afunction definition not shown here). However, wefind that the block A actually conveys part of the
input intent by destroying all, not some, of theminions. Since we are unable to find code block
A in the training data, it is clear that the model has
learned to generalize to some extent from multiple
training card examples with similar semantics or
structure.
The next two examples are from D JANGO. The
first one shows that the model learns the usageof common API calls (e.g., os.path.join), andhow to populate the arguments by copying from
inputs. The second example illustrates the difficulty of generating code with complex nested
structures like lambda functions, a scenario worth
further investigation in future studies. More examples are attached in supplementary materials.
Error Analysis To understand the sources of errors and how good our evaluation metric (exact
match) is, we randomly sampled and labeled 100
and 50 failed examples (with accuracy=0) fromD JANGO and HS, respectively. We found thataround 2% of these examples in the two datasets
are actually semantically equivalent. These examples include: (1) using different parameter names
when defining a function; (2) omitting (or adding)default values of parameters in function calls.
While the rarity of such examples suggests that ourexact match metric is reasonable, more advanced
evaluation metrics based on statistical code analysis are definitely intriguing future work.
For D JANGO, we found that 30% of failed cases
were due to errors where the pointer network
failed to appropriately copy a variable name into
the correct position. 25% were because the generated code only partially implemented the required
functionality. 10% and 5% of errors were due tomalformed English inputs and pre-processing errors, respectively. The remaining 30% of examples were errors stemming from multiple sources,
or errors that could not be easily categorized into
the above. For HS, we found that all failed card
examples were due to partial implementation errors, such as the one shown in Table 5.

input <name> Brawl </name> <cost> 5 </cost> <desc>
Destroy all minions except one (chosen randomly)</desc> <rarity> Epic </rarity> ...
pred. class Brawl(SpellCard):
def init (self):
super(). init (’Brawl’, 5, CHARACTER CLASS.
WARRIOR, CARD RARITY.EPIC)
def use(self, player, game):
super().use(player, game)targets = copy.copy(game.other player.minions)targets.extend(player.minions)for minion in targets:A
minion.die(self)ref.

minions = copy.copy(player.minions)B
minions.extend(game.other player.minions)
if len(minions) > 1:
survivor = game.random choice(minions)for minion in minions:if minion is not survivor: minion.die(self)

input join app config.path and string ’locale’ into a filepath, substitute it for localedir.
pred. localedir = os.path.join(
app config.path, ’locale’) 3
input self.plural is an lambda function with an argumentn, which returns result of boolean expression n notequal to integer 1
pred. self.plural = lambda n: len(n) 7
ref. self.plural = lambda n: int(n!=1)Table 5: Predicted examples from HS (1st) and D JANGO.
Copied contents (copy probability > 0.9) are highlighted.

ting, which helps to investigate similarities anddifferences between generation of more complicated general-purpose code and and more limiteddomain simpler code. Tab. 4 shows the results,
following the evaluation protocol in (Beltagy and
Quirk, 2016) for accuracies at both channel andfull parse tree (channel + function) levels. Ourfull model performs on par with existing neural network-based methods, while outperforming
other neural models in full tree accuracy (82.0%).
This score is close to the best classical method(LR), which is based on a logistic regression
model with rich hand-engineered features (e.g.,brown clusters and paraphrase). Also note that theperformance between NMT and other neural models is much closer compared with the results in
Tab. 3. This suggests that general-purpose code
generation is more challenging than the simpler
I FTTT setting, and therefore modeling structural
information is more helpful.
Case Studies We present output examples inTab. 5. On HS, we observe that most of thetime our model gives correct predictions by filling learned code templates from training data witharguments (e.g., cost) copied from input. This is inline with the findings in Ling et al. (2016). However, we do find interesting examples indicatingthat the model learns to generalize beyond trivial

6

Related Work

Code Generation and Analysis Most works oncode generation focus on generating code for domain specific languages (DSLs) (Kushman and447

7

Barzilay, 2013; Raza et al., 2015; Manshadi et al.,2013), with neural network-based approaches recently explored (Liu et al., 2016; Parisotto et al.,2016; Balog et al., 2016). For general-purpose
code generation, besides the general frameworkof Ling et al. (2016), existing methods often
use language and task-specific rules and strategies (Lei et al., 2013; Raghothaman et al., 2016).
A similar line is to use NL queries for code retrieval (Wei et al., 2015; Allamanis et al., 2015).
The reverse task of generating NL summaries fromsource code has also been explored (Oda et al.,2015; Iyer et al., 2016). Finally, our work falls into
the broad field of probabilistic modeling of sourcecode (Maddison and Tarlow, 2014; Nguyen et al.,2013). Our approach of factoring an AST using
probabilistic models is closely related to Allamanis et al. (2015), which uses a factorized model tomeasure the semantic relatedness between NL and
ASTs for code retrieval, while our model tackles
the more challenging generation task.

Conclusion

This paper proposes a syntax-driven neural code
generation approach that generates an abstract
syntax tree by sequentially applying actions froma grammar model. Experiments on both code generation and semantic parsing tasks demonstrate theeffectiveness of our proposed approach.

Acknowledgment
We are grateful to Wang Ling for his generous help
with LPN and setting up the benchmark. We thankI. Beltagy for providing the I FTTT dataset. We
also thank Li Dong for helping with S EQ 2T REE
and insightful discussions.

References
Miltiadis Allamanis, Daniel Tarlow, Andrew D. Gordon, and Yi Wei. 2015. Bimodal modelling ofsource code and natural language. In Proceedingsof ICML. volume 37.
David Alvarez-Melis and Tommi S. Jaakkola. 2017.
Tree-structured decoding with doubly recurrent neural networks. In Proceedings of ICLR.

Semantic Parsing Our work is related to the general topic of semantic parsing, which aims totransform NL descriptions into executable logicalforms. The target logical forms can be viewed
as DSLs. The parsing process is often guided
by grammatical formalisms like combinatory categorical grammars (Kwiatkowski et al., 2013; Artziet al., 2015), dependency-based syntax (Lianget al., 2011; Pasupat and Liang, 2015) or taskspecific formalisms (Clarke et al., 2010; Yih et al.,2015; Krishnamurthy et al., 2016; Mei et al.,2016). Recently, there are efforts in designingneural network-based semantic parsers (Misra andArtzi, 2016; Dong and Lapata, 2016; Neelakantan
et al., 2016; Yin et al., 2016). Several approaches
have be proposed to utilize grammar knowledge
in a neural parser, such as augmenting the training
data by generating examples guided by the grammar (Kociský et al., 2016; Jia and Liang, 2016).
Liang et al. (2016) used a neural decoder whichconstrains the space of next valid tokens in thequery language for question answering. Finally,
the structured prediction approach proposed by
Xiao et al. (2016) is closely related to our model inusing the underlying grammar as prior knowledge
to constrain the generation process of derivation
trees, while our method is based on a unified grammar model which jointly captures production rule
application and terminal symbol generation, andscales to general purpose code generation tasks.

Yoav Artzi, Kenton Lee, and Luke Zettlemoyer. 2015.
Broad-coverage CCG semantic parsing with AMR.
In Proceedings of EMNLP.
Yoav Artzi and Luke Zettlemoyer. 2013. Weakly supervised learning of semantic parsers for mapping
instructions to actions. Transaction of ACL 1(1).
Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua
Bengio. 2014.
Neural machine translation by
jointly learning to align and translate.
CoRR
abs/1409.0473.
Matej Balog, Alexander L. Gaunt, Marc Brockschmidt,
Sebastian Nowozin, and Daniel Tarlow. 2016.
Deepcoder: Learning to write programs. CoRR
abs/1611.01989.
Robert Balzer. 1985. A 15 year perspective on automatic programming. IEEE Trans. Software Eng.
11(11).
Laura Banarescu, Claire Bonial, Shu Cai, Madalina
Georgescu, Kira Griffitt, Ulf Hermjakob, Kevin
Knight, Philipp Koehn, Martha Palmer, and Nathan
Schneider. 2013. Abstract meaning representation
for sembanking. In Proceedings of LAW-ID@ACL.
I. Beltagy and Chris Quirk. 2016. Improved semantic parsers for if-then statements. In Proceedings of
ACL.
Jonathan Berant, Andrew Chou, Roy Frostig, and Percy
Liang. 2013. Semantic parsing on freebase fromquestion-answer pairs. In Proceedings of EMNLP.

448

Joel Brandt, Mira Dontcheva, Marcos Weskamp, andScott R. Klemmer. 2010. Example-centric programming: integrating web search into the development
environment. In Proceedings of CHI.

Tao Lei, Fan Long, Regina Barzilay, and Martin C. Rinard. 2013. From natural language specifications toprogram input parsers. In Proceedings of ACL.
Chen Liang, Jonathan Berant, Quoc Le, Kenneth D.
Forbus, and Ni Lao. 2016. Neural symbolic machines: Learning semantic parsers on freebase withweak supervision. CoRR abs/1611.00020.

Joel Brandt, Philip J. Guo, Joel Lewenstein, Mira
Dontcheva, and Scott R. Klemmer. 2009. Two studies of opportunistic programming: interleaving web
foraging, learning, and writing code. In Proceedingsof CHI.

Percy Liang, Michael I. Jordan, and Dan Klein. 2011.
Learning dependency-based compositional semantics. In Proceedings of ACL.

Stephen Clark and James R. Curran. 2007. Widecoverage efficient statistical parsing with CCG and
log-linear models. Computational Linguistics 33(4).

Wang Ling, Phil Blunsom, Edward Grefenstette,
Karl Moritz Hermann, Tomás Kociský, Fumin
Wang, and Andrew Senior. 2016. Latent predictor
networks for code generation. In Proceedings of
ACL.

James Clarke, Dan Goldwasser, Ming-Wei Chang, andDan Roth. 2010. Driving semantic parsing from theworld’s response. In Proceedings of CoNLL.

Greg Little and Robert C. Miller. 2009. Keyword programming in java. Autom. Softw. Eng. 16(1).

Li Dong and Mirella Lapata. 2016. Language to logicalform with neural attention. In Proceedings of ACL.
Yarin Gal and Zoubin Ghahramani. 2016. A theoretically grounded application of dropout in recurrent
neural networks. In Proceedings of NIPS.

Chang Liu, Xinyun Chen, Eui Chul Richard Shin,
Mingcheng Chen, and Dawn Xiaodong Song. 2016.
Latent attention for if-then program synthesis. In
Proceedings of NIPS.

Jiatao Gu, Zhengdong Lu, Hang Li, and Victor O. K.
Li. 2016. Incorporating copying mechanism insequence-to-sequence learning. In Proceedings of
ACL.

Thang Luong, Ilya Sutskever, Quoc V. Le, Oriol
Vinyals, and Wojciech Zaremba. 2015. Addressing
the rare word problem in neural machine translation.
In Proceedings of ACL.
Chris J. Maddison and Daniel Tarlow. 2014. Structured
generative models of natural source code. In Proceedings of ICML.

Tihomir Gvero and Viktor Kuncak. 2015. Interactive
synthesis using free-form queries. In Proceedingsof ICSE.

Mehdi Hafezi Manshadi, Daniel Gildea, and James F.
Allen. 2013. Integrating programming by example
and natural language programming. In Proceedingsof AAAI.

Sepp Hochreiter and Jürgen Schmidhuber. 1997. Long
short-term memory. Neural Computation 9(8).
Srinivasan Iyer, Ioannis Konstas, Alvin Cheung, andLuke Zettlemoyer. 2016. Summarizing source codeusing a neural attention model. In Proceedings of
ACL.

Hongyuan Mei, Mohit Bansal, and Matthew R. Walter. 2016. Listen, attend, and walk: Neural mappingof navigational instructions to action sequences. In
Proceedings of AAAI.

Robin Jia and Percy Liang. 2016. Data recombination
for neural semantic parsing. In Proceedings of ACL.

Dipendra K. Misra and Yoav Artzi. 2016. Neural shiftreduce CCG semantic parsing. In Proceedings of
EMNLP.

Tomás Kociský, Gábor Melis, Edward Grefenstette,
Chris Dyer, Wang Ling, Phil Blunsom, andKarl Moritz Hermann. 2016. Semantic parsing withsemi-supervised sequential autoencoders. In Proceedings of EMNLP.

Dipendra Kumar Misra, Kejia Tao, Percy Liang, andAshutosh Saxena. 2015. Environment-driven lexicon induction for high-level instructions. In Proceedings of ACL.

Jayant Krishnamurthy, Oyvind Tafjord, and Aniruddha
Kembhavi. 2016. Semantic parsing to probabilistic
programs for situated question answering. In Proceedings of EMNLP.

Arvind Neelakantan, Quoc V. Le, and Ilya Sutskever.
2016. Neural programmer: Inducing latent programs with gradient descent. In Proceedings of
ICLR.

Nate Kushman and Regina Barzilay. 2013. Using semantic unification to generate regular expressions
from natural language. In Proceedings of NAACL.

Graham Neubig. 2015. lamtram: A toolkit for language and translation modeling using neural networks. http://www.github.com/neubig/lamtram.

Tom Kwiatkowski, Eunsol Choi, Yoav Artzi, andLuke S. Zettlemoyer. 2013.
Scaling semantic
parsers with on-the-fly ontology matching. In Proceedings of the EMNLP.

Tung Thanh Nguyen, Anh Tuan Nguyen, Hoan Anh
Nguyen, and Tien N. Nguyen. 2013. A statisticalsemantic language model for source code. In Proceedings of ACM SIGSOFT.

449

Yusuke Oda, Hiroyuki Fudaba, Graham Neubig,
Hideaki Hata, Sakriani Sakti, Tomoki Toda, andSatoshi Nakamura. 2015. Learning to generate
pseudo-code from source code using statistical machine translation (T). In Proceedings of ASE.
Emilio Parisotto, Abdel-rahman Mohamed, Rishabh
Singh, Lihong Li, Dengyong Zhou, and Pushmeet
Kohli. 2016. Neuro-symbolic program synthesis.
CoRR abs/1611.01855.
Panupong Pasupat and Percy Liang. 2015. Compositional semantic parsing on semi-structured tables. In
Proceedings of ACL.
Python Software Foundation. 2016. Python abstract
grammar. https://docs.python.org/2/library/ast.html.
Chris Quirk, Raymond J. Mooney, and Michel Galley.
2015. Language to code: Learning semantic parsers
for if-this-then-that recipes. In Proceedings of ACL.
Mukund Raghothaman, Yi Wei, and Youssef Hamadi.
2016. SWIM: synthesizing what i mean: code
search and idiomatic snippet synthesis. In Proceedings of ICSE.
Mohammad Raza, Sumit Gulwani, and Natasa MilicFrayling. 2015. Compositional program synthesis
from natural language and examples. In Proceedings of IJCAI.
Lappoon R. Tang and Raymond J. Mooney. 2001. Using multiple clause constructors in inductive logic
programming for semantic parsing. In Proceedingsof ECML.
Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly.
2015. Pointer networks. In Proceedings of NIPS.
Yi Wei, Nirupama Chandrasekaran, Sumit Gulwani, and Youssef Hamadi. 2015.
Building bing developer assistant.
Technical report.
https://www.microsoft.com/enus/research/publication/building-bing-developerassistant/.
Chunyang Xiao, Marc Dymetman, and Claire Gardent.
2016. Sequence-based structured prediction for semantic parsing. In Proceedings of ACL.
Wen-tau Yih, Ming-Wei Chang, Xiaodong He, andJianfeng Gao. 2015. Semantic parsing via staged
query graph generation: Question answering withknowledge base. In Proceedings of ACL.
Pengcheng Yin, Zhengdong Lu, Hang Li, and Ben Kao.
2016. Neural enquirer: Learning to query tables innatural language. In Proceedings of IJCAI.
Luke Zettlemoyer and Michael Collins. 2005. Learning to map sentences to logical form structured classification with probabilistic categorial grammars. In
Proceedings of UAI.

450