Grape: Grammar-Preserving Rule Embedding

1 Introduction

Learning a representation for a basic unit (e.g., words in a sentence) plays an increasingly essential role in natural language processing tasks [Wolf et al., 2014; Sienˇcnik, 2015]. In the form of a real-valued vector, the most widely used word embedding encodes the semantics of a word in a context. Existing approaches mostly focus on how to learn a meaningful representation of words in a natural language (NL) [Mikolov et al., 2013; Pennington et al., 2014].

As we move to a scenario in which embedding techniques routinely represent tokens in context-free languages (e.g., programming languages, domain specific languages, regular expressions), early approaches directly treat the tokens as words in a NL and adopt word embedding techniques. Different from the sentence in NL, the context-free sentence (CFS) 1 can be parsed and further compiled by machines, which highly relies on the pre-defined grammar. For example, if we remove ";" from "int i = 0;", the C++ compiler will report a grammar error and fail to compile the CFS. This highlights the importance of the grammar.

∗Corresponding author.

1 A text written by the corresponding context-free grammar. In this paper, we only talk about the grammar used by common pro-

Mou et al. [2016] has realized the fact and proposes to embed the grammar information by parsing the CFS as an abstract syntax tree (AST). The AST is further represented as a sequence of production rules by more recent work [Yin and Neubig, 2017; Rabinovich et al., 2017; Yin and Neubig, 2018; Iyer et al., 2018; Sun et al., 2020]. Unfortunately, although they transfer the CFS into the production rule sequence, they still use the word embedding technique to represent these rules, which does not utilize the meta-level information in the grammar definition, e.g., b → c can be used after a → b to further expand b.

In this paper, we propose a Grammar-Preserving Rule Embedding approach called Grape. Similar to word embedding, our approach produces the embeddings of the grammar rules that can be used in downstream applications. Unlike word embedding, we preserve the information of the predefined context-free grammar rules.

However, it is challenging to preserve such grammars. First, context-free grammar contains rich structural information, i.e., the structural relationships between different grammar rules, such as whether a rule can be a parent of another rule in an AST. If such information is preserved, structurally similar rules should have similar embeddings. For example in Figure 1, either rule 4 or rule 5 can be a child of rule 3, and also be a parent of rule 6, so their embeddings are better to be close. Second, context-free grammar also contains extensive content information, i.e., the information in the content of the rule definition itself, such as the symbols used in the rule, the order of the symbols, etc. For example, the embedding of rule 6 and rule 9 should be similar as they have the shared symbol orelse. Word embedding can preserve neither type of information because the rules are represented using one-hot encoding, such that neither the structural relation of the rules nor the content of the rules are used as input for the neural network.

To preserve the structural information, we propose to use a graph to represent the context-free grammar, called a grammar relation graph, where each node in the graph corresponds to a rule in the grammar, and each edge represents a parent-child relationship between two rules. Then, we use a graph neural network (GNN) to map each node into a vector. To preserve the content information, we further propose to use a gating layer to integrate the rule definition with the node embedding in the GNN. The above neural structure is then used as an embedding layer in existing neural network for embedding grammar rules.

gramming languages.

Our experiment was conducted on six widely-used benchmarks containing four context-free languages. We used TreeGen [Sun et al., 2020], one of the state-of-the-art models on these benchmarks, as our base model. We directly replace the embedding layer of TreeGen with Grape. The experimental results show that our approach improves the accuracy of TreeGen by 0.8-6.4 percentage points on six mainstream benchmark sets. Although our approach is designed for rule embedding, it also could be applied to AST token embedding. Thus, we combined Grape with Sandwich Transformer [Hellendoorn et al., 2020] on method naming to demonstrate the generality of Grape. Grape also improves the base model by 1.6 F1 score. In summary, we make the following contributions:

• We make the first attempt to learn the embedding of grammar. We design a graph structure to represent context-free grammar and use a novel neural architecture to encode the graph.
• We evaluated our approach on six benchmarks containing four context-free languages. The experimental results show that our approach is effective in learning the syntax and semantic information of the grammar and achieved 0.8-6.4 percentage points improvement over TreeGen on these benchmarks. We also evaluated our approach for an additional code-related task, method naming, to show the generality of Grape. The experimental results show that Grape also improves the performance of base models by 1.6 F1 score.

2 Proposed Approach

Figure 2 shows the overview of Grape. As mentioned before, Grape takes the context-free grammar as input and outputs the embedding of each rule. To implement this component, we first map the grammar into a novel graph structure and then use a graph neural network to produce the embeddings.

2.1 Grammar Relation Graph

In this section, we introduce the detailed structure of the graph and the approach mapping a context-free grammar into the graph. We define a context-free grammar as G(gra) = ⟨N, T, R, λ⟩, where N denotes a set of non-terminals, T denotes a set of terminals, R denotes a set of production rules, and λ ∈ N denotes a special start symbol. Especially, a production rule that can be applied to non-terminal A is represented as A -→B1 B2 · · · Bn, and an application of the rule replaces Awith the sequence B1 B2 · · · Bn.

We propose grammar relation graph to represent contextfree grammars. Formally, given a context-free grammar G(gra) , a grammar relation graph is a tuple G = ⟨V, E⟩, where V = R denotes the vertexes in the graph, and E ⊆ V × V denotes the edges and is a minimal set satisfying the following condition: for two arbitrary rules r1 = A1 -→ B11 B12 · · · B1m ∈ V and r2 = A2 -→B21 B22 · · · B2n ∈ V , (r1, r2) ∈ E if A2 = B1j for some j such that 1 ≤ j ≤ m.

Figure 2 shows an example of a grammar relation graph. On the left side, there is a set of production rules, where the leading numbers are the IDs of the production rules. On the right hand side there is the corresponding grammar relation graph of the given partial context-free grammar. Each node in the graph corresponds to a production rule in the grammar and is labeled with the ID of the rule. As shown, the rule 2 can be used to expand a non-terminal produced by rule 1, and thus node 1 has a directed edge to node 2 in the graph.

2.2 Neural Mechanism

The second part of Grape is a graph neural network (GNN). The model takes the grammar relation graph as input and outputs the vector of each rule. The overview of this part is shown in Figure 2. In this section, we will introduce the detailed structure of the GNN used in our approach.

Embedding Layer. The first layer of Grape is a one-hot encoding layer similar to the most base models. Grape transforms the unique ID of each production rule into a fixed-size vector for GNN to compute.

Static Encoding. We first encode each node in the grammar relation graph into a fixed-sized vector for GNN. Grape directly uses the ID of each production rule as the one-hot encoding label. Thus, we can encode each node in G as n1,n2, · · · ,nP by table-lookup embeddings, where P denotes the total number of rules in R. We use the static encoding of ri, as the initial embedding of the GNN.

Graph Neural Network. The computation of GNN iteratively updates the vector of nodes. In each iteration, the vector of each node is updated by combining those of its neighbors. The computation of each iteration is performed through two components. The first component, the definition encoding component, integrates the corresponding rule definition.

The second component, the neighbor encoding component, combines the vector of each node with those of its neighbors.

Definition Encoding Component. As mentioned before, the static encoding of each node encodes only the ID of the rule. This component integrates the rule content into the vertex of each node. It first encodes the rule content and then uses a gating sub-layer to combine the encoded rule content with the vector of the node.

Definition Encoding Sub-Layer. To encode the content information of each production rule, we first represent the symbol in T ⋃ N as a vector s through table-lookup embeddings. Then, for a production rule r : α -→ β1 β2 · · · βn, we adopt a full-connected layer on the corresponding token embeddings. The rule encoding of r is computed as sr = W[sα; sβ1 ; ...; sβn ], where sα and sβj are the tablelookup embeddings of the parent node α and the child node βj , andW is a trainable parameter. The sequence of the child nodes is padded to a pre-defined maximum length. These vectors are then fed to the gating sub-layer, and are integrated with the input features for each node at each iteration.

Gating Sub-Layer. The input features for each node contain rich structural information of G after several iterations. To emphasize the importance of these features, we adopt a mechanism named Gating Mechanism [Sun et al., 2020] to integrate the input features with the rule content encoding. This mechanism takes three vectors named q, c1, c2 as input and incorporate c1 with c2 through the multi-head mechanism treating q as the control vector. The detailed computation can be found in Sun et al.[2020].

For the t-th iteration, we use the input feature ri t of the node ri as the control vector to integrate itself with the corresponding definition encoding sri . Thus, the computation of node ri at the t-th iteration can be represented as mit = Gating(ri t , ri t , sri ). The vector mit is then fed to the second neural component to integrate the neighbors' information.

Neighbor Encoding Component. As the traditional GNN, the encoding of each node should be integrated with the encoding of its neighbors to extract the structural information of the graph. This component first computes the encoding of the neighbors through the adjacent matrix, and then uses a gating mechanism to combine the vector of the node with the encodings of its neighbors.

Neighbor Encoding Sub-Layer. As the traditional GNN, the encoding the neighbors of node ri at the t-th iteration can be computed as pit = ∑rj ∈G Anri rjmjt . Here, An is a normalized adjacency matrix of G. We use the normal operation proposed by Kipf and Welling [2017]: An = S-1/2 1 AS-1/2 2 . Here A is the adjacency matrix of G, S1 and S2 are the diagonal matrices with summation of A in columns and rows. To encode the direction of edges, we define a hyperparameter β(β > 1) to represent this information. For example, if node ri has a directed edge connected to rj, cell Ai,j is 1 and cell Aj,i is β.

Gating Sub-Layer. To integrate the neighbor encoding with the input vectors for each node, we apply the same sub-layer to the input vector ri t and the neighbor encoding pit . We use the input vector ri t as the control vector q to incorporate these two vectors. This computation can be represented as ri t+1 = Gating(mit , mit , pit ).

We apply the GNN layer of N iterations on the initial encoding of each node and get vectors of each production rule. Then these vectors are fed to a base model.

3 Evaluation

3.1 Experiment I: Grammar Preserving Rule Embedding

We have implemented Grape for several different benchmarks in several context-free languages. In this section, we report our experiments and the performance of Grape.

Dataset. We evaluated our approach on six benchmarks, including the HearthStone benchmark [Ling et al., 2016], two semantic parsing benchmarks [Dong and Lapata, 2016], the Django benchmark [Yin and Neubig, 2017], the Concode benchmark [Iyer et al., 2018] and the StrReg benchmark [Ye et al., 2020]. The statistics of these datasets are shown in Table 1. 2

The HearthStone benchmark contains 665 different cards of HearthStone. Each card is composed of a NL specification and a program written in Python. When processing the NL, we used the structural preprocessing as described in Sun et al. [2020]. The semantic parsing task contains two benchmarks. The input of this task is the NL specification, while the output is a short piece of lambda expressions in a specific DSL. The Django benchmark contains 18,805 lines of Python source code extracted from the Django web framework. Each line of code is annotated with a NL specification. The Concode benchmark contains 104,000 pairs of Java code and a NL specification with the programmatic context. The StrReg benchmark contains 3520 pairs of structurally complex and realistic regexes and a NL description.

The benchmarks involve four context-free languages: Java, Python, lambda expressions, and regular expressions. For Java and Python, we use the grammar extracted from their official parsers 3 . For lambda expressions, we used the grammar written by Kwiatkowski et al. [2013]. For regular expression, we use the grammar defined by Ye et al. [2020].

Metric andHyperparameters. Existing studies use different metrics for different benchmarks. StrAcc, Acc+, ExeAcc, and DFAAcc all measure the percentage of correct programs, but use different definitions for correctness. StrAcc [Yin and Neubig, 2017] considers a program as correct when it has exactly the same token sequence as the ground truth. Acc+ [Sun et al., 2019] further allows the renaming of variables. ExeAcc [Dong and Lapata, 2016] further considers the symmetry of operators. DFAAcc [Ye et al., 2020] considers a regex is correct when it is DFA-equivalent compared with the groundtruth. To compare with existing results, we followed the metrics settings in existing studies.

For the hyperparameters of our model, we set the number of iterations N = 9. The hidden sizes were all set to 256. We applied dropout after each iteration of the GNN layer, where the drop rate is 0.15. The model was optimized by Adam with learning rate lr = 0.0001. We selected the hyperparameters based on the performance of validation set of Concode. The number of iterations has slight influence on the results. As we change the number from 6 to 11, the change of model performance on Concode is less than 0.4%. We run Grape five times with different random seeds on Atis, Job and HearthStone due to the small validation set of these benchmarks. At inference time, we used beam search with beam size b = 5 following Sun et al. [2019].

2 The code is available at https://github.com/pkuzqh/Grape

3 The links of the parsers are https://docs.python.org/3/library/ast.html and https://github.com/c2nes/javalang for Python and Java.

Base model and Inference. We use TreeGen [Sun et al., 2020], which is one of the current state-of-art model on these benchmarks, as the base model. It uses a tree-based transformer to generate the rule sequence. Specially, Treegen chooses the next production rule among all possible candidates by softmax based on the outputs. In our approach, the embeddings of production rules contain rich structural and content information. Thus, we introduce the pointer network that directly selects a rule from the grammar relation graph. The pointer network is computed by

where h denotes the outputs of decoder, r denotes the outputs of Grape fed into the base model.

For training, we first construct the grammar relation graph based on the grammar of the specific language. We then build the corresponding GNN layer based on the grammar graph and connect it with the base model. Thus, it is an end-to-end training where the output of GNN is directly fed into TreeGen and the gradients can be passed backwardly.

Overall Result. Table 2 shows the performance of our approach on several benchmarks, in comparison with previous state-of-the-art models. Each line in Table 2 corresponds to an existing approach and shows its performance. The first part denotes the traditional approaches using rule-based translation but not neural models. The third part denotes the neural models pre-trained with huge extra data. As shown, our approach boosts the performance of TreeGen on all benchmarks. In particular, the performance on Atis is even better than the traditional approaches. To the best of our knowledge, this is the first time that a neural approach has outperformed the traditional approaches on this benchmark. Furthermore, Grape achieves 6.4 points improvement over TreeGen on StrReg, which is the highest among these benchmarks. We conjecture the reason is that the training set of StrReg does not contain rich usage patterns of the grammar. When the training set contains rich usage patterns, a neural network may learn the structural and content information from it, but when the usage patterns are not rich, encoding grammar definitions become critical. These results suggest that learning the grammar embedding is effective in boosting the performance of TreeGen.

Error Rate of Predicted Rules. To understand whether Grape helps the base model to predict the production rule, we TreeGen TreeGen+Grape count the error rate 4 that the predicted production rule violates the grammar constraints on Atis benchmark as shown in Table 3. We count the error rate of the top-1, top-3, and top-5 predicted production rules by these models, which is defined by the number of grammatically incorrect predictions in topk divided by the the total predictions. TreeGen with Grape all performs better compared with TreeGen. Especially, TreeGen with Grape achieves 0.15 percentage error rate of the top-1 prediction. These results show that Grape helps the base model to learn the constraint of the grammar.

Visualization of Rule Embeddings. To figure out whether Grape preserves the structural and content information of the grammar, we use the t-Distributed Stochastic Neighbor Embedding (t-SNE) model, a dimensionality reduction technique, to map the original vectors to 2-D space. Due to the space limit, we randomly choose several rules from the language for semantic parsing to show in the picture. As shown in Figure 3, rules with similar content tend to have similar representations. The rules which are relevant to node "arguments" mainly lie on the left side while the rules associated with "enti-var" lie on the right side while the rule encoding of TreeGen does not has this property. Also, rules with similar structure have similar representations. The rules that can have a common parent, such as entivar -→ evening : pd, entivar -→ afternoon : pd and entivar -→ morning : pd, have similar representations with Grape in the right subfigure. However, entivar -→ evening : pd lies far away from entivar -→ morning : pd without Grape in the left sub-figure. These observations suggest that Grape leads the model to learn a better embedding of production rules.

4 A prediction is incorrect if there are grammatically incorrect rules in the top-k predicted rules. The error rate of the top-k denotes the rate of incorrect prediction during generating.

Time Efficiency andComplexity. We further evaluated the complexity of our model. It takes 34.78s for an epoch on a single Nvidia Titan RTX with Grape on average, whereas 30.74s without Grape. And Grape has 6.5 × 105 parameters on average.

3.2 Experiment II: Grammar Preserving AST Token Embedding

Apart from the production rule sequence, we observe that several approaches [Alon et al., 2019; Sun et al., 2019], use the AST traverse sequence to represent the CFS. These approaches usually treat the AST tokens as words and adopt word embedding to represent the AST tokens. Although Grape is designed for rule embedding, Grape also can be applied to represent the AST tokens. To adapt Grape for the AST token embedding, we replace the corresponding rule ri = α -→ β1 β2 · · · βn of i-th node with α in the grammar relation graph and merge the nodes which have the same label in the graph.

