Repository: mhulden/pyfoma

Issue:
Term negation can't be applied to multi-character symbols (and complement operator is unimplemented)
In foma/xfst, you can use multi-character symbols in "character classes" and then take the complement of these classes, for example:
```
def U [ u | uː ];
def Unround kw -> k || \U _ .#.;
```
There doesn't seem to be any way to do this in pyfoma without some kind of workaround, transforming `uː` into a single character, for example - I had thought I could use the complement operator `~` but it doesn't appear to be implemented yet.

It's not really clear to me how this *works* in foma since the resulting FSTs have magical `@` symbols in them when you look at them with graphviz or export them as AT&T format, but it does seem to work :)

Discussion:
@mhulden: Term negation `\X `in foma is simply shorthand for `? - X `(`. - X` in PyFoma). That means you can do something like `. - (u|'u:')` for the` \U` in your example.@dhdaines: Thanks!  I was thinking something like that would be the way to do it... in foma the `\` operator appears to use intersection+complement rather than subtraction, presumably for exactly the reason that it might be applied to strings longer than one symbol? (though I may be misunderstanding `fsm_identity` here, which maybe just accepts a single symbol?)
```c
struct fsm *fsm_term_negation(struct fsm *net1) {
    return(fsm_intersect(fsm_identity(),fsm_complement(net1)));
}
```
It would be good to implement the complement operator since it's mentioned in the documentation, perhaps I can take a shot at it - my understanding of it from the foma code (corroborated by OpenFst: https://www.openfst.org/doxygen/fst/html/complement_8h_source.html) is it's the `complete` operation (create arcs to ensure all labels can be read from every state) plus switching the final states to non-final (accept said arcs and not the original language).

I believe the `.` label in pyfoma already works like the `ρ` in OpenFst (and, I believe, a bit like those `@` labels in foma), that is it matches any symbol except the ones on the other arcs?@mhulden: Logically `A & ~B` is the same as `A - B`, but I don't recall why foma used intersection and complementation for the term complement.

Both negation and term negation could be implemented as in the following example:

```python3
def neg(fsm):
    return FST.re(".* - $X", {'X':fsm})

def tneg(fsm):
    return FST.re(". - $X", {'X':fsm})

mycustom = {neg, tneg}

