Scratch是一种适合少年儿童使用的可视化编程语言，并在全球的编程教育领域中受到广泛地关注.由于目前各大教育编程平台都开始使用Scratch3.0版本，而已有的特征提取和检测系统并不支持新版本，为此，提出了一种基于链表数据结构和一种语言识别工具（ANTLR）的面向Scratch3.0的特征提取和检测系统.实验结果表明，该系统可以有效地从项目中提取编程特征，并为学生和教师提供反馈，其检测性能和检测稳定性比Scratch2.0均有所提升.
As a visual programming language for children, Scratch has received wide attention in the programming education. Considering that Scratch has evolved to the latest version 3.0 and its storage structure changes significantly from the previous version, the existing methods cannot be directly applied to project analysis. A new feature extraction and detection system based on linked list data structure and another tool for language recognition (ANTLR) was presented to solve the problem. Experimental results show that the system can effectively extract programming features from the projects and provide feedback to students and teachers. Moreover, its detection performance and stability perform better than the original methods in Scratch2.0.
Scratch是麻省理工学院推出的可视化编程社区，学生可以在其上创建、改编和发布项目.目前，该编程社区上有超过300万注册用户和300万个来自全球各地的共享项目.诸如用户和项目信息等大量的共享数据能够构建分析Scratch编程功能的提取和检测模块，基于该系统获得的编程作品检测结果可以帮助学生改进作品质量，进而提升编程能力.
目前各教育编程平台都开始使用Scratch3.0版本，而已有的特征提取和检测系统并不支持这一新版本，主要原因是在Scratch2.0的存储文件中，编程块之间构成了类似数组的高度耦合的结构，而在Scratch3.0中每个编程块以特有的id编号进行解耦，构成了类似链表的数据结构.因此，基于之前对Scratch2.0版本的特征提取和检测的相关工作，针对Scratch3.0版本在JSON文件数据结构上的特点，采用解耦的设计思想[1]对特征的提取检测步骤进行优化.最终，经过与Scratch2.0进行的对比实验证明其达到了预期的检测效果.
1 相关工作Meerbaum-Salant等[2]将Scratch产生的编程习惯大致分为2类：从单个Scratch块开始，完全自下而上的开发过程；极其细粒度的编程.由此了解到不良的编程习惯可能会对学生将来学习高级编程语言产生不良的影响，因此有必要对Scratch编程作品进行特征检测并对类型加以区分.
Wolz等[3]开发了一种可以帮助人们理解Scratch设计模式的工具. Boe等[4]开发了一种名为Hairball的Scratch静态分析框架，它可以帮助理解Scratch的诸如嵌套级别、循环次数等模式.由此可以粗略地区分用户的行为模式，这也为后续的特征挖掘提供了理论基础.
Techapalokul等[5]采用抽象语法树(AST, abstract syntax tree)的思想对Scratch的JSON格式文件进行解析.分析器使用基于Java的语言处理框架JastAdd[6]实现，最终检测到的代码特征由第三方JavaScript库在浏览器中呈现给用户.他们提出了12种检测代码块编程特征的方法[7]，并通过Scratch数据集验证了其编程特征检测方法的有效性.但是对于具有未初始化脚本等功能的项目，它们缺乏相应的检测规则.因此，提出了9种新的编程特征检测规则，并增强了检测结果的可靠性.
Fowler[1]揭示了重构过程并提到了面向对象软件开发中常见的22种不利于代码重构和复用的代码坏味道，这给特征检测提供了许多借鉴之处.
由于Scratch程序是在图形用户界面中开发和运行的，检测Scratch程序的各种编程特征有一定的困难，因此从Scratch项目的JSON文件入手，该JSON文件中保存有Scratch项目完成后的块的所有静态信息. Quality Hound[5]是一种能够自动检测Scratch作品多种编程特征的在线工具. Quality Hound对Scratch的JSON文件利用AST的思路解析为分析程序使用的内部表示，最终可将AST解析为不同的语法子树.
作为一种通过语法描述来自动构造语法解析生成器的框架，语言识别的另一个工具(ANTLR, another tool for language recognition) [8]具有LL(*)解析策略灵活性的优势，因此选择ANTLR来实现该编程特征检测功能.补充了9种新的编程特征检测规则，实验结果表明，新增的特征检测效果也达到了已有的12种编程习惯检测的平均检测水平，具有较好的检测效果.
Scratch2.0已经在少儿编程领域中使用得非常广泛，而Scratch3.0已于2019年1月2日正式取代Scratch2.0.已知目前有关Scratch的检测方法都是基于2.0版本的，并没有针对3.0版本提出新的检测方法.但是3.0版本在底层的数据存储结构上有了巨大的变化，因此有必要针对Scratch3.0的数据结构新特性改进编程特征检测系统.
2 Scratch3.0编程特征检测系统 2.1 系统描述图 1显示了Scratch中特征提取和特征检测的系统模型.首先，从Scratch网站获取大量数据；然后，通过Scratch Feature Extraction子系统提取有效特征，这些有效功能由功能过滤器过滤并存储在特征数据库中.用户可以拖放屏幕上的可视化编程块完成Scratch作品并提交到服务器，然后作品经过格式提取并将其输入到特征检测中，最后在特定的网页上输出分类结果和检测详情.
|
图 1 Scratch特征提取与检测系统 |
由于Scratch2.0底层的数据结构中各个块堆放在一起，这一设计的不合理之处使得很难从JSON文件中抽象出便于解析的数据结构.因此Scratch2.0的检测更适合采用基于ANTLR的特征检测，但是特征提取和特征检测过程都是基于ANTLR v4，而ANTLR与JSON数据格式耦合度很高，这导致特征检测规则的可读性较差，修改和后期完善的难度较大.
在Scratch3.0中，由于JSON信息数据结构设计得完善，采用了使特征提取和特征检测过程进行解耦的思想. 图 2和图 3分别展示了采用解耦思想的特征提取模块和特征检测模块.
|
图 2 Scratch3.0特征提取模块 |
|
图 3 Scratch3.0特征检测模块 |
在特征提取过程的预处理阶段，在遍历JSON的键值对的过程中ANTLR只负责对结构特征的数据提取，并将其转换为与JSON格式无关的数据表格式.
特征检测过程中则使用了基于Python语言的Pandas统计数据分析包，Pandas提供了很多类似SQL的查询统计功能，且相比Python，其性能更好，操作更简单.
3 实现方案 3.1 块信息数据表在Scratch2.0的JSON文件中，相连接的块之间构成了脚本结构(类似于函数)，并在JSON文件中耦合在一起.而在Scratch3.0中每个编程块之间是独立的且都有一个唯一id，通过父节点id和子节点id确定块之间的先后位置，构成了类似链表的数据结构.其好处是各个编程块之间是解耦的，缺点是存储的数据结构冗余度较大，比如某个作品中的Scratch2.0版本的JSON文件大小有17 KB，键值对总数有700个，而该作品的Scratch3.0版本中的JSON文件大小有41 KB，键值对总数则有2 647个.因此，根据JSON数据结构[9]设计了可以存储Scratch3.0的JSON信息的数据表结构.
如表 1所示，这里分为共有字段和各类型的特有字段，JSON中的任何信息块均属于以下5种类型之一，每个信息块包含共有字段和自身所属的数据类型的特有字段.
|
表 1 Scratch块信息表 |
表 1中的共有字段主要表明块所属角色的信息：fileName字段是指文件名称；isStage用于区分是否为舞台或是角色；name表明了该角色的名字(该名字不可重复)；data_type指该块的数据类型(变量型、列表型、块型、注释型)；detection_type和detection_sub_type存储的分别是块的检测信息和子类别信息，两者都在检测结束后由检测模块进行填充.
根据共有字段中的data_type类型，数据块信息中的特有字段各不相同.根据对Scratch3.0的文件结构进行解析，将其归纳为5种块类型.以blocks类型的块为例，它包含如fileName等所有的7个共有字段和id、opcode、next等blocks类型的6个特有字段.
3.2 基于Pandas的特征提取规则基于常见的编程味道以及块信息的统计难度将特征检测分为如表 2所示的3类.
|
|
表 2 检测特征分类表 |
表 2中，“块信息基本统计”的统计方式最简单，主要是基于Pandas包进行计数统计；“块信息复杂统计”需要基于blocks类别块的inputs和fields结合不同的数据表字段综合统计；而“脚本信息复杂统计”类则最复杂，需要构建新脚本结构并对序列进行对比.
这里构建脚本信息的方法是先筛选出所有能作为起始位置的编程块，然后从上述起始块结合next字段递归构建完整的脚本链表.
3.3 检测算法详细的Scratch检测算法如算法1所示.
整个过程大致分为3部分，即从JSON中提取Scratch块信息(2~9行)、根据Pandas检测规则对Scratch块信息进行检测(10~15行)、对检测结果进行统计和分类(17~20行).
在第1部分中，采用了基于ANTLR的JSON解析技术[10]，根据设计的Scratch块信息表以及块信息提取规则[8]对JSON进行顺序遍历并根据提取规则将块信息加入到块结构数据库中.
在第2部分中，根据数据库中存储的块信息以及设计的Pandas检测规则对数据表进行高效的规则检测，然后将结果写入到预留在数据表中的detection_type和detection_sub_type字段中.
在第3部分中，基于预设的分类，系统将统计结果进行分类并输出分类统计结果.
算法 1 Scratch特征检测
输入： Scratch文件(file)；块结构信息(BSM)；Pandas特征检测规则(PFDR)；特征分类规则(FCR)
输出：检测特征(DF)
1 for all file such that file∈JSON do
2 extract JSON from file
3 generate AST from JSON by ANTLR Parser
4 while ParseTreeWalker∈AST do
5 if enter a JSON rule then
6 collecting block message from BSM
7 save block message to BSM Database
8 end if
9 end while
10 while block message ∈ BSM Database do
11 if enter a PFDR then
12 collecting detection message from BSM Database
13 save detection message to detection Database
14 end if
15 end while
16 end for
17 for all feature such that feature.class∈PFDR do
18 count detection message from detection Database
19 add feature to FCR.class
20 end for
21 return DF
相比Scratch2.0中的检测方法，Scratch3.0检测的最大优势在于将各部分检测规则拆分开并将过程结果进行保存.同时，考虑到算法的扩展性单元测试的方便，调试时可以基于Pandas在每个步骤之间输出csv格式的过程结果，并且采用了和Scratch2.0检测算法一致的数据输出格式，增强了算法的可读性和扩展性.
4 实验与结果分析 4.1 实验准备 4.1.1 实验环境为了尽可能与实际的使用环境一致，采用了与阿里云服务器相同配置的环境进行实验，硬件配置为8核CPU、16 GB内存，软件环境Ubuntu 16.04 64位、Python3.6，使用的Chrome浏览器版本为59.0.3071.115.
4.1.2 实验数据集本实验采用的数据集如表 3所示.
|
|
表 3 实验数据集详情表 |
Scratch官网数据集：在Scratch官方编程网站上从不同题材的作品中随机下载了500个Scratch2.0作品和500个Scratch3.0作品.根据Scratch官网的统计信息，用户的年龄分布主要集中在9~18周岁，并且各个年龄段的用户均有参与，用户遍布美国、中国、西班牙、巴西等全球各大洲，因此基本可以代表全世界学生编程作品样本.
金华市中小学生计算机现场制作比赛数据集：与当地教育部门合作承办了金华市中小学生计算机现场制作比赛的活动并获取了金华市第一届中小学生计算机现场制作比赛的比赛作品.本次比赛共有263人参加，共获取有效样本252份.参赛选手全部使用Scratch2.0语言，需要在2 h内完成指定题材作品的制作.与Scratch官网数据集相比，该数据集最大的特点是在当地教育局的监督下，经过严谨的比赛流程设计与实施，因此可以代表国内当前学生编程作品样本.
为了进行对比，采用了将Scratch2.0作品上传到Scratch官网并转换为Scratch3.0然后保存下来的方法来获取对应的Scratch3.0版本作品.经过人工检查确认，经过转换后的Scratch3.0保留了所有的Scratch2.0信息，实现了无损转换.
4.2 算法性能为了在对比实验中有效控制唯一变量，采用了金华比赛数据集的Scratch2.0和Scratch3.0进行性能对比，根据同一个作品的2.0和3.0版本进行耗时对比，对比结果如图 4所示.
|
图 4 算法性能对比 |
基于对Scratch2.0和Scratch3.0的检测算法原理进行分析，可知两者的检测算法时间复杂度均为O(n)，为线性变化.从图 4中可以看到，当单个作品的规模增大时，Scratch2.0的检测算法明显要比Scratch3.0增长得快.经过线性拟合大致得到Scratch2.0的性能拟合曲线为y=0.588 6x-0.966 9，其中R2=0.453 7；Scratch3.0的性能拟合曲线为y=0.284 2x+0.714 5，其中R2=0.793 8.因此，可知Scratch3.0检测算法的增长速度约为Scratch2.0的一半，在大规模作品的检测上优势明显.
4.3 算法稳定性为了在对比实验中有效控制唯一变量，采用了金华比赛数据集的Scratch2.0和Scratch3.0进行性能对比，根据同一个作品的2.0和3.0版本进行耗时分布对比，对比结果如图 5所示.
|
图 5 算法稳定性对比 |
由图 5可知，整体来看，Scratch2.0的耗时分布与Scratch3.0基本一致，中位数Scratch2.0比Scratch3.0要低，但细节上Scratch2.0会出现波动较大的异常值点且分布更分散，而Scratch3.0整体分布更集中，性能更稳定.
4.4 算法检测成功率检测成功率需要采用更广泛的数据集，因此采用了从Scratch官网的数据集.检测结果如图 6所示，整体来看两者的识别率稳定在95%上下且相差不大并均已满足识别预期的效果.
|
图 6 算法功能检测对比 |
考虑到codinggo-Scratch3.0检测采用解耦的设计思路，因此算法有良好的扩展性和可读性，进一步提升识别率更容易，因此codinggo-Scratch3.0的检测算法潜力更大.
同时，也横向对比了drscratch的检测成功率，codinggo-Scratch3.0的检测成功率高于drscratch的成功率，并且20种特征检测多于drscratch的10种检测规则.
4.5 算法输出随机选取Scratch3.0实例来验证Scratch3.0的作品检测功能是否正常，能否按照预期的检测规则输出正确的结果.
如图 7(a)所示，Scratch3.0实例作品中存在一个角色和一个有效脚本，其中存在一个名为my variable的滥用的全局变量，存在一个名为Sprite1的无意义的角色命名，存在一个没有起始块的死代码块以及2个使用了字符串信息的脚本.
|
图 7 Scratch3.0项目实例及检测结果 |
最终的输出结果如图 7(b)所示，与预期的检测结果一致，功能正常.
5 结束语为了解决已有的特征提取和检测系统不支持Scratch3.0版本的问题，提出了一种基于链表数据结构和ANTLR的面向Scratch3.0的特征提取和检测系统.此外，对其与Scratch2.0版本的检测方法进行了性能、稳定性、功能上的对比实验，结果表明，其检测性能和检测稳定性比Scratch2.0均有所提升，达到了预期的功能目标.同时，由于检测采用解耦的算法设计思想使算法有良好的扩展性和可读性，所以Scratch3.0检测算法的改进和提升空间更大.
| [1] |
Fowler M. Refactoring:improving the design of existing code[M]. [S.l.]: Addison-Wesley Professional, 2018.
|
| [2] |
Meerbaum-Salant O, Armoni M, Ben-Ari M. Habits of programming in scratch[C]//Proceedings of the 16th Annual Joint Conference on Innovation and Technology in Computer Science Education-ITiCSE'11. New York: ACM Press, 2011: 168-172.
|
| [3] |
Wolz U, Hallberg C, Taylor B. Scrape: a tool for visualizing the code of Scratch programs[C]//Poster Presented at the 42nd ACM Technical Symposium on Computer Science Education. Dallas: [s.n.], 2011: 100-110.
|
| [4] |
Boe B, Hill C, Len M, et al. Hairball: lint-inspired static analysis of scratch projects[C]//Proceeding of the 44th ACM Technical Symposium on Computer Science Education.[S. l.]: ACM, 2013: 215-220.
|
| [5] |
Techapalokul P, Tilevich E. Quality hound: an online code smell analyzer for scratch programs[C]//2017 IEEE Symposium on Visual Languages and Human-Centric Computing (VL/HCC). New York: IEEE Press, 2017: 337-338.
|
| [6] |
Hermans F, Stolee K T, Hoepelman D. Smells in block-based programming languages[C]//2016 IEEE Symposium on Visual Languages and Human-Centric Computing (VL/HCC). New York: IEEE Press, 2016: 68-72.
|
| [7] |
Techapalokul P, Tilevich E. Understanding recurring quality problems and their impact on code sharing in block-based software[C]//2017 IEEE Symposium on Visual Languages and Human-Centric Computing (VL/HCC). New York: IEEE Press, 2017: 43-51.
|
| [8] |
Parr T. The definitive ANTLR 4 reference[M]. [S.l.]: Pragmatic Bookshelf, 2013.
|
| [9] |
Wang Xiaolei, Huang Xinmin, Yan Chang, et al. Analysis of scratch project with process data[C]//2018 IEEE International Conference on Consumer Electronics-Taiwan (ICCE-TW). New York: IEEE Press, 2018: 1-2.
|
| [10] |
Chang Zhong, Sun Yan, Wu Tinyu, et al. Scratch analysis tool(SAT): a modern scratch project analysis tool based on ANTLR to assess computational thinking skills[C]//2018 14th International Wireless Communications & Mobile Computing Conference (IWCMC). New York: IEEE Press, 2018: 950-955.
|