Gfrktyl

A few months back, I posted a state machine for review. Thanks to the feedback, I was able to greatly simplify the implementation. I am posting the revised version, together with the Regex class which calls it.

I think I'm mainly looking for feedback on structure. The relationship between my Node class and StateMachine class feels a little tangled; I'm not always sure which method ought to belong to which class. I think the way I communicate the next token of my lexer is also cumbersome.

state_machine.py

class Node:

    def __init__(self, value):

        self.value = value

        self.children = set()



    def empty(self):

        return self.value == ''



    def add_child(self, other):

        self.children.add(other)



    def find_parent_of_terminal(self, terminal):

        """

        We assume that there shall only be one node leading to the terminal

        and that there is only one terminal

        """

        visited = set()

        to_explore = {self}

        while to_explore:

            current = to_explore.pop()

            visited.add(current)

            if terminal in current.children:

                # If this fails, then there is a bug in union, concat, or kleene

                assert len(current.children) == 1

                return current

            to_explore.update({node for node in current.children 

                               if node not in visited})

        return None



    def leads_to(self, value):

        """

        Return True iff argument can be reached by traversing empty nodes

        """

        return bool(self._get_node_if_reachable(value))



    def _get_node_if_reachable(self, value):

        for node in self.children:

            while node and node.empty():

                if node == value:

                    return node

                node = node._get_node_if_reachable(value)

        return None



    def __repr__(self):

        result = '{} : ['.format(self.value)

        for node in self.children:

            result += str(node.value) + ', '

        result += ']n'



        return result





def EmptyNode():

    return Node('')





class StateMachine:



    def __init__(self):

        self.initial = EmptyNode()

        self.terminal = EmptyNode()



    def __repr__(self):

        return str(self.initial)



    @staticmethod

    def from_string(source):

        dfa = StateMachine()

        nodes = [Node(char) for char in source]



        dfa.initial.add_child(nodes[0])

        for i in range(len(source) - 1):

            nodes[i].add_child(nodes[i + 1])

        nodes[-1].add_child(dfa.terminal)

        return dfa



    @staticmethod

    def from_set(chars):

        dfa = StateMachine()

        first = EmptyNode()

        penultimate = EmptyNode()

        dfa.initial.children = {first}



        for char in chars:

            char_node = Node(char)

            first.add_child(char_node)

            char_node.add_child(penultimate)



        penultimate.add_child(dfa.terminal)

        return dfa



    def concat(self, other):

        other.initial.find_parent_of_terminal(other.terminal).children = {self.terminal}

        self.initial.find_parent_of_terminal(self.terminal).children = other.initial.children



        return self



    def union(self, other):

        self.initial.children.update(other.initial.children)



        this_last = self.initial.find_parent_of_terminal(self.terminal)

        other_last = other.initial.find_parent_of_terminal(other.terminal)

        empty_node = EmptyNode()

        empty_node.add_child(self.terminal)

        this_last.children = {empty_node}

        other_last.children = {empty_node}

        return self



    def kleene(self):

        penultimate_node = self.initial.find_parent_of_terminal(self.terminal)

        dummy = EmptyNode()

        penultimate_node.children = {dummy}

        dummy.add_child(self.terminal)

        penultimate_node.add_child(self.initial)

        self.initial.add_child(dummy)

        return self



    def _get_next_state(self, nodes, value, visited=None):

        if visited is None:

            visited = set()

        result = set()

        for node in nodes:

            visited.add(node)

            for child in node.children:

                if child.empty() and child not in visited:

                    result.update(self._get_next_state([child], value, visited))

                elif child.value == value:

                    result.add(child)

        return result



    def is_match(self, nodes):

        for node in nodes:

            if node .leads_to(self.terminal):

                return True

        return False



    def match(self, source):

        """

        Match a target string by simulating a NFA

        :param source: string to match

        :return: Matched part of string, or None if no match is found

        """

        result = ''

        last_match = None

        current = {self.initial}

        for char in source:

            next_nodes = self._get_next_state(current, char)

            if next_nodes:

                current = next_nodes

                result += char



                if self.is_match(current):

                    last_match = result

            else:

                break



        if self.is_match(current):

            last_match = result

        return last_match

regex.py

import collections

import enum

import string





from state_machine import StateMachine





class Token(enum.Enum):

    METACHAR = 0

    CHAR = 1

    ERROR = 2





class LexResult(collections.namedtuple('LexResult', ['token', 'lexeme'])):

    def __bool__(self):

        return self.token != Token.ERROR





