# HG changeset patch
# User Eugen Sawin <sawine@me73.com>
# Date 1305575030 -7200
# Node ID 710650dc4db6d62053d71c6692e60c3be1ad3a77
# Parent  a7ca3e23ff413a45935921efff67b8bcb3d0200b
Syntax tree construction.

diff -r a7ca3e23ff41 -r 710650dc4db6 smm.py
--- a/smm.py	Mon May 16 20:23:22 2011 +0200
+++ b/smm.py	Mon May 16 21:43:50 2011 +0200
@@ -21,50 +21,73 @@
 
 class Operator(object):
     def __init__(self, id):
-        self.id = id
+        self.id = id  
     def __str__(self):
         return self.id
 
 class Not(Operator):
-    def __init__(self):
+    arity = 1
+    def __init__(self, values):
         Operator.__init__(self, NOT)
+        self.value = values[0]
     def __call__(self):
         pass
 
 class And(Operator):
-    def __init__(self):
+    arity = 2
+    def __init__(self, values):
         Operator.__init__(self, AND)
-    
+        self.value = values
+
 class Or(Operator):
-    def __init__(self):
+    arity = 2
+    def __init__(self, values):
         Operator.__init__(self, OR)
-    
+        self.value = values
+
 class Imp(Operator):
+    arity = 2
     def __init__(self):
         Operator.__init__(self, IMP)
     
 class Eq(Operator):
+    arity = 2
     def __init__(self):
         Operator.__init__(self, EQ)
     
 class Box(Operator):
-    def __init__(self):
-        Operator.__init__(self,BOX )
-    
+    arity = 1
+    def __init__(self, values):
+        Operator.__init__(self, BOX)
+        self.value = values[0]
+
 class Diamond(Operator):
+    arity = 1
     def __init__(self):
         Operator.__init__(self, DIAMOND)
     
 class Variable(Operator):
-    def __init__(self):
+    arity = 0
+    def __init__(self, values):
         Operator.__init__(self, VARIABLE)
 
+class Lb(Operator):
+    arity = -1
+    def __init__(self, values):
+        Operator.__init__(self, LB)
+
+class Rb(Operator):
+    arity = -1
+    def __init__(self, values):
+        Operator.__init__(self, RB)
+
 class Formula(object):
-    def __init__(self, f):
-        self.f = f
+    def __init__(self):
+        pass
+        
 
-TOKENS = {re.compile("\("): LB,
-          re.compile("\)"): RB,
+TOKENS = {re.compile("\("): Lb,
+          re.compile("\)"): Rb,
           re.compile("~"): Not,
           re.compile("&"): And,
           re.compile("\|"): Or,
@@ -85,26 +108,27 @@
                 if m:                  
                     self.i += m.end(0)
                     value = m.group(0)
-                    return token
+                    return (token, value)
             self.i += 1
+        return (None, None)
     def reset(self, source):
         self.i = 0
         self.source = source
 
 S = Formula
 A = "A"
-#S: (Variable,),
-#S: (Not, S),
-#S: (LB, A, RB),
-#S: (Box, S),
-#S: (Diamond, S),
-#A: (S, And, S),
-#A: (S, Or, S),
-#A: (S, Imp, S),
-#A: (S, Eq, S)
+#0 S: (Variable,),
+#1 S: (Not, S),
+#2 S: (Lb, A, Rb),
+#3 S: (Box, S),
+#4 S: (Diamond, S),
+#5 A: (S, And, S),
+#6 A: (S, Or, S),
+#7 A: (S, Imp, S),
+#8 A: (S, Eq, S)
 SYNTAX = ((Variable,),
           (Not, S),
-          (LB, A, RB),
+          (Lb, A, Rb),
           (Box, S),
           (Diamond, S),
           (S, And, S),
@@ -112,6 +136,14 @@
           (S, Imp, S),
           (S, Eq, S))
 
+class Node(object):
+    def __init__(self, parent, value):
+        self.parent = parent
+        self.value = value
+        self.children = []
+    def addChild(self, value):
+        self.children.append(self, node)
+
 class Parser(object):
     def __init__(self, syntax, scanner):
         self.syntax = syntax
@@ -119,7 +151,7 @@
     def parse(self, source):
         table = {(S, Variable): 0,
                  (S, Not): 1,
-                 (S, LB): 2,
+                 (S, Lb): 2,
                  (S, Box): 3,
                  (S, Diamond): 4,
                  (A, S, And): 5,
@@ -131,11 +163,12 @@
                  (A, Variable, Imp): 7,
                  (A, Variable, Eq): 8}
         stack = [S]
+        trash = []
         out = []
         self.scanner.reset(source)
-        token = self.scanner.next()
-        lookahead = self.scanner.next()
-        accepted = True
+        (token, value) = self.scanner.next()
+        (lookahead, _) = self.scanner.next()
+        accepted = True      
         while token and len(stack):
             top = stack[-1]  
             #print
@@ -143,9 +176,9 @@
             #print "token ", token
             #print "lookahead ", lookahead            
             if top == token:
-                stack.pop()
+                trash.append(stack.pop())
                 token = lookahead
-                lookahead = self.scanner.next()
+                (lookahead, _) = self.scanner.next()
             else:
                 action = None
                 if (top, token) in table:
@@ -159,20 +192,48 @@
                 out.append(action)
                 stack.pop()
                 stack.extend(reversed(self.syntax[action]))
-        return (accepted and not len(stack), out)
-                
+        accepted = accepted and not len(stack)
+        return (accepted, out, trash)                
         
 
 def main():
     args = parse_arguments()
     scanner = Scanner(TOKENS)
     parser = Parser(SYNTAX, scanner)
-    print parser.parse(args.formula)
+    (accepted, out, trash) = parser.parse(args.formula)
+    print (accepted, out, trash)
+    table = []
+    unfinished = []
+    for t in reversed(trash):
+        if t.arity >= 0:
+            print "\nt ", t
+            print "arity ", t.arity
+            print "table ", table
+            if len(table) < t.arity:
+                unfinished.append(t)
+            else:
+                args = table[:t.arity]
+                print "args ", args
+                table = table[t.arity:]
+            
+                node = t(args)
+                print "node ", node
+                table.append(node)
+            if len(unfinished) and unfinished[-1].arity <= len(table):
+                args = table[:unfinished[-1].arity]
+                print "unfinished args ", args
+                table = table[unfinished[-1].arity:]
+                node = unfinished[-1](args)
+                print "unfinished node ", node
+                table.append(node)
+                unfinished.pop()
+
+    print "\n", table
 
 from argparse import ArgumentParser
 
 def parse_arguments():
-    parser = ArgumentParser(description="Parses Simple Modal Logic syntax.")
+    parser = ArgumentParser(description="Parses simple modal logic syntax.")
     parser.add_argument("formula", help="your formula") 
     return parser.parse_args()