Extract all possible sets of strings represented by the string expression (Part of Thompsons Construction)

user_18324843 0
Viewed 125

(This is my first post here so do bear in mind if what I'm asking is seriously too much and that I should consider tackling this piece carefully one at a time, if my question is too specific, too broad, not focused down to a single problem, requiring significantly more info, or otherwise, please don't hesitate to comment down)

In C++, I'm currently in the process of doing Thompson's Construction in a certain way without using the regex header and I'm anxiously stuck on how to proceed and why,

Say I have the following String expression in which '.' is Concatenation, '|' is Union, and '*' is KleeneStar, we can assume the syntax is already checked beforehand, and that they can be read as:

a or

(a)|(b) or

(a).(b) or

((a)|(b)).(c) or

((c)|(d)).((a)|(b)) or

(a)* or

((a)*)|((b)*) or

The goal here is to extract, call, or read the string expression that would lay out a set of strings as its expected output resulting from their corresponding expression (note an empty string could be output as '_') in which:

a outputs {a}

(a)|(b) outputs {a, b}

(a).(b) outputs {ab}

((a)|(b)).(c) outputs {ac, bc}

((c)|(d)).((a)|(b)) outputs {ca, da, cb, db}

(a)* outputs {_, a, aa, aaa, aaaa, ...} (we can consider putting a limit here)

((a)*)|((b)*) outputs {_, a, b, aa, ab, ba, bb, aaa, aab, aba, abb, baa, bab, bba, bbb, ...} (we can consider putting a limit here)

I'm sure there's a better way to do this beforehand using algorithms, pseudo-code, parsing, and more, or that my lack of practice leaves me serious gaps in my coding knowledge to perform such a thing.

As of now, I'm seriously wondering a number of factors such as what functions to make, what recursion calls to make, pointers, stacks, vectors, where and when, etc., and that such a process can perhaps really stress the program to calculate ALL possibilities for whatever I'm achieving, say, matching an input string from a user to match the set of strings listed.

and that perhaps one of the posts I've looked over in forums wasn't fully read over enough to understand. I'm completely overwhelmed in my perspective and would like a walkthrough on what to do one step at a time, further guidance and assistance are seriously greatly appreciated. A complete walkthrough for any solutions or even your own codes posted would be of great help for me to learn. Any suggestions would really help. Again any critical terms that I've forgotten to mention or anything specific please post your comments, Thank you for your time.

EDIT: I've been told that what I'm suggesting can be quite concerning with the KleeneStar operator and that generating the output would may become nontrivial? I was wondering if setting an int limit would be possible or that could still seriously cause even more complications.

g++ c++11 set algorithm string
1 Answers

We can use Thompson's construction to convert the regular expression into a nondeterministic finite automaton with ε-transitions, then run Dijkstra's algorithm in a graph where the nodes are (q, x) pairs where q is a state and x is a string, and the arcs are from (q, x) to (δ(q, σ), x σ) where σ is either a symbol (weight 1, back of the double-ended queue) or ε (weight 0, front of the double-ended queue). By enumerating in this order, we can easily add a size limit.

We parse the regular expression with recursive descent. I'm not going to explain further; there are a million calculator tutorials out there.

Don't-run-this-in-production-grade C++ below.

#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());
}

Output:

"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"
...
user_21446690
Related