Project summary
PLQuiz is a desktop application that creates problem sheets or questionnaires about the usage of lexical
analysis algorithms.
The questionnaires are presented in a Moodle-compatible format or print-ready, including high resolution
images in vector format.
The exercise can be built from a user-provided regular expression, or automatically generated via search and
genetic algorithms.
Resumen del proyecto
PLQuiz es una aplicación que permite generar cuestionarios sobre el uso de algoritmos de análisis léxico.
Los cuestionarios se presentan en formato compatible con Moodle o preparados para imprimir, incluyendo
imágenes de alta resolución utilizando gráficos vectoriales.
Los ejercicios pueden generarse a partir de una expresión regular dada o de manera automática, utilizando
algoritmos de búsqueda aleatoria y genéticos.
Aho-Sehi-Ullman algorithm
Calculate a set of functions from the syntax tree of the regular expression, and use them to generate the
corresponding automata transition table.
The functions are:
- First-pos: set of positions corresponding to the first possible symbols in the matched strings.
- Last-pos: set of positions corresponding to the last symbols.
- Follow-pos: set of positions after a given position in the expression.
Algoritmo de Aho-Sehi-Ullman
Calcula una serie de funciones a partir del árbol sintáctico de la expresión regular, utilizándolas para generar la tabla de transición del autómata.
Las funciones calculadas son:
- Primera-pos: conjunto de posiciones que corresponden con los primeros símbolos posibles en las cadenas que define.
- Última-pos: conjunto de posiciones que corresponden con los últimos símbolos.
- Siguiente-pos: conjunto de posiciones que siguen a una posición dada en la expresión.
McNaughton-Yamada-Thompson algorithm
Uses a regular expression to build the deterministic finite automaton that represents the same language.
The expression's syntax tree is traversed recursively to build the automata, composing each node from tree
automata of the nodes below.
Algoritmo de McNaughton-Yamada-Thompson
Utiliza una expresión regular para obtener un autómata finito determinista que define el mismo lenguaje.
Para construir el autómata recorremos el árbol sintáctico de la expresión recursivamente, construyendo el autómata correspondiente a cada nodo a partir de los autómatas de los nodos inferiores.
Generation of exam questions
The application uses search algorithms to generate regular expression corresponding to a given type and
problem attributes.
The possible attributes that define a problem are:
- If it contains the empty string.
- The number of different symbols available.
- The number of states in the corresponding transition table.
The Aho-Sethi-Ullman exercises use random search algorithms, while the McNaughton-Yamada-Thompson use a
genetic algorithm.
Generación de cuestiones
La aplicación utiliza algoritmos de búsqueda para generar expresiones regulares que correspondan con un problema de un tipo y características dadas. Las características que determinan el problema a generar son:
- Si contiene o no la cadena vacía.
- El número de símbolos diferentes que contiene.
- El número de estados en su tabla de transición correspondiente.
Los problemas de resolución de problemas del algoritmo de Aho-Sethi-Ullman utilizan un algoritmo de búsqueda aleatoria, los de McNaughton-Yamada-Thompson un algoritmo genético.
Questionnaires
The application generates questionnaires in three possible formats:
- HTML + CSS, used in the user interface to display a preview.
- Latex, used to generate print-ready questionnaires to use as exams or problem sheets.
- Moddle XML, used to generate questionnaires that can be easily imported in the e-learning platform.
and also generates images in three possible formats:
- As regular image files, generated by default when exporting as a Latex document.
- As a dot program compatible with Graphviz, as an option when
exporting as Latex document.
- As a 64-bit string, to insert images inside XML documents.
Cuestionarios
La aplicación genera cuestionarios en tres posibles formatos:
- HTML + CSS, utilizado dentro de la propia aplicación para mostrar una vista previa del cuestionario.
- Latex, utilizado para generar cuestionarios que puedan imprimirse en papel, como exámenes.
- Moodle XML, utilizado para generar cuestiones que pueden importarse en la plataforma de aprendizaje virtual.
y imágenes en otros tres formatos distintos:
- Formato de fichero de imagen común, generado al exportar documentos Latex por defecto.
- Formato de programa dot compatible con Graphviz, generado al exportar documentos Latex de manera alternativa.
- Formato de cadena de texto de 64 bits, que permite codificar la imagen dentro de documentos XML.
