Repository: mhulden/pyfoma

Issue:
Feature request: define multi-character symbols for regex compiler
Because pyfoma's regex language, unlike foma/xfst, separates characters by default, what might appear to be single input symbols in a regex frequently are not.  This is quite obviously true in the case where your data is in NFKD / NFD form, but much more perniciously so in NFKC / NFC, where, for instance, č is a single character, and so is ḥ, but x̌ is not.

This means that rewrite rules in particular may not do what you (or someone reading your code) might expect at first glance.

The defensive linguist will resort to putting single quotes around everything, which is probably a good idea, but this leads to rules that are, well, kind of ugly.  Also there are lots of situations where something is fairly obviously not a single character but it would be nice to treat it as one.

This could for instance be an extra argument to `FST.regex` and `FST.rlg`, e.g.:

```python
MULTICHARS = "kʷ kʷ̓ x̌".split()
rule = FST.re(some_regex, multichar_tokens=MULTICHARS)
```

I might make a PR to see if this is easily doable...

Discussion:
@mhulden: I think such an addition should be done as a preprocessing step before the parsing is done, by wrapping single quotes around the multichar tokens, and then doing regular parsing and compilation of the regex:

from `__init__` in regexparse.py:

```python3
self.expression = regularexpression
# call preprocessing here if multichar_tokens is declared
self.tokenized = self._insert_invisibles(self.tokenize())
self.parsed = self.parse()
self.compiled = self.compile()
```

That way the tokenizer and parser code could stay completely untouched.@dhdaines: done  in #31 

Solution patch:
diff --git a/docs/MorphologicalAnalyzerTutorial.ipynb b/docs/MorphologicalAnalyzerTutorial.ipynb
index 1ffa8d7..19dbfd7 100644
--- a/docs/MorphologicalAnalyzerTutorial.ipynb
+++ b/docs/MorphologicalAnalyzerTutorial.ipynb
@@ -164,6 +164,8 @@
    "source": [
     "Here, all the grammar rules are put into a dictionary, which is arbitrarily called `Grammar`. Each key in the dictionary is a left-hand-side of a rule, and the corresponding value is a tuple/iterable of possible right-hand-sides. If the input is different from the output (as on lines 9-13) the right-hand side nonterminals are represented as 2-tuples like `(\"'[N]' '[Sg]'\", \"\")`. The tag symbols `[N]` `[V]` etc. are quoted so that they become single atomic symbols in the resulting automaton (and not a sequence `[` `N` `]` or `[` `V` `]`). This is common practice when designing morphological transducers - tags are multicharacter symbols while actual word forms are concatenations of alphabetic symbols, e.g. `c` `a` `t`.\n",
     "\n",
+    "Note that you can also pass a set of multicharacter symbols to be automatically quoted when creating the transducer with the optional `multichar_symbols` argument to `FST.rlg`.\n",
+    "\n",
     "Now that we have the grammar's dictionary structure in place, we can compile it into a non-deterministic transducer with the `FST` method `rlg()`. The method takes two arguments: the dictionary and the designated start symbol (`S` in our case)."
    ]
   },
diff --git a/docs/RegularExpressionCompiler.ipynb b/docs/RegularExpressionCompiler.ipynb
index 75d1167..9a6d6fa 100644
--- a/docs/RegularExpressionCompiler.ipynb
+++ b/docs/RegularExpressionCompiler.ipynb
@@ -620,8 +620,8 @@
    "source": [
     "myfst1 = FST.re(\"cat\")\n",
     "myfst2 = FST.re(\"c a t\")                        # same as above\n",
-    "myfst3 = FST.re(\"\\+ \\* \\ \")                     # literalizing special characters\n",
-    "myfst4 = FST.re(\"'+' '*' ' '\")                  # same as above using single quotes\n",
+    "myfst3 = FST.re(r\"\\+ \\* \\ \")                    # literalizing special characters\n",
+    "myfst4 = FST.re(r\"'+' '*' ' ' '''\")             # same as above using single quotes (note literalized single quote)\n",
     "myfst5 = FST.re(\"(cat|dog|mouse)s?\")    \n",
     "myfst6 = FST.re(\"[A-Za-z0-9] - [aeiouAEIOU]\")   # all ASCII characters, except vowels (w/ set subtraction)\n",
     "myfst7 = FST.re(\"[^aeiou]\")                     # negated character class\n",
@@ -629,6 +629,41 @@
     "myfst9 = FST.re(\"cat<1.0>|dog<2.0>|mouse<3.0>\") # weights specified by <float>"
    ]
   },
