  In recent years, deep learning techniques have been developed to improve the
performance of program synthesis from input-output examples. Albeit its
significant progress, the programs that can be synthesized by state-of-the-art
approaches are still simple in terms of their complexity. In this work, we move
a significant step forward along this direction by proposing a new class of
challenging tasks in the domain of program synthesis from input-output
examples: learning a context-free parser from pairs of input programs and their
parse trees. We show that this class of tasks are much more challenging than
previously studied tasks, and the test accuracy of existing approaches is
almost 0%.
  We tackle the challenges by developing three novel techniques inspired by
three novel observations, which reveal the key ingredients of using deep
learning to synthesize a complex program. First, the use of a
non-differentiable machine is the key to effectively restrict the search space.
Thus our proposed approach learns a neural program operating a domain-specific
non-differentiable machine. Second, recursion is the key to achieve
generalizability. Thus, we bake-in the notion of recursion in the design of our
non-differentiable machine. Third, reinforcement learning is the key to learn
how to operate the non-differentiable machine, but it is also hard to train the
model effectively with existing reinforcement learning algorithms from a cold
boot. We develop a novel two-phase reinforcement learning-based search
algorithm to overcome this issue. In our evaluation, we show that using our
novel approach, neural parsing programs can be learned to achieve 100% test
accuracy on test inputs that are 500x longer than the training samples.
