Damit der Parser möglichst einfach wird, habe ich bei meinem BASIC-Dialekt die Zeilennummern weg gelassen und Klammern wie bei Lisp/Scheme eingeführt. Im Gegensatz zu Lisp/Scheme ist die Interpretation davon dann aber nicht so allgemein, sondern im Grunde bestehen die Anweisungen alle aus „special forms“, die in einem grossen ``match``-Konstrukt verarbeitet werden.
Als Literale Werte gibt es nur ganze Zahlen.
Die binären Rechenoperationen müssen alle geklammert werden; der Operator steht zwischen den Operanden.
Code: Alles auswählen
(PRINT (3 + 5)) ; Gibt 8 aus.
(PRINT ((3 + 5) - 1)) ; Gibt 7 aus.Code: Alles auswählen
(PRINT 42) ; Ausgabe eines literals.
(PRINT a) ; Ausgabe des Wertes der Variablen `a`.
(PRINT (a 23 42)) ; Ausgabe eines Wertes aus dem 2D Array `a`.Böse zusammengehackt, keine sinnvolle Fehlerbehandlung, und die Sprache nur so weit implementiert, wie es das Beispiel zur Ausführung benötigt (zum Beispiel fehlen die meisten Rechenoperationen):
Code: Alles auswählen
#!/usr/bin/env python3
import re
from pprint import pprint
from attrs import define, field
SOURCE = """\
; Read in the data.
(READ n)
(DIM (t n n) (o n n))
(FOR i = 1 TO n
(FOR j = 1 TO i
(DO
(READ k)
((t i j) = k)
((o i j) = k))))
; Calculate the result.
(FOR i = n DOWNTO 2
(FOR j = 1 TO (i - 1)
(DO
(k = j)
(IF ((t i j) < (t i (j + 1))) THEN (k = (k + 1)))
((t (i - 1) j) = ((t (i - 1) j) + (t i k))))))
(PRINT (t 1 1))
(DATA 15) ; Row count to follow.
; The triangle values.
(DATA 75)
(DATA 95 64)
(DATA 17 47 82)
(DATA 18 35 87 10)
(DATA 20 4 82 47 65)
(DATA 19 1 23 75 3 34)
(DATA 88 2 77 73 7 63 67)
(DATA 99 65 4 28 6 16 70 92)
(DATA 41 41 26 56 83 40 80 70 33)
(DATA 41 48 72 33 47 32 37 16 94 29)
(DATA 53 71 44 65 25 43 91 52 97 51 14)
(DATA 70 11 33 28 77 73 17 78 39 68 17 57)
(DATA 91 71 52 38 17 14 91 43 58 50 27 29 48)
(DATA 63 66 4 68 89 53 67 30 73 16 69 87 40 31)
(DATA 4 62 98 27 23 9 70 98 73 93 38 53 60 4 23)
"""
SCANNER = re.Scanner(
[
(r"\s+|;.*$", None),
(r"\(", "("),
(r"\)", ")"),
(r"-?\d+", lambda _, text: int(text)),
(r"\w+|[-+=<]", lambda _, text: text),
],
re.MULTILINE,
)
def parse(text):
tokens, text = SCANNER.scan(text)
if text:
raise ValueError(f"expected end of source text, found:\n{text}")
stack = []
statement = ["DO"] # Wrap the whole program in a DO block.
for token in tokens:
if token == "(":
stack.append(statement)
statement = []
elif token == ")":
if not stack:
raise ValueError("unexpected closing parenthesis")
stack[-1].append(statement)
statement = stack.pop()
else:
statement.append(token)
if stack:
raise ValueError(f"{len(stack)} unclosed parenthesis")
assert statement and statement[0] == "DO"
#
# If the DO block contains exactly one statement we can do without the DO.
#
return statement[0] if len(statement) == 1 else statement
def filter_data(program):
program_without_data = []
data = []
for statement in program:
match statement:
case "DATA", *values:
data.extend(values)
case _:
program_without_data.append(statement)
return program_without_data, data
@define
class Context:
data_values = field(factory=lambda: iter([]))
scalars = field(factory=dict)
arrays = field(factory=dict)
def execute(context, program):
match program:
case "DO", *statements:
for statement in statements:
execute(context, statement)
case "DIM", *arrays:
for name, *dimensions in arrays:
dimensions = (
execute(context, dimension) + 1
for dimension in reversed(dimensions)
)
array = [0] * next(dimensions)
for dimension in dimensions:
array = [array.copy() for _ in range(dimension)]
context.arrays[name] = array
case (
"FOR",
name,
"=",
start,
"TO" | "DOWNTO" as direction,
end,
statement,
):
context.scalars[name] = execute(context, start)
end_value = execute(context, end)
step_value = 1 if direction == "TO" else -1
while True:
execute(context, statement)
value = context.scalars[name] + step_value
if (
step_value > 0
and value > end_value
or step_value < 0
and value < end_value
):
break
context.scalars[name] = value
case "IF", condition, "THEN", statement:
if execute(context, condition):
execute(context, statement)
case "PRINT", *statements:
print(
" ".join(
str(execute(context, statement))
for statement in statements
)
)
case "READ", name:
context.scalars[name] = next(context.data_values)
case [name, *indices], "=", expression:
array = context.arrays[name]
for index in indices[:-1]:
array = array[execute(context, index)]
array[execute(context, indices[-1])] = execute(context, expression)
case name, "=", expression:
context.scalars[name] = execute(context, expression)
case a, "+", b:
return execute(context, a) + execute(context, b)
case a, "-", b:
return execute(context, a) - execute(context, b)
case a, "<", b:
return execute(context, a) < execute(context, b)
case name, *indices:
result = context.arrays[name]
for index in indices:
result = result[execute(context, index)]
return result
case str(name):
return context.scalars[name]
case int(value):
return value
case _:
raise ValueError(f"can not execute {program!r}")
def main():
program = parse(SOURCE)
pprint(program, indent=2, compact=True)
program, data = filter_data(program)
context = Context(iter(data))
execute(context, program)
if __name__ == "__main__":
main()