whileinterpreter.py

import lexer
from loopinterpreter import LOOPInterpreter, ErrorHandler
import re
import signal
from IPython.display import clear_output
from copy import deepcopy

class Timeout:
    def __init__(self, time):
        self.time = time

    def __enter__(self):
        if self.time > 0:
            signal.signal(signal.SIGALRM, self.interrupt)
            signal.alarm(self.time)

    def __exit__(self, exc_type, exc_value, exc_traceback):
        signal.alarm(0)

    def interrupt(self, sig_num, stack_frame):
        try:
            clear_output(wait=True)
            abort = input('''Die Funktion rechnet relativ lange.
Vielleicht liegt eine Endlosschleife vor.
Möchten sie abbrechen? [J,n]:''')
            if abort.upper() in ['J', 'JA', 'Y', 'YES', '']:
                raise KeyboardInterrupt
            signal.alarm(self.time)
        except EOFError:
            pass

class State:
    def __init__(self, linenumber, values):
        self.values = deepcopy(values)
        self.linenumber = linenumber

    def less_or_equal(self, other):
        if self.linenumber > other.linenumber:
            return False
        values1 = self.values
        values2 = other.values
        different_keys = [k for k in values1 if values1.get(k) != values2.get(k)] +\
                         [k for k in values2 if values1.get(k) is None]

        for key in different_keys:
            if values1.get(key) > 0 and (values2.get(key) is None or values2.get(key) < values1.get(key)):
                return False

        return True


class WHILEInterpreter(LOOPInterpreter):
    def __init__(self, timeout=60):
        super().__init__()
        self.regex_to_token = [(re.compile(r'\d+'), 'NUMBER'),
                               (re.compile(r'x\d+'), 'IDENTIFIER'),
                               (re.compile(r'\+'), 'PLUS'),
                               (re.compile(r'[−-]'), 'MINUS'),
                               (re.compile(r':=|≔'), 'ALLOCATION'),
                               (re.compile(r'/=|≠|!='), 'NOTEQUALS'),
                               (re.compile(r'LOOP'), 'LOOP'),
                               (re.compile(r'WHILE'), 'WHILE'),
                               (re.compile(r'DO'), 'DO'),
                               (re.compile(r'END'), 'END'),
                               (re.compile(r';'), 'SEMICOLON'),
                               (re.compile(r'BREAK'), 'BREAK'),
                               (re.compile(r'\s+', re.MULTILINE), 'WHITESPACE'),
                               (re.compile(r'[^\n]*'), 'UNKNOWN')]
        self.timeout = timeout

    def process_program(self, forbidden_identifiers, current_token):
        if current_token is None or current_token.k not in ['IDENTIFIER', 'LOOP', 'WHILE']:
            self.error_handler.handle_error('Keine passende Anweisung gefunden\n' +
                                            'Erwartet: IDENTIFIER (x0, x1, ...), LOOP oder WHILE')
        elif current_token.k == 'IDENTIFIER':
            current_token = self.process_assignment(forbidden_identifiers, current_token)
        elif current_token.k == 'LOOP':
            current_token = self.process_loop(forbidden_identifiers, current_token)
        elif current_token.k == 'WHILE':
            current_token = self.process_while(forbidden_identifiers, current_token)
        return current_token

    def verify_program(self, forbidden_identifiers, current_token):
        if current_token is None or current_token.k not in ['IDENTIFIER', 'LOOP', 'WHILE']:
            self.error_handler.handle_error('Keine passende Anweisung gefunden\n' +
                                            'Erwartet: IDENTIFIER (x0, x1, ...), LOOP oder WHILE')
        elif current_token.k == 'IDENTIFIER':
            current_token = self.verify_assignment(forbidden_identifiers, current_token)
        elif current_token.k == 'LOOP':
            current_token = self.verify_loop(forbidden_identifiers, current_token)
        elif current_token.k == 'WHILE':
            current_token = self.verify_while(forbidden_identifiers, current_token)
        return current_token

    def process_while(self, forbidden_identifiers, current_token):
        identifier_token = self.next_nonempty_token('WHILE', 'IDENTIFIER (x0, x1, ...)')
        if not identifier_token.k == 'IDENTIFIER':
            self.error_handler.handle_error('IDENTIFIER in WHILE erwartet.')
        if identifier_token.v in forbidden_identifiers:
            self.error_handler.handle_error('Identifier ' + identifier_token.v +
                                            ' ist bereits in Loop vorhanden und darf nicht verwendet werden.')
        if not self.next_nonempty_token('WHILE', 'UNGLEICH').k == 'NOTEQUALS':
            self.error_handler.handle_error('UNGLEICH in WHILE erwartet.')

        zero_token = self.next_nonempty_token('WHILE', '0')
        if not zero_token.k == 'NUMBER':
            self.error_handler.handle_error('0 in WHILE erwartet.')
        if not int(zero_token.v) == 0:
            self.error_handler.handle_error('0 in WHILE erwartet.')

        if not self.next_nonempty_token('WHILE', 'DO').k == 'DO':
            self.error_handler.handle_error('DO in WHILE erwartet.')

        if identifier_token.v in self.values:
            while_value = int(self.values.get(identifier_token.v))
        else:
            while_value = 0

        saved_position = self.lex.current_position
        saved_line = self.error_handler.line_number

        if while_value == 0:
            end_found = False
            while not end_found:
                token = self.verify_program(forbidden_identifiers, self.next_token())
                if token is None or token.k not in ['SEMICOLON', 'END']:
                    self.error_handler.handle_error('SEMICOLON oder END in WHILE erwartet.')
                elif token.k == 'SEMICOLON':
                    continue
                elif token.k == 'END':
                    end_found = True

        while not while_value == 0:
            if self.test_homeomorphic_embedding:
                new_state = State(self.lex.current_position, self.values)
                for state in self.state_list:
                    if state.less_or_equal(new_state):
                        self.error_handler.handle_endless_loop()
                self.state_list.append(new_state)

            self.lex.current_position = saved_position
            self.error_handler.line_number = saved_line
            end_found = False
            while not end_found:
                token = self.process_program(forbidden_identifiers, self.next_token())
                if token is None or token.k not in ['SEMICOLON', 'END']:
                    self.error_handler.handle_error('SEMICOLON oder END in WHILE erwartet.')
                elif token.k == 'SEMICOLON':
                    continue
                elif token.k == 'END':
                    end_found = True

            while_value = int(self.values.get(identifier_token.v))

        return self.next_token()

    def verify_while(self, forbidden_identifiers, current_token):
        identifier_token = self.next_nonempty_token('WHILE', 'IDENTIFIER')
        if not identifier_token.k == 'IDENTIFIER':
            self.error_handler.handle_error('IDENTIFIER in WHILE erwartet.')
        if identifier_token.v in forbidden_identifiers:
            self.error_handler.handle_error('Identifier ' + identifier_token.v +
                                            ' ist bereits in Loop vorhanden und darf nicht verwendet werden.')
        if not self.next_nonempty_token('WHILE', 'UNGLEICH').k == 'NOTEQUALS':
            self.error_handler.handle_error('UNGLEICH in WHILE erwartet.')

        zero_token = self.next_nonempty_token('WHILE', '0')
        if not zero_token.k == 'NUMBER':
            self.error_handler.handle_error('0 in WHILE erwartet.')
        if not int(zero_token.v) == 0:
            self.error_handler.handle_error('0 in WHILE erwartet.')

        if not self.next_nonempty_token('WHILE', 'DO').k == 'DO':
            self.error_handler.handle_error('DO in WHILE erwartet.')

        end_found = False
        while not end_found:
            token = self.verify_program(forbidden_identifiers, self.next_token())
            if token is None or token.k not in ['SEMICOLON', 'END']:
                self.error_handler.handle_error('SEMICOLON oder END in WHILE erwartet.')
            elif token.k == 'SEMICOLON':
                continue
            elif token.k == 'END':
                end_found = True

        return self.next_token()

    def interpret(self, program, values=None, test_homeomorphic_embedding=False):
        try:
            with Timeout(self.timeout):
                self.lex = lexer.Lexer(self.regex_to_token, program)
                self.error_handler = ErrorHandler(program, self)
                self.test_homeomorphic_embedding = test_homeomorphic_embedding
                self.state_list = []
                self.values = values
                if values is None:
                    self.values = {}
                forbidden_identifiers = []
                current_token = self.next_token()
                while current_token is not None:
                    current_token = self.process_program(forbidden_identifiers, current_token)
                    if current_token is not None:
                        if not current_token.k == 'SEMICOLON':
                            self.error_handler.handle_error('Semicolon erwartet')
                        current_token = self.next_token()
                        if current_token is None:
                            self.error_handler.handle_error('Semikolons werden nur zur Trennung und nicht zum ' +
                                                            'Abschluss von Programmen verwendet')
                if 'x0' in self.values:
                    return self.values.get('x0')
                return 0
        except KeyboardInterrupt:
            print('Die Ausführung des Programms wurde unterbrochen.\n' +
                  'Daher ist der Rückgabewert des Programms nicht definiert.')
            return -1


