从 L 语言的给定正则表达式创建字符串集

Question

我正在尝试根据正则表达式(也由用户提供)在字母表(由用户提供)中创建单词序列，但无法成功。

示例场景 1:

Alphabet = [a,b,c]

Regex = (a+c)b*

Word Count = 6

Words = ["a", "c", "ab", "cb", "abb", "cbb"]

示例场景 2:

Alphabet = [a,b]

Regex = (a+b)*a

Word Count = 3

Words = ["a", "aa", "ba"]

我尝试将正则表达式转换为后缀/中缀然后从那里开始，但无法构建引擎算法。

基本上有3个操作；

联盟 (+)
拼接()
闭包 (*)

我为每种运算符类型编写了一个函数；

void union(char* x[], char y)
{
    printf("%s\n%c\n", x, y);

    remainingWordCount -= 2;
}

void concat(char* x[], char* y[])
{
    printf("%s%s\n", x, y);
    remainingWordCount--;
}

void closure(char* x[], char* y[])
{
    while (remainingWordCount > 0)
    {
        concat(x, y);
    }
}

它只适用于大多数基本场景。

所以我的问题是如何在不使用任何正则表达式库的情况下根据给定的正则表达式创建一组字符串？是否有任何已知的算法？

Answer 1

“强力”解决方案是将正则表达式解析为有限状态机的状态转换图，每个状态都有一个转换列表，每个转换都有关联的符号(字符)和下一个状态。您可以使用没有转换的状态来指示终止状态。

然后遍历这个图，记住转换产生的字符串。当您达到终止状态时，打印单词并减少剩余的单词计数，当它达到零时停止。如果通过图形的不同路径最终可能产生相同的单词，您还需要记住任何已经输出的单词，如果相同的单词已经存在，则不要打印/递减。

按排序顺序处理路径(这样较短的路径出现在具有相同前缀的较长路径之前，即，按照 C 中的 strcmp)。这避免陷入循环，并给出您想要的顺序。

例如，对于正则表达式a*(伪代码):

state[0] = { {'a', 0}, {'\0', 1} };
state[1] = { }; // terminal state
paths = { { .state = 0, .string = "" } }; // set initial state

您从处于状态 0 的唯一路径开始，并(分别)向其附加从状态 0 的两个转换以创建新路径:

paths = { { .state = 1, .string = "" },
          { .state = 0, .string = "a" } };

由于带有空字符串的路径排在第一位(由于空字符串排在任何非空字符串之前)，因此首先处理它，并且由于它处于没有转换的终止状态，因此它打印空字符串并减少字数。然后你采取另一条路径并再次添加从状态 0 开始的转换，最后是:

paths = { { .state = 1, .string = "a" },
          { .state = 0, .string = "aa" } };

等等

(免责声明:这完全未经测试，超出了我的头脑，可能存在我没有想到的极端情况。还要注意，对于非平凡的正则表达式，路径数量会激增。)