Page 291 - 《软件学报》2024年第6期
P. 291
周光有 等: 基于关系图卷积网络的代码搜索方法 2867
建了代码图. 代码图由语法节点、语法令牌和对应的边构成, 其骨干结构是代码片段的抽象语法树 (AST). 一个
代码片段的抽象语法树由元组 ⟨N,T,X, s,δ,ϕ⟩ 表示, 其中 N 是一组非终端节点, T 是一组终端节点, X 是一组值,
s ∈ N 是根节点. 函数 δ : N → (N ∪T)∗ 将非终端节点映射到对应的子节点列表, 其中, ∗ 表示 Kleene 算子, (N ∪T)∗
ϕ : T → X 将终端节点映射到与之相关的值. 而且除了根节点之外的
是由括号里的符号生成的一个无穷集合. 函数
每个节点在它的子节点列表中都只出现一次, 语法节点对应 (N ∪T) 中的节点, 语法令牌对应终端节点的值.
/*
Implements the euclidean algorithm Natural language description
find the greatest common divisior of a and b
*/
public static int Greatest_common_divisor (int a, int b) {
while (b != θ) {
if (a > b)
a=a−b;
else
b=b−a;
}
return a;
} Corresponding code snippet
图 3 代码片段的实例
抽象语法树对代码片段进行词法分析和语法分析得到了有效表征代码语义的树结构, 但缺乏节点之间的数据
流关系表达. 这里命名 3 种类型的边来增强 AST 的表示: Child 边用于连接 AST 中的所有语法节点, 在图中用黑
色箭头表示; NextToken 边用于连接每个语法令牌和它的下一个语法令牌, 能够在图中保留程序片段的顺序序列
信息, 在图中用蓝色实线表示; LastLexicalUse 边用于连接变量标识符和它最近一次在代码中的词汇用法, 在图中
用绿色虚线表示. 对于实现欧几里得算法的代码片段, 图 4 展示了相应的代码图构建结果.
if
Method
declaration
Public ClassOr BlockStmt
InterfaceType
Parameter
Int Greatest_com Parameter WhileStmt
mon_divisor
PrimitiveType PrimitiveType b
IfStmt ReturnStmt
Int a Int NEExpr
Variable ExpressionStmt Variable
while Variable Expression
GTExpr Stmt AssignExpr return a
语法节点
a b Variable SubExpr
Variable Variable
else Variable Variable
语法标记 a b
AssignExpr b
b a
Variable
Child 边
SubExpr
NextToken 边 a
Variable Variable
LastLexicalUse 边 a b
图 4 代码图的示例