def interpret(program, value_list=None, timeout=60, debug=False):
    """Funktion zum Ausführen eines WHILE-Programms.
    :param program: WHILE-Programm als String 'x1:=10; x2:=8; x0:=x2+0; WHILE x1 /=0 DO x0:=x0+1; x1:=x1-1 END'
    :param value_list: Array von Integern ([v1, ..., vn]).
                       Das WHILE-Programm startet mit diesen Werten in x1, ..., xn.
    :param timeout: Zeit nach der die Ausführung eines Programms pausiert wird.
                    Gibt eine Möglichkeit zum Abbrechen bei einer Endlosschleife.
                    Ein Wert von 0 deaktiviert den Timeout.
    :param debug: Boolean der angibt ob mit Homeomorphic Embedding auf mögliche Endlosschleifen geprüft werden soll.
    :returns integer: Gibt bei Abbruch -1 und sonst den Wert von x0 nach dem WHILE-Programm zurück.
    :usage interpret('x1:=10; x2:=8; x0:=x2+0; WHILE x1 /=0 DO x0:=x0+1; x1:=x1-1 END')"""
    interpreter = WHILEInterpreter(timeout)
    values = None
    if value_list is not None:
        values = {}
        for index, value in enumerate(value_list):
            if not isinstance(value, int) or value < 0 or not int(value) == value:
                raise ValueError("Variablen können nur natürliche Zahlen zugewiesen bekommen.")
            values.update({'x' + str(index+1): value})
    return interpreter.interpret(program, values, debug)


if __name__ == '__main__':
    help(interpret)