利用机器学习技术来分析程序已经引起了广泛的关注，一个关键问题是如何很好地表示代码片段以进行后续分析。传统的信息检索方式将程序视为自然语言文本，这样会遗漏代码中重要的语义信息，基于抽象语法树（AST）可以更好的表示源代码。问题是ast的规模较大，容易出现长期依赖的问题。所以提出了一种新的模型ASTNN，它的主要思想是将AST分割成一组小的语法树序列。最后通过捕获语句的词汇和语法知识将语句树编码为向量。

二：引言

2.1传统处理代码的方式

代码表示：传统方法通常将代码片段表示为令牌序列或令牌包，这种表示方法常用于代码克隆检测、错误定位和代码作者分类等任务。
基于文本的方法：这些传统方法通常将代码处理成自然语言文本，就像处理常规文本数据一样。它们可能使用词汇标记化和词袋模型等技术来处理和分析代码，就像处理常规文本数据一样。
使用潜在语义索引（LSI）和潜在狄利克雷分配（LDA）：一些研究人员已经应用了潜在语义索引（LSI）和潜在狄利克雷分配（LDA）等技术，用于分析源代码。

问题与局限性：然而，根据文中提到的，这些方法的一个共同问题是它们假设底层的文集即源代码）由自然语言文本组成。尽管代码片段与普通文本有一些共同之处，但由于其更明确的结构信息，它们不应该简单地用基于文本或令牌的方法来处理。

2.2 改进方式（注重结构信息，语法知识的提取）

Abstract Syntax Tree (AST)

Recursive Neural Network (RvNN)

Tree based CNN or Tree-LSTM

这些方法可以更好的捕获词法（即ast的叶节点如标识符）和语法（即ast的非叶节点如语法构造while语句）信息。

问题

与NLP中的长文本类似，这些基于树的神经模型也容易受到梯度消失问题的影响
这些方法要么将ast转换为ast，要么直接视为完整的二叉树，以简化和提高效率，这破坏了源代码的原始语法结构，甚至使ast更深入。转换后的和更深层次的ast进一步削弱了神经模型捕获更真实和更复杂的语义的能力。

2.3 提出新方法（ASTNN）

2.3.1 什么是ASTNN？

它可以表示不必是可编译的代码片段。
在语句级别将一个代码片段的大AST分割成一组小树，并对所有语句树执行基于树的神经嵌入。
它生成可以表示语法和语法知识的语句向量。

2.3.2 模型简图（c）

这里把方法声明视为一个特殊的声明节点。第7行和第15行之间的代码片段包含一个完整的Try语句，而第5行和第6行之间的代码片段只包含初始化变量sb的LocalV可写语句。对于每个语句，比如在主体中包含头和其他语句的Try语句，我们分割了语句的头和所有包含的语句。这样就把完整的AST分割成小的语法树。

2.3.3 简单流程

原始代码片段中相应的语句（或语句头）也用虚线标记。
在多路语句树上设计了一个递归编码器来捕获语句级的词汇法信息和语法信息，然后用语句向量来表示它们。
使用双向门控递归单元（GRU），一种递归神经网络，利用语句的序列自然性，最终得到整个代码片段的向量表示。

2.3.4 结论：

提出了一种新的神经源代码表示方法，它可以捕获词汇级、语句级的句法知识和语句的自然性

2.4 回顾一下AST

AST详解

代码转换工具（ASTExplorer）

抽象语法树（AST）是一种旨在表示源代码[36]的抽象语法结构的树。AST的节点对应源代码的构造或符号。与普通的源代码相比，ast是抽象的，不包括标点符号和分隔符等所有细节。例如方法readText和WhileStatement语句。

2.5 使用基于标记的方法进行源代码搜索

简单举个例子


#file1.py
def calculate_total(price, quantity):
    return price * quantity
 
def display_result(total):
    print(f'Total: {total}')
 
 
 
#file2.py
def calculate_total(price, quantity):
    if price < 0 or quantity < 0:
        return None
    return price * quantity
 
def main():
    price = 10
    quantity = 5
    total = calculate_total(price, quantity)
    display_result(total)

索引化


{
    "calculate_total": [
        {"file": "file1.py", "line": 1},
        {"file": "file2.py", "line": 1}
    ]
}

进行查询


query = "calculate_total"
results = index.get(query)
 
 
[
    {"file": "file1.py", "line": 1},
    {"file": "file2.py", "line": 1}
]

