📳 🎅🏽 👼 Compilador Befunge en Python 🏕️ 👨‍❤️‍👨 🧕🏾

En preparación para el curso "Fundamentos de compiladores" para estudiantes de cuarto año, estudié varios lenguajes de programación esotéricos. Aquí hay un buen artículo sobre este tema . El lenguaje Befunge (Chris Press, 1993) me pareció el más interesante del artículo, especialmente noto tres de sus características:

El campo del programa es un toro bidimensional, es decir. físicamente, esta es una matriz rectangular de comandos de símbolos cerrados a lo largo del límite superior (inferior) y a lo largo de la columna izquierda (derecha). El puntero del comando se mueve alrededor del campo (cada comando es un cierto carácter con coordenadas x, y), ejecuta el comando y continúa. El movimiento puede ser en las 4 direcciones (por defecto, directamente desde el punto 0,0), y cuando va más allá del "campo", el puntero aparece en el lado opuesto.
Hay dos comandos (p, g) en el lenguaje que cambian el campo en sí, es decir el programa se "reescribe a sí mismo" durante la ejecución. El código del programa al inicio puede no ser igual al código al final. Se inició el programa "123pgpg ## @" y el programa "ABC @ 1 @ 2 @ 3.14" (no es un ejemplo correcto) terminó de funcionar.
Chris Pressy señaló que quería crear un lenguaje que fuera lo más complejo posible para compilar. De hecho, es cierto, al crear un compilador que hace que los archivos exe sean terriblemente difíciles para el programa, encontré información de que alguien podría hacerlo en C ... Es mejor crear un traductor del lenguaje al código Python, que todavía llamo compilador por simplicidad.

El campo del programa de 1993 consta de 25 líneas de 80 caracteres cada una. Hay 36 equipos en el idioma, cada uno de los cuales es un carácter de tabla ASCII. Para obtener más información, consulte Wikipedia , daré una breve descripción a partir de ahí:

comandos de movimiento (9):

> Mover hacia la derecha
<Mover hacia la izquierda
^ Mover hacia arriba
v Mover hacia abajo
_ Mover hacia la derecha si la parte superior de la pila es 0, de lo contrario a la izquierda
El | Mover hacia abajo si está en la parte superior de la pila 0, de lo contrario hacia arriba.
? Moverse en una dirección aleatoria
# Saltar la siguiente celda ("trampolín")
@ Fin del programa

Comandos de manipulación de la pila (3)

:: Coloque una copia del vértice en la pila
\ Cambiar vértice y vértice
$ Eliminar vértice

Modificación de los comandos del código del programa (2):
p “PUT”: las coordenadas de celda y el código ASCII del carácter que se coloca en estas coordenadas
se extraen de la pila g “GET”: las coordenadas de celda se extraen de la pila; El código ASCII de un símbolo en estas coordenadas se inserta en la pila.

Comandos constantes (2):

0-9 Coloque un número en la pila de
inicio / fin de modo de símbolo, en el que los códigos ASCII de todos los caracteres del programa actual se

insertan en la pila . Operaciones aritméticas (5):

+ Suma de un vértice y un vértice
- Sustracción de un vértice y un vértice
* Multiplicación de un vértice y un vértice
/ División de enteros
% Resto de división

Comandos para la pila y operaciones lógicas (2)

