Cómo utilizar el intérprete de Python
En la universidad, lo que más me atraía de la informática eran los compiladores. Lo más sorprendente es cómo el compilador puede leer el código de mala calidad que escribí y aun así generar un programa tan complejo. Cuando finalmente tomé un curso de compilación, descubrí que el proceso de compilación era mucho más simple de lo que pensaba.
En esta serie de artículos, intentaré demostrar esta simplicidad escribiendo un intérprete para un lenguaje de comando básico, IMP. Dado que IMP es un lenguaje simple y conocido, escribiré este intérprete en Python. El código Python se parece mucho al pseudocódigo, por lo que puedes entenderlo incluso si no conoces Python. El análisis se puede realizar utilizando una combinación de analizadores implementados desde cero (esto se explicará en el próximo artículo de esta serie). No se utilizan otras bibliotecas excepto sys (para E/S), re (para analizar expresiones regulares) y unittest (para asegurarse de que todo esté funcionando).
Lenguaje IMP
Antes de comenzar a escribir, analicemos el lenguaje que se explicará. IMP es un lenguaje de comandos minimizado con la siguiente estructura:
Declaración de asignación (todas las variables son variables globales y solo pueden almacenar números enteros):
Python
1
x := 1
Declaración condicional:
Python
1
2
3
4
5
si x = 1 entonces
y := 2
más
y:= 3
fin
ciclo while:
Python
1
2
3
mientras x < 10 hacer
x := x + 1
final
Declaración compuesta (separada por punto y coma):
Python
1
2
x := 1;
y := 2
Bien, este es solo un lenguaje de herramientas, pero puedes extenderlo fácilmente a algo más útil que Lua o Python. Quería que este tutorial fuera lo más simple posible.
El siguiente ejemplo es un programa que calcula factoriales:
Python
1
2
3
4
5
6
n := 5;
p := 1;
mientras n > 0 hacer
p := p * n;
n := n - 1
fin
IMP no puede leer la entrada, por lo que el estado inicial debe ser una serie de declaraciones de asignación escritas al comienzo del programa. Además, no hay forma de imprimir los resultados, por lo que el intérprete debe imprimir los valores de todas las variables al final del programa.
La estructura del intérprete
El núcleo del intérprete es la "representación intermedia" (RI). Así se representa el programa IMP en la memoria. Debido a que IMP es un lenguaje muy simple, la representación intermedia corresponderá directamente a la sintaxis del lenguaje; habrá una clase correspondiente para cada expresión y declaración; En lenguajes más complejos, no sólo se necesita una "representación gramatical", sino también una "representación semántica" que sea más fácil de analizar o ejecutar.
El intérprete realizará tres etapas:
Dividir los caracteres del código fuente en tokens
Organizar los tokens en un árbol de sintaxis abstracta (AST). El árbol de sintaxis abstracta es una representación intermedia.
Evalúa el árbol de sintaxis abstracta e imprime el estado del árbol al final.
El proceso de dividir la cadena en tokens se llama "análisis léxico" y lo realiza el analizador léxico. . Las palabras clave son cadenas muy cortas y fáciles de entender que contienen las partes más básicas de un programa, como números, identificadores, palabras clave y operadores. El lexer elimina espacios en blanco y comentarios porque el intérprete los ignora.
El proceso de organizar el marcado en un árbol de sintaxis abstracta (AST) se denomina "proceso de análisis". El analizador extrae la estructura del programa en una tabla que podemos evaluar.
El proceso de ejecución real del árbol de sintaxis abstracta analizado se llama evaluación. En realidad, esta es la parte más simple de este analizador.
En este artículo nos centraremos en los analizadores léxicos. Escribiremos un diccionario general y luego lo usaremos para crear un lexer para IMP. El próximo artículo se centrará en la construcción de un analizador y una calculadora de evaluación.
Vocabulario
El analizador léxico es bastante sencillo de utilizar. Se basa en expresiones regulares, por lo que si eres nuevo en el uso de expresiones regulares, es posible que necesites leer un poco. En pocas palabras, las expresiones regulares son cadenas con formato especial que describen otras cadenas. Puede usarlos para hacer coincidir números de teléfono o direcciones de correo electrónico o, como hemos encontrado en este ejemplo, diferentes tipos de etiquetas.
La entrada al analizador léxico puede ser solo una cadena. Para simplificar, leemos el archivo de entrada completo en la memoria. El resultado es una lista de tokens. Cada token consta de un valor (la cadena que representa) y un token (que indica qué tipo de token es). El analizador utiliza estos dos datos para decidir cómo construir el árbol de sintaxis abstracta.
Dado que el funcionamiento de un lexer es básicamente el mismo independientemente del idioma, crearemos un lexer general que incluya una lista de expresiones regulares y sus correspondientes tokens. Para cada expresión, verifica si coincide con el texto de entrada en la posición actual. Si hay una coincidencia, el texto coincidente se extrae como tokens y se etiqueta con los tokens de la expresión regular. Si la expresión regular no tiene etiquetas, el texto se descarta. De esta manera no nos distraeremos con caracteres basura como comentarios y espacios. Si no hay ninguna expresión regular que coincida, el programa informará un error y finalizará. El proceso continuará en bucle hasta que ningún carácter coincida.
Aquí tienes algunos códigos del diccionario:
Python
1
2
3
4
5
6
7
8
9
10
11tokens de retorno
Tenga en cuenta que el orden en el que iteramos a través de la expresión regular es muy importante. lex recorre en iteración todas las expresiones y acepta la primera que coincide correctamente. Esto también significa que cuando usamos lexers, debemos considerar primero las expresiones más específicas (como expresiones con operadores coincidentes y palabras clave) antes de considerar expresiones más generales (como identificadores y números).
Analizador léxico
Definir un analizador léxico para IMP es muy simple dada la función lex anterior. Lo primero que debemos hacer es definir una serie de etiquetas para las etiquetas. IMP requiere sólo tres marcadores. RESERVADO representa una palabra u operador reservado. INT representa un número entero literal y ID representa un identificador.
Python
1
2
3
4
5
5 p>
importar lexer
RESERVADO = 'RESERVADO'
INT? = 'INT'
ID = 'ID? '
A continuación, defina la expresión simbólica que utilizará el lexer. Las dos primeras expresiones coinciden con espacios y comentarios. Estas dos expresiones no están marcadas, por lo que Lex descarta los caracteres que coincidan.
Python
1
2
3
token_exprs = [
( r'[ nt]+',? Ninguno),
(r'#[^n]*',? Ninguno),
Luego están todos los operadores y palabras reservadas. Recuerde, la "r" delante de cada expresión regular indica que la cadena está "sin formato"; Python no maneja ningún carácter de escape. Esto nos permite incluir barras invertidas en cadenas, que las expresiones regulares utilizan para escapar de operadores como "+" y "*".
Python
1
2
3
4
5
5
p>
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
( r'：=',?RESERVADO),
(r'(',RESERVADO),
(r') ',RESERVADO),
( r';',RESERVADO),
(r'+',RESERVADO),
(r'-', RESERVADO),
(r'*',RESERVADO ),
(r'/',RESERVADO),
(r'<=', RESERVADO),
(r'<', RESERVADO ),
(r'>=', RESERVADO),
(r '>', RESERVADO),
(r'=', RESERVADO) ,
(r'!=', RESERVADO),
(r 'y',? RESERVADO),
(r 'o',RESERVADO) ,
(r 'no',? RESERVADO),
(r 'si', RESERVADO),
(r 'entonces',? RESERVADO) ,
(r 'si no',? RESERVADO),
(r'mientras', RESERVADO),
(r'do',? RESERVED) ,
(r'end',? RESERVED),
Por último, llega el turno de las expresiones enteras y de las expresiones identificadoras . Vale la pena señalar que la expresión regular del identificador coincide con todas las palabras reservadas anteriores y, por lo tanto, debe guardarse para el final.
Python
1
2
3
(r'[0-9]+', INT),
(r'[A-Za-z][A-Za-z0-9_]*', ID),
]
Ahora que la expresión regular está definida, necesitamos crear una función lexer real.
Python
1
2
def imp_lex(caracteres):
return lexer.lex(caracteres , token_exprs)
Si está interesado en esta parte, aquí hay un código de controlador para la salida de prueba:
Python
1
2
3
4
5
6
7
8
9
10
11
importar sistema
desde imp_lexer importar *
if __name__ == '__main__':
nombre de archivo = sys.argv[1]
archivo = open(nombre de archivo)
caracteres = archivo .read()
file.close()
tokens = imp_lex(caracteres)
para token en tokens:
imprimir token
Continuar....
En el próximo artículo de esta serie, analizaré las composiciones de analizadores y luego mostraré cómo se pueden usar para construir árboles de sintaxis abstracta a partir de las listas de tokens generadas por el lexer.
Si estás interesado en implementar un intérprete IMP, puedes descargar el código fuente completo aquí.
Ejecute el intérprete en el archivo de ejemplo incluido en el código fuente:
Python
1
python imp.py hello.imp
Ejecutar prueba unitaria:
Python
1
python test.py
Python test.py
Python test.py
Python test.py
Python test.py
Este es un archivo de muestra incluido en el código fuente.