DESARROLLO DE LOS LENGUAJES ARTIFICIALES
Lenguajes
artificiales, son
los creados por el hombre, basados en los lenguajes naturales, para comunicarse
con la máquina son conocidos como lenguajes de programación.
Lenguajes de
programación. Es
una serie específica de caracteres, utilizada para formar palabras o símbolos,
que le permiten a un programador dar instrucciones a un computador para
efectuar una serie de operaciones aritméticas y lógicas. Cada lenguaje de
programación tiene su propia gramática y sintaxis, que son traducidas a
lenguaje de máquina por ensambladores, compiladores e interpretes
Los lenguajes de
programación son lenguajes artificiales que han sido creados para poder decirle
a la máquina qué es que tiene que hacer. Todos los lenguajes de programación
tienen un grupo de instrucciones propias. Las instrucciones son, simplemente,
órdenes para la computadora.
Los
lenguajes de programación han evolucionado a través de generaciones. En cada
nueva generación, van necesitándose menos instrucciones para indicarle a la
computadora que tarea efectuar. Es decir, un programa escrito en un lenguaje de
primera generación ( maquina y/o ensamblador ) puede requerir mas de 100
instrucciones; ese mismo programa requerirá menos de 25 instrucciones en un lenguaje
de tercera generación
PRIMERA GENERACIÓN DE LENGUAJES
Trabajan
a nivel de instrucciones máquina, con el menor nivel de abstracción posible con
el que se puede representar un programa, el lenguaje ensamblador, representa la
primera generación de lenguajes.
SEGUNDA GENERACIÓN DE LENGUAJES
Fue desarrollada a
finales de los 50 y principios de los 60 y ha servido como base a todos los
lenguajes de programación modernos. La segunda generación de lenguajes esta
caracterizada por su amplio uso, la enorme cantidad de bibliotecas de software
y la gran familiaridad y aceptación
FORTRAN (FORMULA TRANSLATINF
SYSTEM)
Fue
el más usado para programación científica e ingeniería. Foltran I nació en 1954
implementado en la computadora IBM 704 1956, se fueron apareciendo
sucesivamente en II, III etc. en 1977 salió el FOLTRAN 77 añadía
características al lenguaje que mejoraban su capacidad de programación.
COBOL
En
1950 se sintió la necesidad de un lenguaje de procesamiento de datos. 1959 se
formó el comité CODASYL (Conference on Data Systems Languages), desde hay se
hizo una descripción de tal lenguaje. En 1960 se publicó un borrador de este.
En 1968 fue aprobado por la American National Standard. En 1981 se presento
definitivo.
TERCERA GENERACIÓN DE LENGUAJES
Su
nivel de representación de programas de computadora es superior, pero aún hay
que especificar distintos procedimientos algorítmicos perfectamente detallados.
Denominados
lenguajes de programación moderna o estructurada, están caracterizados por sus
potentes posibilidades procedimentales y de estructuración de datos, se pueden
dividir en dos grandes categorías: lenguajes de alto orden de propósito general
y lenguajes especializados.
DE PROPÓSITO GENERAL ENCONTRAMOS
ALGOL,
PL/1, PASCAL, MODULA 2, C Y ADA han sido adoptados como lenguajes con potencial
para un gran espectro de aplicaciones:
PASCAL
Es una evolución
del ALGOL, en 1958 trajo mucho interés e implementación a lo largo de los 3
años, popular entre los científicos informáticos en Europa. Se convirtió en un
lenguaje universal para la definición de algoritmos.
Fue desarrollado
con un lenguaje de propósitos generales con aplicaciones en un amplio rango de
interés surgió el ALGOL 68, fue demasiado ambicioso para ser práctico; Niklaus
Wirth diseñó un sucesor más reducido lo llamo "PASCAL" su versión fue
definida e implementada en 1973 y estandarizado en 1983.
PL/1
Fue
creado como un lenguaje de propósito general. Primera versión fue presentada
por la Advanced Languaje Develomen Comité del Proyecto Share Fortran y fue
llamado NPL (New Programing Languaje) fue implementado por IBM bajo PL/1, así
fue aceptado, aunque en 1981 se ha realizado el refinamiento del PL/1 standard,
llamado Subset/6 PL/1 para preservar la mayoría de las características útiles.
C
Se
diseño para aumentar la economía de expresión en una amplia variedad de
aplicaciones. En 1969 los laboratorios Bell buscaron una alternativa para el
sistema operativo Multics para computadora PDP-7 paralelo al Unix. En 1973 se
reescribio el Unix en C, fue ampliamente usado.
ADA
En 1975 el Departamento de Defensa
formo un grupo de trabajo en lenguajes su misión era: · Identificar los
requerimientos de lenguajes en el Departamento de Defensa, · Evaluar la
adecuación de los lenguajes existentes y · Evaluar la adecuación de los
lenguajes existentes.
En 1979 se presentó la evaluación
final del propuesto por Honeywell-Bull, se seleccionó como el nuevo lenguaje de
alto nivel del Dpto de Defensa, el lenguaje se denominó ADA, en reconocimiento
a Agusta Ada Byron (ella es considerada la primera programadora del mundo, pues
trabajó con Charles Babbage a principios del Siglo XIX).
MODULA -2
En 1977 comenzó el proyecto para el
diseño de una computadora integral Hardware-Software en el Instituto For
Informatic en Zurich, resuelve los problemas de PASCAL , también como
desarrollo de software eficiente y una efectiva utilización de los recursos de
máquina.
LENGUAJES ESPECIALIZADOS
Están
caracterizados por su usual formulación sintáctica que ha sido diseñada para
una aplicación particular, entre los que se encuentran el LIPS, Prolog,
Smalltalk, APL y FORTH.
APL (Aprograming Lenguaje)
Fue
introducido por Kenneth Iverson en su libro A Programming Language (1962),
implementado para los programas que hacen un gran uso de tablas vectores
matrices y para los que se desea una solución rápida interactiva.
Inicialmente
fue soportado por IBM , este contribuye significativamente al campo de los
lenguajes de programación y sus aplicaciones.
LISP (Lisp Processor)
Diseñado
para la manipulación de fórmulas simbólicas. Fue desarrollado por John McCarthy
entre 1956-58, se implementó primero sobre IBM 704 en 1960. Desde 1960 se han
producido varios dialectos, no han sido estandarizados, esta disponible en
software de ayuda.
PROLOG (Programming in Logic)
Diseñado para
aplicaciones de inteligencia artificial, gran parte de la reciente atención al
Prolog se debe al proyecto japonés de Computadora de 5a. generación. Fue
desarrollado a principios de 1970 por Philippe Roussel. Sin embargo el interés
por la programación IA ha llevado al desarrollo de muchas implementaciones
recientes.
SNOBOL
Basado
en unos principios sólidos de identificación de secuencias para resolver los
problemas de manipulación de cadenas.
Fue diseñado en 1962, no ha sido estandarizado
aunque ha sido ampliamente implementado sobre diferentes máquinas, han salido 4
versiones.
CUARTA
GENERACIÓN DE LENGUAJES
Han
elevado el nivel de abstracción, contiene una sintaxis distinta para la
representación del control y para la representación de la estructura de datos
representa estas estructuras en un mayor nivel de abstracción eliminando la
necesidad de especificar detalles algorítmicos. Combinan características
procedimentales y no procedimentales, permite al usuario especificar condiciones
con sus correspondientes acciones (características procedimentales) mientras
que pidiendo al mismo tiempo al usuario que indique el resultado deseado (no
procedimentales) para encontrar los detalles procedimentales aplicando su
conocimiento del dominio específico.
El sistema del L4G "sabe"
cómo calcular los datos financieros deseados y lo hace sin que el programador
tenga que especificar los algoritmos apropiados.
Lenguajes
de petición:
Permiten al usuario manipular de forma sofisticada la información contenida en
base de datos previamente creada.
Generadores
de programas:
Presentan otra clase de L4G , más que basarse en una base de datos predefinida,
un generador de programas permite al usuario crear programas en un lenguaje de
tercera generación usando notablemente menos sentencias. Estos lenguajes de
programación de muy alto nivel hacen un fuerte uso de la abstracción de datos y
procedimientos.
Otros
L4G: Los lenguajes
de soporte a la toma de decisiones: permiten que los no programadores lleven a
cabo una gran variedad de análisis qué pasa si que van desde simples modelos de
hojas de cálculo bidimensionales hasta los sofisticados sistemas de modelos
estadísticos y de investigación operativa. Los lenguajes de prototipos: se han
desarrollado para asistir en la creación de prototipos facilitando en la
creación de interfaces para el usuario y de diálogos, además de proporcionar
medios para el modelado de datos. Los lenguajes de especificación formal: se
pueden considerar L4G cuando producen código de máquina ejecutable.
SMBD sistemas de manejo de base de
datos, lenguajes sin procedimientos, están diseñados para aplicaciones que
procesen bajos volúmenes de datos.
BASIC: Lenguaje interactivo, permite
comunicación entre el usuario y el sistema durante la preparación y uso de los
programas, existe estándares de la ANSI.
Un programa en C se conforma como una colección de
procedimientos (a menudo llamadas funciones, aunque no tengan valores de
retorno). Estos procedimientos contienen declaraciones, sentencias, expresiones
y otros elementos que en conjunto indican a la computadora que realice cierta
acción.
IDENTIFICADORES
ESTANDAR
Los identificadores son nombres dados a constantes,
variables, tipos, funciones y etiquetas de un programa. Un identificador es una
secuencia de letras (mayúsculas y/o minúsculas),dígitos (0,1,...,9) y el
carácter especial de subrayado ( _ ). El primer carácter de un identificador
debe de ser un carácter letra o el carácter de subrayado.
Las letras pueden ser mayúsculas o minúsculas y se
consideran como caracteres diferentes.
Por
ejemplo:
Suma
Calculo_numeros_primos
ab123
_orden
ar
i
PALABRAS
RESERVADAS DEL LENGUAJE C (ANSI-C)
Las palabras reservadas son identificadores
predefinidos que tienen un significado especial para el compilador C. Un
identificador definido por el usuario, no puede tener el mismo nombre que una
palabra reservada.
auto
continue
else
for
long
sizeof
typedef
wile
break
default
num
goto
register
static
union
main
case
do
extern
if
return
struct
unsigned
char
double
float
int
short
switch
void
signed
Algunas
versiones de compiladores pueden tener palabras adicionales, asm, ada, fortran,
pascal, etc. Cabe
hacer mención que el lenguaje que analizaremos es el ANSI C, y éste debe de
compilarse en cualquier compilador y cualquier plataforma, que soporte el ANSI
C (LINUX, UNIX, MS-DOS, etc.).
ESTRUCTURA
DE UN PROGRAMA
Como en todos los lenguajes siempre es bueno
comenzar con un programa,
simple
y sencillo.
/*
Un primer programa en C*/
#include <stdio.h>
void main(void)
{
printf(''Hola
Puebla”);
return;
}
TIPOS
DE DATOS ESTÁNDAR DEL LENGUAJE C
Los tipos básicos del lenguaje son:
Carácter: Este tipo de dato se declara con la palabra reservada char
y ocupa un byte en memoria, con un byte se pueden representar 256 símbolos
posibles.
Real: Este tipo de datos se declara con la palabra reservada
double o float, si se utiliza la primera, entonces la variable que se declare
ocupa 8 bytes de memoria y si se utiliza la segunda entonces la variable que se
declare utiliza 4 bytes de memoria.
Entero: Este tipo de datos se declara con la palabra reservada int
y tiene típicamente la misma longitud en bits que los registros del procesador
de cada máquina. Por ejemplo, ocupa 2 bytes de memoria para equipos de 16 bis
(8088, 80286) y 4 bytes en equipos de 32 bits (80486, Pentium, Celeron , Xeon,
Athlon, Duron). En la Tabla 1 se muestran todos los tipos de datos estándar en
el lenguaje C.
Acerca
de los tipos de datos reales ( flotantes )
C proporciona los tipos flotantes float y double
para manejar números de la forma 1.7, 0.0001, 3.14159. También existe una
forma exponencial para representar un número, por ejemplo, 1.092332e5. La
correspondiente notación científica de este número es:
1.092332e5
= 1.092332*10*10*10*10*10
=
1.092332*100000
=
109233.2
Acerca del tipo de datos char
Las constantes y las variables de tipo char se usan
para representar caracteres y cada carácter se almacena en un byte. Un byte
esta compuesto de 8 bits, el cual es capaz de almacenar 2 a la 8 o 256 valores
diferentes, pero solo un grupo pequeño de ellos es realidad representa a un conjunto de caracteres
imprimibles.
Acerca
de las cadenas
Una cadena es una secuencia de caracteres entre
comillas “ ”.Obsérvese que “ es un solo caracter y no dos. Si el caracter (“)
tiene que aparecer en una cadena, éste debe de ir precedido por el carácter \.
Ejemplos:
“Una
cadena de texto”
DECLARACIÓN
DE VARIABLES Y CONSTANTES
Declaración de variables
Una variable en C se declara de la siguiente
manera: tipo identificador [, identificador , ...., identificador] ;
donde
,
tipo
:determina el tipo
de la variable (char, int, ...).
identificador:
indica el nombre
de la variable. Los corchetes ([ ]) indica que se pueden definir en línea mas
de una variable del mismo tipo separadas por coma (,) y terminando con punto y
coma (;).
Por
ejemplo:
int
i,j,k;
Declaración
de CONSTANTES
Las constantes en C pueden ser:
Números
reales Números enteros Cadenas Carácter
3.10
1234 “hola C.U.” ‘a’
0.987
-10 “” ‘#’
Una constante (cualquier tipo de constante)
en C se define de la siguiente manera:
#define
identificador valor
donde,
identificador
es el nombre de la
constante
valor
es el valor
asociado a la constante
Ejemplo:
#define
entero 10
INSTRUCCIONES
DE ENTRADA Y SALIDA
Las operaciones de entrada y salida no forman parte
del conjunto de sentencias del lenguaje C, sino que pertenecen al conjunto de
funciones de la librería estándar de entrada y salida de C. Por ello, todo
programa que deberá contener la línea (o líneas) iniciales:
#include
< stdio.h >
Las siguientes
funciones son algunas de las más utilizadas para entrada y salida de datos.
printf, scanf, getch, getchar,
puts, gets,
Todas y cada una de ellas tiene una sintaxis que las
identifica.
1
Salida de datos utilizando la función printf ( ) printf(cadena de control, lista de
argumentos) cadena de control especifica como va a ser la salida. Es una
cadena delimitada por comillas (“ “), formada por caracteres ordinarios,
secuencias de escape (ver tabla 9) y especificaciones de formato bajo el cual
se requiere la salida de la información (datos) hacia pantalla lista de
argumentos representa el valor o valores a escribir en la pantalla. Una
especificación de formato está compuesta por:
%
[flags] [width]
[.prec] [F|N|h|l|L] tipo_de_dato
Cada
uno de los datos que se desee mandar a imprimir debe de ir antecedido por el
caracter % y después debe de
venir
(en este orden) lo siguiente (no es necesario poner todo, lo que se encuentra
entre corchetes es opcional ) :
Componente
Que se especifica
[flags]
(Opcional) Justificación, etc.
[width]
(Opcional) Número de dígitos significativos parte entera
[.prec]
(Opcional) Número de dígitos significativos parte real
[F|N|h|l|L]
(Opcional) Modificadores de salida
N =
near apuntador h = entero corto
F =
far apuntador l = entero largo
L =
real largo
tipo_de_dato
(requerido), el
tipo de dato puede ser:
c =
imprime un carácter
d =
imprime un entero
e =
notación cientifica
s =
imprime una cadena
f =
decimal en punto flotante
Ejemplo:
printf("hola Puebla son las %d
\n", tiempo);
EJEMPLO FINAL:
#include <stdio.h>
#include <conio.h>
main()
{
textbackground(4);
clrscr();
float base, altura, area;
textcolor(564+128);
printf("base:\t");
scanf("%f",&base);
printf("altura:\t");
scanf("%f",&altura);
area=
base* altura/2;
printf("el
area es:\t %4.2f",area);
getch
();
return
0;
}
1. Para cada uno de los niveles de la Jerarquía de Chomsky,
proponga
gramáticas que puedan encuadrarse en ellos.
2. Considere la estructura del bucle for en lenguaje C.
Escriba una gramática
libre del contexto que permita generar instancia de dicho
bucle sintácticamente
váli das.
3. Realice el mismo ejercicio para las estructuras while,do
while,ifdel
lenguaje C.
4. Para todo lenguaje A , ¿Cuál es es lenguaje A · Ø?
5. Considere A = { a,å } .Obtenga
n
para n =0 1 2 3. ¿Cuántos elementos,
para n arbitrario tiene A
n
?
Considere los lenguajes A = { ε } ,B = {
aa,ab,bb }
,C = { ε,aa,ab } y D =
Ø.Obtenga ∪B,A ∪C,A ∪D,B ∪D,A ∩B,B ∩C,C ∩D,A ∩D .
7. Demuestre mediante una expresión regular que los
siguientes son lenguajes
regulares, dado Ó = { a,b } .
{ a
i
: i>0 }
{ a
i
: i>n } para un n ¡Ý0 establecido.
{ w ¸Ó *: w termina en a }
8. Demuestre que el lenguaje de las cadenas de unos y ceros
con al menos
dos ceros consecutivos es regular.
9. Construya AFD que acepten los siguientes lenguajes sobre
{ a,b } .
{ w : toda a de w está entre dos b }
{ w : w contiene la subcadena abab }
{ w : w tiene al menos tres a consecutivas }
10. Construya autómatas finitos que acepten el lenguaje que
las siguientes
expresiones regulares definen:
* Corresponde a la relación número 1 para los alumnos
del plan de ITIG 2002.
** c °
Antonio Tomeu
ab +(b + aa )*
ab
³¡
()+ bbb
¢
*+ a *
´
b
((a + b )(a + b ))*+((a + b )(a + b )(a + b
))*
(*y **)+(x + zy )
(+(b )+(c + d *))(*+ d *)
11. Considere una versión reducida del lenguaje C, con las
características
siguientes:
sus únicos tipos son char y int.
la única sentencia iterativa es el bucle for.
la única sentencia bifucartiva es if.
los identificadores comienzan por un carácter y se componen
de caracteres
y dígitos.
se dispone de los operadores siguientes: =,,,==,!=.
Construya una gramática que permita escribir programas
sintácticamente
correctos en este lenguaje.
12.Dado elAFNDde la Figura 3,se pide:
calcular ä 0 (0 0110) =
calcular ä 0 (0 10010) =
calcular ä 0 (0 010) =
obtener un AFD equivalente:
13. Dado el AFND-å de la Figura 4, se pide:
calcular ä 0 (0 000) =
calcular ä 0 (0 0112) =
calcular ä 0 (0 2222) =
obtener un AFND equivalente:
14. Dados los AFD de las Figuras 1 y 2, obtenga gramáticas
regulares que
generen los lenguajes que estos aceptan.
15. Dadas las siguiente gramáticas regulares lineales por
la derecha, obtenga
AFND-å
que acepten los lenguajes que generan.
G 1 = h{S,A,B } , { 0 1 } ,S, { S ¨0101 A ¨1 | 0 B
¨00 | 1 }i
G 2 = h{S,X,Y } , { a,b,c } ,S, { S ¨Xa | Ybc | c,X
¨abX | c,Y ¨baY | c }i
G 3 = h{S } , { 1 } ,S, { S ¨11 | 1 }i
16. Proponga AFD que acepten los siguiente lenguajes sobre
Ó = { 0 1 }
cadenas que terminan en 00
cadenas que incluyen a la subcadena 010.
cadenas con un número impar de 1.
cadenas que empiezan y acaban en 01.
17. Escriba expresiones regulares que representen a los
siguientes lenguajes:
el conjunto de cadenas que no contiene a la subcadena 101.
el conjunto de cadenas donde cada pareja de ceros va
seguida de una pareja
de unos.
18. Un analizador léxico es un autómata finito con salida.
Diseñe un autó-mata
finito con salida capaz de reconocer el siguiente lenguaje
y dando además
la salida que se indica en la tabla:
Palabra reconocida Salida del autómata
main <main
{ <inicio_bloque
} <fin_bloque
w ¸(+ b + ...+ )<identificador
int <entero
+ <op_arit
= <asignación
<<men_est
; <nueva_sent
19. Probar que todo lenguaje reconocido por un AFD es
también reconocido
por una máquina de Turing de cuadruplas. Aplicar el
resultado al lenguaje (0 1)
. ¿Cuál en el significado de poder llevar a cabo dicha
transformación?
20. Dado el lenguaje L = { a
n
b : n>0 } , escriba una gramática regular que
lo genere y un AFD que lo reconozca.
21. Dada la gramática G = h{S,B } , { 0 1 } ,S,P i siendo P
el siguiente con-junto
de reglas de producción
P = { S ¨110 B ¨1 B ¨0 B ¨å }
construya una AFND-å que acepte el lenguaje generado por la
gramática.
22. Repita el mismo ejercicio para G = h{S } , { 0 1 } ,S,P
i siendo P el sigu-
iente conjunto de reglas de producción
P = { S ¨S 10 S ¨0 }
23. Dado el lenguaje L = { xaab : x ¸(1 + 0)* } ,
proprocione una expresión
regular que lo describa, una gramática regular que lo
genere, y un autómata
finito que lo acepte.
24. Escriba una gramática que sea capaz de generar
expresiones aritméti-
cas con parátesis balanceados. Utilice como conjunto de
símbolos terminales el
siguiente:
T = {
a,b,c,()+ ., *,/ }