gotointerpreter.py 14.6 KB
Newer Older
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import lexer
from loopinterpreter import ErrorHandler
from whileinterpreter import Timeout
import re
import operator


class GOTOInterpreter:
    def __init__(self, timeout=60):
        self.values = {}
        self.lex = None
        self.error_handler = None
        self.regex_to_token = [(re.compile(r'\d+'), 'NUMBER'),
                               (re.compile(r'x\d+'), 'IDENTIFIER'),
                               (re.compile(r'M\d+'), 'MARKER'),
                               (re.compile(r'\+'), 'PLUS'),
17
                               (re.compile(r'[−-]'), 'MINUS'),
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
                               (re.compile(r':=|≔'), 'ALLOCATION'),
                               (re.compile(r'='), 'EQUALS'),
                               (re.compile(r'/=|≠|!='), 'NOTEQUALS'),
                               (re.compile(r'IF'), 'IF'),
                               (re.compile(r'THEN'), 'THEN'),
                               (re.compile(r'GOTO'), 'GOTO'),
                               (re.compile(r'HALT'), 'HALT'),
                               (re.compile(r';'), 'SEMICOLON'),
                               (re.compile(r':'), 'COLON'),
                               (re.compile(r'BREAK'), 'BREAK'),
                               (re.compile(r'\s+', re.MULTILINE), 'WHITESPACE'),
                               (re.compile(r'[^\n]*'), 'UNKNOWN')]
        self.marker_to_position = {}
        self.marker_to_line = {}
        self.timeout = timeout
        self.halted = False

    def next_token(self):
        new_token = self.lex.next()
        if new_token is None:
            return None
        elif new_token.k == 'BREAK':
            self.error_handler.handle_break()
            return self.next_token()
        elif new_token.k == 'WHITESPACE':
            if new_token.v.count('\n') > 0:
                self.error_handler.increase_line(new_token.v.count('\n'))
            return self.next_token()
        else:
            return new_token

    def next_nonempty_token(self, current_function, expected_token):
        token = self.next_token()
        if token is None:
            self.error_handler.handle_error(
                'Frühzeitiges Ende von ' + current_function + '\n' + 'Erwartet: ' + expected_token)
        return token

    def process_assignment(self, identifier_token_1):
        identifier_1 = identifier_token_1.v
        if not self.next_nonempty_token('Zuweisung', ':=').k == 'ALLOCATION':
59
            self.error_handler.handle_error(':= in Zuweisung erwartet.')
60
61
62
63
        identifier_token_2 = self.next_nonempty_token('Zuweisung', 'IDENTIFIER (x0, x1, ...) oder NUMBER')
        if identifier_token_2.k == 'NUMBER':
            value_1 = int(identifier_token_2.v)
            self.values.update({identifier_token_1.v: value_1})
64
65
            if not self.next_nonempty_token('Zuweisung', 'SEMICOLON').k == 'SEMICOLON':
                self.error_handler.handle_error('SEMICOLON zum Abschluss einer Zuweisung erwartet.')
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
            return self.next_token()
        if not identifier_token_2.k == 'IDENTIFIER':
            self.error_handler.handle_error('IDENTIFIER in Zuweisung erwartet.')
        identifier_2 = identifier_token_2.v
        if identifier_2 in self.values:
            value_2 = self.values.get(identifier_2)
        else:
            value_2 = 0
        operator_token = self.next_nonempty_token('Zuweisung', '+ oder -')
        op = None
        if operator_token.k == 'PLUS':
            op = operator.__add__
        elif operator_token.k == 'MINUS':
            op = operator.__sub__
        else:
            self.error_handler.handle_error('+ oder - in Zuweisung erwartet.')
        number_token = self.next_nonempty_token('Zuweisung', 'NUMBER')
        if not number_token.k == 'NUMBER':
            self.error_handler.handle_error('NUMBER in Zuweisung erwartet.')
        value_1 = max(0, op(value_2, int(number_token.v)))
        self.values.update({identifier_1: value_1})
87
88
        if not self.next_nonempty_token('Zuweisung', 'SEMICOLON').k == 'SEMICOLON':
            self.error_handler.handle_error('SEMICOLON zum Abschluss einer Zuweisung erwartet.')
89
90
91
        return self.next_token()

    def verify_assignment(self, identifier_token_1):
92
93
        if not self.next_nonempty_token('Zuweisung', ':=').k == 'ALLOCATION':
            self.error_handler.handle_error(':= in Zuweisung erwartet.')
94

95
        identifier_token_2 = self.next_nonempty_token('Zuweisung', 'IDENTIFIER (x0, x1, ...) oder NUMBER')
96
        if identifier_token_2.k == 'NUMBER':
97
98
            if not self.next_nonempty_token('Zuweisung', 'SEMICOLON').k == 'SEMICOLON':
                self.error_handler.handle_error('SEMICOLON zum Abschluss einer Zuweisung erwartet.')
99
100
101
            return self.next_token()

        if not identifier_token_2.k == 'IDENTIFIER':
