TEMA 2: Conceptos de los LP

2.0	Introducción a la especificación de Lenguajes

• El estudio de los LP puede hacerse desde 2 puntos de vista:

• Sintáctico.

• Semántico.

• Sintaxis : líneas de programa, estructura del mismo, etc.

• Semántica : significado de esas estructuras, explica lo que podemos hacer con ese lenguaje.

Ej:

Sentencia condicional en lenguaje C

If (<expresión>) <sentencia>

• Se habla de semántica dirigida por la sintaxis (la semántica de una expresión se define a partir de la sintaxis de esa misma expresión)

• La descripción de la sintaxis es más difícil que la descripción de la semántica.

2.1	Especificación de la sintaxis

Estructura léxica :

• Todos los lenguajes no son más que conjuntos de cadenas de caracteres (cadenas de caracteres, sentencias o frases) que pertenecen al alfabeto.

• Reglas : Especifican que cadenas que se pueden hacer con el alfabeto pertenecen al lenguaje o no.

• Las unidades sintácticas más pequeñas son los lexemas que no aparecen en muchas de las descripciones de los lenguajes de alto nivel. Los lexemas abarcan a los:

• Identificadores

• Constantes

• Operadores

• Palabras claves o especiales del lenguaje.

• Relacionado con lexema tenemos el concepto de TOKEN (categoría de lexema). El lexema es un atributo del Token.

Ej:

Un Token típico de un LP es el “identificador”, es una categoría de lexema en tanto que un identificador puede ser : precio, nombre_cliente, ...

• Categorías sobre los lexemas, a cada uno le damos un nombre y eso sería un Token.

No siempre un Token se asocia a varios lexemas. Ej: Símbolo menor_igual {  }

Ej:

Frase o sentencia en lenguaje C

Indice = 2 * contador + 17;

Lexema Token

Indice identificador

= símbolo igual

2 constante_entera

* operador_producto

contador identificador

+ operador_suma

• constante_entera

• Los Tokens de un lenguaje pueden definirse mediante expresiones regulares.

+ : al menos una repetición

* : puede no haber ninguna repetición.

Ej:

Token Expresión Regular

Identificador letra(letra |'_'| dígito)*

