以交互方式生成正则表达式的算法及演示

林果丰，郑大鹏

（北京理工大学珠海学院计算机学院，珠海519000）

0 引言

正则表达式，又称规则表达式。它由一些特定字符及这些特定字符的组合，组成一个“规则字符串”，这个“规则字符串”用来表达对其他字符串的一种过滤逻辑。正则表达式是对字符串（包括普通字符例如，a到z之间的字母，以及特殊字符即“元字符”）操作的一种逻辑公式，是一种文本模式，该模式描述在搜索文本时要匹配的一个或多个字符串[1]。正则表达式通常被用来检索、替换那些符合某个模式（规则）的文本。

很多专业领域都能使用正则表达式，如网络犯罪案件取证[1]和页面数据获取[2]等。但是在非计算机专业领域却鲜有运用。随着许多传统项目开始电子化，如无纸化考试系统[3]，越来越多问题开始使用计算机处理，正则表达式将被运用到越来越多的各种不同的系统上，但由于其过于专业、晦涩难懂，对于非专业人士很难使用，甚至不知道正则表达式的存在。因此，需要有一个算法，可以在用户不掌握正则表达式的情况下引导用户生成正则表达式，甚至不需要学习正则表达式。

本文提出的算法可通过引导用户从而生成正则表达式，从而使用模式匹配、连字符、元字符、分支条件、重复匹配这些功能[4]。

1 概述

要引导用户使用正则表达式进行匹配会遇到的引导场景有2种情况：用户要匹配的字符串的个数是有限个的和用户要匹配的字符串有无限个。对于第一种情况，使用有限项生成算法，即简单引导用户输入所有待匹配项即可。对于第二种情况，使用无限可描述项生成算法，它需要引导用户输入字符集范围和重复限定的范围才能生成结果。所以要生成正则表达式，需要两种算法。由于这两种算法最终都是生成正则表达式，所以那些无法用正则表达式记录下的匹配要求是无法通过此算法生成正则表达式的。这两种算法都是引导用户思考正则表达式要思考的问题，而不用去关心如何写出正则表达式。真正的正则表达式由算法生成，所以用户可以在不掌握正则表达式的情况下，按照构造正则表达式的思路去思考问题即可。算法不仅要关心正则表达式生成方面的问题，还要重视对用户的引导作用。

2 有限项生成算法

2.1 有限项生成算法流程

对于待匹配项是有限个的情况，可以将每个待匹配项视为一个子表达式[4]，引导用户将所有待匹配项输入，算法再他们组合在一起，形成正则表达式分支条件的语法。如图1所示。

图1 有限项生成算法流程流程图

系统首先生成一个固定的串“^（”，除了第一次不作处理外，每次用户输入后，给用户输入加上前缀“|”，并将这个新串其加入到最终的结果字符串中。当用户结束，加入后缀“）$”生成最终的字符串。为了提高辨识力度，首尾固定添加的串中带有元字符“^”和“$”，从而限制字符串的开头和结束，可有效避免未知因素的干扰，当然，“^”和“$”不是必须的。如果用户希望在某个系统使用生成的正则表达式时，匹配过程中可以忽略空白字符、字母大小写等因素的干扰，可以让该系统在使用正则表达式之前过滤或替换掉目标字符，让系统决定，所以算法在生成正则表达式时不需要考虑空白字符和大小写干扰的情况。

2.2 有限项生成算法效果演示

在网络教育领域中的无纸化考试系统中，教师会设置填空题。在传统的填空题设置、判阅中，都要求教师输入正确答案，在系统判阅时，通常采取静态字符串比较算法。在这种情况下，可以使用有限项生成算法，在教师输入答案时引导生成正则表达式，在判阅时使用正则表达式判题。假设教师题目为“请输入一个数据库事务的特性”，教师希望答题者输入“原子性、一致性、隔离性、持久性”中的一个才可得分。此时引导界面见图2。

图2 有限项生成算法效果演示过程

用户输入完题目后，选择“设定答案”，然后将答案一个一个输入。每输一个答案，就点击右边的“+”号，最后点击“确定”按钮生成预览。最终生成的正则表达式为“（持久性）|（隔离性）|（一致性）|（原子性）”，效果如图3。

图3 有限项生成算法效果演示结果

3 无限可描述项生成算法

3.1 无限可描述项生成算法流程

在无限可描述项生成算法中，创建正则表达式的过程可以简化为构造多个字符重复集合的过程。所谓字符重复集合，由一个字符集合和一个设定重复次数的语句构成。一个最终要生成的正则表达式，可以由一个或多个字符重复集合构成。所以要生成目标串，就要引导用户输入字符集合和设定重复次数。

每一个字符集合都在描述各自对某一类字符的匹配规则，如“[0-9]”就是一个字符集合，它匹配所有阿拉伯数字。所以，需要引导用户考虑他们的匹配规则，让用户输入类似“[0-9]”这样的待匹配的字符或者待匹配的字符范围，在没有字符集合的概念下创建一个字符集合。因为用户不需要掌握连字符，所以用户只需要输入字符集的左右边界即可，引导界面如图4。

图4 字符集创建算法引导图

