Changeset 21058

Show
Ignore:
Timestamp:
10/09/08 21:37:53 (5 years ago)
Author:
hiratara
Message:

ゴミを削除。最小限のソースにした。

Location:
lang/python/dfareg/branches/codezine200809
Files:
9 modified

Legend:

Unmodified
Added
Removed

  • lang/python/dfareg/branches/codezine200809/dfareg/__init__.py

    r20647 r21058  
    1 #!/usr/bin/env python2.5 
    21# -*- coding: utf-8 -*- 
    3 from dfa import * 
    42from nfa2dfa import nfa2dfa 
    5 from parser     import Parser 
    6 from lexer      import Lexer 
    7  
    8 def strict_match_nfa(regexp, string): 
    9     nfa = lexer.compile_to_nfa(regexp) 
    10     return nfa.get_runtime().does_accept(string) 
    11  
    12 def strict_match_dfa(regexp, string): 
    13     nfa = lexer.compile_to_nfa(regexp) 
    14     dfa = nfa2dfa(nfa) 
    15     return dfa.get_runtime().does_accept(string) 
    16  
    17 strict_match = strict_match_dfa 
    18  
    19 def print_nfa(regexp): 
    20     nfa = lexer.compile_to_nfa(regexp) 
    21     print "[START]" 
    22     print nfa.start 
    23     print "[STATES]" 
    24     for s in nfa.states: 
    25         print s 
    26     print "[ACCEPTS]" 
    27     for s in nfa.accepts: 
    28         print s 
    29     print "[TRANSITION]" 
    30     print "not printable" 
    31  
     3from parser  import Parser 
     4from lexer   import Lexer 
    325 
    336class Regexp(object): 
    … …  
    4821def compile(regexp): 
    4922    return Regexp(regexp) 
    50  
    51  
    52 #     for k, v in nfafrag.map.iteritems(): 
    53 #         print k, v 
    54  
    55 # cd /Users/tarara/Documents/技術関係/開発合宿/20080524/python 
    56  
    57 # >>> import dfareg 
    58 # >>> dfareg.strict_match("(p(erl|ython|hp)|ruby)", "python") 
    59 # True 
    60  
    61 # >>> dfareg.print_nfa("A*B") 
    62  
    63 # >>> import re 
    64 # >>> re.match("^x*x*x*x*x*x*x*x*x*x*x*x*x*x*xxxxxxxxxxxxxx$", "xxxxxxxxxxxxxx") 
    65 # <_sre.SRE_Match object at 0x2581a8> 
    66 # >>> dfareg.strict_match("x*x*x*x*x*x*x*x*x*x*x*x*x*x*xxxxxxxxxxxxxx", "xxxxxxxxxxxxxx") 
    67 # True 

  • lang/python/dfareg/branches/codezine200809/dfareg/dfa.py

    r19696 r21058  
    1 #!/usr/bin/env python2.5 
    21# -*- coding: utf-8 -*- 
    3 """ 
    4 An joke deterministic finite automaton implementation. 
    5  
    6 """ 
    72 
    83class DFARuntime(object): 
    … …  
    1813 
    1914    def does_accept(self, input): 
    20         """ 
    21         Check whether an input is accepted by this automaton. 
    22         """ 
    2315        for alphabet in input: 
    2416            self.do_transition(alphabet) 
    2517        return self.is_accept_state() 
    2618 
     19 
    2720class DeterministicFiniteAutomaton(object): 
    28     """ 
    29     An deterministic finite automaton implementation. 
    30     It's just for fun. So, you shouldn't use this in your products. 
    31     """ 
    3221    def __init__(self,  
    33                  transition , # a transition function 
    34                  start      , # a start state 
    35                  accepts    , # a set of accept states 
     22                 transition , # 遷移関数 
     23                 start      , # 開始状態 
     24                 accepts    , # 受理状態の集合 
    3625                 ): 
    37         """ 
    38         Instanciate new deterministic finite automaton  
    39         from 5-tuple. 
    40         """ 
    4126        self.transition = transition 
    4227        self.start      = start 
    … …  
    4530    def get_runtime(self): 
    4631        return DFARuntime(self) 
    47  
    48 if __name__ == '__main__': 
    49     pass 
    50  
    51  
    52  

  • lang/python/dfareg/branches/codezine200809/dfareg/lexer.py

    r20730 r21058  
    1 #!/usr/bin/env python2.5 
    21# -*- coding: utf-8 -*- 
    3  
    4  
    52 
    63class Talken(object): 
    … …  
    4845            # 通常の文字 
    4946            return Talken(ch, Talken.CHARACTER) 
    50  
    51 if __name__ == '__main__': 
    52     lexer = Lexer(u"あ(い\|う|え*(かき|くけこ))*お") 
    53     while True: 
    54         talken = lexer.scan() 
    55         if not talken: break 
    56         print talken 

  • lang/python/dfareg/branches/codezine200809/dfareg/nfa.py

    r20841 r21058  
    1 #!/usr/bin/env python2.5 
    21# -*- coding: utf-8 -*- 
    32 
    43class NondeterministicFiniteAutomaton(object): 
    5     """ 
    6     An nondeterministic finite automaton implementation. 
    7     It's just for fun. So, you shouldn't use this in your products. 
    8     """ 
    94    def __init__(self,  
    105                 transition , # a transition function 
    … …  
    127                 accepts    , # a set of accept states 
    138                 ): 
    14         """ 
    15         Instanciate new deterministic finite automaton  
    16         from 5-tuple. 
    17         """ 
    189        self.transition = transition 
    1910        self.start      = start 

  • lang/python/dfareg/branches/codezine200809/dfareg/nfa2dfa.py

    r20841 r21058  
    1 #!/usr/bin/env python2.5 
    21# -*- coding: utf-8 -*- 
    3  
    42from dfa import DeterministicFiniteAutomaton 
    53 
    64class SubsetsIncludingElem(object): 
    7     """ 
    8     the set of subsets of "super_" including an element of "sub". 
    9  
    10     >>> from dfareg import algebra 
    11     >>> s = algebra.subsets_including_elem(set([1,2,3]), set([1,3])) 
    12     >>> for i in s:  
    13     ...     print i 
    14     ...  
    15     frozenset([3]) 
    16     frozenset([1, 2]) 
    17     frozenset([2, 3]) 
    18     frozenset([1]) 
    19     frozenset([1, 3]) 
    20     frozenset([1, 2, 3]) 
    21     >>> set([1,2]) in s 
    22     True 
    23     >>> set([2]) in s 
    24     False 
    25     """ 
    265    def __init__(self, sub): 
    276        self.sub   = sub 
    … …  
    298        return a_set & self.sub 
    309 
     10 
    3111def nfa2dfa(nfa): 
    32  
    3312    def transition(set_, alpha): 
    3413        ret = set() 
    … …  
    4221            SubsetsIncludingElem(nfa.accepts) 
    4322            ) 
    44  
    45 if __name__ == '__main__': 
    46     regexp = u"あ(い\|う|え*(かき|くけこ))*お" 
    47     regexp = u"A*(B|C)*" 
    48     nfastate = lexer.compile_to_nfa(regexp) 
    49     for s in nfastate.all_states(): 
    50         print s 
    51  
    52     nfa2dfa(nfastate) 

  • lang/python/dfareg/branches/codezine200809/dfareg/nfabuilder.py

    r21057 r21058  
    1 #!/usr/bin/env python2.5 
    21# -*- coding: utf-8 -*- 
    32import nfa 
    … …  
    54 
    65class NFAFragment(object): 
    7     """ 
    8     >>> b = nfa.NFABuilder("abcde") 
    9     >>> b.start 
    10     1 
    11     >>> s1 = b.new_state() 
    12     >>> s2 = b.new_state() 
    13     >>> b.connect(b.start, None, s2) 
    14     >>> b.connect(b.start, "b", s1) 
    15     >>> b.accepting_state(b.start) 
    16     >>> b.accepting_state(s2) 
    17     >>> am = b.build() 
    18     >>> am.start 
    19     1 
    20     >>> am.accepts 
    21     frozenset([1, 3]) 
    22     >>> am.states 
    23     frozenset([1, 2, 3]) 
    24     >>> am.transition(1, None) 
    25     frozenset([3]) 
    26     >>> am.transition(3, None) 
    27     frozenset([]) 
    28     >>> am.transition(1, "b") 
    29     frozenset([2]) 
    30     >>>  
    31     """ 
    326    def __init__(self): 
    337        self.start   = None  # 整数型 
    … …  
    144118 
    145119        return frag 
    146  
    147  
    148  
    149  
    150 if __name__ == '__main__': 
    151     b = NFABuilder() 
    152     f = b.new_fragment() 
    153     print f.start 
    154     s1 = f.new_state() 
    155     s2 = f.new_state() 
    156     f.connect(f.start, "", s2) 
    157     f.connect(f.start, "b", s1) 
    158     f.accepts.add(f.start) 
    159     f.accepts.add(s2) 
    160     am = b.build(f) 
    161     print am.start 
    162     print am.accepts 
    163     # print am.states 
    164     print am.transition(1, "") 
    165     print am.transition(3, "") 
    166     print am.transition(1, "b") 

  • lang/python/dfareg/branches/codezine200809/dfareg/parser.py

    r20822 r21058  
    1 #!/usr/bin/env python2.5 
    21# -*- coding: utf-8 -*- 
    32from lexer import Talken 
    … …  
    8079            self.match(Talken.CHARACTER); 
    8180            return node 
    82  
    83  
    84 if __name__ == '__main__': 
    85     from nfabuilder import NFABuilder 
    86     lexer_ = lexer.Lexer(u"あ(い\|う|え*(かき|くけこ))*お") 
    87     parser = Parser(lexer_, NFABuilder() ) 
    88     parser.expression() 

  • lang/python/dfareg/branches/codezine200809/dfareg/test/dfaregtest.py

    r21057 r21058  
    22# -*- coding: utf-8 -*- 
    33import dfareg 
     4from dfareg.dfa import DeterministicFiniteAutomaton 
    45import unittest 
    56 
    … …  
    1112            if state == 1 and char == u"う": return 3 
    1213            return 4 
    13         self.dfa = dfareg.DeterministicFiniteAutomaton( 
     14        self.dfa = DeterministicFiniteAutomaton( 
    1415            transition, 
    1516            0, 

  • lang/python/dfareg/branches/codezine200809/setup.py

    r21057 r21058  
     1#!/usr/bin/env python 
     2# -*- coding: utf-8 -*- 
     3 
    14from setuptools import setup, find_packages 
    25setup(