import sys
try:
    dateiname = sys.argv[1]
except:
    dateiname = 'divmod1.py'
datei = open(dateiname,'r')
inhalt = datei.read()
datei.close()

import ply.lex as lex

reserved = {'while' : 'WHILE',
            'if'    : 'IF',
            'else'  : 'ELSE',
            'pass'  : 'PASS'}

tokens = ['VAR','NUM','END','OP'] + list(reserved.values())                       
literals = "=:+-"
    
def t_IGN(t):
    r'print\(.*'
    # kein return, damit die Zeile vom Parser nicht gesehen wird
   
def t_VAR(t):
    r'[a-zA-Z_][a-zA-Z_0-9]*'
    t.type = reserved.get(t.value,'VAR')
    return t                             

def t_NUM(t):
    r'\d+'
    t.value = int(t.value)
    return t

def t_END(t):
    r'\#end'
    return t

def t_OP(t):
    r'<=?|>=?|==|!='
    return t

def t_newline(t):
    r'\n+'
    t.lexer.lineno = t.lexer.lineno + len(t.value)

t_ignore  = ' \t'

def t_error(t):
    print('Unerwartetes Zeichen:',t.value[0],',Zeile:',s.lineno)
    t.lexer.skip(1)

s = lex.lex()

vz = 0            # Variablenzaehler
symtab = []       # Symboltabelle
hvz = 0           # Hilfsvariablenzaehler
htab = []         # Hilfsvariablentabelle
ersetzt = {}      # Dictionary fuer Ersetzungen
benutzt = set([]) # Menge, die die Namen der benutzten Hilfvariablen enthält

def var_in(tab,v):
    """
    True genau dann, wenn v bereits in der Tabelle tab
    """
    i = 0
    while i < vz:
        if tab[i][1] == v:
            return True
        else:
            i = i + 1
    return False

def indextab(tab,stelle,wert):
    """
    liefert den Index des Elements in der Tabelle tab,
    bei dem an der Stelle stelle wert steht,
    -1 bedeutet, dass so ein Element nicht existiert
    """
    i = 0
    while i < len(tab):
        if tab[i][stelle] == wert:
            return i
        else:
            i = i + 1
    return -1

def Hilfsvariable():
    """
    sucht die erste freie Hilfsvariable in der globalen Tabelle htab,
    falls keine gefunden wird, so wird die Tabelle erweitert,
    Rueckgabe ist der Name der Hilfsvariablen
    """
    global hvz,htab
    nr = indextab(htab,3,'frei')
    if nr > -1:
        htab[nr][3] = 'belegt'
        return htab[nr][1]          
    else:
        hvz = hvz + 1
        h = '__h'+str(hvz)
        htab.append([hvz,h,0,'belegt'])
        return h

def Hilfsvariable_markieren(h,markierung):
    """
    markiert die Hilfsvariable h in htab mit markierung,
    h muss in htab vorkommen
    """
    global htab
    nr = indextab(htab,1,h)
    htab[nr][3] = markierung

def in_symtab(v,wert):
    """
    fuegt v mit ihrem wert in Symboltabelle ein,
    wenn v nicht in der Symboltabelle ist
    """
    global vz,symtab
    if not var_in(symtab,v):
        vz = vz+1
        symtab.append((vz,v,wert))  
        
def error_symtab(v):
    """
    erzeugt einen Fehler, wenn v nicht in der Symboltabelle ist
    """
    if not var_in(symtab,v):
        print('Fehler: Variable nicht in Symboltabelle')
        raise SyntaxError

import ply.yacc as yacc

def p_0(p):
    "start : kette"
    p[0] = p[1]+['hlt']
    # print("start : kette",p[0])

def p_1(p):
    'kette : befehl kette'
    p[0] = p[1]+p[2]
    # print('kette : befehl kette',p[0])

def p_2(p):
    'kette :'
    p[0] = []
    # print('kette :',p[0])

def p_3(p):
    'befehl : whileAnw'
    p[0] = p[1]
    # print('befehl : whileAnw',p[0])

def p_4(p):
    'befehl : ifAnw'
    p[0] = p[1]
    # print('befehl : ifAnw',p[0])    

def p_5(p):
    'befehl : zuw'
    p[0] = p[1]
    # print('befehl : zuw',p[0])

def p_6(p):
    'befehl : PASS'
    p[0] = []
    # print('befehl : PASS',p[0])



