Mercurial > hg > Members > shinya > pyrect

changeset 89:933d422f21f0

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
add class trie. this can accept suffix-language.
author Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
date Tue, 16 Nov 2010 06:01:56 +0900
parents dafb393108f3
children 8cfa81638130
files pyrect/converter.py pyrect/regexp/nfa.py
diffstat 2 files changed, 13 insertions(+), 5 deletions(-) [+]
line wrap: on
line diff
--- a/pyrect/converter.py	Sun Nov 14 07:56:35 2010 +0900
+++ b/pyrect/converter.py	Tue Nov 16 06:01:56 2010 +0900
@@ -17,6 +17,7 @@
     psr.add_option("--from-nfa", action="store_true", dest="nfa", default=False, help="translate from NFA")
     psr.add_option("--from-snfa", action="store_true", dest="snfa", default=False, help="translate from SuffixNFA")
     psr.add_option("--from-sdfa", action="store_true", dest="sdfa", default=False, help="translate from SuffixDFA")
+    psr.add_option("--from-trie", action="store_true", dest="trie", default=False, help="translate from Trie")
     psr.add_option("-o", action="store", type="string", dest="output", default=False, help="output file", metavar="FILE")
     psr.add_option("-O", action="store_true", dest="optimize", default=False, help="do optimization (only in llvm).")
     psr.add_option("-g", action="store_true", dest="debug", default=False, help="embed debug info")
@@ -33,7 +34,7 @@
     if opts.nfa:
         fa = "NFA"
     elif opts.snfa:
-        fa = "NFA"
+        fa = "SDFA"
         reg.nfa = SuffixNFA(reg.nfa)
         reg.nfacg = CallGraph(reg.nfa)
     elif opts.sdfa:
@@ -41,6 +42,11 @@
         sdfa = SuffixDFATranslator().translate(reg.dfa)
         reg.dfa = sdfa
         reg.dfacg = CallGraph(sdfa)
+    elif opts.trie:
+        fa = "DFA"
+        trie = SuffixTrieTranslator().translate(reg.dfa)
+        reg.dfa = trie
+        reg.dfacg = CallGraph(trie)
     else:
         fa = "DFA"
 
--- a/pyrect/regexp/nfa.py	Sun Nov 14 07:56:35 2010 +0900
+++ b/pyrect/regexp/nfa.py	Tue Nov 16 06:01:56 2010 +0900
@@ -108,8 +108,7 @@
         offset = [x * len(states) for x in range(len(states))]
         for s, ind in zip(states, offset):
             for (s_, i), n in self.pdfa.map.iteritems():
-                if s_ != s: continue
-                sind = s + ind
+                sind = s_ + ind
                 nind = n + ind
                 add_states.add((sind, nind))
                 if n in self.pdfa.accepts:
@@ -117,9 +116,12 @@
                     self.acceptable[nind].add(s)
                 self.map[(sind, i)] = set((nind,))
 
+        starts = set()
+        for i in range(1, len(states)):
+            starts.add(self.start + i + offset[i])
+
         self.states = list(add_states)
-        self.map[(self.start, '')] = add_states.difference((self.start, ))
-        print self.map
+        self.map[(self.start, '')] = starts
 
     def transition(self, state, char):
         return frozenset(self.map.get((state, char), []))