Mi primer proyecto utilizando PLY con Python 3

Se desarrollará un intérprete que recibe como entrada varias expresiones aritméticas y presentando como salida el resultado de dichas expresiones.

Las tecnologías a utilizar son:

• PLY: Generador de analizadores léxicos y sintácticos.
• Python 3: Es un lenguaje de programación interpretado de alto nivel.
• Visual Studio Code: Es un editor de código ligero pero poderoso. Existen complementos para trabajar con este lenguaje.

El proyecto completo lo pueden descargar del siguiente enlace

• Mi primer proyecto utilizando PLY

PLY

PLY es una implementación en Python de lex y yacc, herramientas populares para la construcción de compiladores.

La principal tarea de un analizador léxico es leer los caracteres de entrada del programa fuente, agruparlos en lexemas y producir como salida una secuencia de tokens.

• Un token es un par que consiste en un nombre de token y un valor de atributo opcional.
• Un lexema es una secuencia de caracteres en el programa fuente, que coinciden con el patrón para un token y que el analizador léxico identifica como una instancia de este token.
• Un patrón es una descripción de la forma que pueden tomar los lexemas de un token.

El analizador sintáctico obtiene una cadena de tokens del analizador léxico y verifica que dicha cadena pueda generarse con la gramática para el lenguaje fuente. Una gramática proporciona una especificación precisa y fácil de entender de un lenguaje de programación.

En PLY se definen los patrones de los diferentes tokens que se desean reconocer, esto se hace a través de expresiones regulares. Mientras que las producciones y acciones para formar la gramática se definen a través de funciones.

Pre-requisitos

• Python 3
• PLY

Instalamos PLY

Para hacer uso de PLY en nuestro proyecto no hacemos instalación como tal, lo que necesitamos es descargar el archivo ply-3.11.tar.gz (versión 3.11 al momento de escribir este tutorial) de la página oficial de PLY y lo que hacemos es copiar el fólder “ply” a nuestro proyecto.

Crear nuestro proyecto

Primero crearemos un nuevo fólder, en este caso lo llamaremos PROYECTOPLY. Luego lo abrimos en nuestro editor de texto, en este caso usaremos Visual Studio Code. Finalmente procedemos a crear un nuevo archivo llamado gramatica.py donde escribiremos nuestro compilador.

Los directorios “pycache“, al igual que los archivos “parser.out” y “parsetab.py” son generados por Python los cuales pueden ser excluidos en nuestro controlador de versiones. En este caso, los agregamos a nuestro .gitignore.

1
2
3

parser.out
parsetab.py
**/__pycache__/**

El directorio “ply” es el que descargamos y utilizaremos para construir nuestro compilador.

Código Fuente para el analizador léxico y sintáctico

En el archivo gramatica.py tenemos la construcción de nuestro compilador.

Explicación del código fuente para el analizador léxico

Lo primero que debemos hacer es definir el listado de tokens que vamos a reconocer ya asignarlo a la variable tokens

1
2
3
4
5
6
7
8
9
10
11
12
13
14

tokens  = (
    'REVALUAR',
    'PARIZQ',
    'PARDER',
    'CORIZQ',
    'CORDER',
    'MAS',
    'MENOS',
    'POR',
    'DIVIDIDO',
    'DECIMAL',
    'ENTERO',
    'PTCOMA'
)

Luego escribimos los patrones para los tokens que definimos. Existen dos formas de definir las reglas de nuestros tokens.

La primera, es con expresiones regulares, agregamos el prefijo “t_” al token que queremos definir y luego le especificamos la expresión regular, para esto se hace uso del módulo re de Python.

1
2
3
4
5
6
7
8
9
10
11

# Tokens
t_REVALUAR  = r'Evaluar'
t_PARIZQ    = r'\('
t_PARDER    = r'\)'
t_CORIZQ    = r'\['
t_CORDER    = r'\]'
t_MAS       = r'\+'
t_MENOS     = r'-'
t_POR       = r'\*'
t_DIVIDIDO  = r'/'
t_PTCOMA    = r';'

La otra forma es a través de funciones, esto nos sirve para manipular el valor del token que procesamos. Por ejemplo para los valores numéricos los retornamos con el tipo apropiado, hacer validaciones, etc.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

def t_DECIMAL(t):
    r'\d+\.\d+'
    try:
        t.value = float(t.value)
    except ValueError:
        print("Floaat value too large %d", t.value)
        t.value = 0
    return t

def t_ENTERO(t):
    r'\d+'
    try:
        t.value = int(t.value)
    except ValueError:
        print("Integer value too large %d", t.value)
        t.value = 0
    return t

Es importante definir también los caracteres que se van a ignorar.

1
2

# Caracteres ignorados
t_ignore = " \t"

Las funciones también llevan el prefijo “t_” antes del nombre del token que queremos procesar. La función recibe un parámetro, “t” en nuestro ejemplo, este contiene el valor del token. Retornamos el valor ya procesado que deseamos, o no retornar nada si lo que deseamos es ignorar el token (por ejemplo: comentarios, contadores, etc.).

1
2
3
4
5
6
7

def t_newline(t):
    r'\n+'
    t.lexer.lineno += t.value.count("\n")
    
def t_error(t):
    print("Illegal character '%s'" % t.value[0])
    t.lexer.skip(1)

Finalmente construimos el analizador léxico haciendo uso de las librerías de PLY

1
2
3

# Construyendo el analizador léxico
import ply.lex as lex
lexer = lex.lex()

Explicación del código fuente para el analizador sintáctico

Otra de las ventajas de Python es que en el mismo archivo podemos definir nuestro análisis sintáctico haciendo uso de los tokens previamente definidos en la sección del analizador léxico.

Primeramente definimos la asociatividad y precedencia de los operadores, ya que la gramática escrita es ambigua, es necesario definir una precedencia para que el analizador no entre en conflicto al analizar, en este caso la precedencia es la misma que la de los operadores aritméticos, la precedencia más baja la tienen la suma y la resta, luego están la multiplicación y la división que tienen una precedencia más alta y por último está el signo menos de las expresiones negativas que tendría la precedencia más alta.

1
2
3
4
5
6

# Asociación de operadores y precedencia
precedence = (
    ('left','MAS','MENOS'),
    ('left','POR','DIVIDIDO'),
    ('right','UMENOS'),
    )

Ahora procedemos a escribir nuestras producciones, aquí vemos otra de las ventajas de Python, las acciones semánticas de nuestras producciones se hacen en forma de funciones. Las características de estas funciones son:

• El nombre inicia con el prefijo “_p”. El complemento del nombre queda a nuestra discreción
• Tiene un único parámetro “t” el cual es una tupla, en cada posición tiene el valor de los terminales y no terminales de la producción.
• Haciendo uso del docstring de las funciones de Python especificamos las producciones que serán procesadas por la función.
• En el cuerpo de la función definimos la funcionalidad que deseamos

Por ejemplo:

1
2
3
4
5
6

def p_expresion_evaluar(t):
     'expresion : expresion MAS expresion'
     #   ^            ^      ^    ^
     #  t[0]         t[1]   t[2] t[3]
 
     t[0] = t[1] + t[3]

Sintetizamos en p[0] (expresion) el valor del resultado de sumar loo valores de p[1] (expresion) y p[3].

A continuación el código completo de nuestras producciones:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

# Definición de la gramática
def p_instrucciones_lista(t):
    '''instrucciones    : instruccion instrucciones
                        | instruccion '''

def p_instrucciones_evaluar(t):
    'instruccion : REVALUAR CORIZQ expresion CORDER PTCOMA'
    print('El valor de la expresión es: ' + str(t[3]))

def p_expresion_binaria(t):
    '''expresion : expresion MAS expresion
                  | expresion MENOS expresion
                  | expresion POR expresion
                  | expresion DIVIDIDO expresion'''
    if t[2] == '+'  : t[0] = t[1] + t[3]
    elif t[2] == '-': t[0] = t[1] - t[3]
    elif t[2] == '*': t[0] = t[1] * t[3]
    elif t[2] == '/': t[0] = t[1] / t[3]

def p_expresion_unaria(t):
    'expresion : MENOS expresion %prec UMENOS'
    t[0] = -t[2]

def p_expresion_agrupacion(t):
    'expresion : PARIZQ expresion PARDER'
    t[0] = t[2]

def p_expresion_number(t):
    '''expresion    : ENTERO
                    | DECIMAL'''
    t[0] = t[1]

def p_error(t):
    print("Error sintáctico en '%s'" % t.value)

Por último, podemos manejar también las producciones de error para el manejo de errores sintácticos.

Ahora construimos el analizador sintáctico,la funcionalidad para leer el archivo y enviarle su contenido a nuestro compilador.

1
2
3
4
5
6
7

import ply.yacc as yacc
parser = yacc.yacc()

f = open("./entrada.txt", "r")
input = f.read()
print(input)
parser.parse(input)

Creando un archivo de entrada para nuestro analizador

Creamos un nuevo archivo de texto utilizando nuestro editor llamado entrada.txt. El contenido de este archivo es el siguiente:

1
2
3
4
5

Evaluar[1+1];
Evaluar[1+1*2];
Evaluar[-(1+1*6/3-5+7)];
Evaluar[-(1+1*6/3-5+1*-2)];
Evaluar[-(1.6+1.45)];

Ejecución

Para ejecutar este script corremos el siguiente comando:

1

$  python3 .\gramatica.py

Como podemos ver, obtenemos la salida esperada.

Acerca del autor:

Este tutorial fue elaborado por el Auxiliar de Cátedra Rainman Sián, como contribución al curso de Organización de Lenguajes y Compiladores 2 de la Universidad de San Carlos de Guatemala.

Fuentes consultadas:

Compiladores, principios, técnicas y herramientas. Aho, Lam, Sethi y Ullman. Segunda Edición.