def p_9(p):
    "whileAnw : WHILE cond ':' kette END"
    cond = p[2]
    kette = p[4]
    lk = len(kette)
    if cond[0] == 'von':
        if cond[3] != 0:
            print('Es wird nur der Vergleich mit Null unterstützt.')
            raise SyntaxError
        elif cond[2] == '<':  # immer False
            p[0] = []
        elif cond[2] == '>=': # immer True
            p[0] = kette+['jmp ('+str(-lk)+')']
        else:
            a = cond[1]
            error_symtab(a)
            if cond[2] in ['<=','==']:
                p[0] = ['tst '+a,'jmp ('+str(+lk+2)+')']+kette+['jmp ('+str(-lk-2)+')']
            else:
                p[0] = ['tst '+a,'jmp (+2)','jmp ('+str(lk+2)+')']+\
                        kette+['jmp ('+str(-lk-3)+')']
    else:                        # Fall 'vov'
        h1 = Hilfsvariable()
        #print('Eintrag in Hilfsvariablentabelle: ',htab[-1]) # DEBUG
        h2 = Hilfsvariable()
        #print('Eintrag in Hilfsvariablentabelle: ',htab[-1]) # DEBUG
        d = {'==':(10,8,6),'!=':(9,9,5),'<':(9,9,6),
             '>':(10,9,5),'<=':(9,8,6),'>=':(10,9,5)}
        a = cond[1]
        error_symtab(a)
        b = cond[3]
        error_symtab(b)
        op = cond[2]
        testcode = [['tst '+a,['malloc '+h1,'malloc '+h2]],
                    'jmp (+4)','tst '+b,'jmp ('+str(d[op][0])+')',
                    'jmp ('+str(d[op][1])+')','tst '+b,'jmp (+2)',
                    'jmp ('+str(d[op][2])+')','dec '+a,'dec '+b,'inc '+h2,
                    'jmp (-11)','inc '+h1,'tst '+h2,'jmp (+2)','jmp (+5)',
                    'dec '+h2,'inc '+a,'inc '+b,['jmp (-6)',['free '+h2]]]
        ltest = len(testcode)
        if type(kette[0]) == list:
            kette[0][1] = kette[0][1]+['free '+h1]
        else:
            kette[0] = [kette[0],['free '+h1]]
        p[0] = testcode + ['tst '+h1,'jmp (+2)','jmp ('+str(lk+3)+')']+\
                           ['dec '+h1]+kette+\
                           ['jmp ('+str(-lk-4-ltest)+')']
                          
    # print("whileAnw : WHILE cond ':' kette END",p[0])
    
def p_10(p):
    "ifAnw : IF cond ':' kette ELSE ':' kette END"
    cond = p[2]
    kette1 = p[4]
    lk1 = len(kette1)
    kette2 = p[7]
    lk2 = len(kette2)
    if cond[0] == 'von':
        if cond[3] != 0:
            print('Es wird nur der Vergleich mit Null unterstützt.')
            raise SyntaxError
        elif cond[2] == '<':
            p[0] = kette2
        elif cond[2] == '>=':
            p[0] = kette1
        else:
            if cond[2] in ['<=','==']:
                p[0] = ['tst '+cond[1],'jmp ('+str(lk1+2)+')']+kette1+\
                       ['jmp ('+str(lk2+1)+')']+kette2
            else:
                p[0] = ['tst '+cond[1],'jmp (+2)','jmp ('+str(lk1+2)+')']+\
                       kette1+['jmp ('+str(lk2+1)+')']+kette2
    else:                        # Fall 'vov'
        h1 = Hilfsvariable()
        #print('Eintrag in Hilfsvariablentabelle: ',htab[-1]) # DEBUG
        h2 = Hilfsvariable()
        #print('Eintrag in Hilfsvariablentabelle: ',htab[-1]) # DEBUG
        d = {'==':(10,8,6),'!=':(9,9,5),'<':(9,9,6),
             '>':(10,9,5),'<=':(9,8,6),'>=':(10,9,5)}
        a = cond[1]
        error_symtab(a)
        b = cond[3]
        error_symtab(b)
        op = cond[2]
        testcode = [['tst '+a,['malloc '+h1,'malloc '+h2]],
                    'jmp (+4)','tst '+b,'jmp ('+str(d[op][0])+')',
                    'jmp ('+str(d[op][1])+')','tst '+b,'jmp (+2)',
                    'jmp ('+str(d[op][2])+')','dec '+a,'dec '+b,'inc '+h2,
                    'jmp (-11)','inc '+h1,'tst '+h2,'jmp (+2)','jmp (+5)',
                    'dec '+h2,'inc '+a,'inc '+b,['jmp (-6)',['free '+h2]]]
        if type(kette1[0]) == list:
            kette1[0][1] = kette1[0][1]+['free '+h1]
        else:
            kette1[0] = [kette1[0],['free '+h1]]
        p[0] = testcode + ['tst '+h1,'jmp (+2)','jmp ('+str(lk1+3)+')']+\
                           ['dec '+h1]+kette1+\
                           ['jmp ('+str(lk2+1)+')']+kette2
    # print("ifAnw : IF cond ':' kette ELSE ':' kette END",p[0])
      
