PDF de programación - Construcción de un analizador de un lenguaje imperativo - Procesadores de Lenguajes - Practicas de laboratorio

PROCESADORES DE LENGUAJES



Prácticas de laboratorio

Curso 2016/2017

CONSTRUCCIÓN DE UN ANALIZADOR
DE UN LENGUAJE IMPERATIVO



Universidad de Alcalá
Dpto. Ciencias de la Computación
Asignatura 780018 2016-17


Pág. 1

Laboratorio de Procesadores de Lenguajes
Curso 2016/2017



Índice

1. Introducción .................................................................................................................. 3

2. Analizador Léxico........................................................................................................... 3

Especificaciones Léxicas ............................................................................................... 3

3. Analizador Sintáctico ..................................................................................................... 6

Especificaciones Sintácticas .......................................................................................... 6

4. Analizador Semántico.................................................................................................... 9

5. Evaluación de la práctica ............................................................................................. 13

Elementos a entregar por el alumno .......................................................................... 14

Calificación .................................................................................................................. 15

6. ANEXO I - EJEMPLOS ................................................................................................... 17

7. ANEXO II GUÍA PARA LA REDACCIÓN ........................................................................ 21



Pág. 2





Laboratorio de Procesadores de Lenguajes
Curso 2016/2017



1.

Introducción

Se desea construir un analizador (léxico, sintáctico y semántico) para un
pequeño lenguaje imperativo cuyo único estructuras de control para la selección es
el comando ‘if’ y para la iteración el comando ‘while’. Las variables se declaran de
forma explícita como un entero o un booleano, y la semántica del lenguaje siguen
una fuerte disciplina con las expresiones.

Para el análisis de un lenguaje de programación, habitualmente, se divide en
dos partes, la parte léxica que describe las unidades más pequeñas con significado,
llamado tokens, y la parte de sintaxis que explica cómo se organizan los tokens en
los programas.

Primera Parte

2. Analizador Léxico

Especificaciones Léxicas

La parte léxica reconoce identificadores, números, operadores, signos de

puntuación, símbolos especiales y palabras reservadas.

EspLex 1.

El conjunto de las palabras reservadas del lenguaje es:
program, is, begin, end, var, integer, boolean, read,

write, skip, while, do, if, then, else, and, or, true,

false y not, las cuales generan el token correspondiente a cada una de
ellas.

También, existen una serie de tokens en la gramática, que permiten las

diferentes operaciones del lenguaje, y estos son:

EspLex 2.

Operador de asignación: Símbolo ‘:=’ .

EspLex 3.

Operadores de relación: Símbolos ‘<=‘ , ‘<‘ , ‘=‘ , ‘>‘ , ‘>=‘ y ‘<>‘.

EspLex 4.

Operadores matemáticos: Símbolos ‘+‘ , ‘-‘ , ‘*‘ y ‘/‘ .

EspLex 5.

Signos de puntuación: Símbolos ‘(‘ , ‘)‘ , ‘,‘ , ‘;’ y ‘:‘ .

EspLex 6.

letra y a
continuación pueden aparecer letras y números. Ejemplo: Ident01, a994.

Identificadores: Siempre comienzan por una

Pág. 3



Laboratorio de Procesadores de Lenguajes
Curso 2016/2017



No son sensibles a mayúsculas y minúsculas, lo que significa que “ident01”
e “IDENT01” son el mismo identificador.

EspLex 7.

Los valores de tipo entero (integer) están compuestos por una
secuencia con, al menos, un dígito y, opcionalmente, al principio, pueden
tener un símbolo (+ o -). Ejemplo: 4212, - 4212 ó +4212. Los valores de tipo
booleano (boolean) aceptan únicamente true o false.

EspLex 8.

Puede haber espacios y/o tabuladores en cualquier parte del

fichero a analizar.

EspLex 9.

Se considera un error léxicos la detección de un carácter no

definido.

Requisitos Léxicos

ReqLex 1.

Se deben presentar los errores detectados e indicar para cada
uno el número de línea y columna donde se ha producido. Estos errores
pueden mostrarse a medida que se detectan, o almacenarse en una lista y
mostrarlos al final del análisis.

ReqLex 2.

En la memoria justificativa se deberá incluir un Autómata Finito

Determinista (AFD) por cada una de las expresiones regular definidas1.

ReqLex 3.

El empleo o no de estados léxicos deberá justificarse en la

memoria justificativa.



ReqLex 4.

Al analizar el archivo que contenga un programa en el lenguaje
dado, creará una salida en pantalla con una lista de tokens que representan
los componentes atómicos significativas del programa.



1 Existen muchas herramientas que construyen AFD, ejemplos de ellas son: https://regexper.com/,
http://ivanzuzak.info/noam/webapps/fsm2regex/, http://www.regular-expressions.info/, etc.

Pág. 4

Laboratorio de Procesadores de Lenguajes
Curso 2016/2017



