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 |