Cómo escribir un lex de intérprete

Cómo escribir un intérprete

El intérprete es un contenido relativamente profundo. Aunque intenté comenzar con los principios más básicos y tratar de que este artículo no dependiera de otros conocimientos, este tutorial no es una introducción a la programación funcional, por lo que supongo que ha aprendido el esquema más básico y la programación funcional. Si no comprende esto en absoluto, puede leer los Capítulos 1 y 2 de SICP. Por supuesto, también puedes seguir leyendo este artículo y buscar información si no entiendes nada. También hablaré aquí sobre los principios de recursividad y coincidencia de patrones. Si ya sabe estas cosas, el contenido aquí puede profundizar su comprensión.

El intérprete en realidad no es algo difícil, pero muchas personas no saben cómo escribirlo, porque en sus mentes el intérprete es tan complicado como un intérprete de Python. Si intentas escribir un intérprete de Python desde el principio, probablemente nunca lo escribirás. Debe comenzar con el lenguaje más simple y aumentar gradualmente la complejidad del lenguaje para construir el intérprete correcto. Este artículo le explica cómo escribir un intérprete en el lenguaje más simple (cálculo lambda) con funciones aritméticas básicas que se pueden utilizar como una calculadora avanzada.

Los cursos de compilador general a menudo comienzan con un análisis de sintaxis (análisis), analizando herramientas como lex y yacc. La función de Parsing es en realidad simplemente decodificar la cadena en la estructura de árbol de sintaxis (AST) del programa. ¡Después de obtener el AST, comienzan las verdaderas dificultades! Y muchas personas se han caído después de escribir el analizador. Por esta razón, aquí utilizo "expresión S" para representar la estructura del árbol de sintaxis (AST) del programa. La expresión S nos permite omitir el paso de análisis directamente e ingresar al tema clave: la semántica.

La implementación del esquema utilizada aquí es Racket. Para mantener el programa simple, utilicé la combinación de patrones de Racket. Si utiliza otros esquemas para implementarlo, es posible que deba realizar algunos ajustes usted mismo.

¿Qué es un intérprete?

Primero, hablemos de qué es un intérprete. Para decirlo sin rodeos, un intérprete es similar a una calculadora. Todos aceptan una "expresión" y generan un "resultado". Por ejemplo, después de obtener '(1 2), genera 3. Sin embargo, las expresiones del intérprete son más complicadas que las de la calculadora. Las expresiones aceptadas por el intérprete se denominan "programas" y no son simples expresiones aritméticas. En esencia, cada programa es una "descripción" de una máquina, y el intérprete "simula" el funcionamiento de la máquina, es decir, realiza "cálculos". Entonces, en cierto sentido, el intérprete es la esencia de la informática. Por supuesto, diferentes intérpretes conducirán a diferentes cálculos.

Cabe señalar que el parámetro aceptado por nuestro intérprete es la "estructura de datos" de una expresión, no una cadena. Aquí utilizamos una estructura de datos llamada "expresión S" para representar expresiones. Por ejemplo, el contenido de la expresión '( 1 2) son tres símbolos: ' , '1 y '2, no la cadena "( 1 2)". Extraer información de datos estructurados es conveniente, pero extraer información de cadenas es problemático y propenso a errores.

A grandes rasgos, el intérprete es un concepto general. Una calculadora es en realidad una forma de intérprete, excepto que maneja un lenguaje mucho más simple que el intérprete de un programa. Quizás descubra que las CPU y los cerebros humanos son esencialmente intérpretes, porque la esencia de un intérprete es en realidad "cualquier máquina utilizada para procesar el lenguaje".

Definición recursiva

Los intérpretes son generalmente "programas recursivos". La razón por la que es recursivo es que la estructura de datos (programa) que procesa es en sí misma una estructura "definida recursivamente".

Una expresión aritmética es una estructura como: '(* ( 1 2) (* (- 9 6) 4)). Cada expresión puede contener subexpresiones, y las subexpresiones pueden contener subexpresiones, lo que crea un anidamiento infinito. Parece muy complicado, pero en realidad su definición es simplemente:

La "expresión aritmética" tiene dos formas:

1) un número

2) un ' (op e1 e2) Tal estructura (donde e1 y e2 son dos "expresiones aritméticas")

¿Puedes ver dónde está la "recursión"? Originalmente estábamos definiendo el concepto de "expresión aritmética", ¡y el concepto de "expresión aritmética" en sí se utilizó en su definición! Esto crea un "bucle" que nos permite generar expresiones de profundidad arbitraria.

Muchos otros datos, incluidos los números naturales, se pueden definir mediante recursividad. Por ejemplo, la definición común de números naturales es:

Los "números naturales" tienen dos formas:

1) Cero

2) El sucesor de un determinado "número natural"

¿Lo viste? ¡Aparece en la definición de "números naturales"! Por eso tenemos una cantidad infinita de números naturales.

Así que se puede decir que la recursividad es omnipresente, e incluso algunos dicen que la recursividad es el principio último de la naturaleza. Los datos recursivos siempre requieren procedimientos recursivos para procesarse. Aunque la recursividad a veces aparece en otras formas, como bucles, el concepto de "recursión" es más amplio que el de "bucle". Hay muchos programas recursivos que no se pueden expresar mediante bucles. Por ejemplo, el intérprete que vamos a escribir hoy es un programa recursivo y no se puede expresar mediante bucles. Por tanto, escribir programas recursivos correctos es crucial para diseñar cualquier sistema. De hecho, el concepto de recursividad no se limita a la programación. Existe un concepto en la prueba matemática llamado "inducción", como "inducción matemática". De hecho, la inducción y la recursividad son exactamente lo mismo.

Nuestro intérprete de hoy es un programa recursivo. Acepta una expresión, se llama a sí mismo de forma recursiva para procesar cada subexpresión y luego combina los resultados de cada recursión para formar el resultado final. Esto es un poco como atravesar un árbol binario, excepto que nuestra estructura de datos (programa) es más compleja que un árbol binario.

Coincidencia de patrones y recursividad: una calculadora simple

Dado que la calculadora es el intérprete más simple, ¿por qué no empezamos con una calculadora? A continuación se muestra una calculadora que puede calcular las expresiones de las cuatro operaciones aritméticas. Estas expresiones se pueden anidar arbitrariamente, como '(* ( 1 2) ( 3 4)). Quiero hablar sobre los principios de coincidencia de patrones y recursividad a partir de este sencillo ejemplo.

El siguiente es el código de esta calculadora. Toma una expresión y genera un número como resultado, como se muestra en la sección anterior.