def p_11(p):
    "cond : VAR OP VAR"
    p[0] = ('vov',p[1],p[2],p[3])
    # print("cond : VAR OP VAR",p[0])
        
def p_12(p):
    'cond : VAR OP NUM'
    p[0] = ('von',p[1],p[2],p[3])
    # print('cond : VAR OP NUM',p[0])

def p_13(p):
    'cond : NUM OP VAR'
    op = p[2]
    if op == '<':
        op = '>'
    if op == '>':
        op = '<'
    if op == '<=':
        op = '>='
    if op == '>=':
        op = '<='
    p[0] = ('von',p[3],op,p[1])
    # print('cond : NUM OP VAR',p[0])

def p_14(p):
    "zuw : VAR '=' ausdruck"
    global vz, symtab
    
    def copy(b,a):
        """
        b -> a
        """
        h = Hilfsvariable() # Hilfsvariable anfordern
        #print('Eintrag in Hilfsvariablentabelle: ',htab[-1]) # DEBUG
        copycode = [['tst '+a,['malloc '+h]],
                    'jmp (+2)','jmp (+3)','dec '+a,'jmp (-4)',
                    'tst '+b,'jmp (+2)','jmp (+5)','dec '+b,'inc '+a,'inc '+h,'jmp (-6)',
                    'tst '+h,'jmp (+2)','jmp (+4)','dec '+h,'inc '+b,
                    ['jmp (-5)',['free '+h]]]
        return copycode
 
    bef = {'+':'inc ','-':'dec '}
    
    def incdec(a,op,b):
        """
        a = a op b, op aus ['+','-']
        """
        h = Hilfsvariable() # Hilfsvariable anfordern
        #print('Eintrag in Hilfsvariablentabelle: ',htab[-1]) # DEBUG
        incdeccode = [['tst '+b,['malloc '+h]],
                      'jmp (+2)','jmp (+5)','dec '+b,bef[op]+a,'inc '+h,'jmp (-6)',
                      'tst '+h,'jmp (+2)','jmp (+4)','dec '+h,'inc '+b,
                      ['jmp (-5)',['free '+h]]]
        return incdeccode

        
    # je nach Art des Ausdruck erfolgt eigene Behandlung
    # moegliche Arten: 'n','v','v+n'
    a = p[1]
    if p[3][0] == 'n':  # initiale Zuweisung
        in_symtab(a,p[3][1])
        # print('Eintrag in Symboltabelle: ',symtab[-1])
        p[0] = []
    elif p[3][0] == 'v':           # Kopieren
        b = p[3][1]
        error_symtab(b)
        if not var_in(symtab,a):
            in_symtab(a,0)
            h = Hilfsvariable() # Hilfsvariable anfordern
            p[0] = [['tst '+b,['malloc '+h]],
                      'jmp (+2)','jmp (+5)','dec '+b,'inc '+a,'inc '+h,'jmp (-6)',
                      'tst '+h,'jmp (+2)','jmp (+4)','dec '+h,'inc '+b,
                      ['jmp (-5)',['free '+h]]]
        else:
            p[0] = copy(b,a)
    elif p[3][0] == 'von':         # Addieren/Subtrahieren einer Konstanten
        in_symtab(a,0)
        b = p[3][1]
        error_symtab(b)
        op = p[3][2]
        n = p[3][3]
        # eventuell if not var_in(symtab,a) ..... wie oben einbauen
        if a != b:                 # eventuell zuerst a = b
            p[0] = copy(b,a)
        else:
            p[0] = []
        for i in range(n):
            p[0] = p[0]+[bef[op]+a]
    elif p[3][0] == 'vov':         # Addieren/Subtrahieren einer Variablen
        in_symtab(a,0)
        b = p[3][1]
        error_symtab(b)
        c = p[3][3]
        error_symtab(c)
        op = p[3][2]
        if a != b:                 # eventuell zuerst a = b
            p[0] = copy(b,a)
        else:
            p[0] = []
        p[0] = p[0]+incdec(a,op,c) # a = a op c
    else:
        print('Fehler: unerwarteter Ausdruck')
    # print("zuw : VAR '=' ausdruck",p[0])

