Mercurial > lcfOS
diff python/pyburg.py @ 320:84d67cce67b7
Working burg
author | Windel Bouwman |
---|---|
date | Sun, 19 Jan 2014 16:09:44 +0100 |
parents | 8d07a4254f04 |
children | 8c569fbe60e4 |
line wrap: on
line diff
--- 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: