From Natural Language Specifications to Program Input Parsers

Proceedings of the 51st Annual Meeting of the Association for Computational Linguistics, pages 1294–1303, Sofia, Bulgaria, August 4-9 2013. c⃝2013 Association for Computational Linguistics From Natural Language Specifications to Program Input Parsers Tao Lei, Fan Long, Regina Barzilay, and Martin Rinard Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology {taolei, fanl, regina, rinard}@csail.mit.edu Abstract We present a method for automatically generating input parsers from English specifications of input file formats. We use a Bayesian generative model to cap- ture relevant natural language phenomena and translate the English specification into a specification tree, which is then trans- lated into a C++ input parser. We model the problem as a joint dependency pars- ing and semantic role labeling task. Our method is based on two sources of infor- mation: (1) the correlation between the text and the specification tree and (2) noisy supervision as determined by the success of the generated C++ parser in reading in- put examples. Our results show that our approach achieves 80.0% F-Score accu- racy compared to an F-Score of 66.7% produced by a state-of-the-art semantic parser on a dataset of input format speci- fications from the ACM International Col- legiate Programming Contest (which were written in English for humans with no in- tention of providing support for automated processing).1 1 Introduction The general problem of translating natural lan- guage specifications into executable code has been around since the field of computer science was founded. Early attempts to solve this problem produced what were essentially verbose, clumsy, and ultimately unsuccessful versions of standard formal programming languages. In recent years 1The code, data, and experimental setup for this research are available at http://groups.csail.mit.edu/rbg/code/nl2p the input a single integer T test cases an integer N the next N lines N characters The input contains a single integer T that indicates the number of test cases. Then follow the T cases. Each test case begins with a line contains an integer N, representing the size of wall. The next N lines represent the original wall. Each line contains N characters. The j-th character of the i-th line figures out the color ... (a) Text Specification: (b) Specification Tree: (c) Two Program Input Examples: 1 10 YYWYYWWWWW YWWWYWWWWW YYWYYWWWWW ... WWWWWWWWWW 5Y12 YWYWW ... WWYYY Figure 1: An example of (a) one natural language specification describing program input data; (b) the corresponding specification tree representing the program input structure; and (c) two input ex- amples however, researchers have had success address- ing specific aspects of this problem. Recent ad- vances in this area include the successful transla- tion of natural language commands into database queries (Wong and Mooney, 2007; Zettlemoyer and Collins, 2009; Poon and Domingos, 2009; Liang et al., 2011) and the successful mapping of natural language instructions into Windows com- mand sequences (Branavan et al., 2009; Branavan et al., 2010). In this paper we explore a different aspect of this general problem: the translation of natural language input specifications into executable code that correctly parses the input data …

Content truncated to 500 words