Commits

Martin Vejnár committed a420a41

A bit of documentation.

  • Participants
  • Parent commits 7b19570

Comments (0)

Files changed (8)

File dfa.py

-class FaState:
-    def __init__(self):
-        self.inedges = set()
-        self.outedges = set()
-
-class FaEdge:
-    def __init__(self, f, t, label=None):
-        self.source = f
-        self.target = t
-        self.label = label
-
-class Fa:
-    def __init__(self):
-        self.states = []
-        self.edges = set()
-        self.initial = set()
-        self.accept_labels = {}
-
-    def __str__(self):
-        res = []
-        state_indexes = dict([(state, i) for i, state in enumerate(self.states)])
-        for i, state in enumerate(self.states):
-            accept_label = self.accept_labels.get(state)
-            res.append('%s%d' % ('%r ' % accept_label if accept_label is not None else ' ', i))
-            if state in self.initial:
-                res.append('initial')
-            for edge in state.outedges:
-                res.append('    %d %r' % (
-                    state_indexes[edge.target],
-                    edge.label if edge.label is not None else 'epsilon'))
-        return '\n'.join(res)
-
-    def add_fa(self, fa):
-        self.states.extend(fa.states)
-        self.edges.update(fa.edges)
-        self.accept_labels.update(fa.accept_labels)
-
-    def new_edge(self, s1, s2, label=None):
-        edge = FaEdge(s1, s2, label)
-        s1.outedges.add(edge)
-        s2.inedges.add(edge)
-        self.edges.add(edge)
-        return edge
-
-    def new_state(self, templ=None):
-        new_state = FaState()
-        if templ:
-            old_edges = templ.inedges | templ.outedges
-            for edge in old_edges:
-                source = edge.source if edge.source != templ else new_state
-                target = edge.target if edge.target != templ else new_state
-                self.new_edge(source, target, edge.label)
-            if templ in self.accept_labels:
-                self.accept_labels[new_state] = self.accept_labels[templ]
-        self.states.append(new_state)
-        return new_state
-
-    def remove_edge(self, edge):
-        self.edges.remove(edge)
-        edge.source.outedges.remove(edge)
-        edge.target.inedges.remove(edge)
-
-    def get_edges(self):
-        return set(self.edges)
-
-def make_dfa_from_literal(lit, accept_label):
-    fa = Fa()
-    init = fa.new_state()
-    fa.initial = set([init])
-    for ch in lit:
-        s = fa.new_state()
-        fa.new_edge(init, s, set([ch]))
-        init = s
-    fa.accept_labels = { init: accept_label }
-    return fa
-
-def convert_enfa_to_dfa(enfa):
-    def _epsilon_closure(states):
-        q = list(states)
-        res = set(q)
-        while q:
-            state = q.pop()
-            for edge in state.outedges:
-                if edge.label is not None:
-                    continue
-                if edge.target in res:
-                    continue
-                q.append(edge.target)
-                res.add(edge.target)
-        return res
-
-    dfa = Fa()
-    state_map = {}
-    inv_state_map = {}
-
-    def _get_state(states):
-        states = frozenset(states)
-        if states not in state_map:
-            res = dfa.new_state()
-            state_map[states] = res
-            inv_state_map[res] = states
-        else:
-            res = state_map[states]
-        return res
-
-    initial = _get_state(_epsilon_closure(enfa.initial))
-    q = [initial]
-    dfa.initial = set(q)
-    processed = set(q)
-    while q:
-        current = q.pop()
-        state_set = inv_state_map[current]
-        edges = {}
-        for state in state_set:
-            for edge in state.outedges:
-                if edge.label is not None:
-                    edges.setdefault(edge.target, set()).update(edge.label)
-        while edges:
-            it = edges.iteritems()
-            target, s = it.next()
-            targets = set([target])
-            current_set = set(s)
-            for target, next_set in it:
-                s = current_set & next_set
-                if s:
-                    current_set = s
-                    targets.add(target)
-            dfa_target = _get_state(_epsilon_closure(targets))
-            dfa.new_edge(current, dfa_target, current_set)
-            if dfa_target not in processed:
-                processed.add(dfa_target)
-                q.append(dfa_target)
-
-            for target in edges.keys():
-                reduced = edges[target] - current_set
-                if not reduced:
-                    del edges[target]
-                else:
-                    edges[target] = reduced
-    for state in dfa.states:
-        enfa_states = inv_state_map[state]
-        for enfa_state in enfa_states:
-            if enfa_state not in enfa.accept_labels:
-                continue
-            enfa_label = enfa.accept_labels[enfa_state]
-            if state not in dfa.accept_labels:
-                dfa.accept_labels[state] = enfa_label
-            else:
-                dfa.accept_labels[state] = min(dfa.accept_labels[state], enfa_label)
-    return dfa
-
-def minimize_enfa(fa):
-    fa = convert_enfa_to_dfa(fa)
-
-    # initialize the partition by splitting the state according to the accept label
-    no_accept = set()
-    accept_label_map = {}
-    for state in fa.states:
-        if state not in fa.accept_labels:
-            no_accept.add(state)
-        else:
-            acc_label = fa.accept_labels[state]
-            accept_label_map.setdefault(acc_label, set()).add(state)
-
-    partition = set([frozenset(no_accept)])
-    for states in accept_label_map.itervalues():
-        partition.add(frozenset(states))
-
-    def _get_maximum_charsets(item_charset_map):
-        item_charset_map = dict(item_charset_map)
-        while item_charset_map:
-            it = item_charset_map.iteritems()
-            item, charset = it.next()
-            items = set([item])
-            current_charset = set(charset)
-            for item, charset in it:
-                charset = current_charset & charset
-                if charset:
-                    current_charset = charset
-                    items.add(item)
-
-            yield items, current_charset
-
-            for item in item_charset_map.keys():
-                reduced = item_charset_map[item] - current_charset
-                if not reduced:
-                    del item_charset_map[item]
-                else:
-                    item_charset_map[item] = reduced
-
-    def _create_partition_map(partition):
-        partition_map = {}
-        for state_class in partition:
-            for state in state_class:
-                partition_map[state] = state_class
-        return partition_map
-
-    # iterate and refine
-    while True:
-        partition_map = _create_partition_map(partition)
-
-        new_partition = set()
-        for state_class in partition:
-            sibling_map = {}
-            for state in state_class:
-                sibling_map[state] = set(state_class)
-
-            edge_map = {}
-            for state in state_class:
-                for edge in state.outedges:
-                    edge_map[edge] = set(edge.label)
-
-            for edges, charset in _get_maximum_charsets(edge_map):
-                target_map = {}
-                for edge in edges:
-                    target_map.setdefault(partition_map[edge.target], set()).add(edge.source)
-                for part, source_set in target_map.iteritems():
-                    for source, siblings in sibling_map.iteritems():
-                        if source in source_set:
-                            siblings &= source_set
-                        else:
-                            siblings -= source_set
-
-            for sibling_set in sibling_map.itervalues():
-                new_partition.add(frozenset(sibling_set))
-
-        if partition == new_partition:
-            break
-        partition = new_partition
-
-    # partition is refined
-    partition_map = _create_partition_map(partition)
-
-    new_fa = Fa()
-
-    new_state_map = {}
-    for state_class in partition:
-        new_state = new_fa.new_state()
-        new_state_map[state_class] = new_state
-
-    for state_class, source in new_state_map.iteritems():
-        edge_map = {}
-        for state in state_class:
-            for edge in state.outedges:
-                edge_map[edge] = set(edge.label)
-
-        target_map = {}
-        for edges, charset in _get_maximum_charsets(edge_map):
-            target = partition_map[next(iter(edges)).target]
-            assert all((partition_map[edge.target] == target for edge in edges))
-            target_map.setdefault(new_state_map[target], set()).update(charset)
-
-        for target, charset in target_map.iteritems():
-            new_fa.new_edge(source, target, charset)
-
-    new_fa.initial = set([new_state_map[partition_map[next(iter(fa.initial))]]])
-    for state, accept_label in fa.accept_labels.iteritems():
-        new_fa.accept_labels[new_state_map[partition_map[state]]] = accept_label
-    return new_fa

