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 = r'<'

t_RANGLE = r'>'

t_COMMA = r','

El nombre que sigue a t_ debe coincidir exactamente con uno de los nombres dados en tokens. Si algún tipo de acción debe llevarse a cabo, una regla de token se puede especificar como una función.

Cuando se usa una función, la regla de expresión se especifica en el cuerpo de la función. La función siempre toma un argumento sencillo, qeu es una instancia de LexToken. Este objeto tiene atributos de t.type que es el tipo de token, t.value que es el lexema (el texto matcheado), t.lineno que es el número de línea actual, y t.lexpos que es la posición del token relativa al principio del texto de entrada.

Internamente lex.py usa el modulo re para su reconocimiento de patrones. Cuando se construye la expresión regular maestra, las reglas se añaden en el siguiente orden:

1. los tokens definidos por funciones se añaden en el mismo orden que aparecen en el archivo del lexer.

2. Los tokens definidos en cadenas se añaden a continuación ordenándolos en orden decreciente de acuerdo a la longitud de su expresión regular..

def t_STR_CONST(t):

r'"(([^"]))*"'

t.value = t.value[1:-1]

t.type = reserved.get(t.value,'STR_CONST')

return t

#If a string contains an unescaped newline, report that

#error as ‘‘Unterminated string constant’’and resume

#lexing at the beginning of the next line—we assume the

# programmer simply forgot the close-quote.

def t_UNT_STR_CONST(t):

r'"[^\n]+\n'

t.value = t.value[1:-1]

t.type = reserved.get(t.value,'STR_CONST')

print 'UNTERMINATED STRING CONSTANT:', t.value

return t

def t_TYPEID(t):

r'[A-Z]+[a-zA-Z_0-9]*'

t.value = t.value.lower()

t.type = reserved.get(t.value,'TYPEID')

return t

def t_OBJID(t):

r'[a-z]+[a-zA-Z_0-9]*'

t.value = t.value.lower()

t.type = reserved.get(t.value,'OBJID')

return t

def t_NUMBER(t):

r'\d+'

t.value = int(t.value)

return t

def t_newline(t):

r'\n+'

t.lexer.lineno += len(t.value)

# espacios en blanco

t_ignore = '\t\r\f\v'

# When an invalid character (one that can’t begin any

# token) is encountered, a string containing just that

#character should be returned as the error string.

# Resume lexing at the following character.

def t_error(t):

print "Illegal character

...