Page 199 - 《软件学报》2025年第10期
P. 199
4596 软件学报 2025 年第 36 卷第 10 期
遍历完成后, 一棵新的语法树就构建完成了. 第 3 个方法为 insert, 这是将新节点插入到语法树中的方法, 该方法的
参数分别为根节点 rootNode, 新节点的父节点 fatherId 以及一个新节点 newNode, 从根节点进行判断当前节点的
id 与 newNode 节点的父节点的 id 是否一致, 如果一致就将 newNode 节点插入到当前节点的子节点列表 sonList
中, 否则从根节点的子节点列表开始深度优先遍历每一个节点进行判断. 总体的过程为先建立新的抽象语法树根
节点, 然后遍历编译单元中的每一个正常节点, 将每个节点转化为一个新的节点插入到新的抽象语法树中. 通过该
算法得到的抽象语法树不仅包含了原本抽象语法树的全部语法信息, 而且结构更加简单, 其链式存储方式为后面
的变异操作提供了方便.
算法 1. 抽象语法树优化算法.
输入: 抽象语法树 T;
输出: 优化后的抽象语法树 T'.
1. function setNode(curNode)
2. rootNodeName ← T.getName
3. rootNodeValue ← T.getValue
4. rootId ← setId(rootNodeName, rootNodeValue)
5. newNode ← setNode(rootId, rootNodeName, rootNodeValue)
6. return newNode
7. end function
8. rootNode ← T'.buildrootNode (rootNodeId, rootNodeName, rootNodeValue)
9. while i = 1 to n do
10. int index ← 1
11. ti ← getTree(ni, index, sign)
12. T.add(ti)
13. end while
14. function getTree(rootNode, curNode)
15. childrens ← curNode.getChildren
16. newNode ← setNode(curNode)
17. curNodeFatherId ← curNode.getFatherId
18. T'.insert (rootNode, curNodeFatherId, newNode)
19. for all node ∈ childrens do
20. getTree(rootNode, childrens)
21. end for
22. end function
23. function insert(rootNode, fatherId, newNode)
24. if rootNode.id is fatherId and rootNode.allChilds.notExist(newNode) then
25. rootNode.sonList.add(newNode)
26. end if
sonList ← root.getSonList
27.
28. if sonList is not null then
29. for all node ∈ sonList do
30. getTree (node, fatherId, newNode)
