Mercurial > lcfOS
changeset 320:84d67cce67b7
Working burg
| author | Windel Bouwman |
|---|---|
| date | Sun, 19 Jan 2014 16:09:44 +0100 |
| parents | 8d07a4254f04 |
| children | 8c569fbe60e4 |
| files | python/arm.pb python/pyburg.py python/tree.py |
| diffstat | 3 files changed, 61 insertions(+), 33 deletions(-) [+] |
line wrap: on
line diff
--- a/python/arm.pb Sat Jan 18 18:58:43 2014 +0100 +++ b/python/arm.pb Sun Jan 19 16:09:44 2014 +0100 @@ -4,17 +4,17 @@ %% -stmt: ASGNI(disp, reg) 1 (. .) +stmt: ASGNI(disp, reg) 1 (. print('ASGNI') .) stmt: reg 0 (. .) -reg: ADDI(reg, rc) 1 (. self.emit(Add, src=[$1], dst=[$c], other=[$2]) .) +reg: ADDI(reg, rc) 1 (. print('ADDI(reg, rc)') .) reg: CVCI(INDIRC(disp)) 1 (. .) reg: IOI 0 (. .) reg: disp 1 (. .) disp: ADDI(reg, con) 1 (. .) -disp: ADDRLP 0 (. .) +disp: ADDRLP 0 (. print('ADDRLP') .) rc: con 0 (. .) rc: reg 0 (. .) -con: CNSTI 0 (. .) +con: CNSTI 0 (. print('CNSTI') .) con: IOI 0 (. .)
--- a/python/pyburg.py Sat Jan 18 18:58:43 2014 +0100 +++ b/python/pyburg.py Sun Jan 19 16:09:44 2014 +0100 @@ -23,6 +23,12 @@ The 'a' in the example above indicates an open connection to a next tree pattern. + In the example above 'reg' is a non-terminal. ADDI32 is a terminal. non-terminals + cannot have child nodes. A special case occurs in this case: + reg -> rc + where 'rc' is a non-terminal. This is an example of a chain rule. Chain rules + can be used to allow several variants of non-terminals. + The generated matcher uses dynamic programming to find the best match of the tree. This strategy consists of two steps: - label: During this phase the given tree is traversed in a bottom up way. @@ -76,6 +82,8 @@ class Rule: + """ A rewrite rule. Specifies a tree that can be rewritten into a result + at a specific cost """ def __init__(self, non_term, tree, cost, template): self.non_term = non_term self.tree = tree @@ -99,7 +107,7 @@ class Nonterm(Symbol): def __init__(self, name): super().__init__(name) - self.rules = [] + self.chain_rules = [] class BurgSystem: @@ -116,7 +124,13 @@ non_terminals = property(lambda s: s.symType(Nonterm)) def add_rule(self, non_term, tree, cost, template): + template = template[2:-2].strip() + if not template: + template = 'pass' rule = Rule(non_term, tree, cost, template) + if len(tree.children) == 0 and tree.name not in self.terminals: + print('chain:', rule) + self.non_term(tree.name).chain_rules.append(rule) self.non_term(rule.non_term) self.rules.append(rule) rule.nr = len(self.rules) @@ -126,7 +140,7 @@ raise BurgError('Cannot redefine terminal') if not self.goal: self.goal = name - self.install(name, Nonterm) + return self.install(name, Nonterm) def tree(self, name, *args): return Tree(name, *args) @@ -135,9 +149,9 @@ assert type(name) is str if name in self.symbols: assert type(self.symbols[name]) is t - return self.symbols[name] else: self.symbols[name] = t(name) + return self.symbols[name] def add_terminal(self, terminal): self.install(terminal, Term) @@ -169,23 +183,33 @@ self.print('from tree import Tree, BaseMatcher, State') self.print() self.print('class Matcher(BaseMatcher):') - self.print(' def __init__(self):') - self.print(' self.kid_functions = {}') - self.print(' self.nts_map = {}') + self.print(' def __init__(self):') + self.print(' self.kid_functions = {}') + self.print(' self.nts_map = {}') + self.print(' self.pat_f = {}') for rule in self.system.rules: kids, dummy = self.compute_kids(rule.tree, 't') + rule.num_nts = len(dummy) lf = 'lambda t: [{}]'.format(', '.join(kids), rule) - self.print(' # {}'.format(rule)) - self.print(' self.kid_functions[{}] = {}'.format(rule.nr, lf)) - self.print(' self.nts_map[{}] = {}'.format(rule.nr, dummy)) - self.print('') + pf = 'self.P{}'.format(rule.nr) + self.print(' # {}: {}'.format(rule.nr, rule)) + self.print(' self.kid_functions[{}] = {}'.format(rule.nr, lf)) + self.print(' self.nts_map[{}] = {}'.format(rule.nr, dummy)) + self.print(' self.pat_f[{}] = {}'.format(rule.nr, pf)) + self.print() + for rule in self.system.rules: + if rule.num_nts > 0: + args = ', ' + ', '.join('nt{}'.format(x) for x in range(rule.num_nts)) + else: + args = '' + self.print(' def P{}(self{}):'.format(rule.nr, args)) + self.print(' {}'.format(rule.template)) self.emit_state() - self.print() - self.print(' def gen(self, tree):') - self.print(' self.burm_label(tree)') - self.print(' if not tree.state.has_goal("{}"):'.format(self.system.goal)) - self.print(' raise Exception("Tree not covered")') - self.print(' self.apply_rules(tree, "{}")'.format(self.system.goal)) + self.print(' def gen(self, tree):') + self.print(' self.burm_label(tree)') + self.print(' if not tree.state.has_goal("{}"):'.format(self.system.goal)) + self.print(' raise Exception("Tree not covered")') + self.print(' self.apply_rules(tree, "{}")'.format(self.system.goal)) def emit_record(self, rule, state_var): # TODO: check for rules fullfilled (by not using 999999) @@ -193,11 +217,14 @@ self.print(' kids = self.kids(tree, {})'.format(rule.nr)) self.print(' c = sum(x.state.get_cost(y) for x, y in zip(kids, nts)) + {}'.format(rule.cost)) self.print(' tree.state.set_cost("{}", c, {})'.format(rule.non_term, rule.nr)) + for cr in self.system.symbols[rule.non_term].chain_rules: + self.print(' # Chain rule: {}'.format(cr)) + self.print(' tree.state.set_cost("{}", c + {}, {})'.format(cr.non_term, cr.cost, cr.nr)) def emit_state(self): """ Emit a function that assigns a new state to a node """ - self.print(' def burm_state(self, tree):') - self.print(' tree.state = State()') + self.print(' def burm_state(self, tree):') + self.print(' tree.state = State()') for term in self.system.terminals: self.emitcase(term) self.print() @@ -206,15 +233,9 @@ rules = [rule for rule in self.system.rules if rule.tree.name == term] for rule in rules: condition = self.emittest(rule.tree, 'tree') - self.print(' if {}:'.format(condition)) + self.print(' if {}:'.format(condition)) self.emit_record(rule, 'state') - def emit_closure(self): - for non_terminal in self.system.non_terminals: - self.print('def closure_{}(self, c):'.format(non_terminal)) - self.print(' pass') - self.print() - def compute_kids(self, t, root_name): """ Compute of a pattern the blanks that must be provided from below in the tree """ if t.name in self.system.non_terminals:
--- a/python/tree.py Sat Jan 18 18:58:43 2014 +0100 +++ b/python/tree.py Sun Jan 19 16:09:44 2014 +0100 @@ -14,15 +14,19 @@ class State: + """ State used to label tree nodes """ def __init__(self): self.labels = {} + def has_goal(self, goal): return goal in self.labels + def get_cost(self, goal): - if not self.has_goal(goal): return 999999 return self.labels[goal][0] + def get_rule(self, goal): return self.labels[goal][1] + def set_cost(self, goal, cost, rule): if self.has_goal(goal): if self.get_cost(goal) > cost: @@ -30,7 +34,9 @@ else: self.labels[goal] = (cost, rule) + class BaseMatcher: + """ Base class for matcher objects. """ def kids(self, tree, rule): return self.kid_functions[rule](tree) @@ -38,12 +44,13 @@ return self.nts_map[rule] def burm_label(self, tree): + """ Label all nodes in the tree bottom up """ for c in tree.children: self.burm_label(c) self.burm_state(tree) def apply_rules(self, tree, goal): - print(tree.state.get_rule(goal)) rule = tree.state.get_rule(goal) - for kid_tree, kid_goal in zip(self.kids(tree, rule), self.nts(rule)): - self.apply_rules(kid_tree, kid_goal) + results = [self.apply_rules(kid_tree, kid_goal) + for kid_tree, kid_goal in zip(self.kids(tree, rule), self.nts(rule))] + self.pat_f[rule](*results)