102
103
104
105
106
107
108
            self.error_handler.handle_error('IDENTIFIER in Zuweisung erwartet.')
        if self.next_nonempty_token('Zuweisung', '+ oder -').k not in ['PLUS', 'MINUS']:
            self.error_handler.handle_error('+ oder - in Zuweisung erwartet.')
        if not self.next_nonempty_token('Zuweisung', 'NUMBER').k == 'NUMBER':
            self.error_handler.handle_error('NUMBER in Zuweisung erwartet.')
        if not self.next_nonempty_token('Zuweisung', 'SEMICOLON').k == 'SEMICOLON':
            self.error_handler.handle_error('SEMICOLON zum Abschluss einer Zuweisung erwartet.')
109
110
111
112
113
114
115
116
117
118
119
120
121
122
        return self.next_token()

    def process_goto(self, goto_token):
        marker_token = self.next_nonempty_token('GOTO', 'MARKER (M1, M2, ...)')
        if not marker_token.k == 'MARKER':
            self.error_handler.handle_error('MARKER (M1, M2, ...) in GOTO erwartet.')
        if not self.next_nonempty_token('GOTO', 'SEMICOLON').k == 'SEMICOLON':
            self.error_handler.handle_error('SEMICOLON zum Abschluss eines GOTO erwartet')
        marker_number = int(marker_token.v[1:])
        current_token = self.next_token()
        while current_token is not None and max(self.marker_to_position.keys()) < int(marker_number):
            current_token = self.verify_line(current_token)
        self.lex.current_position = self.marker_to_position.get(marker_number)
        self.error_handler.line_number = self.marker_to_line.get(marker_number)
123
124
        if marker_number not in self.marker_to_position.keys():
            self.error_handler.handle_error('GOTO zu nicht vorhandener Markierung')
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
        return self.next_token()

    def verify_goto(self, goto_token):
        marker_token = self.next_nonempty_token('GOTO', 'MARKER (M1, M2, ...)')
        if not marker_token.k == 'MARKER':
            self.error_handler.handle_error('MARKER (M1, M2, ...) in GOTO erwartet.')
        if not self.next_nonempty_token('GOTO', 'SEMICOLON').k == 'SEMICOLON':
            self.error_handler.handle_error('SEMICOLON zum Abschluss eines GOTO erwartet')
        marker_number = int(marker_token.v[1:])
        saved_position = self.lex.current_position
        saved_line = self.error_handler.line_number
        current_token = self.next_token()
        while current_token is not None and max(self.marker_to_position.keys()) < int(marker_number):
            current_token = self.verify_line(current_token)
        self.lex.current_position = saved_position
        self.error_handler.line_number = saved_line
