TRANX: A Transition-based Neural Abstract Syntax Parser for Semantic Parsing and Code Generation

Pengcheng Yin, Graham Neubig

Introduction

Semantic parsing is the task of transducing natural language (NL) utterances into formal meaning representations (MRs). The target MRs can be defined according to a wide variety of formalisms. This include linguistically-motivated semantic representations that are designed to capture the meaning of any sentence such as $\lambda$ -calculus (Zettlemoyer and Collins, 2005) or the abstract meaning representations (Banarescu et al., 2013). Alternatively, for more task-driven approaches to semantic parsing, it is common for meaning representations to represent executable programs such as SQL queries (Zhong et al., 2017), robotic commands Artzi and Zettlemoyer (2013), smart phone instructions Quirk et al. (2015), and even general-purpose programming languages like Python (Yin and Neubig, 2017; Rabinovich et al., 2017) and Java Ling et al. (2016).

Because of these varying formalisms for MRs, the design of semantic parsers, particularly neural network-based ones has generally focused on a small subset of tasks — in order to ensure the syntactic well-formedness of generated MRs, a parser is usually specifically designed to reflect the domain-dependent grammar of MRs in the structure of the model (Zhong et al., 2017; Xu et al., 2017). To alleviate this issue, there have been recent efforts in neural semantic parsing with general-purpose grammar models (Xiao et al., 2016; Dong and Lapata, 2018). Yin and Neubig (2017) put forward a neural sequence-to-sequence model that generates tree-structured MRs using a series of tree-construction actions, guided by the task-specific context free grammar provided to the model a priori. Rabinovich et al. (2017) propose the abstract syntax networks (ASNs), where domain-specific MRs are represented by abstract syntax trees (ASTs, Fig. 2 Left) specified under the abstract syntax description language (ASDL) framework (Wang et al., 1997). An ASN employs a modular architecture, generating an AST using specifically designed neural networks for each construct in the ASDL grammar.

Inspired by this existing research, we have developed Tranx, a TRANsition-based abstract syntaX parser for semantic parsing and code generation. Tranx is designed with the following principles in mind:

Generalization ability Tranx employs ASTs as a general-purpose intermediate meaning representation, and the task-dependent grammar is provided to the system as external knowledge to guide the parsing process, therefore decoupling the semantic parsing procedure with specificities of grammars.

Extensibility Tranx uses a simple transition system to parse NL utterances into tree-structured ASTs. The transition system is designed to be easy to extend, requiring minimal engineering to adapt to tasks that need to handle extra domain-specific information.

Effectiveness We test Tranx on four semantic parsing (Atis, Geo) and code generation (Django, WikiSQL) tasks, and demonstrate that Tranx is capable of generalizing to different domains while registering strong performance, out-performing existing neural network-based approaches on three of the four datasets (Geo, Atis, Django).

Methodology

Given an NL utterance, Tranx parses the utterance into a formal meaning representation, typically represented as $\lambda$ -calculus logical forms, domain-specific, or general-purpose programming languages (e.g., Python). In the following description we use Python code generation as a running example, where a programmer’s natural language intents are mapped to Python source code. Fig. 1 depicts the workflow of Tranx. We will present more use cases of Tranx in § 3.

The core of Tranx is a transition system. Given an input NL utterance $\bm{x}$ , Tranx employs the transition system to map the utterance $\bm{x}$ into an AST $\bm{z}$ using a series of tree-construction actions (§ 2.2). Tranx employs ASTs as the intermediate meaning representation to abstract over domain-specific structure of MRs. This parsing process is guided by the user-defined, domain-specific grammar specified under the ASDL formalism (§ 2.1). Given the generated AST $\bm{z}$ , the parser calls the user-defined function, AST_to_MR( $\cdot$ ), to convert the intermediate AST into a domain-specific meaning representation $\bm{y}$ , completing the parsing process. Tranx uses a probabilistic model $p(\bm{z}|\bm{x})$ , parameterized by a neural network, to score each hypothesis AST (§ 2.3).

Tranx uses ASTs as the general-purpose, intermediate semantic representation for MRs. ASTs are commonly used to represent programming languages, and can also be used to represent other tree-structured MRs (e.g., $\lambda$ -calculus). The ASDL framework is a grammatical formalism to define ASTs. See Fig. 1 for an excerpt of the Python ASDL grammar. Tranx provides APIs to read such a grammar from human-readable text files.

