Reviewers: marja,
Message:
Committed patchset #1 manually as r17439.
Description:
Experimental parser: some unit tests
[email protected]
BUG=
Committed: https://code.google.com/p/v8/source/detail?r=17439
Please review this at https://codereview.chromium.org/54303002/
SVN Base: https://v8.googlecode.com/svn/branches/experimental/parser
Affected files (+49, -19 lines):
A + tools/lexer_generator/automata_test.py
M tools/lexer_generator/dfa.py
M tools/lexer_generator/nfa.py
M tools/lexer_generator/regex_parser.py
M tools/lexer_generator/transition_keys.py
Index: tools/lexer_generator/automata_test.py
diff --git a/tools/testrunner/local/junit_output.py
b/tools/lexer_generator/automata_test.py
similarity index 57%
copy from tools/testrunner/local/junit_output.py
copy to tools/lexer_generator/automata_test.py
index
437adb178931f82364aa87e66315231b7b57a56d..42346a9100d0e3c8facf7b569701e030288b1e49
100644
--- a/tools/testrunner/local/junit_output.py
+++ b/tools/lexer_generator/automata_test.py
@@ -25,25 +25,41 @@
# (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
# OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+import unittest
+from regex_parser import RegexParser
+from nfa import NfaBuilder
+from dfa import Dfa
-import xml.etree.ElementTree as xml
+def build_automata(string):
+ parser = RegexParser()
+ parser.build()
+ graph = parser.parse(string)
+ nfa = NfaBuilder().nfa(graph)
+ (start_name, dfa_nodes, end_nodes) = nfa.compute_dfa()
+ dfa = Dfa(start_name, dfa_nodes, end_nodes)
+ return (nfa, dfa)
+class AutomataTestCase(unittest.TestCase):
-class JUnitTestOutput:
- def __init__(self, test_suite_name):
- self.root = xml.Element("testsuite")
- self.root.attrib["name"] = test_suite_name
+ # (pattern, should match, shouldn't match)
+ __test_data = [
+ ("a", ["a"], ["b"]),
+ ("ab", ["ab"], ["bb"]),
+ ("a+b", ["ab", "aab", "aaab"], ["a", "b"]),
+ ("a?b", ["ab", "b"], ["a", "c"]),
+ ("a*b", ["ab", "aaab", "b"], ["a", "c"]),
+ ("a|b", ["a", "b"], ["ab", "c"]),
+ ]
- def HasRunTest(self, test_name, test_duration, test_failure):
- testCaseElement = xml.Element("testcase")
- testCaseElement.attrib["name"] = " ".join(test_name)
- testCaseElement.attrib["time"] = str(round(test_duration, 3))
- if len(test_failure):
- failureElement = xml.Element("failure")
- failureElement.text = test_failure
- testCaseElement.append(failureElement)
- self.root.append(testCaseElement)
-
- def FinishAndWrite(self, file):
- xml.ElementTree(self.root).write(file, "UTF-8")
+ def test_matches(self):
+ for (regex, matches, not_matches) in AutomataTestCase.__test_data:
+ (nfa, dfa) = build_automata(regex)
+ for string in matches:
+ self.assertTrue(nfa.matches(string))
+ self.assertTrue(dfa.matches(string))
+ for string in not_matches:
+ self.assertFalse(nfa.matches(string))
+ self.assertFalse(dfa.matches(string))
+if __name__ == '__main__':
+ unittest.main()
Index: tools/lexer_generator/dfa.py
diff --git a/tools/lexer_generator/dfa.py b/tools/lexer_generator/dfa.py
index
945900680019bb2d95d6a00081630d717936b42f..4da6f541f9bc6335a58a4d8e66dd7fe594042067
100644
--- a/tools/lexer_generator/dfa.py
+++ b/tools/lexer_generator/dfa.py
@@ -78,6 +78,19 @@ class Dfa:
edge = next_edge - visited
return state
+ def matches(self, string):
+ state = self.__start
+ for c in string:
+ next_state = None
+ for key, transition_state in state.transitions().items():
+ if key.matches_char(c):
+ next_state = transition_state
+ break
+ if not next_state:
+ return False
+ state = next_state
+ return state in self.__terminal_set
+
def to_dot(self):
def f(node, node_content):
Index: tools/lexer_generator/nfa.py
diff --git a/tools/lexer_generator/nfa.py b/tools/lexer_generator/nfa.py
index
3bb3607dbe126b5ab53b1b98f5c6ce64b00a94d4..8e15f82290cceb978e14f3eaac453c6f7447db8b
100644
--- a/tools/lexer_generator/nfa.py
+++ b/tools/lexer_generator/nfa.py
@@ -245,7 +245,7 @@ class Nfa:
valid_states = Nfa.__close(set([self.__start]))
for c in string:
f = lambda acc, state: acc | state.char_matches(c)
- valid_states = Nfa.__close(reduce(valid_states, f, set()))
+ valid_states = Nfa.__close(reduce(f, valid_states, set()))
if not valid_states:
return False
return self.__end in valid_states
Index: tools/lexer_generator/regex_parser.py
diff --git a/tools/lexer_generator/regex_parser.py
b/tools/lexer_generator/regex_parser.py
index
6851b70a499d3565e790a47d8299cedefc0a0b1e..9837a55e18fc84ef562a6125e4c127455c6c4cea
100644
--- a/tools/lexer_generator/regex_parser.py
+++ b/tools/lexer_generator/regex_parser.py
@@ -125,7 +125,7 @@ class RegexParser:
return ('CAT', left, right)
def build(self, **kwargs):
- self.parser = yacc.yacc(module=self, **kwargs)
+ self.parser = yacc.yacc(module=self, debug=0, write_tables=0, **kwargs)
self.lexer = RegexLexer()
self.lexer.build(**kwargs)
Index: tools/lexer_generator/transition_keys.py
diff --git a/tools/lexer_generator/transition_keys.py
b/tools/lexer_generator/transition_keys.py
index
e7c15b43236d8bccff0e7685ad69434c600e50e7..9d6fbf54fc27027b40844adce61aa6f6f65b2bfd
100644
--- a/tools/lexer_generator/transition_keys.py
+++ b/tools/lexer_generator/transition_keys.py
@@ -70,6 +70,7 @@ class TransitionKey:
return TransitionKey.__create([(129, 129)])
def matches_char(self, char):
+ char = ord(char)
for r in self.__ranges:
if r[0] <= char and char <= r[1]: return True
return False
--
--
v8-dev mailing list
[email protected]
http://groups.google.com/group/v8-dev
---
You received this message because you are subscribed to the Google Groups "v8-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
For more options, visit https://groups.google.com/groups/opt_out.