class RegexLexer(object):

    metachars = '-|^().*'



    def __init__(self, pattern: str):

        self._pattern = pattern

        self._pos = 0

        self._stack = 



    def peek(self) -> LexResult:

        if self._pos >= len(self._pattern):

            return LexResult(Token.ERROR, '')

        next_char = self._pattern[self._pos]

        if next_char in self.metachars:

            token = Token.METACHAR

        else:

            token = Token.CHAR

        return LexResult(token, next_char)



    def _eat_token_type(self, token: Token) -> LexResult:

        next_match = self.peek()

        if next_match.token != token:

            return LexResult(Token.ERROR, next_match.lexeme)

        self._pos += 1

        return next_match



    def _eat_token(self, match: LexResult) -> LexResult:

        next_match = self.peek()

        if next_match == match:

            self._pos += 1

            return next_match

        return LexResult(Token.ERROR, next_match.lexeme)



    def mark(self):

        self._stack.append(self._pos)



    def clear(self):

        self._stack.pop()



    def backtrack(self):

        self._pos = self._stack.pop()



    def eat_char(self, char=''):

        if char:

            return self._eat_token(LexResult(Token.CHAR, char))

        return self._eat_token_type(Token.CHAR)



    def eat_metachar(self, metachar):

        return self._eat_token(LexResult(Token.METACHAR, metachar))





class Regex(object):

    CHARACTERS = string.printable



    def __init__(self, pattern: str):

        """

        Initialize regex by compiling provided pattern

        """

        self._lexer = RegexLexer(pattern)

        self._state_machine = self.parse()



    def match(self, text: str) -> str:

        """

        Match text according to provided pattern.

        Returns matched substring if a match was found,

        or None otherwise

        """

        assert self._state_machine

        return self._state_machine.match(text)



    def parse(self):

        nfa = self.parse_simple_re()

        if not nfa:

            return None

        while True:

            self._lexer.mark()

            if not self._lexer.eat_metachar('|'):

                self._lexer.backtrack()

                return nfa

            next_nfa = self.parse_simple_re()

            if not next_nfa:

                self._lexer.backtrack()

                return nfa

            nfa = nfa.union(next_nfa)

            self._lexer.clear()



    def parse_simple_re(self):

        """

        <simple-re> = <basic-re>+

        """

        nfa = self.parse_basic_re()

        if not nfa:

            return None



        while True:

            next_nfa = self.parse_basic_re()

            if not next_nfa:

                break

            nfa = nfa.concat(next_nfa)

        return nfa



    def parse_basic_re(self):

        """

        <elementary-re> "*" | <elementary-re> "+" | <elementary-re>

        """

        nfa = self.parse_elementary_re()

        if not nfa:

            return None

        next_match = self._lexer.peek()

        if not next_match or next_match.token != Token.METACHAR:

            return nfa

        if next_match.lexeme == '*':

            self._lexer.eat_metachar('*')

            return nfa.kleene()

        if next_match.lexeme == '+':

            self._lexer.eat_metachar('+')

            return nfa.union(nfa.kleene())

        return nfa



    def parse_elementary_re(self):

        """

        <elementary-RE> = <group> | <any> | <char> | <set>

        :return: DFA

        """

        self._lexer.mark()

        nfa = self.parse_group()

        if nfa:

            self._lexer.clear()

            return nfa



        self._lexer.backtrack()

        if self._lexer.eat_metachar('.'):

            return StateMachine.from_set({x for x in self.CHARACTERS})



        char = self._lexer.eat_char()

        if char:

            return StateMachine.from_string(char.lexeme)



        set_chars = self.parse_set()

        if not set_chars:

            return None

        return StateMachine.from_set(set_chars)



    def parse_group(self):

        """

        <group> = "(" <RE> ")"

        :return: DFA

        """

        if not self._lexer.eat_metachar('('):

            return None

        state_machine = self.parse()

        if not state_machine:

            return None

        if not self._lexer.eat_metachar(')'):

            return None

        return state_machine



    def parse_range(self) -> {str}:

        """

        <range> = <CHAR> "-" <CHAR>

        """

        first = self._lexer.eat_char()

        if not first:

            return set()



        if not self._lexer.eat_metachar('-'):

            return set()



        last = self._lexer.eat_char()

        if not last:

            return set()



        return {chr(x) for x in range(ord(first.lexeme), ord(last.lexeme) + 1)}



    def parse_set_item(self) -> {str}:

        """

        <set item> = <range> | <char>

        """

        self._lexer.mark()

        set_item = self.parse_range()

        if set_item:

            self._lexer.clear()

            return set_item

        self._lexer.backtrack()

        next_item = self._lexer.eat_char()

        return {next_item.lexeme} if next_item else set()



    def parse_set_items(self) -> {str}:

        """

        <set items> = <set item>+

        """

        items = self.parse_set_item()

        if not items:

            return set()

        next_items = self.parse_set_item()

        while next_items:

            items.update(next_items)

            next_items = self.parse_set_item()

        return items



    def parse_positive_set(self) -> {str}:

        if not self._lexer.eat_metachar('['):

            return set()

        set_items = self.parse_set_items()

        if not set_items:

            return set()

        if not self._lexer.eat_metachar(']'):

            return set()

        return set_items



    def parse_negative_set(self) -> {str}:

        if not self._lexer.eat_metachar('['):

            return set()

        if not self._lexer.eat_metachar('^'):

            return set()

        set_items = self.parse_set_items()

        if not set_items:

            return set()

        if not self._lexer.eat_metachar(']'):

            return set()

        return set(string.printable).difference(set_items)



    def parse_set(self) -> {str}:

        """

        Parse something like [a-z9] and return the set of allowed characters

        """

        self._lexer.mark()

        set_items = self.parse_positive_set()

        if set_items:

            self._lexer.clear()

            return set_items

        self._lexer.backtrack()

        return self.parse_negative_set()

