diff -r ca2d1c23da5f -r 3d2eea446705 smm.py --- a/smm.py Mon May 16 22:35:49 2011 +0200 +++ b/smm.py Tue May 17 02:19:11 2011 +0200 @@ -20,66 +20,73 @@ RB = ")" class Operator(object): - def __init__(self, id, values): - self.id = id + def __init__(self, id, arity, values): + self.id = id + self.arity = arity self.values = values def __str__(self): - values = "" - if len(self.values): - values = "(" + "".join([str(v) for v in self.values]) + ")" - return self.id + values + out = self.id + if self.arity == 0: + out = str(self.values[0]) + if self.arity == 1: + out = self.id + str(self.values[0]) + elif self.arity == 2: + #print self.id + #print self.values + out = "(" + str(self.values[0]) + " " + self.id + " " + str(self.values[1]) + ")" + return out class Not(Operator): arity = 1 def __init__(self, values): - Operator.__init__(self, NOT, values) + Operator.__init__(self, NOT, Not.arity, values) def __call__(self): pass class And(Operator): arity = 2 def __init__(self, values): - Operator.__init__(self, AND, values) + Operator.__init__(self, AND, And.arity, values) class Or(Operator): arity = 2 def __init__(self, values): - Operator.__init__(self, OR, values) + Operator.__init__(self, OR, Or.arity, values) class Imp(Operator): arity = 2 def __init__(self, values): - Operator.__init__(self, IMP, values) + Operator.__init__(self, IMP, Imp.arity, values) class Eq(Operator): arity = 2 def __init__(self, values): - Operator.__init__(self, EQ, values) + Operator.__init__(self, EQ, Eq.arity, values) class Box(Operator): arity = 1 def __init__(self, values): - Operator.__init__(self, BOX, values) + Operator.__init__(self, BOX, Box.arity, values) class Diamond(Operator): arity = 1 def __init__(self, values): - Operator.__init__(self, DIAMOND, values) + Operator.__init__(self, DIAMOND, Diamond.arity, values) class Variable(Operator): arity = 0 def __init__(self, values): - Operator.__init__(self, VARIABLE, values) - + Operator.__init__(self, VARIABLE, Variable.arity, values) + class Lb(Operator): arity = -1 def __init__(self, values): - Operator.__init__(self, LB, values) + Operator.__init__(self, LB, Lb.arity, values) class Rb(Operator): arity = -1 def __init__(self, values): - Operator.__init__(self, RB, values) + Operator.__init__(self, RB, Rb.arity, values) class Formula(object): def __init__(self): @@ -101,12 +108,13 @@ self.tokens = tokens self.reset(source) def next(self): - while self.i < len(self.source): + while self.i < len(self.source): + re.purge() for p, token in self.tokens.iteritems(): m = p.match(self.source[self.i:]) if m: self.i += m.end(0) - value = m.group(0) + value = m.group(0) return (token, value) self.i += 1 return (None, None) @@ -160,29 +168,42 @@ (A, Variable, And): 5, (A, Variable, Or): 6, (A, Variable, Imp): 7, - (A, Variable, Eq): 8} + (A, Variable, Eq): 8, + (A, Not, Variable, And): 5, + (A, Not, Variable, Or): 6, + (A, Not, Variable, Imp): 7, + (A, Not, Variable, Eq): 8} stack = [S] tree_nodes = [] + tree = None out = [] self.scanner.reset(source) (token, value) = self.scanner.next() - (lookahead, _) = self.scanner.next() - accepted = True - while token and len(stack): + (lookahead, la_value) = self.scanner.next() + (lookahead2, la2_value) = self.scanner.next() + accepted = True + while token and len(stack): top = stack[-1] if top == token: - tree_nodes.append(stack.pop()) - token = lookahead - (lookahead, _) = self.scanner.next() + tree_nodes.append((token, value)) + stack.pop() + #tree_nodes.append((stack.pop(), value)) + (token, value) = (lookahead, la_value) + (lookahead, la_value) = (lookahead2, la2_value) + #(lookahead, _) = self.scanner.next() + (lookahead2, la2_value) = self.scanner.next() else: action = None if (top, token) in table: action = table[(top, token)] elif (top, token, lookahead) in table: - action = table[(top, token, lookahead)] + action = table[(top, token, lookahead)] + elif (top, token, lookahead, lookahead2) in table: + action = table[(top, token, lookahead, lookahead2)] if action is None: accepted = False break + out.append(action) stack.pop() stack.extend(reversed(self.syntax[action])) @@ -190,23 +211,65 @@ return (accepted, out, tree_nodes) class SyntaxTree(object): - def __init__(self, tree_nodes): - self.root = self.compile(tree_nodes) - def compile(self, tree_nodes): + def __init__(self, seq, tree_nodes): + seq.reverse() + tree_nodes.reverse() + print tree_nodes + print seq + self.root = self.compile(seq, tree_nodes)[0] + print self.root + def compile(self, seq, tree_nodes): + stack = [] + waiting = [] + print seq + while len(seq): + s = seq.pop() + if s == 0: + c, v = tree_nodes.pop() + while c != Variable: + c, v = tree_nodes.pop() + stack.append(Variable(v)) + elif s == 1: + stack.append(Not(self.compile(seq, tree_nodes))) + elif s == 2: + stack.extend(self.compile(seq, tree_nodes)) + elif s == 3: + stack.append(Box(self.compile(seq, tree_nodes))) + elif s == 4: + stack.append(Diamond(self.compile(seq, tree_nodes))) + elif s == 5: + stack.append(And(self.compile(seq, tree_nodes))) + elif s == 6: + stack.append(Or(self.compile(seq, tree_nodes))) + elif s == 7: + stack.append(Imp(self.compile(seq, tree_nodes))) + elif s == 8: + stack.append(Eq(self.compile(seq, tree_nodes))) + print stack + return stack + + def compile_(self, tree_nodes): table = [] unfinished = [] node = None - for n in reversed(tree_nodes): + print tree_nodes + for n, v in (tree_nodes): + print + print n if n.arity >= 0: if len(table) < n.arity: + print "appending unfinished ", n unfinished.append(n) else: - args = table[:n.arity] + args = table[:n.arity] + if n.arity == 0: + args = [v] table = table[n.arity:] node = n(args) table.append(node) - if len(unfinished) and unfinished[-1].arity <= len(table): - n = unfinished[-1] + if len(unfinished) and unfinished[-1].arity <= len(table): + n = unfinished[-1] + print "finishing ", n args = table[:n.arity] table = table[n.arity:] node = n(args) @@ -220,8 +283,8 @@ scanner = Scanner(TOKENS) parser = Parser(SYNTAX, scanner) (accepted, out, tree_nodes) = parser.parse(args.formula) - tree = SyntaxTree(tree_nodes) - print tree.root + tree = SyntaxTree(out, tree_nodes) + #print tree.root from argparse import ArgumentParser