三：ASTNN结构

3.1 详细结构：

3.2 模型介绍

首先，通过现有的语法分析工具，可以将源代码片段转换为大型ast。对于每个AST，我们按语句的粒度将其分割，并通过前置遍历提取语句树的序列。

形式上，给定一个AST T和一组语句AST节点S，T中的每个语句节点s∈S对应一个源代码语句。将MethodDeclaration视为一个特殊的语句节点，因此S=S∪{MethodDeclaration}。对于嵌套语句，我们定义了单独的节点集P={block，body}。block用于分割嵌套语句的头和主体，如Try语句和W hile语句，body用于方法声明。语句节点s∈S的所有后代都用D (s)表示。对于任何d∈D (s)，如果存在一个从s到d到一个节点p∈P的路径，这意味着节点d包含在语句主体中的一个语句中。我们称s的节点为已做好的子语句节点。然后由语句节点∈s根的语句树（st树）是由节点s及其所有后代组成的树。

3.3 举个例子


语句1：int x = 5;
 
语句2：System.out.println("Hello World!");
 
 
对于语句1，其ST树如下所示：
 
```
Statement1
└── Declaration
    ├── Type
    │   └── int
    └── Variable
        ├── Identifier
        │   └── x
        └── Value
            └── 5
```
 
对于语句2，其ST树如下所示：
 
