simposio de investigaciÓn...
TRANSCRIPT
SIMPOSIO DE INVESTIGACIÓN USTAMED
LIBRO DE RESÚMENES
SIMPOSIO DE INVESTIGACIÓN USTAMED
LIBRO DE RESÚMENES
28 de octubre de 2016
UNIVERSIDAD SANTO TOMÁS, SEDE MEDELLÍN
Comité Académico: Ángela María Jaramillo Londoño, Camilo Andrés Flórez Velásquez, Luis Hernando
Giraldo, Juan Fernando Valencia, María Isabel Cuartas Giraldo.
Compiladores: Camilo Andrés Flórez Velásquez, Ángela María Londoño Jaramillo.
Universidad Santo Tomás, 2016
Carrera 82 N0. 77 BB 27.
Medellín, Colombia.
Teléfono: (574) 2341034, Ext. 290.
www.ustamed.edu.co
ISSN: 2463-0489 (En línea)
Volumen III
Desarrollo de una estación meteorológica autónoma alimentada con energía
solar para la evaluación de microclimas. 767
Revisión geotectónica y sismológica del sector norte del sistema de fallas de
Algeciras, Colombia. 778
Análisis de las amenazas naturales producidas por el río Ocoa, en Villavicencio
- Meta- Colombia. 788
Implementación nodo principal de red libre. 792
Ultrasonidos de diferentes frecuencias con Arduino y su influencia en el
comportamiento de la broca de café. 797
Diseño de un analizador léxico y un analizador de expresiones para
interpretación de lenguaje. 800
Análisis comparativo de servidores de IPTV para una red NGN para propósitos
académicos. 809
Caracterización de los procesos de remoción en masa como variable
fundamental para la evaluación de amenaza sobre la ladera del río Guatiquía,
costado izquierdo por la vía antigua Villavicencio – Restrepo.
812
Diseño y desarrollo de una plataforma web e - learning con ChatBot para el
aprendizaje interactivo de la teoría de grafos. 824
Marco referencial para el diseño de la infraestructura de datos para una red
NGN para propósitos académicos. 829
Desarrollo de modelos computacionales para el estudio de las variables de
flujo aplicables al diseño de un sistema de monitoreo de tuberías con sensores
de fibra óptica.
832
Diseño y construcción de un sistema de control para una silla de ruedas
mediante señales electrooculográficas para personas con discapacidad motriz. 839
Reconocimiento de señales de tránsito utilizando visión artificial y Python de
Raspberry – Pi, para el control automático de un vehículo diseñado a pequeña
escala.
844
Fijación de dióxido de carbono en carbonatos lineales – Caso dietil carbonato. 850
Brazo robótico con sistema inteligente para detectar y retirar productos
defectuosos en una línea de producción. 859
SmartHomeController, un sistema de control parental y de consumo que ayuda
a ahorrar energía: Controlador y una app para el móvil. 864
Análisis del crecimiento de la estrategia de formación por proyectos en la
Facultad de Ingeniería de la Corporación Universitaria Americana. 868
Usabilidad de la computación en la nube: El caso de la Uniremington. 874
Diseño conceptual de un sistema aéreo no tripulado de ala rotatoria para la
detección de minas antipersonales. 888
Funcionalidad de la tecnología de exoesqueletos y los requerimientos de
movilidad de las personas con discapacidad motriz de miembros inferiores de 898
800
Diseño de un analizador léxico y un
analizador de expresiones para
interpretación de lenguaje Julián Galeano Echeverri 118
Oscar Ignacio Botero Henao 118
Ramiro Antonio López Sánchez 118
Resumen La interpretación del lenguaje escrito es una de las disciplinas con una amplia aplicación en
las áreas de paleontología, computación y la lingüística, entre otras. Para ello se utilizan los
compiladores, que son programas de computador que se encargan de traducir un lenguaje de
alto nivel a otro de bajo nivel, o en lenguaje precompilado (JIT, Just in time), que toma como
entrada un programa escrito legible para los humanos o de alto nivel y generará un lenguaje
equivalente entendible para la máquina objetivo, es decir, código escrito como instrucciones
correspondientes al dispositivo en la cual se ejecutará, basado en la arquitectura u otro
lenguaje de salida.
En este proceso de interpretación o traducción mediante un proceso de fragmentación se
identifican los tokens que componen una cadena léxica. Los tokens son como las palabras de
un lenguaje natural: cada fragmento es una secuencia de caracteres que representa una unidad
de información en el programa fuente, brindando el desarrollo de la primera fase para la
interpretación de lenguajes. El analizador léxico busca en la cadena analizada, coincidencia de
patrones a través de diferentes métodos como expresiones regulares y los autómatas finitos.
Dichos métodos son necesarios ya que esta etapa de interpretación debe funcionar de forma
eficiente y responder en el menor tiempo posible con una mayor eficiencia en sus líneas de
código. Ambos algoritmos fueron implementados para efectos de validación del rendimiento
con respecto al tiempo de cada token (palabra).
Como resultado este componente de software brindará los tokens para su confrontación con
un diccionario albergado en una base de datos, el cual recuperará el campo con su respectiva
descripción.
Introducción
La Institución Universitaria Pascual Bravo apoya este tipo de investigaciones con el
fin de garantizar el ejercicio efectivo de los derechos legales de las personas con
limitaciones físicas, y así mismo, garantizar el acceso real y efectivo de dichas
118 Programa de Tecnología Electrónica y Afines, Grupo en Investigación de Ciencias Electrónicas e Informáticas, Institución
Universitaria Pascual Bravo, Medellín. Correo electrónico: [email protected]
801
personas y a sus familiares a los diferentes servicios sociales que se ofrecen al resto
de ciudadanos.
Dentro del marco normativo, la I.U. Pascual Bravo debe dar cumplimiento a una
serie de leyes que se refieren al tema de la inclusión social a las personas con
limitaciones físicas, como es la Ley 1618 de 2013 y con este proyecto claramente se
apunta al artículo 5° de la ley antes mencionada, la cual reza:
“Las entidades públicas del orden nacional, departamental, municipal,
distrital y local, en el marco del Sistema Nacional de Discapacidad, son
responsables de la inclusión real y efectiva de las personas con discapacidad,
debiendo asegurar que todas las políticas, planes y programas, garanticen el
ejercicio total y efectivo de sus derechos, de conformidad con el artículo 3o
literal c), de Ley 1346 de 2009” (República de Colombia, 2013).
¿El analizador léxico y analizador de expresiones pueden mejorar la interacción de
los seres humanos, ayudando a promover la inclusión social?
Es evidente que la tecnología produce beneficios para el proceso de enseñanza –
aprendizaje en todas las áreas, es por ello que haciendo uso de HCI se pueden
presentar mejoras en el aprendizaje y por ende en las actividades cotidianas. “HCI
ofrece muchas teorías relevantes que son significativas en el contexto del aprendizaje
y la recuperación de los conocimientos” (HCI provides many relevant theories that are
significant in the context of learning and retrieval of knowledge) (Crearie, 2013, pág.
99).
El programa surge con el objetivo de contribuir a la integración social de la
población con discapacidades visual o auditiva, por la vía de abrir oportunidades
laborales para este sector social. Por ello, se busca facilitar a que las personas de esta
población adquieran herramientas para depender menos de otras. De igual forma el
estudio de los compiladores, ayuda por otra parte a comprender mejor la estructura
de los lenguajes de programación y compiladores actuales. El desarrollo de un
analizador léxico no parece tener un paso para su desarrollo y se convierte en un
tema para empresas desarrolladores de software. Se espera que la implementación de
este software se convierta en parte esencial de un desarrollo mayor como lo es un
traductor a lenguaje braille.
Existen analizadores léxicos y analizadores sintácticos disponibles tipo GNU, como
lo son LEX & YACC, los cuales ahorrarían el desarrollo propuesto, pero con el fin de
indagar en el funcionamiento y desarrollo propio de este tipo de aplicaciones, se
procede a su implementación. Además de permitir verificar los tiempos de ejecución y
802
desempeño al utilizar desarrollos propios o reutilizar componentes elaborados por
terceros, ahondando en la enseñanza del campo de los compiladores y la
aproximación a el entendimiento del lenguaje aplicado en autómatas.
Los generadores de análisis sintácticos ANTLR o Bison parecen ser una gran
herramienta, pero en algunas ocasiones reportan errores donde no los hay, ya que
son palabras correctas, esto debido a un conflicto con la gramática del lenguaje de
partida, para remediar dicho inconveniente hay que realizar cambios en la sintaxis
para poder acomodarlo y que no muestre esos errores (Musing Mortoray, 2012).
El lenguaje español, tiene una gran riqueza, deriva de las lenguas romances y las
leyes de construcción gramatical para nuestro lenguaje distan de otras lenguas como
el inglés en aspectos como el conjugar los verbos. Toda esta riqueza añade
complejidad y fue uno de los mayores temores antes de iniciar este desarrollo, sin
contar el ver a google realizar estas tareas de una manera sencilla.
La utilización del analizador léxico, en el proyecto tendrá la función de identificar
las palabras que pueden ser traducidas a otro lenguaje, a pesar de su complejidad
evaluando estructura y forma de construcción de la sintaxis. Adicionalmente en la
figura 1 se presenta una máquina de estado finito de la estructura gramática de la
oración en español.
Figura 1. Máquina de estado finito de la estructura gramática de la oración en español. La imagen fue
elaborada por los autores.
Metodología Empleada
El objetivo de un compilador es traducir un programa escrito en un lenguaje
“fuente”, en otro equivalente denominado lenguaje “objeto”. Si el programa fuente es
803
correcto, podrá ejecutarse la traducción; si no, se obtendrá un mensaje de error que
permita determinar cuál es el error. Dicha traducción podrá hacerse de dos formas:
interpretación (traducción “frase a frase”) y compilación: la traducción se hace del
texto completo (González, s.f.).
El entorno de un compilador está conformado por: la estructura del programa
fuente que se escribe utilizando algún programa de edición de texto en el que puede
ser incluido texto en lenguaje fuente y órdenes para el preprocesador (ej.: eliminación
de comentarios, expansión de macros = #IF, sustitución de constantes = #define,
inclusión de archivos = #include, y otros). Ahora, dicho compilador traducirá los
resultados del preproceso, generando un programa equivalente en lenguaje
ensamblador, que posteriormente será traducido por el mismo a lenguaje de máquina
relocalizable y finalmente, el editor de carga y enlace (link) solucionará las llamadas a
rutinas por medio de bibliotecas, ofreciendo el código de máquina final y ejecutable.
Cabe anotar que no siempre es necesario todo el proceso. En la figura 2 se observa el
diagrama en bloques.
Figura 2. Diagrama en bloque del entorno de un compilador. La imagen fue elaborada por los
autores.
La estructura de un compilador abarca dos grandes tareas: el análisis que examina
el programa fuente para dividirlo en componentes y obtener su significado,
normalmente en una estructura jerárquica, de árbol, en la que cada nodo representa
una operación y cuyos hijos son los argumentos de dicha operación; síntesis donde el
significado se convierte en lenguaje objeto y requiere técnicas de mayor complejidad.
Cada una de las tareas obtiene representaciones intermedias, en el análisis se divide
en tres fases: análisis léxico, sintáctico y semántico; y la síntesis en: generación de
código intermedio, optimización de código y generación de código. Cada una de las 6
fases está en capacidad de detectar errores e informarlos. Ver figura 3.
804
Figura 3. Estructura de un compilador. La imagen fue elaborada por los autores.
A continuación se hará una descripción breve de cada fase (Serna, 2011):
- Analizador léxico: lee la secuencia de caracteres de izquierda a derecha del
programa fuente y los agrupa en unidades con significado propio o “tokens”.
- Análisis sintáctico: determina si la secuencia léxica sigue la sintaxis del
lenguaje y adquiere la estructura jerárquica en forma de árbol.
- Análisis semántico: realiza comprobaciones al árbol sintáctico y determina el
correcto significado del programa.
- Generación de código intermedio: consiste en la calibración del árbol
sintáctico.
- Optimización del código: genera un código mejorado, más fácil de traducir a
código ensamblador o máquina.
- Generación de código objeto: toma como entrada la representación
intermedia y genera el código objeto final.
Para el caso en particular de este desarrollo, fue implementado un analizador de
expresiones teniendo en cuenta la funcionalidad de separar por tokens las palabras
válidas y ésta en letras, para la implementación. Por análisis de eficiencia del
algoritmo tenemos OE con 5(log5), para nuestro primer desarrollo realizado con el
analizador de expresiones. Luego realizamos el análisis del algoritmo para nuestra
implementación del analizador léxico, el cual es recurrente y tenemos OE con
10(Log10). Con estos dos análisis se procede a realizar la prueba directa por
ejecución tomando los tiempos de inicio y restando a los finales.
805
En la implementación del algoritmo del analizador léxico, tenemos el siguiente
seudocódigo:
Inicio (1)
Longitud_cadena = longitud(entrada_de_texto) (2)
Para (i=1; i<=Longitud_cadena; i++) (3)
carácter_analizado = buscar(siguiente) (4)
Si (carácter_analizado <> vacío) entonces (5)
Buscar=Encontrar(carácter_ analizado) (6)
Si (Buscar = OK) entonces (7)
Escribir “Carácter encontrado!” (8)
De lo contrario (9)
Escribir “Carácter no encontrado!” (10)
Fin si (11)
Fin si (12)
Fin Para (13)
Fin (14)
Para determinar el tiempo de ejecución, calcularemos primero el número de
operaciones elementales (OE) que se realizan:
- La línea 1, no tiene ninguna incidencia.
- La línea 2, es una asignación y el llamado a una función (f(n))
- La línea 3, está conformada por una asignación y una validación para ingreso
a ciclo: 2 OE.
- La línea 4, es una función y una asignación (f(n))
- La línea 5, es una comparación
- La línea 6, es una asignación y el llamado a función (f(n))
- La línea 7, es una comparación
- La línea 8, impresión
806
- La línea 9, continuación de condicional
- La línea 10, impresión.
- La línea 11, cierra el condicional
- La línea 12, cierra el segundo condicional.
- La línea 13, retorna a la línea 3, para validar el ciclo, excepto cuando finalice
el mismo.
Las implementaciones construidas permiten identificar las siguientes valoraciones
para los algoritmos: Tabla 1. Tiempos y fórmula de eficiencia. Fuente propia
Implementación Cadena de Carácter
(50)
Cadena de
Carácter (100) Fórmula
Analizador Léxico 15.59 22.21 3(f(n))+14
Analizador de
Expresión
19.64 25.78 3(n(log3))
Lex & Yacc 15.23 20.53 3(n(log5))
Nota: Datos obtenidos bajo la implementación realizada para cada algoritmo en C#.
Dentro de la valoración del tiempo en ejecución, debe ser considerado la velocidad
de los compiladores de acuerdo a cada lenguaje de programación. Los tiempos
proporcionales de acuerdo a los lenguajes de programación aparecen en la tabla 2.
807
Tabla 2. Tiempos para cada lenguaje de programación.
Lenguaje Tiempo Relativo Detalles
C 1 GCC 5
Visual Basic 6.0 1.132 Bajo
optimizaciones
Visual Basic .NET 0.866 Bajo
optimizaciones
C# 0.29 Optimizado
Java 1.121 Sun JDK 7
Nota: fuente (Olaru, Hangan , & Sebestyen-Pal, 2011)
Basados en la Ley de Moore, la capacidad de procesamiento tiende a duplicarse
cada 18 meses aproximadamente y desde la institución de esta ley los tiempos han
bajado a menos de 12 meses, sin embargo, dentro de la investigación debemos
proporcionar la evaluación y caminos a la mejora del algoritmo y no solucionar los
problemas de eficiencia a través del uso de mayor procesamiento. (James, 2016)
Bajo esta premisa, es bueno considerar también la variación de arquitecturas como
la de multiprocesador. Por ejemplo, si el componente secuencial de un algoritmo es
1/s de su tiempo de ejecución, entonces la aceleración máxima posible que puede
alcanzar en el computador paralelo es s. El tiempo para realizar el cómputo con P
procesadores es:
Donde ts es el tiempo de ejecución secuencial.
Según la ley de Amdahl, si un programa tiene un 5% de componente secuencial
entonces la aceleración máxima que se puede alcanzar es de 20. (Huang et al, 2008)
Sin embargo, sabemos que el hecho de utilizar más procesadores no hará que la
aplicación corra necesariamente tan rápido como procesadores agreguemos (por
tiempos de procesamiento y comunicación entre núcleos y demás tiempo de ocio),
además, apenas se viene trabajando en poder llevar a procesamiento en paralelo la
evaluación de los tokens. Esto mejoraría la velocidad de respuesta del algoritmo, pero
aún se desconoce cuánto y continuaría siendo una solución por capacidad de
procesamiento y no de mejora en el algoritmo.
808
Resultados y Conclusiones
La implementación realizada a través de consulta de tokens, parece ser lo
suficientemente eficiente para ser utilizado en el proyecto, así lo demuestra las
valoraciones asintóticas y la evaluación práctica basa en tiempos de ejecución, y
permitirá dar continuidad a la integración de los demás componentes del traductor
propuesto, no sin antes verificar como se puede mejorar los tiempos de respuesta sin
utilizar una mejora en el hardware.
Una de las pruebas pendientes por realizar, es la de verificar cómo se comporta el
algoritmo al ser ejecutado en un ambiente multiprocesador, dividiendo hilos de
procesos y juntándolo de nuevo en un coordinador, esto sin lugar a dudas puede
generar un aumento en la velocidad de ejecución, pero es totalmente dependiente de
las líneas que puedan ser llevadas a paralelismo.
Los próximos desarrollos están encaminados indagar en la creación del analizador
sintáctico, el cual será el encargado de verificar el correcto orden de las palabras
basadas en estructuras definidas del lenguaje destino o gramática.
Referencias
Crearie, L. (2013). ICICTE Proceedings. Obtenido de Human Computer Interaction (HCI) factors in
Technology Enhanced Learning:
http://www.icicte.org/Proceedings2013/Papers%202013/03-3-Crearie.pdf
González, L. (s.f.). Introducción a la construcción de compiladores. Obtenido de Universidad de
Valladolid: http://www.infor.uva.es/~mluisa/talf/docs/aula/A7.pdf
Huang et al, Z. (2008). Virtual Aggregated Processor in Multi-core Computers. Ninth International
Conference on Parallel and Distributed Computing, Applications and Technologies, 481-
488.
James, D. (2016). Moore's law continues into the 1x-nm era. 27th Annual SEMI Advanced
Semiconductor Manufacturing Conference (ASMC), 324-329.
Musing Mortoray. (20 de 07 de 2012). Obtenido de https://mortoray.com/2012/07/20/why-i-
dont-use-a-parser-generator/
Olaru, V., Hangan , A., & Sebestyen-Pal, G. (2011). Java Support Packages and Benchmarks for Multi-
core Processors. High Performance Computing and Communications (HPCC), 528-535.
Serna, E. (2011). Universidad Autónoma de Aguascalientes. Obtenido de Introducción a
compiladores:
http://www.paginasprodigy.com/edserna/cursos/compilador/notas/Notas1.pdf