Tema 2:Descripción Formal de los Lenguajesde Programación
Lenguajes y Paradigmas de Programación
Descripción formal de un LPSintaxis: qué secuencia de caracteres constituyenun programa “legal”
elementos sintácticos del lenguajemodelos de ejecución
Semántica: qué significa (qué calcula) unprograma legal dado
Además de ayudar al programador a “razonar” sobre elprograma, es necesaria para implementar correctamente ellenguaje, y sirve para desarrollar técnicas y herramientas de:
Análisis y Optimización
Depuración
Verificación
Transformación
SintaxisLa sintaxis define “el aspecto” de un programa
qué programas son “legales” o conformes con laespecificación de un lenguaje
Distintos instrumentos:
Notación BNF - Algol
Representación gráfica (con diagramas) -Pascal
La gramática describe cómo formar instrucciones(statements) a partir de palabras (tokens)
Una instrucción = una secuencia de palabras
Una palabra = una secuencia de caracteres
Ejemplo (sintaxis de Java)
while_statement ::= ”while” ”(" expression “)” statement
Ejemplo (sintaxis de Modula-2)
<while_statement> ::= WHILE <expression> DO <statement> { ";" <statement>} END
(Analysis)
(Sinthesis)
Análisis de la sintaxis
Un analizador léxico (scanner) esun programa que divide una secuencia decaracteres (el programa) en una secuencia decomponentes sintácticos primitivoso palabras (identificadores, números,palabras reservadas, etc)Un analizador sintáctico (parser) es unprograma que reconoce una secuencia depalabras y construye una secuencia deinstrucciones(en forma de árbol sintáctico: parse tree)
Análisis léxico
Análisis sintáctico
caracteres
palabras
instrucciones
(parse tree)
ejemplo
[fun,{,Fact,N,},if,N,= =,0,then,1,else,N,*,{,Fact,N,
-,1,},endif,end ] = secuencia de palabras
fun {Fact N}
if N = = 0 then 1
else N* {Fact N-1}
endif
end = instrucción
[f,u,n,{,F,a,c,t,’ ’,N,},’\n’,’ ’,i,f,’ ’,N,=,=,0, ’ ’,
t,h,e,n,’ ’,1,’\n’,’ ’,e,l,s,e,’ ’,N,*,{,F,a, c,t,’ ’,N,
-,1,},’ ’,e,n,d,i,f,’\n’,e,n,d] = secuencia de caracteres
i f
= 1
*
N 0 N call
F act -
N 1
fun
Fact N
Parse tree
(Analysis)
Semántica (1)Concepto y necesidad de las descripciones semánticas
Semántica “estática” del lenguaje: las restricciones de sintaxis que no sepueden expresar en BNF pero sí comprobar en tiempo de compilación
Ejemplo: A := B + Cpodría no ser legal si A, B o C no han sido declaradas previamente
Estas restricciones se comprueban en la fase de análisis semánticolas demás restricciones, que sólo se pueden comprobar durante la ejecución del
programa y no en fase de compilación.constituyen la semántica dinámica(e.g. comprobación de índices dentro del rango del vector)
Comprobaciones que lleva a cabo el análisis semánticoDeclaración de variables previa a su uso
• Compatibilidad y conversión de tipos (coercion)• Signatura de las funciones (coincidencia del número de parámetros
en una llamada con los parámetros formales)
(Sinthesis)
Semántica (2)
¿Por qué no es suficiente considerar sólo la semántica estática, es decir,por qué no es posible que el compilador detecte todos los errores posibles?:
Algunos errores sólo se manifiestan durante la ejecución:
Z=X/Y error si se ejecuta con un valor de Y = 0Z=V[Y] error si Y tiene un valor que cae fuera del rango del vector V
De hecho, muchas propiedades interesantes de un programa no son decidibles.Por ejemplo , no se puede decidir:
1. la terminación (semidecidible… basta ejecutar el programa para “semi-decidirlo”)2. si dos programas cualesquiera computan la misma función3. si dos descripciones BNF generan el mismo lenguaje
Porqué la semántica no es siempre “estática”?
Semántica (3)Estilos de definición semántica
Operacional
Axiomática
Declarativa
Denotacional
Algebraica
Teoría de Modelos
Punto fijo
Semántica operacional (i)es el enfoque más antiguo(con este estilo se definió la semántica de ALGOL’60)
primero se define una máquina abstracta M, y elsignificado de cada construcción se expresa entérminos de las acciones a realizar por la máquina
la forma má simple de definirla es proporcionar un intérpretepara el lenguaje L sobre la máquina M cuyas componentes sedescriben de modo matemático
la definición semántica operacional de un lenguajelo hace ejecutable
proporciona un modelo para la implementación
Semántica operacional (ii)Ejemplo: Structural Operacional Semantics (SOS) (o sistemas de transición de Plotkin)
se de finen reglas de transición que especifican lospasos de computación para una construccióncompuesta A op B en términos de la semántica de lascomponentes
las reglas se suelen escribir en el estilo de lossistemas de deducción natural
_ premisa _conclusión
Semántica operacional (iii)Dado que las construcciones en general modifican una ciertanoción de estado, las reglas de transición se suelen definir sobreconfiguraciones del tipo
<Instrucción, Estado>
las reglas de transición tienen entonces la forma:____premisa____ <i,e> <i’,e’>
indicando que de una configuración se pasa a otra, cuando sesatisface cierta premisa
el conjunto de estas reglas define una relación de transición(que llamaremos ) sobre el conjunto de las configuraciones(un grafo de transiciones)
Semántica operacional (iv)Formalmente, un ST es una 4-tupla (C,I,F, ), donde
o C es el conjunto de las configuraciones c, que son paresde la forma <i,e>
o I C es el conjunto de las configuraciones inicialeso F C es el conjunto de las configuraciones finaleso C x C es la relación de transición
(escribiremos c c’ para indicar que el par (c,c’)
Una secuencia de ejecución es una secuencia deconfiguraciones c1 c2 ... cn tal que
c1 Icn Fci ci+1, para cada i en [1..n[
Un ST se llama determinista si para cada c C existe comomucho un c’ tal que c c’
Semántica operacional (v)
La relación de transición se define recursivamentecomo la mínima relación que satisface que:
Si c1 c’1, …. cn c’n
entonces
op(c1,…, cn) op(c’1,…, c’n)
Ejemplo:SOS de un minilenguaje imperativoExpresiones aritméticas, booleanas e instrucciones
NOTA: estas reglas son semánticas, no están en BNF!
Arit-expr:
a ::= n | X |a0+a1 | a0-a1 | a0*a1
Bool-expr:b ::= true | false | a0=a1 | a0 a1 | ¬b | b0 b1
Command:
i ::= skip | X:=a | i0;i1 | if b then i0 else i1 |while bdo i
Semántica de las expresiones aritméticas:
Evaluación de constantes <n,e> nEvaluación de variables
<X,e> e(X)asumir que el estado está representado como una funcióne= {X1 n1…Xk nk} que asigna a cada variable Xi su valorni en dicho estado (o error si Xi no está inicializada)Evaluación de sumas
<a0,e> n0 <a1,e> n1
< a0 + a1, e> n0 + n1
Evaluación de restas y productos.... similar
ejemplo
Semántica de las expresiones booleanas:Evaluación de las constantes
< true, e> true
< false, e> false
Evaluación de la igualdad
<a0,e> n0 <a1,e> n1 si n0 y n1 son iguales
< a0 = a1, e> true
<a0,e> n0 <a1,e> n1 si n0 y n1 son distintos
< a0 = a1, e> false
ejemplo
Semántica de las expresiones booleanas:Evaluación de la comparación
<a0,e> n0 <a1,e> n1 n0 es menor o igual que n1< a0 a1, e> true
<a0,e> n0 <a1,e> n1 n0 no es menor o igual que n1< a0 a1, e> false
Evaluación de la negación
<b,e> true <b,e> false < ¬ b,e> false < ¬ b,e> true
ejercicio: disyunción
ejemplo
Semántica de las instrucciones:NOTACIÓN:Escribimos <i,e> e’ para representar <(i;{}),e> <{}, e’>
Evaluación de las instrucciones simples< skip, e> e
<a,e> n
< X:=a , e> ({X n} ° e)
Evaluación del condicional<b,e> true ^ < i0,e> e’
< if b then i0 else i1 , e> e’
<b,e> false ^ < i1,e> e’
< if b then i0 else i1 , e> e’
ejemplo
Semántica de las instrucciones: (Big-step)Evaluación de la iteración
<b,e> false
< while b do i, e> e
<b,e> true ^ < i,e> e’’ ^ < while b do i, e’’> e’< while b do i, e> e’
Evaluación de la secuencia< i0,e> e’’ ^ < i1,e’’> e’
< i0; i1, e> e’
ejemplo
Escritura alternativa: (Small-step)Evaluación de la iteración
<b,e> false
< while b do i, e> e
<b,e> true < i,e> e’’< while b do i, e> < while b do i, e’’>
Evaluación de la secuencia< i0,e> e’’
< i0; i1, e> < i1,e’’>
ejemplo
Ejercicio
¿Cómo usar esta semántica?
Calcular la semántica de:
P={X:=4; while X 2 do X:=X-1}
Si <P,{}> * ef
entonces S(P) = ef
Semántica axiomática (i)Enfoque típico de los trabajos sobre verificación fomalde programas (este tipo de semántica lo ideó Hoarecomo herramienta para probar la corrección de programas)
(con este estilo se definió la semántica de Pascal)
Dado P y dos asertos Q y R, se dice que P es correcto w.r.t.Q y R si “toda ejecución de P que comience en un estado que satisface Q,termina en un estado que cumple R”
El trío {Q} P {R} se denomina “tupla de Hoare”. Usando elsistema de Hoare, la demostración de la corrección se haceusando reglas similares a las de la semántica operacional.
El significado de cada construcción i del lenguaje se expresa en términos de unatransformación que establece qué se puede afirmar sobre el estado de la máquina tras laejecución de i en términos de lo que era cierto antes
Por ejemplo:
{Q} skip {Q}
{Q[e]} x:=e {Q[x]}
Para mecanizar las demostraciones, se ideó un sistema equivalente cuyas reglasexpresan qué debe cumplirse antes de la ejecución de i para llegar al estado que setiene tras la ejecución
Semántica axiomática (ii)
En general se define representando los estados mediante predicados (envez de como funciones) y asociando a cada instrucción i del lenguaje untransformador de predicados (o transformador de estados) que funciona en“sentido inverso” al programa
es decir, a partir del estado “de llegada”, representado por el predicado p, ydada una instrucción i del lenguaje considerado,el transformador de predicados
pmd: Instrucciones x LógicaPred. -> LógicaPred
proporciona el “predicado más debil” pmd(i, p) que expresa lo que debecumplirse en el estado anterior a la ejecución de i para que, después dedicha ejecución, se haya alcanzado el estado p
Semántica axiomática (iii)
- si i es una instruccion de asignación del tipo ”X:=e“definimos:
pmd(”X:=e“,p) = p[X e]
donde p[X e] es el predicado que resulta de “deshacer el efecto”de haber sustituido X por e en p.
- si i es una instruccion condicional “if b then x else y”:
-http://www.dsic.upv.es/~alpuente/pmd.html
Semántica axiomática (iv)
Semántica axiomática (v)
¿Cómo usar esta semántica?
Dado P y dos asertos Q y R, se dice que P es correcto w.r.t.Q y R si “toda ejecución de P que comience en un estado que satisfaceQ, termina en un estado que cumple R”
es decir, si pmd(P,R)=Q’ y Q Q’
Semántica axiomática (vi)
Ejemplo: Este programa {P}={X=1}
X:=X-1{Q}={X 0}
¿es corrrecto con respecto a {P} y {Q}?
pmd(X:=X-1, {X 0})= {X-1 0}={X 1}
En este caso el programa es correcto con respecto a la precondición{P} ya que {P} implica a la precondición más débil
{X=1} {X 1}
Semántica declarativa (i)el significado de cada construcción se define en términos
de elementos y estructuras de un dominio matemáticoconocido.
este enfoque ha dado lugar a diferentes aproximaciones:
TEORÍA MATEMÁTICA ESTILO SEMÁNTICO
1. Tª Dominios -> DENOTACIONAL2. Tª Modelos Lógica -> Tª DE MODELOS3. Tª Categorías -> ALGEBRAICA4. Tª Funciones Recursivas -> PUNTO FIJO
Semántica declarativa (ii)1. Semántica DENOTACIONAL SDEN
Con este estilo se da la semántica de lenguajes funcionalese imperativos, como ML y ADA
Técnicamente, es la más compleja, pero también muy rica; permite darcuenta de computaciones que no terminan, orden superior …Se requiere definir:
los dominios sintácticos (construcciones sintác. correctas)
los dominios semánticos (valores asociados a cada const. sintác. correcta)
las funciones de evaluación semántica(de los dominios sintácticos a los semánticos)las ecuaciones semánticas
Operadores estándar sobre dominios + ( ), , Con este estilo, el significado de un programa es la función que establece larelación entre la entrada y la salida, esto es, entre los datos y los resultados.
ejemplo:SDEN de un minilenguaje imperativo
<programa> ::= PROGRAM READ <id>;BEGIN <instruccion>END;
WRITE <expresion> END
<instruccion> ::= <id> := <expresion> |<instruccion>; <instruccion> |
WHILE <expresion> DO <instruccion> END
<expresion> ::= <id> | <cte> | (<expresion>) | <expresion> <op> <expresion>
<id> ::= ……<cte> ::= ……..<op> ::= ……..
dominios sintácticos: (conjuntos)
Id (identificadores) - predefinidoCte (Constantes) - idem
Op (Operadores) - idem
Exp (Expresiones) - definido como:Exp= Id + Cte + (Exp x Op x Exp)
Inst (Instrucciones) - definido como:Inst= (Id x Exp) + (Inst x Inst) + (Exp x Inst)
Prog (Programas)Prog = Id x Inst x Exp
ejemplo
dominios semánticos: (funciones)E (Estados)V (Valores) - predefinido
Sop (Dominio semántico asociado a los operadores)Sexp (Dominio semántico asociado a las expresiones)Sinst (Dominio semántico asociado a las instrucciones)Sprog (Dominio semántico asociado a los Programas)
con las siguientes definiciones: (como funciones)E = Id V
Sop = V x V VSexp = E VSinst = E ESprog = V V
ejemplo
valuaciones :
Vconst: Const V - predefinida Vop: Op Sop - predefinida
Vexp: Exp Sexp Vins: Inst Sinst Vprog: Prog Sprog
ecuaciones semánticas
Para la instrucción compuesta:
Vinst[i1;i2](e) = Vinst[i2] (Vinst[i1] (e))
Para la asignación “x:=e”:
www.dsic.upv.es/~alpuente/asigDen.html
ejemplo
Semántica declarativa (iii)2. Semántica por TEORÍA DE MODELOS STM
Con este estilo se ha definido la semántica de los lenguajeslógicos como Prolog
Intuitivamente, un programa lógico P es un conjunto defórmulas lógicas que definen relaciones
ejemplo P= par(0). par(s(s(X)) par(X).
el significado del programa lógico P dado por una semántica STMes el conjunto de átomos (sin variables) que se deducen de P:
STM(P) = {par(0),par(s(s(0))),par(s(s(s(s(0))))),….}
Semántica declarativa (iv)3. Semántica ALGEBRAICA SALG
Con este estilo se ha definido la semántica de algunos lenguajesfuncionales como OBJ
Intuitivamente, un programa funcional R es un conjunto deecuaciones que definen funciones
ejemplo R = neg(0)=1 neg(1)=0
el significado SALG(R) del programa funcional R es el resultadode agrupar (en una misma clase) todos aquellos datos(construidos con las constantes y símbolos de función delprograma) que siendo sintácticamente diferentes lasecuaciones me dicen que son iguales.
0 neg(1) neg(neg(0)) …
1
neg(0)neg(neg(1))…
Semántica declarativa (v)
SALG(R) =
Semántica declarativa (vi)4. Semántica de PUNTO FIJO SPF
Se usa para todo tipo de lenguajes (imperativo, lógico, funcional, etc)
Se utiliza como enlace para demostrar la equivalencia entre diferentescaracterizaciones de un mismo lenguaje.
Intuitivamente, se asocia al programa P una transformación(generalmente una función continua) TP definida sobreel dominio del programa
el significado del programa se define como el menor puntofijo (least fixpoint lfp) de dicha transformación lfp(TP)
Semántica declarativa (vii)La elección de la semántica depende de:* el uso que se dará a la definición semántica
ayuda a la implementación del lenguaje (e.g. OPERACIONAL)ayuda al programadordiseño del lenguaje (e.g. PUNTO FIJO)…
* el tipo de lenguajeLOGICOFUNCIONALIMPERATIVO…
* la riqueza pretendida para las descripciones
Equivalencia de programas.Corrección y Completitud.
La semántica de un lenguaje nos permite razonar sobre la equivalencia de programasP OB P’ si y solo si SOB (P)=SOB(P’)P es completo respecto a P’ si SOB (P) SOB (P’)P es correcto respecto a P’ si SOB(P) SOB(P’)
donde OB= cualquiera de las semánticas que hemos visto
EJEMPLO: SOP(while false do Q) = SOP(skip)
En particular, si P’ es una especificación formal (presentada también como un programa,probablemente escrito en otro lenguaje, que resuelve el mismo problema que P demanera más simple aunque menos eficiente).la semántica ayuda a verificar si P es una implementación correcta y completa de laespecificación P’: es decir, si computa todo lo que debe y sólo eso.
EJEMPLO: P’=programa funcional “par”P={par(0)=true, par(s(s(X)))=true}
SALG(P) SALG(P’)de hecho, P no sería una implementació correcta ni completa de P’
Clasificación de los LPs
Lenguajes compilados
Lenguajes interpretados
- Los buenos entornos incluyen tanto intérprete (para serusado en la fase de desarrollo) como compilador (parausarse en explotación).
Compilador
programa objeto
Programa objeto
SalidaEntrada
Programa fuente
Intérprete SalidaPrograma fuente
Entrada
Traducción vs. interpretación (iii)La traducción e interpretación pura constituyen dos extremosEn la práctica no se suele usar la traducción pura exceptocuando los leguajes son de nivel muy próximo (como en elcaso de los ensambladores)La interpretación pura tampoco es muy frecuente, excepto enlenguajes de control de S.O. (scripting) o en lenguajesinteractivosEs más común una implementación mixta: el programa setraduce primero de la forma original a otra de ejecución másfácil, que se ejecuta por interpretación.
Máquina virtual SalidaEntrada
Traductor Programa intermedioPrograma fuente
Programa intermedio
Traducción vs. interpretación (iv)La implementación mixta combina las ventajas de los dosmétodos:
el compilador conduce generalmente a una mayor eficiencia (porejemplo, si se puede garantizar que X siempre estará en la posición2534, se pueden generar instrucciones máquina que acceden a esaposición cada vez que se hace una referencia a X (un intérpretebuscaría la dirección de X en una tabla cada vez que deba acceder).cuando el programa fuente tiene un grupo o bloque de instruccionesque se ejecuta de forma repetida (por ejemplo, dentro de un bucle odentro de un subprograma que se invoca 1000 veces), un compiladordecodificará dicho bloque una sola vez, y luego sólo hará falta unadecodificación más sencilla del enunciado traducido durante cada unade las 1000 repeticiones, mientras un intérprete del lenguaje fuenteharía la decodificación más compleja de forma idéntica las 1000 vecesel programa objeto traducido suele ser más grande que el fuente (tantomayor cuanto mayor sea la “distancia” entre los dos lenguajes, poreso, al haber un nivel intermedio, el tamaño del compilado es menor)
Lenguajes típicamente compilados:C, C++, Fortran, Ada
Lenguajes típicamente interpretados:LISP, ML, Smalltalk, Perl, Postscript
Lenguajes con implementación mixta (esto facilita la portabilidad a cualquier plataforma):
Pascal (P-code),Prolog (WAM-code),Java (byte-code, el código de la JVM, i.e.,el formato estándar para la distribución decódigo Java)
Traducción vs. interpretación (v)
Traducción vs. interpretación (vi)
- Un lenguaje con implementación mixta se diceinterpretado cuando el traductor de la fase inicial essimple.
- Si es complicado (análisis profundo y trasformación notrivial), se dice sin embargo que es compilado.