| 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 |
| (...skipping 22 matching lines...) Expand all Loading... |
| 33 | 33 |
| 34 def dfa_from_nfa(nfa): | 34 def dfa_from_nfa(nfa): |
| 35 (start_name, dfa_nodes) = nfa.compute_dfa() | 35 (start_name, dfa_nodes) = nfa.compute_dfa() |
| 36 return Dfa(start_name, dfa_nodes) | 36 return Dfa(start_name, dfa_nodes) |
| 37 | 37 |
| 38 def build_automata(string): | 38 def build_automata(string): |
| 39 nfa = NfaBuilder().nfa(RegexParser.parse(string)) | 39 nfa = NfaBuilder().nfa(RegexParser.parse(string)) |
| 40 dfa = dfa_from_nfa(nfa) | 40 dfa = dfa_from_nfa(nfa) |
| 41 return (nfa, dfa, dfa.minimize()) | 41 return (nfa, dfa, dfa.minimize()) |
| 42 | 42 |
| 43 def simple_action(string): |
| 44 return Action(None, (string, None)) |
| 45 |
| 43 class AutomataTestCase(unittest.TestCase): | 46 class AutomataTestCase(unittest.TestCase): |
| 44 | 47 |
| 45 # (pattern, should match, should not match) | 48 # (pattern, should match, should not match) |
| 46 __test_data = [ | 49 __test_data = [ |
| 47 ("a", ["a"], ["b", ""]), | 50 ("a", ["a"], ["b", ""]), |
| 48 ("ab", ["ab"], ["bb", ""]), | 51 ("ab", ["ab"], ["bb", ""]), |
| 49 ("a+b", ["ab", "aab", "aaab"], ["a", "b", ""]), | 52 ("a+b", ["ab", "aab", "aaab"], ["a", "b", ""]), |
| 50 ("a?b", ["ab", "b"], ["a", "c", ""]), | 53 ("a?b", ["ab", "b"], ["a", "c", ""]), |
| 51 ("a*b", ["ab", "aaab", "b"], ["a", "c", ""]), | 54 ("a*b", ["ab", "aaab", "b"], ["a", "c", ""]), |
| 52 ("a|b", ["a", "b"], ["ab", "c", ""]), | 55 ("a|b", ["a", "b"], ["ab", "c", ""]), |
| (...skipping 21 matching lines...) Expand all Loading... |
| 74 for string in not_matches: | 77 for string in not_matches: |
| 75 for automaton in automata: | 78 for automaton in automata: |
| 76 self.assertFalse(automaton.matches(string)) | 79 self.assertFalse(automaton.matches(string)) |
| 77 | 80 |
| 78 def test_can_construct_dot(self): | 81 def test_can_construct_dot(self): |
| 79 for (regex, matches, not_matches) in self.__test_data: | 82 for (regex, matches, not_matches) in self.__test_data: |
| 80 for automaton in build_automata(regex): | 83 for automaton in build_automata(regex): |
| 81 automaton.to_dot() | 84 automaton.to_dot() |
| 82 | 85 |
| 83 def test_actions(self): | 86 def test_actions(self): |
| 84 left_action = Action("LEFT_ACTION") | 87 left_action = simple_action("LEFT_ACTION") |
| 85 right_action = Action("RIGHT_ACTION") | 88 right_action = simple_action("RIGHT_ACTION") |
| 86 left = RegexParser.parse("left") | 89 left = RegexParser.parse("left") |
| 87 right = RegexParser.parse("right") | 90 right = RegexParser.parse("right") |
| 88 left = NfaBuilder.add_action(left, left_action) | 91 left = NfaBuilder.add_action(left, left_action) |
| 89 right = NfaBuilder.add_action(right, right_action) | 92 right = NfaBuilder.add_action(right, right_action) |
| 90 composite = ('ONE_OR_MORE', NfaBuilder.or_graphs([left, right])) | 93 composite = ('ONE_OR_MORE', NfaBuilder.or_graphs([left, right])) |
| 91 nfa = NfaBuilder().nfa(composite) | 94 nfa = NfaBuilder().nfa(composite) |
| 92 dfa = dfa_from_nfa(nfa) | 95 dfa = dfa_from_nfa(nfa) |
| 93 def verify(string, expected): | 96 def verify(string, expected): |
| 94 actions = list(dfa.collect_actions(string)) | 97 actions = list(dfa.collect_actions(string)) |
| 95 self.assertEqual(len(expected), len(actions)) | 98 self.assertEqual(len(expected), len(actions)) |
| 96 for i, action in enumerate(actions): | 99 for i, action in enumerate(actions): |
| 97 self.assertEqual(action, expected[i]) | 100 self.assertEqual(action, expected[i]) |
| 98 def verify_miss(string, expected): | 101 def verify_miss(string, expected): |
| 99 verify(string, expected + [Action('MISS',)]) | 102 verify(string, expected + [Dfa.miss_action()]) |
| 100 def verify_hit(string, expected): | 103 def verify_hit(string, expected): |
| 101 verify(string, expected + [Action('TERMINATE',)]) | 104 verify(string, expected + [Dfa.terminal_action()]) |
| 102 (l, r) = left_action, right_action | 105 (l, r) = left_action, right_action |
| 103 verify_hit("left", [l]) | 106 verify_hit("left", [l]) |
| 104 verify_miss("lefta", [l]) | 107 verify_miss("lefta", [l]) |
| 105 verify_hit("leftrightleftright", [l, r, l, r]) | 108 verify_hit("leftrightleftright", [l, r, l, r]) |
| 106 verify_miss("leftrightleftrightx", [l, r, l, r]) | 109 verify_miss("leftrightleftrightx", [l, r, l, r]) |
| OLD | NEW |