+  {
+   "cell_type": "markdown",
+   "metadata": {},
+   "source": [
+    "## Multi-character symbols\n",
+    "\n",
+    "To treat a sequence of characters as a single symbol in a regular expression, enclose it in single quotes.  If you wish to have literal single quotes in a multi-character symbol, you can escape them with backslash (remember to use raw strings or to escape the backslash as noted above):"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": null,
+   "metadata": {},
+   "outputs": [],
+   "source": [
+    "myfst1 = FST.re(\"(cat'+Pl'):(cats)\")\n",
+    "myfst2 = FST.re(r\"(is'n\\'t'):(is ' ' not)\")"
+   ]
+  },
+  {
+   "cell_type": "markdown",
+   "metadata": {},
+   "source": [
+    "Similarly to the `Multichar_Symbols` section in a `lexc` file, you can also declare a set of multi-character symbols to be automatically quoted in a regular expression.  This may be useful when dealing with Unicode data where a glyph can possibly consist of many characters, or if you wish to treat digraphs as single symbols:"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": null,
+   "metadata": {},
+   "outputs": [],
+   "source": [
+    "myfst1 = FST.re(\"(perro):(dog)\", multichar_symbols=[\"rr\"])"
+   ]
+  },
   {
    "cell_type": "markdown",
    "metadata": {},
diff --git a/src/pyfoma/algorithms.py b/src/pyfoma/algorithms.py
index 82df93b..f38ae34 100644
--- a/src/pyfoma/algorithms.py
+++ b/src/pyfoma/algorithms.py
@@ -737,9 +737,9 @@ 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})
+def complement(fst: 'FST') -> 'FST':
+    """Returns the complement of an FST."""
+    return FST.re(".* - $X", {"X": fst})
 
 
 @_harmonize_alphabet
diff --git a/src/pyfoma/fst.py b/src/pyfoma/fst.py
index 51cc38c..4aaa371 100644
--- a/src/pyfoma/fst.py
+++ b/src/pyfoma/fst.py
@@ -4,15 +4,35 @@
 
 import heapq, operator, itertools, re as pyre, functools
 from collections import deque, defaultdict
-from typing import Callable, Dict, Any
+from typing import Callable, Dict, Any, Iterable
 from pyfoma.flag import FlagStringFilter, FlagOp
 import subprocess
 import pickle
 
+
 def re(*args, **kwargs):
     return FST.re(*args, **kwargs)
 
 
+def _multichar_matcher(multichar_symbols: Iterable[str]) -> pyre.Pattern:
+    """Create matcher for unquoted multichar symbols in lexicons and
+    regular expressions."""
+    return pyre.compile(
+        r"('(?:\\'|[^'])*')|("
+        + "|".join(pyre.escape(sym)
+                   for sym in multichar_symbols
+                   if len(sym) > 1)
+        + r")")
+
+
+def _multichar_replacer(matchobj: pyre.Match):
+    """Replace character or quoted string with quoted thing."""
+    quoted, sym = matchobj.groups()
+    if quoted is not None:
+        return quoted
+    return "'" + sym.replace("'", r"\'") + "'"
+
+
 # TODO: Move all algorithm functions to the algorithms module
 class FST:
 
@@ -82,7 +102,7 @@ class FST:
         return newfst
 
     @classmethod
-    def regex(cls, regularexpression, defined = {}, functions = set()):
+    def regex(cls, regularexpression, defined = {}, functions = set(), multichar_symbols=None):
         """Compile a regular expression and return the resulting FST.
            Keyword arguments:
            defined -- a dictionary of defined FSTs that the compiler can access whenever
@@ -91,31 +111,40 @@ class FST:
                        is referenced in the regex, e.g. $^myfunc(...)
         """
         import pyfoma.private.regexparse as regexparse
-
+        if multichar_symbols is not None:
+            escaper = _multichar_matcher(multichar_symbols)
+            regularexpression = escaper.sub(_multichar_replacer, regularexpression)
         myregex = regexparse.RegexParse(regularexpression, defined, functions)
         return myregex.compiled
 
     re = regex
 
-
     @classmethod
-    def from_strings(cls, strings):
+    def from_strings(cls, strings, multichar_symbols=None):
         """Create an automaton that accepts words in the iterable 'strings'."""
-        Grammar = {"Start":((w, "#") for w in strings)}
-        return FST.rlg(Grammar, "Start").determinize_as_dfa().minimize().label_states_topology()
+        Grammar = {"Start": ((w, "#") for w in strings)}
+        lex = FST.rlg(Grammar, "Start", multichar_symbols=multichar_symbols)
+        return lex.determinize_as_dfa().minimize().label_states_topology()
 
     @classmethod
-    def rlg(cls, grammar, startsymbol):
+    def rlg(cls, grammar, startsymbol, multichar_symbols=None):
         """Compile a (weighted) right-linear grammar into an FST, similarly to lexc."""
+        escaper = None
+        if multichar_symbols is not None:
+            escaper = _multichar_matcher(multichar_symbols)
         def _rlg_tokenize(w):
             if w == '':
                 return ['']
+            if escaper is not None:
+                w = escaper.sub(_multichar_replacer, w)
             tokens = []
-            tok_re = r"'(?P<multi>([']|[^']*))'|\\(?P<esc>(.))|(?P<single>(.))"
+            tok_re = r"'(?P<multi>'|(?:\\'|[^'])*)'|\\(?P<esc>(.))|(?P<single>(.))"
             for mo in pyre.finditer(tok_re, w):
                 token = mo.group(mo.lastgroup)
                 if token == " " and mo.lastgroup == 'single':
                     token = ""  # normal spaces for alignment, escaped for actual
+                elif mo.lastgroup == "multi":
+                    token = token.replace(r"\'", "'")
                 tokens.append(token)
             return tokens
 
diff --git a/src/pyfoma/private/regexparse.py b/src/pyfoma/private/regexparse.py
index 527ba5d..3d126a7 100644
--- a/src/pyfoma/private/regexparse.py
+++ b/src/pyfoma/private/regexparse.py
@@ -208,7 +208,7 @@ class RegexParse:
         token_regexes = [
             (r"\\", 'ESCAPED', r".", r""),  # Esc'd sym
             (r", *", 'PARAM', r"\w+ *= *[+-]? *\w+", r""),  # Parameter
-            (r"'", 'QUOTED', r"(\\[']|[^'])*", r"'"),  # Quoted sym
+            (r"'", 'QUOTED', r"'|(\\'|[^'])*", r"'"),  # Quoted sym
             (r"", 'SKIPWS', r"[ \t]+", r""),  # Skip ws
             (r"", 'SHORTOP', r"(:\?|[|\-&*+()?:@,/_~])", r""),  # main ops
             (r"\$\^", 'FUNC', r"\w+", r"(?=\s*\()"),  # Functions


Test patch:
diff --git a/test_pyfoma.py b/test_pyfoma.py
index 60e3ccd..e6ccae0 100644
--- a/test_pyfoma.py
+++ b/test_pyfoma.py
@@ -1,4 +1,5 @@
 import unittest
+from pyfoma import algorithms
 from pyfoma.fst import FST
 
 class TestFST(unittest.TestCase):
@@ -71,12 +72,14 @@ class TestFST(unittest.TestCase):
         self.assertEqual(f2.alphabet, {"[NO'UN]", "[VERB]"})
 
     def test_complement(self):
+        """Test the complement operator / method"""
         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"))))
+        # ~ binds tighter than concatenation
         f1 = FST.regex("~(cat | dog)s")
         self.assertEqual(0, len(list(f1.generate("cats"))))
         self.assertEqual(0, len(list(f1.generate("dogs"))))
@@ -86,6 +89,116 @@ class TestFST(unittest.TestCase):
         f1 = FST.regex("~(cat | dog)*s")
         self.assertEqual(0, len(list(f1.generate("catdogs"))))
         self.assertEqual(0, len(list(f1.generate("catdogcats"))))
+        # Verify that the new algorithm/method works too
+        f1 = FST.regex("octopus")
+        self.assertEqual(0, len(list(f1.generate("dog"))))
+        self.assertEqual(1, len(list(f1.generate("octopus"))))
+        # Non-mutating
+        f2 = algorithms.complement(f1)
+        self.assertEqual(1, len(list(f2.generate("dog"))))
+        self.assertEqual(0, len(list(f2.generate("octopus"))))
+        # Mutating
+        f1.complement()
+        self.assertEqual(1, len(list(f1.generate("dog"))))
+        self.assertEqual(0, len(list(f1.generate("octopus"))))
+        f1.complement()
+        self.assertEqual(0, len(list(f1.generate("dog"))))
+        self.assertEqual(1, len(list(f1.generate("octopus"))))
+
+    def test_methods(self):
+        """Verify that generated methods work as expected"""
+        f1 = FST.regex("(cat):(dog)")
+        f2 = FST.regex("(dog):(octopus)")
+        f3 = algorithms.compose(f1, f2)
+        f4 = algorithms.inverted(f1)
+        self.assertEqual("dog", next(f1.generate("cat")))
+        self.assertEqual("octopus", next(f2.generate("dog")))
+        self.assertEqual("octopus", next(f3.generate("cat")))
+        self.assertEqual("cat", next(f4.generate("dog")))
+        # This is mutating (maybe not what you expect?)
+        f1.compose(f2)
+        self.assertEqual("octopus", next(f1.generate("cat")))
+        # So is this!
+        f1.invert()
+        self.assertEqual("cat", next(f1.generate("octopus")))
+
+
+class TestSymbols(unittest.TestCase):
+    MULTICHAR_SYMBOLS = "u: ch ll x̌ʷ".split()
+
+    def test_rlg(self):
+        """Verify multi-character symbols in lexicons (lexc style)"""
+        # Hopefully the third one is not an actual word for anyone
+        words = ["hecho", "llama", "xu:x̌ʷ"]
+        lex = FST.rlg({
+            "Root": [(word, "#") for word in words]
+        }, "Root", multichar_symbols=self.MULTICHAR_SYMBOLS)
+        for sym in self.MULTICHAR_SYMBOLS:
+            self.assertTrue(sym in lex.alphabet)
+        for word in words:
+            self.assertEqual(word, next(lex.generate(word)))
+
+    def test_from_strings(self):
+        """Verify multi-character symbols in from_strings"""
+        words = ["hecho", "llama", "xu:x̌ʷ"]
+        lex = FST.from_strings(words, multichar_symbols=self.MULTICHAR_SYMBOLS)
+        for sym in self.MULTICHAR_SYMBOLS:
+            self.assertTrue(sym in lex.alphabet)
+        for word in words:
+            self.assertEqual(word, next(lex.generate(word)))
+
+    def test_quotes(self):
+        """Make sure already-quoted things stay quoted correctly and we
+        can pathologically escape quotes everywhere"""
+        words = ["'HACKEM'MUCHE", r"FOOBIE'BL\'ETCH'", r"'''"]
+        lex = FST.from_strings(words, multichar_symbols=["CH", "BL"])
+        self.assertTrue("HACKEM" in lex.alphabet)
+        self.assertTrue("BL'ETCH" in lex.alphabet)
+        self.assertTrue("'" in lex.alphabet)
+        self.assertTrue("CH" in lex.alphabet)
+        # Ensure that we don't introduce multichar_symbols inside
+        # already quoted symbols
+        self.assertTrue("BL" not in lex.alphabet)
+        self.assertEqual("HACKEMMUCHE", next(lex.generate("HACKEMMUCHE")))
+        self.assertEqual("FOOBIEBL'ETCH", next(lex.generate("FOOBIEBL'ETCH")))
+        # Escaped quotes in explicit multichar symbol
+        rule = FST.regex(r"$^rewrite('n\'t':(' 'not) / is _)")
+        self.assertEqual("is not", next(rule.generate("isn't")))
+        # Escaped quotes in multichar_symbols
+        rule = FST.regex(r"$^rewrite(n't:(' 'not) / is _)",
+                         multichar_symbols=["n't"])
+        self.assertEqual("is not", next(rule.generate("isn't")))
+        # Escaped quotes in explicit multichar symbol not destroyed by
+        # multichar_symbols escaping
+        rule = FST.regex(r"$^rewrite('n\'t':(' 'not) / is _)",
+                         multichar_symbols=["n't"])
+        self.assertEqual("is not", next(rule.generate("isn't")))
+
+    def test_single_quotes(self):
+        """Test that literal single quotes work everywhere, in a
+        multitude of different ways."""
+        lex = FST.from_strings(["foo'''bar"])
+        self.assertTrue("'" in lex.alphabet)
+        self.assertEqual("foo'bar", next(lex.generate("foo'bar")))
+        # such escaping, so wow
+        f1 = FST.regex("foo ''' bar")
+        self.assertTrue("'" in f1.alphabet)
+        self.assertEqual("foo'bar", next(f1.generate("foo'bar")))
+        f2 = FST.regex(r"foo \' bar")
+        self.assertTrue("'" in f2.alphabet)
+        self.assertEqual("foo'bar", next(f2.generate("foo'bar")))
+        f3 = FST.regex(r"foo '\'' bar")
+        self.assertTrue("'" in f3.alphabet)
+        self.assertEqual("foo'bar", next(f3.generate("foo'bar")))
+
+    def test_rewrite(self):
+        """Verify multi-character symbols in rewrite rules"""
+        # Yes, you can put forbidden characters in symbols now (just
+        # because you can doesn't necessarily mean you should)
+        rule = FST.regex("$^rewrite(x̌ʷ:x / u: _ #)",
+                         multichar_symbols=self.MULTICHAR_SYMBOLS)
+        self.assertEqual("xu:x", next(rule.generate("xu:x̌ʷ")))
+        self.assertEqual("xux̌ʷ", next(rule.generate("xux̌ʷ")))
 
 
 if __name__ == "__main__":