An ASDL grammar has two basic constructs: types and constructors. A composite type is defined by the set of constructors under that type. For example, the stmt and expr composite types in Fig. 1 refer to Python statements and expressions, repectively, each defined by a series of constructors. A constructor specifies a language construct of a particular type using its fields. For instance, the Call constructor under the composite type expr denotes function call expressions, and has three fields: func, args and keywords. Each field in a constructor is also strongly typed, which specifies the type of value the field can hold. A field with a composite type can be instantiated by constructors of the same type. For example, the func field above can hold a constructor of type expr. There are also fields with primitive types, which store values. For example, the id field of Name constructor has a primitive type identifier, and is used to store identifier names. And the field s in the Str (string) constructor hold string literals. Finally, each field has a cardinality (single, optional $?$ and sequential $*$ ), denoting the number of values the field holds.

An AST is then composed of multiple constructors, where each node on the tree corresponds to a typed field in a constructor (except for the root node, which denotes the root constructor). Depending on the cardinality of the field, a node can hold one or multiple constructors as its values. For instance, the func field with single cardinality in the ASDL grammar in Fig. 1 is instantiated with one Name constructor, while the args field with sequential cardinality have multiple child constructors.

2 Transition System

Inspired by Yin and Neubig (2017) (hereafter YN17), we develop a transition system that decomposes the generation procedure of an AST into a sequence of tree-constructing actions. We now explain the transition system using our running example. Fig. 2 Right lists the sequence of actions used to construct the example AST. In high level, the generation process starts from an initial derivation AST with a single root node, and proceeds according to a top-down, left-to-right order traversal of the AST. At each time step, one of the following three types of actions is evoked to expand the opening frontier field $n_{f_{t}}$ of the derivation:

ApplyConstr $[c]$ actions apply a constructor $c$ to the opening composite frontier field which has the same type as $c$ , populating the opening node using the fields in $c$ . If the frontier field has sequential cardinality, the action appends the constructor to the list of constructors held by the field.

Reduce actions mark the completion of the generation of child values for a field with optional (?) or multiple ( $*$ ) cardinalities.

GenToken $[v]$ actions populate a (empty) primitive frontier field with a token $v$ . For example, the field $f_{7}$ on Fig. 2 has type identifier, and is instantiated using a single GenToken action. For fields of string type, like $f_{8}$ , whose value could consists of multiple tokens (only one shown here), it can be filled using a sequence of GenToken actions, with a special $\textsc{GenToken}[$ $]$ action to terminate the generation of token values.

The generation completes once there is no frontier field on the derivation. Tranx then calls the user specified function AST_to_MR( $\cdot$ ) to convert the generated intermediate AST $\bm{z}$ into the target domain-specific MR $\bm{y}$ . Tranx provides various helper functions to ease the process of writing conversion functions. For example, our example conversion function to transform ASTs into Python source code contains only 32 lines of code. Tranx also ships with several built-in conversion functions to handle MRs commonly used in semantic parsing and code generation, like $\lambda$ -calculus logical forms and SQL queries.

3 Computing Action Probabilities p(𝒛|𝒙)𝑝conditional𝒛𝒙p(\bm{z}|\bm{x})

Given the transition system, the probability of an $\bm{z}$ is decomposed into the probabilities of the sequence of actions used to generate $\bm{z}$

Following YN17, we parameterize the transition-based parser $p(\bm{z}|\bm{x})$ using a neural encoder-decoder network with augmented recurrent connections to reflect the topology of ASTs.

The encoder is a standard bidirectional Long Short-term Memory (LSTM) network, which encodes the input utterance $\bm{x}$ of $n$ tokens, $\{x_{i}\}_{i=1}^{n}$ into vectorial representations $\{\mathbf{h}\}_{i=1}^{n}$ .

The decoder is also an LSTM network, with its hidden state $\mathbf{s}_{t}$ at each time temp given by

where $\mathbf{c}_{t}$ is the context vector retrieved from input encodings $\{\mathbf{h}_{i}\}_{i=1}^{n}$ using attention.

$\mathbf{p}_{t}$ is a vector that encodes the information of the parent frontier field $n_{f_{t}}$ on the derivation, which is a concatenation of two vectors: the embedding of the frontier field $\mathbf{n}_{f_{t}}$ , and $\mathbf{s}_{p_{t}}$ , the decoder’s state at which the constructor of $n_{f_{t}}$ is generated by the ApplyConstr action. Parent feeding reflects the topology of tree-structured ASTs, and gives better performance on generating complex MRs like Python code (§ 3).

The probability of an ApplyConstr $[c]$ action with embedding $\mathbf{a}_{c}$ isReduce is treated as a special ApplyConstr action.

