Actividad 10 - Daniel Cuellar

Vista previa del material en texto

UNACAR
Universidad Autónoma del Carmen
“Por la Grandeza de México”
Facultad de Ciencias de la Información
MATERIA
LENGUAJES FORMALES Y AUTOMATAS
TRABAJO
LA GRAMATICA Y LOS TIPOS DE GRAMATICA
NOMBRE
DANIEL VALDEMAR CUELLAR VALLES
MATRICULA
160623
Ciudad del Carmen, Campeche A 6 mayo del 2022
Introducción
Un modelo matemático es uno de los tantos modelos científicos que nos va a permitir representar de forma gráfica o visual y a través de ecuaciones matemáticas, relaciones, hechos, variables, parámetros o comportamientos que son difíciles de observar en la realidad. 
Siendo así la base de los lenguajes formales la cual estudia unas entidades matemáticas abstractas denominadas lenguajes, estos lenguajes difieren a los lenguajes naturales o comunes que se conocen en la actualidad, los lenguajes formales pueden, en determinadas circunstancias, servir como modelos abstractos de determinadas propiedades de las lenguas naturales.
Un lenguaje formal es un conjunto, finito o infinito, de cadenas definidas sobre un alfabeto finito. En pocas palabras estos permiten crear códigos de comunicación entre seres humanos y máquinas, es decir, la programación el punto de partida en este proyecto. Pues se propondrá un lenguaje el cual tiene como objetivo hacer operaciones con vectores, a través de un compilador el cual se encargará de procesar todas las pautas establecidas para el correcto funcionamiento del lenguaje. Este compilador es un traductor que permite traducir un lenguaje establecido por el programador a un lenguaje que entienda la máquina, este compilador tiene 6 etapas, estas etapas se agrupan en 2 fases: Etapa de análisis y Etapa de síntesis. Dentro de la fase de análisis se encuentra el analizador léxico, semántico y sintáctico.
Desarrollo
De acuerdo con (Rock Content, 2019) un lenguaje de programación es un lenguaje formal que, mediante una serie de instrucciones, le permite a un programador escribir un conjunto de órdenes, acciones consecutivas, datos y algoritmos para, de esa forma, crear programas que controlen el comportamiento físico y lógico de una máquina.
Mediante este lenguaje se comunican el programador y la máquina, permitiendo especificar, de forma precisa, aspectos como:
· Cuáles datos debe operar un software específico;
· Cómo deben ser almacenados o transmitidos esos datos;
· Las acciones que debe tomar el software dependiendo de las circunstancias variables.
El lenguaje es el medio y la programación es la forma de darle órdenes a una computadora, este proceso de comunicación entre usuario-maquina se puede descomponer entre dos niveles de programación los cuales son el bajo y el alto nivel.
Lenguaje de bajo nivel
Son lenguajes totalmente dependientes de la máquina, es decir, que el programa que se realiza con este tipo de lenguajes no se puede migrar o utilizar en otras máquinas. Al estar prácticamente diseñados a medida del hardware, aprovechan al máximo las características de este (Martín, 2020).
Este grupo engloba los siguientes tipos:
Lenguaje maquina
Es el sistema de códigos interpretable directamente por un circuito micro programable, como el microprocesador de una computadora. Este lenguaje se compone de un conjunto de instrucciones que determinan acciones que serán realizadas por la máquina.
Este lenguaje es mucho más rápido que los lenguajes de alto nivel.
La desventaja es que son bastantes difíciles de manejar y usar, además de tener códigos fuente enormes donde encontrar un fallo es casi imposible.
Lenguaje ensamblador
Este lenguaje de programación es un derivado del lenguaje máquina y está formado por abreviaturas de letras y números llamadas mnemotécnicos. Con la aparición de este lenguaje se crearon los programas traductores para poder pasar los programas escritos en lenguaje ensamblador a lenguaje máquina.
Como ventaja con respecto al código máquina es que los códigos fuentes eran más cortos y los programas creados ocupaban menos memoria.
Las desventajas de este lenguaje siguen siendo prácticamente las mismas que las del lenguaje ensamblador, añadiendo la dificultad de tener que aprender un nuevo lenguaje difícil de probar y mantener.
Lenguaje de alto nivel
Los lenguajes de programación de alto nivel se caracterizan porque su estructura semántica es muy similar a la forma como escriben los humanos, lo que permite codificar los algoritmos de manera más natural, en lugar de codificarlos en el lenguaje binario de las máquinas, o a nivel de lenguaje ensamblador.
Estos lenguajes permiten al programador olvidarse por completo del funcionamiento interno de la máquina para la que están diseñando el programa. Solo necesitan un traductor que entienda el código fuente como las características de la máquina.
PROGRAMA
Un programa informático es aquel complejo conjunto de componentes que codificados y traducidos a un lenguaje de programación en la red o en un ambiente de código HTML ejecutan tareas fácilmente para los humanos, respondiendo comandos preestablecidos para tal fin. También conocido como software, el programa informático recibe una buena cantidad de soporte que garantice el buen funcionamiento y rendimiento tanto en su versión original como en las mejoras que pueda obtener luego de desarrollado. (Redacción, 2021)
LENGUAJE PROPUESTO
Este lenguaje tiene como objetivo hacer operaciones con vectores los cuales pueden ser suma, resta, etc. En la Ilustración 1 se aprecia la sintaxis de un programa que suma valores de forma ordenada e imprime un resultado. La forma de iniciar un programa en este lenguaje es mediante las palabras reservadas "BEGIN" y "END" por ende todas las instrucciones del programa se deben colocar dentro de estas etiquetas. Muy al estilo de C la manera de terminar cada sentencia del lenguaje propuesto se hace con un ";" el cual le hace saber al compilador el límite de cada orden que se ingresa. Las variables se inicializan con el identificador "set", así mismo estas variables son de tipo conjunto por ejemplo "x","y" y "z". 
Para realizar una asignación de valores en una variable hay que indicar después del operador "=" los números a ingresar separador por comas si son más de uno, estos tienen que permanecer dentro de un paréntesis que funge como delimitador en la sentencia. Así cómo es posible asignar valores a una variable también es posible asignar resultados de operaciones, esto es posible si después del identificador se coloca un operador "=" y justo después se ingresa la palabra reservada correspondiente a la operación que se desea realizar, por último, dentro de los paréntesis delimitadores habrá que colocar las dos variables que contengan los datos para el procedimiento. Una vez almacenado el resultado de la operación es posible imprimirlo con la palabra reservada "print", esta misma no puede operar sola pues hay que indicarle que variable imprimirá mediante los delimitadores "()". El lenguaje propuesto en este proyecto es sensible a mayúsculas y minúsculas lo que implica diferenciar palabras escritas iguales solo cambiando el uso de mayúsculas y minúsculas.
Ilustración 1-Programa de ejemplo
Tabla de tokens
Los tokens son componentes de un programa los cuales están definidos por atributo y valor, el primero define al segundo respectivamente. En la Tabla 1 donde son mostrados todos los tokens utilizados para el lenguaje propuesto se empieza con las palabras reservadas, tales como "Begin" y "set" las cuales empiezan y terminan respectivamente las sentencias en el programa. Otros dos ejemplos de palabras reservadas son "set" la cual se usa para declarar una variable y "print" usada para imprimir texto o variables. 
Como siguiente tipo de atributo en la tabla se encuentran los identificadores como "x", "y" y "z" estos son las variables en el lenguaje propuesto, seguidamente están los signos de puntuación "," y ";" se utilizan para separar sentencias, así como para terminarlas. Después de los signos de puntuación viene el operador "=" el cual es usado para la asignación de datos. Los delimitadores "()" les prosiguen, enel contexto de este lenguaje se utilizan para determinar tipos específicos y los límites de una instrucción. 
Por último, se encuentran los números que van del "0-9" usados como en cualquier lenguaje de programación para usarlos en operaciones o inicializar variables como ejemplos.
	Atributo
	Valor
	Palabra reservada
	Begin
	Palabra reservada
	set
	Palabra reservada
	SUMA
	Palabra reservada
	print
	Palabra reservada
	End
	Identificador
	x
	Identificador
	y
	Identificador
	z
	Signo de puntuación
	;
	Signo de puntuación
	,
	Operador
	=
	Delimitador
	(
	Delimitador
	)
	Número
	1
	Número
	2
	Número
	3
	Número
	4
	Número
	5
	Número
	6
	Número
	7
	Número
	8
	Número
	9
Tabla 1-Tabla de tokens
Autómatas para validar el lenguaje propuesto
La razón para utilizar autómatas finitos deterministas viene en su propia definición pues como indica (P., P., D. , & Wesley, 2006) Este tipo de autómatas admite su definición de dos maneras bien diferentes: Como autómatas traductores o reconocedores. La definición como autómatas traductores continua a la definición de las máquinas secuenciales, y se los podría definir como una subclase de estas, ya que los autómatas finitos tendrían como limitante no poder iniciar desde cualquier estado como lo hacen en las máquinas secuenciales. Al limitarse en iniciar en el primer estado, así como también limitan el aceptar o no una determinada cadena recibida en la entrada, por lo tanto, la salida de estos solo tendrá dos valores posibles aceptar o no aceptar a la palabra de entrada.
Para el lenguaje propuesto se desarrollaron los siguientes autómatas:
1. Autómata para validar identificadores
1. Autómata para validar signos de puntuación
1. Autómata para validar el operador
1. Autómata para validar delimitadores
1. Autómata para validar números enteros sin signo
1. Autómata para validar números enteros con signo
1. Autómata para validar flotantes sin signo
1. Autómata para validar números flotantes con signo
1. Autómata para validar identificadores
El siguiente autómata valida los identificadores y palabras reservadas tales como: “SUMA”, “print”, “End”, “set” y “Begin” del lenguaje propuesto. Las partes que conforman este autómata son el alfabeto representado por , el conjunto de estados se representa con S y el estado inicial S0 seguido del estado final S1. A continuación se muestran estas partes previamente definidas con los datos pertinentes para el autómata que corresponde.
Como se muestra en la Imagen 1 el autómata empieza en el estado inicial S0 y termina en el estado final S1 haciendo que cualquier identificador ingresado empiece exclusivamente por una letra y termine con cualquier otro elemento del alfabeto.Imagen 1-Automata para validar identificadores
En la Tabla 2 se colocaron las transiciones de cada parte del alfabeto respecto a los estados en los cuales se desplazan, esto para validar los identificadores del lenguaje. La tabla está compuesta por 3 filas y 4 columnas, en la primera columna está el listado de todos los estados del autómata los cuales son “S0” y “S1” por último en la primera fila se encuentra el alfabeto compuesto por 
. La finalidad de la tabla es mostrar los movimientos que pueden realizar los componentes del alfabeto por los estados establecidos por el autómata.
	S
	[0-9]
	[a-zA-Z]
	_
	S0
	S1
	ϵ
	ϵ
	S1
	S1
	S1
	S1
Tabla 2-Transiciones de identificadores
2. Autómata para validar signos de puntuación
El siguiente autómata valida los signos de puntuación. Las partes que conforman este autómata son el alfabeto representado por , el conjunto de estados se representa con S y el estado inicial S0 seguido del estado final S1. A continuación se muestran estas partes previamente definidas con los datos pertinentes para el autómata que corresponde.
De acuerdo con la Imagen 2 el autómata empieza en el estado inicial S0 y termina en el estado final S1 haciendo que cualquier signo de puntuación ingresado sea validado solo una vez y acepte únicamente signos de puntuación.
Imagen 2-Autómata que reconozca signos de puntuación
En la Tabla 3 se colocaron las transiciones de cada parte del alfabeto respecto a los estados en los cuales se desplazan, esto para validar los signos de puntuación del lenguaje. La tabla está compuesta por 3 filas y 5 columnas, en la primera columna está el listado de todos los estados del autómata los cuales son “S0” y “S1” por último en la primera fila se encuentra el alfabeto compuesto por 
. La finalidad de la tabla es mostrar los movimientos que pueden realizar los componentes del alfabeto por los estados establecidos por el autómata.
	S
	,
	;
	:
	.
	S0
	S1
	S1
	S1
	S1
	S1
	ϵ
	ϵ
	ϵ
	ϵ
Tabla 3-Transiciones de los signos de puntuación
3. Autómata para validar el operador =
El siguiente autómata valida el operador “=”. Las partes que conforman este autómata son el alfabeto representado por , el conjunto de estados se representa con S y el estado inicial junto con el final S0. A continuación se muestran estas partes previamente definidas con los datos pertinentes para el autómata que corresponde.
En la Imagen 3 el autómata empieza en el estado inicial S0 y termina en ese mismo estado ya que el lenguaje propuesto solo admite un símbolo “=” por lo tanto termina donde empezó.
Imagen 3-Autómata para validar el operador =
En la Tabla 4 se colocaron las transiciones de cada parte del alfabeto respecto a los estados en los cuales se desplazan, esto para validar el operador “=” del lenguaje. La tabla está compuesta por 2 filas y 2 columnas, en la primera columna está el estado del autómata el cual es “S0” por último en la primera fila se encuentra el alfabeto compuesto por . La finalidad de la tabla es mostrar los movimientos que pueden realizar los componentes del alfabeto por los estados establecidos por el autómata.
	S
	=
	S0
	S0