:! Negación: cero en el vértice se reemplaza por 1, el valor distinto de cero se reemplaza por 0
`Comparación" mayor que ": si el vértice es mayor que el vértice, 1 se coloca en la pila, de lo contrario 0

comandos de E / S (4):

Solicite al usuario un número y colóquelo en la pila
~ Pídale al usuario un carácter y coloque en la pila su código ASCII
. Imprima la parte superior de la pila como un entero
, imprima el carácter correspondiente al código ASCII en la parte superior de la pila

Decidí escribir un compilador Befunge (intérprete) en Python de acuerdo con las reglas de 1993 con un par de restricciones: 1) el campo no tiene 25x80 caracteres, pero el mínimo en ancho y alto del bloque de texto, 2) el campo no está enlazado al toro, es decir ir más allá de las fronteras con saltar al lado opuesto no se procesa. Esto no es pereza (aunque, ¿a quién estoy bromeando?), Para pequeños ejemplos todo funciona bien, y para terminar el campo a un toro real es bastante simple, habría un deseo.

El código salió en algunos lugares innecesariamente "en la frente", pero esto se debe al hecho de que es para estudiantes y su tarea es ser lo más claro posible, y no acortarlo a un par de líneas en chino.

Parte 1

El código se proporciona de principio a fin con una excepción (que se especificará), se puede copiar en un archivo y ejecutar. El texto completo está disponible en el enlace rentry.co/ivansedov-befunge , es demasiado pronto para que lo ponga en GitHub. Por cierto, hay alrededor de 20 implementaciones de lenguaje Befunge allí, pero el código está en C (no es mi lenguaje) o Python, pero es tan complicado que no me atreví a bucear. Sin embargo, allí puede tomar programas de muestra para pruebas, por ejemplo, aquí github.com/causal-agent/befungee

from sys import *
import time
import random

Importar las bibliotecas:

La biblioteca sys es necesaria para obtener el nombre del archivo del programa. Mi compilador se llamaba bbb.py, un ejemplo de prueba en el mismo directorio 1.bf, la versión Python 3.7 en sí misma, por lo que la llamada del programa en la consola se veía así: python3 bbb.py 1.bf
time , , 0,5-1,0 .
random «?» ( ), . -, Befunge - , « » (1 , 2 , 3 , 4 ). « » .

class Pointer:
    def __init__(self, x=0, y=0, vector=2, value=None):
        self.x = x
        self.y = y
        self.vector = vector
        self.value = value
        self.stack = []
        self.stack_sf = 0

    def __str__(self):
        return 'Point ({},{}) vektor:{} value:{} stack_sf:{} stack:{}'.format(self.x, self.y, self.vector, self.value, self.stack_sf, self.stack)

    def step(self):
        if self.vector == 1:
            self.x -= 1
        elif self.vector == 2:
            self.y += 1
        elif self.vector == 3:
            self.x += 1
        elif self.vector == 4:
            self.y -= 1

    def action(self):
	#   ,

La clase principal utilizada en el programa: Puntero (puntero), tiene 6 propiedades y 2 métodos. Propiedades: 1) coordenada x (inicialmente = 0), 2) coordenada y (inicialmente = 0), 3) vector (dirección de movimiento, inicialmente = 2 a la derecha), 4) valor (valor de campo, que se encuentra en la coordenada x, y, inicialmente = Ninguno), este es, de hecho, el comando a ejecutar, 5) stack (pila de programa, inicialmente = []) y 6) stack_st (indicador para ingresar líneas, inicialmente = 0).

La clase tiene dos métodos: 1) paso () el paso del puntero, sin ninguna comprobación y prueba, cambia las coordenadas x, y dependiendo de la dirección en el vector y 2) action () es el corazón del compilador, ejecutando el comando del programa actual. Daré el código action () en la segunda parte, para que no distraiga de la lógica.

# ===============================
# =                      =
# ===============================

def open_file(name):
    data = open(name, 'r').read()
    return data

def field_print():
    for row in A:
        for elem in row:
            print(elem, end='')
        print()

Dos funciones auxiliares: 1) abrir_archivo (nombre) abre el archivo por el nombre enviado, lo lee y devuelve el contenido, y 2) field_print () imprime el contenido de la matriz A, en la que se encuentran los caracteres del programa. La creación de la matriz A se muestra a continuación.

# ===========================================
# =                       =
# ===========================================

numbers = ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9']
operators = ['+', '-', '*', '/', '%']
point = Pointer()                           #  
text = open_file(argv[1]).split("\n")       #  
n = len(text)                               # n =  
m = 0                                       # m =  

#    (   m)
for line in text:
    if len(line) > m:
        m = len(line)

#   ( n  m )
A = [' '] * n
for i in range(n):
    A[i] = [' '] * m

#    
for i in range(len(text)):
    for j in range(len(text[i])):
        A[i][j] = text[i][j]

Configuración básica del programa. En la lista de números ponemos todos los números del 0 al 9, que se pueden escribir en el programa (10 ya no caben, dos caracteres). En la lista de operadores ponemos los operadores aritméticos básicos. Cree un punto = objeto puntero (configuración predeterminada), con el que trabajaremos todo el tiempo ...

En el texto variable ponemos el texto leído del programa ejecutable, dividido por el símbolo de "nueva línea". Como resultado, el texto consta de varias líneas de texto de diferentes longitudes, que deben colocarse en una matriz rectangular de espacios en sus lugares. Es fácil encontrar el número de líneas n = len (texto), pero el número de columnas debe calcularse en función de la longitud máxima de las líneas incluidas en el texto. No encontré otra forma de hacer esta frente: recorra todas las líneas y encuentre la que tenga la longitud máxima. Teniendo a mano n y m (el número de filas y el número de columnas del campo futuro), puede hacer una matriz bidimensional, llenarla con espacios y luego pasar el texto para colocar los caracteres en sus lugares.

El resultado es un rectángulo de caracteres entre los espacios y todo esto es una matriz bidimensional n por m. Después de esta configuración, puede llamar a la función field_print () y asegurarse de que todo se ve hermoso, nada ha flotado y no ha violado la situación.

# ==========================================
# =                       =
# ==========================================

# field_print()

while point.value != '@':
    try:
        point.value = A[point.x][point.y]       # 1)    point
        point.action()                          # 2)  
        # print(point)                            # 3) :  
        # time.sleep(0.5)                         # 4) :  0.5 c
    except IndexError:                          #     =  
        print('     ')
        break

# field_print()
print()

Todo termina con el programa principal (ciclo), antes y después del cual puede mostrar el campo (a veces útil). El ciclo gira hasta que el puntero apunta al símbolo "@" (ampersand, dog, end of program). Dentro del ciclo, se realizan 4 acciones cada vez:

En la propiedad point.value, se lee el carácter que se encuentra en la matriz A en las coordenadas point.x, point.y
Se llama al método point.action (), en el que se ejecuta el comando actual (recién leído)
Se muestra un puntero en la pantalla (todas las propiedades)
Se realiza un retraso antes de la siguiente iteración (0.1 seg. - 0.5 seg.)

Los elementos 3 y 4 son completamente opcionales (incluso están comentados), pero recomiendo usarlos para probar. Todas las acciones dentro del bucle ocurren al detectar un error de IndexError (error que excede los límites del índice), esto le permite interceptar dos errores principales del compilador:

Nos dirigimos a la pila y no hay valores.
Accidentalmente fuimos más allá del programa (matriz) en ancho o alto

Se necesita la última impresión vacía () para que después de que se muestre el resultado, la consola funcione desde una nueva línea.

Parte 2

Ahora es el momento del código más importante: el contenido del método point.action () de la clase Pointer. Todo lo siguiente debe insertarse donde se escribió:

    def action(self):
	#   ,

Presta atención a la sangría:

        if self.value == '"' and self.stack_sf == 0:                # ,  "
            self.stack_sf = 1
        elif self.value == '"' and self.stack_sf == 1:
            self.stack_sf = 0
        elif self.stack_sf == 1:                                    # "Hello"   
            self.stack.append(ord(self.value))
        elif self.value in numbers and self.stack_sf == 0:
            # 123   
            self.stack.append(int(self.value))

De hecho, el código dentro de action () tiene muchas condiciones, cada una de las cuales se ejecuta cuando este comando está debajo del puntero. Todo comienza con la condición "si el comando actual = comillas y la bandera del comienzo de la línea stack_sf = 0", en este caso la bandera se eleva a 1. Ingresamos a la línea.

(De lo contrario) si el comando actual = comillas y la bandera se eleva a 1, esto significa que la comilla se encontró por segunda vez y debe dejar de ingresar la cadena (la bandera stack_sf se baja a 0). Estamos fuera de linea.

(De lo contrario) si las dos primeras condiciones no funcionaron y el indicador stack_sf = 1, entonces estamos "ubicados dentro de la línea" y necesitamos agregar el código del símbolo actual a la pila. No el personaje en sí, sino su código ASCII.

(De lo contrario) si el carácter actual se encuentra entre los elementos de los números y el indicador es stack_sf = 0, esto es, en primer lugar, un dígito y, en segundo lugar, no estamos dentro de la línea, debemos agregar el carácter actual = dígito a la pila. No agregue el código de caracteres, sino el propio carácter. Todavía recuerda que hay un número 1, y ella tiene un código = 49. Entonces, si estamos dentro de la línea, entonces necesitamos agregar 49 a la pila, y si está solo en el programa, entonces el comando 1 debería agregar a la pila 1. De aquí en

adelante todas las condiciones serán elif (de lo contrario, si ...), así que las escribiré "Si". Además, todas las condiciones son dobles, debe verificar que el carácter actual sea igual al comando y el hecho de que no estamos dentro de la cadena (dentro de la cadena, todos los caracteres se procesan de manera diferente). Podría escribir todo esto de una manera más optimizada, pero esta solución le permite centrar la atención en esta frente.

        elif self.value in operators and self.stack_sf == 0:
            b = self.stack.pop()
            a = self.stack.pop()
            if self.value == '+':
                res = a + b                                         # a+b  
            elif self.value == '-':
                res = a - b                                         # a-b  
            elif self.value == '*':
                res = a * b                                         # a*b  
            elif self.value == '/':
                if b == 0:
                    res = 0
                else:
                    res = a // b                                    # a//b  
            elif self.value == '%':
                res = a % b                                         # a%b  
            self.stack.append(res)

Si el carácter actual se encuentra entre operadores (y stack_sf = 0), significa que nos metimos en una operación aritmética. Todos son exactamente iguales: 1) se elimina el número b (con eliminación), 2) se elimina el número a (con eliminación), 3) res = el valor de la operación entre ayb, 4) res se coloca en la pila. Al dividir por 0, la respuesta es 0, aunque el autor del idioma proporcionó la opción de 0 o 1.

        elif self.value == '!' and self.stack_sf == 0:
            a = self.stack.pop()
            if a == 0:
                a = 1
            else:
                a = 0
            # 0->1, 1->0
            self.stack.append(a)

        elif self.value == '`' and self.stack_sf == 0:
            a = self.stack.pop()        # 
            b = self.stack.pop()        # 
            if b > a:
                res = 1
            else:
                res = 0
            # b>a -> 1|0
            self.stack.append(res)

Si el símbolo actual es "!", Entonces debe reemplazar la cabeza (vértice) de la pila: era 0, se convertirá en 1, habrá algo diferente de 0, será 1. Si el símbolo actual es "» "(apóstrofe), entonces debe verificar la parte superior y la columna vertebral : 1) si el vértice es más grande que el vértice, luego 1, 2) si el vértice es menor que (o igual a) el vértice, entonces se coloca 0 en la pila. Tenga en cuenta que al eliminar elementos para comparar, se eliminan (eliminan), no son copiados

        elif self.value == '?' and self.stack_sf == 0:
            # ? ( )
            a = random.randint(1, 4)
            self.vector = a

        elif self.value == ':' and self.stack_sf == 0:              #  
            last = self.stack.pop()
            self.stack.append(last)
            self.stack.append(last)

        elif self.value == '\\' and self.stack_sf == 0:             # ab => ba
            a = self.stack.pop()
            b = self.stack.pop()
            self.stack.append(a)
            self.stack.append(b)

Si el carácter actual es "?", Entonces debe elegir una dirección aleatoria y seguirla. Usamos la función random.randint (1, 4), que genera números 1,2,3,4 y coloca el nuevo valor en point.vector.

Si el carácter actual es ":", colocamos en la pila una copia de la parte superior de la pila, es decir. léalo y luego agréguelo a la pila dos veces.

Si el carácter actual es "\\" (barra invertida), entonces necesita intercambiar el vértice y el sub-vértice. Obtenemos dos números, los ponemos en la pila en el orden inverso.

        elif self.value == '#' and self.stack_sf == 0:              #  ""
            self.step()

        elif self.value == ',' and self.stack_sf == 0:              # =65=A
            value = self.stack.pop()
            print(chr(value), end='')

        elif self.value == '.' and self.stack_sf == 0:              # Print 
            a = self.stack.pop()
            print(a, end='')

Si el símbolo actual es "#" (libra), entonces debe saltar sobre el siguiente comando (en dirección). Tenga en cuenta que al final de la acción () hay un salto incondicional hacia adelante self.step (), le permite avanzar al siguiente comando. Habiendo escrito self.step () en el procesamiento "#", en realidad hacemos dos saltos y "saltamos" el siguiente comando después del "#".

Si el carácter actual es "," (coma), entonces necesita imprimir un carácter cuyo código ASCII esté en la parte superior de la pila. Si el número 65 está allí, se debe mostrar "A".

Si el carácter actual es "." (punto), entonces necesita imprimir el número que se encuentra en la parte superior de la pila, como un número. Si hay 65, entonces necesita mostrar "65". En ambos casos, el parámetro end = '' se establece durante la salida para que no haya un nuevo salto de línea.

        elif self.value == '_' and self.stack_sf == 0:              #  "_"
            test = self.stack.pop()
            if test == 0:
                #  = 0, (2)
                self.vector = 2
            else:
                #  !=0, (4)
                self.vector = 4

        elif self.value == '|' and self.stack_sf == 0:              #  "|"
            test = self.stack.pop()
            if test == 0:
                self.vector = 3
            else:
                self.vector = 1

