Analizador Léxico Y Sintáctico Para COOL

I. INTRODUCCION

E

L proyecto se desarrolló creando las etapas de análisis léxico y sintáctico para el lenguaje COOL.

El lexer y parser fueron hechos usando PLY (Python Lex-YAcc).

EL objetico de PLY es mantenerse apegado a la manera en que las herramientas lex/yacc trabajan normalmente.

PLY consiste de dos módulos separados: lex.py y yacc.py, los cuales están en el paquete llamado ply. El módulo lex.py se usa para separar el texto de entrada en tokens especificados por una colección de reglas de expresiones regulares. yacc.py se usa para reconocer la sintaxis del lenguaje que ha sido especificado en la forma de una gramática libre de contexto. yacc.c usa parsing LR y genera sus tablas de parsing usando ya sea algoritmos de generación de LALR (1) o tablas SLR.

Las dos herramientas trabajan juntas. Específicamente, lex.py provee una interface externa en la forma de un función token() que regresa el siguiente token valido en la stream de entrada. yacc.py llama a esta función repetidamente para obtener los tokens e invoca las reglas de gramática.

La motivación de este proyecto nace de poder facilitar la comprensión del funcionamiento de los compiladores,.

II. IMPORTANCIA DE LOS COMPILADORES

Las computadoras solo entienden el lenguaje máquina, el cual es imposible de entender para la mayoría de las personas. Los lenguajes de máquina consisten de dígitos binarios o bits, que vienen en la forma de ceros y unos. Para programar para una computadora, los desarrolladores de software usan los compiladores. Los programadores escriben programas en lenguajes de programación de alto nivel que usan nombres para las operaciones y los datos. Un compilador convierte programas en lenguaje de alto nivel a lenguaje máquina.

III. LEXER

lex.py es usado para tokenizar una cadena de entrada. Por ejemplo la cadena de entrada

x = 3 + 42 * (s - t)

Un tokenizador divide la cadena en tokens individuales

'x','=', '3', '+', '42', '*', '(', 's', '-', 't', ')'

Normalmente a los tokens se les dan nombres que indican lo que son, en el ejemplo:

'ID','EQUALS','NUMBER','PLUS','NUMBER','TIMES',

'LPAREN','ID','MINUS','ID','RPAREN'

Especificamente la entrada se divide en pares de tipos de tokens y valores, de la sigueinte manera:

('ID','x'), ('EQUALS','='), ('NUMBER','3'),

('PLUS','+'), ('NUMBER','42), ('TIMES','*'),

('LPAREN','('), ('ID','s'), ('MINUS','-'),

('ID','t'), ('RPAREN',')'

La identificación de los tokens se hace escribiendo una serie de reglas de expresiones regulares.

A. The Token List

Todos los lexers deben proveer una lista de tokens que define todos los posibles nombres de tokens que pueden ser producidos por el lexer. La lista de tokes es usada también por el modulo yacc.py para identificar símbolos terminales, en el caso del lenguaje COOL, se definió la siguiente lista:

reserved = { 'class':'CLASS',

'else':'ELSE',

'false':'fALSE',

'fi':'FI',

'if':'IF',

'in':'IN',

'inherits':'INHERITS',

'isvoid':'ISVOID',

'let':'LET',

'loop':'LOOP',

'pool':'POOL',

'then':'THEN',

'while':'WHILE',

'case':'CASE',

'esac':'ESAC',

'new':'NEW',

'of':'OF',

'not':'NOT',

'true':'TRUE',

'self_type':'SELF_TYPE',

'self':'SELF',

}

tokens = list(reserved.values()) + [ 'NUMBER',

'TYPEID',

'OBJID',

'PLUS',

'MINUS',

'TIMES',

'DIVIDE',

'EQUAL',

'LPAREN',

'RPAREN',

'LBRACE',

'RBRACE',

'SEMICOLON',

'ASSIGN',

'COLON',

'LANGLE',

'RANGLE',

'COMMA',

'DOT',

'STR_CONST',

'TILDE',

'AT',

'LESSEQ',

'GREATEQ',

'IMPLY',

]

B. Especificación de los Tokens

Cada token es especificado por medio de reglas de expresiones regulares. Cada una de estas reglas son definidas haciendo declaraciones con un prefijo especial t_ para indicar que se define un token. Para los tokens simples, las expresiones regulares se pueden especificar como cadenas, para COOL se definió lo siguiente:

# Regular expression rules for simple tokens

t_PLUS = r'\+'

t_MINUS = r'-'

t_TIMES = r'\*'

t_DIVIDE = r'/'

t_EQUAL = r'='

t_LPAREN = r'\('

t_RPAREN = r'\)'

t_DOT = '\.'

t_LBRACE = r'\{'

t_RBRACE = r'\}'

t_SEMICOLON = r';'

t_COLON = r':'

t_AT = '@'

t_TILDE = '~'

t_LESSEQ = '<='

t_GREATEQ = '>='

t_IMPLY = '=>'

t_ASSIGN = r'<-'

t_LANGLE

...