141
142
        if marker_number not in self.marker_to_position.keys():
            self.error_handler.handle_error('GOTO zu nicht vorhandener Markierung')
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
        return self.next_token()

    def process_if(self, if_token):
        identifier_token = self.next_nonempty_token('IF', 'IDENTIFIER')
        if not identifier_token.k == 'IDENTIFIER':
            self.error_handler.handle_error('IDENTIFIER in IF erwartet')
        if not self.next_nonempty_token('IF', '=').k == 'EQUALS':
            self.error_handler.handle_error('= in IF erwartet')
        number_token = self.next_nonempty_token('IF', 'NUMBER')
        if not number_token.k == 'NUMBER':
            self.error_handler.handle_error('NUMBER in IF erwartet')

        if not self.next_nonempty_token('IF', 'THEN').k == 'THEN':
            self.error_handler.handle_error('THEN in IF erwartet')
        current_token = self.next_nonempty_token('IF', 'GOTO')
        if not current_token.k == 'GOTO':
            self.error_handler.handle_error('GOTO in IF erwartet')
        if identifier_token.v in self.values.keys():
            identifier_value = self.values.get(identifier_token.v)
        else:
            identifier_value = 0
        if identifier_value == int(number_token.v):
            return self.process_goto(current_token)
        else:
            return self.verify_goto(current_token)

    def verify_if(self, if_token):
        if not self.next_nonempty_token('IF', 'IDENTIFIER').k == 'IDENTIFIER':
            self.error_handler.handle_error('IDENTIFIER in IF erwartet')
        if not self.next_nonempty_token('IF', '=').k == 'EQUALS':
            self.error_handler.handle_error('= in IF erwartet')
        if not self.next_nonempty_token('IF', 'NUMBER').k == 'NUMBER':
            self.error_handler.handle_error('NUMBER in IF erwartet')
        if not self.next_nonempty_token('IF', 'THEN').k == 'THEN':
            self.error_handler.handle_error('THEN in IF erwartet')
        current_token = self.next_nonempty_token('IF', 'GOTO')
        if not current_token.k == 'GOTO':
            self.error_handler.handle_error('GOTO in IF erwartet')
        return self.verify_goto(current_token)

    def process_halt(self, halt_token):
        if not self.next_nonempty_token('HALT', 'SEMICOLON').k == 'SEMICOLON':
            self.error_handler.handle_error('SEMICOLON zum Abschluss eines HALT erwartet')
        self.halted = True
        current_token = self.next_token()
        while current_token is not None:
            current_token = self.verify_line(current_token)
        return current_token

    def verify_halt(self, halt_token):
        if not self.next_nonempty_token('HALT', 'SEMICOLON').k == 'SEMICOLON':
            self.error_handler.handle_error('SEMICOLON zum Abschluss eines HALT erwartet')
        return self.next_token()

    def next_marker_number(self):
        if self.marker_to_position.keys():
            return max(self.marker_to_position.keys()) + 1
        else:
            return 1

    def process_line(self, current_token):
        if current_token is None or not current_token.k == 'MARKER':
            self.error_handler.handle_error('Keine passende Anweisung gefunden\n' +
                                            'Erwartet: MARKER (M1, M2, ...)')
        marker_number = int(current_token.v[1:])
        if not (marker_number == self.next_marker_number() or
                (marker_number in self.marker_to_position.keys() and
                 current_token.p == self.marker_to_position.get(marker_number))):
            self.error_handler.handle_error('Die Nummern der Anweisungen starten bei 1 und steigen fortlaufend.')
        self.marker_to_position.update({marker_number: current_token.p})
        self.marker_to_line.update({marker_number: self.error_handler.line_number})
        colon_token = self.next_nonempty_token('LINE', 'COLON')
        if not colon_token.k == 'COLON':
            self.error_handler.handle_error('DOPPELPUNKT nach MARKER (M1, M2, ...) erwartet.')

        current_token = self.next_nonempty_token('LINE', 'IDENTIFIER (x0, x1, ...), IF, GOTO oder HALT')
        if current_token.k not in ['IDENTIFIER', 'IF', 'GOTO', 'HALT']:
            self.error_handler.handle_error('Keine passende Anweisung gefunden\n' +
                                            'Erwartet: IDENTIFIER (x0, x1, ...), IF, GOTO oder HALT')
        elif current_token.k == 'IDENTIFIER':
            current_token = self.process_assignment(current_token)
        elif current_token.k == 'GOTO':
            current_token = self.process_goto(current_token)
        elif current_token.k == 'IF':
            current_token = self.process_if(current_token)
        elif current_token.k == 'HALT':
            current_token = self.process_halt(current_token)
        return current_token

    def verify_line(self, current_token):
        if current_token is None or not current_token.k == 'MARKER':
            self.error_handler.handle_error('Keine passende Anweisung gefunden\n' +
                                            'Erwartet: MARKER (M1, M2, ...)')
        marker_number = int(current_token.v[1:])
        if not (marker_number == self.next_marker_number() or
                (marker_number in self.marker_to_position.keys() and
                 current_token.p == self.marker_to_position.get(marker_number))):
            self.error_handler.handle_error('Die Nummern der Anweisungen starten bei 1 und steigen fortlaufend.')
        self.marker_to_position.update({marker_number: current_token.p})
        self.marker_to_line.update({marker_number: self.error_handler.line_number})
        if not self.next_nonempty_token('LINE', 'COLON').k == 'COLON':
            self.error_handler.handle_error('DOPPELPUNKT nach MARKER (M1, M2, ...) erwartet.')

        current_token = self.next_nonempty_token('LINE', 'IDENTIFIER (x0, x1, ...), IF, GOTO oder HALT')
        if current_token.k not in ['IDENTIFIER', 'IF', 'GOTO', 'HALT']:
            self.error_handler.handle_error('Keine passende Anweisung gefunden\n' +
                                            'Erwartet: IDENTIFIER (x0, x1, ...), IF, GOTO oder HALT')
        elif current_token.k == 'IDENTIFIER':
            current_token = self.verify_assignment(current_token)
        elif current_token.k == 'GOTO':
            current_token = self.verify_goto(current_token)
        elif current_token.k == 'IF':
            current_token = self.verify_if(current_token)
        elif current_token.k == 'HALT':
            current_token = self.verify_halt(current_token)
        return current_token

    def interpret(self, program):
        try:
            with Timeout(self.timeout):
                self.halted = False
                self.lex = lexer.Lexer(self.regex_to_token, program)
                self.error_handler = ErrorHandler(program, self)
                self.values = {}
                current_token = self.next_token()
                while current_token is not None:
                    current_token = self.process_line(current_token)
                if not self.halted:
                    self.error_handler.handle_error('Ende des Programms ohne HALT erreicht.')
                if 'x0' in self.values:
                    return self.values.get('x0')
                return 0
        except KeyboardInterrupt:
276
277
            print('Die Ausführung des Programms wurde unterbrochen.\n' +
                  'Daher ist der Rückgabewert des Programms nicht definiert.')
278
279
280
281
282
283
            return -1


def interpret(program, timeout=60):
    interpreter = GOTOInterpreter(timeout)
    return interpreter.interpret(program)