Ejemplo de entrada:

program switch is

var sum,k : integer;
var switch : boolean;

begin

switch := true; sum := 0; k := 1;
while k<10 do

switch := not(switch);
if switch then

sum := sum+k

end if;
k := k+1

end while;
write sum

end



Ejemplo de Salida del analizador léxico:

Análisis Léxico completado

[program,ide(switch),is,var,ide(sum),coma,ide(k),do
s_puntos,integer,punto_coma,var,ide(switch),dos_pun
tos,boolean,punto_coma,begin,ide(switch),asign,true
,punto_coma,ide(sum),asign,num(0),punto_coma,ide(k)
,asign,num(1),punto_coma,while,ide(k),comp,num(10),
do,ide(switch),asign,not,paren_izq,ide(switch),pare
n_der,punto_coma,if,ide(switch),then,ide(sum),asign
,ide(sum),mas,ide(k),end,if,punto_coma,ide(k),asign
,ide(k),mas,num(1),end,while,punto_coma,write,ide(s
um),end]



Pág. 5



Laboratorio de Procesadores de Lenguajes
Curso 2016/2017



3. Analizador Sintáctico

En esta fase se analiza la estructura de las expresiones utilizando como base la
gramática propuesta por el alumno. Con este análisis ya se puede determinar si
una estructura está bien o mal formada. El análisis que se realiza es jerárquico, es
decir, se lleva a cabo a partir de árboles de derivación que se obtienen de la propia
gramática.

Especificaciones Sintácticas

El lenguaje posee las siguientes especificaciones sintácticas:



EspSimt 1.

El identificador para el nombre del programa no puede ser

declarado en otro lugar en el programa más que al comienzo.


Un identificador de variable no puede ser declarado más de una

EspSimt 2.

vez.



EspSimt 3.

La conjunción o disyunción de expresiones lógicas utiliza los

operadores and y or respectivamente.



EspSimt 4.

Una expresión lógica negada, utiliza el operador not antes de

la expresión lógica entre paréntesis.



EspSimt 5.

La igualdad entre dos expresiones utiliza el operador "=". Las

dos expresiones comparadas deberán de ser del mismo tipo.



EspSimt 6.

La comparación entre dos expresiones de tipo entero utiliza los

operadores de relación.



EspSimt 7.

Las palabras reservadas no se pueden utilizar como nombre

para un identificador.



Pág. 6



Laboratorio de Procesadores de Lenguajes
Curso 2016/2017



EspSimt 8.


La precedencia de los operadores es, de menor a mayor

precedencia (todos los operadores asocian por la derecha) la siguiente:

1. or
2. and
3. not
4. Comparaciones
5. + y -
6. * y /

Requisitos Sintácticos

El analizador solamente ha de aceptar ficheros con extensión

ReqSimt 1.-
“.prog”.



ReqSimt 2.-

La definición de la gramática, para el lenguaje, deberá estar
libre de ambigüedades. El alumno se encontrará con el problema del ‘else
ambiguo’. Deberá indicar en la memoria justificativa cómo se ha resuelto
este problema en las definiciones de la gramática. Ej:

orden ::= if expr_booleana then orden
| if expr_booleana then orden else orden



ReqSimt 3.-

El analizador también debe ser capaz de detectar los errores

sintácticos, tales como:

a. Errores en la declaración de variables. Por ejemplo:

var sum k : integer (error en el nombre del identificador)

b. Expresiones mal formadas. Por ejemplo:

4 + + 5; ó id = (6 + 6;

c. etc.



ReqSimt 4.-

Cuando detecte un error, el analizador propuesto deberá

mostrar un mensaje que indique la línea donde se ha producido.

Al final del análisis, y en caso de haber encontrado errores, deberá
mostrar un informe con el número total de errores que se han producido,
tanto léxicos como sintácticos. Por el contrario, si el analizador hubiera
terminado sin encontrar ningún error deberá mostrar un mensaje
indicando que ha finalizado sin errores.

ReqSimt 5.-

El analizador debe ser capaz de recuperarse cuando encuentre

un error recuperable y continuar analizando el resto del programa.



Pág. 7



Laboratorio de Procesadores de Lenguajes
Curso 2016/2017



ReqSimt 6.-

Al analizar el archivo que contenga un programa en el lenguaje
dado, analizará las producciones creando un árbol de sintaxis abstracta
(AST) que represente la estructura del programa que mostrara por
pantalla, similar al ejemplo dado.



Ejemplo de entrada 2 :

program switch is

var sum,k : integer;
var switch : boolean;

begin

switch := true; sum := 0; k := 1;
while k<10 do

switch := not(switch);
if switch then sum := sum+k end if;
k := k+1

end while;
write sum

end



Ejemplo de Salida :



Análisis Sintáctico completado
AST resultado del analisis
program([decl(integer,[sum,k]),decl(boolean,[switch])],