(define calc

(lambda (exp)

(match exp; dos casos de expresiones coincidentes

[(? number? p> (let ([v1 (calc e1)]; llama a calc de forma recursiva y obtiene el valor de e1

[v2 (calc e2)]); llama a calc de forma recursiva y obtiene el valor de e2

(match op; rama: procesando 4 casos de operador op

[' (v1 v2)]; si es un signo más, el resultado de salida es (v1 v2)

['- (- v1 v2)] ; Si es un signo menos, signo de multiplicación, signo de división, procesamiento similar

['* (* v1 v2)]

[ '/ (/ v1 v2)]))])))

La declaración de coincidencia aquí es una coincidencia de patrón. Su forma es así:

(match exp

[Resultado del patrón]

[Resultado del patrón]

... .. .

)

Realiza operaciones de "ramificación" basadas en la "estructura" de la expresión exp. Cada rama consta de dos partes, la izquierda es un "patrón" y la derecha es un resultado. El patrón de la izquierda puede tener algunas variables vinculadas después de la coincidencia, que se pueden usar en la expresión de la derecha.

En términos generales, existen tantas "definiciones" de datos como "modos" utilizados para procesarlos. Por ejemplo, hay dos casos de expresiones aritméticas, números o (op e1 e2). Entonces, la declaración de coincidencia utilizada para manejarlo tiene dos modos. "Puedo manejar todas tus situaciones", este es el "método exhaustivo". La idea del agotamiento es muy importante. Es muy probable que cualquier situación que pase por alto le cause problemas. El llamado "método de inducción matemática" es la manifestación de este método exhaustivo en la definición recursiva de los números naturales. Como ha agotado las dos formas posibles en que se pueden construir los números naturales, puede asegurarse de que el teorema sea válido para "cualquier número natural".

Entonces, ¿cómo funcionan los patrones? Por ejemplo, '(, op, e1, e2) es un patrón que se utiliza para hacer coincidir la entrada exp. El principio básico de la coincidencia de patrones es hacer coincidir datos con la "misma estructura". Por ejemplo, si exp es '( 1 2), entonces '(, op , e1 , e2) vinculará op a ' , e1 a '1 y e2 a '2 .

Esto se debe a que tienen la misma estructura:

'(, op, e1, e2)

'( 1 2)

Para decirlo sin rodeos, un patrón es un patrón que puede contener "estructuras de datos" con "nombres" (como op, e1 y e2), como '(, op, e1, e2). Tomamos esta estructura con nombre y la "emparejamos" con los datos reales (como '(1 2)). Cuando se corresponden uno a uno, estos nombres se vinculan automáticamente a los valores en las posiciones correspondientes en los datos reales. Los patrones pueden contener no sólo nombres, sino también datos específicos. Por ejemplo, puede construir un patrón '(, op, e1 42) para hacer coincidir expresiones donde el segundo operando está fijo en 42.

Cuando ve el patrón de la izquierda, parece "ver" la forma de los datos de entrada directamente y luego operar con los elementos internos. Nos permite "destruir" la estructura de datos a la vez y vincular los valores de cada componente (campo) a múltiples variables sin utilizar múltiples funciones de acceso. Por lo tanto, la coincidencia de patrones es un método de programación muy intuitivo que vale la pena aprender en todos los idiomas. Hay funciones similares disponibles en muchos lenguajes funcionales, como ML y Haskell.

Tenga en cuenta que los operandos en e1 y e2 aún no son valores, son expresiones. Llamamos a interp1 de forma recursiva sobre sí mismo para obtener los valores v1 y v2 de e1 y e2 respectivamente. Deberían ser números.

¿Notaste dónde usamos la recursividad? Si vuelves a mirar la definición de "expresión aritmética":

La "expresión aritmética" tiene dos formas:

1) un número

2) Una estructura como '(op e1 e2) (donde e1 y e2 son dos "expresiones aritméticas")

Encontrarás que la parte "recursiva" en esta definición es e1 y e2, por lo que calc se llama a sí mismo de forma recursiva en e1 y e2. Si recurre en cada punto de la definición de datos, su programa recursivo agotará todos los casos.

Después de eso, operamos sobre los dos valores v1 y v2 respectivamente según los diferentes operadores op. Si op es el signo más ' , llamamos a la operación de suma de Scheme en v1 y v2 y devolvemos el valor resultante. Si es un signo menos, un signo de multiplicación o un signo de división, también realizamos las operaciones correspondientes y devolvemos sus valores.

Así podrás obtener los siguientes resultados de la prueba:

(calc '( 1 2))

=gt; (calc '(* 2 3))

;; =gt; 6

(calc '(* (1 2) (3 4)))

; =gt; 21

Una calculadora es así de simple. Puede probar estos ejemplos y luego crear algunos nuevos usted mismo.

¿Qué es el cálculo lambda?

Ahora pasemos a un lenguaje más potente: el cálculo lambda. Aunque su nombre parezca aterrador, en realidad es muy simple. Sus tres elementos son: variables, funciones y llamadas. En notación tradicional, se ven así:

Variable: x

Función: λx.t

Llamada: t1 t2

Cada El lenguaje de programación tiene estos tres elementos, pero la sintaxis específica es diferente, por lo que en realidad usas el cálculo lambda todos los días.

Usando Scheme como ejemplo, estos tres elementos se verían así:

Variable: x

Función: (lambda (x) e)

Llamada: ( e1 e2)

Los lenguajes de programación generales tienen muchas otras estructuras, pero estos tres elementos son indispensables. Entonces, el paso más crítico en la construcción de un intérprete es descubrir estas tres cosas. La construcción de un intérprete para cualquier idioma generalmente comienza con estos tres elementos y luego agrega lentamente otros elementos después de asegurarse de que sean completamente correctos.

Existe una forma de pensar muy sencilla que permite ver directamente la esencia de estos tres elementos. ¿Recuerda que dije que cada programa es una "descripción de una máquina"? Entonces, cada expresión del cálculo lambda es también una descripción de una máquina. Esta máquina es muy similar a un circuito electrónico. Existe una correspondencia uno a uno entre el programa de cálculo lambda y la máquina: una variable es un cable. Una función es una "plantilla" de algún tipo de dispositivo electrónico, con sus propios terminales de entrada y salida y su propia lógica. Una llamada inserta una "instancia" de un dispositivo electrónico en el diseño y conecta sus terminales de entrada a algunos cables existentes, llamados "parámetros". Entonces, un intérprete de cálculo lambda es en realidad un simulador de un circuito electrónico. Por lo tanto, no es sorprendente escuchar que algunas empresas de chips están comenzando a utilizar lenguajes similares a Haskell (como Bluespec System Verilog) para diseñar hardware.

Cabe señalar que, a diferencia de los lenguajes ordinarios, la función del cálculo lambda tiene un solo parámetro. En realidad, esto no es una limitación importante, porque las funciones de cálculo lambda se pueden pasar por valor (esto se llama función de primera clase), por lo que puede usar definiciones de funciones anidadas para representar funciones con más de dos argumentos. Por ejemplo, (lambda (x) (lambda (y) y)) puede representar una función de dos parámetros que devuelve el segundo parámetro. Pero cuando se llama, se necesitan dos capas de llamadas, como esta:

(((lambda (x) (lambda (y) y)) 1) 2)

; ; =gt; 2

Aunque parece un poco feo, hace que nuestro intérprete alcance la máxima simplicidad. La simplicidad es crucial para quienes diseñan lenguajes de programación. Buscar un diseño complejo desde el principio a menudo conduce a una serie de problemas enredados.

Otra característica del cálculo lambda que se diferencia de los lenguajes comunes es que no tiene tipos de datos básicos como números, por lo que no se puede utilizar directamente el cálculo lambda para calcular expresiones como (1 2). Pero, curiosamente, los números pueden "codificarse" mediante los tres elementos básicos del cálculo lambda. Esta codificación se puede utilizar para representar números naturales, tipos booleanos, pares, listas e incluso todas las estructuras de datos. También puede representar estructuras de sintaxis complejas, como declaraciones condicionales. Una codificación común de este tipo se llama codificación de la Iglesia. Entonces, el cálculo lambda puede producir las funciones de casi cualquier lenguaje de programación. El antiguo dicho chino "Tres cosas dan origen a todas las cosas" puede significar esto.

Orden de evaluación, llamada por nombre, llamada por valor

A la hora de interpretar un programa, podemos tener varios "órdenes de evaluación" diferentes (orden de evaluación). Esto es un poco como atravesar un árbol binario en varios órdenes diferentes (en orden, en orden previo, en orden posterior). Es solo que el orden aquí es más complicado.

Por ejemplo, el siguiente programa:

((lambda (x) (* x x)) ( 1 2))

Podemos ejecutar primero la llamada más externa y reemplazar ( 1 2 ) Pasado a la función, obtenemos (* ( 1 2) ( 1 2)). Entonces el orden de evaluación es:

((lambda (x) (* x x)) ( 1 2))

=gt (* ( 1 2) ( 1 2))

=gt; (* 3 (1 2))

=gt; (* 3 3)

=9