def p_15(p):
    'ausdruck : NUM'
    p[0] = ('n',p[1])
    # print('ausdruck : NUM',p[0])

def p_16(p):
    'ausdruck : VAR'
    p[0] = ('v',p[1])
    # print('ausdruck : VAR',p[0])

def p_17(p):
    "ausdruck : VAR '+' NUM"
    p[0] = ('von',p[1],p[2],p[3])
    # print("ausdruck : VAR '+' NUM",p[0])

def p_18(p):
    "ausdruck : VAR '-' NUM"
    p[0] = ('von',p[1],p[2],p[3])
    # print("ausdruck : VAR '-' NUM",p[0])

def p_19(p):
    "ausdruck : NUM '+' VAR"
    p[0] = ('von',p[3],p[2],p[1])
    # print("ausdruck : NUM '+' VAR",p[0])

def p_20(p):
    "ausdruck : VAR '+' VAR"
    p[0] = ('vov',p[1],p[2],p[3])
    # print("ausdruck : VAR '+' VAR",p[0])
          
def p_21(p):
    "ausdruck : VAR '-' VAR"
    p[0] = ('vov',p[1],p[2],p[3])
    # print("ausdruck : VAR '-' VAR",p[0])

def p_error(p):
    print('Syntaxfehler in Zeile:',s.lineno)

p = yacc.yacc()


prog = p.parse(inhalt)

# Speicherbelegung optimieren
# ganz htab als frei markieren
for x in htab:
    Hilfsvariable_markieren(x[1],'frei')
# prog durchgehen
prog2 = []
for bef in prog:
    if type(bef) == list:
        befehl = bef[0]
        for x in bef[1]:
            opcode = x[0:4]
            if opcode == 'mall':
                hvalt = x[7:]
                hvneu = Hilfsvariable()
                ersetzt.update({hvalt:hvneu})
                benutzt = benutzt|{hvneu}
                # print('malloc',ersetzt,benutzt) # DEBUG
            else:
                hvalt = x[5:]
                # print('free',ersetzt,benutzt) # DEBUG
                hvneu = ersetzt[hvalt]
                Hilfsvariable_markieren(hvneu,'frei')
                if hvalt in ersetzt:
                    ersetzt.pop(hvalt)
    else:
        befehl = bef
    opcode = befehl[0:4]
    if opcode in ['inc ','dec ','tst ']: 
        hv = befehl[4:]
        if hv in ersetzt:
            prog2 = prog2+[opcode+ersetzt[hv]]
        else:
            prog2 = prog2+[opcode+hv]
    else:
        prog2 = prog2+[befehl]
prog = prog2

# unnoetige Hilfsvariablen aus htab loeschen
htab2 = []
for hv in htab:
    if hv[1] in benutzt:
        htab2 = htab2 + [hv]        
htab = htab2        
# Hilfsvariablen an Symboltabelle anhaengen
for h in htab:
    vz = vz+1
    symtab = symtab+[(vz,h[1],h[2])]

# Symboltabelle einarbeiten und relative Adressen durch absolute ersetzen
prog2 = []
for nr in range(len(prog)):
    bef = prog[nr]
    opcode = bef[0:4]
    address = bef[4:]
    if opcode in ['inc ','dec ','tst ']:
        i = indextab(symtab,1,address)
        prog2 = prog2+[opcode+str(symtab[i][0])]
    elif opcode == 'jmp ':
        prog2 = prog2+['jmp '+str(nr+1+int(address[1:-1]))]
    else:
        prog2 = prog2+[bef]

# for i in range(len(prog2)):     # DEBUG
#    print(i+1,prog2[i],prog[i])  # DEBUG

prog = prog2        
# print(prog) # DEBUG
               
# Ausgabedatei erzeugen
ausgabename = dateiname.split('.')[0]+'.bon'
datei = open(ausgabename,'w')
for bef in prog:
    # print(bef)
    datei.write(str.upper(bef)+'\n')
for v in symtab:
    datei.write('#'+str(v[2])+'\n')
for v in symtab:
    datei.write(';'+v[1]+' '+str(v[2])+'\n')
datei.close()
datei = open(ausgabename,'r') # DEBUG
inhalt = datei.read()         # DEBUG
datei.close()                 # DEBUG
print(inhalt)                 # DEBUG