Si el carácter actual es "_" (guión bajo), compruebe horizontalmente. Eliminamos de la pila el número para verificar (prueba), si es = 0, luego nos movemos hacia la derecha (vector = 2), si es = 0, luego nos movemos hacia la izquierda (vector = 4).

Si el carácter actual = "|" (barra vertical), entonces necesita hacer una verificación vertical. Eliminamos el número (prueba) de la pila, si es = 0, luego nos movemos hacia abajo (vector = 3), de lo contrario nos movemos hacia arriba (vector = 1).

        elif self.value == '$' and self.stack_sf == 0:              #  
            self.stack.pop()

        elif self.value == '~' and self.stack_sf == 0:              # Input: A => 65
            val = input(' : ')
            self.stack.append(ord(val[0]))

        elif self.value == '&' and self.stack_sf == 0:              # Input: 65 => 65
            val = int(input(' : '))
            self.stack.append((val))

        elif self.value == 'p' and self.stack_sf == 0:              # x, y, symcode
            x = self.stack.pop()                                    # A(x,y) = symcode
            y = self.stack.pop()
            symcode = self.stack.pop()
            A[x][y] = chr(symcode)

        # x, y, value=A(x,y)
        elif self.value == 'g' and self.stack_sf == 0:
            x = self.stack.pop()                                    # ord(value) => 
            y = self.stack.pop()
            value = A[x][y]
            self.stack.append(ord(value))

Si el carácter actual = "$", debe eliminar el vértice. Hacer pop simple ().

Si el carácter actual = "~" (tilde), le pedimos al usuario un carácter y colocamos su código ASCII en la pila. El usuario "A" (inglés) envió, debemos poner 65 en la pila. Por si acaso, pondremos val [0], de lo contrario el usuario puede ingresar "Apple" y traducirlo al código no funciona.

Si el carácter actual = "&" (ampersand), le pedimos al usuario un número y lo ponemos en la pila. Ingresaste 65, necesitas poner 65 en la pila,

ahora los dos equipos más difíciles.

