Mercurial > lcfOS

comparison python/pyburg.py @ 320:84d67cce67b7

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Working burg
author Windel Bouwman
date Sun, 19 Jan 2014 16:09:44 +0100
parents 8d07a4254f04
children 8c569fbe60e4
comparison
equal deleted inserted replaced
319:8d07a4254f04 320:84d67cce67b7
20 X(a, b, b) 20 X(a, b, b)
21 Trees can be nested: 21 Trees can be nested:
22 X(Y(a, a), a) 22 X(Y(a, a), a)
23 The 'a' in the example above indicates an open connection to a next tree 23 The 'a' in the example above indicates an open connection to a next tree
24 pattern. 24 pattern.
25
26 In the example above 'reg' is a non-terminal. ADDI32 is a terminal. non-terminals
27 cannot have child nodes. A special case occurs in this case:
28 reg -> rc
29 where 'rc' is a non-terminal. This is an example of a chain rule. Chain rules
30 can be used to allow several variants of non-terminals.
25 31
26 The generated matcher uses dynamic programming to find the best match of the 32 The generated matcher uses dynamic programming to find the best match of the
27 tree. This strategy consists of two steps: 33 tree. This strategy consists of two steps:
28 - label: During this phase the given tree is traversed in a bottom up way. 34 - label: During this phase the given tree is traversed in a bottom up way.
29 each node is labelled with a possible matching rule and the corresponding cost. 35 each node is labelled with a possible matching rule and the corresponding cost.
74 self.token = self.tokens.__next__() 80 self.token = self.tokens.__next__()
75 return t 81 return t
76 82
77 83
78 class Rule: 84 class Rule:
85 """ A rewrite rule. Specifies a tree that can be rewritten into a result
86 at a specific cost """
79 def __init__(self, non_term, tree, cost, template): 87 def __init__(self, non_term, tree, cost, template):
80 self.non_term = non_term 88 self.non_term = non_term
81 self.tree = tree 89 self.tree = tree
82 self.cost = cost 90 self.cost = cost
83 self.template = template 91 self.template = template
97 105
98 106
99 class Nonterm(Symbol): 107 class Nonterm(Symbol):
100 def __init__(self, name): 108 def __init__(self, name):
101 super().__init__(name) 109 super().__init__(name)
102 self.rules = [] 110 self.chain_rules = []
103 111
104 112
105 class BurgSystem: 113 class BurgSystem:
106 def __init__(self): 114 def __init__(self):
107 self.rules = [] 115 self.rules = []
114 terminals = property(lambda s: s.symType(Term)) 122 terminals = property(lambda s: s.symType(Term))
115 123
116 non_terminals = property(lambda s: s.symType(Nonterm)) 124 non_terminals = property(lambda s: s.symType(Nonterm))
117 125
118 def add_rule(self, non_term, tree, cost, template): 126 def add_rule(self, non_term, tree, cost, template):
127 template = template[2:-2].strip()
128 if not template:
129 template = 'pass'
119 rule = Rule(non_term, tree, cost, template) 130 rule = Rule(non_term, tree, cost, template)
131 if len(tree.children) == 0 and tree.name not in self.terminals:
132 print('chain:', rule)
133 self.non_term(tree.name).chain_rules.append(rule)
120 self.non_term(rule.non_term) 134 self.non_term(rule.non_term)
121 self.rules.append(rule) 135 self.rules.append(rule)
122 rule.nr = len(self.rules) 136 rule.nr = len(self.rules)
123 137
124 def non_term(self, name): 138 def non_term(self, name):
125 if name in self.terminals: 139 if name in self.terminals:
126 raise BurgError('Cannot redefine terminal') 140 raise BurgError('Cannot redefine terminal')
127 if not self.goal: 141 if not self.goal:
128 self.goal = name 142 self.goal = name
129 self.install(name, Nonterm) 143 return self.install(name, Nonterm)
130 144
131 def tree(self, name, *args): 145 def tree(self, name, *args):
132 return Tree(name, *args) 146 return Tree(name, *args)
133 147
134 def install(self, name, t): 148 def install(self, name, t):
135 assert type(name) is str 149 assert type(name) is str
136 if name in self.symbols: 150 if name in self.symbols:
137 assert type(self.symbols[name]) is t 151 assert type(self.symbols[name]) is t
138 return self.symbols[name]
139 else: 152 else:
140 self.symbols[name] = t(name) 153 self.symbols[name] = t(name)
154 return self.symbols[name]
141 155
142 def add_terminal(self, terminal): 156 def add_terminal(self, terminal):
143 self.install(terminal, Term) 157 self.install(terminal, Term)
144 158
145 159
167 181
168 self.print('#!/usr/bin/python') 182 self.print('#!/usr/bin/python')
169 self.print('from tree import Tree, BaseMatcher, State') 183 self.print('from tree import Tree, BaseMatcher, State')
170 self.print() 184 self.print()
171 self.print('class Matcher(BaseMatcher):') 185 self.print('class Matcher(BaseMatcher):')
172 self.print(' def __init__(self):') 186 self.print(' def __init__(self):')
173 self.print(' self.kid_functions = {}') 187 self.print(' self.kid_functions = {}')
174 self.print(' self.nts_map = {}') 188 self.print(' self.nts_map = {}')
189 self.print(' self.pat_f = {}')
175 for rule in self.system.rules: 190 for rule in self.system.rules:
176 kids, dummy = self.compute_kids(rule.tree, 't') 191 kids, dummy = self.compute_kids(rule.tree, 't')
192 rule.num_nts = len(dummy)
177 lf = 'lambda t: [{}]'.format(', '.join(kids), rule) 193 lf = 'lambda t: [{}]'.format(', '.join(kids), rule)
178 self.print(' # {}'.format(rule)) 194 pf = 'self.P{}'.format(rule.nr)
179 self.print(' self.kid_functions[{}] = {}'.format(rule.nr, lf)) 195 self.print(' # {}: {}'.format(rule.nr, rule))
180 self.print(' self.nts_map[{}] = {}'.format(rule.nr, dummy)) 196 self.print(' self.kid_functions[{}] = {}'.format(rule.nr, lf))
181 self.print('') 197 self.print(' self.nts_map[{}] = {}'.format(rule.nr, dummy))
198 self.print(' self.pat_f[{}] = {}'.format(rule.nr, pf))
199 self.print()
200 for rule in self.system.rules:
201 if rule.num_nts > 0:
202 args = ', ' + ', '.join('nt{}'.format(x) for x in range(rule.num_nts))
203 else:
204 args = ''
205 self.print(' def P{}(self{}):'.format(rule.nr, args))
206 self.print(' {}'.format(rule.template))
182 self.emit_state() 207 self.emit_state()
183 self.print() 208 self.print(' def gen(self, tree):')
184 self.print(' def gen(self, tree):') 209 self.print(' self.burm_label(tree)')
185 self.print(' self.burm_label(tree)') 210 self.print(' if not tree.state.has_goal("{}"):'.format(self.system.goal))
186 self.print(' if not tree.state.has_goal("{}"):'.format(self.system.goal)) 211 self.print(' raise Exception("Tree not covered")')
187 self.print(' raise Exception("Tree not covered")') 212 self.print(' self.apply_rules(tree, "{}")'.format(self.system.goal))
188 self.print(' self.apply_rules(tree, "{}")'.format(self.system.goal))
189 213
190 def emit_record(self, rule, state_var): 214 def emit_record(self, rule, state_var):
191 # TODO: check for rules fullfilled (by not using 999999) 215 # TODO: check for rules fullfilled (by not using 999999)
192 self.print(' nts = self.nts({})'.format(rule.nr)) 216 self.print(' nts = self.nts({})'.format(rule.nr))
193 self.print(' kids = self.kids(tree, {})'.format(rule.nr)) 217 self.print(' kids = self.kids(tree, {})'.format(rule.nr))
194 self.print(' c = sum(x.state.get_cost(y) for x, y in zip(kids, nts)) + {}'.format(rule.cost)) 218 self.print(' c = sum(x.state.get_cost(y) for x, y in zip(kids, nts)) + {}'.format(rule.cost))
195 self.print(' tree.state.set_cost("{}", c, {})'.format(rule.non_term, rule.nr)) 219 self.print(' tree.state.set_cost("{}", c, {})'.format(rule.non_term, rule.nr))
220 for cr in self.system.symbols[rule.non_term].chain_rules:
221 self.print(' # Chain rule: {}'.format(cr))
222 self.print(' tree.state.set_cost("{}", c + {}, {})'.format(cr.non_term, cr.cost, cr.nr))
196 223
197 def emit_state(self): 224 def emit_state(self):
198 """ Emit a function that assigns a new state to a node """ 225 """ Emit a function that assigns a new state to a node """
199 self.print(' def burm_state(self, tree):') 226 self.print(' def burm_state(self, tree):')
200 self.print(' tree.state = State()') 227 self.print(' tree.state = State()')
201 for term in self.system.terminals: 228 for term in self.system.terminals:
202 self.emitcase(term) 229 self.emitcase(term)
203 self.print() 230 self.print()
204 231
205 def emitcase(self, term): 232 def emitcase(self, term):
206 rules = [rule for rule in self.system.rules if rule.tree.name == term] 233 rules = [rule for rule in self.system.rules if rule.tree.name == term]
207 for rule in rules: 234 for rule in rules:
208 condition = self.emittest(rule.tree, 'tree') 235 condition = self.emittest(rule.tree, 'tree')
209 self.print(' if {}:'.format(condition)) 236 self.print(' if {}:'.format(condition))
210 self.emit_record(rule, 'state') 237 self.emit_record(rule, 'state')
211
212 def emit_closure(self):
213 for non_terminal in self.system.non_terminals:
214 self.print('def closure_{}(self, c):'.format(non_terminal))
215 self.print(' pass')
216 self.print()
217 238
218 def compute_kids(self, t, root_name): 239 def compute_kids(self, t, root_name):
219 """ Compute of a pattern the blanks that must be provided from below in the tree """ 240 """ Compute of a pattern the blanks that must be provided from below in the tree """
220 if t.name in self.system.non_terminals: 241 if t.name in self.system.non_terminals:
221 return [root_name], [t.name] 242 return [root_name], [t.name]