To evaluate the effectiveness, we conducted an additional experiment on method naming task. In this task, the model needs to predict the name of a method given its corresponding body. Following Alon et al. [2018], the model predicts the target method name as a sequence of sub-tokens, e.g., getIndexOf is predicted as the sequence "get index of". As described by Hellendoorn et al. [2020], Sandwich Transformer (S-Transformer) adopts Transformer to extract the long dependency of the code and adopts GNN layers to learn the structural information of the code. Thus, we used STransformer, which is capable of handling long dependencies and rich structural information, as our base model.

For this task, we adopted the widely used Java benchmark [Alon et al., 2019; Alon et al., 2018], Java-small, which contains 11 relatively large Java projects. We took 9 projects for training, 1 project for validation and 1 project for test following Alon et al. [2018]. This dataset contains 691,607 examples in the training set, 23,844 examples in the validation set and 57,088 examples in the test set. We used three metrics, precision, recall, and F1 score over the target sequence as Alon et al. [2019]. We used F1 score on the development set to select the best model.

The performance of Grape on method naming task is shown in Table 4. Each line in Table 4 shows the performance measured by the three metrics on the benchmark of the corresponding approach. Compared with S-Transformer, Grape improves the performance on three metrics by 0.58, 2.47, 1.60, respectively. These results exhibit the generality of Grape.

4 RelatedWork

Code Generation. Code generation aims to generate code from a NL specification [Ling et al., 2016; Dong and Lapata, 2016; Liang et al., 2022] and has been intensively studied during recent years. The early work generates code based on templates and searching [Kwiatkowski et al., 2013; Wang et al., 2014]. Ling et al. [2016] proposed a sequenceto-sequence framework to generate code as sequences. Note that code has the constraints of grammar, which is different from NL. Thus, the abstract syntax tree (AST) was used to represent the generated code [Dong and Lapata, 2016; Yin and Neubig, 2017; Rabinovich et al., 2017; Xiong et al., 2018]. To alleviate the long dependency problem, Sun et al. applied the convolutional neural network [Sun et al., 2019] and transformer [Sun et al., 2020] for code generation. However, these existing approaches just embed the partial rule list through static labeling directly. Our approach further integrate the structural and content information of the grammar into the embeddings.

Distributed representations. Learning distributed representation for elements (e.g. words, code tokens, AST tokens) have been used to boost the performance of the neural models in several areas of natural language processing [Pennington et al., 2014; Alon et al., 2019]. Pennington et al. [2014] introduced, word2vec, an approach to learning a good representation of words based on self-supervised tasks. Devlin et al. [2018] proposed, BERT, to compute the word embedding with the sentence context via Transformer [Vaswani et al., 2017]. Inspired by this work, [Alon et al., 2019] used a pathattention based model to learn the representation of code. In this paper, we propose Grape to learn a grammar-preserving rule embedding via a well-designed GNN.

Graph Neural Network. Graph Neural Network has been widely investigated in recent years. The concept of GNN was proposed byC Scarselli et al.. Based on this framework, various GNNs have been proposed [Kipf and Welling, 2017; Li et al., 2016; Zhong and Mei, 2020]. In particular, Li et al. [2016] proposed a gated graph neural network(GGNN), which adapts the LSTM layer to GNN for better encoding the node.

5 Conclusion

In this paper, we propose an approach to learn the distributed representation of context-free grammar. We first introduce a novel graph to represent the grammar. Then we adopt a gated graph neural network to extract the structural information of production rules and integrate the content information with the node embedding via a gating layer. To confirm the effectiveness of our approach, we conducted experiments on several widely used benchmarks on code generation and semantic parsing. The results show that Grape learns a good embedding of the production rules and the combined model surpasses the existing state-of-the-art methods on these benchmarks.

Acknowledgements

This work is sponsored by the National Key Research and Development Program of China under Grant No. 2019YFE0198100, the Innovation and Technology Commission of HKSAR under Grant No. MHP/055/19, National Natural Science Foundation of China under Grant No. 61922003 and a grant from ZTE-PKU Joint Laboratory for Foundation Software.