regex2mdfa.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "provenance": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "code",
      "source": [
        "# !python --version\n",
        "# !python -m pip install graphviz"
      ],
      "metadata": {
        "id": "PFZ6bTbaxdd6"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "# Lexer File\n",
        "\n",
        "It's used to tokenize the input regex string\n",
        "\n",
        "> Note: Lexer completely ignores escape character,\n",
        "> so whatever character you choose for #them, it’s one you can’t match literally\n",
        "> (and you can easily modify it to allow escaping #the escapes themselves)"
      ],
      "metadata": {
        "id": "0ZzSUfQmudhb"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "from enum import Enum, auto\n",
        "\n",
        "\n",
        "# | * + ? ( ) [ ] - are the meta characters\n",
        "class TokenType(Enum):\n",
        "    OR = auto()\n",
        "    STAR = auto()\n",
        "    PLUS = auto()\n",
        "    DASH = auto()\n",
        "    LITERAL_CHARACTER = auto()\n",
        "    QUESTION_MARK = auto()\n",
        "    OPEN_PARENTHESIS = auto()\n",
        "    CLOSED_PARENTHESIS = auto()\n",
        "    OPEN_SQUARE_BRACKET = auto()\n",
        "    CLOSED_SQUARE_BRACKET = auto()\n",
        "\n",
        "\n",
        "class Token:\n",
        "    # colab error: unsupported operand type(s) for |: 'type' and 'NoneType'\n",
        "    # def __init__(self, token_type: TokenType, value: str | None):\n",
        "    def __init__(self, token_type: TokenType, value):\n",
        "        self.token_type = token_type\n",
        "        self.value = value\n",
        "\n",
        "    def __str__(self):\n",
        "        return f\"<{self.token_type}, {self.value}>\"\n",
        "\n",
        "    def __repr__(self):\n",
        "        return f\"<{self.token_type}, {self.value}>\"\n",
        "\n",
        "\n",
        "class Lexer:\n",
        "    Escape_Character = \"/\"\n",
        "    Meta_Characters_Map = {\n",
        "        \"|\": TokenType.OR,\n",
        "        \"*\": TokenType.STAR,\n",
        "        \"+\": TokenType.PLUS,\n",
        "        \"?\": TokenType.QUESTION_MARK,\n",
        "        \"(\": TokenType.OPEN_PARENTHESIS,\n",
        "        \")\": TokenType.CLOSED_PARENTHESIS,\n",
        "        \"[\": TokenType.OPEN_SQUARE_BRACKET,\n",
        "        \"]\": TokenType.CLOSED_SQUARE_BRACKET,\n",
        "        \"-\": TokenType.DASH,\n",
        "    }\n",
        "\n",
        "    def __init__(self, input_regex: str):\n",
        "        self.input_regex = input_regex\n",
        "        self.tokens = []\n",
        "\n",
        "    def tokenize(self) -> list[Token]:\n",
        "        prev_char = None\n",
        "        for char in self.input_regex:\n",
        "            if char == Lexer.Escape_Character:\n",
        "                prev_char = char\n",
        "                continue\n",
        "            if char in Lexer.Meta_Characters_Map and prev_char != Lexer.Escape_Character:\n",
        "                self.tokens.append(Token(Lexer.Meta_Characters_Map[char], char))\n",
        "            else:\n",
        "                self.tokens.append(Token(TokenType.LITERAL_CHARACTER, char))\n",
        "            prev_char = char\n",
        "        return self.tokens\n",
        "        "
      ],
      "metadata": {
        "id": "gRxYPOkIuI2q"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "# AST Classes\n",
        "\n",
        "This `Parser` will be using those classes when parsing the tokens returned from the `Lexer`"
      ],
      "metadata": {
        "id": "ekHBnnF0vBz_"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "class AstNode:\n",
        "    pass\n",
        "\n",
        "\n",
        "class OrAstNode(AstNode):\n",
        "    def __init__(self, left: AstNode, right: AstNode):\n",
        "        self.left = left\n",
        "        self.right = right\n",
        "\n",
        "    def __str__(self):\n",
        "        return f\"({self.left} | {self.right})\"\n",
        "\n",
        "    def __repr__(self):\n",
        "        return f\"({self.left} | {self.right})\"\n",
        "\n",
        "\n",
        "class SeqAstNode(AstNode):\n",
        "    def __init__(self, left: AstNode, right: AstNode):\n",
        "        self.left = left\n",
        "        self.right = right\n",
        "\n",
        "    def __str__(self):\n",
        "        return f\"({self.left} {self.right})\"\n",
        "\n",
        "    def __repr__(self):\n",
        "        return f\"({self.left} {self.right})\"\n",
        "\n",
        "\n",
        "class StarAstNode(AstNode):\n",
        "    def __init__(self, left: AstNode):\n",
        "        self.left = left\n",
        "\n",
        "    def __str__(self):\n",
        "        return f\"({self.left}*)\"\n",
        "\n",
        "    def __repr__(self):\n",
        "        return f\"({self.left}*)\"\n",
        "\n",
        "\n",
        "class PlusAstNode(AstNode):\n",
        "    def __init__(self, left: AstNode):\n",
        "        self.left = left\n",
        "\n",
        "    def __str__(self):\n",
        "        return f\"({self.left}+)\"\n",
        "\n",
        "    def __repr__(self):\n",
        "        return f\"({self.left}+)\"\n",
        "\n",
        "\n",
        "class QuestionMarkAstNode(AstNode):\n",
        "    def __init__(self, left: AstNode):\n",
        "        self.left = left\n",
        "\n",
        "    def __str__(self):\n",
        "        return f\"({self.left}?)\"\n",
        "\n",
        "    def __repr__(self):\n",
        "        return f\"({self.left}?)\"\n",
        "\n",
        "\n",
        "class LiteralCharacterAstNode(AstNode):\n",
        "    def __init__(self, char: str):\n",
        "        self.char = char\n",
        "\n",
        "    def __str__(self):\n",
        "        return self.char\n",
        "\n",
        "    def __repr__(self):\n",
        "        return self.char\n",
        "\n",
        "\n",
        "class CharacterClassAstNode(AstNode):\n",
        "    # colab error: unsupported operand type(s) for |: 'type' and 'types.GenericAlias'\n",
        "    # def __init__(self, char_class: set[str | tuple[str, str]]): \n",
        "    def __init__(self, char_class):\n",
        "        self.char_class = char_class\n",
        "\n",
        "    def __str__(self):\n",
        "        return f\"[{self.char_class}]\"\n",
        "\n",
        "    def __repr__(self):\n",
        "        return f\"[{self.char_class}]\""
      ],
      "metadata": {
        "id": "Xgtp7X4FvZmA"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "# Parser File\n",
        "\n",
        "This will build the necessary `AST` so later the compiler backend will be able to use it and build the `NFA`, `DFA` and `Minmized DFA` \n",
        "\n",
        "\n",
        "### The Grammer used as the guide line for the parser is as following:\n",
        "```\n",
        "regex-expr = regex-or-expr\n",
        "\n",
        "regex-or-expr = regex-seq-expr (OR_TOKEN regex-seq-expr)*\n",
        "\n",
        "regex-seq-expr = regex-quantified-expr (regex-quantified-expr)*\n",
        "\n",
        "regex-quantified-expr = \n",
        "  regex-base-expr (STAR_TOKEN | PLUS_TOKEN | QUESTION_MARK_TOKEN)?\n",
        "\n",
        "regex-base-expr ::= \n",
        "  LITERAL_CHAR_TOKEN | \n",
        "  OPEN_SQUARE_BRACKET_TOKEN square-bracket-content CLOSED_SQUARE_BRACKET_TOKEN |\n",
        "  OPEN_PARENTHESIS_TOKEN regex-expr CLOSED_PARENTHESIS_TOKEN\n",
        "\n",
        "square-bracket-content = square-bracket-element+\n",
        "\n",
        "square-bracket-element = \n",
        "  LITERAL_CHAR_TOKEN | \n",
        "  LITERAL_CHAR_TOKEN DASH LITERAL_CHAR_TOKEN\n",
        "\n",
        "```"
      ],
      "metadata": {
        "id": "joMV7TEIvffP"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "from typing import Tuple\n",
        "\n",
        "\n",
        "class Parser:\n",
        "    def __init__(self, tokens: list[Token]):\n",
        "        self.tokens = tokens\n",
        "\n",
        "    def parse(self) -> AstNode:\n",
        "        return self.__parse(0)[0]\n",
        "\n",
        "    def __parse(self, index: int) -> Tuple[AstNode, int]:\n",
        "        return self.__parse_or(index)\n",
        "\n",
        "    def __parse_or(self, index: int) -> Tuple[AstNode, int]:\n",
        "        left, index = self.__parse_seq(index)\n",
        "        rem_tokens = index < len(self.tokens)\n",
        "        if not rem_tokens:\n",
        "            return (left, index)\n",
        "        result = left\n",
        "        while rem_tokens and self.tokens[index].token_type == TokenType.OR:\n",
        "            index += 1\n",
        "            right, index = self.__parse_seq(index)\n",
        "            result = OrAstNode(result, right)\n",
        "            rem_tokens = index < len(self.tokens)\n",
        "        return (result, index)\n",
        "\n",
        "    def __parse_seq(self, index: int) -> Tuple[AstNode, int]:\n",
        "        left, index = self.__parse_counters(index)\n",
        "        rem_tokens = index < len(self.tokens)\n",
        "        if not rem_tokens:\n",
        "            return (left, index)\n",
        "        result = left\n",
        "        while (\n",
        "            rem_tokens\n",
        "            and self.tokens[index].token_type != TokenType.OR\n",
        "            and self.tokens[index].token_type != TokenType.CLOSED_PARENTHESIS\n",
        "        ):\n",
        "            right, index = self.__parse_counters(index)\n",
        "            result = SeqAstNode(result, right)\n",
        "            rem_tokens = index < len(self.tokens)\n",
        "        return (result, index)\n",
        "\n",
        "    def __parse_counters(self, index: int) -> Tuple[AstNode, int]:\n",
        "        left, index = self.__parse_base(index)\n",
        "        rem_tokens = index < len(self.tokens)\n",
        "        if not rem_tokens:\n",
        "            return (left, index)\n",
        "        # if not rem_tokens:\n",
        "        #     return (left, index)\n",
        "        # if rem_tokens and self.tokens[index].token_type == TokenType.QUESTION_MARK:\n",
        "        #     index += 1\n",
        "        #     return (QuestionMarkAstNode(left), index)\n",
        "        # if rem_tokens and self.tokens[index].token_type == TokenType.STAR:\n",
        "        #     index += 1\n",
        "        #     return (StarAstNode(left), index)\n",
        "        # if rem_tokens and self.tokens[index].token_type == TokenType.PLUS:\n",
        "        #     index += 1\n",
        "        #     return (PlusAstNode(left), index)\n",
        "        while rem_tokens and self.tokens[index].token_type in [TokenType.PLUS, TokenType.STAR, TokenType.QUESTION_MARK]:\n",
        "            if rem_tokens and self.tokens[index].token_type == TokenType.QUESTION_MARK:\n",
        "                index += 1\n",
        "                left = QuestionMarkAstNode(left)\n",
        "            elif rem_tokens and self.tokens[index].token_type == TokenType.STAR:\n",
        "                index += 1\n",
        "                left = StarAstNode(left)\n",
        "            elif rem_tokens and self.tokens[index].token_type == TokenType.PLUS:\n",
        "                index += 1\n",
        "                left = PlusAstNode(left)\n",
        "            rem_tokens = index < len(self.tokens)\n",
        "        return (left, index)\n",
        "\n",
        "    def __parse_square_bracket(self, index: int) -> Tuple[AstNode, int]:\n",
        "        rem_tokens = index < len(self.tokens)\n",
        "        if not rem_tokens:\n",
        "            raise Exception()\n",
        "        chars = []\n",
        "        end_range = False\n",
        "        while rem_tokens and self.tokens[index].token_type != TokenType.CLOSED_SQUARE_BRACKET:\n",
        "            if self.tokens[index].token_type == TokenType.DASH:\n",
        "                end_range = True\n",
        "            elif end_range:\n",
        "                if len(chars) == 0:\n",
        "                    raise Exception()\n",
        "                start = chars.pop()\n",
        "                end = self.tokens[index].value\n",
        "                if start > end:\n",
        "                    raise Exception()\n",
        "                chars.append((start, end))\n",
        "                end_range = False\n",
        "            else:\n",
        "                chars.append(self.tokens[index].value)\n",
        "            index += 1\n",
        "            rem_tokens = index < len(self.tokens)\n",
        "        if not rem_tokens:\n",
        "            raise Exception()\n",
        "        return (CharacterClassAstNode(set(chars)), index)\n",
        "\n",
        "    def __parse_base(self, index: int) -> Tuple[AstNode, int]:\n",
        "        rem_tokens = index < len(self.tokens)\n",
        "        if not rem_tokens:\n",
        "            raise Exception()\n",
        "        current_token = self.tokens[index]\n",
        "        index += 1\n",
        "        if current_token.token_type == TokenType.LITERAL_CHARACTER:\n",
        "            return (LiteralCharacterAstNode(current_token.value), index)\n",
        "        if current_token.token_type == TokenType.OPEN_PARENTHESIS:\n",
        "            left, index = self.__parse(index)\n",
        "            rem_tokens = index < len(self.tokens)\n",
        "            if not rem_tokens:\n",
        "                raise Exception()\n",
        "            if self.tokens[index].token_type != TokenType.CLOSED_PARENTHESIS:\n",
        "                raise Exception()\n",
        "            index += 1\n",
        "            return (left, index)\n",
        "        if current_token.token_type == TokenType.OPEN_SQUARE_BRACKET:\n",
        "            left, index = self.__parse_square_bracket(index)\n",
        "            rem_tokens = index < len(self.tokens)\n",
        "            if not rem_tokens:\n",
        "                raise Exception()\n",
        "            if self.tokens[index].token_type != TokenType.CLOSED_SQUARE_BRACKET:\n",
        "                raise Exception()\n",
        "            index += 1\n",
        "            return (left, index)"
      ],
      "metadata": {
        "id": "CPd0KROvv8_j"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "# NFA\n",
        "\n"
      ],
      "metadata": {
        "id": "w9_0rYyOyHs7"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "from enum import Enum\n",
        "from typing import Dict, List, Set, Tuple\n",
        "\n",
        "\n",
        "class State:\n",
        "    def __init__(self, label: str, accept: bool = False):\n",
        "        self.label = label\n",
        "        self.accept = accept\n",
        "\n",
        "    def __str__(self):\n",
        "        return self.label\n",
        "\n",
        "    def __repr__(self):\n",
        "        return self.label\n",
        "\n",
        "    def __eq__(self, other):\n",
        "        if isinstance(other, State):\n",
        "            return self.label == other.label\n",
        "        return False\n",
        "\n",
        "    def __lt__(self, other):\n",
        "        if isinstance(other, State):\n",
        "            return self.label < other.label\n",
        "        return False\n",
        "\n",
        "    def __hash__(self):\n",
        "        return hash(self.label)\n",
        "\n",
        "\n",
        "class ThompsonNFA:\n",
        "    def __init__(self, start: State, end: State):\n",
        "        self.start = start\n",
        "        self.end = end\n",
        "\n",
        "\n",
        "EPSILON = \"ε\"\n",
        "\n",
        "\n",
        "# transition table will be like this:\n",
        "# {from_state: [(to_state, char)]}\n",
        "# where from_state is the state that the transition is coming from\n",
        "# and to_state is the state that the transition is going to\n",
        "# and char is the character that the transition is on the edge & epsilons\n",
        "__transition_table: Dict[State, List[Tuple[State, str]]] = {}\n",
        "\n",
        "# to store the initial and terminal states of the NFA\n",
        "__starting_state, __accepting_state = State(None), State(None)\n",
        "\n",
        "# set the verbosity level of the NFA\n",
        "# i.e whether to expand ranges like [a-z] to [a, b, c, ..., z] or not\n",
        "__verbose = False\n",
        "\n",
        "def get_transition_table() -> Dict[State, List[Tuple[State, str]]]:\n",
        "    return __transition_table\n",
        "\n",
        "\n",
        "def get_starting_state() -> State:\n",
        "    global __starting_state\n",
        "    return __starting_state\n",
        "\n",
        "\n",
        "def get_accepting_state() -> State:\n",
        "    global __accepting_state\n",
        "    return __accepting_state\n",
        "\n",
        "\n",
        "def ast_to_nfa(root: AstNode, verbose: bool = False) -> None:\n",
        "    global __verbose\n",
        "    __verbose = verbose\n",
        "    _, _ = __ast_to_nfa(root=root, index=0)\n",
        "    # __transition_table[nfa.start] = [(nfa.end, EPSILON)]\n",
        "\n",
        "\n",
        "def __add_transition(from_state: State, to_state: State, char: str) -> None:\n",
        "    global __transition_table\n",
        "    if from_state not in __transition_table:\n",
        "        __transition_table[from_state] = []\n",
        "    # print(f\"adding transition from {from_state} to {to_state} on {char}\")\n",
        "    __transition_table[from_state].append((to_state, char))\n",
        "\n",
        "\n",
        "def __update_start_finish(start: State, end: State) -> None:\n",
        "    global __starting_state, __accepting_state\n",
        "    __starting_state = start\n",
        "    __accepting_state = end\n",
        "\n",
        "\n",
        "def __ast_to_nfa(root: AstNode, index: int = 0) -> Tuple[ThompsonNFA, int]:\n",
        "    global __verbose\n",
        "    if root is None:\n",
        "        start = State(f\"S{index}\")\n",
        "        end = State(f\"S{index + 1}\")\n",
        "        __update_start_finish(start, end)\n",
        "        # __add_transition(start, end, EPSILON)\n",
        "        return ThompsonNFA(start, end), index + 2\n",
        "    if isinstance(root, LiteralCharacterAstNode):\n",
        "        return __literal_character_ast_to_nfa(root.char, index)\n",
        "    if isinstance(root, OrAstNode):\n",
        "        return __or_ast_to_nfa(root, index)\n",
        "    if isinstance(root, SeqAstNode):\n",
        "        return __seq_ast_to_nfa(root, index)\n",
        "    if isinstance(root, StarAstNode):\n",
        "        return __star_ast_to_nfa(root, index)\n",
        "    if isinstance(root, PlusAstNode):\n",
        "        return __plus_ast_to_nfa(root, index)\n",
        "    if isinstance(root, QuestionMarkAstNode):\n",
        "        return __question_mark_ast_to_nfa(root, index)\n",
        "    if isinstance(root, CharacterClassAstNode):\n",
        "        if __verbose:\n",
        "            return __character_class_ast_to_nfa_verbose(root, index)\n",
        "        else:\n",
        "            return __character_class_ast_to_nfa(root, index)\n",
        "\n",
        "\n",
        "def __literal_character_ast_to_nfa(root_char: str, index: int) -> Tuple[ThompsonNFA, int]:\n",
        "    start = State(f\"S{index}\")\n",
        "    end = State(f\"S{index + 1}\")\n",
        "    __add_transition(start, end, root_char)\n",
        "    __update_start_finish(start, end)\n",
        "    return ThompsonNFA(start, end), index + 2\n",
        "\n",
        "\n",
        "def __or_ast_to_nfa(root: OrAstNode, index: int) -> Tuple[ThompsonNFA, int]:\n",
        "    \"\"\"\n",
        "          -e-> S2 -a-> S3 -e->\n",
        "         //                   \\\\\n",
        "     -> S0                     -> S6\n",
        "         \\\\                   //\n",
        "          -e-> S4 -b-> S5 -e->\n",
        "    \"\"\"\n",
        "    start = State(f\"S{index}\")  # S0\n",
        "    left_nfa, index = __ast_to_nfa(root.left, index + 1)\n",
        "    right_nfa, index = __ast_to_nfa(root.right, index + 1)\n",
        "    end = State(f\"S{index}\")  # S6\n",
        "    __add_transition(start, left_nfa.start, EPSILON)  # S0 -e-> S2\n",
        "    __add_transition(start, right_nfa.start, EPSILON)  # S0 -e-> S4\n",
        "    __add_transition(left_nfa.end, end, EPSILON)  # S3 -e-> S6\n",
        "    __add_transition(right_nfa.end, end, EPSILON)  # S5 -e-> S6\n",
        "    __update_start_finish(start, end)\n",
        "    return ThompsonNFA(start, end), index + 1\n",
        "\n",
        "\n",
        "def __seq_ast_to_nfa(root: SeqAstNode, index: int) -> Tuple[ThompsonNFA, int]:\n",
        "    \"\"\"\n",
        "    -> S0 -a-> S1 -e-> S2 -b-> S3\n",
        "    \"\"\"\n",
        "    start = State(f\"S{index}\")  # S0\n",
        "    left_nfa, index = __ast_to_nfa(root.left, index + 1)\n",
        "    right_nfa, index = __ast_to_nfa(root.right, index + 1)\n",
        "    __add_transition(start, left_nfa.start, EPSILON)  # S0 -e-> S1\n",
        "    __add_transition(left_nfa.end, right_nfa.start, EPSILON)  # S2 -e-> S3\n",
        "    __update_start_finish(start, right_nfa.end)\n",
        "    return ThompsonNFA(start, right_nfa.end), index + 1\n",
        "\n",
        "\n",
        "def __star_ast_to_nfa(root: StarAstNode, index: int) -> Tuple[ThompsonNFA, int]:\n",
        "    \"\"\"\n",
        "        v------e-------|\n",
        "    -> S0 -e-> S1 -a-> S2 -e-> S3\n",
        "        ^---------e------------|\n",
        "    \"\"\"\n",
        "    start = State(f\"S{index}\")  # S0\n",
        "    nfa, index = __ast_to_nfa(root.left, index + 1)\n",
        "    end = State(f\"S{index}\")  # S3\n",
        "    __add_transition(start, end, EPSILON)  # S0 -e-> S3\n",
        "    __add_transition(start, nfa.start, EPSILON)  # S0 -e-> S1\n",
        "    __add_transition(nfa.end, end, EPSILON)  # S2 -e-> S3\n",
        "    __add_transition(nfa.end, nfa.start, EPSILON)  # S2 -e-> S1\n",
        "    __update_start_finish(start, end)\n",
        "    return ThompsonNFA(start, end), index + 1\n",
        "\n",
        "\n",
        "def __plus_ast_to_nfa(root: PlusAstNode, index: int) -> Tuple[ThompsonNFA, int]:\n",
        "    \"\"\"\n",
        "        v------e-------|\n",
        "    -> S0 -e-> S1 -a-> S2 -e-> S3\n",
        "    \"\"\"\n",
        "    start = State(f\"S{index}\")  # S0\n",
        "    nfa, index = __ast_to_nfa(root.left, index + 1)\n",
        "    end = State(f\"S{index}\")  # S3\n",
        "    __add_transition(start, nfa.start, EPSILON)  # S0 -e-> S1\n",
        "    __add_transition(nfa.end, end, EPSILON)  # S2 -e-> S3\n",
        "    __add_transition(nfa.end, nfa.start, EPSILON)  # S2 -e-> S1\n",
        "    __update_start_finish(start, end)\n",
        "    return ThompsonNFA(start, end), index + 1\n",
        "\n",
        "\n",
        "def __question_mark_ast_to_nfa(root: QuestionMarkAstNode, index: int) -> Tuple[ThompsonNFA, int]:\n",
        "    \"\"\"\n",
        "        |------e-------v\n",
        "    -> S0 -e-> S1 -a-> S2\n",
        "                |--e---^\n",
        "    \"\"\"\n",
        "    start = State(f\"S{index}\")  # S0\n",
        "    nfa, index = __ast_to_nfa(root.left, index + 1)\n",
        "    end = State(f\"S{index}\")  # S2\n",
        "    __add_transition(start, end, EPSILON)  # S0 -e-> S2\n",
        "    __add_transition(start, nfa.start, EPSILON)  # S0 -e-> S1\n",
        "    __add_transition(nfa.end, end, EPSILON)  # S2 -e-> S2\n",
        "    __update_start_finish(start, end)\n",
        "    return ThompsonNFA(start, end), index + 1\n",
        "\n",
        "\n",
        "def __character_class_ast_to_nfa(root: CharacterClassAstNode, index: int) -> Tuple[ThompsonNFA, int]:\n",
        "    \"\"\"\n",
        "    this time root it has a set[str | Tuple[str, str]] so in\n",
        "    1. just a char: it's just a literal char\n",
        "    2. a range: it's a range of chars like [a-z] => \"a-z\" for simplicity\n",
        "        2.a it could be written as [abc...z], later maybe !\n",
        "        2.b in case of reversed range => the parser will throw an error\n",
        "    then consider all of the result as ored literals\n",
        "    \"\"\"\n",
        "    start = State(f\"S{index}\")  # S0\n",
        "    nfas = []\n",
        "    for char in root.char_class:\n",
        "        if isinstance(char, str):\n",
        "            value = char\n",
        "        else:\n",
        "            value = f\"{char[0]}-{char[1]}\"\n",
        "        nfa, index = __literal_character_ast_to_nfa(value, index + 1)\n",
        "        nfas.append(nfa)\n",
        "\n",
        "    # or each 2 nfas together\n",
        "    while len(nfas) > 1:\n",
        "        nfa1 = nfas.pop()\n",
        "        nfa2 = nfas.pop()\n",
        "        semi_start = State(f\"S{index + 1}\")  # S0\n",
        "        semi_end = State(f\"S{index + 2}\")  # S1\n",
        "        __add_transition(semi_start, nfa1.start, EPSILON)  # S0 -e-> S1\n",
        "        __add_transition(semi_start, nfa2.start, EPSILON)  # S0 -e-> S2\n",
        "        __add_transition(nfa1.end, semi_end, EPSILON)  # S3 -e-> S4\n",
        "        __add_transition(nfa2.end, semi_end, EPSILON)  # S5 -e-> S4\n",
        "        nfas.append(ThompsonNFA(semi_start, semi_end))\n",
        "        index += 2\n",
        "\n",
        "    end = State(f\"S{index + 1}\")  # S1\n",
        "    __add_transition(nfas[0].end, end, EPSILON)  # S3 -e-> S4\n",
        "    __add_transition(start, nfas[0].start, EPSILON)  # S0 -e-> S1\n",
        "    __update_start_finish(start, end)\n",
        "    return ThompsonNFA(start, end), index + 2\n",
        "\n",
        "# def __character_class_ast_to_nfa_verbose(root: CharacterClassAstNode, index: int) -> Tuple[ThompsonNFA, int]:\n",
        "# \"\"\"\n",
        "#                     -e-> S2 -a-> S3 -e->\n",
        "#                   //                    \\\\\n",
        "#               -> S0                     S6 ->\n",
        "#             //    \\\\                    //   \\\\\n",
        "#            //      -e-> S4 -b-> S5 -e-->      \\\\\n",
        "#        -> S0                                   S7 ->\n",
        "#            \\\\                                 //\n",
        "#             \\\\                               //\n",
        "#              ---e----> S4 -b-> S5 -----e----->\n",
        "# \"\"\"\n",
        "#     def build_or_ast_from_set(chars: Set[str]) -> AstNode:\n",
        "#         if len(chars) == 1:\n",
        "#             return LiteralCharacterAstNode(chars.pop())\n",
        "#         else:\n",
        "#             char = chars.pop()\n",
        "#             return OrAstNode(LiteralCharacterAstNode(char), build_or_ast_from_set(chars))\n",
        "#     all_chars = set()\n",
        "#     for char in root.char_class:\n",
        "#         if isinstance(char, str):\n",
        "#             all_chars.add(char)\n",
        "#         else:\n",
        "#             for c in range(ord(char[0]), ord(char[1]) + 1):\n",
        "#                 all_chars.add(chr(c))\n",
        "#     return __ast_to_nfa(build_or_ast_from_set(all_chars), index)\n",
        "\n",
        "\n",
        "def __character_class_ast_to_nfa_verbose(root: CharacterClassAstNode, index: int) -> Tuple[ThompsonNFA, int]:\n",
        "    \"\"\"\n",
        "          ---------a-------->\n",
        "         //                 \\\\\n",
        "     -> S0 ---------b-------> S1\n",
        "         \\\\                 //\n",
        "          ---------c-------->\n",
        "    \"\"\"\n",
        "    start = State(f\"S{index}\")  # S0\n",
        "    index += 1\n",
        "    end = State(f\"S{index}\")\n",
        "\n",
        "    all_chars = set()\n",
        "    for char in root.char_class:\n",
        "        if isinstance(char, str):\n",
        "            all_chars.add(char)\n",
        "        else:\n",
        "            for c in range(ord(char[0]), ord(char[1]) + 1):\n",
        "                all_chars.add(chr(c))\n",
        "\n",
        "    for char in all_chars:\n",
        "        __add_transition(start, end, char)\n",
        "\n",
        "    __update_start_finish(start, end)\n",
        "\n",
        "    return ThompsonNFA(start, end), index + 1\n",
        "\n"
      ],
      "metadata": {
        "id": "bN6Q915LyHiN"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "# DFA"
      ],
      "metadata": {
        "id": "FQGrHz1VymAU"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "# this file is used to generate the DFA from the NFA\n",
        "\n",
        "from typing import Dict, List, Tuple, Set\n",
        "from copy import deepcopy\n",
        "\n",
        "\n",
        "class DFA:\n",
        "    def __init__(\n",
        "        self,\n",
        "        starting_state: frozenset[State],\n",
        "        accepting_states: list[frozenset[State]],\n",
        "        transitions: Dict[frozenset[State], Set[Tuple[frozenset[State], str]]],\n",
        "        all_states: Set[frozenset[State]],\n",
        "    ):\n",
        "        self.starting_state = starting_state\n",
        "        self.accepting_states = accepting_states\n",
        "        self.transitions = transitions\n",
        "        self.all_states = all_states\n",
        "\n",
        "\n",
        "class DFAClean:\n",
        "    def __init__(\n",
        "        self,\n",
        "        starting_state: State,\n",
        "        accepting_states: list[State],\n",
        "        transitions: Dict[State, Set[Tuple[State, str]]],\n",
        "        all_states: Set[State],\n",
        "    ):\n",
        "        self.starting_state = starting_state\n",
        "        self.accepting_states = accepting_states\n",
        "        self.transitions = transitions\n",
        "        self.all_states = all_states\n",
        "\n",
        "\n",
        "def __get_epsilon_closure(nfa_start: State, nfa_transitions: Dict[State, List[Tuple[State, str]]]) -> Set[State]:\n",
        "    \"\"\"\n",
        "    Returns the epsilon closure of the given NFA start state.\n",
        "\n",
        "    Args:\n",
        "        nfa_start: The start state of the NFA.\n",
        "        nfa_transitions: The transitions of the NFA. it's in the form of:\n",
        "        {from_state: [(to_state, transition_symbol|ε), ...], }\n",
        "\n",
        "    Returns:\n",
        "        The epsilon closure of the given NFA start state.\n",
        "    \"\"\"\n",
        "\n",
        "    # A state R is in the epsilon closure of a state S if\n",
        "    # 1- S is R\n",
        "    # 2- R can be reached via an epsilon transition from any state in the epsilon closure of S\n",
        "    epsilon_closure = set()\n",
        "    epsilon_closure.add(nfa_start)\n",
        "    still_adding = True\n",
        "    while still_adding:\n",
        "        still_adding = False\n",
        "        for state in deepcopy(epsilon_closure):\n",
        "            for next_state, char in nfa_transitions.get(state, []):\n",
        "                if char == EPSILON and next_state not in epsilon_closure:\n",
        "                    still_adding = True\n",
        "                    epsilon_closure.add(next_state)\n",
        "    return epsilon_closure\n",
        "\n",
        "\n",
        "def build_powerset(\n",
        "    nfa_start: State,\n",
        "    nfa_accepting: State,\n",
        "    nfa_transitions: Dict[State, List[Tuple[State, str]]],\n",
        ") -> DFA:\n",
        "    \"\"\"\n",
        "    Builds the powerset of the given NFA.\n",
        "\n",
        "    Args:\n",
        "        nfa_start: The start state of the NFA.\n",
        "        nfa_accepting: The accepting state of the NFA.\n",
        "        nfa_transitions: The transitions of the NFA. it's in the form of:\n",
        "        {from_state: [(to_state, transition_symbol|ε), ...], }\n",
        "\n",
        "    Returns:\n",
        "        a DFA {starting_state, accepting_states, transitions, all_states}\n",
        "    \"\"\"\n",
        "\n",
        "    dfa_start = __get_epsilon_closure(nfa_start, nfa_transitions)\n",
        "    dfa_accept: List[frozenset[State]] = []\n",
        "    dfa_states: Set[frozenset[State]] = set()\n",
        "    dfa_transitions: Dict[frozenset[State], Set[Tuple[frozenset[State], str]]] = {}\n",
        "\n",
        "    superstates_to_process: List[Set[State]] = [dfa_start]\n",
        "\n",
        "    while superstates_to_process:\n",
        "        superstate = superstates_to_process.pop()\n",
        "        frozen_superstate = frozenset(superstate)\n",
        "        dfa_states.add(frozen_superstate)\n",
        "        if nfa_accepting in superstate:\n",
        "            dfa_accept.append(frozen_superstate)\n",
        "\n",
        "        superstate_transitions: Dict[str, Set[State]] = {}\n",
        "        for state in superstate:\n",
        "            for next_state, char in nfa_transitions.get(state, []):\n",
        "                if char != EPSILON:\n",
        "                    state_moving = __get_epsilon_closure(next_state, nfa_transitions)\n",
        "                    if char in superstate_transitions:\n",
        "                        superstate_transitions[char] = superstate_transitions[char].union(state_moving)\n",
        "                    else:\n",
        "                        superstate_transitions[char] = state_moving\n",
        "\n",
        "        for char, next_superstate in superstate_transitions.items():\n",
        "            frozen_next_superstate = frozenset(next_superstate)\n",
        "            if frozen_superstate in dfa_transitions:\n",
        "                dfa_transitions[frozen_superstate].add((frozen_next_superstate, char))\n",
        "            else:\n",
        "                dfa_transitions[frozen_superstate] = {(frozen_next_superstate, char)}\n",
        "            if next_superstate not in dfa_states:\n",
        "                superstates_to_process.append(next_superstate)\n",
        "\n",
        "    return DFA(frozenset(dfa_start), dfa_accept, dfa_transitions, dfa_states)\n",
        "\n",
        "\n",
        "def clean_dfa(dfa: DFA) -> DFAClean:\n",
        "    \"\"\"\n",
        "    Cleans the given DFA i.e exchange the supersets with just a single state representing them.\n",
        "\n",
        "    Args:\n",
        "        dfa: The DFA to clean.\n",
        "\n",
        "    Returns:\n",
        "        A DFAClean {starting_state, accepting_states, transitions, all_states}\n",
        "    \"\"\"\n",
        "    index = 0\n",
        "    superstate_to_state: Dict[frozenset[State], State] = {}\n",
        "    for superstate in dfa.all_states:\n",
        "        superstate_to_state[superstate] = State(f\"S{index}\")\n",
        "        index += 1\n",
        "    clean_start = superstate_to_state[dfa.starting_state]\n",
        "    clean_accepting = [superstate_to_state[superstate] for superstate in dfa.accepting_states]\n",
        "\n",
        "    clean_transitions: Dict[State, Set[Tuple[State, str]]] = {}\n",
        "    for superstate, transitions in dfa.transitions.items():\n",
        "        for next_superstate, char in transitions:\n",
        "            if superstate_to_state[superstate] in clean_transitions:\n",
        "                clean_transitions[superstate_to_state[superstate]].add((superstate_to_state[next_superstate], char))\n",
        "            else:\n",
        "                clean_transitions[superstate_to_state[superstate]] = {(superstate_to_state[next_superstate], char)}\n",
        "\n",
        "    clean_all_states = set(superstate_to_state.values())\n",
        "\n",
        "    return DFAClean(clean_start, clean_accepting, clean_transitions, clean_all_states)\n"
      ],
      "metadata": {
        "id": "gHE1MCLZyvR0"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "# Minimzed DFA"
      ],
      "metadata": {
        "id": "xZ8g0niJyzlI"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "\n",
        "from typing import Dict, List, Tuple, Set\n",
        "from copy import deepcopy\n",
        "\n",
        "\n",
        "class Hashabledict(dict):\n",
        "    def __hash__(self):\n",
        "        return hash(frozenset(self.items()))\n",
        "\n",
        "\n",
        "def minimize_dfa(cdfa: DFAClean) -> DFAClean:\n",
        "    accepting_states = set(cdfa.accepting_states)\n",
        "    rejecting_states = cdfa.all_states - accepting_states\n",
        "    accepting_states = frozenset(accepting_states)\n",
        "    rejecting_states = frozenset(rejecting_states)\n",
        "\n",
        "    which_group = {}\n",
        "    for state in cdfa.all_states:\n",
        "        if state not in accepting_states:\n",
        "            which_group[state] = rejecting_states\n",
        "        else:\n",
        "            which_group[state] = accepting_states\n",
        "\n",
        "    mdfa_all_groups = {accepting_states, rejecting_states}\n",
        "    still_splitting = True\n",
        "\n",
        "    while still_splitting:\n",
        "        still_splitting = False\n",
        "        mdfa_all_groups_copy = deepcopy(mdfa_all_groups)\n",
        "        for group in mdfa_all_groups:\n",
        "            if len(group) > 1:\n",
        "                possible_splits = {}\n",
        "                for state in group:\n",
        "                    state_transitions = Hashabledict()\n",
        "                    for next_state, char in cdfa.transitions.get(state, []):\n",
        "                        state_transitions[char] = which_group[next_state]\n",
        "\n",
        "                    if state_transitions not in possible_splits:\n",
        "                        possible_splits[state_transitions] = {state}\n",
        "                    else:\n",
        "                        possible_splits[state_transitions].add(state)\n",
        "\n",
        "                if len(possible_splits) > 1:\n",
        "                    still_splitting = True\n",
        "                    mdfa_all_groups_copy.remove(group)\n",
        "                    for new_group in possible_splits.values():\n",
        "                        new_group = frozenset(new_group)\n",
        "                        mdfa_all_groups_copy.add(new_group)\n",
        "                        for state in new_group:\n",
        "                            which_group[state] = new_group\n",
        "\n",
        "                mdfa_all_groups = deepcopy(mdfa_all_groups_copy)\n",
        "\n",
        "    mdfa_starting_state = which_group[cdfa.starting_state]\n",
        "\n",
        "    mdfa_accepting_states = []\n",
        "    for state in cdfa.accepting_states:\n",
        "        mdfa_accepting_states.append(which_group[state])\n",
        "\n",
        "    mdfa_transitions = {}\n",
        "    for state, transitions in cdfa.transitions.items():\n",
        "        mdfa_transitions[which_group[state]] = []\n",
        "        for next_state, char in transitions:\n",
        "            mdfa_transitions[which_group[state]].append((which_group[next_state], char))\n",
        "\n",
        "    mdfa_all_states = set()\n",
        "    for group in mdfa_all_groups:\n",
        "        mdfa_all_states.add(frozenset(group))\n",
        "\n",
        "    intermediate = DFA(mdfa_starting_state, mdfa_accepting_states, mdfa_transitions, mdfa_all_states)\n",
        "    return clean_dfa(intermediate)\n"
      ],
      "metadata": {
        "id": "nIIriMwMy2hs"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "# Logger Helper functions"
      ],
      "metadata": {
        "id": "jXz_wBEGy-IG"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "# this file will be used to log down the nfa, dfa and mdfa\n",
        "# into the json file with the desired format which is like this:\n",
        "\"\"\"\n",
        "{\n",
        "    \"startingState\": \"S0\"\n",
        "    \"S0\": {\n",
        "        isTerminatingState: true,\n",
        "        \"0\": \"S0\",\n",
        "        \"1\": \"S1\"\n",
        "    },\n",
        "    \"S1\": {\n",
        "        isTerminatingState: false,\n",
        "        \"0\": \"S2\",\n",
        "        \"1\": \"S0\"\n",
        "    },\n",
        "    \"S2\": {\n",
        "        isTerminatingState: true,\n",
        "        \"0\": \"S1\",\n",
        "        \"1\": \"S2\"\n",
        "    }\n",
        "}\n",
        "\"\"\"\n",
        "\n",
        "import json\n",
        "from typing import Dict, List, Tuple\n",
        "\n",
        "\n",
        "__nfa_filename = \"NFA.json\"\n",
        "# colab error: unsupported operand type(s) for |: 'type' and 'type'\n",
        "# __nfa_result: Dict[str, str | Dict[str, str | bool]] = {}\n",
        "__nfa_result = {}\n",
        "\n",
        "__mdfa_filename = \"MDFA.json\"\n",
        "# colab error: unsupported operand type(s) for |: 'type' and 'type'\n",
        "# __mdfa_result: Dict[str, str | Dict[str, str | bool]] = {}\n",
        "__mdfa_result = {}\n",
        "\n",
        "\n",
        "def __build_nfa_result(transition_table, accepting_state: State):\n",
        "    accepted_labeled = False\n",
        "    for state, transitions in transition_table.items():\n",
        "        __nfa_result[state.label] = {}\n",
        "        accepted_labeled = accepted_labeled or (state == accepting_state)\n",
        "        for next_state, char in transitions:\n",
        "            # if the char has been added before, then make it a list and append the next state\n",
        "            if char in __nfa_result[state.label]:\n",
        "                if isinstance(__nfa_result[state.label][char], list):\n",
        "                    __nfa_result[state.label][char].append(next_state.label)\n",
        "                else:\n",
        "                    __nfa_result[state.label][char] = [__nfa_result[state.label][char], next_state.label]\n",
        "            else:\n",
        "                __nfa_result[state.label][char] = next_state.label\n",
        "        __nfa_result[state.label][\"isTerminatingState\"] = state == accepting_state\n",
        "    if not accepted_labeled:\n",
        "        __nfa_result[accepting_state.label] = {\"isTerminatingState\": True}\n",
        "\n",
        "\n",
        "def log_nfa(transition_table: Dict[State, List[Tuple[State, str]]], starting_state: State, accepting_state: State):\n",
        "    __nfa_result.update({\"startingState\": starting_state.label})\n",
        "    __build_nfa_result(transition_table, accepting_state)\n",
        "    with open(__nfa_filename, \"w\") as f:\n",
        "        json.dump(__nfa_result, f, ensure_ascii=False, indent=2)  # ensure utf-8 encoding\n",
        "\n",
        "\n",
        "def __build_mdfa_result(mdfa: DFAClean):\n",
        "    for state, transitions in mdfa.transitions.items():\n",
        "        __mdfa_result[state.label] = {}\n",
        "        for next_state, char in transitions:\n",
        "            __mdfa_result[state.label][char] = next_state.label\n",
        "        __mdfa_result[state.label][\"isTerminatingState\"] = state in mdfa.accepting_states\n",
        "\n",
        "\n",
        "def log_mdfa(mdfa: DFAClean):\n",
        "    __mdfa_result.update({\"startingState\": mdfa.starting_state.label})\n",
        "    __build_mdfa_result(mdfa)\n",
        "    with open(__mdfa_filename, \"w\") as f:\n",
        "        json.dump(__mdfa_result, f, ensure_ascii=False, indent=2)\n"
      ],
      "metadata": {
        "id": "buKAAYeTzGtt"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "# Graph and Visualize the Reults"
      ],
      "metadata": {
        "id": "hOzk-VtZzWji"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "import graphviz\n",
        "from typing import Dict, List, Tuple\n",
        "\n",
        "\n",
        "def visualize_nfa(\n",
        "    transition_table: Dict[State, List[Tuple[State, str]]],\n",
        "    starting_state: State,\n",
        "    accepting_state: State,\n",
        "    filename: str = \"NFA\",\n",
        "):\n",
        "    g = graphviz.Digraph(\"NFA\", filename=filename, format=\"png\")\n",
        "    # make the graph horizontal\n",
        "    g.attr(rankdir=\"LR\")\n",
        "    g.edge(\"\", starting_state.label)  # add an arrow entering the starting state\n",
        "    g.node(\"\", shape=\"none\")  # and remove the very first circle\n",
        "    for state, transitions in transition_table.items():\n",
        "        for next_state, char in transitions:\n",
        "            g.edge(state.label, next_state.label, label=char)\n",
        "    # add another oval for the accepting state\n",
        "    g.node(accepting_state.label, peripheries=\"2\")\n",
        "    # add a title two lines under the graph\n",
        "    g.attr(label=r\"\\n\\nNFA\", fontsize=\"20\", labelloc=\"b\")\n",
        "    g.view()\n",
        "\n",
        "\n",
        "def __frozenset_str(frozenset: frozenset[State]) -> str:\n",
        "    \"\"\"\n",
        "    Returns the name of the given frozenset like in set.__str__\n",
        "    \"\"\"\n",
        "    return \"{\" + \", \".join([state.label for state in frozenset]) + \"}\"\n",
        "\n",
        "\n",
        "def visualize_dfa(dfa: DFA, filename: str = \"DFA\"):\n",
        "    g = graphviz.Digraph(\"DFA\", filename=filename, format=\"png\")\n",
        "    g.attr(rankdir=\"LR\")\n",
        "    g.edge(\"\", __frozenset_str(dfa.starting_state))\n",
        "    g.node(\"\", shape=\"none\")\n",
        "    for state, transitions in dfa.transitions.items():\n",
        "        x = __frozenset_str(state)\n",
        "        for next_state, char in transitions:\n",
        "            y = __frozenset_str(next_state)\n",
        "            g.edge(x, y, label=char)\n",
        "    for accepting_state in dfa.accepting_states:\n",
        "        g.node(__frozenset_str(accepting_state), peripheries=\"2\")\n",
        "    g.attr(label=r\"\\n\\nDFA\", fontsize=\"20\", labelloc=\"b\")\n",
        "    g.view()\n",
        "\n",
        "\n",
        "def visualize_clean_dfa(clean_dfa: DFAClean, filename: str = \"DFAClean\"):\n",
        "    g = graphviz.Digraph(\"DFAClean\", filename=filename, format=\"png\")\n",
        "    g.attr(rankdir=\"LR\")\n",
        "    g.edge(\"\", clean_dfa.starting_state.label)\n",
        "    g.node(\"\", shape=\"none\")\n",
        "    for state, transitions in clean_dfa.transitions.items():\n",
        "        for next_state, char in transitions:\n",
        "            g.edge(state.label, next_state.label, label=char)\n",
        "    for accepting_state in clean_dfa.accepting_states:\n",
        "        g.node(accepting_state.label, peripheries=\"2\")\n",
        "    g.attr(label=r\"\\n\\nDFA Clean\", fontsize=\"20\", labelloc=\"b\")\n",
        "    g.view()\n",
        "\n",
        "\n",
        "def visualize_mdfa(mdfa: DFAClean, filename: str = \"MDFA\"):\n",
        "    g = graphviz.Digraph(\"MDFA\", filename=filename, format=\"png\")\n",
        "    g.attr(rankdir=\"LR\")\n",
        "    g.edge(\"\", mdfa.starting_state.label)\n",
        "    g.node(\"\", shape=\"none\")\n",
        "    for state, transitions in mdfa.transitions.items():\n",
        "        for next_state, char in transitions:\n",
        "            g.edge(state.label, next_state.label, label=char)\n",
        "    for accepting_state in mdfa.accepting_states:\n",
        "        g.node(accepting_state.label, peripheries=\"2\")\n",
        "    g.attr(label=r\"\\n\\nMinimized DFA\", fontsize=\"20\", labelloc=\"b\")\n",
        "    g.view()\n"
      ],
      "metadata": {
        "id": "5sXJeSj6zcRB"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "# Main"
      ],
      "metadata": {
        "id": "U5V2oX4Rzhvg"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "def get_args():\n",
        "    parser = argparse.ArgumentParser(description=\"A simple regex compiler that compiles a regex to a NFA\")\n",
        "    parser.add_argument(\n",
        "        \"regex\",\n",
        "        type=str,\n",
        "        help=\"the regex to compile\",\n",
        "    )\n",
        "    # make the verbose flag optional when given set it to true\n",
        "    parser.add_argument(\n",
        "        \"-v\",\n",
        "        \"--verbose\",\n",
        "        action=\"store_true\",\n",
        "        help=\"expand ranges like [a-z] to [a, b, c, ..., z] not just [a-z] on one edge\",\n",
        "    )\n",
        "    return parser.parse_args()\n",
        "\n",
        "\n",
        "def run(input_regex: str, verbose: bool = False):\n",
        "    lexer = Lexer(input_regex)\n",
        "    tokens = lexer.tokenize()\n",
        "\n",
        "    parser = Parser(tokens)\n",
        "    ast = parser.parse()\n",
        "    print(tokens)\n",
        "    print(ast)\n",
        "\n",
        "    ast_to_nfa(ast, verbose=verbose)\n",
        "    nfa = get_transition_table()\n",
        "\n",
        "    starting_state = get_starting_state()\n",
        "    accepting_state = get_accepting_state()\n",
        "    log_nfa(nfa, starting_state, accepting_state)\n",
        "    visualize_nfa(nfa, starting_state, accepting_state)\n",
        "\n",
        "    dfa = build_powerset(starting_state, accepting_state, nfa)\n",
        "    visualize_dfa(dfa)\n",
        "\n",
        "    cdfa = clean_dfa(dfa)\n",
        "    visualize_clean_dfa(cdfa)\n",
        "\n",
        "    mdfa = minimize_dfa(cdfa)\n",
        "    log_mdfa(mdfa)\n",
        "    visualize_mdfa(mdfa, \"MDFA\")\n"
      ],
      "metadata": {
        "id": "Yr5GpEotzlz4"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "# Testing"
      ],
      "metadata": {
        "id": "gkuAV16q0L9p"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "regex = [\n",
        "\"(AB)\", # 0\n",
        "\"(A|B)\", # 1\n",
        "\"([A-Z])\", # 2\n",
        "\"(A+)\", # 3\n",
        "\"(A*)\", # 4\n",
        "\"(((AB)((A|B)*))(AB))\", # 5\n",
        "\"((((AB)|[A-Z])+)([A-Z]*))\", # 6\n",
        "\"(((((ABE)|C)|((([A-Z])S)*))+)((AB)C))\", # 7\n",
        "\"((([a-z_])(([a-z0-9_])*))(([!?])?))\", # 8\n",
        "\"(A(((B*)|(DA))*))((CG)|(D([DEF])))\", # 9\n",
        "\"(ab\", # 10\n",
        "\"(a([b-c))\", # 11\n",
        "\"((a|b)|)\", # 12\n",
        "\"(a{3,2})\" # 13\n",
        "]\n",
        "\n",
        "run(regex[8], verbose=True)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "aJ2r34Eh0K4K",
        "outputId": "7cb7738c-d103-4639-b981-14a08dfc460a"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "[<TokenType.OPEN_PARENTHESIS, (>, <TokenType.OPEN_PARENTHESIS, (>, <TokenType.OPEN_PARENTHESIS, (>, <TokenType.OPEN_SQUARE_BRACKET, [>, <TokenType.LITERAL_CHARACTER, a>, <TokenType.DASH, ->, <TokenType.LITERAL_CHARACTER, z>, <TokenType.LITERAL_CHARACTER, _>, <TokenType.CLOSED_SQUARE_BRACKET, ]>, <TokenType.CLOSED_PARENTHESIS, )>, <TokenType.OPEN_PARENTHESIS, (>, <TokenType.OPEN_PARENTHESIS, (>, <TokenType.OPEN_SQUARE_BRACKET, [>, <TokenType.LITERAL_CHARACTER, a>, <TokenType.DASH, ->, <TokenType.LITERAL_CHARACTER, z>, <TokenType.LITERAL_CHARACTER, 0>, <TokenType.DASH, ->, <TokenType.LITERAL_CHARACTER, 9>, <TokenType.LITERAL_CHARACTER, _>, <TokenType.CLOSED_SQUARE_BRACKET, ]>, <TokenType.CLOSED_PARENTHESIS, )>, <TokenType.STAR, *>, <TokenType.CLOSED_PARENTHESIS, )>, <TokenType.CLOSED_PARENTHESIS, )>, <TokenType.OPEN_PARENTHESIS, (>, <TokenType.OPEN_PARENTHESIS, (>, <TokenType.OPEN_SQUARE_BRACKET, [>, <TokenType.LITERAL_CHARACTER, !>, <TokenType.QUESTION_MARK, ?>, <TokenType.CLOSED_SQUARE_BRACKET, ]>, <TokenType.CLOSED_PARENTHESIS, )>, <TokenType.QUESTION_MARK, ?>, <TokenType.CLOSED_PARENTHESIS, )>, <TokenType.CLOSED_PARENTHESIS, )>]\n",
            "(([{('a', 'z'), '_'}] ([{('a', 'z'), '_', ('0', '9')}]*)) ([{'!', '?'}]?))\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [],
      "metadata": {
        "id": "mke27sKoYb6G"
      },
      "execution_count": null,
      "outputs": []
    }
  ]
}