Si el carácter actual = "p", debe extraer las coordenadas de celda y el código ASCII del carácter de la pila, y luego colocar este carácter en estas coordenadas en el campo A. Supongamos que 1.2.65 estaba en la pila y obtuvimos (1.2) y 65, deberíamos poner el símbolo "A" en la celda (1.2). Una vez más, observo: obtuvimos tres números y pusimos un símbolo en las coordenadas.

Si el carácter actual = "g", las coordenadas de la celda se recuperan de la pila, la celda se busca en el campo, el carácter se toma de allí y su código ASCII se inserta en la pila. Supongamos que el símbolo "B" yacía en el campo en la celda (2,3), el equipo actual obtuvo "g" y obtuvimos 2,3 de la pila. En este caso, vamos a lo largo de las coordenadas (2,3), obtenemos el símbolo "B" desde allí, lo traducimos al número 66 (código de símbolo B) y ponemos 66 en la pila.

        elif self.value == '>' and self.stack_sf == 0:              # >
            self.vector = 2
        elif self.value == '<' and self.stack_sf == 0:              # <
            self.vector = 4
        elif self.value == '^' and self.stack_sf == 0:              # ^
            self.vector = 1
        elif self.value == 'v' and self.stack_sf == 0:              # v
            self.vector = 3
        self.step()                                                 #

Bueno, y las últimas líneas de código: la organización de mover el puntero por el campo. Aquí todo es simple: miramos el símbolo y cambiamos la dirección (vector). Al final de la función action () está self.step (), que da un paso en la dirección actual. Por lo tanto, action () es tanto la ejecución de la acción como el paso para el siguiente personaje.

Conclusión

Escribir este compilador fue un placer. Y cuánta alegría trajo los momentos en que arrojas un cierto código al programa, y se ejecuta (¡correctamente!) ¡Y lo observas! El sitio befungius.aurlien.net ayudó mucho al trabajar , en el que el autor publicó el intérprete en línea Befunge (en JavaScript). Aquí está su video de una conferencia www.youtube.com/watch?v=oCPT3L33848 , en la que habla sobre el idioma.

Para las pruebas, puede usar casi cualquier programa en Befunge, excepto aquellos que requieren un campo como toro, es decir, tener transiciones en diferentes direcciones del mundo. Para algunos programas, debe ver el campo en sí (por ejemplo, el programa contador cambia la coordenada A [0] [1]), por lo tanto, inserte la salida de esta coordenada en la pantalla o muestre la matriz A completa después de cada paso.

En cualquier caso, este no es un programa para brillar, sino un código de capacitación que se puede agregar y editar. Los errores tipográficos son posibles, aunque lo he probado muchas veces. La crítica no es bienvenida, pero no está prohibida. Buena suerte a todos y buen código.

¡Hola Mundo!

0"!dlrow olleH">:#,_@

Bazz

0> 1+:3%v
>^  v%5:_:5% v
,v.:_v     v0_0"zzub"v
"v         #
     >0"zzub"v
"   v"fizz"<         <
^<         $<>:#,_v
    >      #^^#   <

Fibonacci

62*1+v>01p001>+v>\:02p\:02gv
     0       ^             <
     .         :p
     "         .1
        v 0," "<0
     "  >1g12-+:|
     ,          @
     >^

Contar

>91+:9`v
p   v  _v
    >$0 v
^ 01+*68<

Pero esto no funciona, salir del campo

0>:00p58*`#@_0>:01p78vv$$<
@^+1g00,+55_v# !`\+*9<>4v$
@v30p20"?~^"< ^+1g10,+*8<$
@>p0\>\::*::882**02g*0v >^
`*:*" d":+*:-*"[Z"+g3 < |<
v-*"[Z"+g30*g20**288\--\<#
>2**5#>8*:*/00g"P"*58*:*v^
v*288 p20/**288:+*"[Z"+-<:
>*%03 p58*:*/01g"3"* v>::^
   \_^#!:-1\+-*2*:*85<^

Enlaces y materiales adicionales:

Compilador Befunge en Python

Parte 1

Parte 2

Conclusión

More articles: