2015年12月4日金曜日

開発環境

  • OS X El Capitan - Apple (OS)
  • Emacs(Text Editor)
  • Python 3.5 (プログラミング言語)

アンダースタンディング コンピュテーション (Tom Stuart (著)、 笹田 耕一(著)、笹井 崇司 (翻訳)、オライリージャパン)の第1部(プログラムと機械)、3章(最も単純なコンピュータ)、3.3(正規表現)、3.3.2(意味論)を Python (本書ではRuby) で取り組んでみる。

3.3.2(意味論)

コード(Emacs)

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

class FARule:
    def __init__(self, state, character, next_state):
        self.state = state
        self.character = character
        self.next_state = next_state

    def is_applies_to(self, state, character):
        return self.state == state and self.character == character

    def follow(self):
        return self.next_state    

    def __repr__(self):
        return '#<FARule {0} --{1}--> {2}>'.format(
            repr(self.state), self.character, repr(self.next_state))

class NFARulebook:
    def __init__(self, rules):
        self.rules = rules

    def next_states(self, states, character):
        mapped = map(lambda state: self.follow_rules_for(state, character),
                     states)
        return set([x for l in mapped for x in l])

    def follow_rules_for(self, state, character):
        return map(lambda x: x.follow(), self.rules_for(state, character))

    def rules_for(self, state, character):
        return filter(lambda rule: rule.is_applies_to(state, character),
                      self.rules)

    def follow_free_moves(self, states):
        more_states = self.next_states(states, None)
        if more_states <= states:
            return states
        return self.follow_free_moves(states | more_states)

class NFA:
    def __init__(self, current_states, accept_states, rulebook):        
        self.current_states = rulebook.follow_free_moves(current_states)
        self.accept_states = accept_states
        self.rulebook = rulebook

    def is_accepting(self):
        return any(self.current_states & set(self.accept_states))

    def read_character(self, character):
        self.current_states = self.rulebook.next_states(
            self.rulebook.follow_free_moves(self.current_states), character)

    def read_string(self, string):
        for character in string:
            self.read_character(character)

class NFADesign:
    def __init__(self, start_state, accept_states, rulebook):
        self.start_state = start_state
        self.accept_states = accept_states
        self.rulebook = rulebook

    def is_accepts(self, string):
        nfa = self.to_nfa()
        nfa.read_string(string)
        return nfa.is_accepting()
    
    def to_nfa(self):
        return NFA({self.start_state}, self.accept_states, self.rulebook)    

class Pattern:
    def __init__(self, precedence):
        self.precedence = precedence
        
    def bracket(self, outer_precedence):
        if self.precedence < outer_precedence:
            return '({0})'.format(self)
        return str(self)

    def __repr__(self):
        return '/{0}/'.format(self)

    def is_matches(self, string):
        return self.to_nfa_design().is_accepts(string)
        
class Empty(Pattern):
    def __init__(self):
        Pattern.__init__(self, 3)        
        
    def __str__(self):
        return ''

    def to_nfa_design(self):
        start_state = object()
        accept_states = [start_state]
        rulebool = NFARulebook([])
        return NFADesign(start_state, accept_states, rulebool)
        

class Literal(Pattern):
    def __init__(self, character):
        Pattern.__init__(self, 3)
        self.character = character
        
    def __str__(self):
        return self.character

    def to_nfa_design(self):
        start_state = object()
        accept_state = object()
        rule = FARule(start_state, self.character, accept_state)
        rulebool = NFARulebook([rule])
        return NFADesign(start_state, [accept_state], rulebool)

class Concatenate(Pattern):
    def __init__(self, first, second):
        Pattern.__init__(self, 1)
        self.first = first
        self.second = second

    def __str__(self):
        return ''.join([pattern.bracket(self.precedence)
                        for pattern in (self.first, self.second)])

    def to_nfa_design(self):
        first_nfa_design = self.first.to_nfa_design()
        second_nfa_design = self.second.to_nfa_design()
        
        start_state = first_nfa_design.start_state
        accept_states = second_nfa_design.accept_states
        rules = first_nfa_design.rulebook.rules + \
                second_nfa_design.rulebook.rules
        extra_rules = list(map(
            lambda state: FARule(state, None, second_nfa_design.start_state),
            first_nfa_design.accept_states))
        rulebook = NFARulebook(rules + extra_rules)
        return NFADesign(start_state, accept_states, rulebook)

class Choose(Pattern):
    def __init__(self, first, second):
        Pattern.__init__(self, 0)
        self.first = first
        self.second = second

    def __str__(self):
        return '|'.join(map(lambda pattern: pattern.bracket(self.precedence),
                            (self.first, self.second)))

    def to_nfa_design(self):
        first_nfa_design = self.first.to_nfa_design()
        second_nfa_design = self.second.to_nfa_design()
        start_state = object()
        accept_states = first_nfa_design.accept_states + \
                        second_nfa_design.accept_states
        rules = first_nfa_design.rulebook.rules + \
                second_nfa_design.rulebook.rules
        extra_rules = [FARule(start_state, None, nfa_design.start_state)
                       for nfa_design in (first_nfa_design, second_nfa_design)]
        rulebook = NFARulebook(rules + extra_rules)
        return NFADesign(start_state, accept_states, rulebook)

class Repeat(Pattern):
    def __init__(self, pattern):
        Pattern.__init__(self, 2)
        self.pattern = pattern

    def __str__(self):
        return self.pattern.bracket(self.precedence) + '*'

    def to_nfa_design(self):
        pattern_nfa_design = self.pattern.to_nfa_design()
        start_state = object()
        accept_states = pattern_nfa_design.accept_states + [start_state]
        rules = pattern_nfa_design.rulebook.rules
        extra_rules = [FARule(accept_state, None,
                              pattern_nfa_design.start_state)
                       for accept_state in pattern_nfa_design.accept_states]
        extra_rules += [FARule(start_state, None,
                               pattern_nfa_design.start_state)]
        rulebook = NFARulebook(rules + extra_rules)
        return NFADesign(start_state, accept_states, rulebook)
                           

if __name__ == '__main__':
    nfa_design = Empty().to_nfa_design()
    print(nfa_design)
    print(nfa_design.is_accepts(''))
    print(nfa_design.is_accepts('a'))
    nfa_design = Literal('a').to_nfa_design()
    print(nfa_design)
    print(nfa_design.is_accepts(''))
    print(nfa_design.is_accepts('a'))
    print(nfa_design.is_accepts('b'))
    print()

    print(Empty().is_matches('a'))
    print(Literal('a').is_matches('a'))
    print()

    pattern = Concatenate(Literal('a'), Literal('b'))
    print(pattern)
    print(pattern.is_matches('a'))
    print(pattern.is_matches('ab'))
    print(pattern.is_matches('abc'))
    pattern = Concatenate(Literal('a'),
                          Concatenate(Literal('b'), Literal('c')))
    print(pattern)
    print(pattern.is_matches('a'))
    print(pattern.is_matches('ab'))
    print(pattern.is_matches('abc'))
    print()

    pattern = Choose(Literal('a'), Literal('b'))
    print(pattern)
    print(pattern.is_matches('a'))
    print(pattern.is_matches('b'))
    print(pattern.is_matches('c'))
    print()

    pattern = Repeat(Literal('a'))
    print(pattern)
    print(pattern.is_matches(''))
    print(pattern.is_matches('a'))
    print(pattern.is_matches('aaaa'))
    print(pattern.is_matches('b'))

    # 以下、うまく動かなかった。Concatenate か Empty に問題がありそう。
    # pattern = Repeat(Concatenate(Literal('a'),
    #                              Choose(Empty(), Literal('b'))))
    # print(pattern)
    # print(pattern.is_matches(''))
    # print(pattern.is_matches('a'))
    # print(pattern.is_matches('ab'))
    # print(pattern.is_matches('aba'))
    # print(pattern.is_matches('abab'))
    # print(pattern.is_matches('abab'))
    # print(pattern.is_matches('abba'))

入出力結果(Terminal, IPython)

$ ./sample3_2.py
<__main__.NFADesign object at 0x10a7c3710>
True
False
<__main__.NFADesign object at 0x10a7c3828>
False
True
False

False
True

ab
False
True
False
abc
False
False
True

a|b
True
True
False

a*
True
True
True
False
$

0 コメント:

コメントを投稿

Comments on Google+: