Repository: Aunsiels/pyformlang (language: python)

Issue:
Trouble with Regex
Hello,

When I was using regular expressions in my program, I found some unusual behavior.

For example, I can write this:

``` python
Python 3.9.0 (default, Nov 18 2020, 13:28:38) 
[GCC 8.3.0] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> from pyformlang.regular_expression import Regex
>>> Regex('a a | a')
((a.a)|a)
>>> Regex('a . a | a')
((a.a)|a)
>>> Regex('a* a | a')
(((a)*.a)|a)
```

So, I realise that priority of operator `.` more than priority of operator `|`. But when I use `*` just before `|`, priority of this operations changes:

``` python
>>> Regex('a a* | a')
(a.((a)*|a))
>>> Regex('a . a* | a')
(a.((a)*|a))
>>> Regex('a . a* | (a)')
(a.((a)*|a))
>>> Regex('a* a* | a')
((a)*.((a)*|a))
```

I can define expression `((a.(a)*)|a)` only through using parenthesis:

``` python
>>> Regex('(a a*) | a')
((a.(a)*)|a)
```

And error isn't in printing:

``` python
>>> Regex('b a* | a').accepts('b')
True
>>> Regex('b a* | a').accepts('a')
False
>>> Regex('(b a*) | a').accepts('a')
True
>>> 
```


Discussion / hints:

Fix patch:
diff --git a/pyformlang/__init__.py b/pyformlang/__init__.py
index 61d5c26..dc80d0a 100644
--- a/pyformlang/__init__.py
+++ b/pyformlang/__init__.py
@@ -1,18 +1,13 @@
 """
 Pyformlang
 ==========
-
 Pyformlang is a python module to perform operation on formal languages.
-
 How to use the documentation
 ----------------------------
-
 Documentation is available in two formats: docstrings directly
 in the code and a readthedocs website: https://pyformlang.readthedocs.io.
-
 Available subpackages
 ---------------------
-
 regular_expression
     Regular Expressions
 finite_automaton
@@ -26,6 +21,8 @@
     Push-Down Automata
 Indexed Grammar
     Indexed Grammar
+rsa
+    Recursive automaton
 
 """
 
@@ -34,4 +31,5 @@
            "cfg",
            "fst",
            "indexed_grammar",
-           "pda"]
+           "pda",
+           "rsa"]
diff --git a/pyformlang/rsa/box.py b/pyformlang/rsa/box.py
new file mode 100644
index 0000000..cf113a9
--- /dev/null
+++ b/pyformlang/rsa/box.py
@@ -0,0 +1,96 @@
+"""
+Representation of a box for recursive automaton
+"""
+
+from pyformlang.finite_automaton.epsilon_nfa import EpsilonNFA
+from pyformlang.finite_automaton.finite_automaton import to_symbol
+from pyformlang.finite_automaton.symbol import Symbol
+
+
+class Box:
+    """ Represents a box for recursive automaton
+
+    This class represents a box for recursive automaton
+
+    Parameters
+    ----------
+    enfa : :class:`~pyformlang.finite_automaton.EpsilonNFA`
+        A epsilon nfa
+    label : :class:`~pyformlang.finite_automaton.Symbol`
+        A label for epsilon nfa
+
+    """
+
+    def __init__(self, enfa: EpsilonNFA = None, label: Symbol = None):
+        if enfa is not None:
+            enfa = enfa.minimize()
+        self._dfa = enfa or EpsilonNFA()
+
+        if label is not None:
+            label = to_symbol(label)
+        self._label = label or Symbol("")
+
+    def change_label(self, label: Symbol):
+        """ Set a new label
+
+        Parameters
+        -----------
+        label : :class:`~pyformlang.finite_automaton.Symbol`
+            The new label for automaton
+
+        """
+        self._label = to_symbol(label)
+
+    def change_dfa(self, enfa: EpsilonNFA):
+        """ Set an epsilon finite automaton
+
+        Parameters
+        -----------
+        enfa : :class:`~pyformlang.finite_automaton.EpsilonNFA`
+            The new epsilon finite automaton
+
+        """
+        enfa = enfa.minimize()
+        self._dfa = enfa
+
+    @property
+    def dfa(self):
+        """ Box's dfa """
+        return self._dfa
+
+    @property
+    def label(self):
+        """ Box's label """
+        return self._label
+
+    @property
+    def start_state(self):
+        """ The start state """
+        return self._dfa.start_states
+
+    @property
+    def final_states(self):
+        """ The final states """
+        return self._dfa.final_states
+
+    def is_equivalent_to(self, other):
+        """ Check whether two boxes are equivalent
+
+        Parameters
+        ----------
+        other : :class:`~pyformlang.rsa.Box`
+            A sequence of input symbols
+
+        Returns
+        ----------
+        are_equivalent : bool
+            Whether the two boxes are equivalent or not
+        """
+
+        if not isinstance(other, Box):
+            return False
+
+        if self._dfa.is_equivalent_to(other.dfa) and self._label == other.label:
+            return True
+
+        return False
diff --git a/pyformlang/rsa/recursive_automaton.py b/pyformlang/rsa/recursive_automaton.py
new file mode 100644
index 0000000..f94a7eb
--- /dev/null
+++ b/pyformlang/rsa/recursive_automaton.py
@@ -0,0 +1,162 @@
+"""
+Representation of a recursive automaton
+"""
+
+from typing import AbstractSet
+
+from pyformlang.finite_automaton.finite_automaton import to_symbol
+from pyformlang.finite_automaton.symbol import Symbol
+from pyformlang.rsa.box import Box
+from pyformlang.regular_expression.regex import Regex
+
+
+class RecursiveAutomaton:
+    """ Represents a recursive automaton
+
+    This class represents a recursive automaton.
+
+    Parameters
+    ----------
+    labels : set of :class:`~pyformlang.finite_automaton.Symbol`, optional
+        A finite set of labels for boxes
+    initial_label : :class:`~pyformlang.finite_automaton.Symbol`, optional
+        A start label for automaton
+    boxes : set of :class:`~pyformlang.rsa.Box`, optional
+        A finite set of boxes
+
+    """
+
+    def __init__(self,
+                 labels: AbstractSet[Symbol] = None,
+                 initial_label: Symbol = None,
+                 boxes: AbstractSet[Box] = None):
+
+        if labels is not None:
+            labels = {to_symbol(x) for x in labels}
+        self._labels = labels or set()
+
+        if initial_label is not None:
+            initial_label = to_symbol(initial_label)
+            if initial_label not in self._labels:
+                self._labels.add(initial_label)
+        self._initial_label = initial_label or Symbol("")
+
+        self._boxes = dict()
+        if boxes is not None:
+            for box in boxes:
+                self._boxes.update({to_symbol(box.label): box})
+                self._labels.add(box.label)
+
+        for label in self._labels:
+            box = self.get_box(label)
+            if box is None:
+                raise ValueError("RSA must have the same number of labels and DFAs")
+
+    def get_box(self, label: Symbol):
+        """ Box by label """
+
+        label = to_symbol(label)
+        if label in self._boxes:
+            return self._boxes[label]
+
+        return None
+
+    def add_box(self, new_box: Box):
+        """ Set a box
+
+        Parameters
+        -----------
+        new_box : :class:`~pyformlang.rsa.Box`
+            The new box
+
+        """
+
+        self._boxes.update({new_box.label: new_box})
+        self._labels.add(to_symbol(new_box.label))
+
+    def get_number_of_boxes(self):
+        """ Size of set of boxes """
+
+        return len(self._boxes)
+
+    def change_initial_label(self, new_initial_label: Symbol):
+        """ Set an initial label
+
+        Parameters
+        -----------
+        new_initial_label : :class:`~pyformlang.finite_automaton.Symbol`
+            The new initial label
+
+        """
+
+        new_initial_label = to_symbol(new_initial_label)
+        if new_initial_label not in self._labels:
+            raise ValueError("New initial label not in set of labels for boxes")
+
+    @property
+    def labels(self) -> set:
+        """ The set of labels """
+
+        return self._labels
+
+    @property
+    def boxes(self) -> dict:
+        """ The set of boxes """
+
+        return self._boxes
+
+    @property
+    def initial_label(self) -> Symbol:
+        """ The initial label """
+
+        return self._initial_label
+
+    @classmethod
+    def from_regex(cls, regex: str, initial_label: Symbol):
+        """ Create a recursive automaton from regular expression
+
+        Parameters
+        -----------
+        regex : str
+            The regular expression
+        initial_label : :class:`~pyformlang.finite_automaton.Symbol`
+            A initial label for the recursive automaton
+
+        Returns
+        -----------
+        rsa : :class:`~pyformlang.rsa.RecursiveAutomaton`
+            The new recursive automaton
+        """
+
+        initial_label = Symbol(initial_label)
+        box = Box(Regex(regex).to_epsilon_nfa(), initial_label)
+        return RecursiveAutomaton({initial_label}, initial_label, {box})
+
+    def is_equivalent_to(self, other):
+        """ Check whether two recursive automata are equivalent
+
+        Parameters
+        ----------
+        other : :class:`~pyformlang.rsa.RecursiveAutomaton`
+            The input recursive automaton
+
+        Returns
+        ----------
+        are_equivalent : bool
+            Whether the two recursive automata are equivalent or not
+        """
+
+        if not isinstance(other, RecursiveAutomaton):
+            return False
+
+        if self._labels != other._labels:
+            return False
+
+        for label in self._labels:
+            box_1 = self.get_box(label)
+            box_2 = other.get_box(label)
+
+            if not box_1.is_equivalent_to(box_2):
+                return False
+
+        return True


Test patch:
diff --git a/pyformlang/rsa/tests/__init__.py b/pyformlang/rsa/tests/__init__.py
new file mode 100644
index 0000000..e69de29
diff --git a/pyformlang/rsa/tests/test_rsa.py b/pyformlang/rsa/tests/test_rsa.py
new file mode 100644
index 0000000..aedab17
--- /dev/null
+++ b/pyformlang/rsa/tests/test_rsa.py
@@ -0,0 +1,66 @@
+import unittest
+
+from pyformlang.rsa.recursive_automaton import RecursiveAutomaton
+from pyformlang.finite_automaton.symbol import Symbol
+from pyformlang.regular_expression import Regex
+from pyformlang.rsa.box import Box
+
+
+class TestRSA(unittest.TestCase):
+    def test_creation(self):
+        # S -> a S b | a b
+        enfa = Regex("a S b | a b").to_epsilon_nfa()
+        dfa = enfa.minimize()
+        box = Box(dfa, Symbol("S"))
+        rsa_1 = RecursiveAutomaton({Symbol("S")}, Symbol("S"), {box})
+
+        self.assertEqual(rsa_1.get_number_of_boxes(), 1)
+        self.assertEqual(box.is_equivalent_to(rsa_1.get_box(Symbol("S"))), True)
+        self.assertEqual(rsa_1.labels, {Symbol("S")})
+        self.assertEqual(rsa_1.initial_label, Symbol("S"))
+
+        rsa_2 = RecursiveAutomaton()
+        rsa_2.add_box(box)
+        rsa_2.change_initial_label(Symbol("S"))
+
+        self.assertEqual(rsa_2.is_equivalent_to(rsa_1), True)
+
+        # Checking to add a start label
+        rsa_3 = RecursiveAutomaton(set(), Symbol("S"), {box})
+        self.assertEqual(rsa_3.labels, {Symbol("S")})
+
+        try:
+            rsa_4 = RecursiveAutomaton({Symbol("S"), Symbol("v")}, Symbol("S"), {box})
+        except ValueError:
+            self.assertEqual(True, True)
+
+    def test_from_regex(self):
+        # S -> a*
+        rsa_2 = RecursiveAutomaton.from_regex("a*", Symbol("S"))
+
+        enfa = Regex("a*").to_epsilon_nfa()
+        dfa = enfa.minimize()
+        box = Box(dfa, Symbol("S"))
+        rsa_1 = RecursiveAutomaton({Symbol("S")}, Symbol("S"), {box})
+
+        self.assertEqual(rsa_2.is_equivalent_to(rsa_1), True)
+
+    def test_is_equivalent_to(self):
+        # S -> a* b*
+        rsa_1 = RecursiveAutomaton.from_regex("a* b*", Symbol("S"))
+
+        # S -> a+ b+
+        rsa_2 = RecursiveAutomaton.from_regex("a a* b b*", Symbol("S"))
+
+        self.assertEqual(rsa_1.is_equivalent_to(rsa_2), False)
+
+    def test_add_box(self):
+        rsa_1 = RecursiveAutomaton.from_regex("a* b*", Symbol("S"))
+        new_box = Box(Regex("a*").to_epsilon_nfa().minimize(), Symbol("S"))
+        rsa_1.add_box(new_box)
+        self.assertEqual(new_box.dfa.is_equivalent_to(rsa_1.get_box(Symbol("S")).dfa), True)
+        self.assertEqual(rsa_1.labels, {Symbol("S")})
+
+
+if __name__ == '__main__':
+    unittest.main()