Upload
juan-pez
View
79
Download
0
Embed Size (px)
Citation preview
18/03/13
1
Adapted from C. Varela, S. Haridi and P. Van Roy
1
Modelo Computacional Secuencial y Declarativo
Sintaxis del Lenguaje de Kernel Almacenamiento de simple asignación
Descripción
• Definiremos un lenguaje de programación
• Qué hace falta para definir un lenguaje de programación:
Cómo se escribe con este lenguaje?
Qué significan las cosas que escribimos con este lenguaje?
2
Descripción
• Definiremos un lenguaje de programación
• Qué hace falta para definir un lenguaje de programación:
Cómo se escribe con este lenguaje? sintaxis
Qué significan las cosas que escribimos con este lenguaje? semántica
3 4
Definición de un lenguaje
• Sintaxis: define las “oraciones” “permitidas” Secuencia de caracteres (‘letras’) = token (‘palabra’) Secuencia de tokens (‘palabras’) = sentencias (‘oración’) Quién verifica que un programa sea sintácticamente correcto?
• Semántica: define qué significa un programa, y qué se se espera del programa.
print “hello world” Quién verifica que un programa sea semánticamente correcto?
5
Definición de un lenguaje (sección 2.1 del libro)
• Sintaxis: define las “oraciones” “permitidas” Secuencia de caracteres (‘letras’) = token (‘palabra’) Secuencia de tokens (‘palabras’) = sentencias (‘oración’) Quién verifica que un programa sea sintácticamente correcto? el compilador
• Semántica: define qué significa un programa, y qué se se espera del programa.
print “hello world” Quién verifica que un programa sea semánticamente correcto? en algunos casos, la derivación, el testing
Sintaxis
18/03/13
2
Sintaxis
7
Tokenizer
Parser
Secuencia de Caracteres
Secuencia de Tokens
Árbol sintáctico representado al
programa.
Buenos#Aires#es#la#capital#y#la#ciudad#mas#grande
[“Buenos Aires”,”es”, “la”, “capital”,”y”,”la”,”ciudad”,
”mas”,”grande”]
Bs As
es
y
la ciudad mas grande la capital
8
Sintaxis
Tokenizer
Parser
Secuencia de Caracteres
Secuencia de Tokens
Árbol sintáctico representado al
programa.
“fun {Max X Y}\n\tif X>Y then X else Y end\nend”
‘fun’ ‘{‘ ‘Max’ ‘X’ ‘Y’ ‘}’ ‘if’ ‘X’ ‘>’ ‘Y’ ‘then’ ‘X’ ‘else’ ‘Y’ ‘end’ ‘end’
Max
fun
[X Y] if
> X Y
X Y
• definimos la sintaxis de un lenguaje mediante reglas (en el mejor caso, con una gramática) • una oración pertenece a nuestro lenguaje (es válida) si hay una secuencia de reglas de la gramática que explican cómo se generó • una secuencia de reglas se puede representar como un árbol de derivación
Sintaxis y derivación sintáctica
10 Ejemplo de derivación sintáctica top-down y bottom-up
<s> local X in <s> end
local X in local Y in <s> end end local X in local Y in <s> <s> end end
local X in local Y in X=true <s> end end local X in local Y in X=true if <x> then <s> else <s> end end end local X in local Y in X=true if X then Y=1 else Y=~1 end end end
Ejemplos de gramáticas informales
11
NAME ls -- list directory contents SYNOPSIS ls [-ABCFGHLOPRSTUW@abcdefghiklmnopqrstuwx1] [file ...]
NAME man - format and display the on-line manual pages SYNOPSIS man [-acdfFhkKtwW] [--path] [-m system] [-p string] [-C config_file] [-M pathlist] [-P pager] [-B browser] [-H htmlpager] [-S section_list] [section] name
Qué problemas presentan estas descripciones informales? Qué ambigüedades? Qué efectos puede tener la ambigüedad?
Ejemplos de gramáticas informales
Una dirección de correo es: un string, seguido de una @ seguido de varios strings separados por puntos.
Qué es un string? Qué caracteres pueden aparecer en un string? Cuántos strings pueden aparecer separados por puntos? Cuántas @ puede haber? una larga lista de etc.
12
18/03/13
3
13 Gramáticas Independientes de Contexto y
Sensibles al Contexto
• Gramática independiente (o libre) de contexto (CFG) Fácil de leer y entender No consigue capturar de forma elegante e intuitiva algunos fenómenos propios de los lenguajes de programación
• Gramática sensible al contexto Expresa restricciones en el lenguaje (e.g. “una variable debe estar declarada antes de usarse”)
14 Gramáticas Independientes de Contexto y
Sensibles al Contexto
• Gramática independiente (o libre) de contexto (CFG) Fácil de leer y entender No consigue capturar de forma elegante e intuitiva algunos fenómenos propios de los lenguajes de programación
• Gramática sensible al contexto Expresa restricciones en el lenguaje (e.g. “una variable debe estar declarada antes de usarse”)
para definir lenguajes de programación:
Gramáticas Libres de Contexto (e.g. con BNF) +
Conjunto de restricciones (e.g. con predicados)
15
<digit> ::= 0 | 1 | 2 | 3 | 4| 5 | 6 | 7 | 8 | 9 <int> ::= <digit> { <digit> } <list <int>> ::= nil | <int> ‘|’ <list <int>> <statement> ::= if <expression> then<statement> {elseif <expression> then <statement>} [ else <statement> ] end | …
Definiendo gramáticas formales con la Forma Bachus-Naur (BNF):
31 | 5 | nil
BNF y su notación
16
::= el elemento a la izquierda es definido por las construcciones de la derecha
* el elemento ocurre 0 o más veces {…} agrupa los elementos entre llaves […] agrupa elementos opcionales | “o” exclusivo
17
Definimos nuestro Lenguaje de Kernel
〈s〉 ::= skip sentencia vacía | 〈var〉 = 〈var〉 unificación variable-variable
| 〈var〉 = 〈value〉 unificación variable-valor | 〈s〉 〈s〉 composición secuencial | local 〈var〉 in 〈s〉 end declaración | if 〈var〉 then 〈s〉 else 〈s〉 end condicional | '{' 〈var〉 〈var〉 … 〈var〉 '}' aplicación de procedimiento | case 〈var〉 of 〈pattern〉 then 〈s〉 else 〈s〉 end chequeo de patrones
〈var〉 ::= ... expresión de valor 〈pattern〉 ::= ... patrón
sintaxis de una sentencia 〈s〉 Tokenizador Tokens
Análisis Sintáctico
Semántica
Lenguaje de Programación Secuencia de
Caracteres
EBNF BNF
CFG
Parser
Palabras clave
18/03/13
4
19
Para saber más…
• sobre qué es una gramática: http://en.wikipedia.org/wiki/Formal_grammar • y de ahí:
• BNF: http://en.wikipedia.org/wiki/Backus%E2%80%93Naur_Form • EBNF: http://en.wikipedia.org/wiki/Extended_Backus%E2%80%93Naur_form
27 Sentencias de nuestro lenguaje de núcleo (tabla 2.1)
〈s〉 ::= skip sentencia vacía | 〈var〉 = 〈var〉 unificación variable-variable
| 〈var〉 = 〈value〉 unificación variable-valor | 〈s〉 〈s〉 composición secuencial | local 〈var〉 in 〈s〉 end declaración | if 〈var〉 then 〈s〉 else 〈s〉 end condicional | '{' 〈var〉 〈var〉 … 〈var〉 '}' aplicación de procedimiento | case 〈var〉 of 〈pattern〉 then 〈s〉 else 〈s〉 end chequeo de patrones
〈var〉 ::= ... expresión de valor 〈pattern〉 ::= ... patrón
sintaxis de una sentencia 〈s〉
28
Indentificadores de Variables (2.3.1)
• 〈variables〉 Define un conjunto de variables. • Las variables empiezan con letra mayúscula seguida de una secuencia (posiblemtente vacía) de caracteres alfanuméricos o underscore. • Cualquier secuencia de caracteres imprimibles encerrados entre comillas cruzadas (back-quote). • ejemplos:
X Y1 Hello_World `hello this is a $5 bill`
ejercicio: Escribir la gramática que describe el lenguaje de variables (la solución está en las tablas C.9 y C.10 del apéndice C del libro)
29
Valores y tipos (2.3.1)
• Un tipo de datos es un conjunto de valores y un conjunto de operaciones asociadas. • ejemplo: Int es el tipo de datos ”Entero”, i.e el conjunto de todos los valores enteros. 1 is of type Int
• Int tiene un conjunto de operaciones asociadas, incluyendo +,-,*,div, etc. • Crearemos nuestro lenguaje de manera que se puedan describir elementos de distinto tipo. El modelo viene con un conjunto de tipos básicos.
30
Descripción de Tipos de Valores (tabla 2.2)
〈value〉 ::= 〈procedure〉 | 〈record〉 | 〈number〉 〈procedure〉 ::= proc '{' '$' 〈var〉 … 〈var〉 '}' 〈s〉 end 〈record〉, 〈pattern〉 ::= 〈literal〉 | 〈literal〉 (〈feature〉 : 〈var〉 … 〈feature〉 : 〈var〉)
〈literal〉 ::= 〈atom〉 | 〈bool〉 〈feature〉 ::= 〈int〉 | 〈atom〉 | 〈bool〉 〈bool〉 ::= true | false 〈number〉 ::= 〈int〉 | 〈float〉 〈atom〉 ::= 〈lowercasechar〉 {<alphanumerchar>} …
33
Números (2.3.3)
• Enteros 314, 0 ~10 (minus 10)
• Flotantes 1.0, 3.4, 2.0e2, 2.0E2 (2×102)
18/03/13
5
34
Átomos y Booleanos (2.3.3)
• Una secuencia que empieza con un caracter en minúscula, seguido de caracters o dígitos, …
person, peter ‘Seif Haridi’
• Booleanos: true false
• Esta definición es ambigua, cómo la arreglamos?
35
Registros (2.3.3)
• Representación Compuesta (lo usaremos para estructura de datos)
〈l〉(〈f1〉 : 〈x1〉 … 〈fn〉 : 〈xn〉) 〈l〉 is a literal
• ejemplos person(age:X1 name:X2) person(1:X1 2:X2) ‘|’(1:H 2:T) nil person
37
Registros Especiales: tuplas (2.3.3)
Tuplas 〈l〉(〈x1〉 … 〈xn〉)
Equivalente al registro: 〈l〉(1: 〈x1〉 … n: 〈xn〉)
• ejemplo: person(X Y)
corresponde al registro person(1:X 2:Y)
38 Registros Especiales: listas (subtipo de tupla) (2.3.3)
Listas 〈x1〉 | 〈x2〉
(también podemos escribirlas con un operador infijo ‘|’) Equivalente a la tupla: ‘|’(〈x1〉 〈x2〉)
• ejemplo: H | T
corresponde a la tupla ‘|’(H T)
que corresponde al registro ‘|’(1:H 2:T)
39
listas
〈x1〉 | 〈x2〉 | 〈x3〉 ‘|’ asocia a la derecha
〈x1〉 | (〈x2〉 | 〈x3〉)
ejemplo: 1 | 2 | 3 | nil
es 1 |( 2 | (3 | nil ))
‘|’
‘|’
‘|’
1
2
3 nil
42
Variaciones sintácticas en listas
Podemos escribir X1=5|6|7|nil
que es lo mismo que X1=5|(6|(7|nil))
que es lo mismo que X1=‘|’(5 ‘|’(6 ‘|’(7 nil)))
Y todavia mas corto: X1=[5 6 7]
18/03/13
6
46 Registros Especiales: strings (subtipo de lista) (2.3.3)
• Un string es una lista de códigos de caracteres encerrados con comillas. • ejemplo: ”E=mc^2”
significa lo mismo que: [69 61 109 99 94 50]
47
Definición de Procedimientos (2.3.3)
〈x〉 = proc {$ 〈y1〉 … 〈yn〉} 〈s〉 end Crea un valor, “resultado” del procedimiento Liga la variable 〈x〉 a ese valor Una variación sintáctica del procedimiento: proc {〈x〉 〈y1〉 … 〈yn〉} 〈s〉 end
Pero no olvidemos que un procedimiento es siempre una asignación, se ve cuando lo traducimos a kernel
49
Reflexiones sobre Sintaxis
50
Asignación de Tipo a Variables
• Los valores claramente tiene un tipo, e.g., enteros, strings. Qué pasa con las variables?
51
Asignación de Tipo a Variables
• Los valores claramente tiene un tipo, e.g., enteros, strings. Qué pasa con las variables? Los lenguajes de programación tienen diferentes comportamientos respecto al tipo de las variables: • Fuertemente Tipado: La variables pueden tener asociado un tipo, que restringe el tipo de valor que pueden acomodar. Cómo se determina ese tipo?
Estático: todos los tipos de las variables se saben en tiempo de compilación. Puede ser declarado por el usuario. Dinámico: una variable adquiere un tipo en cuando se le asocia un valor. En cualquier caso, ese tipo no cambia a lo largo de la ejecución. El tipo es único y fijo.
• Débilmente Tipado: Las variables no tienen tipos asociados. Eg. Los argumentos de una función pueden variar de tipo.