| OLD | NEW |
| 1 # Copyright 2013 the V8 project authors. All rights reserved. | 1 # Copyright 2013 the V8 project authors. All rights reserved. |
| 2 # Redistribution and use in source and binary forms, with or without | 2 # Redistribution and use in source and binary forms, with or without |
| 3 # modification, are permitted provided that the following conditions are | 3 # modification, are permitted provided that the following conditions are |
| 4 # met: | 4 # met: |
| 5 # | 5 # |
| 6 # * Redistributions of source code must retain the above copyright | 6 # * Redistributions of source code must retain the above copyright |
| 7 # notice, this list of conditions and the following disclaimer. | 7 # notice, this list of conditions and the following disclaimer. |
| 8 # * Redistributions in binary form must reproduce the above | 8 # * Redistributions in binary form must reproduce the above |
| 9 # copyright notice, this list of conditions and the following | 9 # copyright notice, this list of conditions and the following |
| 10 # disclaimer in the documentation and/or other materials provided | 10 # disclaimer in the documentation and/or other materials provided |
| 11 # with the distribution. | 11 # with the distribution. |
| 12 # * Neither the name of Google Inc. nor the names of its | 12 # * Neither the name of Google Inc. nor the names of its |
| 13 # contributors may be used to endorse or promote products derived | 13 # contributors may be used to endorse or promote products derived |
| 14 # from this software without specific prior written permission. | 14 # from this software without specific prior written permission. |
| 15 # | 15 # |
| 16 # THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS | 16 # THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS |
| 17 # "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT | 17 # "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT |
| 18 # LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR | 18 # LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR |
| 19 # A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT | 19 # A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT |
| 20 # OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, | 20 # OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, |
| 21 # SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT | 21 # SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT |
| 22 # LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, | 22 # LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, |
| 23 # DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY | 23 # DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY |
| 24 # THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT | 24 # THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
| 25 # (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE | 25 # (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE |
| 26 # OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. | 26 # OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
| 27 | 27 |
| 28 import unittest | 28 import unittest |
| 29 from dot_utilities import * |
| 29 from automaton import Action | 30 from automaton import Action |
| 30 from regex_parser import RegexParser | 31 from regex_parser import RegexParser |
| 31 from transition_keys import TransitionKey, KeyEncoding | 32 from transition_keys import TransitionKey, KeyEncoding |
| 32 from nfa_builder import NfaBuilder | 33 from nfa_builder import NfaBuilder |
| 33 from dfa import Dfa | 34 from dfa import Dfa |
| 34 | 35 |
| 35 class AutomataTestCase(unittest.TestCase): | 36 class AutomataTestCase(unittest.TestCase): |
| 36 | 37 |
| 37 __encoding = KeyEncoding.get('latin1') | 38 __encoding = KeyEncoding.get('latin1') |
| 38 | 39 |
| (...skipping 35 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 74 for string in matches: | 75 for string in matches: |
| 75 for automaton in automata: | 76 for automaton in automata: |
| 76 self.assertTrue(automaton.matches(string)) | 77 self.assertTrue(automaton.matches(string)) |
| 77 for string in not_matches: | 78 for string in not_matches: |
| 78 for automaton in automata: | 79 for automaton in automata: |
| 79 self.assertFalse(automaton.matches(string)) | 80 self.assertFalse(automaton.matches(string)) |
| 80 | 81 |
| 81 def test_can_construct_dot(self): | 82 def test_can_construct_dot(self): |
| 82 for (regex, matches, not_matches) in self.__test_data: | 83 for (regex, matches, not_matches) in self.__test_data: |
| 83 for automaton in self.__build_automata(regex): | 84 for automaton in self.__build_automata(regex): |
| 84 automaton.to_dot() | 85 automaton_to_dot(automaton) |
| 85 | 86 |
| 86 def test_minimization(self): | 87 def test_minimization(self): |
| 87 encoding = self.__encoding | 88 encoding = self.__encoding |
| 88 def empty_node(): | 89 def empty_node(): |
| 89 return { | 90 return { |
| 90 'transitions' : {}, | 91 'transitions' : {}, |
| 91 'terminal' : False, | 92 'terminal' : False, |
| 92 'action' : Action.empty_action() } | 93 'action' : Action.empty_action() } |
| 93 mapping = { k : empty_node() for k in ['S_0', 'S_1', 'S_2', 'S_3'] } | 94 mapping = { k : empty_node() for k in ['S_0', 'S_1', 'S_2', 'S_3'] } |
| 94 key_a = TransitionKey.single_char(encoding, ord('a')) | 95 key_a = TransitionKey.single_char(encoding, ord('a')) |
| 95 key_b = TransitionKey.single_char(encoding, ord('b')) | 96 key_b = TransitionKey.single_char(encoding, ord('b')) |
| 96 key_c = TransitionKey.single_char(encoding, ord('c')) | 97 key_c = TransitionKey.single_char(encoding, ord('c')) |
| 97 | 98 |
| 98 mapping['S_0']['transitions'][key_a] = 'S_1' | 99 mapping['S_0']['transitions'][key_a] = 'S_1' |
| 99 mapping['S_0']['transitions'][key_b] = 'S_2' | 100 mapping['S_0']['transitions'][key_b] = 'S_2' |
| 100 mapping['S_1']['transitions'][key_c] = 'S_3' | 101 mapping['S_1']['transitions'][key_c] = 'S_3' |
| 101 mapping['S_2']['transitions'][key_c] = 'S_3' | 102 mapping['S_2']['transitions'][key_c] = 'S_3' |
| 102 mapping['S_3']['terminal'] = True | 103 mapping['S_3']['terminal'] = True |
| 103 | 104 |
| 104 mdfa = Dfa(encoding, 'S_0', mapping).minimize() | 105 mdfa = Dfa(encoding, 'S_0', mapping).minimize() |
| 105 self.assertEqual(3, mdfa.node_count()) | 106 self.assertEqual(3, mdfa.node_count()) |
| OLD | NEW |