File ebnf_grammar.py

 >>> grammar_in_ebnf = 'list = { item }; item = "i";'
 >>> for rule in ebnf_parse(grammar_in_ebnf):
 ...     print rule
-list ::= @1
-@1 ::= <empty>
-@1 ::= @1 @2
-@2 ::= item
-item ::= i
+'list' = '@1';
+'@1' = ;
+'@1' = '@1', '@2';
+'@2' = 'item';
+'item' = 'i';
 
 The helper function 'parse_from_ebnf' uses 'ebnf_parse'
 to generate the list of Rule objects, constructs a grammar, a parser
+"""
+Finite automaton engine. Contains classes to represent FAs
+and algorithms to convert between DFAs, NFAs and regexes.
+
+>>> nature_fa = make_dfa_from_literal('nature')
+>>> endnature_fa = make_dfa_from_literal('endnature')
+>>> union = union_fa([nature_fa, endnature_fa])
+>>> fa = minimize_enfa(union)
+>>> len(fa.states)
+10
+"""
+
+class State:
+    """
+    A state of a finite automaton. Contains references
+    to the sets of incoming and outgoing edges.
+    """
+    def __init__(self):
+        self.inedges = set()
+        self.outedges = set()
+
+class Edge:
+    """
+    An edge of a finite automaton. Leads between two FA states.
+    Optionally, the edge can be labeled.
+    """
+    def __init__(self, f, t, label=None):
+        self.source = f
+        self.target = t
+        self.label = label
+
+class Fa:
+    """
+    A finite automaton consists of a set of states and a set of edges
+    that interconnect them.
+    
+    Edges can be labeled. The labels are in now way interpreted,
+    some algorithms, however, expect that the labels can be combined
+    using the standard set operators &, | and -. Furthermore,
+    epsilon edges are supposed to be labeled with None.
+
+    The FA can have zero or more initial states and zero or more accepting
+    states. The accepting states are labeled -- as with edge labels,
+    some algorithms expect accept labels to behave like sets. Accepting
+    states are stored in a dict that maps them to the corresponding label.
+    """
+    def __init__(self):
+        """
+        Initialized the FA to contain no states (and thus no edges).
+        """
+        self.states = []
+        self.edges = set()
+        self.initial = set()
+        self.accept_labels = {}
+
+    def __str__(self):
+        res = []
+        state_indexes = dict([(state, i) for i, state in enumerate(self.states)])
+        for i, state in enumerate(self.states):
+            accept_label = self.accept_labels.get(state)
+            res.append('%s%d' % ('%r ' % accept_label if accept_label is not None else ' ', i))
+            if state in self.initial:
+                res.append('initial')
+            for edge in state.outedges:
+                res.append('    %d %r' % (
+                    state_indexes[edge.target],
+                    edge.label if edge.label is not None else 'epsilon'))
+        return '\n'.join(res)
+
+    def add_fa(self, fa):
+        """
+        Adds the states and edges of another FA to this FA. The remote
+        FA should be thrown away right after the joining.
+        """
+        self.states.extend(fa.states)
+        self.edges.update(fa.edges)
+        self.accept_labels.update(fa.accept_labels)
+
+    def new_edge(self, s1, s2, label=None):
+        """
+        Joins two states with a new edge and applies an optional label
+        to it. Returns the new edge.
+        """
+        edge = Edge(s1, s2, label)
+        s1.outedges.add(edge)
+        s2.inedges.add(edge)
+        self.edges.add(edge)
+        return edge
+
+    def new_state(self, templ=None):
+        """
+        Creates a new state. If a template state is provided,
+        the new state is a duplicate of the template.
+        Returns the new state.
+        """
+        new_state = State()
+        if templ:
+            assert templ in self.states
+            old_edges = templ.inedges | templ.outedges
+            for edge in old_edges:
+                source = edge.source if edge.source != templ else new_state
+                target = edge.target if edge.target != templ else new_state
+                self.new_edge(source, target, edge.label)
+            if templ in self.accept_labels:
+                self.accept_labels[new_state] = self.accept_labels[templ]
+        self.states.append(new_state)
+        return new_state
+
+    def remove_edge(self, edge):
+        """
+        Removes an edge from the FA.
+        """
+        self.edges.remove(edge)
+        edge.source.outedges.remove(edge)
+        edge.target.inedges.remove(edge)
+
+    def get_edges(self):
+        """
+        Returns a copy of the edge set.
+        """
+        return set(self.edges)
+
+def make_dfa_from_literal(lit, accept_label=True):
+    """
+    Create a DFA from a sequence. The FA will have `n+1` states,
+    where `n` is the length of the sequence. The states will be connected
+    to form a chain that begins with the only inital state and ends
+    with an accepting state labeled by the provided label.
+    """
+    fa = Fa()
+    init = fa.new_state()
+    fa.initial = set([init])
+    for ch in lit:
+        s = fa.new_state()
+        fa.new_edge(init, s, set([ch]))
+        init = s
+    fa.accept_labels = { init: accept_label }
+    return fa
+
+def convert_enfa_to_dfa(enfa, accept_combine=min):
+    """
+    Converts an NFA with epsilon edges (labeled with None) to a DFA.
+    The function expects edge labels that are not None to be sets
+    and accepting state labels to be combinable using the accept_combine
+    function passed as a parameter.
+    """
+    def _epsilon_closure(states):
+        q = list(states)
+        res = set(q)
+        while q:
+            state = q.pop()
+            for edge in state.outedges:
+                if edge.label is not None:
+                    continue
+                if edge.target in res:
+                    continue
+                q.append(edge.target)
+                res.add(edge.target)
+        return res
+
+    dfa = Fa()
+    state_map = {}
+    inv_state_map = {}
+
+    def _get_state(states):
+        states = frozenset(states)
+        if states not in state_map:
+            res = dfa.new_state()
+            state_map[states] = res
+            inv_state_map[res] = states
+        else:
+            res = state_map[states]
+        return res
+
+    initial = _get_state(_epsilon_closure(enfa.initial))
+    q = [initial]
+    dfa.initial = set(q)
+    processed = set(q)
+    while q:
+        current = q.pop()
+        state_set = inv_state_map[current]
+        edges = {}
+        for state in state_set:
+            for edge in state.outedges:
+                if edge.label is not None:
+                    edges.setdefault(edge.target, set()).update(edge.label)
+        while edges:
+            it = edges.iteritems()
+            target, s = next(it)
+            targets = set([target])
+            current_set = set(s)
+            for target, next_set in it:
+                s = current_set & next_set
+                if s:
+                    current_set = s
+                    targets.add(target)
+            dfa_target = _get_state(_epsilon_closure(targets))
+            dfa.new_edge(current, dfa_target, current_set)
+            if dfa_target not in processed:
+                processed.add(dfa_target)
+                q.append(dfa_target)
+
+            for target in edges.keys():
+                reduced = edges[target] - current_set
+                if not reduced:
+                    del edges[target]
+                else:
+                    edges[target] = reduced
+    for state in dfa.states:
+        enfa_states = inv_state_map[state]
+        for enfa_state in enfa_states:
+            if enfa_state not in enfa.accept_labels:
+                continue
+            enfa_label = enfa.accept_labels[enfa_state]
+            if state not in dfa.accept_labels:
+                dfa.accept_labels[state] = enfa_label
+            else:
+                dfa.accept_labels[state] = accept_combine(dfa.accept_labels[state], enfa_label)
+    return dfa
+
+def minimize_enfa(fa, accept_combine=min):
+    """
+    Converts an NFA with epsilon edges to a minimal DFA. The requirements
+    on the edge and accept labels are the same as with
+    the convert_enfa_to_dfa function.
+    """
+    fa = convert_enfa_to_dfa(fa, accept_combine)
+
+    # initialize the partition by splitting the state according to the accept label
+    no_accept = set()
+    accept_label_map = {}
+    for state in fa.states:
+        if state not in fa.accept_labels:
+            no_accept.add(state)
+        else:
+            acc_label = fa.accept_labels[state]
+            accept_label_map.setdefault(acc_label, set()).add(state)
+
+    partition = set([frozenset(no_accept)])
+    for states in accept_label_map.itervalues():
+        partition.add(frozenset(states))
+
+    def _get_maximum_charsets(item_charset_map):
+        item_charset_map = dict(item_charset_map)
+        while item_charset_map:
+            it = item_charset_map.iteritems()
+            item, charset = it.next()
+            items = set([item])
+            current_charset = set(charset)
+            for item, charset in it:
+                charset = current_charset & charset
+                if charset:
+                    current_charset = charset
+                    items.add(item)
+
+            yield items, current_charset
+
+            for item in item_charset_map.keys():
+                reduced = item_charset_map[item] - current_charset
+                if not reduced:
+                    del item_charset_map[item]
+                else:
+                    item_charset_map[item] = reduced
+
+    def _create_partition_map(partition):
+        partition_map = {}
+        for state_class in partition:
+            for state in state_class:
+                partition_map[state] = state_class
+        return partition_map
+
+    # iterate and refine
+    while True:
+        partition_map = _create_partition_map(partition)
+
+        new_partition = set()
+        for state_class in partition:
+            sibling_map = {}
+            for state in state_class:
+                sibling_map[state] = set(state_class)
+
+            edge_map = {}
+            for state in state_class:
+                for edge in state.outedges:
+                    edge_map[edge] = set(edge.label)
+
+            for edges, charset in _get_maximum_charsets(edge_map):
+                target_map = {}
+                for edge in edges:
+                    target_map.setdefault(partition_map[edge.target], set()).add(edge.source)
+                for part, source_set in target_map.iteritems():
+                    for source, siblings in sibling_map.iteritems():
+                        if source in source_set:
+                            siblings &= source_set
+                        else:
+                            siblings -= source_set
+
+            for sibling_set in sibling_map.itervalues():
+                new_partition.add(frozenset(sibling_set))
+
+        if partition == new_partition:
+            break
+        partition = new_partition
+
+    # partition is refined
+    partition_map = _create_partition_map(partition)
+
+    new_fa = Fa()
+
+    new_state_map = {}
+    for state_class in partition:
+        new_state = new_fa.new_state()
+        new_state_map[state_class] = new_state
+
+    for state_class, source in new_state_map.iteritems():
+        edge_map = {}
+        for state in state_class:
+            for edge in state.outedges:
+                edge_map[edge] = set(edge.label)
+
+        target_map = {}
+        for edges, charset in _get_maximum_charsets(edge_map):
+            target = partition_map[next(iter(edges)).target]
+            assert all((partition_map[edge.target] == target for edge in edges))
+            target_map.setdefault(new_state_map[target], set()).update(charset)
+
+        for target, charset in target_map.iteritems():
+            new_fa.new_edge(source, target, charset)
+
+    new_fa.initial = set([new_state_map[partition_map[next(iter(fa.initial))]]])
+    for state, accept_label in fa.accept_labels.iteritems():
+        new_fa.accept_labels[new_state_map[partition_map[state]]] = accept_label
+    return new_fa
+
+def union_fa(fas):
+    """
+    Builds a FA that accepts a union of languages of the provided FAs.
+    """
+    final_fa = Fa()
+    final_init = final_fa.new_state()
+    final_fa.initial = set([final_init])
+    for fa in fas:
+        final_fa.add_fa(fa)
+        for init in fa.initial:
+            final_fa.new_edge(final_init, init)
+    return final_fa
+
+if __name__ == '__main__':
+    import doctest
+    doctest.testmod()
 from lime_grammar import LexDiscard, LexRegex
-from dfa import make_dfa_from_literal
+from fa import make_dfa_from_literal
 
 def _make_lexer(g, dfa):
     labels = []
     from lime_grammar import parse_lime_grammar
     g = parse_lime_grammar(test)
 
-#    from lrparser import Parser
-#    p = Parser(g, keep_states=True)
-
-#    from regex_parser import make_multi_dfa, minimize_enfa, regex_parser, make_enfa_from_regex
-
-#    fas = []
-#    for i, lex_rule in enumerate(g.lex_rules):
-#        (lhs, lhs_name), (rhs, rhs_name), action = lex_rule
-#        if isinstance(rhs, LexRegex):
-#            g2 = regex_parser(rhs.regex)
-#            fa = make_enfa_from_regex(g2, i)
-#        else:
-#            fa = make_dfa_from_literal(rhs.literal, i)
-#        fas.append(fa)
-#    dfa = make_multi_dfa(fas)
-#    dfa = minimize_enfa(dfa)
-#    print dfa
-
     from lime_parser import make_lime_parser
     p = make_lime_parser(g)
     print lime_cpp(p)
 
 #    import doctest
 #    doctest.testmod()
-#    print _make_lexer(g, dfa)

File lime_grammar.py

     from lrparser import extract_second
     return p.parse(lime_lexer(input), extract_value=extract_second)
 
+def make_lime_parser(g):
+    from lrparser import Parser
+    p = Parser(g)
+
+    from fa import make_dfa_from_literal, union_fa, minimize_enfa
+    from regex_parser import (regex_parser, make_enfa_from_regex)
+    from lime_grammar import LexRegex
+
+    fas = []
+    for i, lex_rule in enumerate(g.lex_rules):
+        (lhs, lhs_name), (rhs, rhs_name), action = lex_rule
+        if isinstance(rhs, LexRegex):
+            g2 = regex_parser(rhs.regex)
+            fa = make_enfa_from_regex(g2, i)
+        else:
+            fa = make_dfa_from_literal(rhs.literal, i)
+        fas.append(fa)
+    enfa = union_fa(fas)
+    dfa = minimize_enfa(enfa)
+    p.lexer = dfa
+    return p
+
 if __name__ == "__main__":
     test = """
 ws :: discard

File lime_parser.py

-def make_lime_parser(g):
-    from lrparser import Parser
-    p = Parser(g)
-
-    from dfa import make_dfa_from_literal
-    from regex_parser import (make_multi_dfa, minimize_enfa,
-        regex_parser, make_enfa_from_regex)
-    from lime_grammar import LexRegex
-
-    fas = []
-    for i, lex_rule in enumerate(g.lex_rules):
-        (lhs, lhs_name), (rhs, rhs_name), action = lex_rule
-        if isinstance(rhs, LexRegex):
-            g2 = regex_parser(rhs.regex)
-            fa = make_enfa_from_regex(g2, i)
-        else:
-            fa = make_dfa_from_literal(rhs.literal, i)
-        fas.append(fa)
-    dfa = make_multi_dfa(fas)
-    dfa = minimize_enfa(dfa)
-    p.lexer = dfa
-    return p
+"""
+This is the main script that accepts the grammar file and generates
+the C++ header file containing the parser and potentially the lexer.
+"""
+
 def _main(options, fname):
     import os.path
     if not options.output:

File regex_parser.py

 from lrparser import Parser
 from docparser import parser_LR, action, matcher
 from simple_lexer import simple_lexer
-from dfa import *
+from fa import State, Edge, Fa, union_fa
 
 class _Lit:
-    def __init__(self, charset):
+    def __init__(self, charset, inv=False):
         self.charset = set(charset)
-
-    def __str__(self):
-        return str(sorted(self.charset))
+        self.inv = inv
 
     def __repr__(self):
-        return repr(sorted(self.charset))
+        if inv:
+            return '_Lit(%r, inv=True)' % (sorted(self.charset),)
+        else:
+            return '_Lit(%r)' % (sorted(self.charset),)
 
 class _Empty:
     pass
         return _Lit(charset)
 
     @action
+    def range_inv(self, range_elems):
+        """
+        literal = _lbracket, _circumflex, { range_elem }, _rbracket;
+        """
+        charset = set()
+        for elem in range_elems:
+            charset.update(elem.charset)
+        return _Lit(charset, inv=True)
+
+    @action
     def escaped(self, esc):
         """
         literal = esc;
             yield ('pipe', ch)
         elif ch == '?':
             yield ('q', ch)
