← Back to branch summary

~ubuntu-branches/ubuntu/hardy/gnue-common/hardy

« back to all changes in this revision

Viewing changes to src/external/plex/DFA.py

  • Committer: Bazaar Package Importer
  • Author(s): Andrew Mitchell
  • Date: 2005-03-09 11:06:31 UTC
  • Revision ID: james.westby@ubuntu.com-20050309110631-8gvvn39q7tjz1kj6
Tags: upstream-0.5.14
Import upstream version 0.5.14

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/external/plex/DFA.py
 
1
#=======================================================================
 
2
#
 
3
#   Python Lexical Analyser
 
4
#
 
5
#   Converting NFA to DFA
 
6
#
 
7
#=======================================================================
 
8
 
 
9
import Machines
 
10
from Machines import LOWEST_PRIORITY
 
11
from Transitions import TransitionMap
 
12
 
 
13
def nfa_to_dfa(old_machine, debug = None):
 
14
  """
 
15
  Given a nondeterministic Machine, return a new equivalent
 
16
  Machine which is deterministic.
 
17
  """
 
18
  # We build a new machine whose states correspond to sets of states
 
19
  # in the old machine. Initially we add a new state corresponding to
 
20
  # the epsilon-closure of each initial old state. Then we give transitions
 
21
  # to each new state which are the union of all transitions out of any
 
22
  # of the corresponding old states. The new state reached on a given
 
23
  # character is the one corresponding to the set of states reachable
 
24
  # on that character from any of the old states. As new combinations of
 
25
  # old states are created, new states are added as needed until closure
 
26
  # is reached.
 
27
  new_machine = Machines.FastMachine()
 
28
  state_map = StateMap(new_machine)
 
29
  # Seed the process using the initial states of the old machine.
 
30
  # Make the corresponding new states into initial states of the new
 
31
  # machine with the same names.
 
32
  for (key, old_state) in old_machine.initial_states.items():
 
33
    new_state = state_map.old_to_new(epsilon_closure(old_state))
 
34
    new_machine.make_initial_state(key, new_state)
 
35
  # Tricky bit here: we add things to the end of this list while we're
 
36
  # iterating over it. The iteration stops when closure is achieved.
 
37
  for new_state in new_machine.states:
 
38
    transitions = TransitionMap()
 
39
    for old_state in state_map.new_to_old(new_state).keys():
 
40
      for event, old_target_states in old_state.transitions.items():
 
41
        if event and old_target_states:
 
42
          transitions.add_set(event, set_epsilon_closure(old_target_states))
 
43
    for event, old_states in transitions.items():
 
44
      new_machine.add_transitions(new_state, event, state_map.old_to_new(old_states))
 
45
  if debug:
 
46
    debug.write("\n===== State Mapping =====\n")
 
47
    state_map.dump(debug)
 
48
  return new_machine
 
49
 
 
50
def set_epsilon_closure(state_set):
 
51
  """
 
52
  Given a set of states, return the union of the epsilon
 
53
  closures of its member states.
 
54
  """
 
55
  result = {}
 
56
  for state1 in state_set.keys():
 
57
    for state2 in epsilon_closure(state1).keys():
 
58
      result[state2] = 1
 
59
  return result
 
60
 
 
61
def epsilon_closure(state):
 
62
  """
 
63
  Return the set of states reachable from the given state
 
64
  by epsilon moves.
 
65
  """
 
66
  # Cache the result
 
67
  result = state.epsilon_closure
 
68
  if result is None:
 
69
    result = {}
 
70
    state.epsilon_closure = result
 
71
    add_to_epsilon_closure(result, state)
 
72
  return result
 
73
 
 
74
def add_to_epsilon_closure(state_set, state):
 
75
  """
 
76
  Recursively add to |state_set| states reachable from the given state
 
77
  by epsilon moves.
 
78
  """
 
79
  if not state_set.get(state, 0):
 
80
    state_set[state] = 1
 
81
    state_set_2 = state.transitions.get_epsilon()
 
82
    if state_set_2:
 
83
      for state2 in state_set_2.keys():
 
84
        add_to_epsilon_closure(state_set, state2)
 
85
 
 
86
class StateMap:
 
87
  """
 
88
  Helper class used by nfa_to_dfa() to map back and forth between
 
89
  sets of states from the old machine and states of the new machine.
 
90
  """
 
91
  new_machine     = None # Machine
 
92
  old_to_new_dict = None # {(old_state,...) : new_state}
 
93
  new_to_old_dict = None # {id(new_state) : old_state_set}
 
94
 
 
95
  def __init__(self, new_machine):
 
96
    self.new_machine = new_machine
 
97
    self.old_to_new_dict = {}
 
98
    self.new_to_old_dict= {}
 
99
 
 
100
  def old_to_new(self, old_state_set):
 
101
    """
 
102
    Return the state of the new machine corresponding to the
 
103
    set of old machine states represented by |state_set|. A new
 
104
    state will be created if necessary. If any of the old states
 
105
    are accepting states, the new state will be an accepting state
 
106
    with the highest priority action from the old states.
 
107
    """
 
108
    key = self.make_key(old_state_set)
 
109
    new_state = self.old_to_new_dict.get(key, None)
 
110
    if not new_state:
 
111
      action = self.highest_priority_action(old_state_set)
 
112
      new_state = self.new_machine.new_state(action)
 
113
      self.old_to_new_dict[key] = new_state
 
114
      self.new_to_old_dict[id(new_state)] = old_state_set
 
115
      #for old_state in old_state_set.keys():
 
116
        #new_state.merge_actions(old_state)
 
117
    return new_state
 
118
  
 
119
  def highest_priority_action(self, state_set):
 
120
    best_action = None
 
121
    best_priority = LOWEST_PRIORITY
 
122
    for state in state_set.keys():
 
123
      priority = state.action_priority
 
124
      if priority > best_priority:
 
125
        best_action = state.action
 
126
        best_priority = priority
 
127
    return best_action
 
128
  
 
129
#       def old_to_new_set(self, old_state_set):
 
130
#               """
 
131
#               Return the new state corresponding to a set of old states as
 
132
#               a singleton set.
 
133
#               """
 
134
#               return {self.old_to_new(old_state_set):1}
 
135
 
 
136
  def new_to_old(self, new_state):
 
137
    """Given a new state, return a set of corresponding old states."""
 
138
    return self.new_to_old_dict[id(new_state)]
 
139
 
 
140
  def make_key(self, state_set):
 
141
    """
 
142
    Convert a set of states into a uniquified
 
143
    sorted tuple suitable for use as a dictionary key.
 
144
    """
 
145
    lst = state_set.keys()
 
146
    lst.sort()
 
147
    return tuple(lst)
 
148
 
 
149
  def dump(self, file):
 
150
    from Transitions import state_set_str
 
151
    for new_state in self.new_machine.states:
 
152
      old_state_set = self.new_to_old_dict[id(new_state)]
 
153
      file.write("   State %s <-- %s\n" % (
 
154
        new_state['number'], state_set_str(old_state_set)))
 
155
    
 
156