```
Statement2
└── MethodInvocation
    ├── Target
    │   └── System.out
    ├── MethodName
    │   └── println
    └── Arguments
        └── StringLiteral
            └── "Hello World!"

在这个例子中，语句1和语句2分别是两个独立的ST树。根据定义，对于每个语句节点s，其所有后代节点集合D(s)包括该语句节点及其所有后代节点。对于每个后代节点d∈D(s)，如果存在一条从s到d的路径通过一个节点p∈P，那么节点d被语句s的主体中的一个语句包含。在这个例子中，语句1的后代节点集合D(Statement1)包括Statement1、Declaration、Type、int、Variable、Identifier和Value。语句2的后代节点集合D(Statement2)包括Statement2、MethodInvocation、Target、System.out、MethodName、println、Arguments和StringLiteral。因此，对于语句1的每个后代节点d∈D(Statement1)，存在一条从Statement1到d的路径通过一个节点p∈P（在这个例子中，p是Declaration节点），所以节点d被语句1的主体中的一个语句包含。同样，对于语句2的每个后代节点d∈D(Statement2)，存在一条从Statement2到d的路径通过一个节点p∈P（在这个例子中，p是MethodInvocation节点），所以节点d被语句2的主体中的一个语句包含。

3.4 粒度问题

粒度太大我们也可能会遇到第二节中提到的梯度消失问题。但是如果它太小（例如，AST的节点级别），模型将成为一个基于标记的RNN，它可能捕获更少的语句语法知识。实验结果表明，所提出的语句级粒度更好，因为它在st树的大小和语法信息的丰富度之间有很好的权衡。

3.5 在多路st树上Encoder

给定st树，设计了一个基于RvNN的语句编码器，用于学习语句的向量表示。由于AST中存在各种特殊的语法符号，通过AST的前序遍历获取所有符号作为训练语料库。使用word2vec算法来学习这些符号的无监督向量，并将训练好的符号嵌入作为语句编码器的初始参数。由于AST的叶节点包含了表示词法信息（如标识符）的信息，我们的符号嵌入可以很好地捕捉词法知识。以图1中以MethodDeclaration节点为根的第一个ST树为例，编码器遍历ST树并递归地将当前节点的符号作为新的输入与其子节点的隐藏状态一起计算。这里展示了前两层。在ST树中，两个子节点readText（即方法名）和FormalParameter（即方法的参数定义语法结构）以及其他兄弟节点丰富了MethodDeclaration的含义。如果我们将ST树转换为二叉树，例如将readText节点移动到FormalParameter节点的一个子节点或后代节点，原始的语义可能会被破坏。因此，将原始的多路ST树作为输入。具体而言，给定一个ST树t，令n表示一个非叶节点，C表示其子节点的数量。在开始时，使用预训练的嵌入参数We∈R|V|×d，其中V是词汇表大小，d是符号的嵌入维度，可以通过以下公式获得节点n的词法向量：

V_{n}=W_{e}^{T}X_{n}(1)

其中xn是符号n的独热表示，vn是嵌入。接下来，节点n的向量表示通过以下公式计算：

h=σ({W_n}^\top v_n+\sum_{i\in[1,C]}h_i+b_n) (2)

其中Wn∈Rd×k是具有编码维度k的权重矩阵，bn是偏置项，hi是每个子节点的隐藏状态，h是更新后的隐藏状态，σ是激活函数，例如tanh或恒等函数。在本文中，使用恒等函数。类似地，我们可以递归地计算和优化ST树t中所有节点的向量。此外，为了确定节点向量的最重要特征，所有节点被推入堆栈，然后通过最大池化进行采样。也就是说，我们通过公式3得到ST树和相应语句的最终表示，其中N是ST树中节点的数量。

et=[max(hi1),···,max(hik)],i=1,···,N (3)

这些语句向量可以捕捉语句的词法和语句级别的句法信息。

3.6 批处理


Input: The array of root nodes in batched ST-trees, B;
Output: The vectors of batched ST-trees, BV ;
1: L ← len(B);
2: BI ← [1, ··· , L]; // ST-tree indexes in the batch
3: S ∈ RN×L×k ← φ; // record all node vectors
4: Call DynamicBatch(B,BI);
5: Perform pooling on S by Eq. 3 to get BV ∈ RL×k;
6: return BV ;
7: function DYNAMICBATCH(ns, ids)  The batched
current nodes ns and their indexes ids
8: l ← len(ns);
9: BC ∈ Rl×d ← 0; // initialize the matrix
10: Calculate Eq. 1 in batch for ns and fill into BC
according to ids;
11: Initialize two array list C, CI ← φ to record children
nodes and their batch indexes;
12: for each node ∈ ns do
13: for each children node child of node do
14: group child by its position, and record child
to C and its batch index to CI ;
15: end for
16: end for
17: for i = 0 → len(C) − 1 do
18: ˜
h ∈ Rl×k ← 0;
19: η ← DynamicBatch(C[i], CI[i]);
20: ˜
h ← ˜
h + η;
21: end for
22: Calculate h by Eq. 2 in batch;
23: BZ ∈ RL×k ← 0; // for calculating BV
24: Fill h into BZ according to ids and add BZ to S;
25: return h;
26: end function

本文中的批处理是指对多个样本（即代码片段）同时进行处理的算法。在算法1中，我们首先将L个批次的ST树进行批处理，并从根节点开始广度优先遍历它们（第4行）。对于批次中相同位置的当前节点ns，我们首先在批处理中计算方程1（第10行），然后通过节点位置（第12-16行）检测和分组所有子节点。如图4所示，我们通过节点位置将子节点分为三组，并将这些组记录在数组列表C和CI中。基于这些组，我们对所有子节点进行递归批处理（第17-21行）。在获取所有子节点的结果后，我们通过批处理计算方程2（第22行），并将所有节点向量推入Algorithm 1中的ST树向量堆栈S（第24行）。最后，我们通过使用方程3对S进行汇集，得到批处理ST树的向量BV（第5行）。

3.7 表示语句的顺序

基于st树向量的序列，利用GRU来跟踪语句的自然性。给定一个代码片段，假设从其AST中提取T STtree，让Q∈R^T*K=[e1，···，et，···，eT ]，t∈[1，T]表示序列中的ST树编码向量.。在t时刻，跃迁方程如下：

r_{t} =\sigma(W_{r}e_{t}+U_{r}h_{t-1}+b_{r})

z_{t} =\sigma(W_{z}e_{t}+U_{z}h_{t-1}+b_{z})

tilde{h}_{t} =tanh(W_{h}e_{t}+r_{t}\odot(U_{h}h_{t-1})+b_{h})

h_{t} =(1-z_{t})\odot h_{t-1}+z_{t}\odot\tilde{h_{t}}

其中rt是复位门来控制先前状态的影响，zt是结合过去和新信息的更新门，h˜t是候选状态，用于进行线性插值与先前状态˜−1来确定当前状态。Wr，Wz，Wh，Uz，∈R^k*m是权重矩阵br，bz是偏差项。通过迭代计算所有时间步长的隐藏状态，可以得到这些语句的序列自然性。为了进一步提高循环层捕获依赖信息的能力，我们采用了双向GRU [34]，其中将两个方向的隐藏状态连接起来，形成如下的新状态

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/weixin_40725706/article/detail/735569