+        elif ch == '^':
+            yield ('circumflex', ch)
         else:
             yield ('ch', ch)
     if esc:
         yield ('ch', ch)
 
+class invertible_set:
+    def __init__(self, iterable, inv=False):
+        self.base = set(iterable)
+        self.inv = inv
+
+    def __repr__(self):
+        if self.inv:
+            return 'invertible_set(%r, inv=True)' % sorted(self.base)
+        else:
+            return 'invertible_set(%r)' % sorted(self.base)
+
 def make_enfa_from_regex(regex, accept_label):
     fa = Fa()
     initial = fa.new_state()
 
     return fa
 
-def make_multi_dfa(fas):
-    final_fa = Fa()
-    final_init = final_fa.new_state()
-    final_fa.initial = set([final_init])
-    for fa in fas:
-        final_fa.add_fa(fa)
-        final_fa.new_edge(final_init, next(iter(fa.initial)))
-    return final_fa
-
 def regex_parser(input):
     p = _RegexParser()
     from lrparser import extract_second
     return p.parse(_regex_lexer(input), extract_value=extract_second)
-
-if __name__ == "__main__":
-    fa = make_multi_dfa([
-        (r'endmodule', 0),
-        (r'module', 1),
-        (r'discipline', 2),
-        (r'enddiscipline', 3),
-        (r'nature', 4),
-        (r'endnature', 5)
-        ])
-    print fa
-    fa = minimize_enfa(fa)
-    print '-------------------------------'
-    print fa
-