For GenToken actions, we employ a hybrid approach of generation and copying, allowing for out-of-vocabulary variable names and literals (e.g., “file.csv” in Fig. 1) in $\bm{x}$ to be directly copied to the derivation. Specifically, the action probability is defined to be the marginal probability

Experiments

To demonstrate the generalization and extensibility of Tranx, we deploy our parser on four semantic parsing and code generation tasks.

We evaluate on Geo and Atis datasets. Geo is a collection of 880 U.S. geographical questions (e.g., “Which states border Texas?”), and Atis is a set of 5,410 inquiries of flight information (e.g., “Show me flights from Dallas to Baltimore”). The MRs in the two datasets are defined in $\lambda$ -calculus logical forms (e.g., “lambda $x$ (and (state $x$ ) (next_to $x$ texas))” and “lambda $x$ (and (flight $x$ dallas) (to $x$ baltimore))”). We use the pre-processed datasets released by Dong and Lapata (2016). We use the ASDL grammar defined in Rabinovich et al. (2017), as listed in Fig. 3.

1.2 Code Generation

We evaluate Tranx on both general-purpose (Python, Django) and domain-specific (SQL, WikiSQL) code generation tasks. The Django dataset (Oda et al., 2015) consists of 18,805 lines of Python source code extracted from the Django Web framework, with each line paired with an NL description. Code in this dataset covers various real-world use cases of Python, like string manipulation, I/O operation, exception handling, etc.

WikiSQL (Zhong et al., 2017) is a code generation task for domain-specific languages (i.e., SQL). It consists of 80,654 examples of NL questions (e.g., “What position did Calvin Mccarty play?”) and annotated SQL queries (e.g., “SELECT Position FROM Table WHERE Player = Calvin Mccarty”). Different from other datasets, each example also has a table extracted from Wikipedia, and the SQL query is executed against the table to get an answer.

In order to achieve strong results, existing parsers, like most models in Tab. 3, use specifically designed architectures to reflect the syntactic structure of SQL queries. We show that the transition system used by Tranx can be easily extended for WikiSQL with minimal engineering, while registering strong performance. First, we use define a simple ASDL grammar following the syntax of SQL (Fig. 4). We then augment the transition system with a special GenToken action, $\textsc{SelColumn}[k]$ . A $\textsc{SelColumn}[k]$ action is used to populate a primitive column_idx field in Select and Condition constructors in the grammar by selecting the $k$ -th column in the table. To compute the probability of $\textsc{SelColumn}[k]$ actions, we use a pointer network over column encodings, where the column encodings are given by a bidirectional LSTM network over column names in an input table. This can be simply implemented by overriding the base Parser class in Tranx and modifying the functions that compute action probabilities.

2 Results

In this section we discuss our experimental results. All results are averaged over three runs with different random seeds.

Tab. 1 lists the results for semantic parsing tasks. We test Tranx with two configurations, with or without parent feeding (§ 2.3). Our system outperforms existing neural network-based approaches. This demonstrates the effectiveness of Tranx in closed-domain semantic parsing. Interestingly, we found the model without parent feeding achieves slightly better accuracy on Geo, probably because that its relative simple grammar does not require extra handling of parent information.

Tab. 2 lists the results on Django. Tranx achieves state-of-the-art results on Django. We also find parent feeding yields +1 point gain in accuracy, suggesting the importance of modeling parental connections in ASTs with complex domain grammars (e.g., Python).

Tab. 3 shows the results on WikiSQL. We first discuss our standard model which only uses information of column names and do not use the contents of input tables during inference, as listed in the top two blocks in Tab. 3. We find Tranx, although just with simple extensions to adapt to this dataset, achieves impressive results and outperforms many task-specific methods. This demonstrates that Tranx is easy to extend to incorporate task-specific information, while maintaining its effectiveness. We also extend Tranx with a very simple answer pruning strategy, where we execute the candidate SQL queries in the beam against the input table, and prune those that yield empty execution results. Results are listed in the bottom two-blocks in Tab. 3, where we compare with systems that also use the contents of tables. Surprisingly, this (frustratingly) simple extension yields significant improvements, outperforming many task-specific models that use specifically designed, heavily-engineered neural networks to incorporate information of table contents.

Conclusion

We present Tranx, a transition-based abstract syntax parser. Tranx is generalizable, extensible and effective, achieving strong results on semantic parsing and code generation tasks.

Acknowledgements

This material is based upon work supported by the National Science Foundation under Grant No. 1815287. PY would like to thank Junxian He and Li Dong for helpful discussions.