PDF de programación - sintaxis semantica variables 2014

1. Semántica de un lenguaje: primera aproximación

El establecer el significado de las frases de un lenguaje de programación es un problema
de múltiples aristas en tanto puede tener variados objetivos, que van desde la comprensión
humana hasta la necesidad de que una máquina los pueda interpretar o traducir a una
secuencia de instrucciones ejecutables. Del significado trata un manual de usuario, en tanto
provee una descripción intuitiva de una acción o una denotación, y también un intérprete,
un compilador, o una herramienta teórica destinada a desentrañar principios básicos de
diseño. Todas constituyen vertientes de significación que responden a distintos intereses y
usos de los lenguajes de programación.

Como una primera aproximación, podemos destacar cuatro maneras diferentes de dar
significado a los lenguajes de programación. Las primeras tres de ellas ponen énfasis en el
sentido dinámico finito, en tanto la cuarta se refiere a un significado ideal en un universo
formado por objetos matemáticos.

informal, intuitiva: explica el funcionamiento de los programas a través de frases
comprensibles en el lenguaje natural (ejemplo: manuales, documentación tipo java-
doc)
axiomática: explica el sentido dinámico de manera implícita, estableciendo en el mar-
co de una lógica qué propiedades son asignables a una determinada frase del lenguaje,
estableciendo así una manera de razonar sobre programas (ejemplo: {P/v ← e} v :=
e {P})
operacional: explica el sentido dinámico de manera explícita, diciendo de que manera
se ejecuta un programa (ejemplo: intérprete)
denotacional: asigna a cada programa un significado estático en un universo semán-
tico especialmente definido para representar los fenómenos que el lenguaje describe
(este universo podría ser el universo de las frases de otro lenguaje, por ejemplo un
compilador)

En este curso ocupa un lugar destacado el último enfoque, y en menor medida el anteúl-
timo. A partir del desarrollo de la Teoría de Dominios la semántica denotacional adquiere
un relevancia especial, no sólo por tratarse de objetos matemáticos perfectamente definidos
en el contexto de una teoría particular, sino además porque comienza a ser utilizada como
la definición del lenguaje y luego, si se proponen otras semánticas (operacional, axiomáti-
ca), se las demuestra correctas con respecto a dicha definición. La semántica operacional
también ocupará un lugar importante por ser una manera formal y la vez intuitiva de
aproximarse por primera vez al significado de un lenguaje, poniéndo énfasis en el auténtico
sentido de sus construcciones.

Para atribuir un significado denotacional al lenguaje debemos primero fijar nuestro do-
minio semántico, o sea el universo de objetos matemáticos que constituirán los significado
de las frases. Luego debemos definir una función que asigna a cada frase un significado. Al
utilizar el concepto matemático de función nos aseguramos que el significado de cada frase
será único.

1

2

Pero para el caso de los lenguajes de programación que nos interesan, tanto la defini-
ción del dominio semántico como la definición de la función semántica requieren el uso
de herramientas matemáticas no triviales. Antes de abordar el estudio de los lenguajes
propiamente dichos, vamos a abordar el estudio de estas herramientas. En las secciones
siguientes trataremos:

Herramientas para dar la sintaxis del lenguaje, es decir una determinación del con-
junto de frases que serán consideradas prográmas válidos (sección 2).
El problema de la buena definición del dominio semántico y la función semántica
(sección 3).
El manejo de variables, la ligadura y los problemas de captura (secciones 4, y 5).
Herramientas matemáticas para caracterizar los objetos definidos mediante recursión
(próximo apunte).

2. Gramáticas abstractas: la definición del lenguaje

La herramienta por excelencia para la definición de lenguajes formales es la noción de
gramática. Para nuestros propósitos la noción de gramática convencional no es del todo
adecuada, porque los lenguajes que estudiaremos sufren del problema de la ambiguedad.
Consideremos por ejemplo el siguiente lenguaje de expresiones aritméticas:

(cid:104)intexp(cid:105)

::= 0 | 1 | 2 | ...
−(cid:104)intexp(cid:105) |
(cid:104)intexp(cid:105) + (cid:104)intexp(cid:105) |
(cid:104)intexp(cid:105) ∗ (cid:104)intexp(cid:105)

Observemos ejemplos de frases generadas por esta gramática:
142
-15
-15+3
2+3+4
2*-4
La gramátíca es ambigua en el siguiente sentido: algunas frases admiten diferentes ma-

neras de generarse. Tal es el caso de 2+3+4:

(1) (cid:104)intexp(cid:105)

→ (cid:104)intexp(cid:105) + (cid:104)intexp(cid:105)
→ (cid:104)intexp(cid:105) + 4
→ (cid:104)intexp(cid:105) + (cid:104)intexp(cid:105) + 4
→ (cid:104)intexp(cid:105) + 3 + 4
→ 2 + 3 + 4

(2) (cid:104)intexp(cid:105)

→ (cid:104)intexp(cid:105) + (cid:104)intexp(cid:105)
→ 2 + (cid:104)intexp(cid:105)
→ 2 + (cid:104)intexp(cid:105) + (cid:104)intexp(cid:105)
→ 2 + 3 + (cid:104)intexp(cid:105)
→ 2 + 3 + 4

(1) se corresponde intuitivamente con asociar a izquierda, es decir (2 + 3) + 4, mientras
que (2) con asociar a derecha, es decir 2 + (3 + 4). Lo cierto es que ninguna de estas dos
frases puede generarse, porque los paréntesis no están entre los símbolos terminales de la
gramática.

Pregunta: ¿con cuáles de las otras frases mencionadas más arriba ocurre lo mismo?

3

El problema podría resolverse agregando paréntesis y desambiguando la gramática. Por

ejemplo, cambiando la gramática por la siguiente:

(cid:104)intexp(cid:105)
(cid:104)termexp(cid:105)
(cid:104)groundexp(cid:105)

::= (cid:104)intexp(cid:105) + (cid:104)termexp(cid:105)|(cid:104)termexp(cid:105)
::= (cid:104)groundexp(cid:105)| − (cid:104)termexp(cid:105)
::= 0|1|2|....|((cid:104)intexp(cid:105))

donde queda claro que el + asocia a izquierda y que el menos tiene mayor precedencia. Esta
gramática dice cómo se escriben concretamente las frases del lenguaje. Podríamos llamarla
gramática concreta, y a las frases que genera, frases concretas. Podríamos decir que
define la sintaxis concreta del lenguaje.

La gramática concreta resulta más complicada que la que dimos anteriormente. Nos
obligaría a fijar detalles de la sintaxis del lenguaje que son irrelevantes para nuestros pro-
pósitos, y que de hecho cada lenguaje de programación lo resuelve de una manera distinta,
constituyendo una molestia a la hora de concentrarse en lo sustancial del lenguaje (que
en la gramática anterior era evidente): que el mini-lenguaje tiene constantes no negativas,
un operador unario (-) y un operador binario (+). Por esta razón, se prefiere la gramática
que se dió en primer lugar, a la que llamaremos gramática abstracta, en parte porque
no expresa detalles de cómo se escriben las expresiones (asociatividades, precedencias, pa-
réntesis) sino que expresa qué construcciones tiene el lenguaje, cuál es la estructura de las
frases que hay, cuáles son las subfrases.

Pero debemos dejar sentado, justamente por el problema de ambigüedad, que la gramá-
tica no pretende describir la notación exacta o concreta, sólo la estructura de las frases,
dice cuáles son las construcciones que hay en el lenguaje. No interesa cómo se escriben las
frases sino qué frases hay. Diremos que es una gramática abstracta, que describe la sintaxis
abstracta y determina frases abstractas. Trabajar a este nivel de abstracción es muy conve-
niente ya que nos permite desentendernos de detalles propios de la notación concreta que
no tienen interés cuando se trata de dar significado a las frases.

En el ejemplo anterior, la estructura abstracta diferente se pone de manifiesto al repre-

sentar cada derivación a través de un árbol sintáctico:

(1)

(cid:104)intexp(cid:105)
(cid:46) ↓ (cid:38)

+
(cid:104)intexp(cid:105) + (cid:104)intexp(cid:105)

(cid:104)intexp(cid:105)
(cid:46) ↓ (cid:38)
↓
2

↓
3

(cid:104)intexp(cid:105)

↓
4

(cid:104)intexp(cid:105)

↓
4

(2)

(cid:104)intexp(cid:105)
(cid:46) ↓ (cid:38)

+
(cid:104)intexp(cid:105) + (cid:104)intexp(cid:105)

(cid:104)intexp(cid:105)
(cid:46) ↓ (cid:38)
↓
3

↓
2

El libro de Reynolds (a partir de ahora, “el libro”) hace un tratamiento detallado del
significado preciso de gramática abstracta. Es muy interesante y lectura recomendada para
entender esto con precisión (no es imprescindible para comprender la materia).

4

Una vez aceptado que trabajaremos con gramáticas abstractas, surge el problema de la
notación que utilizaremos en este texto (y en la clase) para referirnos a una producción
particular de tal gramática (por ejemplo la (1)). En las pocas ocasiones en que nos resulte
necesario precisar notación específica resolveremos los problemas de ambigüedad mencio-
nados estableciendo precedencias, stopping symbols, y utilizando los paréntesis que sean
necesarios. Aunque resulte reiterativo aclaramos que tales símbolos no serán parte de la
gramática en cuestión, sino sólo convenciones de notación que nos permitirán entender de
qué producción de la gramática abstracta estamos hablando.

3. Función semántica

Una vez establecido el universo de frases abstractas que constituyen un lenguaje, dar una
semántica denotacional implica definir una función que a cada frase abstracta le asigna una
denotación en un dominio determinado. Cuando hablamos de lenguajes de programación
no triviales, la definición de la función semántica presenta ciertas dificultades. Es necesario
recurrir a herramientas matemáticas más complejas no sólo para la construcción de los
dominios semánticos, sino además para la definición misma de la función. El objetivo es
garantizar ciertas propiedades tanto de la semántica como de la definición de la misma.
Aunque es difícil explicar ahora la importancia de “garantizar propiedades”, en términos
generales podemos decir que tienen que ver con

que la semántica denotacional sea una herramienta que aporte claridad conceptual,
y no que sea un instrumento de traducir algo poco comprensible en otra cosa incom-
prensible,
que la semántica denotacional sea un referente co