1.本发明涉及程序自动测试技术领域，尤其涉及一种token级的程序输入文法自动生成方法。
背景技术：2.在软件自动测试过程中，软件通常只接受某些特定格式的输入，而如果一个输入不符合格式的要求将会被软件拒绝，并可能产生输入错误报告。对于复杂结构的输入格式，通常会有一些输入文法，可以由正则表达式或上下文无关文法指定，比如编程语言文法。然而上述输入文法可能是不可用的，即使存在一些对输入文法的描述，比如自然语言的描述，文法也可能是不完整的，而且很少采用机器可读的格式。当输入格式复杂的软件的输入文法不可用时，软件的自动测试就会变得非常具有挑战性。如在符号执行和模糊测试的过程中，可能会生成大量不满足输入格式要求的输入而被软件拒绝，使得测试过程无效或者低效，例如导致代码覆盖率低或无法检测程序错误，尤其是功能错误。如果输入在格式检查阶段被拒绝，则软件不会执行测试功能代码。因此通过文法学习可以提高接受复杂输入软件的自动测试能力，利用文法学习可以显著提高自动测试工具的有效性和效率，例如可以使用学到的文法进行基于文法的灰盒模糊测试或面向文法的符号执行。
3.为复杂的解析程序自动综合输入文法是很有挑战的，传统的文法综合方法有不同的可行性、有效性和效率，不同方法在各方面表现不同，例如软件源代码的可用性(例如，白盒或黑盒)，所学文法的表现力和可用的预言机oracle的类型等等。当前最先进的文法学习方法通常是假设存在一组初始有效输入，给定初始输入集合α，通过不断扩张文法范围以此来获得目标文法，其中输入通常以字符级给出，例如字符串或字节级文件。但是程序的有效输入有时是不可用的，而如果要求有效输入具有良好的分布的情况下，也可能是得不到这样的输入的，在获取不到输入的情况下就无法使用上述文法学习方法。利用符号执行来生成用于文法学习的有效字符级输入可以解决上述问题，但是基于字符级输入的学习过程并不高效，甚至可能限制所学文法的有效性。
技术实现要素：4.本发明要解决的技术问题就在于：针对现有技术存在的技术问题，本发明提供一种实现方法简单、文法生成的有效性与效率高以及文法完整的token级的程序输入文法自动生成方法，能够显著提高接受复杂输入软件的自动测试能力，提高自动测试工具的有效性和效率。
5.为解决上述技术问题，本发明提出的技术方案为：
6.一种token级的程序输入文法自动生成方法，步骤包括：
7.步骤s01.获取一个符合解析程序文法的字符串作为初始输入并进行符号执行，生成对应解析程序的token序列集合并收集每个token的上下界范围；
8.步骤s02.对所述token序列集合进行正则表达式泛化，生成正则表达式；
9.步骤s03.将泛化得到的所述正则表达式中指定非终结符进行合并,转化为上下文无关文法；
10.步骤s04.使用所述token的上下界范围作为约束，对所述上下文无关文法中每个token的字符级产生式进行字符泛化，得到最终的文法输出，所述字符级产生式用于表示每个token所对应的字符级的值。
11.进一步的，所述步骤s01中，使用测试用例自动生成工具gadse(grammar-agnostic dynamic symbolic execution)自动生成能被所述解析程序接收的token序列集合以及收集每个token对应的上下界范围。
12.进一步的，所述步骤s02中进行正则表达式泛化使用重复泛化、交替泛化，所述重复泛化为重复文法中给定的子字符串，所述交替泛化为在文法中分解子字符串并形成交替。
13.进一步的，所述步骤s02中进行正则表达式泛化还使用交换泛化，所述交换泛化通过将当前表达式l分成三个部分，并交换其中的第一部分和第三部分。
14.进一步的，所述步骤s02中每次泛化后还包括测试每个可能的token正则表达式步骤，包括：生成具有代表性的token序列，然后使用所述token的上下界范围作为约束，将生成的所述token序列转换为字符级输入以测试当前token序列的有效性。
15.进一步的，所述步骤s03包括：遍历泛化得到的所述正则表达式中的所有非终结符，判断其中是否有非终结符是等价的，如果有，则将等价的非终结符合并为一个非终结符，合并完成后的正则表达式即为转化得到的上下文无关文法。
16.进一步的，所述步骤s04中，使用smt计算每个token字符的上限和下限，并将各token字符泛化为所述上限与所述下限之间的值，以实现字符泛化。
17.进一步的，所述步骤s04中字符泛化后，还包括将泛化出的字符值放入token字符所出现的序列中并检查字符值的有效性，以检查泛化后的字符值。
18.一种token级的程序输入文法自动生成装置，包括：
19.符号执行模块，用于获取一个符合解析程序文法的字符串作为初始输入并进行符号执行，生成对应解析程序的token序列集合并收集每个token的上下界范围；
20.第一泛化模块，用于对所述token序列集合进行正则表达式泛化，生成一个正则表达式；
21.第二泛化模块，用于将泛化得到的所述正则表达式中指定非终结符进行合并,转化为上下文无关文法；
22.第三泛化模块，用于使用所述token的上下界范围作为约束，对所述上下文无关文法中每个token的字符级产生式进行字符泛化，得到最终的文法输出，所述字符级产生式用于表示每个token所对应的字符级的值。
23.一种存储有计算机程序的计算机可读存储介质，所述计算机程序执行时实现如上述方法。
24.与现有技术相比，本发明的优点在于：
25.1、本发明通过使用与文法无关的程序符号执行为具有复杂输入格式的程序生成token序列，同时收集每个token的上下界范围，然后使用生成token序列综合出输入的文法，先泛化成为正则表达式，对正则表达式中的非终结符再进行合并操作，转化为上下文无
关文法，然后结合token值的上下界范围对上下文无关文法中的每个token所对应的字符级值进行字符泛化以进一步扩张文法范围，得到最终的文法输出，能够实现token级文法综合，与传统的字符级输入学习方式相比，能够有效提高文法综合的有效性和效率，基于token级的综合还可以提高文法生成的完整性。
26.2、本发明进一步通过结合测试用例自动生成技术，使用gadse可以为文法学习提供大量分布良好的初始输入，进一步提高了文法综合的自动化程度和效果，基于token级实现语法综合，在解析过程中，由一个token代表一个字符序列，可以节省gadse大量的分区时间，实现更快、更高层次的语法综合。
27.3、本发明进一步考虑非终结符的生成规则，通过在重复、交替操作的基础上，引入新的交换泛化操作，通过将表达式分成三个部分并交换其中的第一部分和第三部分实现交换泛化，可以进一步提高文法生成的精度。
28.4、本发明通过利用符号执行收集的token约束并转换为smt优化问题，使得可以利用smt优化来泛化token的可能字符级的值，可以进一步提高了文法的准确性。
附图说明
29.图1是本实施例token级的程序输入文法自动生成方法的实现流程示意图。
30.图2是本实施例token级的程序输入文法自动生成方法的具体流程示意图。
31.图3是本发明具体应用实施例中所使用的示例程序示意图。
32.图4是本发明具体应用实施例中使用得到的gadse工具得到的token约束示意图。
33.图5是本发明具体应用实施例中使用得到的gadse工具得到的token序列示意图。
34.图6是本发明具体应用实施例中得到的文法综合结果示意图。
具体实施方式
35.以下结合说明书附图和具体优选的实施例对本发明作进一步描述，但并不因此而限制本发明的保护范围。
36.如图1、2所示，本实施例token级的程序输入文法自动生成方法的步骤包括：
37.步骤s01.获取一个符合解析程序文法的字符串作为初始输入并进行符号执行，生成对应解析程序的token序列集合并收集每个token的上下界范围；
38.步骤s02.对token序列集合进行正则表达式泛化，生成正则表达式；
39.步骤s03.将泛化得到的正则表达式中指定非终结符进行合并,转化为上下文无关文法；
40.步骤s04.使用token的上下界范围作为约束，对上下文无关文法中每个token的字符级产生式进行字符泛化，得到最终的文法输出，字符级产生式用于表示每个token所对应的字符级的值。
41.在词法分析中，输入首先被标记为一个token序列，然后根据语法分析中的文法规则检查token序列，记号序列更接近文法中的产生式，因此对于文法学习，如果能够执行token级别学习文法，即以token序列为基准进行文法学习，则学习过程会更加高效、结果也会更加精确和完整。
42.本实施例通过以一个符合解析程序文法的字符串作为初始输入，对初始输入进行
符号执行，以此自动生成对应解析程序的合法token序列集合，即通过先使用与文法无关的程序符号执行为具有复杂输入格式的程序生成token序列，同时收集每个token的上下界范围，然后使用生成token序列综合出输入的文法，先对token序列使用泛化操作，泛化成为正则表达式，对泛化得到的正则表达式中的非终结符再进行合并操作，获取文法的递归属性，转化为上下文无关文法，然后结合token值的上下界范围对上下文无关文法中的每个token所对应的字符级值进行字符泛化以进一步扩张文法范围，得到最终的文法输出，能够基于符号执行实现token级的文法综合。
43.作为一种白盒学习方法，本实施例上述基于符号执行的token级文法学习方式，与传统的字符级输入学习方式相比，能够有效提高文法综合的有效性和效率，实现更有效地综合文法，基于token级的综合还可以提高文法生成的完整性，尤其可适用于对文法分布良好、输入样本不可用的解析程序进行输入文法自动学习生成。
44.本实施例步骤s01中，使用测试用例自动生成工具gadse自动生成能被解析程序接收的token序列集合以及收集每个token对应的上下界范围，由每个token对应的上下界范围作为每个token对应的约束值。通过结合测试用例自动生成技术，使用gadse可以为文法学习提供大量分布良好的初始输入，进一步提高了文法综合的自动化程度和效果。
45.以如图3中示例语法为例，其中上部分为示例语法，下部分为语法的解析程序，该程序实际上实现了一个上下文相关文法，其中，示例程序中的语法，其中(
…
)+，(
…
)*为正则表达式符号，《t》表示单个字符，《id》表示长度大于1的大写标识符号，《number》必须是一个单数字数字，并且《sep》表示特殊的分离符号。该文法中要求标签应该具有相同的名称，例如，《a》aa《a》是有效的，但《a》aa《b》是无效的。上述可以使用一个递归下降解析器实现，以及利用堆栈来检查标签是否具有相同的名称。
46.在具体应用实施例中，首先给定初始输入“《a》；《a》”，然后使用gadse对初始输入进行符号执行，以此生成对应解析程序的合法token序列集合和每个token对应的约束值。示例程序中有6种token值。gadse首先会为解析程序中的token生成约束，其中token的长度均为1，如图4所示。然后gadse生成token级的路径约束并求解得到token序列。通过生成新的token序列来搜索token级路径空间，gadse可以更有效地探索解析程序的路径空间。如图5所示，上部分表示初始输入的token级路径约束，下部分表示gadse探索解析程序路径空间所生成的两个有效的token序列。
47.本实施例进行正则表达式泛化时具体使用重复(repetition)泛化、交替(alternation)泛化，重复泛化为重复文法中给定的子字符串(例如，aa可以泛化为a(a)*)，交替泛化则为在文法中分解子字符串并形成交替(例如，(ab)*可泛化为(a|b)*)。对于步骤s01生成的token序列，将token序列作为初始输入，对每个token序列应用正则泛化操作，迭代地生成候选正则文法。然后，通过从候选文法生成新输入并查看新输入是否被解析程序接受来检查这些候选语法的正确性。对通过检查的候选文法继续应用泛化操作，直至无法泛化为止，得到最终的正则文法，然后进入步骤s03。
48.本实施例步骤s02中具体使用黑盒语法综合器glade来进行正则表达式泛化，glade从一组有效输入开始，对于每个输入i，glade逐渐将i推广到正则表达式e，泛化过程即是一系列正则表达式l0,
…
,ln，其中l0只包含i，ln为e。对于每个0≤i≤n-1，每一步泛化试图扩张li，但同时也要避免过度泛化。glade提供了两种泛化操作：重复
(repetition)以及交替(alternation)，其中重复泛化时先将li分成三个部分，即li＝α1α2α3，然后按照如下方式重复第二部分和第三部分：
49.α1([α2]
alt
)*[α3]
rep
ꢀꢀ
(1)
[0050]
其中，[]rep、[]alt中的表达式分别表示要使用重复、交替以分别泛化表达式。
[0051]
由于可能存在多种划分情况，进一步通过针对新表达式生成几个字符串并检查这些字符串是否可以被程序接受以检查新的正则表达式。如果所有字符串都有效，则将新表达式作为候选泛化表达式。例如，对于示例程序，假设i是《a》aa；0《a》并且使用重复来泛化i，则可以得到以下四个候选规则且通过检查：
[0052]
《a》([aa；]
alt
)
*
[0《a》]
rep
ꢀꢀꢀ
(2)
[0053]
《a》([a]
alt
)
*
[a；0《a》]
rep
[0054]
《a》a([a]
alt
)
*
[；0《a》]
rep
[0055]
《a》aa([；0]
alt
)*[《a》]
rep
[0056]
glade进一步选择长度最大的重复，即第一个表达式(aa；的长度为3)作为泛化表达式。
[0057]
交替操作即是将li分成两部分，即li＝a1α2，并递归地分别对第一部分和第二部分应用重复和交替，即规则为：
[0058]
[α1]
rep
+[α2]
alt
ꢀꢀꢀ
(3)
[0059]
与重复操作相同的，本实施例在交替操作时也检查不同的候选项，并选择其中一个候选项作为候选泛化表达式li+1。例如，对于式(2)中的表达式，若不能将aa分开，则只需重复表达式即得到表达式：
[0060]
《a》([aa；]
rep
)*[0《a》]
rep
ꢀꢀꢀ
(4)
[0061]
对于每个泛化步骤，使用glade能够确保li是li+1的子集，并通过检查可能的泛化表达式还可以使得尽量不过度泛化。默认情况下，初始输入i首先通过重复生成，aa；o的泛化过程如下：
[0062][0063]
上述过程总共有9个步骤，基于该泛化过程，glade为最终的正则表达式生成以下文法：
[0064]
s：＝《a》(s1)
*
0《a》 s1：＝(a)
+
；
ꢀꢀꢀ
(5)
[0065]
且glade还可以通过尝试所有可能的字符泛化单个字符，例如将上述上下文无关文法可以生成到下述文法：
[0066]
s：＝《a》(s1)
*
(0|...|9)《a》 s1：＝(a|...|z)
+
(：|；)
ꢀꢀꢀ
(6)
[0067]
上述最终的上下文无关文法接近于图2中的文法。对于多个初始有效输入，glade可以为每个输入泛化一个语法，并将生成的语法统一为一个作为结果。但是glade需要假设
初始输入是有效的，有效输入的分布也决定了综合文法的完整性，而如果没有输入文法，很难获得分布良好的有效输入，例如覆盖所有产生式规则和文法终结符的输入。本实施例通过使用动态符号执行(dse)作为程序生成的输入，可以得到分布良好的有效输入。由于glade是基于字符级别进行综合，在每个泛化步骤中，在字符级别存在许多可能的分区，因而glade需要很多时间来检查每个分区的有效性，这也限制了glade的泛化能力，本实施例则通过基于token级实现语法综合，在解析过程中，一个token代表一个字符序列，而glade不需要对token的字符串进行分区，因而可以节省大量的分区时间，实现更快、更高层次的语法综合。
[0068]
考虑到非终结符《content》的生产规则为：
[0069]
《cpmtent》：＝《value》(《sep》《content》)*
ꢀꢀꢀ
(7)
[0070]
其中，《value》有两种情况，即为一个标识或一个数字。
[0071]
如果当前表达式为aa；0，glade当前的泛化操作限制了泛化能力，，因为只有子表达式(如aa；或者；0)可以重复，然而如果想泛化成以下表达式：
[0072]
《value》(《sep》《content》)*
ꢀꢀꢀ
(8)
[0073]
需要同时具有；0和；aa(或aa；和0；)，而这通过交换第一部分和第三部分即可以得到。因此，通过交换第一和第三部分可以扩大泛化范围，泛化aa；0到《content》的正则表达式。
[0074]
本实施例利用上述特征，在步骤s02中进行正则表达式泛化时还使用交换([]exh)泛化，即引入交换泛化操作进行泛化，交换泛化通过将当前表达式l分成三个部分，并交换其中的第一部分和第三部分，可表示为：
[0075]
((([α1]
rep
+[α3]
rep
)[α2]
rep
)*([α1]
rep
+[α3]
rep
))
ꢀꢀꢀ
(9)
[0076]
例如，使用交换操作可以将token序列推广到以下三个候选正则token表达式：
[0077]
ltr([is]
alt
)*[nltr]
rep
ꢀꢀꢀ
(10)
[0078]
ltri([sn]
alt
)*[ltr]
rep
[0079]
ltr([isn]
exh
)[ltr]
rep
[0080]
为了简单起见，在上述表达式中，我们使用每个token值的第二部分的第一个字母来表示token，例如，s代表t_sep。
[0081]
本实施例在上述每个泛化步骤中还包括检查每个可能的token正则表达式，具体包括：首先生成具有代表性的token序列；然后，通过token值约束(上下界范围)和字符级常量(在gadse中收集)将token序列转换为字符级输入，以检查其有效性。例如，将ltrnsiltr(用于测试最后一个表达式)和ltrisisnltr分别转换为《a》0；aa《a》和《a》aa；aa；0《a》，它们都被解析程序接受，即均是有效的。
[0082]
本实施例在上述检查token有效性后，优先选择交换泛化继续泛化，ltrisnltr的泛化过程具体可表示为：
[0083][0084]
其中，每个字母表示一个token，对应每个token值的第二部分的第一个字母。
[0085]
按照上述步骤即可得到如下的上下文无关文法：
[0086]
s：＝(ltr s
1 ltr)s1：＝(s
2 s)*s
2 s2：＝s3|s
4 s3：＝i s4：＝n
[0087]
本实施例步骤s03进一步对步骤s02的正则表达式中非终结符合并，以转化为上下文无关相关文法，步骤包括：遍历泛化得到的正则表达式中的所有非终结符，判断其中是否有非终结符是等价的，如果有，则将等价的非终结符合并为一个非终结符，合并完成后的正则表达式即为转化得到的上下文无关文法。
[0088]
如上述上下文无关文法中，s1、s2、s3和s4是可合并的，可以使用s1来替换。此外，对于第一个产生式规则，s和s1也是可合并的，但s和s2不可合并，，因此，本实施例只在第一条规则中合并s和s1，合并后可以得到以下语法：
[0089]
s：＝(ltr s ltr)|s
1 s1：＝s1ss1|i|n。
[0090]
本实施例步骤s04通过对步骤s3的文法结果中的每个token非终结符结合token值的上下限进行字符泛化，以进一步扩张文法范围，得到最终的文法。对于每个token字符t使用语法综合来泛化其可能的字符值，字符泛化后，还包括将泛化出的字符值放入token字符所出现的序列中并检查字符值的有效性，以检查泛化后的字符值。
[0091]
本实施例步骤s04中，具体使用smt计算每个token字符的上限和下限，并将各token字符泛化为上限与下限之间的值，以实现字符泛化。通过利用符号执行收集的token约束并转换为smt优化问题，使得可以利用smt优化来泛化token的可能字符级的值，可以进一步提高了文法的准确性。
[0092]
例如，token i具有字符值“aa”，可以将该值泛化到正则表达式(a)+，此外，通过在gadse第一阶段收集的token约束来泛化每个token的字符级值，使用smt优化理论计算每个字符的上限和下限，并将token泛化为上下限之间的值。例如，对于token值l，其约束为s[0]＝
‘
《’；因此，它的值只能是
‘
《’。对于token值n的约束为s[0]≥
’0’
∧s[0]≤
’9’
，因此n的值是在
‘0’
和
’9’
之间。最后，基于上述步骤，可以综合出如下式(12)的上下文无关文法，该文法与图4中的文法是等价的。
[0093]
[0094]
在具体应用实施例中，以图3中最后一个token序列为例进行综合为例，对token序列进行综合的详细步骤包括：
[0095]
步骤1、对于最后一个token序列，即ltriltr，基于token的综合对token序列进行重复、替换以及交换操作；
[0096]
步骤2、在每个泛化步骤中测试每个可能的token正则表达式：首先生成具有代表性的token序列；然后，通过token值约束和常量将token序列转换为字符级输入以测试有效性。
[0097]
步骤3、对正则泛化后得到的正则表达式中的非终结符进行合并操作，获取文法的递归属性，转化为上下文无关文法。
[0098]
步骤4、对于每个token值，通过gadse在步骤s01中收集的token约束(上下界范围)来泛化其字符级值，其中使用smt优化理论计算token中每个字符的上界和下界，并将token一般化为下界和上界之间的值，基于token序列和token值约束，即可合成最终的上下文无关文法输出。
[0099]
在具体应用实施例中，应用于某java解析程序，在基于jpf的与文法无关的concolic执行引擎和glade上实现了上述文法生成，得到的文法结果如图6所示。从图6可以看出最终通过本发明综合生成出来的文法与目标文法是一致的，且相比于传统基于字符级别的文法约束，本发明能够极大地提高了文法综合的效率以及文法的完整性。具体的，与配备字符级符号执行的state-of-the-arts(即glade和arvada)相比，本发明方法的f1分数分别提高了5.24倍和3.54倍，与arvada相比，本发明在文法综合方面可以实现141.93倍的时间加速，即本发明可以有效地提高文法生成的精度和召回率。
[0100]
本实施例token级的程序输入文法自动生成装置包括：
[0101]
符号执行模块，用于获取一个符合解析程序文法的字符串作为初始输入并进行符号执行，生成对应解析程序的token序列集合并收集每个token的上下界范围；
[0102]
第一泛化模块，用于对token序列集合进行正则表达式泛化，生成一个正则表达式；
[0103]
第二泛化模块，用于将泛化得到的正则表达式中指定非终结符进行合并,转化为上下文无关文法；
[0104]
第三泛化模块，用于使用token的上下界范围作为约束，对上下文无关文法中每个token的字符级产生式进行字符泛化，得到最终的文法输出，字符级产生式用于表示每个token所对应的字符级的值。
[0105]
本实施例token级的程序输入文法自动生成装置与上述token级的程序输入文法自动生成方法为一一对应，在此不再一一赘述。
[0106]
本实施例还提供存储有计算机程序的计算机可读存储介质，计算机程序执行时实现上述方法。
[0107]
上述只是本发明的较佳实施例，并非对本发明作任何形式上的限制。虽然本发明已以较佳实施例揭露如上，然而并非用以限定本发明。因此，凡是未脱离本发明技术方案的内容，依据本发明技术实质对以上实施例所做的任何简单修改、等同变化及修饰，均应落在本发明技术方案保护的范围内。
技术特征：1.一种token级的程序输入文法自动生成方法，其特征在于，步骤包括：步骤s01.获取一个符合解析程序文法的字符串作为初始输入并进行符号执行，生成对应解析程序的token序列集合并收集每个token的上下界范围；步骤s02.对所述token序列集合进行正则表达式泛化，生成正则表达式；步骤s03.将泛化得到的所述正则表达式中指定非终结符进行合并,转化为上下文无关文法；步骤s04.使用所述token的上下界范围作为约束，对所述上下文无关文法中每个token的字符级产生式进行字符泛化，得到最终的文法输出，所述字符级产生式用于表示每个token所对应的字符级的值。2.根据权利要求1所述的token级的程序输入文法自动生成方法，其特征在于，所述步骤s01中，使用测试用例自动生成工具gadse自动生成能被所述解析程序接收的token序列集合以及收集每个token对应的上下界范围。3.根据权利要求1所述的token级的程序输入文法自动生成方法，其特征在于，所述步骤s02中进行正则表达式泛化使用重复泛化、交替泛化，所述重复泛化为重复文法中给定的子字符串，所述交替泛化为在文法中分解子字符串并形成交替。4.根据权利要求3所述的token级的程序输入文法自动生成方法，其特征在于，所述步骤s02中进行正则表达式泛化还使用交换泛化，所述交换泛化通过将当前表达式l分成三个部分，并交换其中的第一部分和第三部分。5.根据权利要求1所述的token级的程序输入文法自动生成方法，其特征在于，所述步骤s02中每次泛化后还包括测试每个可能的token正则表达式步骤，包括：生成具有代表性的token序列，然后使用所述token的上下界范围作为约束，将生成的所述token序列转换为字符级输入以测试当前token序列的有效性。6.根据权利要求1～5中任意一项所述的token级的程序输入文法自动生成方法，其特征在于，所述步骤s03包括：遍历泛化得到的所述正则表达式中的所有非终结符，判断其中是否有非终结符是等价的，如果有，则将等价的非终结符合并为一个非终结符，合并完成后的正则表达式即为转化得到的上下文无关文法。7.根据权利要求1～5中任意一项所述的token级的程序输入文法自动生成方法，其特征在于，所述步骤s04中，使用smt计算每个token字符的上限和下限，并将各token字符泛化为所述上限与所述下限之间的值，以实现字符泛化。8.根据权利要求7所述的token级的程序输入文法自动生成方法，其特征在于，所述步骤s04中字符泛化后，还包括将泛化出的字符值放入token字符所出现的序列中并检查字符值的有效性，以检查泛化后的字符值。9.一种token级的程序输入文法自动生成装置，其特征在于，包括：符号执行模块，用于获取一个符合解析程序文法的字符串作为初始输入并进行符号执行，生成对应解析程序的token序列集合并收集每个token的上下界范围；第一泛化模块，用于对所述token序列集合进行正则表达式泛化，生成一个正则表达式；第二泛化模块，用于将泛化得到的所述正则表达式中指定非终结符进行合并,转化为上下文无关文法；
第三泛化模块，用于使用所述token的上下界范围作为约束，对所述上下文无关文法中每个token的字符级产生式进行字符泛化，得到最终的文法输出，所述字符级产生式用于表示每个token所对应的字符级的值。10.一种存储有计算机程序的计算机可读存储介质，其特征在于，所述计算机程序执行时实现如权利要求1～8中任意一项所述的方法。
技术总结本发明公开一种token级的程序输入文法自动生成方法，步骤包括：S01.获取一个符合解析程序文法的字符串作为初始输入并进行符号执行，生成对应解析程序的token序列集合并收集每个token的上下界范围；S02.对token序列集合进行正则表达式泛化，生成正则表达式；S03.将泛化得到的正则表达式中指定非终结符进行合并,转化为上下文无关文法；S04.使用所述token的上下界范围作为约束，对所述上下文无关文法中每个token的字符级产生式进行字符泛化，得到最终的文法输出。本发明具有实现方法简单、生成有效性与效率高且文法完整等优点。生成有效性与效率高且文法完整等优点。生成有效性与效率高且文法完整等优点。
技术研发人员：陈振邦 王戟 罗运来 潘威宇 毛晓光 董威 李姗姗 文艳军 陈立前 刘万伟 尹良泽
受保护的技术使用者：中国人民解放军国防科技大学
技术研发日：2022.03.16
技术公布日：2022/7/5