Tabla 4-Transiciones del operador =
4. Autómata para validar delimitadores
El siguiente autómata valida los delimitadores. Las partes que conforman este autómata son el alfabeto representado por , el conjunto de estados se representa con S y el estado inicial S0 seguido del estado final S1. A continuación se muestran estas partes previamente definidas con los datos pertinentes para el autómata que corresponde.
En la Imagen 4 el autómata empieza en el estado inicial S0 y termina en el estado final S1 haciendo que cualquier delimitador sea validado solo una vez, aceptando únicamente el alfabeto mostrado.
Imagen 4-Autómata para validar delimitadores
En la Tabla 5 se colocaron las transiciones de cada parte del alfabeto respecto a los estados en los cuales se desplazan, esto para validar los delimitadores del lenguaje. La tabla está compuesta por 3 filas y 4 columnas, en la primera columna están los estados los cuales son “S0” y “S1” por último en la primera fila se encuentra el alfabeto compuesto por . La finalidad de la tabla es mostrar los movimientos que pueden realizar los componentes del alfabeto por los estados establecidos por el autómata.
	S
	[ ]
	{ }
	( )
	S0
	S1
	S1
	S1
	S1
	ϵ
	ϵ
	ϵ
Tabla 5-Transiciones de los delimitadores
5. Autómata para validar números enteros sin signo
El siguiente autómata valida los números enteros sin signo. Las partes que conforman este autómata son el alfabeto representado por , el conjunto de estados se representa con S y el estado inicial S0 seguido del estado final S1. A continuación se muestran estas partes previamente definidas con los datos pertinentes para el autómata que corresponde.
En la Imagen 5 el autómata empieza en el estado inicial S0 y termina en el estado final S1 haciendo que cualquier número entero sin signo sea validado solo una vez, aceptando únicamente el alfabeto mostrado.
Imagen 5-Autómata para validar números enteros sin signo
En la Tabla 6 se colocaron las transiciones de cada parte del alfabeto respecto a los estados en los cuales se desplazan, esto para validar los números enteros sin signo del lenguaje.La tabla está compuesta por 3 filas y 2 columnas, en la primera columna están los estados los cuales son “S0” y “S1” por último en la primera fila se encuentra el alfabeto compuesto por . La finalidad de la tabla es mostrar los movimientos que pueden realizar los componentes del alfabeto por los estados establecidos por el autómata.
	S
	[0-9]
	S0
	S1
	S1
	S1
Tabla 6-Transiciones de los números enteros sin signo
6. Autómata para validar números enteros con signo
El siguiente autómata valida los números enteros con signo. Las partes que conforman este autómata son el alfabeto representado por , el conjunto de estados se representa con S y el estado inicial S0 seguido del estado final S2. A continuación se muestran estas partes previamente definidas con los datos pertinentes para el autómata que corresponde.
En la Imagen 6 el autómata empieza en el estado inicial S0 y termina en el estado final S2 haciendo que cualquier número entero sin signo sea validado solo una vez, aceptando únicamente el alfabeto mostrado.
Imagen 6-Autómata para validar números enteros con signo
En la Tabla 7 se colocaron las transiciones de cada parte del alfabeto respecto a los estados en los cuales se desplazan, esto para validar los números enteros con signo del lenguaje. La tabla está compuesta por 4 filas y 4 columnas, en la primera columna están los estados los cuales son “S0”, “S1” y “S2” por último en la primera fila se encuentra el alfabeto compuesto por . La finalidad de la tabla es mostrar los movimientos que pueden realizar los componentes del alfabeto por los estados establecidos por el autómata.
	S
	+
	-
	[0-9]
	S0
	S1
	S1
	S1
	S1
	ϵ
	ϵ
	S2
	S2
	ϵ
	ϵ
	S2
Tabla 7-Transiciones de los números enteros con signo
7. Autómata para validar flotantes sin signo
El siguiente autómata valida los números flotantes sin signo. Las partes que conforman este autómata son el alfabeto representado por , el conjunto de estados se representa con S y el estado inicial S0 seguido del estado final S3. A continuación se muestran estas partes previamente definidas con los datos pertinentes para el autómata que corresponde.
En la Imagen 7 el autómata empieza en el estado inicial S0 y termina en el estado final S3 haciendo que cualquier número entero sin signo sea validado solo una vez, aceptando únicamente el alfabeto mostrado.
Imagen 7-Autómata para validar flotantes sin signo
En la Tabla 8 se colocaron las transiciones de cada parte del alfabeto respecto a los estados en los cuales se desplazan, esto para validar los números flotantes sin signo del lenguaje. La tabla está compuesta por 5 filas y 3 columnas, en la primera columna están los estados los cuales son “S0”, “S1”, “S2” y “S3” por último en la primera fila se encuentra el alfabeto compuesto por . La finalidad de la tabla es mostrar los movimientos que pueden realizar los componentes del alfabeto por los estados establecidos por el autómata.
	S
	.
	[0-9]
	S0
	ϵ
	S1
	S1
	S2
	S1
	S2
	ϵ
	S3
	S3
	ϵ
	S3