Finally, a small set of unit tests to show usage:

import unittest

from state_machine import StateMachine

from regex import Regex





class TestStateMachine(unittest.TestCase):



    def test_union(self):

        state_machine = StateMachine.from_string('abc')

        state_machine = state_machine.union(StateMachine.from_string('def'))



        self.assertEqual(state_machine.match('abc'), 'abc')

        self.assertEqual(state_machine.match('def'), 'def')

        self.assertIsNone(state_machine.match('de'))



    def test_kleene(self):

        state_machine = StateMachine.from_string('abc')

        state_machine = state_machine.kleene()



        self.assertEqual(state_machine.match(''), '')

        self.assertEqual(state_machine.match('abc'), 'abc')

        self.assertEqual(state_machine.match('abcabc'), 'abcabc')

        self.assertEqual(state_machine.match('abcDabc'), 'abc')



    def test_concat(self):

        state_machine = StateMachine.from_string('ab')

        state_machine = state_machine.concat(StateMachine.from_string('cd'))



        self.assertEqual(state_machine.match('abcd'), 'abcd')

        self.assertEqual(state_machine.match('abcde'), 'abcd')

        self.assertIsNone(state_machine.match('abc'))





class TestRegex(unittest.TestCase):



    def test_identifier_regex(self):

        regex = Regex('[a-zA-Z_][a-zA-Z0-9_]*')

        self.assertEqual(regex.match('a'), 'a')

        self.assertFalse(regex.match('0'))

        self.assertTrue(regex.match('a0'))

        self.assertEqual(regex.match('a0_3bd'), 'a0_3bd')

        self.assertEqual(regex.match('abd-43'), 'abd')



    def test_parentheses(self):

        regex = Regex('d(ab)*')

        self.assertEqual(regex.match('d'), 'd')

        self.assertEqual(regex.match('dab'), 'dab')

        self.assertEqual(regex.match('daa'), 'd')

        self.assertEqual(regex.match('dabab'), 'dabab')



    def test_union(self):

        regex = Regex('(ab*d)|(AG)')

        self.assertEqual(regex.match('adG'), 'ad')

        self.assertEqual(regex.match('AGfe'), 'AG')





if __name__ == '__main__':

    unittest.main()

Yay! You ran flake8 and followed PEP-8. Nice clean code.

    self.assertEqual(state_machine.match('abc'), 'abc')

Ummm, this is arguably backwards.
Convention for xUnit in many languages is to assertEqual(expected, computed).
It can affect how the diagnostic output is displayed for a failure.

    state_machine = state_machine.union(StateMachine.from_string('def'))

Choosing the name union for your public API is perhaps slightly confusing.
"Union" is drawn from set theory,
while "alternation" is the term the regex literature tends to use for |.

    state_machine = StateMachine.from_string('abc')

The class name is perfectly clear, it's great.
For a local variable that we'll be using a bunch, sm would have sufficed.
You already have a line that verifies that .from_string() doesn't blow up, so
consider combining two assignments on a single line:

    sm = StateMachine.from_string('abc').kleene()

The Regex class is wonderfully straightforward.
Pat yourself on the back.

The peek method in the lexer is perhaps a little on the tricky side,
and would benefit from comments
about when we consume something or not.
I'm looking for invariants on pos and the stack.
I like the assert in find_parent_of_terminal, and its comment.

        to_explore.update({node for node in current.children 

                           if node not in visited})

That's just set difference, yes? children - visited

Overall, looks good. Ship it!