Mercurial > hg > Members > shinya > pyrect

comparison pyrect/regexp/nfa_translator.py @ 87:d23f12ce0369

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
add suffix-dfa, it's used to be parallel-matching-algorithm (not implement, yet).
author Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
date Sun, 14 Nov 2010 04:16:12 +0900
parents fd3d0b8326fe
children 82a8232625c3
comparison
equal deleted inserted replaced
85:b34a900a3a0b 87:d23f12ce0369
8 class NFATranslator(ASTWalker): 8 class NFATranslator(ASTWalker):
9 """ Create NFA from AST with Visitor-Pattern. 9 """ Create NFA from AST with Visitor-Pattern.
10 AST (ast), is represented by Node-Tree. 10 AST (ast), is represented by Node-Tree.
11 >>> prs = Parser() 11 >>> prs = Parser()
12 >>> nfat = NFATranslator() 12 >>> nfat = NFATranslator()
13 >>> nfat.translate(prs.parse('(A|B)*C')).map 13 >>> nfa = nfat.translate(prs.parse('(A|B)*C'))
14 {(3, ''): set([2, 4]), (2, ''): set([0, 1]), (1, (Character:'B')): set([3]), (0, (Character:'A')): set([3]), (4, (Character:'C')): set([5])} 14 >>> nfa.map
15 >>> nfat.translate(prs.parse('(A|B)*C')).accepts 15 {(3, ''): set([2, 4]), (2, ''): set([0, 1]), (1, (Character:'B')): set([3]), (4, (Character:'C')): set([5]), (0, (Character:'A')): set([3])}
16 [5] 16 >>> anfa = ANFA(nfa)
17 >>> nfat.translate(prs.parse('ほ?げ+')).map 17 >>> anfa.map
18 {(1, (Character:'B')): set([3]), (0, (Character:'A')): set([3]), (3, ''): set([2, 4]), (6, ''): set([0, 1, 2, 3, 4, 5]), (2, ''): set([0, 1]), (4, (Character:'C')): set([5])}
18 """ 19 """
19 20
20 def __init__(self): 21 def __init__(self):
21 self.ast = None 22 self.ast = None
22 self.nfa = None 23 self.nfa = None