UVG_DLP_Regex-NFA

Facultad de Ingeniería
Departamento de Ciencias de la Computación
CC3071 - Diseño de Lenguajes de Programación
Ma. Isabel Solano 20504

Índice

• Sobre el Laboratorio
• Objetivos
• Dependencias
• Funciones
• Modo de uso
• Tecnologías

Sobre el Laboratorio

Se buscba desarrollar una implementación de algoritmos para la construcción de autómatas finitos no deterministas a partir de una expresión regular dada. Para ello se utiliza la construcción de Thompson.

Objetivos

• Generales
  • Implementación de algoritmos básicos de autómatas finitos no deterministas y expresiones regulares.
  • Desarrollar una sección para la base de la implementación del generador de analizadores léxicos.
• Específicos
  • Conversión de una expresión regular en notación infix a notación postfix. Puede utilizar el algoritmo Shunting Yard.
  • Implementación del algoritmo de Construcción de Thompson.
  • Generación visual de los AF.

Dependencias

Para el correcto uso del programa, es necesario que se tenga instalado GraphViz (Descarga graphviz-7.1.0 (64-bit) EXE installer) y que dot sea una variable del sistema.

Funciones

• Identificación de ingreso de input incorrecto
• Conversión de una expresión infix a postfix
• Determinación del alfabeto del lenguaje a partir de la expresión ingresada
• Construcción de árbol sintáctico a partir de expresión postfix
• Construcción de AFN por Thompson y por subconjuntos basados en el árbol sintáctico
• Graficación del AFN con ayuda de GraphViz

Modo de uso

Input:
Expresión regular con los operadores '|', '.', '+', '-', '?'

Correr:

• javac src/Controller.java
• java src/Controller

Output: (ab)|(a?b+a*)

Tecnologías