在C++中，我目前正在以某种方式进行Thompson's Construction，而不使用regex头，我焦急地纠结于如何进行以及为什么，
假设我有下面的字符串表达式，其中有"."是Concatenation，'|'是Union，'*'是KleeneStar，我们可以假设语法已经预先检查过了，它们可以读作：
a或
(a)|(b)或
(a).(b)或
((a)|(b)).(c)或
((c)|(d)).((a)|(b))或
(a)*或
((a)*)|((b)*)或
这里的目标是提取、调用或读取字符串表达式，该表达式将把一组字符串作为其相应表达式的预期输出(注意，空字符串可以输出为"_"(，其中：
a输出{a}
(a)|(b)输出{a, b}
(a).(b)输出{ab}
((a)|(b)).(c)输出{ac, bc}
((c)|(d)).((a)|(b))输出{ca, da, cb, db}
(a)*输出{_, a, aa, aaa, aaaa, ...}(我们可以考虑在此处设置限制(
((a)*)|((b)*)输出{_, a, b, aa, ab, ba, bb, aaa, aab, aba, abb, baa, bab, bba, bbb, ...}(我们可以考虑在此处设置限制(
我相信有一种更好的方法可以提前使用算法、伪代码、解析等来做到这一点，或者我缺乏实践，在执行这样的事情时，我的编码知识存在严重差距。
到目前为止，我很想知道很多因素，比如要生成什么函数，要生成什么递归调用，指针、堆栈、向量、何时何地等等，而且这样的过程可能真的会给程序带来压力，让它计算出我所实现的一切的所有可能性，比如说，匹配用户的输入字符串以匹配列出的字符串集。
也许我在论坛上看过的一篇帖子读得不够透彻。我完全被自己的观点淹没了，我想一步一步地演练一下该做什么，非常感谢进一步的指导和帮助。对任何解决方案，甚至发布您自己的代码进行完整的演练，将对我的学习有很大帮助。任何建议都会很有帮助。再次，任何我忘记提及的关键术语或任何具体内容，请发表您的评论，谢谢您抽出时间。
编辑：有人告诉我，我的建议可能与KleeneStar运算符有关，生成输出可能会变得不平凡？我想知道是否可以设置int限制，或者这仍然会严重导致更多的并发症。
我们可以使用Thompson构造将正则表达式转换为具有ε-转换的不确定有限自动机，然后在图中运行Dijkstra算法，其中节点是(q，x(对，其中q是状态，x是字符串，弧从(q，x(到(δ(q，σ(，xσ(，其中σ是符号(权重1，双端队列的后面(或ε(权重0，双端排队的前面(。通过按此顺序枚举，我们可以很容易地添加大小限制。
我们用递归下降来解析正则表达式。我不打算进一步解释；有一百万个计算器教程。
不要在生产中使用低于C++级别的软件。
#include <deque>
#include <iostream>
#include <tuple>
#include <unordered_set>
#include <vector>
struct State;
struct Transition {
char symbol;
State *successor;
};
struct State {
std::vector<State *> epsilon_transitions;
std::vector<Transition> transitions;
std::unordered_set<std::string> visited_strings;
};
struct Automaton {
State *initial_state;
State *final_state;
};
Automaton Eps() {
Automaton c;
c.initial_state = c.final_state = new State;
return c;
}
Automaton Sym(char symbol) {
Automaton c;
c.initial_state = new State;
c.final_state = new State;
c.initial_state->transitions.push_back({symbol, c.final_state});
return c;
}
Automaton Star(Automaton a) {
Automaton c;
c.initial_state = c.final_state = new State;
c.final_state->epsilon_transitions.push_back(a.initial_state);
a.final_state->epsilon_transitions.push_back(c.final_state);
return c;
}
Automaton Cat(Automaton a, Automaton b) {
Automaton c;
c.initial_state = a.initial_state;
c.final_state = b.final_state;
a.final_state->epsilon_transitions.push_back(b.initial_state);
return c;
}
Automaton Alt(Automaton a, Automaton b) {
Automaton c;
c.initial_state = new State;
c.final_state = new State;
c.initial_state->epsilon_transitions.push_back(a.initial_state);
c.initial_state->epsilon_transitions.push_back(b.initial_state);
a.final_state->epsilon_transitions.push_back(c.final_state);
b.final_state->epsilon_transitions.push_back(c.final_state);
return c;
}
void Enumerate(Automaton a, std::size_t size_limit = 4) {
std::deque<std::tuple<State *, std::string>> queue = {
{a.initial_state, std::string()}};
do {
auto [state, string] = queue.front();
if (string.size() > size_limit) {
std::cout << "...n";
break;
}
queue.pop_front();
if (!state->visited_strings.insert(string).second) {
continue;
}
if (state == a.final_state) {
std::cout << """ << string << ""n";
}
for (State *successor : state->epsilon_transitions) {
queue.push_front({successor, string});
}
for (auto [symbol, successor] : state->transitions) {
queue.push_back({successor, string + std::string(1, symbol)});
}
} while (!queue.empty());
std::cout << "n";
}
#include <cctype>
#include <cstdio>
#include <istream>
#include <optional>
#include <sstream>
char Peek(std::istream &input) {
input >> std::ws;
return input.peek();
}
bool Match(std::istream &input, char c) {
if (Peek(input) == c) {
input.get();
return true;
}
return false;
}
std::optional<char> ParseSymbol(std::istream &input) {
if (std::isalpha(Peek(input))) {
return input.get();
}
return std::nullopt;
}
std::optional<Automaton> Parse(std::istream &input);
std::optional<Automaton> ParsePrimitive(std::istream &input) {
if (auto maybe_symbol = ParseSymbol(input)) {
return Sym(maybe_symbol.value());
}
if (Match(input, '(')) {
if (auto maybe_a = Parse(input)) {
if (Match(input, ')')) {
return maybe_a.value();
}
}
}
return std::nullopt;
}
std::optional<Automaton> ParseFactor(std::istream &input) {
if (auto maybe_a = ParsePrimitive(input)) {
if (Match(input, '*')) {
return Star(*maybe_a);
}
return *maybe_a;
}
return std::nullopt;
}
std::optional<Automaton> ParseTerm(std::istream &input) {
if (auto maybe_a = ParseFactor(input)) {
Automaton a = maybe_a.value();
while (Match(input, '.')) {
if (auto maybe_b = ParseFactor(input)) {
a = Cat(a, maybe_b.value());
} else {
return std::nullopt;
}
}
return a;
}
return std::nullopt;
}
std::optional<Automaton> Parse(std::istream &input) {
if (auto maybe_a = ParseTerm(input)) {
Automaton a = maybe_a.value();
while (Match(input, '|')) {
if (auto maybe_b = ParseTerm(input)) {
a = Alt(a, maybe_b.value());
} else {
return std::nullopt;
}
}
return a;
}
return std::nullopt;
}
std::optional<Automaton> Parse(const std::string &input) {
std::stringstream stream(input);
if (auto maybe_a = Parse(stream)) {
if (Peek(stream) == EOF) {
return maybe_a.value();
}
}
return std::nullopt;
}
int main() {
Enumerate(Parse("a").value());
Enumerate(Parse("a|b").value());
Enumerate(Parse("a.b").value());
Enumerate(Parse("(a|b).c").value());
Enumerate(Parse("(c|d).(a|b)").value());
Enumerate(Parse("a*").value());
Enumerate(Parse("(a|b)*").value());
}
输出：
"a"
"b"
"a"
"ab"
"bc"
"ac"
"db"
"da"
"cb"
"ca"
""
"a"
"aa"
"aaa"
"aaaa"
...
""
"b"
"a"
"bb"
"ba"
"ab"
"aa"
"bbb"
"bba"
"bab"
"baa"
"abb"
"aba"
"aab"
"aaa"
"bbbb"
"bbba"
"bbab"
"bbaa"
"babb"
"baba"
"baab"
"baaa"
"abbb"
"abba"
"abab"
"abaa"
"aabb"
"aaba"
"aaab"
"aaaa"
...