第一行用户可以输入要被匹配的特殊符号，即除了数字、大小写字母外的任何字符，包括全半角字符、中文等，如果其中字符如果是“”、“-”或“^”等字符，还要进行转义。接下来3行处理要使用连字符的情况，范围都是从左边下拉框的字符到右边下拉框的字符。若在某行的“是否使用”后打钩，则会将该行左边下拉选择框和右边下拉选择框内的两个字符用连字符连接起来，形成“字符-字符”的形式，并加入生成的结果中。为了生成最终的字符集，需使用上述的有限项生成算法。用户思考的结果会填入这四行的某几行中，每填入一行，都是一个有限项生成算法中的“待匹配项”。所以我们可以认为这是个通过有限项生成算法用1到4个待匹配项生成的一个字符集合。最终算法使用“[”和“]”包围它们。该部分实现函数GenerateCharacterSet（）的伪代码如下：

上面的算法中，str长度至少为5，即使用户没有输入也会有“^（[]）”，这可以判断用户是否有输入字符集的内容。在用户完成对字符集的设定后，再立即引导用户输入“重复匹配”的次数，设定次数的引导界面如图5。

图5 重复匹配次数算法输入引导图

用户输入了次数后，只需要给输入加上“{”前缀和“}”后缀，然后将结果放到上一步生成的字符集后，便成功构造了一个字符重复集合。

这已经能正确生成字符重复集合了，但是这仍不足，我们应该要让多个字符重复集合成为一个子表达式，从而使用正则表达式强大的功能。所以还应该在生成字符重复集合的算法上再进一步操作，允许更多字符集合进入某个子表达式中。可以这样设定，如果用户仅仅指定字符集而没有输入重复字数，则不加入重复次数，简单将字符集生成，下次生成字符集就跟在这个字符集后面，而不是原本的让一个字符集为一个子表达式，它们变成同一个子表达式。如果用户在没有指定字符集时，仅仅输入重复次数，则将上一个子表达式用括号括起来，并加上用户输入和“{”与“}”，让上一个子表达式重复匹配指定次数。这样就能让用户真正使用正则表达式的功能了。函数RegGeneration（）便完成了这个功能，伪代码如下：

用户通过该算法引导一次或多次便能得到最终想要的正则表达式。完整引导界面如图6。

图6 无限可描述项生成算法输入引导图

用户将需求输入，点击“+”号生成一个字符重复集合。然后可以再进行输入，再点击“+”号。多次点击“+”号从而多次调用无限可描述项生成算法，直到用户达到了需求目标。点击“确定”即可生成最终的正则表达式。

3.2 无限可描述项生成算法效果演示

如果用户希望生成一个正则表达式去匹配邮箱，可以使用无限可描述项生成算法。邮箱有邮箱名称、“@”和域名这三部分组成，所以，用户应该调用至少三次无限可描述项生成算法。邮箱名称允许出现英文字母、数字、下划线、英文句号，以及中划线，不以英文句号开头，并且至少出现一次，所以生成邮箱名称部分需要调用两次算法。在第一次调用算法时，可如图7填写。

图7 无限可描述项生成算法输入演示输入图

填写完成后点击“+”号，生成的结果为“[0-9a-zAZ]{1}”，第二次调用时同样勾选三个选择框，并在特殊符号栏加上“._-”且将次数改为“0,”，便能生成“[._-0-9a-zA-Z]{0,}”。“@”部分只需要限制“@”字符出现一次即可，所以在特殊符号栏输入“@”，不勾选任何“是否使用”框并将次数设为“1”，其他都留空便可生成“[@]{1}”。

域名部分可以分为两部分：它们都由字母、数字、下划线和中划线组成的字符重复集合，它们都至少出现一次，但是第二个字符集合额外地以“.”开头。填写效果见图8。

图8 域名部分字符重复集合输入图

点击“+”后生成“[/-_0-9a-zA-Z]{1,}”。接着，不设定出现次数，仅输入特殊符号“.”，生成“[.]”。之后，再重复上图所示步骤，再次生成“[/-_0-9a-zA-Z]{1,}”，因为上次生成的字符集没有重复匹配次数，所以本次生成会拼接上上次生成的结果，成为一个新的子表达式，即变成“[.][/-_0-9a-zA-Z]{1,}”。最后，仅输入出现次数为“1，”，便可让上一个子表达式出现至少一次。最终生成的结果为（[0-9a-zA-Z]{1}）（[._/-0-9a-zA-Z]{0,}）（[@]{1}）（[/-_0-9a-zA-Z]{1,}）（（[.][/-_0-9a-zA-Z]{1,}）{1,}）。

4 结语

本文给出的算法可以引导用户将正则表达式生成出来，并利用HTML和CSS实现了引导界面、利用Ja-vaScript编程实现算法。该算法在越来越多传统行业都向电子化系统靠拢的网络背景下，可以被许多领域使用。在教育领域的电子考试系统中，教师出填空题和判题系统自动判阅填空题都可以用到正则表达式，教师可出更多类型的填空题，出题更方便，判题系统正确率高也可以变得更灵活，也没有传统的死板。有限项生成算法和无限可描述项生成算法都可以被使用。即使在计算机领域，程序员在遇到需要编写正则表达式的情况下也可以使用本系统减少出错概率，大大减少人力成本。该算法可用于任何需要写出正则表达式的场景，具有一定的实际意义。用JavaScript语言实现的演示程序则有助于读者更好地理解该算法的基本思想和实现过程。