View
45
Download
9
Category
Preview:
DESCRIPTION
Resumen de Leguajes de programacion, e introduccion a compiladores.
Citation preview
1
RESUMENDEMAKLENGUAJESYCOMPILADORES(P rimerCuatrimestre) Autor :Ar ielNader ar ielnader@gmail.com
DefinicionesIniciales
Loslenguajesdeprogramacintienentresaspectosfundamentales:
Sintaxis:Es elconjuntode reglasqueespecifican lacomposicindelprogramaapartirde letras,dgitos yotroscaracteres.Estononosdicenadaacercadelsignificadodecadasentencia,soloindicasiunasentenciadeterminadaesvlidadentrodellenguajeono.Estacompuestapordoselementos:
o Lxica.o Gramtica.
Semntica: especifica el significado de un programa escrito de forma vlida bajo las reglas de sintaxis.Definencualeselefectodecadaunadelassentenciasyelprogramacompleto.
Pragmtica:Partedelestudiodeloslenguajesquesededicaatodoloquetienequeverconlascuestionesdeconstruccin.Implementacin,velocidad,versiones,etc.
Alfabeto Elementosdel Sentencias,Lenguaje(Tokens) Programas
Sobre el conjunto de caracteres del alfabeto, podemos aplicarle reglas de sintaxis para obtener los elementos dellenguajevlidos.Ejemplosdeelementossonlapalabrawhile,lasvariables,lasconstantes,lapalabraint,etc.Aesteconjunto,seleaplicanlasreglasdesemnticaparadefinirlassentenciasylosprogramasvlidosparaellenguaje.
BindingyVar iables
El binding o ligadura es el momento exacto en el que conoce un atributo o propiedad de un elemento de ciertolenguaje. Se entiende por elemento de lenguaje a variables, identificadores, constantes, funciones, procedimientos,etc. De esta forma, el binding de una variable es el concepto que define el momento en el que se conoce unapropiedaddeterminadadeunavariable(esdecir, elmomentopreciso enelqueunapropiedaddeunavariableestdefinida).Elbindingesunconceptocentralenladefinicindelasemnticadeloslenguajesdeprogramacin.
Cada variable tiene un nombre y este es utilizado para que pueda ser referenciada. Las variables tienen cuatroatributosquepodemosestudiarentrminosdebinding:
Tipo:Eslaespecificacindelconjuntodevaloresquepuedetenerunavariable,juntoconlasoperacionesenlasquepuedeintervenir.Cuandosecreaunlenguaje,sedefinenungrupodetiposdedatosdelosquepuedeserunavariable(ej:int,char,bool,etc).Enalgunoslenguajeselprogramadorpuededefinirnuevostipos.
Lostipospuedenenlazarse: Estticamente:porejemplo,enCunavariabledefinidacomointvarsiempreser int.Estosedefineen
tiempodecompilacin. Dinmicamente:por ejemplo,en uncompiladordeBASICdeterminado una variabledefinida comoDim
varpuede enunmomentoalbergar unvalornumricoymas tarde un string, estohacequeel tipode lavariablecambie.Otroejemploocurreenel lenguajeAPL.As,el tipovaadependerdelflujodeejecucindelprograma.
Valor:Es el contenido de la variable en un determinadomomento. Se representa codificado pormedio de bits y,segneltipodelavariable,esarepresentacintieneunsignificadodistinto.Estevalorpuedesermodificadoporunaoperacindeasignacin.
Losvalorespuedenenlazarse:
Sintaxis Semntica
2
Estticamente:paraelcasodelasconstantessimblicas,elvalornuncacambiaalolargodelaejecucin.Porejemplo,constintvar=3.Estoseestableceentiempodecompilacin.
Dinmicamente:Eselcasodecualquiervariablecomnquepormediodeunaasignacinsuvalorcambia.Todoestodependedelflujodeejecucin.
Alcance:Eselrangodeinstruccionesdelprogramaenelcualesconocidalavariable.
Elalcancepuedeenlazarse: Estticamente:Enestecaso,estaperfectamentedefinidocualesinstruccionespuedenaccederalavariableal
momentodelacompilacin.EjemploenC:
{intx=0x=x+1
}y=x
Estecdigodaerrorporquelavariablexnoexisteenelmomentodeasignarlaalavariabley.Podramosdecir,queelalcancedelavariablepuededelimitarseconterminalesdelaestructuralxicadelprograma(esdecir,lasllaves{}).
Dinmicamente:Paraesteenlace,elalcancesedefineenelmomentodelaejecucindelprograma.EjemploenGWBASIC:
10: A=1020: INPUTX30: IFX>0THENGOTO5040: B=750: C=A+B
LoqueocurreacaesquelavariableBpuedeserconocidaonoenla lnea50dependiendodelvalor ingresadopor teclado en la lnea 20. Si el usuario ingresa 1 el flujo de programa pasa por 40 y la variable B esdimensionadaenmemoria.Perosi elusuario ingresa1,entraenel IFy estehaceunsaltoa la lnea50detalformaquenuncasedimensionaenmemoria lavariableByen lalnea50intentautilizarlasinantescrearla loqueresultaenunerrordeejecucin.
Almacenamiento/TiempodeVida:Eselmomentoenelcualunreadememoriaesasignadaalavariableparaquepuedacontenerunvalor.
Elalmacenamientopuedeenlazarse: Estticamente:enesteenlace,seconocelaposicindememoriaqueocuparacadavariablealmomentodela
compilacin ya que al inicio de ejecucin se reserva toda la memoria necesaria total. Lenguajes comoFORTRANyCOBOL trabajan de esta forma. Por ejemplo, la variable precio almomento de compilarsiempreocuparaladireccin03AF6x0enlamemoria.Estonopermitelarecursividadyaquenopuedotenerdosvariablesprecioalmismotiempoyaquehacenreferenciaalamismaceldadememoria.
Dinmicamente:Lamayoradeloslenguajesnodefinenellugarfsicodesusvariableshastatantonoestelprogramaenejecucinyelbloquequecontengalavariablenoseaactivado.Deestaformaseaprovechamaslamemoriaysepermitelarecursividad.
Entonces,podemosdecir queunbindingesest ticosiestestablecidoantesdelmomentodela ejecucindelprogramaynopuedeser cambiadomastarde,yqueesdinmicosiseestableceentiempodeejecucinypuedeser cambiadodeacuerdoaalgunasr eglasespecificadaspor ellenguaje.
Atr ibutodelBindingdeVar iable Esttico DinmicoValor Constantes MayoraTipo Mayora APL,LISP,J,SMALLTALK
Alcance Mayora BASIC,APL,JAlmacenamiento FORTRAN,COBOL Mayora
3
ClasificacindelosLenguajesdeProgramacin
Loslenguajesseclasificanentresgrandesgrupossegnlossiguientescriterios:
Sitienealmacenamientoesttico:LENGUAJEESTATICO
Sitienealmacenamientodinmico:
o Sitienetipoyalcanceestticos:LENGUAJETIPOALGOL/ORIENTADOALAPILA
o Sitienetipooalcancedinmico:LENGUAJEDINAMICO
ModelosdeEjecucin
Existendosmodelos:
Compilada: toma un programa escrito en un determinado lenguaje y lo traduce a otro lenguaje, sea estedirectamente ejecutable o no. Es decir, no necesariamente el lenguaje resultante se puede ejecutardirectamenteporunaCPU.Ej:elEXEquegeneraunprogramaenC++oelcdigoILde.Net.
Interpretada: el interprete toma un programa escrito en determinado lenguaje y ejecuta cada instruccindirectamente.
Noexisteunlenguajequeutilice100%unodelosmodelosperolamayoradeloslenguajestipoAlgolseacercanalmodelocompiladoylamayoradeloslenguajesdinmicosseacercanalmodelointerpretado.
UsodeMemor ia
LenguajesEstticos:Lamemoriaqueelprogramanecesitaesreservadaantesdeliniciodelaejecucin.Cadavariabletieneunaposicinprefijadaenlamemoriaymantienesuespaciodurantetodoeltiempoqueseestejecutandoelprograma.Estoslenguajesnopermitenrecursin.
o Tipo:estticoo Alcance:estticoo Almacenamiento:esttico
Ejemplos:COBOL,FOLTRAN.
Estos lenguajes hacen unaasociacin rgidaentre el nombre de la variable y ladireccindememoria queocuparn. Por ejemplo, la variable precio es reemplazada por la direccin 59A0F al compilarse. Estosprogramasdebenejecutarsesiempreenelmismolugardememoriayesporestoquesiempresesabecuantamemoriaocupan.
Sitenemoslasiguienteasignacindondeseutilizan3variablesenteras:A=B+C
Programaejecutable
datos
Noseusa
Tamaofijo
4
Elcompiladortraducelasvariablesaunadireccinfijaenmemoria:
AF123BAB11C1234
Entoncescompilalaasignacinalsiguientecdigoasembler:
MOVAX,AB11ADD1234,AXMOVF123,AX
LenguajesDinmicos:Tienenunusodememoriaimpredecibles.Permitenlarecursividado Tipo:dinmicoo Alcance:dinmicoo Almacenamiento:dinmico
Ejemplos:LISP,PROLOG,APL,SNOBOL4.
Enestoslenguajesunavariablepuedecambiardetipotansoloconrecibirunaasignacindeunvalordistintoaltipooriginalquecontena.Porejemplo,sepuedecomenzarasignandoalavariableprecioconunvalorde10ymasadelantealamismavariableasignarleelstringdiez.Estoprovocauncambiodetipodedatodelavariable.Deestopodemosdeducirqueentiempodecompilacin,no sepuededeterminarqueoperacionesestnpermitidasparaciertavariable,yaquealcompilarlaoperacinprecio/5nosabemossiestavariablevaaserINTEGERoSTRING(enelprimercasosepermiteladivisin,enelsegundono).Para implementar algo asi, necesitamos tener punteros al descriptor de la variable precio dentro de laTABLADESIMBOLOS.Estatablaesunlistadodedescriptoresquecontienenentreotrascosas,elnombrede la variable (si, el nombre que se le da en el cdigo, en este caso precio), el tipo(si es INTEGER,STRING,etcenestemomento)yunpunteroalsectordelHEAPdondeseencuentranlosdatosdelavariable.El HEAP es un sector de memoria dedicado a contener los valores, clases y estructuras de las variablesdinmicas(profundizaremosmasadelanteenestosconceptos).Algo para destacar es que por lo general, los lenguajes estticos y de pila se compilan mientras que losdinmicos se interpretan.Estoquieredecirquenecesitandeunprograma interpretequeestejecutandoenmemoriaparaserejecutados.
Sitenemoslasiguienteasignacindondeseutilizan3variablesenteras:A=B+C
Elinterpretetraducirlaasignacinaunaseriedeoperacionescomolassiguientes:
Intrprete
Programasemitraducido
Tabladesmbolos
Datosdispersosen
memoria
punteros
HEAP
5
o BuscarenTabladeSmbolosaBo BuscarenTabladeSmbolosaCo Llamarrutinadesumaenteroso BuscarenTabladeSmbolosaAo AlmacenarelvalorresultanteenA
LenguajesbasadosenPila/TipoALGOL:Nosepuedeasegurarelusodememoriadelosprogramasdeestetipo,perosepuedepredecir.ElusodememoriasigueunadisciplinaLIFO(tipocomounapila).
o Tipo:estticoo Alcance:estticoo Almacenamiento:dinmico
Ejemplos:ALGOL,C,PASCAL,ADA,MODULA.
Lasvariablesnotienenpredefinidoel lugarexactodondeserncontenidasenmemoria,envezdeeso,cadavariable tienefijounoffsetdesdeelbloquequelecorresponda.Estebloqueescomounsegmentodedatosasociadoaunaunidaddeejecucin(funcin,procedimientoobloquedecdigo)ynotieneunlugarfijoenmemoria.Graciasaesto,permitenlarecursividad.Porejemplo,lafuncinsumar()seejecutaenunlugarXenmemoria. Para esto, se genera un bloque asociado adicha funcin donde estarn contenidas cada variabledeclaradadentrodelamisma.Entonces,lavariableprecio,queestdeclaradaenlafuncin,esreemplazadaal compilar por unOFFSET fijo desde el comienzo de dicho bloque.De esta forma, si la misma funcinsumar() se llama a si misma, un nuevo bloque se reserva en otro sector de memoria y la nueva variablepreciotendrelMISMOOFFSETencadaejecucinperolaBASEdelBLOQUEserdistintapermitiendopoder ser diferenciadas. A este bloque se lo llama REGISTRODEACTIVACION.Hablaremos de esteconceptomasadelante.
UnidadoBloque
Se define como un conjunto de instrucciones delimitadas de forma explicita donde se permite declarar variableslocales.Lasinstruccionesdentrodelbloqueconocenypuedenreferenciaralasvariablesquealldentrosedeclaran,perounavezqueelbloquefinaliza,estasvariablesdejandeexistirynosonreconocidasporelrestodelprograma.
Clasificacin: Annimos: No tienen un nombre, simplemente se entra en el debido al flujo de instrucciones, en otras
palabras,laejecucinllegaallugardondeseencuentradeclarado.Debidoaquenopuedeserllamado,noesrecursivo.
Con Nombre: Tienen nombre, son funciones, procedimientos, etc. Son invocados por una instruccin ypuedenserrecursivos.
Ejemplos: EnCelbloqueencerradoentre{}esunbloqueannimo:
.....{
.....
.....
.....}.....
Programaejecutable
datosPuedeque
todoelprograma
noentreenmemoria
fronteravariable
6
EnC,lasfuncionessonbloquesconnombre.voidfuncion(){
.....
.....
.....}
EnPascal,losprocedimientossonbloquesconnombre.Procedureprocedim()Begin
.....
.....
.....End
PeroenPascalnoexistenlosbloquesannimosyaque,apesardeexistirelpardeinstruccionesbegin/end,dentrodeellosnosepermitendeclararvariables.
Begin...............
End
EsimportanterepasarladefinicindeUnidadoBloqueparasabercuandoestamoshablandodeunoycuandono.Enloscuatrocasosanteriores,ladelimitacindelbloqueeraexplicita,peroenelltimonosepermitedeclararvariablesdentroyestohacequenoseaconsideradobloque.
RegistrodeActivacin
Losregistrosdeactivacinsonunaporcindememoriareservadaparalosdatosquemanipulaunaunidadobloqueenejecucin.Cuandoenelprogramasellamaaunafuncin,inmediatamentesereservaenmemoraelespaciodondecontendrlasvariableslocalesdelafuncin,losparmetrosdeentradaydesalidaytodosaquelloselementosquesenecesitenparasuejecucin.Cuandoestafuncinconcluyesuejecucin,seprocedealiberarlamemoriaqueocupaelregistrodeactivacinyseretornaalbloquellamador.Cadaunidadenejecucintieneunregistrodeactivacin.
Supongamos la secuencia de llamados de los siguientes bloquesA B C. Entonces diagramemos lo que vaocurriendoacadamomento:
1) Enmemoriaestalojadoel cdigodelprograma.ComoAestejecutando tambinse tieneenmemoria elregistrodeactivacindeAcontodassusvariableslocales.
2) LuegoAllamaaB,conlocualelregistrodeactivacindeBescargado.
Programaejecutable
Reg.Act.A
Programaejecutable
Reg.Act.A
Reg.Act.B
7
3) YluegoBllamaaC.
4) FinalmenteCretornayseeliminaenmemoriasuregistrodeactivacin.
5) LomismoparaBcuandoretorna.
EstodemuestraclaramentequelosregistrosdeactivacintienenuncomportamientodetipoLIFO(LastInputFirstOutput)ydeahdelnombredelenguajesorientadosalapila.Sedicequecuandoelregistrodeactivacindeunaunidadsecarga,adquieredireccionamiento.
Comohabamosdicho,cadavariableseremplazaporunoffsetfijoenelmomentodelacompilacin,cuyabasevienedadaporladireccindecomienzodelregistrodeactivacinquelacontiene.Estabaseesguardadageneralmenteenelregistro BP (o EBP). Entonces supongamos que tenemos las siguientes variables y que el compilador le dio esasdistanciasdeoffsetqueseaclaranenelcuadro:
Variable OffsetZ 10X 20Y 30
LainstruccinZ=X+Ysecompiladelasiguientemanera:
MOV R1,[BP+20] #SecargaenelregistroR1elvalordeXADD R1,[BP+30] #SesumaalregistroR1elvalordeYMOV [BP+10],R1 #SealmacenaenZelvalorresultante
Programaejecutable
Reg.Act.A
Reg.Act.B
Reg.Act.C
Programaejecutable
Reg.Act.A
Reg.Act.B
Programaejecutable
Reg.Act.A
8
Esosoffset son asignadosalmomentode la compilacin y quedan fijosen elcdigo del programa.Deesta formapodemos ver claramente que el nombre de la variable no queda disponible en el momento de ejecucin en loslenguajesdetipoPila.EstosoloocurreenloslenguajesDinmicos.
CadenaDinmica
Antes de explicar este concepto, vamos a explicar la problemtica. En cada momento, el programa mantiene alregistroBPapuntandoalabasedelregistrodeactivacinactivo.Cuandoseproduceunllamadoaotrobloque,antesde realizar el saltoal cdigocorrespondiente, sedebeapuntaral nuevo registrode activacin.Estenuevo registroestarcontiguoalregistroanteriorconlocual,paraapuntaralnuevoseledebesumaralBPel tamaodelregistroanterior.Lasinstruccionesnecesariasparahacerestolasconstruyeelcompiladoryaqueconoceeltamaodelregistrodeactivacinactual.
ADD BP,(TAMAOR.A.ACTUAL) #SesumaeltamaodelR.A.Actual.
Masadelante,conlaejecucindelprogramallegaelmomentoderetornardeunafuncin.LoquesedeberealizarenesemomentoesvolveratrselBP,esdecir,apuntaralregistrodeactivacinanterior.Peroelproblemaesqueenestecaso,una funcin no puede saber porquien ha sido llamada, con lo cual, no sabra a cuanto restarle alBP.Parasolucionaresto, elcompilador reservaenunlugarfijodecada registrodeactivacin ladireccindel registrode launidadque lollamo.
Estecomportamientogeneraunasucesindepunterosquevadesdeelregistrodeactivacinactivohastaelprimero,pasandoportodosdentrodelapiladellamadas.AestacadenadepunterosselellamaCADENADINAMICA.
Entonces,ampliamosel cdigodelllamadoconloexplicadoanteriormente:
MOV R7,BP #Guardaenunregistrocualquiera,elvaloractualdeBP.ADD BP,(TAMAOR.A.ACTUAL) #Sesumaeltamao.EstogeneracambiodecontextoMOV [BP+4],R7 #GuardaelvalordelBPanteriorenelR.A.actual,posicin4........ #Seejecutaelcdigodelafuncinllamada....MOV BP,[BP+4] #VuelvoaapuntaralBPanterior
Elcompiladordecideaqueoffset fijovaaguardarelpunteroBPanterior, y lo respetapara todos los registrosdeactivacin(enesteejemplodecdigo,eloffsetesde4).
AcontinuacinrealizamosunarepresentacindelacadenadinmicaparalasecuenciadellamadosABQalmomentodeejecutarQ.Omitiremoselcdigodelprogramaparasimplificareldibujo,einvertiremoselsentidodelamemoria.
BPActual
Eneldibujoseveclaramentecomocadaregistrodeactivacintieneenunoffsetfijounpunteroalregistroanteriorformandounacadenadepunteros,yelBPactualapuntandoalregistroactivo.
EstructuradeUnidades
Los lenguajes de tipo Algol tienen una estructura que tiene por objetivo poder dividir el cdigo en unidades ycontrolarelmbitodelasvariables.Estoesunanidamientoestticodeunidades,lasdefineelprogramadorynovaria
R.A.deQ
R.A.deB
R.A.deA
9
luego de la compilacin. Las unidades pueden estar anidadas hacia adentro o independientes. Esto puede serrepresentadoconlassiguientesimgenes:
EnlaprimerfigurasemuestraunprogramaquetieneunaunidadprincipalA.EstecontienedosunidadesByE.Asuvez,BcontienelaunidadCyestecontieneaD.Porotrolado,launidadEcontienelasunidadesFyG.Estamismaestructurapuederepresentarseconelrboldelasegundafigura.
Encadaunidadsepuedendeclararvariables.UnavariabledeclaradaenlaunidadAtienenivel0,unadeclaradaenelBoE tienenivel1yascon lasdemsunidades, lanotacinparadescribirelniveldeanidacindeunaunidadesnivel(U)paralaunidadU.Cadaunidadpuedemanipularlasvariablesquesedeclaranenellademaneralocalylasvariablesquesedeclaranenunidadesdondeestncontenidasdemaneraglobal.Porejemplo,unavariabledeclaradaenBeslocalaByglobalaCyD.Enelcasoqueunavariabletengaelmismonombrequeotraglobalalaunidad,serefierealavariable localsinteneraccesoa laglobal.Estoquieredecirquelavariablelocalenmascaraalavariableglobal.
Elrboldeanidamientoesunaestructuraqueconstruyeelcompiladoralmomentodecompilar,lautilizaparatalfinyunavezqueterminoelprocesodecompilacinladestruye.
Ahorabien,supongamosunprogramaconlasiguienteestructura:
A
B
C
D
F
G
E
A
B E
C
D
F G
EstructuradeUnidades ArboldeAnidamiento
A
B
C
D I
E
F
G
H
J
z=x+yintyintx
intz
10
Estenoes lenguajeC.Vemos la estructuraydestacamosqueen launidadA sedeclara lavariablez, enlaC lavariablex,enlaGlavariabley,mientrasqueenlaunidadJseoperacondichasvariables.
Si lasvariables fuerandeclaradasenlaunidadJ, laoperacinde sumaseriasencilladecompilaryaquesedeberareemplazarcadaunaconel[BP+offset]comosemostranteriormente.Perolacuestinesqueestasvariablesnoseencuentranubicadasenelregistrodeactivacinactual,conlocualobligaalprogramaabuscarlasenlosanteriores.
Paratal fin, eldiseadordelcompiladordebeestableceruna regladealcanceyseguirdicha regla al compilar.Unejemploseria:Busquelasvariablesenelentornolocal,sinoestnahbusqueenlaunidadpadreyassucesivamente.Paraello,debemossaberaquedistanciaestacadavariable(dentrodelrboldeanidamiento)segnlaunidaddondeseencuentralaoperacin.Paraestecasotenemos:
Variable ArcosZ 3X 2Y 1
El concepto de arco es la cantidad de saltos atrs que debe hacer para encontrar la variable dentro del rbol deanidacin.VemosqueparazdesdelaunidadJsedebepasarporG,CyAparaencontrarla,paraxporGyCyparaysoloporG.Hayquetenerencuentaquecadavariabledentrodesuregistrodeactivacintieneunoffsetfijo,conlocualhayquetenerencuentalasdoscuestionesalahoradecompilar,eloffsetylosarcos.Vamosaescribirunpseudocdigoenassemblerquedecmosecompilaralasumaymasadelantelocompletaremos:
MOV R1,2arcos+[BP+20] #SecargaenelregistroR1elvalordeXADD R1,1arco+[BP+30] #SesumaalregistroR1elvalordeYMOV 3arcos+[BP+10],R1 #SealmacenaenZelvalorresultante
CadenaEsttica
Comovemos,paraobtenerel lugardememoriadeunavariableseutilizanlosarcos.Paraesto,elcompiladorarmaunaestructurapara implementar lasbsquedasque realizenelrboldeanidamientoperoqueenejecucinyanotiene.Estoesunacadenadepunterosdondecadaregistrodeactivacinapuntaalabasedesupadre.EstacadenasellamaCADENAESTATICA.Entoncescadaregistrodeactivacintienealmacenadounpuntero(enunoffsetfijo)queapuntaalregistrodeactivacinpadredentrodelaestructurasdelasunidades.
Paralasiguientesecuenciadellamadosconlaestructuraanteriormentevista,semuestranlospunteros:
ABCHGJ
BPActual
CadenaEstticaCadenaDinmica
Entonces, paraobtener la variablexdesde J dijimos que necesitabadosarcos, estoesmoverdos a travs de lacadenaestticayaunoffsetde20esencontrada(dentrodelregistrodeactivacindeC).
R.A.deC
R.A.deB
R.A.deA
R.A.deJ
R.A.deG
R.A.deH
11
Bueno,ahorasi,podemosescribirelcdigoassemblerdelasumaejecutadaenelmduloJasumiendoqueelpunterodelacadenaestticaseencuentraenunoffsetfijodedosdentrodelregistrodeactivacin.
MOV R4,BP #GuardaelBPenunregistrocualquieraparanoperderlo
MOV BP,[BP+2] #BajadosvecesenlacadenaestticaparaencontraraXMOV BP,[BP+2]MOV R1,[BP+20] #GuardaenelR1elvalordeX(offsetde20dentrodesuregistrodeactivacin)
MOV BP,R4 #VuelvealcontextodelaunidadJ
MOV BP,[BP+2] #BajaunavezenlacadenaestticaparaencontrarYADD R1,[BP+30] #LesumaaR1elvalordeY(offsetde30dentrodesuregistrodeactivacin)
MOV BP,R4 #VuelvealcontextodelaunidadJ
MOV BP,[BP+2] #BajatresvecesenlacadenaestticaparaencontraraZMOV BP,[BP+2]MOV BP,[BP+2]MOV [BP+10],R1#GuardaelresultadoenZ(offsetde10dentrodesuregistrodeactivacin)
Aclaraciones:
EllenguajeCnotieneanidacindeunidades,solotiene2niveles:
ElpunterodecadenaestticadelaunidadpadreAapuntaasimismo.
Cadaunidaden lacadenaestticaapuntaalpadrequese llamporltimavez.Esdecir,parala secuenciaABABeldiagramaeselsiguiente:
BPActual
CadenaEstticaCadenaDinmica
Paraelcasodelosllamadosentreunidades,unafuncinesglobalparasimismayparalasrestantesfuncionessalvoqueseasupadre.Esnecesariohablardelavisibilidadentrefunciones.Supongamosquetenemosestaestructura:
A
B C D
R.A.deA
R.A.deB
R.A.deA
R.A.deB
A
C
D
E
F
B
12
Lasunidadesseconsiderandeclaradasenlaunidadqueespadre.Deestaforma,enAsedeclaranlasunidadesByC,enBlasDyEyenClaF.Deestaforma,deducimosquelaunidadApuedellamaralaunidadBporqueeslocalenA.Ahorabien,siestoyejecutandoenlaunidadBeintentounallamadaalaunidadC,elcompiladornovaaencontrarenprimera instanciaadichaunidad en el entorno local, asque seguir la cadenaesttica segn indica laregladealcancehastaencontrarla,conlocual,bajahastaAyencuentradeclaradalaunidadC.Observequesolosehizounabajadaatravsdelacadenaesttica,loquesignificaqueesGlobaldeDistancia1.LalgicaeslamismaparaelcasodequeDquierallamaraC,peroladistanciaes2,asqueCconrespectoaDesglobaladistancia2.Enelcasodeunallamadarecursiva,siEquierellamaraE,alcompilarnovaaencontrarladeclaracindeEensuentornolocalasquebajarunoporlacadenaestticayloencuentraenB,conlocualestallamadaesglobaldedistancia1(siemprequeesrecursivaesdedistancia1).YsiBintentallamaraF?EstecasonoesposibleyelcompiladorarrojarunerrorporquealnoencontraraFensuentornolocalbajahastaAytampocoloencuentraperonopuedebajarmasyaqueestamosenelnodoraz.
Resumiendocadacaso:
ABeslocal(L) BCesglobaldedistanciauno(G1) DCesglobaladistanciados(G2) EEesglobaldedistanciauno(G1oRderecursiva),todoslosllamadosrecursivossondeestacategora BFnosepuederealizar
Paraayudarnosalintentarsaberqueunidadpuedellamaracualotra,secreaunamatrizdellamados:
A B C D E FA R L L B G2 R G1 L L C G2 G1 R LD G3 G2 G2 R G1 E G3 G2 G2 G1 R F G3 G2 G2 R
Estamatriznolacreaelcompilador,soloesunaayudaparanosotrosalintentarestudiareltema.
Ahoraquesabemosqueunidadpuedellamaracualotra,podemosaclararcomoesqueseconstruyenlospunterosdela cadena esttica. Bsicamente, el principio que se sigue es que la cadena esttica se forma siguiendo la mismacadenaestticapreconstruida.Veamosunejemplo,conlasiguientesecuenciadellamados:
ABCFC
1)Comienzala ejecucindeA, enmemoriaseencuentraunnico registrodeactivacin.Acontinuacineldibujo(porrazonesprcticasnodibujaremoslacadenadinmica).
CadenaEsttica BPActual
2)AB:Alencontrarelllamado,elcompiladorescribelassentenciasquedimensionanelregistrodeactivacindeB.Luegodeello,vuelveaapuntaralR.A.deAyconsultaelrboldeanidamiento.ComoencuentraqueBeslocalaA,tomaladireccindeBPdeAylaguardaenelpunterodecadenaestticadeB.
R.A.deA
13
CadenaEstticaBPActual
3)BC:Alencontrarelllamado,elcompiladorescribelassentenciasquedimensionanelregistrodeactivacindeC.Luegodeello,vuelveaapuntaralR.A.deByconsultaelrboldeanidamiento.ComoencuentraqueCesglobala distancia1 con respecto aB, entonces baja unaposicin en la cadena esttica hasta elR. A. deA y copia esadireccinqueapuntaaeseR. A.enelpunterodecadenaestticadeC.
BPActual
CadenaEsttica
4)CF:Alencontrarelllamado,elcompiladorescribelassentenciasquedimensionanelregistrodeactivacindeF.Luegodeello,vuelveaapuntaralR.A.deCyconsultaelrboldeanidamiento.ComoencuentraqueFeslocalaC,tomaladireccindeBPdeCylaguardaenelpunterodecadenaestticadeF.
BPActual
CadenaEsttica
5)FC:Alencontrarelllamado,elcompiladorescribelassentenciasquedimensionanelregistrodeactivacindeC.Luegodeello,vuelveaapuntaralR.A.deFyconsultaelrboldeanidamiento.ComoencuentraqueCesglobaladistancia 2 con respecto a F, entonces baja dos posiciones en la cadena esttica hasta el R. A. de A y copia esadireccinqueapuntaaeseR.A.enelpunterodecadenaestticadeC.
BPActual
CadenaEsttica
R.A.deA
R.A.deB
R.A.deA
R.A.deB
R.A.deC
R.A.deA
R.A.deB
R.A.deC
R.A.deF
R.A.deA
R.A.deB
R.A.deC
R.A.deF
R.A.deC
14
Loimportanteadestacarentodoesteprocedimientoesquesegnlacantidaddedistanciaqueunaunidadseaglobalaotra es iguala la cantidaddearcosque sedebebajardesdeelR.A. de la unidad llamadora a travsde la cadenaestticapreconstruidaparaobtenerqueRA.sedebealmacenarenelpunterodecadenaestticadelR.A.delaunidadllamada.
Acontinuacinsepresentala implementacindeesteprocedimientoencdigoassemblerparala llamadaFCysuponiendoqueelpunterodecadenaestticaesta3yeldecadenadinmicaesta4.
MOV R6,BP #GuardaelBPqueapuntaaCenunregistrocualquieraparanoperderlo
MOV BP,[BP+4] #Bajaalbloquedelllamador(esF)
MOV BP,[BP+3] #Bajadosvecesatravsdelacadenaesttica.EstoesasiporqueCesglobalMOV BP,[BP+3] #adosdeF.Sifueraglobala1,elcompiladorsoloponeunasoladeestas
#sentencias.Sifueralocal,nopondraninguna.
MOV [R6+3],BP #ComohabamosguardadoenR6elpunteroalbloquellamado,lopodemosutilizarde#baseparasumarleeloffsetdondeseencuentraelpunterodecadenaesttica,#yenelguardarleelpunteroalaunidadA(queeslaactual).
MOV BP,R6 #Vuelvoaapuntaralbloquellamadoparacontinuarlaejecucin
Porltimovamosaaclararundetalle.SabemosquelaunidadBpuedellamaralaC,peroloquehayquesaberesquenopuedeaccederasusvariables.EstoesporqueparaqueBaccedadebeirhaciaatrsunavezporlacadenaestticaparaencontrarelregistrodeactivacindeAqueesdondeestdeclaradaC.PoresoBaccedeallamaraCperonopuedeaccederasusvariables,porquenuncallegaapararsesobresuregistrodeactivacin(perosiaccedealregistrodeA,poresopuedeversusvariablesyladeclaracindelaunidadC).
Clasificacindelasvariables:
Yaque conocimos la clasificacinde los lenguajes deprogramacin, ahoravamos a clasificar las variablescon elmismocriterio.
Est ticas: tienen lugar y tamao fijo en toda la ejecucin del programa. Se encuentran en el cdigo en unaposicinabsolutaenmemoria.Porlogeneralnoseencuentranenlosregistrosdeactivacin.SonpropiasdelosLenguajesEstticoscomoCobolyFoltran.
Semiestticas:tienenlugarvariableendistintasejecucionesytamaofijo.SonpropiasdelosLenguajesbasadosenlaPila.Elregistrodeactivacinquelascontienevariadelugar,peroloquenovariaeseloffsetdelavariabledentrodelmismo.
Unarreglodelmitesfijosesdeestetipo.Porejemplo:intv(10to20)
Elcompiladorubicaestavariableenelregistrodeactivacin,sabedondeempiezaydondeterminaporquetieneloslmitesespecificadosalmomentodeladefinicin(almacenatodosloselementosdelarraydeformacontigua).Estosemuestraenlasiguienteimagenparaelarraydelejemploanterior
IniciodeRA OffsetdeV OffsetdeV(12)
v10 v11 V20...v12
15
Almomentodecompilarunaccesoaunelementodelarray,elcompiladorgeneraunafrmulaparacalculareloffsetdelelemento solicitado.Supongamosque sehaceunaasignacincomolasiguiente:v(i)=2.Primeroelcompiladoraveriguaeloffsetconlaformula
Dv(i)=Dv+(i10)*TE
Donde:Dv:eseloffsetdondecomienzanlosvaloresdelarraydentrodelregistrodeactivacin.Dv(i):eseloffsetdelelementoquequeremoscalcular.i:eslavariablequeelprogramadorutilizcomondicedeacceso.10:esellmiteinferiorenladeclaracindelarray.TE:eseltamaodelelementoenposicionesdememoria.Porej,siesintpuedeser2bytes,float4bytes,etc.
Todos los elementos de la frmula son conocidos en tiempo de compilacin ya que el tipo es fijo, como asitambinloslmitesdelvector.EsporesoqueelcompiladorgeneralasinstruccionesembebidasenelcdigoparaobtenereloffsetDv(i)cadavezqueelprogramadorhace referenciaaunelementodelarray.Enelregistrodeactivacinlonicoquehayguardadosonlosvaloresdeloselementosdelarray.
Otravariablesemiestticaesunamatriz.Porejemplo:inty(10to20,30to40)
Haydosmanerasdeguardarunamatrizenmemoriadentrodelregistrodeactivacin.Ellenguajedebeestipularunadelasformasyguardartodassusmatricesdeesaforma.Enambasseguardademaneralinealycontigua.Lasformasson:
1. Almacenamientoporcolumnas:Sealmacenaprimerolalneadeelementosquevandesdeelprimer elemento hasta el ltimo de la primer columna, luego se almacena desde el primerelementohastaelltimodelasegundacolumna,yassucesivamente.
2. Almacenamiento por filas: Se almacena primero la lnea de elementos que van desde elprimerelementohastaelltimodelaprimerfila,luegosealmacenadesdeelprimerelementohastaelltimodelasegundafila,yassucesivamente.
IniciodeRA
OffsetdeY OffsetdeY(12,30)
y10,30 ...y11,30 y12,30 y10,31y20,30 y20,31...
PrimerColumna SegundaColumna
IniciodeRA
OffsetdeY OffsetdeY(12,30)
y10,30 ...y10,31 y10,32 y11,30y10,40 y11,40...
PrimerFila SegundaFila
16
Enestoscasos,ocurre lomismoqueen losvectores, los lmitessonfijosy los tiposdeelementoquecontienetambin,porlotantoelcompiladorembebeunafrmuladeacceso.Estafrmuladependedecmosealmacenelamatriz.
Paraalmacenamientoporcolumna,eslasiguiente:
Dy(i,j)=Dy+[[(j30)*(2010+1)]+(i10)]*TE
Paraalmacenamientoporfila,eslasiguiente:
Dy(i,j)=Dy+[[(i10)*(4030+1)]+(j30)]*TE
Donde:Dy:eseloffsetdondecomienzanlosvaloresdelamatrizdentrodelregistrodeactivacin.Dy(i,j):eseloffsetdelelementoquequeremoscalcular.i:eslavariabledefilaqueelprogramadorutilizcomondicedeacceso.j:eslavariabledecolumnaqueelprogramadorutilizcomondicedeacceso.10:esellmiteinferiordefilaenladeclaracindelamatriz.20:esellmitesuperiordefilaenladeclaracindelamatriz.30:esellmiteinferiordecolumnaenladeclaracindelamatriz.40:esellmitesuperiordecolumnaenladeclaracindelamatriz.TE:eseltamaodelelementoenposicionesdememoria.Porej,siesintpuedeser2bytes,float4bytes,etc.
Porejemplo,siqueremosaccederalelementoy(12,30)conalmacenamientoporcolumnas,laecuacinnosdalosiguiente:
Dy(i,j)=Dy+[[(j 30)*(2010+1)]+(i 10)]*TEDy(12,30)=Dy+[[(3030)*(2010+1)]+(1210)]*TEDy(12,30)=Dy+[[(0)*(11)]+(2)]*TEDy(12,30)=Dy+[2]*TE
Otroejemplo, siqueremosacceder al elemento y(12, 30) conalmacenamiento por filas, la ecuacin nos da losiguiente:
Dy(i,j)=Dy+[[(i 10)*(4030+1)]+(j 30)]*TEDy(12,30)=Dy+[[(1210)*(4030+1)]+(3030)]*TEDy(12,30)=Dy+[[(2)*(11)]+(0)]*TEDy(12,30)=Dy+[22]*TE
En cada caso, simultiplicamos el resultado por el tamao enposiciones dememoria del elemento y a eso losumamosaladireccininicialdelamatrizencontramoselelemento.
Existenlenguajesqueverificanqueloslmitesqueescribeelprogramadoralaccederaunelementoseencuentrenenelrangoconlosquefuedeclaradolamatriz.Porejemplo,unaccesodey(5,8)noseravlidoenlenguajesquecontrolanellmitecomoPASCALyADA,sinembargoseratotalmentevlidoenlenguajescomoC.Esecontroldelmitesserealizamedianteinstruccionesembebidasenelcdigo:
If(ilimiteSuperior1)Error
If(jlimiteSuperior2)Error
Observequelos lmitesdelmatrizno seencuentranalmacenadosenmemoria, sinoqueestnembebidosenelcdigocomoconstantes.Estotambinocurreparalosvectores.
17
Semidinmicas:sondetamaoylugarvariableendistintasejecuciones.Sololosarreglosconlmitesvariablescaendentro de esta categora.Una vezque secrea el registrode activacin nocambia, por ejemplo,un arraydeclaradocomox[2..n,3..m]dondenymsonvariablesglobalesqueyatienenunvalorantesdequelaunidadquecontieneestadeclaracinseallamada.Entonces,endiferentesejecucionesnymtendrndistintosvaloresypor consecuencia el arreglo tendr distinto tamao, pero una vez creada este tamao no cambia. El arreglo esdimensionadoenelmomentodecrearelregistrodeactivacin.
Este tipo de estructuras tienen un descriptor, que contiene los valores de los lmites ya que deben estar enmemoriaporquealnoserconstantesnosepuedenembeberenelcdigo(noseconocensusvaloresalmomentodelacompilacin).Estoslmitesseguardanenundescriptor(juntoaltamaodelaestructurayunpuntero)delcual se puede decir que se comporta como una variable semiesttica. Este puntero indica el lugar donde seencuentranlosdatosdelarreglo.Estosdatosseubicanalfinaldelregistrodeactivacinyaquealserdetamaovariable,primerodebenubicarselasvariablessemiestticasportenerunoffsetfijorelativoalcomienzodelR.A.Observeelgrficoacontinuacin:
Paracompilarunaccesoalarreglo,semanejacomoconlosarreglossemiestticos(embebiendolafrmula)peroenvezdedejarlosvaloresdeloslmitescomoconstantes,utilizalosvaloresalmacenadoseneldescriptor.
LenguajescomoADAtienenestetipodevariables,peronoeselcasodellenguajeC.
Dinmicas:el lugaresvariabley el tamaocambiaencualquiermomento luegode tenerasignadoespaciodealmacenamientoparalavariableencuestin.Elcontenidodevalordeestasvariablesnoestnenelregistrodeactivacin,encambio loquesi estesunpunteroqueapuntaaunsectordememoriallamadoHEAPdondesealmacenanestetipodeestructuras.Sedividenendostipos:
o Annimas: EnC,sondeclaracionescomolasiguiente:
int*punteropuntero=malloc(50)
Lavariablepunteroessemiesttica,seencuentraenelregistrodeactivacinycomosesabe,esunpunteroaunaestructurade tipodedato int.Cuandose realizaelmalloc, elcompilador reserva 50posicionesenelHEAPyhacequelavariablepunteroapunteaestaestructura(queeslavariableannima). Esel usuario elque se encargadelHEAP, pide y devuelvememoriade formaexplicitacomovimosenelcdigodeejemplo.
(otrasvariables)
Descriptor
DatosdelArreglo
R.A.
Puntero
HEAP
50
Variablesemiesttica Variabledinmicaannima
18
o Connombre:EnAlgol68,soncosascomoesta:
Flexvar(1:0)ofintvar=(1234)var=(12)var=(123)
En este cdigo se declara un arreglo de enteros y en cada asignacin se le da distinta cantidaddevalores(encadaunase redefineel tamaodelvector).Enel registrodeactivacin seencuentraundescriptorqueentreotrascosastieneunpunteroalHEAPdondeseencuentranlosvaloresdelarreglo.Ladiferenciaconelanterioresqueestacoleccindevalorestienenombreyseadquierememoriaenformaimplcitacuandoselomanipula.
RecordemosqueelHEAPseencuentraenelmismobloquequelosregistrosdeactivacin.
EnlenguajeC,soloexistenvariablessemiestticasydinmicasannimas.EnADAsoloexistenvariablessemiestticas,dinmicasannimasyvariablessemidinmicas.
Super dinmicas: Sonlasvariablesdinmicasdeloslenguajesdinmicos.Obviamentecambiandetipodurantelaejecucin. En los lenguajes dinmicos no existe el registro de activacin, sino una tabla de smbolos y estasvariablesestnincluidasenlpormediodeundescriptor,queentreotrascosastieneelnombredelavariableconlaquesereferenciaenelcdigoyunpunteroalHEAPdondeseencuentraelvalordelamisma.
Elerrordequereroperarvariablesdedistintotiposoloocurreenejecucinporquelostipodevaloresquetienenlasvariablesdependendelaejecucin.
Valeaclararquetodosloslenguajesgeneranunatabladesmbolosentiempodecompilacinparapodergenerarelcdigo,perolosnicoslenguajesquetienentabladesmboloenmemoriamientrasejecutansonlosdinmicos.
R.A.
Descriptor
HEAP
var
Variablesemiesttica Variabledinmicac/nombre
Ejecutable
RegistrosdeActivacin
HEAP
19
ProblemasconPunteros
Como vimos, dentro del registro de activacin puede haber punteros hacia otras estructuras como pueden ser avariables semiestticas, semidinmicas, descriptores que apunten a estructuras en el HEAP, etc. Alguno de estospunteros son generados por el compilador sin que el programador sepa de su existencia, pero otros punteros soncreados por el programador y es ah donde se presentan los inconvenientes. A continuacin diagramamos loanteriormenteexpuesto:
Lasflechaspunteadassonpunterosqueelcompiladorconstruyeyqueelprogramadornopuedever.Conestetipodepunterosnosurgenproblemasyaquesonadministradosporelprogramadeformatransparenteparaelprogramador.
Lasflechasconlnearepresentanpunterosadministradospor elprogramador.Eselcasode: Punterosqueapuntanaotravariablesemiesttica. Ej:
inta=5int*pp=a
VariablesdinmicasannimasquetienenunpunteroreferenciandoaunbloquededatosenelHEAP.Ej:int*punteropuntero=malloc(50)
Punterosqueapuntanavariablessemidinmicas.
Elmotivoporelcualseproducenproblemasconestegrupodepunterosesporqueelprogramadorpuedehacerunamalaadministracindelosmismos.Veamoslosproblemasquepuedensurgir:
ConflictodeTipos
Engeneral,elpunteropuedeapuntaracualquiertipodevariablesalvoqueellenguajenolopermita.Elcasoclsico de este conflicto se d en el lenguaje PL/I. Existe un tipo de dato del puntero que se le otorga aldeclararlo.Luegoaesepunterolepuedodarunadireccindeunavariableenteraodeunaconcomaflotante.Masadelanteendeterminadopuntodelprogramanopuedodeterminar si esepunteroapuntaaque tipodedatoporqueestodependedelflujodeejecucindelprograma.Elcdigodeejemplo:
DeclarePPointerDeclareAFixedBase
Datosdevariables
semidinmicas
Descriptoresdevariables
dinmicasconnombre
Descriptoresdevariables
semidinmicas
Variablessemiestticas
RegistrodeActivacin
HEAP
20
DeclareBFloatBase
P:=Addr(A)P:=Addr(B)
Lamayora de los lenguajes exige que se defina el tipo de dato al queapunta el puntero y lo controla entiempodecompilacin.
PunterosColgados
Enestecasoelprogramadormanipulalospunterosdetal formaqueluegode tomarunbloquededatos, loliberadejandounpunterosealandolazonaquefueliberada.EjenC:
p=malloc(100)q=pfree(p)
Enesteejemplo,sereserveunbloquede100bytes,luegoseasignaelpunteroqparaqueapunteaesebloqueyfinalmenteseliberaelbloquedejandoalpunteroqapuntandoalazonadondeyanoest.
Otrocasotpicodeesteproblemasedebealtiempodevidadelospunteros.Sitengounpunteroglobalylosdatossonlocales,cuandoseterminalaunidadestosdatosyanosernvlidos,sinembargoelpunteroseguirapuntandoaesazona.EjenALGOL:
ProcZ1intxrefintpx
ProcZ2intyrefintpy
Px:=x//mismombito(globales):ok
Py:=x//alretornar,elpunterodesapareceperomantengolosdatos:ok
Px:=y//alretornar,pierdolosdatosyelpunteroquedacolgado:mal
Py:=y//mismombito(locales):ok
......
...
Deloscuatrocasosqueseexplicaenelcdigo,eltercerosufredeproblemasdepunterocolgadoyaquealterminar la ejecucin de la unidad Z2, la variable y deja de ser direccionable pero el puntero sigueapuntando a la zona dememoria donde se encontraba. EnALGOL ese cdigo dara error de compilacinporquecontrolaqueenasignacionesdepunterosqueelqueestalaizquierdatengaunmenoroigualalcancequeelqueestaladerecha.Peroenotroslenguajes,estonosecontrola,permitiendoelproblemadepunteroscolgados. Es fcil esquematizar lospunteros susceptibles de teneresteproblema, son los queapuntanaundatoqueseencuentraenunregistrodeactivacinsuperior.
Garbage
EstoocurrecuandohayunbloquededatosenelHEAPdelcualseperdisupunteroypor lo tantonohayformadeaccederal(porlogeneralocurrenconvariablesdinmicasannimas).EjemploenC:
A
B
21
p=malloc(100)q=malloc(200)p=q
Primeroreserv100bytesapuntadosporp,luegoreservotros200apuntadoporqyfinalmentehicequepapuntea los200bytesreservadosen la segundalnea,dejndomeinaccesible los100reservadosen laprimera.Notengootropunteroapuntandoalbloqueperdidoporlotantoesinaccesible.
LenguajesdeProgramacinySistemasOperativos
Cadaunodeestoselementosnoesindependientedelotro.Unoafectaalotroyviceversa.VamosaestudiarcadatipodeSistemaOperativoycomofuncionanlaejecucindeloslenguajesencadacaso.
SistemaOperativoconParticionesFijas
EnestosSistemaselprogramacorreenunaparticinfijadememoriaquenovariaalolargodeltiempo.Ellenguajeponeloselementosenmemoriaenelsiguienteorden:
Ejecutable Variablesestticas Lapiladeregistrosdeactivacin ElHEAP
Comosabemos,lapilaescompacta,crececoncadallamadoaunaunidadydecrececuandoseretornadelllamado.EncambioelHeapesunbloquededatosdesordenado,quecontienehuecoslibresyquecrecedemaneramasrpidaquelapila.Ejemplodeporqueocurreesto:
p=malloc(100)q=malloc(200)
free(p)
p=malloc(150)
z=malloc(40)
Enelejemplovemoscomodetantopedirydevolvermemoriadedistintotamaoquedanhuecosenelmedio.ExistenmuchaspolticasdeasignacindememoriaparaelementosenelHeapperonoentraremosendetalle(enelejemploutilizamosFirst Fit, podrahaber sidounaBest Fit o cualquier otra). ElHeap se va acercando a lazonadonde seencuentralapilayalmismotiempodesperdiciandomemoria.
EsquemadememoriaparalenguajestipoAlgolySistemasOperativosconparticionesfijas:
Ejecutable VariablesEstticas
Reg.Act.1
Reg.Act.2
Reg.Act.3
Usado1 Libre1 Usado2 Libre2 Usado3 Usado4
200 100libre
200libre libre
200150 libre
libre200150 40
22
Aquserepresentalaparticinfijadelamemoriadondeestcontenidoelprograma.Sobrelaizquierdaseencuentrael ejecutable, lasvariablesestticasy lapilade registrosdeactivacin, a laderecha seubicaelHeap.ExistendosestructurasquesonutilizadasparamantenerlosespaciosusadosyloslibresdelHeap.
Lista de usados: Dentro de las variables estticas se encuentra un puntero al primer bloque de usados del Heap.Luego, dentro de cada bloque de usado hay una lista enlazada donde cada uno apunta al siguiente dentro de lacadena(enelgrficoestrepresentadoporlasflechasslidas).
Listadelibres:DentrodelasvariablesestticasseencuentraunpunteroalprimerbloquedelibresdelHeap.Luego,dentrodecadabloquede librehayuna listaenlazadadondecadaunoapuntaalsiguientedentrode lacadena(enelgrficoestrepresentadoporlasflechaspunteadas).
Almomentodereservarunbloqueparausarlo,ellenguajereservaM+Ncantidaddebytes,dondeMeslacantidadsolicitadaporelprogramadoryNeslacantidaddebytesqueocupaunpuntero,yaqueenelbloquedebecontenerseelpunteroalsiguienteusado.
Elmallocrecorrelacadenadelibresyleasignaunbloquequenoestsiendousadoparaocupar.Vanavegandoporlalistadesdeelfondohacialazonadelapilaenbuscadelacantidaddebyteslibressolicitada(enelcasodefirstfit).
El freepasaunbloqueusadoa la cadenadelibresy recompone la listaenlazada.Dos librescontiguos se juntanyquedanagrupados.
Estospunterossontotalmentetransparentesparaelprogramador,losadministraellenguajedentrodelasllamadasdepedidoyliberadodememoria.
ElverdaderoconceptodeGarbage(basura)consisteenquealgunodelosbloquesdeusadosquevimosenelejemplono tiene un puntero que lo referencie dentro de la pila de registros de activacin y a su vez (obviamente) estcontenidodentrodelacadenadeusados.Enesecaso,estamosenpresenciadefragmentacinygarbage.
EsquemadememoriaparalenguajesdinmicosySistemasOperativosconparticionesfijas:
Interprete Programa TabladeSmbolos Usado1 Libre1 Usado2 Libre2 Usado3 Usado4
Enestoslenguajesnoexistenlascadenasdelibresyusados(noexistemallocyfreetampoco).Loqueexisteesunatabla de smbolos que contiene la referencia hacia el sector de Heap donde se encuentra los datos del bloquepropiamente dicho. Losmovimientos en el Heap tienen que vermas con cambios de tipos (por ejemplo, que unavariablepaseaserdeunnuevotipomasgrandequeelanterior).
El programador no ve los punteros, solo ve las variables. Cada bloque usado tiene su puntero desde la tabla desmbolos,larelacinesunoauno.ContodoestosededucequenoexisteelGarbagecomoenelcasoanterior,solohayfragmentacin.
Por lo general, estos tipos de lenguajes implementan un Garbage Collector que se encarga solo de compactar lamemoriaparaeliminarbloqueslibresenmediodebloquesusados.Estoestransparenteparaelprogramador.
GarbageCollectorenLenguajesDinmicos
Acontinuacinseexplicaelalgoritmoqueejecuta:
23
Elinterpreterevisalatabladesmbolosmirandolospunterosyeligeelqueapuntealadireccinmasaltadememoria
Sepreguntasiestalfondodelaparticinfijao Siloest,simplementelamarcacomoyarevisadao Sinoloest,correalfondoelbloquededatos,obviamentesinpisarotrosbloquesqueseencontraran
masatrs.Lamarcacomoyarevisada Vuelvearealizarlaoperacinsoloqueignorandolosbloquesyarevisadosyhastaquenoquedeningunosin
revisar.
Estealgoritmoseejecutaenelmomentoespecificadoporeldiseadordellenguajesegndiversoscriteriosqueestepuedaadoptar.Paraelprogramadorresultaimpredecible.Existenlenguajesquepermitenejecutarelprocesoconunllamadoaunafuncin.
GarbageCollectorenLenguajesTipoAlgol
Acontinuacinseexplicaelalgoritmoqueejecutaparalaeliminacindegarbage: Recorrelalistadeusadosyacadaunolecolocaunamarca. Luegorecorre todoslospunterosqueseencuentrenenlapiladeregistrosdeactivacinyparacadabloque
apuntadoborralamarcaquepusoenelprimerpaso.Tambinsefijaenaquellospunterosqueseencuentrancontenidosencadaunodelosbloquesalosqueleborra lamarca,con locual,siunbloqueusadonotienepunteroenlapilaperositienepunteroenotrobloquedeusadosquedaincluidoenestepaso.
Recorrelacadenadeusadosliberandolosbloquesqueconservanlamarca.
Mientras que el primer y el tercer paso son sencillos, el segundo es muy complicado. Obliga al lenguaje a tenercontroldetodoslospunterosquemanejaelusuario.
Otracomplicacinesqueenel segundopaso,el algoritmo tieneque recorrer losbloquesylospunterosdedichosbloquesquesongeneradosporelusuario.Estasestructuraspuedenserrboles,listas,grafos,etc.Porlogeneral,estostiposdealgoritmosestnasociadosconllamadasrecursivasyesonecesitamuchamemoriaparaejecutar.Justamente,elgarbagecollectorseejecutacuandofaltamemoriaconlocualesunproblema.Sinembargo,sediseounalgoritmoque realiza esta tarea y no necesita ser recursivo. El algoritmo tiene tres punteros y con ellos va avanzando yretrocediendodentrodelaestructura.Enprimerainstanciahacequelostrespunterosapuntenunoacadanodocomofiguraacontinuacin.
Luego,avanzaconelpuntero2alnodoHperoantesdoyvueltaelpunteroquetieneBparaqueapunteaA.EstoesporquesinoluegonovaatenercomovolveraAunavezqueterminalarecorridadeestarama.
A
B
D
H
M
C
E
Puntero1
Puntero2
Puntero3
24
Hacelomismoconelpuntero1.
Ydeestaformavarecorriendocadanodoyrealizandolasmarcas.Elmotivoporelcualdavueltalospunterosdelamismaestructuraesparapodervolverdandopasoshaciaatrsynonecesitarmuchospunteros,esdecir,aprovechalospunterosqueyatienelaestructura.Alirvolviendorestituyelospunterosdelaestructuraoriginal.
Ademsdeeliminarelgarbage,tambinsedebecompactarelHeap.Pararealizaresto,elGCdebebuscarcadabloqueusadoyporcadaunotienequerealizarelalgoritmoqueseexplicanteriormenteenbuscadepunterosqueapuntenadichobloqueparapoderrefrescarlos.Estoesdeuncostocomputacionalaltsimoaunquepuedeimplementarse.
Por lo general, no existen implementaciones de garbage collector en lenguajes de tipo Algol debido a losinconvenientes que fuimos describiendo. En vez de eso, algunos lenguajes utilizan una tcnica conocida comocontadordereferencia.Esta tcnicaconsisteenasignarleacadabloqueusadounvalorqueindica la cantidaddereferenciasqueapuntanadichobloque.Sise leagregaotrareferencia,elcontadorpasaaser2,siluegose lequitaunareferenciavuelvea1ycuandoelbloqueyanotengareferenciasequedaen0yeseliminadodelalistadeusados.Porejemplo,tenemosdospunterosapuntandoaunbloquecadauno:
A
B
D
H
M
C
E
Puntero1
Puntero2
Puntero3
A
B
D
H
M
C
E
Puntero1
Puntero2
Puntero3
1
1
p
q
25
Luegoseejecutat=q:
Luegop=q:
Elbloquedearribaesdescartadoyaquesucontadordereferenciasestenceroylamemoriaesliberada.
Estealgoritmoessencillo,rpidoyeficienteperotieneunproblemayesquenofuncionabienconlistascirculares.Supongamoslosiguiente:
Observequeloselementostienenunpunterodentrodesuestructuraqueapuntaaotrodeloselementosdelalista.Asuvez,tenemosunpunteropqueapuntaaunodeloselementosyporelcuallaestructuraesaunaccesibleparaelprogramador.Siluegoeliminamoselpunterop,laestructuranosquedadelasiguientemanera:
1
2
p
q
t
0
3
p
q
t
2
1
1
p
1
1
1
26
En este momento la estructura ya no es accesible para el programa que se est ejecutando, pero sin embargo loselementosnoseeliminandelamemoriaporquecadaunotieneunareferenciaapuntndole.Elalgoritmofallacuandohaygrafos.Estonopasaparaestructuratiporbolyaquelarazessoloapuntadaporelpunterodeusuarioysiesteseelimina,larazquedaenceroytambinseelimina.Estoocasionaeldesalojoencascadadeloselementosrestantes.
SistemaOperativoconSegmentos
Enestecaso,elsistemaoperativoleentregaalprogramaunsegmentodememoriaelcualelprogramanopuedesalirdeah.Enelcasodeloslenguajesestticos,nohayproblemasyaquealconocersecuantamemoriasenecesitaseledajustolaquenecesitaynohaydesperdicios.ParalenguajesdeTipoAlgolyDinmicosnosesabecuantamemorianecesitar un programa de antemano, entonces el Sistema Operativo deja que lo defina el mismo programa. Porejemplo, losEXEs deWindows tienen una cabecera en donde se incluye entre otras cosas el tamao dememorianecesitadoparaejecutarelprograma.Peroelcompiladortampocopuedepredecircuantoespaciovaanecesitarparaejecutar,asiquenecesitaqueelprogramador se lo indique.Loscompiladorestienenunaopcindonde selepuedeindicarcuantamemoriapediralSistemaOperativocuandosevayaaejecutar.Siesaopcinnoesutilizada,siempreexisteunvalorpordefectoqueelcompiladorutilizayqueesunmontobastantegeneroso,loqueimplicaquesiguehabiendoperdidadememoria(fragmentacininterna).
ExistenSistemasOperativosqueentregandiferentes tiposde segmentosa losprogramas (segmentosdecdigo,dedatosydepila).Enesecaso,leentregaacadaprogramaunsegmentoparaelcdigo,otroparalasvariablesestticas,otroparalapilayotroparaelHeap.Enestoscasosdesapareceelenfrentamientodeespacioentrelapilayelheap,peroahoraestosdosvanalucharcontraeltopedelsegmento(permanecelamismaproblemtica)ysigueexistiendolafragmentacininterna.
SistemaOperativoconPaginacinyMemoriaVirtual
Eneste caso, el SistemaOperativo entrega segmentos fijosmuchsimomasgrandes al programa ya que estos sonpaginadosypuedenalmacenarseeneldiscosinoseutilizan.Losproblemassonlosmismosperoaltenermasespaciodifcilmentelapilayelheapsechoquen.Lafragmentacininternapodraversecomomuchomasgrandeperoelcasoesqueaquellaspginasquenoseanaccedidasporelprogramavanaestarenmemoriavirtual(discorgido)conlocualnosedesperdicialamemoriaprincipal.Lomismoocurreconlaspginasdondehayagarbage,nosonaccedidasypermanecen en el disco. El programador puede cometer muchas equivocaciones, generando garbage pero no esproblemayaqueestosestnmitigados.
NotasobreObjetos
Hastaahoranohablamosnadadeestetema.LosObjetostienenlamismaspropiedadesquelasvariablesencuantoalaubicacinyelaccesoa losmismospara lenguajedeTipoAlgol.Para lenguajesDinmicos, seencuentranen latabladesmbolos.Ladiferenciaestenquemientrasunavariablesolotienedatos,elobjetotienedatosypunterosalosmtodosqueimplementa:
DatosdeVariable
DatosdeObjeto
Mtodo1
Mtodo2
Mtodon
27
Losobjetosdelenguajesmasmodernostienenunatabladedespachocomnparainstanciasdelamismaclasedondeseencuentranlospunterosalosmtodos:
ConcurrenciayHebrasdeEjecucin
SabemosqueunSistemaOperativopuedemanejarconcurrencia,unejemplodeestoesUNIX.Tambinsabemosqueexistenlenguajesqueejecutantareasconcurrentes,porejemploADA.Estasdoscuestionessonbiendiferentes,porunladoestlaconcurrenciaquemanejaelSistemaOperativo(tienelacapacidaddeadministrarejecucionesparalelasdediversosprocesos)ylaquemanejaelLenguaje(poseeestructuraseinstruccionesquepuedeusarelprogramadorparaadministrar de forma paralela diversas tareas de un mismo programa). Estas cuestiones se presentan y puedencoordinarentrelasdos.Veamoscadaunodelosambientes:
SistemaOperativo sinconcurrencia /Lenguaje sinconcurrencia:Obviamente,no existe la concurrenciaenestesistema.
SistemaOperativoconconcurrencia/Lenguajesinconcurrencia:ExistelaconcurrenciaadministradaporelS. O. El lenguaje cree que l solo est corriendo en el procesador mientras que el S. O. conmuta entreprocesosindependientes.
SistemaOperativosinconcurrencia /Lenguajeconconcurrencia:Existe laconcurrenciaadministradaporellenguaje. Este es el que implementa los mtodos de sincronizacin y lo que se conmuta es entreprocedimientosdelmismoprograma.
SistemaOperativoconconcurrencia /Lenguajeconconcurrencia:Dentrodeestacategorapuededarsedossituacionesdistintas:
o El SistemaOperativo y elLenguaje no se conocen:Esto significa que uno no sabeque el otro esconcurrente.ExistendoscolasdeCPU,unalamanejaelS.O.(dondeseconmutaporproceso)ylaotraelLenguaje(dondeseconmutaporprocedimientodentrodelprograma).Cuandounprogramaesseleccionadode lacoladelistosparaejecutar,esteeselque indicaqueprocedimientoeselque seejecutar en ese ciclo. Tambin se manejan prioridades independientes (el S.O. no reconoceprioridades entre los procedimientos de un proceso) y de esta forma no se pueden evaluar enconjunto.
o El Sistema Operativo y el Lenguaje se conocen: El lenguaje descansa en el S. O. para laimplementacin de la cola de listos. El S.O. conmuta entre procedimientos (hebras) del mismo
DatosdeObjeto
ProaTabla
Mtodo2
Mtodon
Mtodo1
DatosdeObjeto
ProaTabla
TabladeDespacho
28
procesoanalizandosusprioridades.EnestepuntoesdondeelS.O.empiezaaconoceracercadelascaractersticasdelosprocesosqueejecuta.
Teniendoconcurrencia,unprogramadejadeserlineal,conlocualunasecuenciadellamadoscomolasqueveamosantespuedeserdelasiguientemanera:
CFMAB
DROP
Conestasituacin,yanosepuedeutilizarunapilacomolaestbamosutilizandoantesporquepierdesucarcterdeLIFO.Siarmamoslapiladellamadascomolohacamosantes,seriaalgocomolosiguiente:
Pararealizaresto,elcompiladoralmacenaenunsectordistintoyalejadodelamemoriaacadaregistrodeactivacin.ConestocadapilapuedechocarconcualquierotraeinclusoconelHeap.PerorecordemosqueenS.O.conmemoriavirtualtenamosmuchoespacioenelsegmentoconlocualnodebemospreocuparnos.
Pararesolverdondeponerlaspilas,elS.O.solicitaqueelprogramaseloindiqueyasuvezestealprogramador.Sinoesindicado,seubicacadapilaenlamitaddelsegmentoquelequededisponible.Esdecir,laprimerpilaadicionalvaairenlamitaddelsegmento,lasegundaenlamitaddelamitad,etc.
R.A.deA
R.A.deB
R.A.deC R.A.deD
R.A.deF
R.A.deM
R.A.deR
R.A.dePR.A.deO
Ejecutable
Pila1
HEAP
Pila2
Pilan
29
PasajedeParmetros
Sesabequecuandounaunidadinvocaaotra,lepuedeenviarparmetrosdeentradayrecibirunarespuestaluegodelaejecucin.Paraesto,launidadqueinvocaselellamaunidadllamadoraylaqueesinvocadaselellamaunidadllamada. La unidad llamadora tiene los parmetros reales a la unidad llamada, la cual define los parmetrosformales.
Clasificacinsegnlasintaxis:
AsociacinPosicional:Cadaparmetrorealseasociaconunoformalsegnlaposicinqueocupan.Dentrodeestacategorasedividenen:
o SinFaltantes:Tienequeserunoauno,nohayfaltantes.Encadallamadoexistelamismacantidaddeparmetrosrealesquedeformales.
o ConFaltantes:Un llamado a una unidad puede no tener especificado todos los parmetrosque sedefinenenladeclaracinformalDentrodeestosseclasificanen:
FaltantesalFinal:Ellenguajepermitequelallamadaalafuncinnotengalamismacantidadde parmetros en en la definicin formal pero los que falten son los que se encuentran alfinal.Ejemplo:
FuncionA(a,b,c)FuncionA(intx,inty,intz,intw)
La llamada que se encuentra a la izquierda tiene tres parmetros reales mientras que ladeclaracindelafuncintienecuatroformales.Elvalorquenosesuministraeseldewyellenguajedebeimplementaralgnmtodoparadefinirelvalordeeseparmetrocuandonoesexplicitado.
FaltantesenCualquierLugar:Ellenguajeofreceunaformadeindicarqueparmetrossonlosqueselepasaelvalorycualesno.Ejemplo:
FuncionA(_,_,3)FuncionA(intx,inty,intz)
AsociacinExplicita:Enlallamadaseindicaexplcitamentequevalorrealseasignaaqueparmetroformal.EjemploenADA:
FuncionA(xas3,yas4)FuncionA(x,y)
AsociacinAnnima: La unidad recibe una cantidad variable de parmetros a partir de algn mecanismoimplementadoporellenguaje.EjemploenC:
intfuncionX(floatb,...)
Estafuncinpuedeserllamadapordiferentesllamadoscomoestos:
FuncionX(55,a)FuncionX(2,3,8,4)
Unejemplodeestoeselprintf.Ejemplo:
printf(Valores:%d,%d,a,b)
30
Losparmetrospuedentenerunvalorpordefectosiesqueenlallamadanoselepasavalor.Ejemplo:
intFuncion(intx,inty,floatz=0.5)
Clasificacinsegnlasemntica:
Referencia:Estoconstaenqueelcompiladorse larebuscaparaquecadaunodelosparmetrosrealesseanreferenciadosenelcuerpodelaunidadllamadacuandolosparmetrosformalessonutilizados.Parasermasclaros,cuandounaunidadAllamaaunaunidadB,secreaelregistrodeactivacindeBperonosereservalugarparalosvaloresdelosparmetrosformales,sinoquecuandolaunidadutiliceaunodeellosenrealidadtendrunaccesoalregistrodeactivacindeAdondeseencuentranlosparmetrosreales.
Nombre:Elcompiladorreemplazalosparmetrosformalesporlosrealestextualmenteenlafuncinllamada.EstolousaAlgolyhoydiaenlasMacro.
Copia: En este caso, en el registro de activacin de la unidad llamada existe el espacio dedicado a losparmetrosformales.Esteseclasificaenlossiguientes:
o Copia Valor: El compilador en cada invocacin genera las instrucciones necesarias para copiar elvalordelosparmetrosrealesdentrodelespaciodealmacenamientodelosparmetrosformalesenelregistrodeactivacinllamado.Estoocurrealprincipiodelllamado.Ejemplo:
A(a,b)B(x,y)
Elcompiladorcreaestasinstruccioneselmomentoantesderealizarelsaltoalanuevaunidad:
x=ay=bCall....
o Copia Resultado: Realiza exactamente lo contrario, asignando los valores resultantes sobre losparmetrosrealesalfinalizarlaejecucindelaunidadllamada.Ejemplo:
A(a,b)B(x,y)
Elcompiladorcreaestasinstruccioneselmomentoantesderealizarelretornoalaunidadllamadora:
a=xb=yReturn....
o CopiaValor/Resultado:Realizaambascosas.
EllenguajeCsolotienepasajeporCopiaValoryhayquedestacarquenotienepasajeporreferencia.EstoavecesseconfundeporqueenestelenguajeloquesepermiteespasarunadireccindeunavariableporCopiaValor.Peroladireccindeesavariableseencuentraalmacenadaenelregistrodeactivacindelaunidadllamada.
EjemplodeEjecucinconDiferentesPasajes
Vamosaejecutarmentalmenteel siguiente programaescrito enun lenguaje ficticio yobtenerel resultado finaldecadaunadelasvariablesinvolucradas:
31
inteleminta(1..2)
procedurepasaje(intx)a(1)=6elem=2x=x+3
endpasaje
procedureMain()a(1)=1a(2)=2elem=1pasaje(a(elem))
endMain
Por Refer encia:Alejecutarelllamadoapasaje,aestaunidadseleestpasandoladireccinfsicadelelemento1delarray.Poresodentrodelamisma, lasrefrenciasaa(1)yxdesembocanenlamismaceldadememoria,con locualprimeroseleasigna6yluegoselesuma3guardndolaenelmismolugar.
Resultado:
A(1) A(2) Elem9 2 2
Por Nombre:Elcompiladorgeneraelreemplazotextualdelosparmetrosquedandoasi:
procedurepasaje(intx)a(1)=6elem=2a(elem)=a(elem)+3
endpasaje
Conlocual,enlatercerinstruccinutilizalacelda2delarrayyaqueenmedioselemodificaelvaloraelem.
Resultado:
A(1) A(2) Elem6 5 2
Por CopiaValor : Simplemente la x es una variable independiente que se aloja en el registro de activacin de launidadllamadayalaqueselecopiaelvalorpasadocomoparmetro.
Resultado:
A(1) A(2) Elem6 2 2
Por Copia Valor /Resultado:Pasalomismoqueenelanteriorconladiferenciaquealfinalizarelprocedimientoelvalordexescopiadoaladireccindelavariablequeseutilizcomoparmetrodeentrada(enestecasoa(1)).
Resultado:
A(1) A(2) Elem4 2 2
32
EvolucindelPasajedeParmetros
AlprincipiocuandosecreoelcompiladordeFoltranquisieronquelospasajesdeparmetrossehaganporreferencia.Elproblemasurgecuandoaunprocedimientoqueselepaseunaconstantecomoparmetroesteleasigneunvaloradichoparmetro.Ejemplo:
FuncionX(8,a) FuncionX(x,y)............x=6
EndFuncionX
Enelejemplovemoscomoelparmetrorealconelquesellamaalafuncinesun8mientrasquedentrodelcuerpodelamismaseleasignaunvaloralparmetroformalx.Nohaydondeguardaresevaloryaqueelparmetrofueunaconstante.Estoprovocalaimposibilidaddepasarconstantesoexpresionesporreferencia.
Mastarde secreoAlgolperoestenousopasajeporreferencia.Loqueusofueelpasajepornombres.Peroaestemtodoleocurraelmismoproblema.Veamosunejemploconexpresiones:
FuncionX(b+3,a) FuncionX(x,y)............x=6
EndFuncionX
Elcompiladorreemplazatextualmentelaasignacinpararesolverelllamadoyquedaasi:
FuncionX(x,y)............b+3=6
EndFuncionX
Nosepuederealizarlaasignacin,sigueteniendoproblemas.Poresocrearonelmtodoporcopias.
ADAesunlenguajequemanejatodosestosmtodosylohaceatravsdesusintaxis:
FuncionX(inA,inB,outC,inoutD)
Enestecasolasintaxisdirigealasemntica.
CompatibilidadyConversinentreTiposdeDatos
Cuando tenemos una asignacina = b pueden ocurrir dos cosas diferentes dependiendo del tipo de lenguaje deprogramacindondeseejecute:
Lenguaje Dinmico: la variable apasa a ser delmismo tipo que la variable b y ambas referencian almismodato.
LenguajeTipoAlgol:eltipodedatodelavariablebdebetenerformadetransformarsealtipodedatodelavariablea.
De aca enmas, todo lo que digamos va a aplicar a los lenguajes de TipoAlgol. Si la sentencia anterior a =bcompila,sedicequeambostiposdedatossoncompatibles.Existendostiposdecompatibilidad:
33
Nombre:Serefiereacuandolostiposdedatossonincompatiblestansolocontenerdistintonombre.EjemploenADA:
typerealesisnewfloatA:realesB:float
A+B Errordecompilacin
Elprogramaanteriornocompilaporquelasvariablessondedistintotipoapesarqueendefinitiva,realesesenrealidadunfloat.
Estructura: Se refiere cuando los tipos de datos son incompatibles solo si tienen estructuras diferentes(cantidaddebitsysignificadodelosmismos).EjemploenC:
typedeffloatrealesrealesAfloatB
A+B okyseejecuta
Sibien los tiposdedatosparecen serdiferentes,son compatiblesporqueambostienenelmismo tamaoycadaunodesusbitssignificanlomismo(esdecir,lamismaestructura).
Comovimos,CtienecompatibilidadporestructuramientrasqueADApornombre.PorquelosdiseadoresdeADAlohicieronasi?Parapoderdiferenciarvaloresqueconceptualmenteseandistintos.Ej:
typedolarisnewfloattypepesosisnewfloat
A,B:dolarC,D:pesosE,F:float
A=C+E ErrordecompilacinE:=float(A+dlar(C)) Realizalastransformacionesexplcitamente,estoestpermitido
EstohaceaADApocoescribibleperomuylegible.
Existendostipodeconversionesentretipos:
Implcitas:Sonlasqueelcompiladorgeneraautomticamentecuandoaunavariabledeuntiposeleasignaotradeuntipocompatible.
Explcita:Elprogramadorescribeestasconversionesdentrodelasexpresiones.
Notaaparte:ADAtienetiposderivados.Porejemplo:
SubtypeeurosisfloatSubtypeedadisfloatrange0..110
Estos secomportan igualqueunfloatporqueesunsubtipo,sepuedesumarfloatyedad.Sienmediode laejecucin,unavariabledetipoedadsevaderango,se arrojaunerroroutofrange.
ConversionesImplcitasenAlgol(Coerciones)
Voiding:EnAlgolesposibledefinirunavariabledetipoVoid (nulo).Estasvariablessirvenparadescartarresultadosdefunciones.EstetipodedatosnoesequivalentealpunteroaVoiddeC.
34
voidxx:=2//Elvalornosealmacenaenningnladox:=Fun(2,a)//EnAlgolnosepodaignorarelretornodeunafuncinsalvoconvoid
Widening:Esta esunaconversinde tipos dondeel valor seensancha.Porejemplo,unavariable int setransformaenunreal.
realaintba:=2//Lasdoslneascontienenwideninga:=b
Rowing:diferentesautoresdicendistintascosasacercadeestetipodeconversin,perovamosaexplicarunadeellas.LosarreglosenAlgolsellamanrows,yconstadelaasignacindeunvaloralarreglodemaneraquetodosloselementosdelarregloseinicialicencondichovalor.
[4:20]intzz:=4 //todosloselementosdezadquierenelvalor4
Uniting:UnauninenAlgolesunavariablequepuedetenermasdeuntipo.Ejemplo:
union(int,real)w
Supongamosque los intocupan2bytesy los real4bytes, entonces la estructuraw ocuparalmenos 5bytes.Estosedebeaquelaestructuratieneespacioparaguardarelmasgrandedelosvaloresyunbytemasparaindicarquetipoestguardandoacadamomento.Esecamposellamadiscriminante.
w:=4
Conestaasignacinlaestructuratomarelvalor4coneltipodedatoint.Estosignificaqueelvalorocupar2bytes,dejandootros2bytessinusoyeldiscriminanteindicarqueseestalmacenandounint.
w:=6.5
Estotambinesvlidoyconestaasignacinlaestructuratomarelvalor6.5coneltipodedatoreal.Estosignifica que el valor ocupar los 4 bytes del campo de valor y el discriminante indicar que se estalmacenandounreal.
Conestoel lenguajeproveeciertodinamismoentipodevariablesenunlenguajetipoAlgolperoesostiposestnsujetosalosquesedefinienladeclaracin.
Peroexisteunproblemacuandoseutilizaunavariabledeestetipoaladerechaenunaasignacin:
intzunion(int,real)w...z:=w
Esto no compila porque el compilador no puede asegurar que w tenga el tipo int en esemomento paraasignrseloaz.Parasolucionareste temaseinventelconceptodeclusuladeconformidad.Estaesunaestructuradedecisinqueseejecutaconsultandoeldiscriminanteenlavariabledeunin.Ej:
casewin:whenwint:z:=3*w+hwhenwreal:m:=7.1*w
esac
35
Dependiendodeltipodevalorseejecutaunadelasasignacionesocualquierotra instruccinquesepongabajo la clusula When. De esta forma el compilador acepta la asignacin y asi Algol asegura que lasunionessonseguras.
Desproceduring:Paraveresteconceptoprimerodebemosexplicarlosiguiente.Ejemplo:
procxx(...)...procyy(...)...
Puedodeclararunprocedimientosinindicarsusinstrucciones:
proctmp
Entonces,puedohacerlossiguiente:
tmp:=xx//Elprocesostmpahoraeselmismoquexx
Enestemomentosiinvocoatmpelprocesoqueseejecutaeseldeclaradoenxx.Tambinpuedohacer:
xx:=yyyy:=tmp
Estoseimplementadefiniendoatodoslosprocedimientoscomounpunteroalasinstrucciones.Estosehizoasi porque siempre se busc hacer programas genricos. En C se hizo lomismo pero con los punteros afunciones.Estoeslanocininicialdeloquedespusfuelaherenciaenprogramacinorientadaaobjetos.
Cuandoenlaasignacintengounprocedimientoaladerechayunavariablenumricaalaizquierda,envezde asignar el procedimiento a otra variable, este se ejecuta y retorna un valor. La accin de ejecutar elprocedimientoenvezderetornarsudireccinsellamaDesproceduring.Ejemplo:
intaa:=xx(...)
Losprocedimientosseejecutansitienenunavariablealaizquierdadelaasignacin.
Desreferencing: Para ver este concepto primero debemos explicar lo siguiente. Vamos a declarar lassiguientesvariablesenAlgol:
intaintbrefintcrefintdrefrefinterefrefintf
Enelcdigoanteriorsedeclarandosvariablesdetipoint,dosvariablesquesonunpunteroaunintyotrasdosque sonunpunteroaunpunteroaunint.Acavemoselmismocdigoperoen lenguajeCparaque seentiendamejor:
intaintbint*cint*dint**eint**f
Grficamentesepuederepresentarlasvariablesanterioresdelasiguientemanera:
36
Algoldefinequecadavariablerepresenta ladireccindonde seencuentraeldato.Comovemos, aybapuntan directamente al dato enmemoria, es decir, para referenciar su valor el programa realiza una solabsquedaenmemoriaparaobtenerlo.Enelcasodecyd,lasvariablesrepresentanladireccindeunaceldadememoriaquecontieneladireccindeldatofinal.Paraobtenerdichovalor,elprogramarealizadosaccesosamemoria,primeroparabuscarelvalordelpunteroyconesevalorrealizaunsegundoaccesoparaobtenereldato.Lasvariableseyfsonpunterosapunterosdeint,asiquerealizantresaccesosamemoriaparaobtenereldato.
Algol tiene la particularidad de definir que en una asignacin, la parte derecha debe rebuscrsela paradevolvereltipodevalorqueestsolicitandolaparteizquierda.Porejemplo,sitenemosa:=...loquehayaaladerechadebedevolverunint,sitenemosc:=....debedevolverunareferenciaaintysitenemose:=...debedevolverunareferenciaaunareferenciadeint.
Veamosejemplos:
o Asignacionesqueesperantipoint:Enestasasignacioneslavariablealaizquierdaesadetipoint,estosignificaqueelvaloresperadoesunvalordetipoint.
a:=bComobqueestala izquierdatambinesunint, loquehaceelcompiladoresbuscarenmemoriaelvalordebyasignrseloa lavariablea.Sedicequeestaasignacinhace1desrefer encingporqueparaobtenerelvalordebhaceunabsquedaenmemoria(besladireccindedichovalor).Notequeelaccesoamemoriaparaguardarenvalorenanoestenidoencuenta.
a:=cLavariablecesunpunteroaunint.Entonces,comoselepideunvalordeintloquehaceelcompiladoresbuscarenmemoria lareferenciayluegoconellabuscarelvalordefinitivodetipoint.Estohacedosaccesosamemoriaporlotantosedicequehay 2desr efer encing.
a:=eDelamismaformaqueelanterior,sesolicitaunintylanicaformaconeesrealizarlostresaccesosamemoriaquenosllevanaencontrardichovalor.Hace3desreferencing
o Asignacionesqueesperanunadireccinauntipoint:En estas asignaciones la variable a la izquierda es c de tipo ref int, esto significa que el valoresperadoesunadireccinquecontengaunvalordetipoint.
c:=aHabamosdichoqueenAlgollasvariablesrepresentanlaspropiasdireccionesenmemoriadesusvalores.Enestaasignacin,comocesperaporunadireccindeunint,esadireccinyaestembebidaenaconlocualnonecesitairamemoriaparabuscarladireccindelvalor.Porlotantonohaydesreferencing.
inta
intb
refintc int
refintd int
refrefinte refint int
refrefintf refint int
37
c:=dLavariabledcontieneunpunteroa int.Paraobtener suvalor sedebeaccederamemoriaconlocualserealiza1desreferencing.
c:=eLavariableecontieneunpunteroaunpunteroaint.Comosoloseesperaunpunteroaint,el compilador loquehaceesprimeroaccederamemoriaparaobtenerelprimerpunterodee el cual contiene la direccin de otro puntero y al cual accede para obtener su valor ydevolverloac.Sondosaccesosamemoria,conlocualhay 2desreferencing.
o Asignacionesqueesperanunadireccindeunadireccinauntipoint:Enestasasignaciones lavariablea la izquierdaesede tipo ref ref int,esto significaqueelvaloresperadoesunadireccinquecontengaladireccindeunvalordetipoint.
e:=aEstaasignacin es imposible y arroja error decompilacin.Esto sedebe aqueaes unadireccindeunintynohayformadedevolverleunpunteroapunterodeint.
e:=cEn este caso, la variablec en el cdigo ya es la direccin de una celdaque contiene unpunteroaint.Conlocual,siledamosaeesamismadireccinquecontienelavariablecencajaperfectoenloquepide.Porlotantonohaydesrefer encing.
e:=fSeaccedeamemoriaunavezparaobtenerelvalorquecontieneladireccinapuntadaporlavariablefyseloasignaene.Hace 1desreferencing.
La idea deAlgoleramatar ladiferenciaentre ladireccindeun valor y el contenidodelmismo.Esto dioconfusinalosprogramadores.ApartirdeAlgolloslenguajesmodernostienenundesreferencingimplcito.Porejemplo,escribamoslasmismasasignacionesenlenguajeC:
o Asignacionesqueesperantipoint:
a=b1desreferencing
a=*c2desreferencing.
a=**e3desreferencing
o Asignacionesqueesperanunadireccinauntipoint:
c=&aNohaydesreferencing
c=d1desreferencing
c=*e2desreferencing.
o Asignacionesqueesperanunadireccindeunadireccinauntipoint:
38
e=&cNohaydesreferencing
e=f1desreferencing
El operador & suprime el desreferencing implcito en C. Por ejemplo, en la asignacin c = &a si noagregamoseloperador,elcompilador loqueharaesbuscarelvalorquecontienelavariableaenvezdedarlesudireccinac.Algoparecidoocurreconlosoperadores*quesonnecesariosincluirlosparaagregardesreferencingalaasignacinademsdelqueyaserealizaimplcito.
ValeaclararquetodoestoesasiporqueellenguajeCnoconstruyeautomticamente las instruccionesparaqueelvalordevueltoenlapartederechadelaasignacinencajeconlaparteizquierdacomopasaenAlgol.
Uncasoparticular:Si tengo lavariableedelejemployquieroalterar laceldaqueapuntadirectamentealvalorint:
Deboponerlosiguiente:
(refint)e:=....
Estohacequeseomitaundesreferecing.EstaoperacinesllamadaCASTINGenAlgol(peronoeslomismoqueelcastingdelenguajeC).
ControldePrecisin
Elresultadodeciertasexpresionesdeunprograma puedendependerdelaformaquetieneelmismoderepresentarlosvaloresdecomaflotante.Ejemplo:
floatxx:=0.1if(x*10.0==1.0)
thenprintQuebien!elseprintQuemal!
Para saber que es lo que se imprime en pantalla al ejecutar el programa se debe saber el tipo de aritmtica dellenguaje.Existendosformasdeestructurarundatoencomaflotante:IEEEyBCD.EnlenguajeC,sepuedecompilarconlabibliotecaSTDLIB(utilizaIEEE)yelresultadodelprogramadaraquemal,mientrasquesisecompilaconCBDLIB (utilizaBCD)muestraque bien.EnPascal siempre se utiliza IEEEpor lo tanto devuelve Quemal.Vemoslosformatos:
IEEE:Eldatotienevarioscampos:signo,mantisayexponente.Ensimpleprecisintiene32bits(1designo,23demantisay8deexponente.Endobleprecisinson64bits(1designo,52demantisay11deexponente).Esteformatoesaptopararealizaroperacionesmatemticasrpidasyescompactoperotieneunproblema,alser una representacinbinaria existen ciertos nmeros que son peridicos pero en decimal no lo son. Porejemplo,endecimalel0.1esexactoyenbinarioesemismonmeroesperidico.Poreso,enelcdigodeejemplo,cuandoserealizalaoperacinx*10.0,altener0.1estonodaexactosinounnmeroperidicoquealcompararsecon1.0alprogramaleresultadistinto.
BCD:DelassiglasBinaryCodeDecimal,esteformatotienelaparticularidaddeguardarcadadgitodecimalconcuatrobits.Porejemplo,elvalor13.6enBCDestarepresentadoporlasiguientecadenadebits:
refrefinte refint int
Quieromodificaresta
39
00010011.0110
Estohacequeelformatorepresentefielmentelosnmerosdecimalesyaqueel0.1noesperidico,sinounafiel representacindelmismo.Lacontradeestoesque losvaloresocupanmasespaciodealmacenamiento(simplede32bitsydoblede80bits)yquelasoperacionesmatemticassonmuchomaslentas.
Para profundizar sobre IEEE decimos por ejemplo que 5 * 1/5 no nos d 1 como pensamos, porque el 1/5 esperidicoenbinario.
Algunoslenguajesylosformatos: CobolusaBCDporquenecesitaexactitud. FortranusunPreIEEE. Cusaambas. PascalusaunaIEEE. ADAusaambasperodirigidoporlasintaxis.Ejemplo:
typePesosisnewfloatdelta0.01
EstoindicaqueelfloatsemanejaconBCDcon2dgitosaladerechadelacoma.Esdecir,elvalor12.30y12.31soncontinuosinmediatos,noexistenadaentreellos.
typePesos2isnewfloatdelta0.001A:PesosB:Pesos2A=A+Pesos(B)/B=B+Pesos2(A)
Tengoqueconvertirparasumar.Sinopongolodedelta,elfloatsemanejaenIEEE.
BNF
BackusNormFormesun lenguajededefinicindesintaxisdelenguajes(unmeta lenguaje).En1957BackuscreoFoltranyusoBNFparacrearlo.DesdeesemomentoloslenguajessedefinenutilizandoBNF.
ElementosutilizadosparadefinirunlenguajeenBNF:
FlechadeDefinicin():Lafechaaladerechasignificaestadefinidocomo.Seusadelasiguientemanera:ABdondeAeselobjetoqueestadefiniendo,yBescomosedefineeseobjeto.
EntidadesNoTerminales: soncaracteresque encierran entidadesNoTerminales. Porejemplo, estoes unaentidad no terminal: . Todas las entidades no terminales necesitan ser definidas pormedio de laflechadedefinicinquevimosenelitemanterior.
EntidadesTerminales:Sonlossmbolosdelalfabeto.NodebenserdefinidospormediodellenguajeBNF.Ejemplosdeelementosterminalessonelpunto,lacoma,laletraa,todoslosdgitos,etc.
Podemosusarel|(pipe)parasimplificarvariasreglasquedefinenalamismaentidadnoterminal.
VamosadarunejemplodeunasentenciaBNFquedefineuntokenvlido:
0|...|9a|...|z||
40
Conestasreglasloquequeremoshaceresdefinirqueunavariablepuedeserrepresentadaporunaseguidilladeletrasydgitosperoconlarestriccindequenopuedecomenzarconundgito.
LaprimerregladefinealaentidadnoterminalDIGITOcomocualquieradelosdgitosdel0al9(estassonentidadesterminalesynonecesitamosdefinirlas).
LasegundaregladefinealaentidadnoterminalLETRAcomocualquieradelasletrasdelaaalazminsculas(estassonentidadesterminalesynonecesitamosdefinirlas).
Con laltima regla(que en realidad son tres reglas separadasporpipesquedefinen lamismacosa)definimos a laentidadnoTerminalVARIABLE.Enelprimercasonosdicequeunavariablepuedesersimplementeunaletra.Enlosotrosdoscasos nos dicequeuna variable puede ser lo que conocemos comovariableyademsuna letraoundgitofinal.Estonosdaunaideadeanidamientoentrereglas.Porejemplo:
Veamossilavariablenum4esvlida:
Lanesuna,asiqueporahoratenemos:um4Unaesunasegndicelatercerregla,asiquetenemos:um4Si tomamos u por la cuarta regla sabemos que una es tambin una,ycomouesunaentoncesnosquedalosiguiente:m4Sirepetimoslaoperacinanteriorperoconm,tenemoslosiguiente:4Y la ltima regla nos dice que tambin es una asi que, como 4 es unnosquedalaentidadnoTerminalcomoresultado:
Pudimospartirdeltextooriginalyverificamosqueesetextorepresentaalaentidaddentrodenuestrolenguajedefinidoporlasreglasanteriormentevistas.Estetextoentoncesesvlidodentrodenuestroprograma.
Veamossilavariable 8yesvlida:
El8esunasiquetenemos:yComoyesunatenemos:
Nohayreglaquedefinamasqueesto,asiquenopudimosllegaraladefinicindeporlotanto8ynoesunavariablevlidaparanuestrolenguaje.
Arboldeparsing:EsunaestructuraqueserealizaparacomprobarsiunaexpresinestacorrectamenteescritasegnlasreglasBNFdadas,esdecir,seutilizaparaquedadounprogramaescritoendeterminadolenguajeylasreglasBNFquecomponensusintaxis,podersabersielprogramaesvlidoono.
Ejemploderboldeparsing:
BNF:1. +2. 3. *4.
41
5. 6. 7. 8. 9. 10.11.12.0|...|913.a|...|z
Teniendoestasreglas,hacemoselrboldeparsingparaverificarsilasiguienteexpresinesvalidadentrodenuestrolenguaje: va+58*r2+p*3
regla1
regla1
regla2regla3regla3
regla4regla4regla4
regla5 regla6regla5regla5regla6
regla8regla10regla7
regla9regla11regla9regla9regla11
regla13regla12regla13regla12regla13regla12
va+58*r2+p*3
Elrbolseleedeabajohaciaarriba,cadaelementosevatransformandoenotraentidadnoterminalpormediodelaaplicacin de diferentes reglas hasta llegar a ser una expresin.Comopudimos llegar a entoncessabemosquelasintaxisdeltextodelejemplo,segnelconjuntodereglasBNFdadas,efectivamenteesunaexpresinbienescrita.Esterboldeparsingesascendente, estoquieredecirque separtedel textoaverificaryse llegaa laentidad Terminal que agrupa todo los conceptos (en este caso ). A este terminal se lo llamaENTIDADPRIVILEGIDADAoDISTINGUIDA.
Elrboldeparsingdescendenteencambio, comienzadesdelaentidadprivilegiadaysedesarrollahastaobtener lasentidades terminales que componen el texto a verificar. Si hiciramos este rbol para el ejemplo anterior,comenzaramosescribiendoen lomasalto la entidadeiramosaplicandolasmismasreglasdesdearribahaciaabajohastapoderobtenerlaexpresinqueestamosverificandoenelejemplo.
SibienelprincipalobjetivodeBNFesdeterminarsiunprogramaestabienomalescritosegnunasintaxis,tambinesutilizadoalahoraderesolverelcdigodellenguajeenlasinstruccionesresultantes.Veamosunejemplodeesto.
Tenemoslasiguienteexpresin:2+7*3.Sihacemosprimerolasuma,elvalorresultanteseria27,mientrasquesirealizamosprimerolamultiplicacinelresultadoes23.
42
SupongamoslasiguienteBNF:
1. +2. 3. *4. /5. 6. |7. .....(paraestamuestrasimplificamosladefinicindeyquesonlasmismas
queyamostramosperodebenestarsiempre.Vamosasimplificarlotambinenelrbol).
Hacemoselrboldeparsingparaelejemplo:
regla3
regla1
regla5
regla6regla6regla6
2 + 7 * 3
Comopodemosapreciar,laformulaesefectivamenteunaexpresin.Observeelmomentoqueaplicamoslaregla1,enesa reglaestamosobteniendoel resultadode2+7.Estoes,el compiladorgenera las instruccionesnecesariaspararealizarlasumaantesquelamultiplicacin.ConlaBNFutilizada,tantoeloperadordesuma,resta,multiplicacinydivisintienenlamismaprecedencia.Entonces,altenerlamisma,seresuelvedeizquierdaaderecha.Ahora,veamosotraBNFaplicadaalamismaformula:
1. +2. 3. 4. *5. /6. 7. |8. ...
Yhacemoselrboldeparsing:
regla1
regla3regla4
regla6regla6
regla7regla7regla7
2 + 7 * 3
43
Almomentodeaplicar la regla4elcompiladorgenera las instruccionesnecesariasparaejecutar lamultiplicacin.Estaserealizaantesquelasumaapesardequeseencuentramasaladerecha.AestoselellamaqueeloperadordemultiplicacintienemasprecedenciaqueeldelasumayvienedadoporlaBNF.Siobservamosestaltima,notamosquelamultiplicacinyladivisinestnunnivelmasabajoquelasumaylaresta.
Lomismoocurrecon losoperadoreslgicos(AND,OR,etc)y losoperadoresdecomparacin (,=,etc).Paracontemplarlos,agregamoslassiguientesreglasdeBNFalaanteriorquevimos:
andor==||!=
Vemoscomo la comparacindeexpresionesestunnivelmasbajoqueelusodelosoperadores lgicosandyor.Hagamoselrboldeparsingdeunacondicin:
2 + 2 > 1and5 15
44
Como podemos ver, la primer divisin que se resuelve es 2 /2. Esto en realidad es porque tuvimos que llevar eldesarrollo del rbol por el lado izquierdo para que nos quede lo siguiente: / (en eseorden).AhorasupongamosotraBNF:
5. *6. /7. 8. |5. ...
hacemoselrboldeparcing:
2 / 2 / 4
Ahora vemos locontrario!Se resuelve primero ladivisin 2 /4. Estoesporque necesitamos llevarel rbol a unaexpresin como la siguiente: / . Si procediramos a convertir el lado izquierdo en nunca podramos avanzar ya que no hay regla que contemple un y un signo / a suderecha.ConestosejemplosestamosviendocomolaBNFinfluyeenelsentidoenelqueseresuelvenlasoperacionesaritmticas.
Estoltimoquevimosobviamentetambinseaplicaalasumayalaresta,yacualquierparogrupodeoperadorescon la misma precedencia. De hecho, podemos hacer una BNF que resuelva las operaciones de multiplicacin ydivisin de izquierda a derecha y al mismo tiempo que resuelva las operaciones de suma y resta de derecha aizquierdaenunnivelmayor.
Paraterminar,vamosaincluiralosparntesisennuestraBNF.Veamosestasreglas:
1. +2. 3. 4. *5. /6. 7. |8. 9. (10.)
Comovemos, lasreglas8,9y10nuncalashabamosvisto.Loqueestamoshaciendoesagregndoleunadefinicinmasalaentidad.Estareglaloquehaceesponercomocontenidodelparntesisunaexpresinytodoloqueello implica.Estosignificaqueunaexpresincomplejaentreparntesispuedeserunfactorparaotraoperacinfueradelossignosdeparntesis.Veamosunejemplorpido:
45
(2 + 7 ) * 3
La resolucin demuestra que parapoder absorber los parntesis con una regla se debe primero resolver lo que seencuentraentreestosdossmbolosparaqueseauna.Unavezquesetieneresueltalaparteinterior,esto genera un y todo vuelve a comenzar desde el nivel inferior de anidacin. Gracias a esto, elcompilador resuelveprimerola formulamatemticaquese encuentradentrode losparntesis(queesunasuma)ydejaparaelfinallamultiplicacin(cuandonormalmente,sinoestuvieranlosparntesis,loprimeroqueresolveraesestaltimaoperacin).
Recommended