Parser de mini-C en Python

He estado aprendiendo desde hace algún tiempo un módulo para hacer el lexer y parser de un compilador en Python. Se trata de una herramienta relativamente fácil de usar (comparada con otras como antlr) y muy parecidas en sintaxis a LEX y YACC. De hecho, el nombre de PLY viene de Python-Lex-Yacc.

Hay muchísimos tutoriales y ejemplos de este módulo, así que mi intención aquí no es más que explicar cómo se usa y poco más.

Qué instalar

Tenemos que instalar el módulo ply para Python. Esto lo podemos hacer desde los repositorios de Ubuntu o a través del tar.gz de la página del proyecto.

$ sudo apt-get install python-ply

Analizador léxico

Lo primero en realizar es el analizador léxico. Lo que tenemos que hacer es importar el módulo de ply y comenzar a trabajar con él.

import ply.lex as lex

# list of tokens
tokens = (
    # Reserverd words
    'ELSE',
    'IF',
    'INT',
    'RETURN',
    'VOID',
    'WHILE',
   
    # Symbols
    'PLUS',
    'MINUS',
    'TIMES',
    'DIVIDE',
    'LESS',
    'LESSEQUAL',
    'GREATER',
    'GREATEREQUAL',
    'EQUAL',
    'DEQUAL',
    'DISTINT',
    'SEMICOLON',
    'COMMA',
    'LPAREN',
    'RPAREN',
    'LBRACKET',
    'RBRACKET',
    'LBLOCK',
    'RBLOCK',

    # Others   
    'ID', 
    'NUMBER',
)

Lo que se ha hecho es hacer un array con todos los tokens del lenguaje. En este caso de ha cogido un subconjunto de C, al que hemos llamado cminus.

Ahora, como es de esperar, debe haber expresiones regulares para todas estos tokens. Una forma de hacer esto es (esto es nuevo a partir de la versión 3 de PLY) coger todos aquellos tokens que solo sea una sentencia y hacerlo directamente de la forma:

# Regular expressions rules for a simple tokens 

t_PLUS   = r'\+'

t_MINUS  = r'-'

t_TIMES  = r'\*'

t_DIVIDE = r'/'

t_EQUAL  = r'='

t_LESS   = r'<'

t_GREATER = r'>'

t_SEMICOLON = ';'

t_COMMA  = r','

t_LPAREN = r'\('

t_RPAREN  = r'\)'

t_LBRACKET = r'\['

t_RBRACKET = r'\]'

t_LBLOCK   = r'{'

t_RBLOCK   = r'}'

Para el resto de tokens, lo que hacemos es una función. Notar que todas las reglas  comienzan con una t, esto es así porque el módulo coge todo aquello que contenga esa t_TOKEN crea el diagrama de transición correspondiente. Algunas de ellas son:

def t_ELSE(t):
    r'else'
    return t

def t_IF(t):
    r'if'
    return t

def t_NUMBER(t):
    r'\d+'
    t.value = int(t.value)
    return t

def t_ID(t):
    r'\w+(_\d\w)*'
    return t

def t_newline(t):
    r'\n+'
    t.lexer.lineno += len(t.value)

t_ignore = ' \t'

def t_comments(t):
    r'/*(.|\n)*?\*/'
    t.lexer.lineno += t.value.count('\n')

def t_comments_C99(t):
    r'//(.)*?\n'
    t.lexer.lineno += 1

def t_error(t):
    print "Lexical error: " + str(t.value[0])
    t.lexer.skip(1)

Análisis sintáctico

Ahora vamos a darle un orden a todos estos tokens que nos van llegando. Esto lo conseguimos con una gramática. Especificar gramáticas en PLY es muy similar a como se hace en YACC.

''' not_terminal : list_of_terminals not_terminals '''

Por ejemplo,

""" program : PROGRAM ID SEMICOLON block EOF """

Lo que hace el PLY, es coger la primera cadena de cada producción, analizarla y crear el analizador sintáctico. Por ejemplo, algunas de las producciones del C-menos son:
______________________________________________________

import ply.yacc as yacc
from cminus_lexer import tokens
import cminus_lexer

def p_program(p):
    'program : declaration_list'
    pass

def p_declaration_list_1(p):
    'declaration_list : declaration_list declaration' 

    pass

def p_declaration_list_2(p):
    'declaration_list : declaration'
    pass

def p_declaration(p):
    '''declaration : var_declaration
                  | fun_declaration'''
    pass

def p_var_declaration_1(p):
    'var_declaration : type_specifier ID SEMICOLON'
    pass

def p_var_declaration_2(p):
    'var_declaration : type_specifier ID LBRACKET NUMBER RBRACKET SEMICOLON'
    pass

def p_type_specifier_1(p):
    'type_specifier : INT'
    pass

def p_type_specifier_2(p):
    'type_specifier : VOID'
    pass

def p_fun_declaration(p):
    'fun_declaration : type_specifier ID LPAREN params RPAREN compount_stmt'
    pass 

def p_empty(p):
    'empty :'
    pass

______________________________________________________

Nótese que los símbolos no terminales están en minúscula y los terminales están en mayúscula. Esto es por convenio. Además, los tokens son los creados anteriormente en el analizador léxico. En el PLY es necesario colocar una producción tonta que haga la función de epsilon. (P → epsilon). Esta no hace nada. Este es un analizador que simplemente comprueba que la sintaxis es correcta, pero si no es correcta, necesitamos que cante el error. Esto lo hacemos mediante la producción p_error().

______________________________________________________

def p_error(p):
    if p is not None:
        print "Syntax error at line " + str(p.lexer.lineno) +  

        " Unexpected token  " + str(p.value)
    else:
        print "Syntax error at line: " + str(cminus_lexer.lexer.lineno) 

 
______________________________________________________

Una vez que tengamos todas las reglas escritas, tenemos llamar al método del parser. La primera vez que se ejecute, se construirá un fichero py con el analizador, llamado parsetab.py y otro con la información del léxico y sintáctico llamado parser.out.

______________________________________________________

parser = yacc.yacc()


if __name__ == '__main__':
    data = '''
        // Comment C99 style
        int gcd (int u, int v) {
            if (v == 0) 
                return u

             else
                return gcd(v, v-u);
        }
    '''
    parser.parse(data, tracking=True) 

______________________________________________________

Para ejecutar el programa, invocamos al parser y éste cogerá el código de ejemplo descrito anteriormente y le pasará el analizador sintáctico.

$ python cminus_parser.py Syntax error at line 6 Unexpected token  else

Código completo

Se puede ver el código completo en el repositorio:

http://bitbucket.org/jjfumero/cminus

El siguiente paso es construir el AST. La estrategia a seguir es ir construyéndolo a medida que se hace el parser.

Referencias

• PLY
• Tutorial para un mini-lisp