myfst1 = FST.re("$^neg(u|'u:')", functions = mycustom)
myfst2 = FST.re("$^tneg(u|'u:')", functions = mycustom)
```

These could be included as-is as built-in functions. The negation could possibly be a prefix-operator (~) which would require an additional minor change of a line or two in the parser, I believe.@dhdaines: Makes sense! The prefix-operator `~` for complement is already in the parser (and the documentation), it just doesn't do anything: https://github.com/mhulden/pyfoma/blob/642c3e2f46b8545c04edf7afebcbcb0ee0d2abb4/src/pyfoma/private/regexparse.py#L38

I'll submit a PR...@dhdaines: Also thank you for the examples!

It turns out that in my specific example, but for rewrite rules in general, the complement operator is not useful.  This took a bit of thinking on my part to understand but is obvious in hindsight - since `~(u | u:)` matches *anything* that isn't `u` or `u:`, including epsilon, the rule will always apply, which is clearly not what we want :)

Nonetheless I implemented complement anyway in the PR - the docstring says "FSM", not sure if complement is defined for FSTs or not?

Solution patch:
diff --git a/src/pyfoma/algorithms.py b/src/pyfoma/algorithms.py
index e16c019..82df93b 100644
--- a/src/pyfoma/algorithms.py
+++ b/src/pyfoma/algorithms.py
@@ -737,6 +737,11 @@ def difference(fst1: 'FST', fst2: 'FST') -> 'FST':
                        oplus = lambda x,y: x, pathfollow = lambda x,y: x)
 
 
+def complement(fsm: 'FST') -> 'FST':
+    """Returns the complement of an FSM."""
+    return FST.re(".* - $X", {"X": fsm})
+
+
 @_harmonize_alphabet
 def product(fst1: 'FST', fst2: 'FST', finalf = any, oplus = min, pathfollow = lambda x,y: x|y) -> 'FST':
     """Generates the product FST from fst1, fst2. The helper functions by default
@@ -805,5 +810,6 @@ _algorithms_to_add: Dict[str, Callable] = {
     'union': union,
     'intersection': intersection,
     'difference': difference,
-    'product': product
+    'product': product,
+    'complement': complement,
 }
diff --git a/src/pyfoma/private/regexparse.py b/src/pyfoma/private/regexparse.py
index ce94d4c..527ba5d 100644
--- a/src/pyfoma/private/regexparse.py
+++ b/src/pyfoma/private/regexparse.py
@@ -30,7 +30,7 @@ class RegexParse:
                 'input': _builtins_input_lambda,
                 'output': _builtins_output_lambda}
     precedence = {"FUNC": 11, "COMMA": 1, "PARAM": 1, "COMPOSE": 3, "UNION": 5, "INTERSECTION": 5,
-                  "MINUS": 5, "CONCAT": 6, "STAR": 9, "PLUS": 9, "OPTIONAL": 9, "WEIGHT": 9,
+                  "MINUS": 5, "CONCAT": 6, "COMPLEMENT": 7, "STAR": 9, "PLUS": 9, "OPTIONAL": 9, "WEIGHT": 9,
                   "CP": 10, "CPOPTIONAL": 10, "RANGE": 9, "CONTEXT": 1, "PAIRUP": 2}
     operands = {"SYMBOL", "VARIABLE", "ANY", "EPSILON", "CHAR_CLASS"}
     operators = set(precedence.keys())
@@ -194,6 +194,8 @@ class RegexParse:
             elif op == 'CHAR_CLASS':
                 charranges, negated = self.character_class_parse(value)
                 _append(stack, FST.character_ranges(charranges, complement=negated))
+            elif op == 'COMPLEMENT':
+                _append(stack, _pop(stack).complement())
         if len(stack) != 1:  # If there's still stuff on the stack, that's a syntax error
             self._error_report(SyntaxError, \
                                "Something's happening here, and what it is ain't exactly clear...", 1, 0)
@@ -208,7 +210,7 @@ class RegexParse:
             (r", *", 'PARAM', r"\w+ *= *[+-]? *\w+", r""),  # Parameter
             (r"'", 'QUOTED', r"(\\[']|[^'])*", r"'"),  # Quoted sym
             (r"", 'SKIPWS', r"[ \t]+", r""),  # Skip ws
-            (r"", 'SHORTOP', r"(:\?|[|\-&*+()?:@,/_])", r""),  # main ops
+            (r"", 'SHORTOP', r"(:\?|[|\-&*+()?:@,/_~])", r""),  # main ops
             (r"\$\^", 'FUNC', r"\w+", r"(?=\s*\()"),  # Functions
             (r"\$", 'VARIABLE', r"\w+", r""),  # Variables
             (r"<", 'WEIGHT', r"[+-]?[0-9]*(\.[0-9]+)?", r">"),  # Weight


Test patch:
diff --git a/test_pyfoma.py b/test_pyfoma.py
index eab713a..60e3ccd 100644
--- a/test_pyfoma.py
+++ b/test_pyfoma.py
@@ -70,6 +70,23 @@ class TestFST(unittest.TestCase):
         f2 = FST.regex(r"'[NO\'UN]' '[VERB]'")
         self.assertEqual(f2.alphabet, {"[NO'UN]", "[VERB]"})
 
+    def test_complement(self):
+        f1 = FST.regex("~a")
+        self.assertEqual(0, len(list(f1.generate("a"))))
+        f1 = FST.regex("~(cat | dog)")
+        self.assertEqual(0, len(list(f1.generate("cat"))))
+        self.assertEqual(0, len(list(f1.generate("dog"))))
+        self.assertEqual(1, len(list(f1.generate("octopus"))))
+        f1 = FST.regex("~(cat | dog)s")
+        self.assertEqual(0, len(list(f1.generate("cats"))))
+        self.assertEqual(0, len(list(f1.generate("dogs"))))
+        self.assertEqual(1, len(list(f1.generate("octopus"))))
+        self.assertEqual(1, len(list(f1.generate("catdogs"))))
+        # * binds tighter than ~
+        f1 = FST.regex("~(cat | dog)*s")
+        self.assertEqual(0, len(list(f1.generate("catdogs"))))
+        self.assertEqual(0, len(list(f1.generate("catdogcats"))))
+
 
 if __name__ == "__main__":
     unittest.main()