開発環境
- 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 コメント:
コメントを投稿