Numero_sin_signo digito+ | dígito* `.' digito+

Separador (` ` | TAB | CR (retorno de carro))+

Letra = (`A' .. `Z') v (`a' .. `z')

Digito = `0' .. `9'

2.1.2. Gramáticas:

• La sintaxis de un lenguaje especifica como se construyen los programas en dicho lenguaje.

• La sintaxis: es el conjunto de reglas y criterios de escritura que permite la formación de programas correctos en un lenguaje, considerando solo el punto de vista de la representación.

• El primer lenguaje para el que se definió sintaxis fue Algol. El lenguaje era BNF (Bac Kus-Naur), lenguaje que permite definir nuevos lenguajes y al que se le llama metalenguaje. Se dice que este metalenguaje es equivalente a las gramáticas in-contextuales (libres de contexto) de N.Chomsky (conjunto de reglas que permiten comprobar que una sentencia pertenece a un lenguaje atendiendo a la representación.

• Se definió como (Σn, Σt , S, P)

• Σn : conjunto de símbolos no terminales de la gramática (no pertenecen al lenguaje que se está definiendo pero definen categorías sintácticas en el lenguaje)

• Σt : conjunto de símbolos terminales (símbolos que se corresponden con los tokens del lenguaje)

• S : Simbolo inicial

• P : conjunto de reglas de producción (cadenas de terminales y no terminales)

(x,y) x ∈ Σn , y∈ (Σn ∪ Σt)*

x y x::=y

x se define independientemente del contexto en que se encuentra

Ej: de una gramática para un lenguaje pequeño (ver fotocopia)

<programa> begin <lista_sentencias> end

<lista_sentencias>

...

• Estas gramáticas pueden usarse de 2 formas:

Como generadoras de programas válidos.

<programa> begin <lista_sentencias> end

El nº de programas válidos que se pueden generar con la gramática son infinitos.

Reducción de un programa válido hasta el símbolo inicial (antes de izquierda a derecha, ahora de derecha a izquierda) (ver dibujo del arbol sintáctico)

• Generador de analizadores léxicos más conocidos es Yace(ATT) herramienta para la construcción de compiladores, muy utiles. Estos analizadores sintáticos tambien se llaman PARSERS.

2.1.3 Gramáticas ambígüas :

• Si existe alguna sentencia que admite 2 arboles sintáticos diferentes, por ejemplo gramatica para la generación de expresiones aritméticas (ver que ocurre con la expresión : a*b+c) (ver fotocopias)

• Vamos a estar interesados en gramáticas no ambiguas, dabido a que di no fuera así el compilador no sabría que gramática generar.

• La semántica se ve influida por el hecho de que la gramática sea ambígua. El hecho de que un operador se genere mas abajo en el árbol sintáctico, implica que tiene más precedencia; por tanto podemos usar la gramática para asignar más precedencia.

Arbol 1 : * más precedencia que +

Arbol 2 : + más precedencia que *

Ej.

Gramáticas Ambiguas II ⇒ <op_ad> tiene más precedencia que <op_mult>

• Asociatividad. Que deben interpretar los analizadores sintácticos cuando se encuentran con expresiones como:

a * b / c * d

a + b + c - d

Ej.

Gramáticas Ambiguas II ⇒ tiene Asociatividad por la izquierda. Para reducir un término, primero reduce el término de la izquierda.

• Se dice que tiene asociatividad por la izquierda si<termino> <termino><op_multi><factor>. La recursividad por la izquierda determina asociatividad por la izquierda.

• Para indicar asociatividad por la derecha aplicamos recursividad por la derecha.

Ej.

<factor> <id> * <factor>

<id> a | b | c

a * * ( b * * c )

<id> <id>

<id> <factor>

<factor>

<factor>

Ejemplo de Ambigüedad: Gramática.

<sentencia> <condición>

| <otras>

<condición> if <expr> then <sentencia>

| if <expr> then <sentencia>

else <sentencia>

Si analizamos la siguiente frase:

If <expr> then if <expr> then <sentencia> else <sentencia>

Tenemos 2 árboles sintácticos diferentes (ver fotocopias). Tenemos una gramática ambigua.

Solución:

<sentencia> <condición>

| <otras>

<condicion> <cond_simple>

| <cond_simple> else <sentencia>

<cond_simple> if <expr> then <sentencia>

Esta es una Gramática NO AMBIGUA.

2.1.4. BNF extendido y grafos sintáctico

• Extensiones del BNF:

• Utilización de corchetes [ ] para indicar opcionalidad en la parte derecha de la regla. Ej.

<valor> [<signo>]<num_sin_signo>[ .<num_sin_signo>]

• Utilización de llaves para indicar repetición en la parte derecha de la regla.

Ej.

<numero_sin_signo> <dígito>{<dígito>} se repite 0 o más veces

• { }+ ⇒ repite 1 o más veces, aparece por lo menos una vez

Ej.

<numero_sin_signo> {<dígito>}+

• Utilización de | para indicar alternación : <signo> + | -

Ej.

<sentencia_for> for <var> ::= <expr> (to|downto) <expr> do <sentencia>

• Grafos Sintácticos: Se usan para representar la sintaxis del lenguaje. Llamados grafos, diagramas o dibujos sintácticos. Son Grafos dirigidos. Ver fotocopias VI.5.

2.2	Especificación de la semántica

• Razones para la especificación de la semántica:

• los programadores necesitan saber que es lo que hace cada sentencia. Esto se consigue leyendo el lenguaje natural asociado a la sentencia en cualquier manual. Pero las descripciones en LN son imprecisas, pueden existir distintas interpretaciones , se necesita una herramienta para especificar la semántica.

• Asociado a esto, está: “La demostración de la corrección de programas”. La especificación formal de un programa está asociada a la demostración de la corrección.

• Los desolladores deberían tener una herramienta que les ayude a especificar la semántica, igual que tienen para la especificación de la sintaxis.

• No hay ningún método universalmente aceptado para la especificación de la semántica. Veremos varios.

• Semántica Operacional.

El significado de un programa se describe mediante la ejecución de sus sentencias sobre una máquina. Tengo que traducir el lenguaje fuente del que quiero especificar la semántica, a un lenguaje de bajo nivel, típicamente al lenguaje máquina. Como esto es muy complejo, en vez de traducir a un lenguaje máquina, lo que se hace es traducir a un lenguaje de una máquina abstracta ( es un lenguaje máquina en el que se eliminan los detalles particulares de la maquina)

Ej.

Sentencias del C

For (expr1; expr2; expr3) { ... }

Con semántica operacional:

Expr1;

Bucle : if expr2=0 goto salir

Expr3;

Goto bucle;

Salir: ...

• Semántica Axiomática.

Se utiliza para demostrar la corrección de los programas, para demostrar que un programa hace los que dice la especificación. Cada sentencia del programa está precedida y seguida por una expresión lógica que especifica restricciones sobre el contenido de las variables del programa, antes y después de la ejecución de la sentencia.

Utilizaremos la Lógica de Predicados. Un predicado es una relación entre objetos a la que siempre es posible asignar uno de los valores del conjunto {Falso,Verdadero} en función de los objetos involucrados.

Ej. “” Lógica de Predicados””

{P}

sentencia

{Q}

• Estas inst. lógicas o predicados se llaman Precondición y Postcondición respectivamente. El predicado P se denomina Precondición y caracteriza el estado inicial para el que está garantizado que el programa funciona correctamente, mientras que el Predicado Q se denomina Postcondición y caracteriza la relación entre el estado inicial, supuesto este válido, y el estado final alcanzado por el algoritmo. Relacionado con el concepto de Precondición está : Weakest Precondition (precondición menos restrictiva que garantiza la validez de la postcondición).

Ej.

S : num ::= 2 * x + 1

{ num > 1 } ⇒ wp(S, {num>1} ) = { x > 0 }

otras precondiciones válidas son {x > 10} {x>25} ...

• Para la demostración de corrección del programa se usa la wp. A partir de la postcondición del programa y la última sentencia calculamos la precondición de la última sentencia que será la postcondición de la anterior [penúltima], y se sigue el proceso hasta obtener la precondición menos restrictiva wp del programa, tal que después de la ejecución de P se obtiene Q.

Las precondiciones que se van obteniendo siempre son las menos restrictivas wp.

Ej.

Wp {P} Programa p

- - -

{P2}

- - -

{P1}

- - -

{Q}

• Calcular la precondición menos restrictiva a partir de cualquier sentencia se puede hacer con un:

• Axioma : predicado lógico que suponemos cierto.

• Regla de inferencia: método de inferir predicados ciertos a partir de otros también ciertos.

• Bases Axiomáticas: Se pretende establecer un mecanismo para poder razonar sobre la corrección de diferentes algoritmos, para lo cual es necesario, además de un lenguaje apropiado, disponer de una serie de reglas de inferencia, así como un conjunto de reglas que expliquen el funcionamiento de las estructuras básicas de control de un algoritmo:

{P}

x :: = E sentencia de asignación

{Q}

Mediante el axioma P = Q xE ⇒ P es igual a Q, donde las ocurrencias de x se substituyen por E. Esto no está garantizado si la variable E provoca efectos laterales.

{P} = {Q x E }

x :: = E

{Q}

Ej.

P = { y >14 }

X : = 2 * y - 3

Q = { x > 25 }

{P} = {2y - 3 > 25} = { y>14 } precondición menos restrictiva. Wp.

¿Qué ocurriría si: P = { y > 20 }

si { y > 20 } ⇒ { y > 14 }, esto sería una regla de inferencia que se llama Regla de concurrencia

• Mediante las reglas de Inferencia

s1 , s2 , ... , sn

S ⇒ que si s1 , s2 , ... , sn son ciertos entonces S también es cierto.

Regla de la consecuencia: Si {P} S {Q} ,, P'⇒P y Q'⇒Q

{P'} S {Q'}

Ej.

{y>14} x::=2*y-3 {x>25} ,, {y>20} ⇒ {y>14} ,, {x>25} ⇒ {x>25}

{y>20} x::=2*y-3 {x>25}

también podemos substituir la postcondición:

Ej.

{y>14} x::=2*y-3 {x>25} ,, {y>20} ⇒ {y>14} ,, {x>25} ⇒ {x>0}

{y>20} x::=2*y-3 {x>0}

substituyo la postcondición por otra menos restrictiva.

Para la SECUENCIA O COMPOSICIÓN SECUENCIAL DE SENTENCIAS:

Sea {P1}

S1

{P2}

S2

{P3}

• Regla de Inferencia para aplicar a la composición secuencial de sentencias:

Si {P1}S1{P2} ,, {P2}S2{P3}

Entonces {P1} S1 ; S2 {P3}

Ej.

Y::=3*x+1; {P1} ¿cuál es la precondición bajo la cual se verifica Q?

X::=y + 3 ; {P2}

Q = {x<10}

1- {P2}={y+3<10} = {y<7} (sustituimos x por y +3)

2- {P1}={3x+1<7} = {x<2} (sustituimos y por 3x + 1)

Ej.

Sobre un programa que intercambia el contenido de 2 variables:

{P1} = { x = X e y = Y }

t := x;

{P2} = { y = Y y t = X }

x:=y;

{P3} = { x = Y y t = X }

y:=t;

{x = Y e y = X } las variables intercambiaron el valor de sus contenidos.

Tenemos que comprobar que P1 = {x = X e y = Y }:

1- Calculamos { P3 }

{P3} = {x = Y y t = X}

2- Calculamos {P2}

{P2} = {y = Y y t = X}

3- Calculamos {P1}

{P1} = {y = Y y x = X}

• La semántica axiomática no se utiliza para definir la semántica de los lenguajes porque haría falta definir una o más reglas de inferencia para cada sentencia del lenguaje (while, case, etc...) . La semantica axiomática se utiliza en la demostración de la corrección de programas.

• Semántica Denotacional.

Es el mas riguroso, se basa en la teoría matemática de funciones recursivas. Para cada entidad del lenguaje define:

• Un objeto matemático.

• Una función matemática que aplica instancias de dicha entidad del lenguaje a instancias del objeto matemático. (Esto es lo complicado del método).

• Se define una función matemática para cada regla de producción de la sintaxis.

Ej:

Vamos a definir una semántica denotacional para la gramática para la construcción de nºs binarios:

<num_binario> -> 0

| 1

| <num_binario>0

| <num_binario>1

Construcción del árbol para 110:

<num_binario>

<num_binario> 0

<num_binario> 1

1

Objeto: nº entero no negativo.

Función: Mbin (a las estructuras de este lenguaje (producciones) les va a asignar un nº entero no negativo), es una función recursiva:

Mbin(0) = 0

Mbin(1) = 1

Mbin(<num_binario>0) = 2 * Mbin(<num_binario>)

Mbin(<num_binario>1) = 2 * Mbin(<num_binario>) + 1

¿Como se aplica esta definición al ejemplo?

(6) <num_binario>

(3) <num_binario> 0

(1) <num_binario> 1

1

Se definen pares de valores (<i,v>,...) que definen el estado del computador en cada instante.

• Este es un ejemplo de la semántica guiada por la sintaxis => el significado de una expresión se define atendiendo a su estructura sintáctica. Para un lenguaje de programación va a ser la función que defina el significado de la sentencia de asignación, etc

2.3	Procesadores de Lenguajes

• Formas de ejecutar los programas fuentes en un computador. Podemos hacerlo a través de un compilador o a través de un intérprete.

2.3.1.- Compiladores e intérpretes.

• Intérprete: Programa especial que lee, analiza y ejecuta una a una las sentencias de un programa escrito en un determinado lenguaje.

Ej: Hugs(Haskell).

Como el intérprete siempre tiene a mano el programa fuente, si se produce un error en la ejecución, el intérprete puede decir que sentencias del programa fuente son las causantes del error.

• Compiladores: Se dispone de un programa especial: el compilador que lee y analiza las instrucciones del programa fuente y genera un programa objeto en lenguaje maquina que es equivalente al programa fuente en un lenguaje de alto nivel.

C -> printf, ... (sustituye por una refenrencia externa)

Pascal -> Write,...

• Lo que hace es producir referencias externas que resuelve el linkador (busca en el programa objeto esas referencias externas y localiza el trozo de código correspondiente).

• Ventaja: Se puede repetir el paso de ejecución tantas veces como quiera sin tener que hacer de cada vez el análisis del código fuente.(transparencia).

• Como resultado de esto: un programa compilado puede ser miles de veces + rápido que uno interpretado. Si se produce un error en tiempo de ejecución, la estructura de este programa ejecutable no tiene nada que ver con la estructura del programa fuente, por lo que los errores no sabemos exactamente donde se producen => ventaja del interprete.

• Ventaja: El programa fuente puede dividirse en módulos mas manejables y trabajar con ellos por separado.

2.3.2.- INTRODUCCIÓN AL PROCESO DE COMPILACIÓN.

• Para diseñar un compilador, lo que se hace es dividirlo en fases (conceptualmente) que transforman una estructura de entrada en otra de salida. Luego se agrupan esas fases y no se generan de forma explícita todas las fases intermedias.

• Administrador de la tabla de símbolos: Una de las tareas fundamentales del compilador es registrar cada identificador y sus propiedades (información sobre las características de cada uno de los identificadores además de los identificadores en sí). La tabla de símbolos es una estructura que permite tanto registrar como almacenar, consultar información. Se va a añadir mas información a la tabla de símbolos y se va a consultar información de la tabla de símbolos a lo largo de las fases siguientes.

• Detección de errores: En cada fase se pueden encontrar errores o situaciones que conviene que se notifiquen al usuario. El compilador ha de ser capaz de enfrentarse a ese error prosiguiendo con la compilación (el análisis), no parándose en el error. Existen varios tipos de errores:

• En el análisis léxico : Un lexema incorrecto. Ej: 7Z

• En el análisis sintáctico (secuencias incorrectas de lexemas correctos): x:=procedure a;

• En el análisis semántico (incompatibilidades de tipo, identificadores no declarados, errores en lista de parámetros).

• Durante la optimización. Si hay variables que has declarado pero que no utilizas o si hay trozos de código inaccesibles.

• Durante la generación de código. Declaración de un array demasiado grande.

• Análisis Léxico: Se transforma el programa fuente (cadena de caracteres) en una secuencia de tokens (lexemas). También se añaden los identificadores que encuentra en la tabla de símbolos. El análisis léxico simplifica la entrada.

• Análisis sintáctico: Utiliza la gramática incontextual que define el lenguaje, junto con la secuencia de tokens de entrada y genera el árbol sintáctico.

• Análisis semántico: Realiza un estudio de los que se llaman características contextuales del lenguaje. Estos aspectos contextuales son:

• Comprobación de tipos.

• Comprobación de flujo de control. Ej: C -> Break

• Comprobaciones de unicidad. Ej: que los identificadores se declaren una sola vez,... (ej. Pascal -> Case con etiquetas iguales).

• Comprobaciones relacionadas con nombres.

Ej: ADA -> Program A

... {Comprueba si coincide este nombre}

End A

Esta es la fase en la que se completa la información de la tabla de símbolos y donde se comienza a usar esa información.

• Generación de Código Intermedio: Muy relacionada con la semántica operacional. Se define un código (código intermedio para una máquina abstracta) correspondiente a una máquina imaginaria. Es un código fácil de generar a partir de las instrucciones del lenguaje fuente. Debe ser fácil también el paso de código intermedio a código objeto.

Ej. de código intermedio: código de 3 direcciones (como máximo 3 operandos)

A partir de un árbol sintáctico con información semántica, genera código intermedio.

• Optimización: Genera un código intermedio a partir de otro código intermedio donde:

• Elimina redundancias.

• Calcula subexpresiones que son constantes.

• Generación de código: A partir de aquí hará falta saber que máquina se esta usando. Habrá que estudiar las características de la maquina. Se genera código ensamblador.

2.4	Características de diseño de los lenguajes

Objetivos que vamos a marcar:

• Utilidad.

¿Va a ser útil la característica que vamos a añadir?

¿Va a haber otras características que hagan lo mismo?

• Conveniencia.

¿Evitamos que el programador escriba demasiado?

¿Se elimina confusión en el código?

• Eficiencia.

¿Es fácil o difícil de implementar?

¿Mejora o degrada el rendimiento del lenguaje?

¿Se puede traducir a un código eficiente?

• Potabilidad.

Si la característica puede introducirse en cualquier maquina.

• Legibilidad.

Añadiendo esta característica ¿Son mas legibles los programas?

• Ortogonalidad.(Independencia)

Si esta característica que vamos a añadir se combina de forma coherente con el resto de los conceptos o si provoca una excepción.

• Simplicidad.

¿Esta el lenguaje diseñado como un todo simple y general o esta repleto de características de propósito específico?

Hay características que son incompatibles.

Ej: ADA no es simple y esta lleno de excepciones, es difícil de aprender.

Tema 2: Conceptos de losLP LPR

1

12