Gygyg

SEMANTICA Y SUS DOCUMENTOS.TRABAJO II.21/02/2011Lenguajes de Programación
Qwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyui

opasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfgh

jklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvb

nmqwertyuiopasdfghj

Semántica
Estilos de definición semántica
* Operacional
* Axiomática
* Declarativa
*Algebraica
* Teoría de Modelos
* Punto fijo
* Denotacional

Semántica operacional

* 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 el significado de cada construcción se expresa en términos de las acciones a realizar por la máquina
* la forma más simple de definirla es proporcionar unintérprete para el
Lenguaje L sobre la máquina M cuyas componentes se describen de modo matemático
* La Definición semántica operacional de un lenguaje lo hace ejecutable proporciona un modelo para la implementación
* Ejemplo: Structural Operacional Semantics (SOS) (o sistemas de transición de Plotkin)
* Se de finen reglas de transición que especifican los pasos de computación para unaConstrucción compuesta A op B en términos de la semántica de las componentes
* las reglas se suelen escribir en el estilo de los sistemas de deducción natural



* Dado que las construcciones en general modifican una cierta noción de estado, las reglas de transición se suelen definir sobre configuraciones del tipo<Instrucción, Estado>
* las reglas de transición tienen entonces la forma:
Indicando que una configuración en otra, cuando se satisface 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).

Formalmente, un ST es una 4-tupla (C,I,F,→),
Donde:
* C es el conjuntode las configuraciones c, que son pares de la forma <i,e>
* I ⊆ C es el conjunto de las configuraciones iniciales
* F ⊆ C es el conjunto de las configuraciones finales
* → ⊆ 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 de configuraciones c1 c2
... cn tal que:
* c1 ∈ I
* cn ∈ F* ci → ci+1, para cada i en [0..n]

Un ST se llama determinista si para cada c ∈ C existe como mucho un c’ tal que c → c’

La relación de transición → se define recursivamente como la mínima relación que satisface que:
Si c1 → c’1, …. cn → c’n
entonces
op(c1,…, cn) → op(c’1,…, c’n)

Semántica axiomática
Enfoque típico de los trabajos sobre verificación formal de programas
(Con esteestilo se definió la semántica de Pascal)
El significado de cada construcción i del lenguaje se expresa en términos de una transformación que establece qué se puede afirmar sobre el estado de la máquina tras la ejecución de i en términos de lo que era cierto antes o viceversa, qué debe cumplirse antes para llegar al estado que se quiere obtener tras la ejecución.

En general se definerepresentando los estados mediante predicados (en vez de como funciones) y asociando a cada instrucción i del lenguaje un transformador 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, y dada una instrucción i del lenguaje considerado, el transformador de predicados
pmd: Instrucciones xLógicaPred. -> LógicaPred

Proporciona el “predicado más debil” pmd(i, p) que expresa lo que debe cumplirse en el estado anterior a la ejecución de i para que, después de dicha ejecución, se haya alcanzado el estado p

Por ejemplo, si i es una instruccion de asignación del tipo:
”X:=e“ definimos:
pcm(”X:=e“,p) = p[e → X]

donde p[e→ X] es el predicado que resulta de “deshacer el...