Tabla 8-Transiciones de los números flotantes sin signo
8. Autómata para validar números flotantes con signo
El siguiente autómata valida los números flotantes con signo. Las partes que conforman este autómata son el alfabeto representado por , el conjunto de estados se representa con S y el estado inicial S0 seguido del estado final S4. A continuación se muestran estas partes previamente definidas con los datos pertinentes para el autómata que corresponde.
En la Imagen 8 el autómata empieza en el estado inicial S0 y termina en el estado final S4 haciendo que cualquier número flotantes con signo sea validado solo una vez, aceptando únicamente el alfabeto mostrado.
Imagen 8-Autómata para validar números flotantes con signo
En la Tabla 9 se colocaron las transiciones de cada parte del alfabeto respecto a los estados en los cuales se desplazan, esto para validar los números flotantes con signo del lenguaje. La tabla está compuesta por 6 filas y 5 columnas, en la primera columna están los estados los cuales son “S0”, “S1”, “S2”, “S3” y “S4” por último en la primera fila se encuentra el alfabeto compuesto por . La finalidad de la tabla es mostrar los movimientos que pueden realizar los componentes del alfabeto por los estados establecidos por el autómata.
	S
	-
	+
	[0-9]
	.
	S0
	S1
	S1
	ϵ
	ϵ
	S1
	ϵ
	ϵ
	S2
	ϵ
	S2
	ϵ
	ϵ
	S2
	S3
	S3
	ϵ
	ϵ
	S4
	ϵ
	S4
	ϵ
	ϵ
	S4
	ϵ
Tabla 9-Transiciones de los números flotantes con signo
Conclusión 
(Pedro Bavera & Martín Nordio, 2003) “El analizador léxico forma parte de la primera fase de un compilador. Un compilador es un programa que lee un programa escrito en un lenguaje, el lenguaje fuente, y lo traduce a un programa equivalente en otro lenguaje, el lenguaje objetó.” esto quiere decir que sin un analizador léxico no sería posible compilar cualquier programa realizado en algún lenguaje de programación por ende las herramientas de software para el análisis léxico resultan ser muy útiles ya que facilitan la tarea de crear compiladores e intérpretes, así como autómatas destinados a diferentes propósitos ya sean en la industria o para tareas simples.
En conclusión, el análisis léxico es la piedra angular de la programación pues bien mencionan (Hernández Palacios & Hernández González, 2013) “A partir de los años 50 es necesario un compilador derivado de los lenguajes de alto nivel. Desde entonces, gracias al descubrimiento de técnicas sistemáticas para el manejo de muchas tareas, al desarrollo de buenos lenguajes de implantación, entornos de programación y herramientas de software, el diseño y desarrollo de un compilador se ha simplificado enormemente.” Esto es gracias a la creación de todas estas herramientas las cuales simplifican en enormes cantidades el generar autómatas, compiladores o algún otro programa que necesite el análisis léxico o sintáctico pues de no existir se tendrían que realizar a mano lo que resulta en una tarea tardada y tediosa.
Referencias
Hernández Palacios, R., & Hernández González, D. (05 de 07 de 2013). Herramientas para el diseño de compiladores. Obtenido de https://repository.uaeh.edu.mx/revistas/index.php/huejutla/article/view/1024/4817
Martín. (08 de 06 de 2020). Lenguajes de programación: los 3 niveles. Obtenido de ¿Qué es un lenguaje de programación? ¿Qué tipos existen? Alto, medio y bajo nivel.: https://catedrauno.com/programacion-lenguajes-niveles-436/#lenguajes-de-medio-nivel
P., I., P., M., D. , B., & Wesley, A. (2006). GHD. Obtenido de https://www.institucional.frc.utn.edu.ar/sistemas/ghd/T-M-AFD.htm
Pedro Bavera, F., & Martín Nordio, D. (02 de 05 de 2003). TesisJTLex-Bavera-Nordio-02.pdf. Obtenido de https://dc.exa.unrc.edu.ar/staff/fbavera/papers/TesisJTLex-Bavera-Nordio-02.pdf
Redacción. (01 de 02 de 2021). Definición de Programa. Obtenido de https://conceptodefinicion.de/programa/
Rock Content. (20 de 04 de 2019). rockcontent. Obtenido de https://rockcontent.com/es/blog/que-es-un-lenguaje-de-programacion/